LeetCode每日一题之2023年3月份

Posted on Edited on In Views:
数据结构和算法是很重要的，无论是在工作过程中还是在面试笔试中。这里记录LeetCode每日一题。

2023年03月01日

2373. 矩阵中的局部最大值

解法1：滑动窗口，有限数组。

使用一个有限数组记录3x3中的数字，滑动窗口的时候，变更有限数组中的数字，获取最大值。

优化点：使用更好的数据结构替换有限数组，在删除和插入的时候，可以直接排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func largestLocal(grid [][]int) [][]int {
    n := len(grid)
    res := make([][]int, 0, n-2)
    for i := 0; i < n-2; i++ {
        var tmp [101]int
        tmpRes := make([]int, 0, n-2)
        // 先记录一次
        for j := 0; j < 3; j++ {
            tmp[grid[i][j]]++
            tmp[grid[i+1][j]]++
            tmp[grid[i+2][j]]++
        }
        tmpRes = append(tmpRes, max(tmp))
        // 后面使用滑动窗口
        for j := 1; j < n-2; j++ {
            tmp[grid[i][j-1]]--
            tmp[grid[i+1][j-1]]--
            tmp[grid[i+2][j-1]]--
            tmp[grid[i][j+2]]++
            tmp[grid[i+1][j+2]]++
            tmp[grid[i+2][j+2]]++
            tmpRes = append(tmpRes, max(tmp))
        }
        res = append(res, tmpRes)
    }
    return res
}

func max(tmp [101]int) int {
    for i := 100; i >= 0; i-- {
        if tmp[i] > 0 {
            return i
        }
    }
    return 0
}

2023年03月02日

面试题 05.02. 二进制数转字符串

解法1：按照二进制的思想，一个数的二进制，是2的次方相加，那么小数就是2的负的次方相加。

为了好计算，可以将数字乘以2，每次乘以2，都代表是二进制的前一位。例如0.625=0.5+0.125=2^(-1)+2^(-3)=0.101；0.625*2=1.25，提取前面的1,0.25*2=0.5，提取前面的0，0.5*2=1，提取前面的1，并且num=0，则结束。按照提出来的顺序，也就是101，最后加上前缀0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func printBin(num float64) string {
   s := strings.Builder{}
   s.WriteString("0.")
   var size int

   for size < 32 && num != 0 {
      num *= 2
      s.WriteString(strconv.Itoa(int(num)))
      num = num - float64(int(num))
      size++
   }
   if size < 32 {
      return s.String()
   }
   return "ERROR"
}

2023年03月03日

1487. 保证文件名唯一

解法1：使用HashMap记录每个写入的文件夹。

这个解法会超时。

优化：HashMap的value记录前缀的个数，减少HashMap的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func getFolderNames(names []string) []string {
    l := len(names)
    res := make([]string, l)
    all := make(map[string]int, l)

    for i := 0; i < l; i++ {
        size := all[names[i]]
        if size == 0 {
            res[i] = names[i]
            all[names[i]]++
            continue
        }

        for j := size; j < l; j++ {
            tmp := names[i] + "(" + strconv.Itoa(j) + ")"
            tmpSize := all[tmp]
            if tmpSize == 0 {
                res[i] = tmp
                all[names[i]] = j + 1
                all[tmp]++
                break
            }
        }
    }
    return res
}

解法2：使用字典树

2023年03月04日

982. 按位与为零的三元组

解法1：暴力枚举，三重循环。这种方式会出现超时。解决超时的方法，可以使用HashMap记录二重循环的值，减少重复的数据。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func countTriplets(nums []int) int {
   m := len(nums)
   tmp := make(map[int]int)
   for i := 0; i < m; i++ {
      for j := 0; j < m; j++ {
         tmp[nums[i]&nums[j]]++
      }
   }
   var res int
   for i := 0; i < m; i++ {
      for k, v := range tmp {
         if nums[i]&k == 0 {
            res += v
         }
      }
   }

   return res
}

后续优化思路：耗时主要是在hash，由于nums[i] < 2¹⁶，因此，可以将HashMap改成有限数组，减少hash的时间，以及记录有数字的数组位置，进一步优化便利数组的时间。

2023年03月05日

1599. 经营摩天轮的最大利润

解法1：按照测试用例分析即可，记录登船者、等待者个数，以及每次转动之后的利润，以及利润的最大值和此时的转动次数。先便利数组，记录所有游客登录的情况，再讨论如果有剩余的游客的情况。如果最大值等于0，说明没有盈利的情况，返回-1，如果非0，则说明有最佳盈利的情况，返回对应转动次数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
   res := 0
   max := 0
   var board, wait, profit int
   for i := 0; i < len(customers); i++ {
      wait += customers[i]
      if wait >= 4 {
         board += 4
         wait -= 4
      } else {
         board += wait
         wait = 0
      }
      profit = board*boardingCost - (i+1)*runningCost
      if profit > max {
         max = profit
         res = i + 1
      }
   }

   tmpOper := len(customers)
   for wait > 0 {
      tmpOper++
      if wait >= 4 {
         profit += 4*boardingCost - runningCost
      } else {
         profit += wait*boardingCost - runningCost
      }
      if profit > max {
         max = profit
         res = tmpOper
      }
      wait -= 4
   }

   if max == 0 {
      return -1
   }

   return res
}

2023年03月06日

1653. 使字符串平衡的最少删除次数

解法1：使用dp，将问题缩小为重复性的子问题。

  • 如果结尾是a，则要么将这个a删掉，要么把前面所有的b删掉，取最小值；
  • 如果结尾是b，则一定是合法的，加上b的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minimumDeletions(s string) int {
    length := len(s)

    // dp，记录对应长度字符串的最小变化次数
    dp := make([]int, length)
    // 并且记录b的次数
    var b int
    // 初始化条件，只有一个字符的时候，肯定是0次
    // 如果初始字符是b，则b为1
    if s[0] == 'b' {
        b++
    }
    // 变化条件，如果是a，则要么将这个a删掉，要么把前面所有的b删掉，取最小值
    // 如果是b，则一定是合法的，加上b
    for i := 1; i < length; i++ {
        if s[i] == 'a' {
            dp[i] = min(dp[i-1] + 1,b)
        } else {
            dp[i] = dp[i-1]
            b++
        }
    }

    return dp[length-1]
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

2023年03月07日

1096. 花括号展开 II

解法1：我自己的解法写得复杂了，使用的是字符串拼接，从左到右平推，切片和切片双循环遍历，字符串拼接后面括号内的字符串，这个解法不推荐，复杂而且会超时。

解法2：使用dfs，通过括号找到需要拆开的字符串，将括号的内容提取出来，拼接上括号之前和反括号之后的内容，将新的内容作为一个子问题，将结果放到map中去重，最后便利map然后排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func braceExpansionII(expression string) []string {
    s := map[string]struct{}{}
    var dfs func(string)
    dfs = func(exp string) {
        // 找到第一个反括号
        j := strings.Index(exp, "}")
        // 没有找到反括号，说明是单独的字符串，放到map中去重
        if j == -1 {
            s[exp] = struct{}{}
            return
        }
        // 找到第一个反括号前面的第一个括号，这两者中间就是子问题
        i := strings.LastIndex(exp[:j], "{")
        // 将括号前面+便利的子问题+反括号后，作为新的字符串，进行递归处理
        a, c := exp[:i], exp[j+1:]
        for _, b := range strings.Split(exp[i+1:j], ",") {
            dfs(a + b + c)
        }
    }
    dfs(expression)
    // 将map中的字符串放到切片中，并且排序
    ans := make([]string, 0, len(s))
    for k := range s {
        ans = append(ans, k)
    }
    sort.Strings(ans)
    return ans
}

2023年03月08日

剑指 Offer 47. 礼物的最大价值

解法1：使用dp，二维数组，代表对应位置下的最大值。当i=0或者j=0时，只能有一个方向，初始化的时候直接获取对应价值。dp状态转移方程是dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maxValue(grid [][]int) int {
    m, n := len(grid), len(grid[0])

    // 定义dp，代表对应格子的最大值
    dp := make([][]int, m)
    dp[0] = make([]int, n)
    // 初始化，第0，0格的价格对应
    dp[0][0] = grid[0][0]
    for i := 1; i < n; i++ {
        dp[0][i] += dp[0][i-1] + grid[0][i]
    }
    for i := 1; i < m; i++ {
        dp[i] = make([]int, n)
        dp[i][0] += dp[i-1][0] + grid[i][0]
        for j := 1; j < n; j++ {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        }
    }

    return dp[m-1][n-1]
}

func max(i int, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}

2023年03月09日

2379. 得到 K 个黑块的最少涂色次数

解法1：其实是求解滑动窗口中W的最大个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func minimumRecolors(blocks string, k int) int {
    size, res := 0, k
    for i := 0; i < k; i++ {
        if blocks[i] == 'W' {
            size++
        }
    }
    if size < res {
        res = size
    }

    for i := k; i < len(blocks); i++ {
        if blocks[i] == 'W' {
            size++
        }
        if blocks[i-k] == 'W' {
            size--
        }
        if size < res {
            res = size
        }
    }
    return res
}

2023年03月10日

1590. 使数组和能被 P 整除

解法1：核心点是理解一个数学题。题目中的子数组是一个连续数组，因此，如果说总和的余数是rem，数组的尾索引是y，数组的头索引是x+1，则数组[0:x+1]总和的余数remX，数组[0:y+1]总和余数remY，这三者有这样的关系：

(remX + rem) % p = remY

那么便利数组的时候，通过y，可以求出x

remX = (remY + p - rem) % p

也就是说，遍历数组的时候，计算对应的当前和的对应余数，通过自己是remY求得remX的最新坐标，就是x和y的坐标，同时自己自己的rem作为remX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minSubarray(nums []int, p int) int {
   var sum int
   for i := 0; i < len(nums); i++ {
      sum += nums[i]
   }
   rem := sum % p

   if rem == 0 {
      return 0
   }

   res := len(nums)
   // (y+x) % p = rem
   // x = (p+rem - y ) % p
   allRem := map[int]int{0: -1}
   sum = 0
   for i := 0; i < len(nums); i++ {
      sum += nums[i]
      tmpRem := sum % p
      last := (tmpRem + p - rem) % p
      if v, ok := allRem[last]; ok {
         temRes := i - v
         if temRes < res {
            res = temRes
         }
      }
      allRem[tmpRem] = i
   }

   if res == len(nums) {
      return -1
   }
   return res
}

优化点：将HashMap改成数组，可以节省时间。

2023年03月11日

面试题 17.05. 字母与数字

解法1：前缀和。解法核心与昨天一样，如果是字母，则+1，如果非字母，则-1，那么最长的子子数组，左边的字母数等于右边的子母数。与昨天不一样的是记录第一次出现的字母数即可。那么第一次出现0的，就是-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func findLongestSubarray(array []string) []string {
   all := map[int]int{0: -1}

   var num, max int
   var res []string
   for i := 0; i < len(array); i++ {
      if unicode.IsLetter(rune(array[i][0])) {
         num++
      } else {
         num--
      }
      if v, ok := all[num]; ok {
         tmp := i - v
         if tmp > max {
            max = tmp
            res = array[v+1 : i+1]
         }
      } else {
         all[num] =  i 
      }
   }

   return res
}

2023年03月12日

1617. 统计子树中城市之间最大距离

解法1：先通过数组，将树构建出来。然后使用递归，选择城市，也就是说每个城市都可以选择是否被选择，自己是否被选择，然后+后面的城市的情况，在这种所有城市组合的情况下，通过dfs求：解这个树的直径，然后放到结果中。需要注意的是，递归树的时候，递归出来的树，需要与被递归的树的集合相等，这样的话就代表所有的节点都被递归到。

解法2：与解法1差不多，区别是选择城市组合的方式，使用二进制。

核心点：

  1. 求解树的直径，使用dfs求解，方法：
    1. 先取任意一个节点，找到距离这个节点最远的节点x，再找到x最远的节点，两个节点之间的距离就是最深的
    2. 取所有节点，获取所有节点的最长直径。这里选择这种情况
  2. 遍历所有节点，获取所有节点是否被选择的情况，方法：
    1. 使用递归，先选择本节点是否被选中，然后进入下一层，到最后一层时，进行求解树的直径
    2. 使用二进制，通过二进制映射到节点是否被选中，然后进行求解树的直径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
func countSubgraphsForEachDiameter(n int, edges [][]int) []int {
   // 建树，m代表城市编号，n是这个城市连接的编号，用于后面求解最长路径时快速便利
   g := make([][]int, n)
   for _, e := range edges {
      x, y := e[0]-1, e[1]-1 // 编号改为从 0 开始
      g[x] = append(g[x], y)
      g[y] = append(g[y], x)
   }

   // inSet保存要遍历的城市的个数
   // vis保存便利的时候已经遍历过的城市，不会出现反过头成环
   var inSet, vis [15]bool

   // dfs 求树的直径，使用递归dfs，返回对应节点x的最深深度，调用时，需要重置diameter
   var dfs func(int) int
   dfs = func(x int) (maxLen int) {
      vis[x] = true
      for _, y := range g[x] {
         if !vis[y] && inSet[y] {
            ml := dfs(y) + 1
            if ml > maxLen {
               maxLen = ml
            }
         }
      }
      return
   }

   ans := make([]int, n-1)
   // 方法1：递归选择城市
   //var f func(int)
   //f = func(i int) {
   // if i == n {
   //    for v, b := range inSet {
   //       if b {
   //          vis, diameter = [15]bool{}, 0
   //          dfs(v)
   //          break
   //       }
   //    }
   //    if diameter > 0 && vis == inSet {
   //       ans[diameter-1]++
   //    }
   //    return
   // }
   //
   // // 不选城市 i
   // // inSet[i] = false 其实不选城市设置为false放在这里，理解起来会更加简单
   // f(i + 1)
   //
   // // 选城市 i
   // inSet[i] = true
   // f(i + 1)
   // inSet[i] = false // 恢复现场，这里很重要，但是理解起来有点吃力，想等于在不选城市时，inSet[i] = false
   //}
   //f(0)

   // 方法2：使用二进制，选择城市
   for i := 0; i < 1<<n; i++ {
      var count int
      inSet = [15]bool{}
      for j := 0; j < n; j++ {
         if (i>>j)&1 == 1 {
            inSet[j] = true
            count++
         }
      }

      // 最起码有两个城市，才计算距离
      if count > 1 {
         // 通过for循环每一个城市，确定直径

         // 初始化最大距离
         var diameter int
         for j := 0; j < n; j++ {
            if inSet[j] {
               // 初始化便利过的节点
               vis = [15]bool{}
               tmp := dfs(j)
               if tmp > diameter && vis == inSet {
                  diameter = tmp
               }
            }
         }

         // 要确保所有节点都便利到，因此vis需要等于inSet
         if diameter > 0 {
            ans[diameter-1]++
         }
      }
   }
   return ans
}

func max(a, b int) int {
   if a < b {
      return b
   }
   return a
}

2023年03月13日

2383. 赢得比赛需要的最少训练时长

解法1：依次计算需要战胜对手时，需要的经历和经验即可。也就是说，可以在中途回过头去训练。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func minNumberOfHours(initialEnergy int, initialExperience int, energy []int, experience []int) int {
   var res int
   for i := 0; i < len(energy); i++ {
      initialEnergy = initialEnergy - energy[i]
      if initialEnergy < 1 {
         res = res - initialEnergy + 1
         initialEnergy = 1
      }
      if initialExperience <= experience[i] {
         res = res + experience[i] - initialExperience + 1
         initialExperience = experience[i] + 1
      }
      initialExperience += experience[i]
   }
   return res
}

2023年03月14日

1605. 给定行和列的和求可行矩阵

解法1：题目已经给出来一定有解决的方法，而且求解一种即可，那么就不需要使用递归或者迭代，进行回溯求解，而是使用贪心即可。问题的关键就是如何理解这个贪心。如果各自是1x1，那么就只有一种选择，如果格子是1x2，选择也只有一种，此时[0][0]是rowSum[0]和colSum[0]之间的最小值。也就是

1
res[i][j] = min(rowSum[i],colSum[j])

选择了一个数字之后，则修改对应的rowSum[i]和colSum[j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func restoreMatrix(rowSum []int, colSum []int) [][]int {
    res := make([][]int, len(rowSum))
    for i := 0; i < len(res); i++ {
        res[i] = make([]int, len(colSum))
    }

    for i := 0; i < len(res); i++ {
        for j := 0; j < len(res[i]); j++ {
            res[i][j] = min(rowSum[i], colSum[j])
            rowSum[i] -= res[i][j]
            colSum[j] -= res[i][j]
        }
    }

    return res
}

func min(i int, i2 int) int {
    if i < i2 {
        return i
    }
    return i2
}

2023年03月15日

1615. 最大网络秩

解法1：暴力解法，现状换成二维数组，记录每个城市相连的城市，先选出第一个连接数最多的城市，然后在其他城市中去掉该城市，然后再选出第二个连接数最多的城市。最终结果即使两个连接数相加。这个解法理解简单，但是写法比较麻烦

解法2：在解法1的基础上进行优化，一个二维数组记录城市之间是否连接，另外一个数组记录对应城市的连接数，最终结果就是便利数组，两个城市之间的连接数相加减去两个城市是否相连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maximalNetworkRank(n int, roads [][]int) int {
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }

    connection := make([]int, n)
    for _, road := range roads {
        x, y := road[0], road[1]
        dp[x][y], dp[y][x] = 1, 1
        connection[x]++
        connection[y]++
    }

    var res int
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            tmp := connection[i] + connection[j] - dp[i][j]
            if tmp > res {
                res = tmp
            }
        }
    }

    return res 
}

2023年03月16日

2488. 统计中位数为 K 的子数组

解法1：子数组，典型的前缀和问题，理解题目的核心点就是寻找前缀和的关系。

先将所有的数字做区分，要么是大于目标数字，要么是小于目标数字，要么是等于目标数字，也就是转换成-1,0,1的关系

1
2
3
xxxx     xxxxx      xxxx
       奇数情况，中间数组相加等于0
也就是说，左边数组的前缀和，等于右边数组的前缀和
1
2
3
xxxx     xxxx      xxxxxx
偶数情况，中间数组相加等于1
也就是说，左边数组的前缀和，等于右边数组的前缀和-1

而且题目要求包含k，则记录左边的前缀和到HashMap中，出现k，开始计算答案个数。

需要注意，要包含k本身作为1个答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func countSubarrays(nums []int, k int) int {
   var flag int
   for i := 0; i < len(nums); i++ {
      if nums[i] == k {
         flag = i
         break
      }
   }

   count := make(map[int]int) // 计数器
   // 保留一个等于自身的值
   count[0] = 1
   var res,c int
   for i := 0; i < len(nums); i++ {
      c += getCount(nums[i],k)
      if i < flag {
         count[c]++
      } else {
         // 结果为0，代表是相加是奇数的情况
         p0 := count[c]    // 等于对应数可以
         p1 := count[c-1]   // 等于对应数-1也可以
         res += p0+p1
      }
   }
   return res
}

func getCount(i int,k int) int  {
   if i > k {
      return 1
   } else if i < k {
      return -1
   }
   return 0
}

优化点：可以将两次遍历整合成一次，可以加速一点；将HashMap换成有线数组，也可以加速。

2023年03月17日

2389. 和有限的最长子序列

解法1：按照题目要求，不需要返回具体数组，只需要个数，而且子数组可以是任意组合，因此，可以先将数组进行排序，然后获取子数组的和，那么题目的答案，就变成寻找这个和里面最大的相加个数，也就是转换成前缀和的问题。

如果前缀和放到map里面，key放和，value放index，那么就需要便利target以及target小的数字，这种解法很容易超时。

因此可以转换思路，将map使用等长数组表示，数组的index就是nums的index，value是前缀和，那么target就可以通过二分法求解。

使用二分法的逻辑则是寻找这个数，如果存在，则返回index，如果不存在，则返回比这个数小的最大值的index，最终结果则是index+1。

重点：换一句话说，二分法求解的是，往这个数组中插入一个数字，插入后的index，但是需要相等的时候，结果是index+1，不相等的时候，则是index，因此还可以优化成插入这个数字+1，这样无论什么情况，返回的结果都是index。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func answerQueries(nums []int, queries []int) []int {
   sort.Ints(nums)
   all := make([]int, len(nums))
   var sum int
   for i := 0; i < len(nums); i++ {
      sum += nums[i]
      all[i] = sum
   }

   res := make([]int, len(queries))
   for i := 0; i < len(queries); i++ {
      res[i] = sort.SearchInts(all, queries[i]+1)
   }

   return res
}

这里补充一下golang的二进制检索代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
//
// For instance, given a slice data sorted in ascending order,
// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
// returns the smallest index i such that data[i] >= 23. If the caller
// wants to find whether 23 is in the slice, it must test data[i] == 23
// separately.
//
// Searching data sorted in descending order would use the <=
// operator instead of the >= operator.
//
// To complete the example above, the following code tries to find the value
// x in an integer slice data sorted in ascending order:
//
//    x := 23
//    i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
//    if i < len(data) && data[i] == x {
//        // x is present at data[i]
//    } else {
//        // x is not present in data,
//        // but i is the index where it would be inserted.
//    }
//
// As a more whimsical example, this program guesses your number:
//
//    func GuessingGame() {
//        var s string
//        fmt.Printf("Pick an integer from 0 to 100.\n")
//        answer := sort.Search(100, func(i int) bool {
//            fmt.Printf("Is your number <= %d? ", i)
//            fmt.Scanf("%s", &s)
//            return s != "" && s[0] == 'y'
//        })
//        fmt.Printf("Your number is %d.\n", answer)
//    }
func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}
1
2
3
4
5
6
7
// SearchInts searches for x in a sorted slice of ints and returns the index
// as specified by Search. The return value is the index to insert x if x is
// not present (it could be len(a)).
// The slice must be sorted in ascending order.
func SearchInts(a []int, x int) int {
   return Search(len(a), func(i int) bool { return a[i] >= x })
}

也就是往数组中插入一个数字，返回插入的这个数字的index。

2023年03月18日

1616. 分割两个字符串得到回文串

解法1：分析题意，拼接两个字符串，选择a的头和b的尾（也可以调换，选择a的尾和b的头），往中间移动，判断是否相同，如果相同，则说明可以切割，直到出现不同的字符，那么就需要判断如果此时切割a或者切割b后，是否可以组成新的回文串，也就是判断a[i:len-i]或者b[i:len-i]是否是回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func checkPalindromeFormation(a, b string) bool {
   return checkPalindrome(a, b) || checkPalindrome(b, a)
}

func checkPalindrome(a, b string) bool {
   for i := 0; i < len(a)>>1; i++ {
      if a[i] != b[len(a)-1-i] {
         return isPalindrome(b[i : len(a)-i]) || isPalindrome(a[i : len(a)-i])
      }
   }
   return true
}

func isPalindrome(a string) bool {
   for i := 0; i < len(a)>>1; i++ {
      if a[i] != a[len(a)-1-i] {
         return false
      }
   }
   return true
}

2023年03月19日

1625. 执行操作后字典序最小的字符串

解法1：BFS，准备一个HashMap，将所有会转换到的字符串放到map中，再将待转换的字符放到队列中，从队列中取出字符，进行换位，然后将所有位置相加，如果不在map中，则放到map中并且放到队列中。从队列中取出数字时，进行比较，获取最小字典序的数字。这里需要注意，为了确保所有的情况都能便利到，以及不会超时，采取的措施，最好是全部累加一次，轮转一次。

解法2：枚举，核心跟BFS差不多，就是枚举出所有可能出现的数字，如果是b是偶数，则只有偶数位可以累加，如果是奇数，则所有位数都可以相加，枚举出所有的可能结果，然后获取最小的即可。

解法1更好理解和好操作，解法2性能更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func findLexSmallestString(s string, a int, b int) string {
   all := map[string]bool{s: true}
   stack := []string{s}
   res := s
   for len(stack) > 0 {
      // 出栈
      s = stack[0]
      stack = stack[1:]
      // 比较
      if s < res {
         res = s
      }

      // 转换
      ss := []byte(s)
      s = s[len(s)-b:] + s[:len(s)-b]
      if !all[s] {
         all[s] = true
         stack = append(stack,s)
      }
      // 累加
      for i := 1; i < len(ss); i += 2 {
         ss[i] = byte((int(ss[i]-'0')+a)%10) + '0'
      }
      if !all[string(ss)] {
         all[string(ss)] = true
         stack = append(stack,string(ss))
      }
   }
   return res
}

2023年03月20日

1012. 至少有 1 位重复的数字

解法1：这里求至少重复，那么换句话来说，就是求没有重复的数字。重复的数字可以使用位运算来进行求解。使用递归，求解每一位都不重复时的次数。

这里需要注意，使用递归的时候，需要加速检索，不然会出现超时的情况。加速的时候，可以加速当12***的情况和21***的情况，因此需要有一个状态记录使用了某几个数字的时候的次数，最好是使用位数，来记录使用的数字。

并且在递归的过程中，记录已经使用的数字，后续递归的时候就直接去掉这个已经使用的数字，这样做的好处是方便使用二进制计算。

当然，也可以使用一个临时数字来存储已经放入的数字，只是这个过程要写入，还要回滚到最初状态，因此直接传入已经使用的数字的二进制更加简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
func numDupDigitsAtMostN(n int) (ans int) {
    s := strconv.Itoa(n)
    m := len(s)
    // 记录没有填过的数字的使用次数，用于提升便利速度
    // 例如 如果计算了 12***，那么就不需要计算21***的数量
    all := make([][1 << 10]int, m)
    for i := 0; i < m; i++ {
        for j := 0; j < 1<<10; j++ {
            // 将-1记录为没有使用过
            all[i][j] = -1
        }
    }

    // 分别代表第几位，已经填过的数字，是否有限制，前缀是否是0
    var f func(i int, mask int, limit bool, zero bool) int
    f = func(i int, mask int, limit bool, zero bool) (res int) {
        // 位数结束，代表该数字可以
        if i == m {
            return 1
        }

        // 自身没有限制，并且前缀不是0
        if !limit && !zero {
            p := &all[i][mask]
            if *p > 0 {
                return *p
            }
            defer func() { *p = res }()
        }

        // 先处理前面都是0的情况
        if zero {
            // 此时i+1位不限制，并且前面都是0
            res += f(i+1, 0, false, true)
        }

        // 起始值
        start := 0
        if zero {
            start = 1
        }

        // 结束值
        end := 9
        if limit {
            end = int(s[i] - '0')
        }
        //fmt.Println(start,end)
        for ; start <= end; start++ {
            if mask>>start&1 != 1 {
                res += f(i+1, mask|1<<start, limit && start == end, false)
            }
        }
        return
    }

    // 第0位，一个数字都没有使用，肯定是限制的,前面都是0
    return n + 1 - f(0, 0, true, true)
}

2023年03月21日

2469. 温度转换

解法1：按照题目计算即可

1
2
3
func convertTemperature(celsius float64) []float64 {
   return []float64{celsius + 273.15, celsius*1.8 + 32}
}

2023年03月22日

1626. 无矛盾的最佳球队

解法1：排序加动规。先将球员按照分数和年龄升序排序，如果分数一样，则将年龄升序排序。这样的话，就将问题转换成排序之后，求解年龄的子数组最大分数的问题。使用dp，代表当选择该球员时的最大分数,dp的求解，就是不算上自己，前面的所有无矛盾的球员的最大分数，加上自己的分数。最终结果，取dp的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func bestTeamScore(scores, ages []int) (ans int) {
    type member struct {
        score int
        age   int
    }

    members := make([]member, len(scores))
    for i := 0; i < len(scores); i++ {
        members[i] = member{
            score: scores[i],
            age:   ages[i],
        }
    }
    // 先按照分数排序，再按照年龄排序
    sort.Slice(members, func(i, j int) bool {
        return members[i].score < members[j].score || (members[i].score == members[j].score && members[i].age < members[j].age)
    })
    //fmt.Println(members)
    dp := make([]int, len(scores))
    dp[0] = members[0].score
    res := dp[0]
    for i := 1; i < len(scores); i++ {
        for j := i - 1; j >= 0; j-- {
            // 找到所有年龄小于或者等于自己的，最大的dp
            if members[j].age <= members[i].age {
                dp[i] = max(dp[i], dp[j])
            }
        }
        dp[i]+=members[i].score
        res = max(dp[i], res)
    }
    //fmt.Println(dp)
    return res
}

func max(i int, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}

2023年03月23日

1630. 等差子数组

解法1：按照题目进行切割和排序，然后验证即可。需要注意的是，排序后的数组，不要影响原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func checkArithmeticSubarrays(nums []int, l []int, r []int) (ans []bool) {
   check := func(nums []int) bool {
      m := len(nums)
      if m < 2 {
         return false
      }

      newN := make([]int,m)
      copy(newN,nums)
      sort.Ints(newN)
      //fmt.Println(newN)
      for i := 0; i < m-1; i++ {
         if newN[i+1] - newN[i] != newN[1] - newN[0] {
            return false
         }
      }
      return true 
   }
   for i := 0; i < len(l); i++ {
      ans = append(ans,check(nums[l[i]:r[i]+1]))
   }
   return
}

2023年03月24日

1032. 字符流

解法1：使用字典树，倒着将字符串记录到字典树中，查询也使用倒着查，同时需要注意，要保存之前输入的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type Tree struct {
   tree  [26]*Tree
   isSet bool
}

func (t *Tree) insert(s string) {
   tmp := t
   for j := len(s) - 1; j >= 0; j-- {
      l := int(s[j] - 'a')
      if tmp.tree[l] == nil {
         tmp.tree[l] = new(Tree)
      }
      tmp = tmp.tree[l]
   }
   tmp.isSet = true
}

func (t *Tree) search(s string) bool {
   tmp := t
   for j := len(s) - 1; j >= 0; j-- {
      l := int(s[j] - 'a')
      if tmp.tree[l] == nil {
         return false
      }
      if tmp.tree[l].isSet {
         return true
      }
      tmp = tmp.tree[l]
   }
   return tmp.isSet
}

type StreamChecker struct {
   tree  *Tree
   query []byte
}

func Constructor(words []string) StreamChecker {
   checker := StreamChecker{
      tree: new(Tree),
   }
   for i := 0; i < len(words); i++ {
      checker.tree.insert(words[i])
   }
   return checker
}

func (this *StreamChecker) Query(letter byte) bool {
   this.query = append(this.query, letter)
   return this.tree.search(string(this.query))
}

2023年03月25日

1574. 删除最短的子数组使剩余数组有序

解法1：按照题目可以直到，去掉这个子数组之后，剩下的是非递减，那么可以先求出一边的边界，然后再求出另外一边的边界。先求出右边界，那么将左边全部删掉即可。题目是求最小的长度，则开始从左侧遍历，移动左边满足条件的角标，这里核心点是确认是否保留当前数字，如果不保留，则答案就是right-left-1，如果要保留，则需要向右移动右角标。直到左边出现不合法或者右角标移动到最后，最终的最小数就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func findLengthOfShortestSubarray(arr []int) int {
   m := len(arr)
   // 右边
   right := m - 1
   for right > 0 && arr[right] >= arr[right-1] {
      right--
   }
   if right == 0 {
      return 0
   }
   res := right
   // 左边
   for i := 0; i < right; i++ {
      if i > 0 && arr[i] < arr[i-1] {
         break
      }
      for right < m && arr[i] > arr[right] {
         right++
      }
      res = min(res, right-i-1)
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

2023年03月26日

2395. 和相等的子数组

解法1：使用HashMap并且遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
func findSubarrays(nums []int) bool {
   m := len(nums)
   all := make(map[int]bool, m)
   for i := 0; i < m-1; i++ {
      tmp := nums[i] + nums[i+1]
      if all[tmp] {
         return true
      } else {
         all[tmp] = true
      }
   }
   return false 
}

2023年03月27日

1638. 统计只差一个字符的子串数目

解法1：枚举所有的只差一个字符的子串

解法2：dp，二维数组，并且使用双dp，一个dp记录从左侧数组开始取，一个dp记录从右侧数组开始取。如果字符相等，就说明两个左侧的子串是满足的，右侧同理。最终结果，便利字符，取当字符不想等时，左侧的个数乘以右侧的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func countSubstrings(s string, t string) int {
   m, n := len(s), len(t)

   dpl, dpr := make([][]int, m+1), make([][]int, m+1)
   dpl[0], dpr[m] = make([]int, n+1), make([]int, n+1)

   for i := 0; i < m; i++ {
      dpl[i+1] = make([]int, n+1)
      for j := 0; j < n; j++ {
         if s[i] == t[j] {
            dpl[i+1][j+1] = dpl[i][j] + 1
         }
      }
   }

   for i := m - 1; i >= 0; i-- {
      dpr[i] = make([]int, n+1)
      for j := n - 1; j >= 0; j-- {
         if s[i] == t[j] {
            dpr[i][j] = dpr[i+1][j+1] + 1
         }
      }
   }

   var res int
   for i := 0; i < m; i++ {
      for j := 0; j < n; j++ {
         if s[i] != t[j] {
            res += (dpl[i][j] + 1) * (dpr[i+1][j+1] + 1)
         }
      }
   }

   return res
}

2023年03月28日

1092. 最短公共超序列

解法1：使用dp，先查询出最长公共子序列，因为最短公共超序列肯定会包含最长公共子序列。然后再最短公共超序列从未到头递推，如果str1[i] == str2[j]，则将放入对应字符，角标都-1，如果不想等，则判断dp[i][j+1],dp[i+1][j]，大的，说明左侧的字符中有更多的公共子序列，选择长的情况，将字符放入。直到两个角标都为0，最后翻转字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
func shortestCommonSupersequence(str1 string, str2 string) string {
   m, n := len(str1), len(str2)
   dp := make([][]int, m+1)
   dp[0] = make([]int, n+1)
   for i := 1; i <= m; i++ {
      dp[i] = make([]int, n+1)
      for j := 1; j <= n; j++ {
         if str1[i-1] == str2[j-1] {
            dp[i][j] = dp[i-1][j-1] + 1
         } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
         }
      }
   }
   //fmt.Println(dp)

   var ans strings.Builder
   i, j := m-1, n-1
   for i >= 0 && j >= 0 {
      if str1[i] == str2[j] {
         ans.WriteByte(str1[i])
         i--
         j--
      } else {
         if dp[i][j+1] > dp[i+1][j] {
            ans.WriteByte(str1[i])
            i--
         } else {
            ans.WriteByte(str2[j])
            j--
         }
      }
   }



   for ;i >= 0;i-- {
      ans.WriteByte(str1[i])
   }
   for ;j >= 0;j-- {
      ans.WriteByte(str2[j])
   }
   str := ans.String()
   return reverseString(str)
}

func max(i int, i2 int) int {
   if i > i2 {
      return i
   }
   return i2
}

func reverseString(s string) string {
   var ans strings.Builder
   for i := len(s) - 1; i >= 0; i-- {
      ans.WriteByte(s[i])
   }
   return ans.String()
}

2023年03月29日

1641. 统计字典序元音字符串的数目

解法1：按照题目描述，其实有以下关系

1
2
3
4
5
f(n) a = f(n-1) a + f(n-1) e + f(n-1) i + f(n-1) o + f(n-1) u
f(n) e = f(n-1) e + f(n-1) i + f(n-1) o + f(n-1) u
f(n) i = f(n-1) i + f(n-1) o + f(n-1) u
f(n) o = f(n-1) o + f(n-1) u
f(n) u = f(n-1) u

按照题目表述，最终结果相加即可

1
2
3
4
5
6
7
8
9
10
11
12
func countVowelStrings(n int) int {
   dp := make([][5]int, n)
   dp[0] = [5]int{1, 1, 1, 1, 1}
   for i := 1; i < n; i++ {
      dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]
      dp[i][1] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]
      dp[i][2] = dp[i-1][2] + dp[i-1][3] + dp[i-1][4]
      dp[i][3] = dp[i-1][3] + dp[i-1][4]
      dp[i][4] = dp[i-1][4]
   }
   return dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4]
}

2023年03月30日

1637. 两点之间不包含任何点的最宽垂直区域

解法1：先排序，然后获取最小差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxWidthOfVerticalArea(points [][]int) int {
    sort.Slice(points,func(i,j int)bool {
        return points[i][0] < points[j][0]
    })

    var ans int 
    for i:= 1 ;i < len(points);i++ {
        tmp := points[i][0] - points[i-1][0]
        if tmp > ans {
            ans = tmp
        }
    }
    return ans 
}

2023年03月31日

2367. 算术三元组的数目

解法1：使用HashMap记录另外两个元素是否存在即可，由于题目中最大数字只有200，因此可以使用有限数组替代HashMap，提高性能

1
2
3
4
5
6
7
8
9
10
11
func arithmeticTriplets(nums []int, diff int) int {
   var all, res = [201]bool{}, 0
   for i := 0; i < len(nums); i++ {
      if nums[i]-diff >= 0 && all[nums[i]-diff] &&
         nums[i]-diff*2 >= 0 && all[nums[i]-diff*2] {
            res++
      }
      all[nums[i]] = true
   }
   return res
}