算法错题簿（持续更新）

go

1、01背包，快速幂计算

• 经典01背包问题，背包容量是n，从1-n中挑选任意个数字，每个数字的权重是i**x，问有几种方案

func numberOfWays(n int, x int) int {
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; pow(i, x) <= n; i += 1 {
		v := pow(i, x)
		for s := n; s >= v; s-- {
			f[s] += f[s-v]
		}
	}
	return f[n] % (1e9 + 7)
}
func pow(x, n int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res *= x
		}
		x *= x
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 创建一个n+1的数组，这样下标就是选择是数字，数组中的值就是这个数字符合条件的组合数，如果更大的数字挑选这个数字作组合的话，组合数就是这个数字在数组中的值。
• 对权重值小于n的数字进行遍历，并更新对于数字n，符合条件的组合数，注意不仅要更新n，还要更新之前的数字，否则后续计算失效
• 快速计算幂，每次指数折半，将底数翻倍，如果本轮指数是奇数，就将底数乘到res中

2、字符串组合

• 这道题猛地一看没有什么思路，这时候可以尝试暴力，直接遍历abc所有排列，尝试合并成一个字符串，每种结果相互比较，选出最短且字典序最小的结果

func minimumString(a string, b string, c string) string {
    // 合并s和t，将t插入s后面
    f := func(s string,t string) string{
        if strings.Contains(s,t){
            return s
        }
        if strings.Contains(t,s){
            return t
        }
        n := len(s)
        start := min(n,len(t))
        for i:=start;i>=0;i--{
            if s[n-i:]==t[:i]{
                return s+t[i:]
            }
        }
        return s+t
    }
    
    ans := ""
    ss := []string{a,b,c}
    turn := [][]int{{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}}
    for _,nums := range turn{
        res := f(f(ss[nums[0]],ss[nums[1]]),ss[nums[2]])
        // fmt.Println(res)
        if ans=="" || len(ans)>len(res) || len(ans)==len(res) && ans>res{
            ans=res
        }
    }
    return ans
}
func min(a int,b int)int{
    if a>=b{
        return b
    }else{
        return a
    }
}
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

• 合并的函数中，比较s的后缀和t的前缀，在调用时需要使用全排列，即turn二维数组，最终结果比较长度，如果一样长比较字典序，注意go中两个字符串比较字典序可以直接比较

• 这里需要使用全排列，因为在合并函数中每次返回的是最小的结果，但是两次合并贪心最优不代表最终结果最优，可能会出现这种情况

• "gfaa" + "aaccf" + "faaacc"
  如果不适用全排列，两次贪心的结果是 >> "gfaaccfaaacc"
  但是全排列就考虑到021这种情况，结果是 >> "gfaaaccf"
  1
  2
  3

• 所以我们采用全排列+贪心的方法来避免每次最短结果不是最短这种尴尬情况

3、数位dp，模拟记忆化搜索，位运算

• 对每一位数进行递归，遍历所有可能出现的情况，每一位数的取值范围该如何确定？
• 最小值：如果全是0，那么有可能出现010这种情况，10明显是符合条件的，但是数字0出现了两次，所以应该把0出现的情况划分开。如果前面所有位数都没有选值，那么这一位也可以不选，即为跳过，也可以选，可以选的最小值是1，如果前面有一位已经选了>0的值，后面就不能跳过了，此时可以选的最小值是0
• 最大值：如果前面的位数都选了最大的值，比如135 >> 13*，那么这一位最大可以选5，如果前面的位数有一个没有定格选，那么这一位最大可以选9
• 对上面两种情况需要维护两个bool值，isLimit表示这一位是否被限制不能选9，isNum表示前面是否选了数字
• 流程确定，每次先判断能不能跳过，然后从最小值到最大值遍历，如果数字还没被选，那么符合题目条件，这里我们用位运算来记录前面选了哪些数
• 最后使用记忆化数组来提高计算效率，分别用第i位和位运算来当下标，由于两个bool值的存在，我们选择记录!isLimit && isNum这种情况，因为这种情况最多

func countSpecialNumbers(n int) int {
    s := strconv.Itoa(n)
    m := len(s)
    // dp数组，模拟记忆化搜索，只记录!isLimit && isNum的情况，其他情况不能合并并且发生次数少
    cache := make([][1<<10]int, m)
    for i := range cache{
        for j := range cache[i]{
            cache[i][j] = -1
        }
    }
    // 第i位填数字，前i位选过的数字记录在mask中
    // isLimit表示，如果前i位全是n[i]，那么这一位最多填n[i]
    // isNum表示，如果前i位选过数字，那么这一位只能选数字，不能跳过
    var f func(int, int64, bool, bool) int
    f = func(i int,mask int64,isLimit bool,isNum bool) int{
        if i==m{
            if isNum{
                return 1
            }else{
                return 0
            }
        }

        res := 0
        // 先检查cache是否已经记录本次递归，如果是直接返回结果，最终记录结果
        if !isLimit && isNum{
            p := &cache[i][mask]
            if *p>=0{
                return *p
            }
            defer func(){*p = res}()
        }

        // 跳过
        if !isNum{
            res += f(i+1,mask,false,false)
        }

        // 不跳过
        start := 1
        if isNum{
            start = 0
        }
        end := 9
        if isLimit{
            end = int(s[i]-'0')
        }
        for j:=start;j<=end;j++{
            if mask>>j & 1 == 0 {
                res += f(i+1,mask|(1<<j),isLimit && j==end,true)
            }
        }
        return res
    }
    return f(0,0,true,false)
}
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

4、多源BFS，并查集

• 首先找到全部的1，然后从1开始扩散，记录数组中所有点离最近的1的距离，从距离最大的几个点扩散，更新并查集，并判断从左上是否联通右下，如果是就返回，如果不是就遍历下一个距离的点集，最终返回0
• 为什么用多源BFS：所有的1以相同速度同时扩散，就可以判断出某个点离哪个1最近
• 为什么用并查集：可以快速判断两个点是否联通

func maximumSafenessFactor(grid [][]int) int {
    n := len(grid)
    // 查找 1 的下标
    type pair struct{ x, y int}
    q := []pair{}
    dist := make([][]int, n)
    for i, row := range grid{
        dist[i] = make([]int, n)
        for j, x := range row{
            if x==1{
                q = append(q, pair{i, j})
            }else{
                dist[i][j] = -1
            }
        }
    }
    // fmt.Println(q,dist)

    // 从1开始扩散，记录到1的距离，根据距离分层，记录下标
    // 由于有多个1，所以用多源BFS，滚动数组遍历grid，来更新距离，保存下标
    dir4 := []pair{{-1,0}, {1,0}, {0,-1}, {0,1}}
    groups := [][]pair{q}
    for len(q) > 0{
        temp := q
        q = nil
        for _,p := range temp{
            for _,d := range dir4{
                x, y := p.x+d.x, p.y+d.y
                if 0<=x && x<n && 0<=y && y<n && dist[x][y]<0{
                    q = append(q,pair{x,y})
                    dist[x][y] = len(groups)
                }
            }
        }
        groups = append(groups,q)
    }
    // fmt.Println(groups,dist)

    // 由层数从大到小遍历，对每个点遍历上下左右，只可以去层数更大的点
    // 如果当前层数遍历完成后左上能到右下，就返回层数，判断左上右下两点是否联通使用并查集
    fa := make([]int, n*n)
    for i := range fa{
        fa[i] = i
    }
    var find func(int)int
    find = func(x int)int{
        if fa[x] != x{
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    for ans := len(groups)-2; ans>0; ans-=1{
        for _,p := range groups[ans]{
            i, j := p.x, p.y
            for _,d := range dir4{
                x, y := p.x+d.x, p.y+d.y
                if 0<=x && x<n && 0<=y && y<n && dist[x][y] >= dist[i][j]{
                    fa[find(x*n+y)] = find(i*n+j)
                }
            }
        }
        if find(0) == find(n*n-1){
            // fmt.Println(fa)
            return ans
        }
    }
    return 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
61
62
63
64
65
66
67
68
69

输出示例：

// 所有的1
[{0 3} {3 0}] 
// 距离记录前的样子
[[-1 -1 -1 0]
 [-1 -1 -1 -1]
 [-1 -1 -1 -1]
 [0 -1 -1 -1]]
// 距离更新后的样子
[[3 2 1 0]
 [2 3 2 1]
 [1 2 3 2]
 [0 1 2 3]]
// 根据层数来分组的点
[[{0 3} {3 0}] 
 [{1 3} {0 2} {2 0} {3 1}]
 [{2 3} {1 2} {0 1} {1 0} {2 1} {3 2}]
 [{3 3} {2 2} {1 1} {0 0}]
 []] 
// 并查集维护的数组
[14 14 2 3 14 4 9 7 8 14 9 14 12 13 14 14]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5、有序队列

• 双指针遍历数组，下标间距正好是x，前一个指针添加到一个有序队列中，后一个指针在有序队列中查找与之相近的值，最后返回结果
• 力扣中支持第三方库github.com/emirpasic/gods/tree/v1.18.1，提供了一个红黑树，插入数据后直接根据key值大小排列成一个有序数组，我们将key设为nums[i]，value设为空

func minAbsoluteDifference(nums []int, x int) int {
    ans := math.MaxInt
    // 第三方库，把红黑树当做有序队列
    tree := redblacktree.NewWithIntComparator()
    // 只用排序功能，只需要设置key值，
    // 首先插入两个哨兵，分别位于有序队列的头和尾，保证每次查找都能返回一个结果
    tree.Put(math.MaxInt, nil)
    tree.Put(math.MinInt/2, nil)
    // 双指针遍历数组，把前一个数添加到队列中，后一个数在队列中查找刚好大于和小于的叶子节点
    for i,y := range nums[x:]{
        tree.Put(nums[i], nil)
        c,_ := tree.Ceiling(y)
        f,_ := tree.Floor(y)
        ans = min(ans, min(y-f.Key.(int), c.Key.(int)-y))
    }
    return ans
}
func min(i,j int)int{if i<j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6、线性dp

• 第一眼思路是dfs，维护房屋end和买家下标，每次判断要不要卖给买家，但是超时了，使用dp数据优化，但是数据范围过大，不能生成 [1e5] [1e5] int 大小数组
• 正确解法是线性dp，递推式dp[n] = max( dp[n-1], max( dp[starti]) + goldi )

// DP问题两个思路，
// 一个是选或不选，是否卖当前房子，
// 一个是枚举选哪个，以当前房子结尾最多可以赚多少钱
func maximizeTheProfit(n int, offers [][]int) int {
    // 线性dp，选或不选，不选f[n+1]=f[n]，选，枚举选哪个f[n+1]=max(f[starti]+goldi)
    groups := make([][][2]int, n)
    for _,arr := range offers{
        groups[arr[1]] = append(groups[arr[1]], [2]int{arr[0], arr[2]})
    }
    dp := make([]int, n+1)
    // 从递推式可知，计算n+1需要用到f[start]，所以从前往后遍历
    for i:=1;i<=n;i+=1{
        // 不选
        dp[i] = dp[i-1]
        // 选，枚举选哪个
        for _,arr := range groups[i-1]{
            dp[i] = max(dp[i], dp[arr[0]]+arr[1])
        }
    }
    return dp[n]
}
func max(i,j int)int{if i>=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 这道题我的问题在于过度依赖dfs和dp数组优化，对于dp问题，应该从选或不选入手，选则继续考虑枚举选哪个

7、对数组至多删除k个元素，求子数组最大值

• 这道题就是没思路，总不能对每个元素进行遍历，每次操作之后求一次子数组长度
• 当直接对数组遍历不行时，就需要对数组进行预处理，以每个元素分组，记录同一类元素下标，遍历下标数组，维护一个最大值
• 例如nums = [1,3,2,3,1,3], k = 3，元素分组后的结果是[[] [0 4] [2] [1 3 5] [] [] []]，如何遍历才能考虑全所有情况，找到最大的数组长度呢？答案是使用双指针，遍历右端点，移动左端点，寻找以当前右端点结尾数组满足题目要求的左端点。

//对nums进行预处理，根据值对下标分组
//对每组进行双指针遍历，寻找满足要求的子数组，维护最大长度
func longestEqualSubarray(nums []int, k int) int {
    //数据范围 0
    n := len(nums)
    pos := make([][]int, n+1)
    for i,x := range nums{
        pos[x] = append(pos[x], i)
    }
    fmt.Println(pos)
    //对每一组进行遍历，维护子数组最大值
    ans := 0
    for _,arr := range pos{
        //如何遍历才能考虑全所有情况？我们只需要找数组最长的情况，所以使用双指针遍历
        //遍历右端点，移动左端点，使得中间删除元素刚好小于k，这个长度就是这个右端点的长度
        l := 0
        for r,idx := range arr{
            //删除次数=下标数组记录的nums长度-下标数组arr的长度
            //       =一共有几个数字-不需要删除的数字
            for (idx-arr[l]+1) - (r-l+1) > k{
                l += 1
            }
            ans = max(ans,r-l+1)
        }
    }
    return ans
}
func max(i,j int)int{if i>=j{return i}else{return 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

• 这道题是个套路题，对数组操作，并求满足题目要求值，这是一个出题模板

8、前缀和

数组问题一个通用有效方法是计算前缀和、前缀最大值、后缀最大值等等

• 数组预处理，整除为1，否则为0，双指针遍历数组，查找子数组中满足1数量的所有子数组
• 查找子数组数量这一步不好做，可以使用前缀数组的方法，

func countInterestingSubarrays(nums []int, m int, k int) int64 {
    // 如果能除尽，算作1，否则为0，为了得到数量，还需要求前缀和，用p[r]-p[l]来表示[l, r]中的这个数量
    pre := make([]int, len(nums)+1)
    for i,x := range nums{
        pre[i+1] = pre[i]
        if x%m == k{
            pre[i+1]+=1
        }
    }
    fmt.Println(pre)
    // 求 (p[r] - p[l]) % m == k
    // => (p[r] - p[l] + m) % m == k % m 
    // => (p[r] - k + m) % m == p[l] % m
    // 有多少个上式成立，就可以往ans中加几个值，
    // 遍历前缀数组，使用哈希表查询以当前值为right，记录以当前值为left
    ans := 0
    cnt := map[int]int{}
	for _, v := range pre {
        ans += cnt[(v - k + m) % m]
        cnt[v%m]+=1
    }
    return int64(ans)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• [3,1,9,6] => [0 1 1 2 3] => 2

9、矩阵处理，全排列

• 这个题最初打算先对矩阵预处理，分别记录石头多的和缺石头的，然后缺石头的从距离最近处取石头

• 还有另外一种解法，首先预处理，石头多的，多几次就记录几次，如下

  • [[0 1] [0 1] [2 2] [2 2]] : [[0 2] [1 1] [1 2] [2 1]]

• 然后求石头多的全排列，分别和缺石头的对应，计算距离，如此难点就成了计算全排列

func minimumMoves(grid [][]int) int {
    from := make([][]int, 0)
    to := make([][]int, 0)
    for i,arr := range grid{
        for j,x := range arr{
            if x>1{
                for c:=1; c<x; c+=1{
                    from = append(from, []int{i,j})
                }
            }else if x==0{
                to = append(to, []int{i,j})
            }
        }
    }
    fmt.Println(from," : ",to)
    // 枚举from的全排列，分别计算与to的移动次数
    ans := math.MaxInt
    permute(from, 0, func(){
        temp := 0
        for i,f := range from{
            temp += abs(f[0] - to[i][0]) + abs(f[1] - to[i][1])
        }
        ans = min(ans, temp)
    })
    return ans
}
func permute(arr [][]int, idx int, do func()){
    if idx==len(arr){
        do()
        return
    }
    permute(arr, idx+1, do)
    for j:=idx+1;j<len(arr);j+=1{
        arr[idx], arr[j] = arr[j], arr[idx]
        permute(arr, idx+1, do)
        arr[idx], arr[j] = arr[j], arr[idx]
    }
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if b < a { return b }; return a }
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

• 在全排列函数permute中，分别求首元素固定和首元素移动的情况

10、前缀最大值、后缀最大值

• 这道题我想复杂了，我想的是遍历找到最小的j，然后分别求两边最大的i和k，k使用map，i使用max
• 实际上直接遍历j，两边的最大值分别用数组的前缀最大值和后缀最大值来计算
• 还有一种一次遍历的方法，遍历k，同时维护max(nums[i]-nums[j])，以及max(nums[i])

方法一：

func maximumTripletValue(nums []int) int64 {
    // 分别计算前缀最大值和后缀最大值
    n := len(nums)
    pre := make([]int,n)
    pre[0] = nums[0]
    suf := make([]int,n)
    suf[n-1] = nums[n-1]
    for i:=0;i<n-1;i+=1{
        pre[i+1] = max(pre[i],nums[i+1])
    }
    for i:=n-1;i>0;i-=1{
        suf[i-1] = max(suf[i], nums[i-1])
    }
    // fmt.Println(pre, suf)
    res := 0
    for i,x := range nums[1:n-1]{
        res = max(res, (pre[i]-x)*suf[i+2])
    }
    return int64(res)
}
func max(i,j int)int{if i>=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：

func maximumTripletValue(nums []int) int64 {
    res := 0
    // 遍历k，维护一个max_diff，res=max_diff*nums[k]，而max_diff=max_pre-nums[k]
    max_diff := 0
    max_pre := 0
    for _,x := range nums{
        // 把k当做k
        res = max(res, max_diff*x)
        // 把k当做j
        max_diff = max(max_diff, max_pre-x)
        // 把k当做i
        max_pre = max(max_pre, x)
    }
    return int64(res)
}
func max(i,j int)int{if i>=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 有没有可能，这样求出来的max(nums[i]-nums[j])，并非是固定k后的最大值，毕竟这样更新的res，j和k是紧挨着的，我觉得不会，因为有一个max比较的过程，如果j和k紧挨的情况不是最大值，那么就不会更新max_diff
• 其次这个维护计算的顺序是不能乱的，因为i

11、一次遍历数组排序

• 一次遍历对数组排序，有两种方法
• 第一种，双指针，p0和p1指向0和1的下一个位置，遍历数组，0放到p0，原先p0数字放到p1，1放到p1
• 第二种，双指针，p0和p2指向0和2的下一个位置，遍历数组，0放到p0，遇2则循环放到p2

// 双指针，指向0和1的下一个位置，遍历数组，0放到p0，原先p0数字放到p1，1放到p1
func sortColors(nums []int)  {
    p0,p1 := 0,0
    for i,x := range nums{
        if x==0{
            nums[i],nums[p0] = nums[p0],nums[i]
            if p1>p0{
                nums[i],nums[p1] = nums[p1],nums[i]
            }
            p0++
            p1++
        }else if x==1{
            nums[i],nums[p1] = nums[p1],nums[i]
            p1++
        }
    }
}
// 双指针，指向0和2的下一个位置，遍历数组，0放到p0，遇2则循环放到p2
func sortColors1(nums []int)  {
    n := len(nums)
    p0,p2 := 0,n-1
    for i := range nums{
        for ;i<=p2 && nums[i]==2;p2-=1{
            nums[i],nums[p2] = nums[p2],nums[i]
        }
        if nums[i]==0{
            nums[i],nums[p0] = nums[p0],nums[i]
            p0+=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

12、动态规划，操作字符串

• 动态数组d[i][j]表示word1前i个字符和word2前j个字符的编辑距离

// if word1[i]==words2[j] 则 d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1])
// if word1[i]!=words2[j] 则 d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+1)
func minDistance(word1 string, word2 string) int {
    n,m := len(word1),len(word2)
    d := make([][]int, n+1)
    for i := range d{
        d[i] = make([]int, m+1)
    }
    for i:=0;i<=n;i+=1{
        d[i][0] = i
    }
    for j:=0;j<=m;j+=1{
        d[0][j] = j
    }
    for i:=1;i<=n;i+=1{
        for j:=1;j<=m;j+=1{
            if word1[i-1]==word2[j-1]{
                d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1])
            }else{
                d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+1)
            }
        }
    }
    return d[n][m]
}
func min(i,j,k int)int{if i<=j{if i<=k{return i}else{return k}}else{if j<=k{return j}else{return k}}}
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

13、单调栈，哨兵

• 暴力遍历分两种，一种是遍历矩形的宽，i=0:n，j=i:n，一种是遍历矩形的高，heights[i]向两边扩散找宽
• 第一种固定O(n2)时间复杂度，没有太多优化空间，所以优化第二种，遍历高，找宽
• 创建一个单调栈，遍历heights，如果遍历的值递增就添加到栈中，如果遍历的值小于栈尾值就弹出值并计算弹出值为高所画的最大矩形，直到遍历的值大于等于栈尾值
• 至于如何求矩形的面积，高=stack[i]，宽=右-左=遍历的下标-(i-1)

func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := make([]int,n+2)
    idx := 0
    heights = append(append([]int{0},heights...),0)
    ans := 0
    for i,x := range heights{
        if idx==0 || x>=heights[stack[idx-1]]{
            stack[idx] = i
            idx++
            continue
        }
        for j:=idx-1;j>=0;j--{
            if x>=heights[stack[j]]{
                stack[j+1] = i
                idx = j+2
                break
            }else{
                ans = max(ans,heights[stack[j]]*(i-stack[j-1]-1))
            }
        }
    }
    return ans
}
func max(i,j int)int{if i>=j{return i}else{return 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

延伸：

这道题只需把每一行看做一道单调栈的题，例如第一行是10100，第二行是20211，第三行是31322，第四行是40030，维护一个最大矩形面积值即可

14、反向排序

• 考虑在nums1上一次遍历就完成原地排序的情况，如果从前往后遍历，设置双指针，哪个大就放到nums1中，这会导致nums1中小的数字被覆盖，如何避免这种情况，可以从后往前遍历，哪个大就放入nums1中，这样就可以避免落选数字被覆盖的问题

func merge(nums1 []int, m int, nums2 []int, n int)  {
    i1,i2 := m-1,n-1
    for i:=m+n-1;i>=0;i--{
        if i2<0 || (i1>=0 && nums1[i1]>nums2[i2]){
            nums1[i] = nums1[i1]
            i1--
        }else{
            nums1[i] = nums2[i2]
            i2--
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

15、01背包问题

• 最初想法是回溯，但是超时了，这道题的问题在于能不能看出是01背包问题

// 选出若干选项组成target，属于01背包问题
func lengthOfLongestSubsequence(nums []int, target int) int {
    dp := make([]int,target+1)
    // 最开始只有target==0可以直接获得，其他初始化为一个负值
    for i:=1;i<=target;i++{
        dp[i] = math.MinInt
    }
    for _,x := range nums{
        for i:=target;i>=x;i--{
            dp[i] = max(dp[i],dp[i-x]+1)
        }
    }
    if dp[target]>0{
        return dp[target]
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

16、增量法，lazy线段树

增量法：

• 观察例子abbca，有以下推论式

  	  a -> ab -> abb -> abbc -> abbca
  	  1 -> 21 -> 211 -> 3221 -> 33321
  	  1 -> 3  -> 4   -> 8    -> 12
  增量： 1 -> 2  -> 1   -> 4    -> 4
  1
  2
  3
  4

  增量正好是当前字符下标与上一次出现同样字符下标之差，我们可以记录每个字符上一次出现的下标，维护一个总和sum，遍历s计算增量加到总和sum上，然后将当前sum加到结果res

// a -> ab -> abb -> abbc -> abbca
// 1 -> 21 -> 211 -> 3221 -> 33321
// 1 -> 3  -> 4   -> 8    -> 12    sum=28
func appealSum(s string) int64 {
    sumg,res := 0,0
    last := [26]int{}
    for i := range last{last[i] = -1}
    for i,c := range s{
        c-='a'
        sumg += i-last[c]
        res += sumg
        last[c] = i
    }
    return int64(res)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

lazy线段树：

如果后面又来了一个更新，破坏了有 lazy tag 的区间，那么这个区间就得继续递归更新了。

// 线段树
// 保存每个线段的信息，左右端点，1的个数，是否翻转（lazy标志）
type seg []struct{
    l,r,cnt1 int
    flip bool
}
// 维护线段内1的个数
func (t seg) maintain(o int){
    t[o].cnt1 = t[o*2].cnt1+t[o*2+1].cnt1
}
// 构建线段树
func (t seg) build(a []int, o,l,r int){
    t[o].l,t[o].r = l,r
    if l==r{
        t[o].cnt1 = a[l-1]
        return
    }
    m := (l+r)/2
    t.build(a,o*2,l,m)
    t.build(a,o*2+1,m+1,r)
    t.maintain(o)
}
// 执行区间翻转，只需要更新lazy标签以及区间内1的个数
func (t seg) do(O int){
    o := &t[O]
    o.cnt1 = o.r-o.l+1-o.cnt1
    o.flip = !o.flip
}
// 更新lazy标签，传给左右儿子
func (t seg) spread(o int){
    if t[o].flip{
        t.do(o*2)
        t.do(o*2+1)
        t[o].flip = false
    }
}
// 更新线段，区间翻转，lazy更新
func (t seg) update(o,l,r int){
    if l<=t[o].l && r>=t[o].r{
        t.do(o)
        return
    }
    // 当前区间不是全在[l,r]内，需要将flip标签传递下去
    t.spread(o)
    m := (t[o].l+t[o].r)/2
    if l<=m{
        t.update(o*2,l,r)
    }
    if m<r{
        t.update(o*2+1,l,r)
    }
    t.maintain(o)
}
func handleQuery(nums1 []int, nums2 []int, queries [][]int) (ans []int64) {
    sum := 0
    for _,x := range nums2{
        sum += x
    }
    // 总线段数不会超过最短线段数的四倍
    t := make(seg,len(nums1)*4)
    t.build(nums1,1,1,len(nums1))
    for _,arr := range queries{
        if arr[0]==1{
            t.update(1,arr[1]+1,arr[2]+1)
        }else if arr[0]==2{
            sum += arr[1]*t[1].cnt1
        }else{
            ans = append(ans,int64(sum))
        }
    }
    return ans
}
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

增量法+lazy线段树：

• 与上一题的总体思路类似，但是这道题是平方和，那么增量差就不是下标差了，而是(x+1)2-x2=2x+1，同样是与上一次出现方位内元素累加，等于2sum(xi)+N，

17、回溯+动态规划+数组空间优化

• 这儿道题分别用回溯和动态规划以及空间优化来解决

  

回溯：

func minIncrementOperations(nums []int, k int) int64 {
    n := len(nums)
    memo := make([][3]int,n)
    for i := range memo{
        memo[i] = [3]int{-1,-1,-1}
    }
    // fmt.Println(memo)
    var dfs func(int,int)int
    dfs = func(i,j int)int{
        if i==n{
            return 0
        }
        if memo[i][j]!=-1{
            return memo[i][j]
        }
        res := 0
        defer func(){memo[i][j] = res}()
        if j<2{
            res = min(dfs(i+1,0)+max(k-nums[i],0), dfs(i+1,j+1))
        }else{
            res = dfs(i+1,0)+max(k-nums[i],0)
        }
        return res
    }
    // defer func(){fmt.Println(memo)}()
    return int64(dfs(0,0))
}
func max(i,j int)int{if i>=j{return i}else{return j}}
func min(i,j int)int{if i<=j{return i}else{return 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
29

动态规划：

func minIncrementOperations(nums []int, k int) int64 {
    n := len(nums)
    dp := make([]int,n)
    for i := range dp{
        if i<3{
            dp[i] = max(k-nums[i],0)
        }else{
            dp[i] = min(min(dp[i-3],dp[i-2]),dp[i-1])+max(k-nums[i],0)
        }
    }
    return int64(min(min(dp[n-1],dp[n-2]),dp[n-3]))
}
func max(i,j int)int{if i>=j{return i}else{return j}}
func min(i,j int)int{if i<=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数组空间优化：

func minIncrementOperations(nums []int, k int) int64 {
    n := len(nums)
    dp := make([]int,3)
    for i:=0;i<n;i++{
        if i<3{
            dp[i] = max(k-nums[i],0)
        }else{
            cur := min(min(dp[0],dp[1]),dp[2])+max(k-nums[i],0)
            dp[0],dp[1],dp[2] = dp[1],dp[2],cur
        }
    }
    return int64(min(min(dp[0],dp[1]),dp[2]))
}
func max(i,j int)int{if i>=j{return i}else{return j}}
func min(i,j int)int{if i<=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

18、二叉搜索树

• 第一个问题是如何筛除重复项，回溯是以递归的方式遍历所有可能情况，所以会导致重复项，所以可以在递归的基础上有选择的递归
• 举例：1,2,3。以2为根节点，左节点是1，右节点是3，因为是搜索树，所以不递归左3右1的情况，从而避免了重复项

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    var dfs func(int,int)[]*TreeNode
    dfs = func(l,r int)(ans []*TreeNode){
        // 这一句不能少[]*TreeNode{nil}和[]*TreeNode{}不一样
        if l>=r{
            return []*TreeNode{nil}
        }
        for i:=l;i<r;i++{
            for _,leftNode := range dfs(l,i){
                for _,rightNode := range dfs(i+1,r){
                    ans = append(ans,&TreeNode{i,leftNode,rightNode})
                }
            }
        }
        // 最后的return也不能少
        return ans
    }
    return dfs(1,n+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

19、连接每一层树节点

• 考虑进阶问题，注意题目这里是完美二叉树，一个父节点必有两个子节点，可以通过递归的方法将每一层相邻两个节点传入dfs

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root!=nil{
        dfs(root.Left,root.Right)
    }    
    return root
}
func dfs(p,q *Node){
    if p==nil{
        return
    }
    p.Next = q
    dfs(p.Left,p.Right)
    dfs(p.Right,q.Left)
    dfs(q.Left,q.Right)
}
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

• 对于这道题，树不再是完全二叉树，如果递归，需要面对q和p左右节点都可能为nil的情况，这个时候可以逐层遍历，下一层不再暂存到栈中，而是插入到一个链表尾部，这就实现了常数个额外空间

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    head := &Node{0,nil,nil,root}
    for head.Next!=nil{
        temp := head
        cur := head.Next
        temp.Next = nil
        for cur!=nil{
            if cur.Left!=nil{
                temp.Next = cur.Left
                temp = temp.Next
            }
            if cur.Right!=nil{
                temp.Next = cur.Right
                temp = temp.Next
            }
            cur = cur.Next
        }
    }
    return root
}
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

20、记忆化搜索的特殊例子

• 递归字符串，遍历当前字符串可能的切割位置，这样做会超时，需要使用记忆化搜索，但这样就不能让递归的参数是两个字符串

  func isScramble(s1 string, s2 string) bool {
      var dfs := func(s1,s2 string)bool{
          return false
      }
      return dfs(s1,s2)
  }
  1
  2
  3
  4
  5
  6

• 正确解法是传入字符串在原始字符串中的下标，注意到递归的两个字符串参数是等长的，所以只需要两个起始下标和长度这三个参数，同时记忆化数组就是一个三维数组

func isScramble(s1 string, s2 string) bool {
    n := len(s1)
    if n==1{
        return s1==s2
    }
    memo := make([][][]int,n)
    for i := range memo{
        arr := make([][]int,n)
        for j := range arr{
            temp := make([]int,n+1)
            for k := range temp{
                temp[k] = -1
            }
            arr[j] = temp
        }
        memo[i] = arr
    }
    var dfs func(int,int,int)bool
    dfs = func(i1,i2,length int) bool {
        if length==1{
            return s1[i1]==s2[i2]
        }
        if memo[i1][i2][length]!=-1{
            return memo[i1][i2][length]==1
        }
        for i:=1;i<length;i++{
            if dfs(i1,i2,i) && dfs(i1+i,i2+i,length-i){
                memo[i1][i2][length]=1
                return true
            }
            if dfs(i1,i2+length-i,i) && dfs(i1+i,i2,length-i){
                memo[i1][i2][length]=1
                return true
            }
        }
        memo[i1][i2][length]=0
        return false
    }
    return dfs(0,0,n)
}
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

21、动态规划，买卖股票

• 这道题通过动态规划思考，首先思考每一天有几种状态，一共有五种，不买不卖，第一次买入，第一次卖出，第二次买入，第二次卖出，这样就能保证最多两次买入卖出，如果没有两次这个限制条件，状态可以分成持有股票和未持有股票

• 第一种状态利润为0，只需记录后四种状态获得的利润，buy1，sell1，buy2，sell2

• 在知道第i-1天这四种状态后，即可计算出第i天的对应状态，所以无需创建dp[n][4]数组

• 同一天买入卖出，这种情况题目没说是否允许，但是带来的收益是0，所以无论是否这么做都不影响结果，所以传递公式如下：

  b1 = max(b1,-prices[i])
  s1 = max(s1,b1+prices[i])
  b2 = max(b2,s1-prices[i])
  s2 = max(s2,b2+prices[i])
  1
  2
  3
  4

• 考虑初始条件，第一天buy1=-prices[i]，s1=0，buy2=-prices[i]，视为第一天买入卖出再买入，s2=0

• 动态规划结束后，由于完成的交易数可以是0/1/2，所以结果=max(0,s1,s2)，由于遍历时一直用max维护一个最大值，所以s1>=0，s2>=0，如果最优解是只买入卖出一次，由于同一天可以两次买入卖出，所以最优解会从s1传递到s2

func maxProfit(prices []int) int {
    n := len(prices)
    b1,s1,b2,s2 := -prices[0],0,-prices[0],0
    for i:=1;i<n;i++{
        b1 = max(b1,-prices[i])
        s1 = max(s1,b1+prices[i])
        b2 = max(b2,s1-prices[i])
        s2 = max(s2,b2+prices[i])
    }
    return s2
}
func max(i,j int)int{if i>=j{return i}else{return j}}
1
2
3
4
5
6
7
8
9
10
11
12

22、位运算，求最大异或值

• 解题思路如下：

func findMaximumXOR(nums []int) int {
    ans := 0
    // slices.Max求nums的最大值，bits.Len求最大值的位数
    highBit := bits.Len(uint(slices.Max(nums)))-1
    seen := map[int]bool{}
    mask := 0
    for i:=highBit;i>=0;i--{
        // 清空哈希表
        clear(seen)
        mask |= 1<<i
        newAns := ans | 1<<i
        for _,x := range nums{
            x &= mask
            if seen[newAns^x]{
                ans = newAns
                break
            }
            seen[x] = true
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• slices.Max求数组的最大值，bits.Len求数字的位数，只能传入uint格式的数字，clear是go1.21新添加函数，可以清除map，slice，除此以外还新增max和min

• 与上一题类似，都是求数组中最大异或值，只不过这里多了一个条件，在数组排序的情况下，把这个条件转化一下，就是2*x>=y，而为了保存x和y，上一题解中的map[int]bool需要改成map[int]int

func maximumStrongPairXor(nums []int) int {
    sort.Ints(nums)
    ans := 0
    // slices.Max求nums的最大值，bits.Len求最大值的位数
    highBit := bits.Len(uint(slices.Max(nums)))-1
    seen := map[int]int{}
    mask := 0
    for i:=highBit;i>=0;i--{
        // 清空哈希表
        clear(seen)
        mask |= 1<<i
        newAns := ans | 1<<i
        for _,x := range nums{
            mask_x := x&mask
            if seen[newAns^mask_x]>0 && seen[newAns^mask_x]*2>=x{
                ans = newAns
                break
            }
            seen[mask_x] = x
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

23、中序遍历转树结构

• 一个方法是找到链表的中节点，左边是左子树，右边是右子树，找中节点可以通过快慢节点，或者先找长度length，然后从头结点计数遍历
• 另一个方式是正常做中序递归，因为传入参数就是中序遍历得到的数组，所以中序递归节点生成的先后次序就是数组的先后次序

func sortedListToBST(head *ListNode) *TreeNode {
    length := 0
    for cur:=head;cur!=nil;cur=cur.Next{
        length++
    }
    cur := head
    var dfs func(int,int)*TreeNode
    dfs = func(left, right int) *TreeNode {
        if left >= right {
            return nil
        }
        mid := (left+right)/2
        l := dfs(left,mid)
        res := &TreeNode{cur.Val,nil,nil}
        cur = cur.Next
        res.Left = l
        res.Right = dfs(mid+1,right)
        return res
    }
    return dfs(0, length)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 由于空节点在数组中不显示，所以dfs需要传入起止下标，如果数组中通过null或者#来表示空节点，那么就无须传入任何参数

24、树状DP

• 题目意思是在保证树的每一条叶子结点路线值之和都不为0的情况下，求可以选择最大值，也就是所有数总和-每条线路至少挑选一个值，即总和-损失之和

• 从根节点开始，如果挑选根节点作为损失值，那么与根节点连接的所有线路都不需要损失，如果不损失根节点，那么与根节点连接的每条线路都需要损失一个值，子问题与母问题类似，所以递推式如下

  lossi = min(values[i], sum(dfs(j)))
  1

• 其中j是与i相连的所有节点，创建树状dp，dp[i][j]

• 做题正向思考困难则反向思考，选择那些数字困难，就思考损失哪个数字

func maximumScoreAfterOperations(edges [][]int, values []int) int64 {
    // 树状DP，dp[i][j]
    dp := make([][]int,len(values))
    // dfs中判断叶子结点是根据该节点连接数量判断的，可以为根节点额外连接一个-1，以免误判
    dp[0] = append(dp[0],-1)
    for _,arr := range edges{
        dp[arr[0]] = append(dp[arr[0]],arr[1])
        dp[arr[1]] = append(dp[arr[1]],arr[0])
    }
    var dfs func(int,int)int
    dfs = func(idx,from int)int{
        // 在叶子节点上，只能损失该节点
        if len(dp[idx])==1{
            return values[idx]
        }
        // 损失当前节点
        loss1 := values[idx]
        // 选择该节点，则损失为后续节点之和
        loss2 := 0
        for _,x := range dp[idx]{
            if x!=from{
                loss2 += dfs(x,idx)
            }
        }
        return min(loss1,loss2)
    }
    res := -dfs(0,-1)
    for _,x := range values{
        res += x
    }
    return int64(res)
}
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

25、O(1)求只出现过一次的数字

• 如果每个元素出现2次，某个元素出现1次，那么可以把所有元素相异或，最后得到的就是只出现一次的
• 每个元素恰好出现三次，如果用hash表，就可以记录每个元素出现次数，如果要求O(1)空间复杂度解题，可以对32位记录出现1的次数，如果除3余1，就是只出现一次的那个数字
• 除了这个思路，还可以对32位进行遍历，每一位对数组进行遍历，求出这一位出现的次数，进一步优化可以创建一个只有三状态的寄存位，(a,b)=00,01,11,10，这属于电路的知识，两个元素就能保存这一位的数据

func singleNumber(nums []int) int {
    bit := [32]int{}
    for _,x := range nums{
        for i := range bit{
            bit[i] += x>>i&1
        }
    }
    var res int32 = 0
    for i,b := range bit{
        if b%3==1{
            res |= 1<<i
        }
    }
    return int(res)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

26、容斥原理Ⅰ

• 容斥原理：符合条件的方案数=总方案数-不满足要求的方案数

• 一共n个球，如何分给三个人，在可以分0个的情况下，答案等于C(n+2, 2)，相当于从n+2个隔板中选择两个隔板，正好分成三份

• 基于上述两条原理，答案如下，abc分别是三位小朋友得到超过limit颗糖果的情况，那么分别从总数n中减去limit+1，然后取两个隔板即可，abc三种情况有交集，所以需要减去交集，加上共同交集，只需要单独写个函数求C(n, 2)

  ans = all - (a+b+c-ab-ac-bc+abc)
  	= c(n+2, 2)-(3*c(n-(limit+1)+2, 2)-3*c(n-2*(limit+1)+2, 2)+c(n-3*(limit+1)+2, 2))
  1
  2

func distributeCandies(n int, limit int) int64 {
    // ans = all - (a+b+c-ab-ac-bc+abc)
    return int64(c(n+2)-(3*c(n-(limit+1)+2)-3*c(n-2*(limit+1)+2)+c(n-3*(limit+1)+2)))
}
// return C(n,2)
func c(n int)int{
    if n<=1{
        return 0
    }
    return n*(n-1)/2
}
1
2
3
4
5
6
7
8
9
10
11

27、容斥原理Ⅱ

• 为何用容斥原理？正面思考困难，至少有1个l，至少有2个e，难以用代码实现，可以反向思考，最多有0个l，就是用25个英文字母填补n个空位，有1个e，就是n*用25个英文字母填补n-1个空位
• 其次注意取余的位置，在每次求pow的时候，在最终结果相加的时候，需要取余保证值不越界，还需要在取余后加上MOD在取余保证结果非负

const MOD = int(1e9+7)
func stringCount(n int) int {
    // 求最少有1个l，至少有2个e这种比较难算，可以利用容斥原理求最多有几个...
    // a = 没有l
    // b = 没有t
    // c = 没有e/只有一个e
    // ans = all - (a+b+c-ab-ac-bc+abc)
    all := pow(26,n)
    a := pow(25,n)
    b := pow(25,n)
    c := pow(25,n)+n*pow(25,n-1)
    ab := pow(24,n)
    ac := pow(24,n)+n*pow(24,n-1)
    bc := pow(24,n)+n*pow(24,n-1)
    abc := pow(23,n)+n*pow(23,n-1)
    // 保证结果非负
    return ((all - (a+b+c-ab-ac-bc+abc))%MOD+MOD)%MOD
}
// 快速幂，注意MOD取余的位置
func pow(x,y int)int{
    res := 1
    for y>0{
        if y%2==1{
            res=res*x%MOD
        }
        x=x*x%MOD
        y/=2
    }
    return res
}
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

28、树状数组

• 实现快速更新和查询数组，可以用线段树或者树状数组
• 树状数组
  • 传统数组修改复杂度是O(1)，查询是O(n)
  • 如果是前缀和数组，修改复杂度是O(n)，查询是O(1)
  • 如果结合两种方式，使得修改和查询复杂度都在1-n之间，就诞生了树状数组
  • 数组arr[i]保存的是前面若干位二进制下标数组值的和，第k位数字需要累加在k+lowbit(k)位上
  • 例如arr[3]，3=11，lowbit(11)=1，所以arr[3]需要累加到arr[3+1]=arr[4]上，而4=100，需要累加到arr[4+4]=arr[8]上，依此类推，就像下图所示，1-2-4-8,3-4-8
  • 所以可以把树状数组看做二进制的前缀和
  • 如果我想知道arr[4]上的数字，就需要计算arr[1:4]-arr[1:3]，如何计算arr[1:4]呢？arr[4]就是arr[1:4]，如何计算arr[1:3]呢？arr[1:3]=arr[3]+arr[1:2]
  • 如何获得最低位1表示的数字？lowbit(n) = n&-n = (^n+1)&n

// 结构体，可以添加一个表示数组元素个数+1的属性
// 由于idx=0时没有最低位1，所以不能在arr[0]存入数据
type NumArray struct {
    Tree []int
}

// 初始化
func Constructor(nums []int) NumArray {
    res := NumArray{Tree:make([]int,len(nums)+1)}
    for i,x := range nums{
        res.Update(i,x)
    }
    return res
}

// 更新第idx位数字
func (this *NumArray) Update(idx int, val int)  {
    val = val-this.SumRange(idx,idx)
    n := len(this.Tree)
    idx++
    for ;idx<n;idx+=(idx&-idx){
        this.Tree[idx]+=val
    }
    return
}

// 获得前idx位数字和
func (this *NumArray) Get(idx int) int {
    res := 0
    for ;idx>0;idx-=(idx&-idx){
        res+=this.Tree[idx]
    }
    return res
}

// 计算[left, right]的和
func (this *NumArray) SumRange(left int, right int) int {
    return this.Get(right+1)-this.Get(left)
}
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

29、避免除法的浮点误差

对于float格式变量而言，运算是有误差的，例如：

1 - 0.22222222 * 3  = 0.3333333
4 - 0.22222222 * 12 = 0.33333325
1
2

避免除法的浮点误差有两种方法：

除法改乘法，z=1/3=4/12，1*12==4*3

除数和被除数除以最大公约数，4/gcd(4,12)，12/gcd(4,12)

// 计算最大公约数
func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}
1
2
3
4
5
6
7

30、辅助栈

• 要求常数时间返回最小值，可以创建一个栈保存当前值，一个辅助栈保存当前下标对应的最小值

    stack = 5 6 1 4 0 2
  austack = 5 5 1 1 0 0
  1
  2

• 如果进一步要求不能使用额外空间，只需要一个栈，一个最小值变量，栈内保存当前值与上一个最小值的差值，例如6-5,1-5,4-1，如果差值<=0，当前值小于上一个最小值，那么最小值就是当前值，如果差值>0，当前值大于上一个最小值，那么最小值+差值就是当前值

• 返回当前值的之后根据保存的diff大小决定最小值变量是否需要加上diff

   put = 5 6  1 4  0 2
   min = 5 5  1 1  0 0
  diff = 5 1 -4 3 -1 2
   pop = if diff<0 return min 
         if diff>=0 return min+diff
       = 5 6 1 4 0 2
  1
  2
  3
  4
  5
  6

31、寻找相交链表的相交点

• A比B少了一个点，如果从a1和b2分别开始往下遍历，当两个cur相同时就是相交点了
• 那么如何从b2开始遍历呢？注意到从两个头结点开始遍历，当A遍历完时，B在c3处，距离遍历结束正好差了B-A的距离，此时让A的cur遍历B，B的cur在遍历结束后去遍历A，就能实现两个cur分别从a1和b2开始往下遍历了

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    cur1,cur2 := headA,headB
    for cur1!=cur2{
        if cur1==nil{
            cur1 = headB
        }else{
            cur1 = cur1.Next
        }
        if cur2==nil{
            cur2 = headA
        }else{
            cur2 = cur2.Next
        }
    }
    return cur1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

32、排序算法

计数排序：

nums = [2 3 8 7 1 2 2 2 7 3 9 8 2 1 4 2 4 6 9 2]
// arr[i]记录数字i出现的次数，arr的长度就是出现数字的max-min+1 = 9-1+1 = 9
arr  = [2 6 2 2 0 1 2 2 2]
		1 2 3 4 5 6 7 8 9
sort = [11 222222 33 44 6 77 88 99]
1
2
3
4
5

基数排序：

每次排序需要把每个分组数据保存在二维数组的桶里，如果从百位开始比较，就不能使用桶排序，可以用计数排序

33、从1开始计数的26进制

• 正常k进制是从0开始的，0……k-1，对n，每次取余数作为当前位值，再除以k
• 这道题是从1开始计数的，所以每次计算可以先减去1，实现整体偏移的效果，然后再正常计算

func convertToTitle(n int) string {
    s := []byte{}
    for n>0{
        // 从1开始的26进制，最开始减去1，实现整体偏移，接下来就按10进制正常算
        n--
        s = append(s,byte(n%26+'A'))
        n/=26
    }
    res := strings.Builder{}
    for i:=len(s)-1;i>=0;i--{
        res.WriteByte(s[i])
    }
    return res.String()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

34、摩尔投票法

• 摩尔投票法就是设置初始选举人=nums[0]，计数为1，后续遍历不等于选举人就计数减一，当计数为零时就换选举人，这个算法适用条件是存在超过一半的元素

func majorityElement(nums []int) int {
    // 摩尔投票法
    cand,cnt := nums[0],1
    for _,x := range nums[1:]{
        if x==cand{
            cnt++
        }else{
            cnt--
            if cnt==0{
                cand=x
                cnt=1
            }
        }
    }
    return cand
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

升级问题，找出nums中出现次数超过n/k次的元素

• 摩尔投票算法的核心思想是对拼消耗，而出现次数超过n/k的元素种类不超过k-1个，所以我们先选出k-1个可能的选举人，然后统计选举人的出现次数，最后把出现次数超过n/k的选举人存入答案即可

// 摩尔投票算法的核心是对拼消耗
func majorityElement(nums []int) []int {
    n := len(nums)
    // 出现次数超过n/k的元素种类不超过k-1个
    k := 3
    // 先选出所有可能的选举者
    voters := make(map[int]int,k-1)
    for _,x := range nums{
        // 已有3个候选者，并且x不是候选者
        if len(voters)==k-1 && voters[x]==0{
            for key,val := range voters{
                if val==1{
                    delete(voters,key)
                }else{
                    voters[key]--
                }
            }
        }else{
            voters[x]++
        }
    }
    // 找到k-1个可能的选举者，二次遍历统计每个选举者的出现次数
    for key := range voters{
        voters[key]=0
    }
    for _,x := range nums{
        voters[x]++
    }
    // 把可能选举者中，出现次数大于n/k的放入答案中
    ans := make([]int,0,k-1)
    for key,val := range voters{
        if val>n/k{
            ans = append(ans,key)
        }
    }
    return ans
}
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

35、计算阶乘结果尾随0的个数

• 如果阶乘项中包含10的倍数，例如10，20，30，那么阶乘计算的结果就有尾随0，如果阶乘项中包含5和2的因式，阶乘结果也有尾随0，那么就可以计算min(因子5的个数, 因子2的个数)，显而易见，因子5更少
• 如何计算因子5的个数？例如n=36，每隔5个计数就有一个数包含因子5，即36/5=7个，这7个中又有7/5=1个包含因子25，即两个因子5，如此不断除以5，直到除尽，就找到因子5的个数了

func trailingZeroes(n int) (res int) {
    for n>0{
        n/=5
        res += n
    }
    return res
}
1
2
3
4
5
6
7

36、分治，将二进制前后颠倒

• 对于32位数字，如果前16和后16位数字分别颠倒，将两个结果颠倒位置，就能得出结果，如何将两个结果颠倒位置呢？将数字与上一个掩码0xffff0000，就能得到前16位，后移16位，后半截做相同处理，与上掩码再移位，就可以实现结果颠倒，利用分治的思想，最小单位是1位。

  

func reverseBits(n uint32) uint32 {
    // 32位数字n前后16位交换
    n = (n >> 16) | (n << 16)
    // 每个16位中前后8位交换
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
    // 每个8位中前后4位交换
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
    // 每个4位中前后2位交换
    n = ((n & 0b11001100110011001100110011001100) >> 2) |
    ((n & 0b00110011001100110011001100110011) << 2)
    // 每个2位中前后1位交换
    n = ((n & 0b10101010101010101010101010101010) >> 1) |
    ((n & 0b01010101010101010101010101010101) << 1)
    return n
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

37、最小堆

• 在queries中，如果a==b或者h[a]=h[b]，那么就只能从b后面找一个高度大于h[a]的跳过去
• 一次遍历如何保证两个约束？首先对queries进行分类，按照b相同的分到一组，在遍历时，如果i>b，就可以和h[a]进行比较，如果大于h[a]，那么i就是答案，答案记录在数组中，所以在分组时，不仅要保存a，还要保存[a,b]在queries中的下标
• 以上思路用golang写是通不过的，会超时，可以发现需要i>b才能对h[a]进行比较，所以在遍历i结束时，才把以i为b的对应a添加到对比序列中，而且对于对比序列，如果当前遍历的值比对比序列中最小的那个值还要小，那就不需要继续比下去了，意思就是我们需要按照h[a]的大小排序，小的在前面，比对通过了还要排出去，这个数据结构就是最小堆，golang中没有最小堆，所以我们用python写

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        res = [-1]*len(queries)
        # 根据b分类保存a的高度和在queries中的位置
        temp = [[] for _ in heights]
        for qi,(i,j) in enumerate(queries):
            # 确保ab先后顺序
            if i>j: i,j = j,i
            # 如果ab出发位置相同，或者h[a]
            if i==j or heights[i]<heights[j]: res[qi] = j
            else: temp[j].append((heights[i], qi))
        heap = []
        # 遍历heights，如果x大于最小堆中最小的高度，即堆顶，那么i就是堆顶的答案
        for i,x in enumerate(heights):
            while heap and heap[0][0]<x:
                qi = heappop(heap)[1]
                res[qi] = i
            # 确保后续遍历的i都在temp中b的后边，这样x>h[a]时，能从a和b跳到i
            for arr in temp[i]:
                heappush(heap, arr)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

38、一定范围数字按位与

• 最开始思路是找规律，left>1<
• 对于数字5和7，他们的二进制分别是101和111，[5, 7]区间内所有数字按位与，第一位和第二位结果是0，那我们只需要找两个端点的相同前缀，对于5和7，相同前缀就是100
• 找相同前缀有两个思路，同时后移，直到两个数字相同，再前移回去，要么就是right不断减去最后一个1，直到小于left

func rangeBitwiseAnd(left int, right int) int {
    i:=0
    for ;left!=right;i++{
        left>>=1
        right>>=1
    }
    return left<<i
}

func rangeBitwiseAnd(left int, right int) int {
    for left<right{
        right -= right&-right
    }
    return right
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

39、统计小于n的所有质数个数，线性质数筛

• 埃氏筛的原理，是将2_{n-1假设为质数，从2}根号n遍历，遍历数字的倍数全都不是质数，遍历结束剩下未被标记的就是质数。但是这有个问题，例如12，12=2*6=3*4，会被标记多次，所以埃氏筛时间复杂度是O(nlognlogn)

• 线性筛的时间复杂度可以降低到o(n)，一个质数只会被标记一次，不会被重复标记，它的原理是假设2_{n-1是质数，从2}n-1遍历，将质数保存在数组中，遍历的数字x乘以所有质数，乘积标记为非质数，当遍历的数字x可以除尽遍历的质数时，就不用继续乘之后的质数了，因为当前遍历的数字x中包含了其他质因子，而x的倍数已经被这个质因子排除过了，这样就保证了所有数只会被标记一次

• 埃氏筛和线性筛的区别，如下图所示，埃氏筛是一列一列标记数字的，而线性筛是一行一行标记数字的，红色是线性筛跳过的，例如3*4，4可以除尽质数2，所以4以及4的倍数已经被标记过了

func countPrimes(n int) int {
    primes := []int{}
    isPrime := make([]bool, n)
    // 假设2~n-1全是素数
    for i := range isPrime{
        isPrime[i] = true
    }
    for i:=2;i<n;i++{
        if isPrime[i]{
            primes = append(primes, i)
        }
        for _,p := range primes{
            if i*p>=n{
                break
            }
            // i的倍数不是素数
            isPrime[i*p] = false
            // i中除了p还包含其他质因子，那么i的倍数都已经被这个质因子排除了
            if i%p==0{
                break
            }
        }
    }
    return len(primes)
}
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

40、建图，广度优先遍历

• 这道题是一道经典的图算法题，而且是有向图，需要先建图，并记录每个节点的入度个数，每次不断遍历入度个数为0的节点，即是前置课程已经学完的课程，如果遍历结束课程没有学完，那么这个有向图就有环

func findOrder(numCourses int, prerequisites [][]int) []int {
    // 广度优先遍历，从最先要学的科目开始遍历
    // 建图，一个二维数组存储有向图，一个一维数组存储每个节点入度，入度个数就是要学的科目数
    edges := make([][]int,numCourses)
    indeg := make([]int,numCourses)
    for _,arr := range prerequisites{
        edges[arr[1]] = append(edges[arr[1]], arr[0])
        indeg[arr[0]]++
    }
    // 第一轮要遍历的科目
    q := []int{}
    for i,x := range indeg{
        if x==0{
            q = append(q,i)
        }
    }
    // 广度优先遍历
    res := make([]int,0,numCourses)
    for len(q)>0{
        cour := q[0]
        q = q[1:]
        res = append(res,cour)
        for _,c := range edges[cour]{
            indeg[c]--
            if indeg[c]==0{
                q = append(q,c)
            }
        }
    }
    // 有向图闭环，则不可能完成所有课程
    if len(res)!=numCourses{
        return []int{}
    }
    return res
}
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

41、单调栈，贡献

• 维护一个单调递增栈，当栈内元素弹出时，结果加上这个值乘以这个值的贡献，例如[3,1,2,4]，对于数字2的贡献就是[2,3]对应的子数组个数，即3，计算这个贡献需要得到数组左右端点以2为分界线，左边区间是[l,i]，右边区间是[i,r]，总的子数组个数是(i-l+1)*(r-i+1)，在单调栈中记录下标

func sumSubarrayMins(arr []int) int {
    MOD := int(1e9)+7
    n := len(arr)
    // 单调栈
    stack := make([]int,n+1)
    stack[0] = -1
    // idx指向单调栈的末位下标
    idx := 1
    res := 0
    for i,x := range arr{
        for idx>1 && x<=arr[stack[idx-1]]{
            // 对于单调栈中大于x的值，res = res + 值*值的贡献
            // 本题中值的贡献就是值作为最小值的范围[l,r]中子数组个数
            res += arr[stack[idx-1]]*(stack[idx-1]-stack[idx-2])*(i-stack[idx-1])
            res %= MOD
            idx--
        }
        stack[idx] = i
        idx++
    }
    for idx>1{
        res += arr[stack[idx-1]]*(stack[idx-1]-stack[idx-2])*(n-stack[idx-1])
        res %= MOD
        idx--
    }
    return res
}
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

42、滑动窗口，单调队列

• 如果滑动窗口左右端点向同一方向移动，并且求其最大值或最小值，那么可以用单调队列来优化算法

func maxSlidingWindow(nums []int, k int) []int {
    // 单调队列，滑动窗口左右端点向同一方向移动
    res := []int{}
    // 单调队列中元素顺序递减，首位元素下标不在窗口内时弹出队列，
    q := []int{}
    for i,x := range nums{
        // 入队，保证队列的元素递增
        n := len(q)
        for n>0 && x>=nums[q[n-1]]{
            q = q[:n-1]
            n--
        }
        q = append(q,i)
        // 出队，如果队首元素不在滑动窗内，就抛出
        if i-k>=q[0]{
            q = q[1:]
        }
        // 保存队列第一个元素，即最大值
        if i>=k-1{
            res = append(res,nums[q[0]])
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

43、计算器

• 这道题虽然不是四则运算，但是我们可以按照四则运算的方式来解题
• 正常思路是两个栈，一个保存数字，一个保存符号，如果遇到’)‘，就计算，直到遇到’('，但是有个问题，对于2-1+2会算成2-(1+2)，如何处理减号呢？如果遇到符号，无论是+还是-，都开始计算，这样2-1+2就是2-1+2=1+2=3，这样还有个好处，就是可以一边遍历一边计算，遍历完成直接返回答案，但是还有个问题，对于-(2+3)这种，减号前面没有值，那又该怎么办呢？可以在初始化时，就在栈中保存一个0，最后返回栈的最后一个元素值，而且在遍历中遇到减号时，添加一个加号和一个0，这样就避免了减号表示负号、没有减数的问题
• 这道题还有一个捷径，因为只有+和-，那么遇到括号时，如果括号前面是+，括号里面就是原符号，如果括号前面是-，类似于-(2+3)，括号里面就是相反的符号，可以用+1，-1来表示+和-，从而简化符号转化过程

func calculate(s string) int {
    // 避免-2这种情况
    nums := []int{0}
    ops := []byte{}
    // 算完或者算到'('
    cal := func(){
        i,j := len(nums)-1,len(ops)-1
        for ;i>0 && j>=0 && ops[j]!='(';j--{
            if ops[j]=='+'{
                nums[i-1] += nums[i]
            }else{
                nums[i-1] -= nums[i]
            }
            i--
        }
        nums = nums[:i+1]
        ops = ops[:j+1]
    }
    for i:=0;i<len(s);{
        if s[i]==' '{
            i++
        }else if s[i]=='('{
            ops = append(ops,s[i])
            i++
        }else if s[i]=='+' || s[i]=='-'{
            // 如果有新操作+/-加入队列，就把能算的都算了，这样就避免2-1+2=-1这种问题
            cal()
            if s[i]=='-'{
                ops = append(ops,'+')
                nums = append(nums,0)
            }
            ops = append(ops,s[i])
            i++
        }else if s[i]==')'{
            cal()
            ops = ops[:len(ops)-1]
            i++
        }else{
            j := i
            for ;j<len(s) && s[j]>='0' && s[j]<='9';j++{}
            num,_ := strconv.Atoi(s[i:j])
            nums = append(nums,num)
            i = j
        }
    }
    cal()
    return nums[len(nums)-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

44、从数组中找出只出现一次的两个数字

• 如果可以将两个数字区分开，或者分成两个数组，那么对两个数组异或，就可以得到答案
• 如何区分两个只出现一次的数字？对nums进行异或，得到的结果就是两个数字的异或结果，最低位1就是两个数字不同的最低位，用最低位1表示的数字作为mask，对数组nums进行区分，分成两个数组，从而成功将两个数字分开。

func singleNumber(nums []int) []int {
    //首先将所有数字异或
    n1 := 0
    for _,x := range nums{
        n1 ^= x
    }
    //所有数字异或结果就是答案两个数字异或的结果，最低位1就是两个数字不相同的最低位
    mask := n1&(-n1)
    //通过mask将nums分成两组，答案的两个数字就分别在两组中
    res := []int{0,0}
    for _,x := range nums{
        if x&mask==mask{
            res[0] ^= x
        }else{
            res[1] ^= x
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

45、数组不同范围增加不同值，差分数组

• 由于数据大小from、to不超过1000，所以可以创建一个长为1001的数组，把trips中每个范围的数据加到数组中，如果数组中出现超过capacity的数字，就返回false
• 以上方法需要把例子中1-5,3-7都遍历一遍，其实没有必要这么做，只需在1标记增加2，在5标记减少2，记录差分数组，然后遍历累加，判断遍历过程中是否超过capacity即可

func carPooling(trips [][]int, capacity int) bool {
    nums := make([]int,1001)
    for _,arr := range trips{
        nums[arr[1]]+=arr[0]
        nums[arr[2]]-=arr[0]
    }
    fmt.Println(nums)
    sum := 0
    for _,x := range nums{
        sum += x
        if sum>capacity{
            return false
        }
    }
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 差分数组[0 2 0 3 0 -2 0 -3 0]
• 其实可以不用设置1001的数组，直接设置一个变量在遍历过程中累加减去，不过这种方法我没做出来

第二种思路就是在hash中添加区间的左右端点，然后排序，根据端点顺序进行遍历相加，比1001长度数组要快

func carPooling(trips [][]int, capacity int) bool {
    d := map[int]int{}
    for _, t := range trips {
        d[t[1]] += t[0]
        d[t[2]] -= t[0]
    }
    keys := make([]int, 0, len(d))
    for k := range d {
        keys = append(keys, k)
    }
    slices.Sort(keys)
    s := 0
    for _, k := range keys {
        s += d[k]
        if s > capacity {
            return false
        }
    }
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

46、巴什博弈

• 巴什博弈，如果n%(m+1)!=0，那么先手总是赢
• 让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜；如果堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，他可以将剩余的石头全部取完，从而他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。
• 我们继续推理，假设当前堆里只剩下五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。显然我们继续推理，可以看到它会以相同的模式不断重复 n=4,8,12,16,… 基本可以看出如果堆里的石头数目为 4 的倍数时，你一定会输掉游戏。
• 如果总的石头数目为 4 的倍数时，因为无论你取多少石头，对方总有对应的取法，让剩余的石头的数目继续为 4 的倍数。对于你或者你的对手取石头时，显然最优的选择是当前己方取完石头后，让剩余的石头的数目为 4 的倍数。假设当前的石头数目为 x，如果 x 为 4 的倍数时，则此时你必然会输掉游戏；如果 x 不为 4 的倍数时，则此时你只需要取走 x mod 4 个石头时，则剩余的石头数目必然为 4 的倍数，从而对手会输掉游戏。

func canWinNim(n int) bool {
    return n%(3+1)!=0
}
1
2
3

47、思维题，需要添加硬币的最小数

• 思维题，归纳法，假设我能取得[0:s-1]的所有数字，此时我又添加了一个x，如果0+x>s，那我能得到[0:s-1]和[x:s+x-1]，这两个区间就缺了一部分，所以需要添加一个值y，使得s-1+1=0+y，即添加数字s
• 对于[1,4,10]，添加1时，[0:1]，添加4时，[0:1]+[4:5]，缺少2，所以先添加2，[0:1]+[2:3]=[0:3]，再添加4，得到[0:7]，添加10时，[0:7]+[10:17]，缺少8，所以先添加8，得到[0:15]，再添加10，得到[0:25]，此时囊括了target=19，所以只需要添加三个数字
• 写代码时，需要遍历s，在扩展s时，如果排序后的coins缺失一部分，就说明需要添加一个数字，这个数字就是s

func minimumAddedCoins(coins []int, target int) int {
    sort.Ints(coins)
    // 表示可以组成[0:s-1]的所有数字
    s := 1
    idx := 0
    res := 0
    for s<=target{
        if idx<len(coins) && s>=coins[idx]{
            // [0:s-1]+x -> [x:s+x-1]
            s += coins[idx]
            idx++
        }else{
            // coins用完了，或者缺失了一个中间值s
            s += s
            res++
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

48、分组循环

• 这道题有两个条件，一个是m种字符恰好出现k次，一个是相邻字符之差最多为2，那么可以先根据条件2来圈定一个数组长度，在这个数组中通过滑动窗口判断每个子字符串是否满足条件1，注意条件1中是m种字符恰好出现k次，那么滑动窗口的长度就是m*k，遍历m，从1到26，不断移动滑动窗口，右加左减，每次对窗口内元素判断是否满足条件1，最后返回满足条件的子字符串总个数。

func countCompleteSubstrings(word string, k int) int {
    res := 0
    // 根据条件将问题分成两部分，实现解耦
    for i,n := 0,len(word); i<n; {
        // 根据第二个条件，截取[start:i]的部分
        start := i
        for i++; i<n && abs(int(word[i])-int(word[i-1]))<=2; i++{}
        // 根据第一个条件，判断截取部分有几个完全字符串
        res += getNum(word[start:i], k)
    }
    return res
}
func abs(i int)int{ if i<0{return -i}else{return i} }
// 分组循环
func getNum(s string, k int)(res int){
    // s中每个字符恰好出现k次 =>> len(s) = s中字符种类*k = m*k
    // 枚举m种字符，用m*k的滑动窗口，判断窗口内每种是否恰好出现k次
    for m:=1;m<=26 && m*k<=len(s);m++{
        cnt := [26]int{}
        check := func(){
            for i := range cnt{
                if cnt[i]>0 && cnt[i]!=k{
                    // 如果不写成函数，这里只能用goto，或者设置一个bool值
                    // 写成函数后可以用return来跳过res++
                    return
                }
            }
            res++
        }
        for r,in := range s{
            cnt[in-'a']++
            // 窗口左端点l+1，如果l>=0，即窗口长度大于m*k，左边需要出队列
            if l:=r+1-m*k;l>=0{
                // 滑动窗口内的字符出现次数是否满足条件二
                check()
                cnt[s[l]-'a']--
            }
        }
    }
    return
}
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

49、动态规划的无后效性

• 这道题一看就是动态规划，但是如果从左上到右下，需要保存每一条路径的总点数和最小点数，前者用于计算当前点数是否需要更新最小点数，后者是需要维护的答案，这不满足动态规划的无后效性，当前情况的选择被以前的选择所左右，所以可以从右下往左上走
• 从右下到左上，dp[i][j]是从当前位置到右下所需的最小生命值，最终返回dp[0][0]
• 题中人物正着走既会加分也会扣分，而我们要求的是这个过程的最小值，所以正着求比较困难，如果倒着求，一些后面很大的加分实际上对结果没有帮助，因为我们求得是最小值，所以dp中我们保存的是最小生命值，这个值不能小于1，所以我们用max来重置dp状态，排除迷宫后端大加分的影响，也正因如此才能不用像正向那样保存总点数。

func calculateMinimumHP(dungeon [][]int) int {
    n,m := len(dungeon),len(dungeon[0])
    dp := make([][]int,n+1)
    for i := range dp{
        dp[i] = make([]int,m+1)
        for j := range dp[i]{
            dp[i][j] = math.MaxInt
        }
    }
    // 对于终点，该点所需最小体力是1-nums[n-1][m-1]
    dp[n][m-1], dp[n-1][m] = 1,1
    // 从右下往左上走，nums[i][j]是从这里出发能走到终点所需最小体力
    for i:=n-1;i>=0;i--{
        for j:=m-1;j>=0;j--{
            dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j], 1)
        }
    }
    return dp[0][0]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

50、求幂、求余数

• 这道题就是用快速幂很快就能做出来，但是我被一个测试用例卡住了，被卡住的原因是，pow(x,n)溢出了，注意到第二个条件中有两个求余，应该在计算pow的时候加入被除数一起算，pow(x,n,MOD)

func getGoodIndices(variables [][]int, target int) []int {
    res := make([]int,0,len(variables))
    for i,arr := range variables{
        a,b,c,m := arr[0],arr[1],arr[2],arr[3]
        if pow(pow(a,b,10),c,m)==target{
            res = append(res,i)
        }
    }
    return res
}
func pow(x,n,MOD int)int{
    res := 1
    for n>0{
        if n%2==1{
            res = res*x%MOD
        }
        x = x*x%MOD
        n/=2
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

51、可以分割成多少个子数组

• 最开始想法是找到包含相同元素的左右下标，例如[3,1,2,1,2,4,5]，下标就是1和4，左边分割子数组个数乘以右边分割子数组个数就是答案，但是求分割子数组很难。而且这种想法是错误的，例如[3,1,1,4,2,2,5]，左右下标可能不唯一
• 对于示例应该这么去想，求有多少条分割线，例如[3,1,2,1,2,4,5]，3有一条，1,2,1,2有一条，4有一条，5有一条，每条分割线可以选也可以不选，将数组分割成长短不一的子数组，总共有2^m-1种分割情况，m就是分割线的个数

func numberOfGoodPartitions(nums []int) int {
    lastIdx := map[int]int{}
    for i,x := range nums{
        lastIdx[x] = i
    }
    maxi := -1
    // 分割线的个数
    m := 0
    for i,x := range nums{
        maxi = max(maxi,lastIdx[x])
        if maxi==i{
            m++
        }
    }
    return pow(2,m-1,int(1e9)+7)
}
func pow(x,n,MOD int)int{
    res := 1
    for n>0{
        if n%2==1{
            res = res*x%MOD
        }
        x = x*x%MOD
        n /= 2
    }
    return res
}
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

52、Flyod和Dijkstra

• Flyod可以应用于正负权图，多源最短路径，时间复杂度O(n3)，核心思想从i->j，枚举k当中间节点，更新最短路径

• Dijkstra只能应用于正权图，单源最短路径，时间复杂度O(n2)，核心思想从0->i，枚举0连接的最短路径的节点k，能否用k更新0->其他i

• 这道题显然是多源最短路径，用Flyod，Flyod算法精髓是用中间节点来优化最短路径，i->j优化成i->k->j

• 递归选或不选，dfs(i,j,k)表示i->j的中间节点都小于k

  dfs(i,j,k)=min(dfs(i,j,k-1),dfs(i,k,k-1)+dfs(k,j,k-1))

• 递归改动态规划，递归的终止条件就是dp数组的初始值

  dp[k][i][j] = min(dp[k-1][i][j],dp[k-1][i][k]+d[k-1][k][j])

• dp数组空间优化，枚举k，对所有i和j进行遍历，计算k能否成为中间节点

  d[i][j] = min(d[i][j], d[i][k]+d[k][j])

// 多源最短路径，Flyod
func findTheCity(n int, edges [][]int, distanceThreshold int) int {
    // 建图
    d := make([][]int,n)
    for i := range d{
        d[i] = make([]int,n)
        for j := range d[i]{
            d[i][j] = 10001
        }
    }
    for _,arr := range edges{
        from,to,weight := arr[0],arr[1],arr[2]
        d[from][to] = weight
        d[to][from] = weight
    }
    // Flyod求最短路径
    for k:=0;k<n;k++{
        for i:=0;i<n;i++{
            for j:=0;j<n;j++{
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
                // 如果要记录i->j的中间节点
                // 取中间节点时递归path[i][j]->path[k][j]->...
                // path[i][j] = k
            }
        }
    }
    // 返回符合要求的答案
    res := -1
    minc := n
    for i,arr := range d{
        sum := 0
        for j,x := range arr{
            if i==j{
                continue
            }
            if x<=distanceThreshold{
                sum++
            }
        }
        if sum<=minc{
            minc = sum
            res = i
        }
    }
    return res
}
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

53、最大值的最小值，从起点到终点联通

• 这道题求最大值的最小值，那么第一个思路就是二分，看数据范围是[0,1e6]，在这个范围内对结果进行二分，假定结果是mid，进行广度优先遍历，从起点开始往四个方向走，只要路径中高度差最大值小于mid且能走到终点，那么这个假定的结果就是可选的，我们二分找一个最小的可选结果
• 将图中的所有边按照权值从小到大进行排序，并依次加入并查集中，当我们加入一条权值为x的边之后，如果左上角和右下角从非连通状态变为连通状态，那么x即为答案。

二分查找：

type pair struct{x,y int}
func minimumEffortPath(heights [][]int) int {
    // 二分，在[0,1e6]中对结果进行二分，判断条件是以mid为最大差值能否走到终点
    n,m := len(heights),len(heights[0])
    d := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    l,r := 0,int(1e6)
    mid := 0
    visit := make([]bool,n*m)
    // 广度优先遍历，从上下左右四个方向同时走，只要能走到终点就返回true
    var bfs func(int,int)bool
    bfs = func(i,j int)bool{
        clear(visit)
        visit[i*m+j] = true
        q := []pair{{i,j}}
        for {
            temp := []pair{}
            for _,p := range q{
                if p.x==n-1 && p.y==m-1{
                    return true
                }
                for _,pd := range d{
                    x,y := p.x+pd.x,p.y+pd.y
                    if x>=0 && x<n && y>=0 && y<m && !visit[x*m+y] && abs(heights[x][y]-heights[p.x][p.y])<=mid{
                        visit[x*m+y] = true
                        temp = append(temp,pair{x,y})
                    }
                }
            }
            if len(temp)==0{
                break
            }
            q = temp
        }
        return false
    }
    // 从(0,0)开始走
    for l<r{
        mid = (l+r)/2
        if bfs(0,0){
            // 走得通，mid偏大，还可以更小
            r = mid
        }else{
            // 假定的结果mid太小了，走不通
            l = mid+1
        }
    }
    return l
}
func abs(x int)int{if x<0{return -x}else{return x}}
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

并查集：

// h表示x->y之间的高度差
type pair struct{x,y,h int}
func minimumEffortPath(heights [][]int) int {
    n,m := len(heights),len(heights[0])
    fa := make([]int, n*m)
    for i := range fa{
        fa[i] = i
    }
    var find func(int)int
    find = func(x int)int{
        if fa[x] != x{
            fa[x] = find(fa[x])
        }
        return fa[x]
    }
    // 只需记录左上点到本点的边
    edges := []pair{}
    for i,arr := range heights{
        for j,h := range arr{
            if i>0{
                edges = append(edges,pair{(i-1)*m+j,i*m+j,abs(h-heights[i-1][j])})
            }
            if j>0{
                edges = append(edges,pair{i*m+j-1,i*m+j,abs(h-heights[i][j-1])})
            }
        }
    }
    // 根据边权值排序
    sort.Slice(edges, func(i,j int)bool{return edges[i].h<edges[j].h})
    // 从小到大将边加入并查集中，如果加入一条边后，可以从起点到终点，那么答案就是这条边边权
    for _,p := range edges{
        fa[find(p.x)] = find(p.y)
        if find(0)==find(n*m-1){
            return p.h
        }
    }
    // 对于单点图，edges为空，没有其他点和它有边，结果是0
    return 0
}
func abs(x int)int{if x<0{return -x}else{return x}}
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

54、Flyod+暴力枚举

• 这道题只看出要用Floyd来做，但不知道求出最短路径后怎么办？
• 看到数据范围，n最多只有10个，那么可以暴力枚举，实际上是总容易忽略的解法，枚举每个分部要么开，要么关，只有10个分部的情况下，最多只有1<<10，即1024种情况，每次枚举计算当前假设剩余的分部的最短路径，如果其中最短路径仍大于maxDistance，就不记录这个情况，否则返回1

func numberOfSets(n int, maxDistance int, roads [][]int) int {
    // 暴力枚举，mask=0b1100110011，表示编号为0,1,4,5,8,9的6个分部保留，其余分部删除
    // 建图
    d := make([][]int,n)
    for i := range d{
        d[i] = make([]int,n)
        for j := range d[i]{
            if i==j{continue}
            // 防止加法溢出
            d[i][j] = math.MaxInt/2
        }
    }
    for _,arr := range roads{
        x,y,v := arr[0],arr[1],arr[2]
        d[x][y] = min(d[x][y],v)
        d[y][x] = min(d[y][x],v)
    }
    // Floyd算法
    var f func(int)int
    f = func(mask int)int{
        // 保留的部分
        idx := make([]int,0,n)
        for i:=0;i<n;i++{
            if mask>>i&1==1{
                idx = append(idx,i)
            }
        }
        nums := make([][]int,n)
        for _,i := range idx{
            nums[i] = make([]int,n)
            copy(nums[i],d[i])
        }
        for _,k := range idx{
            for _,i := range idx{
                for _,j := range idx{
                    nums[i][j] = min(nums[i][j],nums[i][k]+nums[k][j])
                }
            }
        }
        for _,i := range idx{
            for _,j := range idx{
                if nums[i][j]>maxDistance{
                    return 0
                }
            }
        }
        return 1
    }
    // 暴力枚举所有可能情况
    res := 0
    for i:=0;i<1<<n;i++{
        res += f(i)
    }
    return res
}
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

• 代码中有一个小细节，建表的时候，将初始化的最大值设为MaxInt的一半，这是避免在相加的时候出现溢出，溢出也是代码过程容易忽略的问题

55、子序列DP、子序列 + 考虑相邻元素

• 子序列 + 不考虑相邻元素 = 选或不选
• 子序列 + 考虑相邻元素 = 枚举选哪个
• 尝试选或不选超时，应该用枚举选哪个，i之后从i+1~n-1选一个作为下一个子序列下标，依此类推，可以写成递推

func getWordsInLongestSubsequence(n int, words []string, groups []int) []string {
    // dp[i]表示i~n-1中选出的最长子序列长度
    dp := make([]int,n)
    // 下一个子序列的下标，用于记录子序列
    from := make([]int,n)
    start := n-1
    for i:=n-1;i>=0;i--{
        for j:=i+1;j<n;j++{
            if dp[j]>dp[i] && groups[i]!=groups[j] && isOk(words[i],words[j]){
                dp[i] = dp[j]
                from[i] = j
            }
        }
        // 子序列以i为起始字符串
        dp[i]+=1
        if dp[i]>dp[start]{
            start = i
        }
    }
    // 从maxi开始，记录字符串
    res := make([]string,dp[start])
    for i := range res{
        res[i] = words[start]
        start = from[start]
    }
    return res
}
// 判断字符串是否满足题目要求
func isOk(s1,s2 string)bool{
    if len(s1)!=len(s2){
        return false
    }
    cnt := 0
    for i := range s1{
        if s1[i]!=s2[i]{
            if cnt==1{
                return false
            }
            cnt++
        }
    }
    return cnt==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

56、中位数贪心+回文数打表

• 最开始想法是从数组中位数开始往两边找回文数，计算最小代价，但是超时了
• 可以先对回文数进行打表，[1,1e9]，然后从中位数二分找最临近的回文数，对于偶数数组，中位数有两个，那就找最临近的两个回文数，计算最小代价。

// 回文数打表，找[1,1e9]内所有回文数
var pal = make([]int,0)
func initPalindrome(){
    // 插入前哨兵
    pal = append(pal,0)
    // 对于数字123,12321是回文数，123321也是回文数
    // 遍历[1,int(1e5)]，对所有数字计算对称得到的两个回文数，按顺序组合
    // 注意到12->121和1221,123->12321,123321，如果每10倍计算一次再按顺序组合，就不需要排序，得到[121 1221 12321 123321]，所以遍历[1,int(1e4)]
    for i:=1;i<int(1e5);i*=10{
        for j:=i;j<i*10;j++{
            // 123->12321
            temp := j/10
            x := j
            for temp>0{
                x = x*10+temp%10
                temp /= 10
            }
            pal = append(pal,x)
        }
        if i>int(1e4){
            // 对于12345->123454321和1234554321，只需要计算前一个，不需要计算后一个
            continue
        }
        for j:=i;j<i*10;j++{
            // 123->123321
            temp := j
            x := j
            for temp>0{
                x = x*10+temp%10
                temp /= 10
            }
            pal = append(pal,x)
        }
    }
    // 插入后哨兵，防止二分查找时找不到
    pal = append(pal,int(1e9)+1)
    return
}
func minimumCost(nums []int) int64 {
    if len(pal)==0{
        initPalindrome()
    }
    // 对于数组[10 20 30 40]，小于10的数字离10越近总代价越小，大于40的数字同理，大于10小于20的数字对于10和40的代价和是恒定的，离20越近总代价越小，所以需要找一个离nums中位数最近的回文数
    // 一共两个情况，偶数时找离20和30最近的两个数，奇数时，找离中位数最近的中位数，统一一下，二分找i，计算比较i和i-1
    sort.Ints(nums)
    n := len(nums)
    i := sort.SearchInts(pal,nums[n/2])
    fmt.Println(pal[i],pal[i-1])
    sum1 := 0
    sum2 := 0
    for _,x := range nums{
        sum1 += abs(x-pal[i])
        sum2 += abs(x-pal[i-1])
    }
    return int64(min(sum1,sum2))
}
func abs(x int)int{if x<0{return -x}else{return x}}
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

57、中位数贪心+滑动窗口

• 这道题用滑动窗口就能做，对于一个有序数组，最小操作数的众数就是数组的中位数，至于原因见上一题题解，如果一个滑动窗口的操作频率大于k，就移动左端点，直到操作频率小于等于k
• 如何对一个有序数组快速计算操作数呢，已知目标众数是中位数，那么小于中位数的操作数=m*k-sum，大于中位数的操作数=sum-m*k，可以用前缀和快速计算一段数组的sum

// 选一个数作为目标元素，这个数肯定是中位数，奇数选中间n/2，偶数选(n-1)/2
func maxFrequencyScore(nums []int, k int64) (res int) {
    n := len(nums)
    sort.Ints(nums)
    // 对于一个有序数组，小于中位数的操作次数=m*k-总和，大于中位数的操作次数=总和-m*k
    // 利用前缀和快速计算总和
    pre := make([]int,n+1)
    for i,x := range nums{
        pre[i+1] = pre[i]+x
    }
    // 计算窗口内的操作次数
    cal := func(l,r int)int64{
        m := (l+r)/2
        x := nums[m]
        return int64((m-l)*x-(pre[m]-pre[l])+(pre[r+1]-pre[m+1])-(r-m)*x)
    }
    // 滑动窗口，如果窗口内计算的操作次数大于k，就移动左端点
    l := 0
    for r := range nums{
        for cal(l,r)>k{
            l++
        }
        // fmt.Println(nums[l:r+1],cal(l,r),r-l+1)
        res = max(res,r-l+1)
    }
    return res
}
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

这道题还可以用贡献法来做

58、对二维数组每一行最大值二分

• 如果只需返回任一极大值，那么可以选最大值，对于每一行的最大值进行二分，就将二维数组二分变成了一维数组二分

func findPeakGrid(mat [][]int) []int {
    n := len(mat)
    // 二分查找，按照每一行的最大值进行二分
    maxi := make([]int,n)
    for i,arr := range mat{
        mi := 0
        for j,x := range arr{
            if x>arr[mi]{
                mi = j
            }
        }
        maxi[i] = mi
    }
    l,r := 0,n-1
    for l<r{
        mx := (l+r)/2
        my := maxi[mx]
        // fmt.Println(l,r,mx,my,mat[mx][my])
        if mat[mx][my]<=mat[mx+1][my]{
            // 下面的更大
            l = mx+1
        }else{
            // 该行及上面的更大
            r = mx
        }
    }
    return []int{l,maxi[l]}
}
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

59、最长递增子序列

• 递归，dfs(i)返回以nums[i]为开头或结尾的递增子序列的长度，每次枚举可以选的数字，使用dp进行记忆化搜索。

• 贪心+二分，用一个栈保存递增子序列，与单调栈不同的是，省略出栈这一步，直接把小数添加到适合的位置，由于添加的数字在二分查找到的位置，依旧能保持有序，最终返回栈的长度

  [10,9,2,5,3,7,101,18] ->
  [10]
  [9]
  [2]
  [2,5]
  [2,3]
  [2,3,7]
  [2,3,7,101]
  [2,3,7,18]
  1
  2
  3
  4
  5
  6
  7
  8
  9

func lengthOfLIS(nums []int) int {
    // 二分+贪心
    n := len(nums)
    g := make([]int,0,n)
    for _,x := range nums{
        idx := sort.SearchInts(g,x)
        if idx==len(g){
            g = append(g,x)
        }else{
            g[idx] = x
        }
    }
    return len(g)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果直接在nums中进行修改，用一个变量记录g的长度，就能做到O(1)的空间复杂度

func lengthOfLIS(nums []int) int {
    // 二分+贪心+空间优化
    length := 0
    for _,x := range nums{
        idx := sort.SearchInts(nums[:length],x)
        nums[idx] = x
        if idx==length{   
            length++
        }
    }
    return length
}
1
2
3
4
5
6
7
8
9
10
11
12

60、最小高度树

• 第一种解法，从任意一个节点k出发，找到最远的节点x，找到距离x最远的节点y，最小高度树的根节点就是x->y路径的中间节点，如果是奇数，就是中间点，如果是偶数，就是中间两个节点
• 这个结论记住即可
• 广度优先遍历需要一个数组vis记录每个点的遍历情况，防止循环遍历，还需要一个队列保存节点，比每一层都换一个新的queue要快
• 第二种解法，不断删除度为1的节点，直到最后剩下1个或2个节点，即是答案
• 此时需要按照层数创建多个队列，temp=q，q=nil这种方法比对q遍历，最后q=temp要快得多

func findMinHeightTrees(n int, edges [][]int) (res []int) {
    // 建图
    nums := make([][]int,n)
    for _,arr := range edges{
        nums[arr[0]] = append(nums[arr[0]],arr[1])
        nums[arr[1]] = append(nums[arr[1]],arr[0])
    }
    parents := make([]int,n)
    // 广度优先遍历，用先进后出队列保存节点
    bfs := func(start int)(i int){
        vis := make([]bool,n)
        vis[start] = true
        q := []int{start}
        for len(q)>0{
            i,q = q[0],q[1:]
            for _,j := range nums[i]{
                if !vis[j]{
                    q = append(q,j)
                    vis[j] = true
                    parents[j] = i
                }
            }
        }
        return 
    }
    // 找到与节点0最远的节点x
    x := bfs(0)
    // 找到与节点x最远的节点y
    y := bfs(x)
    // 记录x->y的路径节点，返回中间节点
    path := make([]int,0,n)
    for {
        path = append(path,y)
        if y==x{
            break
        }
        y = parents[y]
    }
    if len(path)%2==0{
        return []int{path[len(path)/2-1],path[len(path)/2]}
    }else{
        return []int{path[len(path)/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

方法二

func findMinHeightTrees(n int, edges [][]int) []int {
    if n==1{
        return []int{0}
    }
    // 建图
    g := make([][]int,n)
    deg := make([]int,n)
    for _,arr := range edges{
        x,y := arr[0],arr[1]
        g[x] = append(g[x],y)
        g[y] = append(g[y],x)
        deg[x]++
        deg[y]++
    }
    // 删除度为1的节点，直到最后剩下1个或2个节点，即是答案
    q := make([]int,0,n)
    for i,x := range deg{
        if x==1{
            q = append(q,i)
        }
    }
    remainNodes := n
    for remainNodes>2{
        remainNodes -= len(q)
        temp := q
        q = nil
        for _,i := range temp{
            for _,j := range g[i]{
                deg[j]--
                if deg[j]==1{
                    q = append(q,j)
                }
            }
        }
    }
    return q
}
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

61、数学题，求正方形内点的总数

• 边长为n的正方形内点的个数是2n(n+1)(2n+1)，这道题的关键是如何证明这一步，最开始的思路是找到一条边的，然后乘4倍，但是正方形内部也有点，不只要计算边长

62、两个杯子倒水

• 每次对杯子x，y只有三种操作，装满、清空、一个杯子倒到另一个杯子，而每个杯子的状态只有0_x，0y，所以可以dp状态划分，dfs深度优先遍历
• 每次操作有很多都是重复的，例如对y倒水，再倒到x内，等效于直接往x中倒水，从数学角度分析，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。这个结论猛地一看好像是错的，如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？
  • 如何证明？
  • 首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；
  • 其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
  • 再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。
  • 因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。
• 所以题目转化为求解等式ax+by=z，首先系数a和b可以是负数，但对结果没有影响。如果a是负数，即要把x往外倒水，可以先往 y 中倒水，再把 y 壶的水倒入 x 壶，如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
• 综上，即求z是否是x和y的最大公约数。

func canMeasureWater(x int, y int, z int) bool {
    if x+y<z{return false}
    // 每个杯子的状态是[0:x]和[0:y]
    // 通过深度优先遍历直到出现dp[z][z]的状态
    // 每次有如下此操作x->y，y->x，->x，x->，->y，y->
    dp := map[int]map[int]bool{}
    var dfs func(int, int)bool
    dfs = func(i,j int)bool{
        if _,ok := dp[i][j];ok{return false}
        if i==z || j==z || i+j==z{return true}
        if dp[i]==nil{
            dp[i] = make(map[int]bool)
        }
        dp[i][j] = true
        res := dfs(x,j)||dfs(0,j)||dfs(i,y)||dfs(i,0)
        if i+j>y{
            res = res||dfs(i+j-y,y)
        }else{
            res = res||dfs(0,i+j)
        }
        if i+j>x{
            res = res||dfs(x,i+j-x)
        }else{
            res = res||dfs(i+j,0)
        }
        return res
    }
    res := dfs(0,0)
    return res
}
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

• 对dp做了空间优化，因为xy的取值范围在[0,1e6]，创建1e12的数组会超过内存限制

func canMeasureWater(x int, y int, z int) bool {
    if x+y<z{return false}
    // 如果z能除尽x和y的最大公约数，就返回true
    return z%gcd(x,y)==0
}
func gcd(x,y int)int{
    for x!=0{
        x,y = y%x,x
    }
    return y
}
1
2
3
4
5
6
7
8
9
10
11

63、枚举操作次数->第i个数->第i个数最小成本

• 题目意思是每次操作将数组向前挪一位，第i个巧克力可以在第j次操作时购买，求最小成本
• 那可以暴力枚举所有的操作次数k，遍历所有数字i，每个数字求[i:i+k]中的最小值，最后求n次操作的最小值
• 但是这种方法时间复杂度是O(n3)，会超时
• 可以先记录所有的操作次数，遍历所有巧克力i，每个巧克力后移j-i次，操作次数就是j-i，这期间求得的最小值加到操作次数中，注意，操作次数为k，并不表示第i个数取得的值是min(i, i+k)，最后返回操作次数的最小值

暴力枚举：

func minCost(nums []int, x int) int64 {
    n := len(nums)
    res := math.MaxInt
    for k:=0;k<n;k++{
        sum := k*x
        for i := range nums{
            temp := math.MaxInt
            for j:=i;j<=i+k;j++{
                temp = min(temp,nums[j%n])
            }
            sum += temp
        }
        res = min(res,sum)
    }
    return int64(res)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

枚举巧克力->操作次数，记录最小值：

func minCost(nums []int, x int) int64 {
    n := len(nums)
    cost := make([]int,n)
    for i := range cost{
        // 换i次的操作成本
        // 换一次操作成本为x，第j个巧克力花费是min(j,j+1)
        // 换二次操作成本为2x，第j个巧克力花费是min(j,j+1,j+2)...依此类推
        cost[i] = i*x
    }
    // 暴力枚举操作次数->每个巧克力->每个巧克力的最小花费，O(n3)
    // 遍历左端点i，维护子数组[i:j]最小值minCost，即每个巧克力->每个巧克力的最小花费
    // 将最小花费加到操作次数中
    // 从nums[i]取到nums[j]需要操作j-i次，所以最小值加到cost[j-i]
    for i,x := range nums{
        minCost := x
        for j:=i;j<n+i;j++{
            minCost = min(minCost, nums[j%n])
            cost[j-i] += minCost
        }
    }
    // 答案就是n次操作cost的最小值
    res := math.MaxInt
    for _,x := range cost{
        res = min(res,x)
    }
    return int64(res)
}
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

64、去除重复字母直至字符串最小

• 显而易见，字符串最长26位，用一个单调栈记录遍历的字符，且从小到大排列，例如bcabc，bc->abc，但是如果栈尾的字母后面不会再出现，就不能去除，例如cbacdcbc，acd->acdb，如果当前遍历的字母s[i]已经在栈中了，就不能比较出入栈，例如abacb，ab->abc
• 以上三条规则就可以得到正确答案

func removeDuplicateLetters(s string) string {
    // 记录26个字母最后一次出现的位置
    last := make([]int,26)
    for i := range last{
        last[i] = -1
    }
    for i,c := range s{
        last[int(c)-97] = i
    }
    // 单调栈，最后结果应该是a,b,c,d...
    stack := make([]byte,26)
    idx := 0
    // 如果当前遍历的s[i]已经在栈里，就不要入栈
    visit := make([]bool,26)
    for i := range s{
        for idx>0 && s[i]<=stack[idx-1] && last[int(stack[idx-1])-97]>i && !visit[int(s[i])-97]{
            visit[int(stack[idx-1])-97] = false
            idx--
        }
        if !visit[int(s[i])-97]{
            visit[int(s[i])-97] = true
            stack[idx] = s[i]
            idx++
        }
    }
    // 返回答案
    res := strings.Builder{}
    res.Write(stack[:idx])
    return res.String()
}
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

65、闰年

年份能整除4，且不能整除100，或者能整除400的才是闰年，2月有29天

if (year%4==0 && year%100!=0) || year%400==0{
	// 闰年
}
1
2
3

1971年1月1日是周五

66、从「自顶向下」的记忆化搜索变为「自底向上」的动态规划

• 这道题根据分治的思想，戳[i:j]的气球中找一个中间气球k，那么dfs(i,j)=dfs(i,k)+nums[i]*nums[k]*nums[j]+dfs(k,j)，初始条件是dfs(0,n-1)

• 如何从自顶向下的记忆化搜索改成自底向上的动态规化呢？看下面这个图

• 这个图像比较形象，记忆化搜索就是递归，从初始条件不断向下递归，而记忆化搜索保证了递归过程的唯一性，那我们就可以自底向上计算，用dp数组保存计算结果，最后计算的就是答案

• 递归时对k进行遍历，状态规划时需要自底向上计算，i从n-1到0，注意遍历顺序

func maxCoins(nums []int) int {
    nums = append(append([]int{1},nums...),1)
    n := len(nums)
    dp := make([][]int,n)
    for i := range dp{
        dp[i] = make([]int,n)
    }
    // 自顶向下的记忆化搜索
    // var dfs func(int,int)int
    // dfs = func(i,j int)int{
    //     if dp[i][j]!=0{
    //         return dp[i][j]
    //     }
    //     res := 0
    //     defer func(){dp[i][j] = res}()
    //     for k:=i+1;k
    //         res = max(res, dfs(i,k)+nums[i]*nums[k]*nums[j]+dfs(k,j))
    //     }
    //     return res
    // }
    // return dfs(0,n-1)
    
    // 自底向上的动态规化
    // 注意i,j,k的遍历顺序
    for i:=n-1;i>=0;i--{
        for j:=i+2;j<n;j++{
            for k:=i+1;k<j;k++{
                dp[i][j] = max(dp[i][j], dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j])
            }
        }
    }
    return dp[0][n-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

67、挑选子序列并拼接

• 这道题的思路是从两个数组得到两个最大子序列，序列长度之和等于k，然后将两个最大子序列合并得到结果
• 对其中一个子序列的长度i进行遍历，另一个子序列的长度就是k-i，在将两个子序列合并的时候需要考虑一种情况，对于两个子序列[6,3]，[6,8,3]，第一个数是相同的，在合并的时候该选哪个呢，可以dfs得到若干个答案，例如[6,8,6,3,3]，[6,6,8,3,3]，这种方法是超时的，那如何比较呢？这里有一个好方法，比较后一位的数字，66，63<68，如果第二位也相同，就继续比较，例如6868，68<683，所以选第二个子序列的6，然后继续比6<8。
• 比较后一位这种方法比递归遍历所有情况要好得多，非常优雅。

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    n1,n2 := len(nums1),len(nums2)
    res := make([]int,k)
    for i:=max(0,k-n2);i<=min(k,n1);i++{
        // 从两个数组得到指定长度的最大子序列
        arr1 := getSequence(nums1,i)
        arr2 := getSequence(nums2,k-i)
        // 将两个子序列合并
        temp := conbined(arr1,arr2)
        // 维护一个最大的结果
        for i,x := range res{
            if x<temp[i]{
                copy(res,temp)
                break
            }else if x>temp[i]{
                break
            }
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

68、多指针计算丑数

• 根据示例，[2,7,13,19]每个数字若干个组合相乘，得到所有丑数，第一个数是1，primes依次相乘最小值是2，接下来primes中2和第二个数相乘，其他依旧与1相乘，最小值是4，第四个数是7，那么接下来2和4相乘，7和第二个数2相乘，发现规律，创建len(primes)个指针，多指针指向丑数对应相乘的位置，每次计算primes与对应数相乘的最小值，保存到丑数数组中，多指针独立移动，直到算出结果

func nthSuperUglyNumber(n int, primes []int) int {
    m := len(primes)
    // 保存所有丑数
    dp := make([]int,n+1)
    dp[1] = 1
    // 多指针
    pointers := make([]int,m)
    for i := range pointers{
        // 最初所有指针都指向1
        pointers[i] = 1
    }
    for i:=2;i<=n;i++{
        // 求primes与对应指针指向dp乘积的最小值
        mn := math.MaxInt
        for j,k := range pointers{
            mn = min(mn,primes[j]*dp[k])
        }
        // 可能不止一组值可以计算出最小值，例如7*2和2*7，对于所有能计算出mn的pointers都需要加一
        for j,k := range pointers{
            if mn==primes[j]*dp[k]{
                pointers[j]++
            }
        }
        dp[i] = mn
    }
    return dp[n]
}
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

69、查找一个数组的中位数

• 对一个数组，例如[1,3,2,2,2,1,1,3,1,1,2]，如何快速找到其中位数，即第n/2大的数字，并对数组按中位数排序，排成[x]的形式，即[1,1,1,1,1,2,2,2,2,3,3]？

• 分治算法，找任意一个值当中位数x，对数组特定区域排序，如果排序之后，x的下标不在n/2，就移动目标区间，直到找到一个数x，其下标包括了n/2

• 扩展：如果找的不是中位数，而是第k大的数字，那就把比较的下标换成k

func sortByMedian(arr *[]int){
    nums := *arr
    n := len(nums)
    // 分治查找中位数
    var dfs func(int,int)
    dfs = func(l,r int){
        x := nums[(l+r)/2]
        // 将nums[l:r]排序成[x]的形式
        i,j := l,l
        for k:=l;k<=r;k++{
            if nums[k]<x{
                nums[i],nums[k] = nums[k],nums[i]
                if j>i{
                    nums[j],nums[k] = nums[k],nums[j]
                }
                i++
                j++
            }else if nums[k]==x{
                nums[j],nums[k] = nums[k],nums[j]
                j++
            }
        }
        if i>n/2{
            dfs(l,i)
        }else if j-1<n/2{
            dfs(j,r)
        }
    }
    dfs(0,n-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

70、找规律，0~n中二进制1的个数

• 如何找规律，nums[i]与之前数字的关系，或者找是否能直接算出nums[i]
• 第一个规律，去掉i最低位的1，然后再加上1
• 第二个规律，i右移一位，然后加上i最低位的数字

var nums = []int{}
func countBits(n int) []int {
    nums = make([]int,n+1)
    for i:=1;i<n+1;i++{
        // 规律一，去掉i最右边的1
        nums[i] = nums[i&(i-1)]+1
        // 规律二，右移一位
        nums[i] = nums[i>>1]+(i&1)
    }
    return nums
}
1
2
3
4
5
6
7
8
9
10
11

71、byte，rune，int的本质

byte是1字节，8位，本质是uint8

rune，占4个字节，共32位，所以它和 uint32 本质上也没有区别

go语言中的int的大小是和操作系统位数相关的，如果是32位操作系统，int类型的大小就是4字节；如果是64位操作系统，int类型的大小就是8个字节

一般int是8字节，与int64相同

注意byte本质是uint，所以可以用位运算，例如交换字符串中两个位置的字符

s[i] ^= s[j]
s[j] ^= s[i]
s[i] ^= s[j]
1
2
3

72、每位数字都不同的数字的个数，排列组合

• 题目要求数字每一位都不同，思路有两个，直接找出所有满足要求的数字个数，总数字个数-不满足要求的数字个数

• 注意到n比n-1多了一位，n的结果等于n-1的结果+n位满足要求的数字的个数，例如n=1的结果是10，n=2的结果是10+81，这个81是怎么算出来的呢

• 对于n位数字，第一位从1-9九个数字中选一个，第二位可以从0-9十个数字中选一个和第一位不同的数字，即9种选择，第三位可以选8个，第四位7个…，所以dp[n]=dp[n-1]+9*9*8*7*...=dp[n-1]+9*A(9,n-1)

• 

• Cnk = n!/k!(n-k)!

73、如何用位运算表示+和-，位运算优先级

• 相加减的公式是a^b + (a&b)<<1，相当于将a+b拆分成无进位加法结果与进位结果的和，可以用递归的方法表示中间的+号
• 非！，移位<<，按位与&，按位异或^，按位或|

func getSum(a int, b int) int {
    if a==0 || b==0{
        return a^b
    }
    // return a^b + (a&b)<<1
    return getSum(a^b, (a&b)<<1)
}
1
2
3
4
5
6
7

74、多路归并，及其优化方法

• 这道题与多指针计算丑数类似，属于多路归并问题，所以第一个思路是创建nums1个指针，初始化指向nums2的0下标，不断找到最小值，并移动对应的下标指针，但是这个方法超时了
• 如何优化？既然是要找最小值，那么可以用最小堆，入堆元素是(nums1[i]+nums2[j], i, j)
• 最小堆的初始化方法有两种，第一是装入nums1个指针，即(nums1[i]+nums2[0], i, 0)，第二是注意到nums1和nums2都是非递减的，所以最小值肯定是nums1[0]+nums2[0]，每次找完最小值将(i, j+1)和(i+1, 0)入堆

因为用到最小堆，所以用Python写，方法一：

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        n,m = len(nums1),len(nums2)
        ans = []
        # 最小堆，记录下标对
        h = []
        # 初始化将nums1的所有下标对(i,0)入堆
        for i in range(n): heappush(h,(nums1[i]+nums2[0],i,0))
        while h and len(ans)<k:
            # 最小堆根据第一维元素大小排序
            # 堆顶的下标对就是ans下一个结果
            _, i, j = heappop(h)
            ans.append([nums1[i],nums2[j]])
            # 移动对应的下标对，并入堆
            if j+1<m: heappush(h,(nums1[i]+nums2[j+1],i,j+1))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        n,m = len(nums1),len(nums2)
        ans = []
        # 最小堆，记录下标对
        # 初始化只入堆(nums1[i]+nums2[0],i,0)
        h = [(nums1[0]+nums2[0],0,0)]
        while h and len(ans)<k:
            # 最小堆根据第一维元素大小排序
            # 堆顶的下标对就是ans下一个结果
            _, i, j = heappop(h)
            ans.append([nums1[i],nums2[j]])
            # 入堆(i+1, 0)
            # 这里有一个判断j==0，1.避免重复，2.如果j>0，那(i,j)和(i+1,0)大小无法判断
            if j==0 and i+1<n: heappush(h,(nums1[i+1]+nums2[0],i+1,0))
            # 入堆(i, j+1)
            if j+1<m: heappush(h,(nums1[i]+nums2[j+1],i,j+1))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

75、最小代价猜数字，分治与dp

• 从示例来看，最后返回的结果是猜数字代价最坏的情况，如果n=1，那代价为0，因为只有一个数，如果n=2，那代价=min(1,2)=2
• 对于数字范围[i, j]，最大代价cost(i, j) = min(k + max(cost(i, k-1), cost(k+1, j))，k的取值范围是[i, j)，为什么是左闭右开呢？首先icost(i, i) = 0，即cost(n, n) = 0，如果k=j，那就需要求cost(n+1,n)，超出范围。
• 这道题的题目意思比较难理解，但如果抓住单次猜测代价，并分治递归成更小的问题，就可以用动态规划的方法轻松解决，进一步加深了对分治和dp的理解

var dp = [][]int{}
func getMoneyAmount(n int) int {
    if len(dp)==0{
        // 初始化dp
        m := 201
        dp = make([][]int,m)
        for i:=0;i<m;i++{
            dp[i] = make([]int,m)
        }
        // 初始化条件，dp[i][i]==0
        // dp公式，dp[i:j] = min(dp[i:j],k+max(dp[i:k-1],dp[k+1:j]))
        for j:=1;j<m;j++{
            for i:=j-1;i>=1;i--{
                // 初始化一个最大值
                dp[i][j] = m*m
                // 遍历[i,j]的中间值，包括i和j，因为dp[i][i]是已知的初始条件
                for k:=i;k<j;k++{
                    dp[i][j] = min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j]))
                }
            }
        }
    }
    return dp[1][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

76、每个元素可以选择无数次的背包问题

• 这道题和第一题的01背包最大不同在于每个元素可以选择无数次，例如6=1+2+3，那么[1,2,3]和[3,2,1]是两个不同的答案
• 由于每个数值可以被选择无限次，因此需要保证 nums 中的每一位都会被考虑到，即对组合总和 target 的遍历在外，对数组 nums 的遍历在内

func combinationSum4(nums []int, target int) int {
    // 与完全背包不同的是，本题的解有顺序之分
    // 例如6=1+2+3，[1,2,3]和[3,2,1]是两个不同的答案
    f := make([]int,target+1)
    f[0] = 1
    // 由于每个数值可以被选择无限次，因此保证 nums 中的每一位都会被考虑到即可
    // 即对组合总和 target 的遍历在外，对数组 nums 的遍历在内
    for s:=1;s<target+1;s++{
        for _,x := range nums{
            if s-x>=0{
                f[s] += f[s-x]
            }
        }
    }
    return f[target]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

77、二分，多路归并

• 矩阵左上角小，右下角大，那么第一个思路是二分，左右端点分别是矩阵左上角和右下角，每次统计矩阵中小于等于中间值的个数，进行二分
• 由于矩阵是n行排序的，所以可以用多路归并的解法，类似归并排序，使用最小堆维护最小值

解法一，注意1.统计不大于x个数的方法、2.左闭右闭区间二分的写法、3.避免mid==right的取值方法：

func kthSmallest(matrix [][]int, k int) int {
    // 从左下角或右上角出发，如果大于就往上走，如果小于就往右走
    n,m := len(matrix),len(matrix[0])
    // 返回小于等于x的数字的个数
    count := func(x int)int{
        i,j := n-1,0
        res := 0
        for i>=0 && j<m{
            if matrix[i][j]<=x{
                res += i+1
                j++
            }else{
                i-=1
            }
        }
        return res
    }
    l,r := matrix[0][0],matrix[n-1][m-1]
    // [l,r]这种二分的写法
    for l<r{
        // 可能会出现m==r，从而陷入死循环
        // m := (l+r)/2
        // 这种写法可以避免m==r这种情况
        m := l+(r-l)/2
        // fmt.Println(l,m,r)
        if count(m)>=k{
            r = m
        }else{
            l = m+1
        }
    }
    return l
}
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

解法二，最小堆Python：

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n,m = len(matrix),len(matrix[0])
        h = [(matrix[i][0],i,0) for i in range(n)]
        # heapq.heapify(h)简写成heapify
        heapify(h)
        for _ in range(k-1):
            _,i,j = heappop(h)
            if j+1<m:
                heappush(h,(matrix[i][j+1],i,j+1))
        return heappop(h)[0]
1
2
3
4
5
6
7
8
9
10
11

78、蓄水池算法，等概率从数据流挑选数字

• 蓄水池算法：给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。
• 当链表前行到第一个数字，此时取第一个数字的几率为100%，那result自然等于这个数字。
• 前进到第二个数字，那么此时取这个数字的几率自然就为50%（池子里只有两个数字），那么就是50%的几率取新数字，50%的几率保留原本的数字。
• 第三个数字的时候，33%的几率取当前最新的这个数字，66%的几率保留原本的数字。这66%中，原本的数字有50%的几率是1，有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法，就能达到取数的概率均摊，从而实现随机。
• 遍历到第i个数字，有1/i的概率留下这个数字，如果我们需要挑选k个数字，那遍历到第i个数字，有k/i的概率留下这个数字。这就是蓄水池算法，蓄水池的容量就是k

func (this *Solution) GetRandom() int {
    res := -1
    i,k := 1,1
    for cur:=this.Root.Next;cur!=nil;cur=cur.Next{
        // 这里应该写成概率的格式 (rand.Intn(i)+1)/i <= k/i
        // 但是golang中自动舍去小数，所以直接比较分子即可
        if (rand.Intn(i)+1) <= k{
            res = cur.Val
        }
        i++
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13

79、等概率随机排列数组

• 随机对数组进行重排序，遍历数组，遍历的第i个数字，与后面n-i个数字中的某一个数字交换位置，随机交换位置之后第i个位置的数字就确定了，继续往后遍历剩余数字，这就是 Knuth 洗牌算法，在 O(n) 复杂度内等概率返回某个方案
• 代码过程中有一些优化技巧，在结构体中保存原始数组和每次打乱的数组，在打乱数组的基础上重新打乱，此外，传入的参数是指针类型，在创建结构体时需要使用copy来创建，避免old和new指向同一个数组

type Solution struct {
    OldNums []int
    Nums []int
}

func Constructor(nums []int) Solution {
    arr := make([]int,len(nums))
    copy(arr,nums)
    return Solution{arr,nums}
}

func (this *Solution) Reset() []int {
    copy(this.Nums, this.OldNums)
    return this.OldNums
}

func (this *Solution) Shuffle() []int {
    n := len(this.Nums)
    for i:=0;i<n;i++{
        // 将nums中第i个元素和后n-i个元素中某个元素交换
        idx := rand.Intn(n-i)+i
        this.Nums[idx],this.Nums[i] = this.Nums[i],this.Nums[idx]
    }
    return this.Nums
}
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

80、数字字典序规律

• 对于一个整数 number，它的下一个字典序整数对应下面的规则：

• 尝试在 number 后面附加一个零，即 number×10，如果 number×10≤n，那么说明 number×10 是下一个字典序整数；

• 如果 number mod 10=9 或 number+1>n，那么说明末尾的数位已经搜索完成，退回上一位，即 number=[number/10]，然后继续判断直到 number mod 10≠9 且 number+1≤n 为止，那么 number+1 是下一个字典序整数。

• 字典序最小的整数为 number=1，我们从它开始，然后依次获取下一个字典序整数，加入结果中。

func lexicalOrder(n int) []int {
    nums := make([]int,n)
    num := 1
    for i := range nums{
        nums[i] = num
        if num*10<=n{
            num *= 10
        }else{
            for num%10==9 || num+1>n{
                num /= 10
            }
            num++
        }
    }
    return nums
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

81、隔一个删除一个元素求最后剩余元素

• res是第一个元素，step是第一个元素移动的步长
• 如果是从左到右一个一个删除，那步长就是固定的1
• 如果是从左到右隔一个删除一个，那步长每次变化2倍，例如1->2->4->8，步长1->2->4
• 这样好理解，因为隔一个删除一个导致中间是镂空的
• 如果一次从左往右，一次从右往左，那res只有在从左往后，和从右往左但能删除第一个元素时移动，即n%2==1

func lastRemaining(n int) int {
    // 结果，从第一个元素1开始
    res := 1
    // true为从左往右，false为从右往左
    flag := true
    // res移动的步长
    step := 1
    for n>1{
        if flag || n%2==1{
            res += step
        }
        flag = !flag
        step *= 2
        n /= 2
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

82、灵活运用滑动窗口

• 一眼滑动窗口，但是这道题不能直接遍历右端点移动左端点，因为这道题求的是最长子串，如果移动左端点则缺少移动条件
• 发现一个符合要求的滑动窗口内如果有 t 种元素，那窗长必然大于等于t*k，所以可以对元素种类 t 进行遍历，每次遍历进行滑动窗口，移动左端点的条件就是窗口内元素种类大于 t

func longestSubstring(s string, k int) (res int) {
    // 滑动窗口，由于求最长子串，所以不能直接遍历r移动l
    // 对于滑动窗口 s[l:r] ，它的长度一定大于等于k*t，t是出现字符的种类
    // 所以对t进行遍历，维护l和r以及实际出现的字符种类tReal，并保存最大长度
    for t:=1;t<=26;t++{
        nums := make([]int,26)
        l,tReal := 0,0
        for r,c := range s{
            if nums[int(c)-97]==0{
                tReal++
            }
            nums[int(c)-97]++
            for l<r && tReal>t && (r-l+1)>k*t{
                nums[int(s[l])-97]--
                if nums[int(s[l])-97]==0{
                    tReal--
                }
                l++
            }
            if (r-l+1)>=k*t && tReal==t && isOk(nums,k){
                // 长度对了，种类对了，每个字母出现次数也对了
                res = max(res,r-l+1)
            }
        }
    }
    return res
}
func isOk(nums []int, k int)bool{
    for _,x := range nums{
        if x>0 && x<k{return false}
    }
    return true
}
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

83、二分，数位dp

• 这道题如果要暴力，就是从1开始遍历，直到累加的1的个数大于k，但是当遍历数字很大的时候有相当长的空窗期没有增加的1的个数
• 这道题可以用二分来做，随着遍历数字的增长，1的个数增大，对1~num进行二分，计算小于num的1的个数，如果快速计算呢？数位dp，对数字num的二进制每一位进行数位dp，递归累加所有可能的结果
• idx := sort.Search(n, func(num int)bool{return true})这个函数计算0~n中满足条件的最小的数字，由于题目求小于等于k的最大数字，所以在判断的函数中判断条件是大于k，结果-1即可

func findMaximumNumber(k int64, x int) int64 {
    // 本题可以二分，因为随着数字的增大，结果是非递减的
    // 计算1~mid中第a*x位上1的个数，与k进行二分比较
    // 如何计算1的个数？数位dp，在二进制的数位上进行dp
    // l,r := 1,math.MaxInt>>4
    // for l
    //     m := (l+r)/2
    //     if countDigitOne(m)>k{
    //         r = m
    //     }else{
    //         l = m
    //     }
    // }
    // return int64(l)
    // 计算1~n在二进制位上1的个数
    countDigitOne := func(m int) int64 {
        n := bits.Len(uint(m))
        //数位dp，递归生成所有的数字，递归到终点时返回1的个数
        dp := make([][]int,n)
        for i := range dp{
            dp[i] = make([]int,n)
            for j := range dp[i]{
                dp[i][j] = -1
            }
        }
        //下标，前面填了几个1，是否顶格选值
        var dfs func(int,int,bool)int
        dfs = func(idx,cnt int, isLimit bool)(res int){
            if idx>=n{
                // 递归完毕，返回计算得到的1的个数
                return cnt
            }
            if !isLimit{
                // 顶格选的值只有一个，所以只记录非顶格选的情况
                if dp[idx][cnt]!=-1{
                    return dp[idx][cnt]
                }else{
                    defer func(){dp[idx][cnt] = res}()
                }
            }
            up := 1
            if isLimit{
                up = m>>(n-1-idx)&1
            }
            // 枚举要填入的数字
            for i:=0;i<=up;i++{
                if i==1 && (n-idx)%x==0{
                    res += dfs(idx+1, cnt+1, isLimit&&i==up)
                }else{
                    res += dfs(idx+1, cnt, isLimit&&i==up)
                }
            }
            return res
        }
        return int64(dfs(0,0,true))
    }
    ans := sort.Search(math.MaxInt>>4, func(num int)bool{return countDigitOne(num)>k})-1
    return int64(ans)
}
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

84、思维题

• 这道题通过示例1可以发现，最小值可以和其他比他大的数取余，从而消除大数，最后得到原本个数的最小数，结果就是cnt/2向上取整
• 但是看到示例3可以发现，通过取余也可以得到比最小值更小的数字，如果示例3改成[2,2,3,4]，那最后结果依然是1，因为可以通过4%3得到1，用这一个1把所有数字都消掉，所以遍历数组，如果有数字取余最小值可以得到更小的数，就返回1

func minimumArrayLength(nums []int) int {
    sort.Ints(nums)
    minn := nums[0]
    cnt := 0
    for _,x := range nums{
        if x==minn{
            cnt++
        }else if x%minn!=0{
            return 1
        }
    }
    return (cnt+1)/2
}
1
2
3
4
5
6
7
8
9
10
11
12
13

85、一定条件下的数组排序

• 数组排序，但是增加一个条件，即当前数字前面有且只有第二个参数个大于等于它的数字
• 先排序，身高从高往低站，如果身高一样，那前面没有更高的站前面。
• 在遍历的时候就可以保证已经遍历过的数字都是大于等于当前数字的，那当前数字的站位就是第二个参数，即people[i][1]就是排序的下标。
• 可以再创建一个数组来保存答案，或者直接在people原地修改答案。

func reconstructQueue(people [][]int) [][]int {
    sort.SliceStable(people,func(i,j int)bool{
        return people[i][0]>people[j][0] || (people[i][0]==people[j][0] && people[i][1]<people[j][1])
    })
    for i,arr := range people{
        // [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
        copy(people[arr[1]+1: i+1], people[arr[1]: i+1])// p[1]的元素后移一位
        people[arr[1]] = arr
    }
    return people
}
1
2
3
4
5
6
7
8
9
10
11

86、数位题，填位法

/*
填位法：
对于示例[5,2,3,6]，二进制[101,010,011,110]，k=2
从最高位开始，有两个1，消除这两个1需要2次与操作
第二位，有三个1，需要进行几次与操作使得前两位都是1呢？需要3次与操作，大于k=2，所以第二位是1
第三位，有两个1，由于第二位一定是1了，所以后续无需考虑第二位，需要进行几次与操作使得1、3位都是1呢？，需要2次与操作
所以答案是010，即2
*/
func minOrAfterOperations(nums []int, k int) int {
    res := 0
    // 通过掩码来控制是否考虑某些位
    mask := 0
    // 数组最大值的位数
    b := bits.Len(uint(slices.Max(nums)))
    for i:=b-1;i>=0;i--{
        // 考虑第i位，以及前面不是1的位
        mask = mask|(1<<i)
        // 操作次数
        cnt := 0
        // 每次与操作的结果，-1的二进制全是1
        and := -1
        // 遍历数字，将选定数位进行与操作，如果当前与操作结果不为0，就说明消耗了1次操作次数
        // 举个例子，1,1,1,0，前三位相与为1，消耗三次操作，第四次操作结果为0，那这一段消除的操作次数是3
        // 如果打乱顺序，1,1,0,1，前三次操作次数为2，第四个数操作次数为1，在结果为0时重置操作结果
        // 如果不止一位，10,01,11,01，前两次结果为0，操作次数为1，后两次结果不为0，操作次数为2
        for _,x := range nums{
            and = and&(x&mask)
            if and!=0{
                // 操作结果不为0，操作次数+1
                cnt++
            }else{
                // 重置操作结果
                and = -1
            }
        }
        // 如果这一位根本不能消除成0，那消除次数是n，题目条件k
        if cnt>k{
            // 操作次数大于k，那这一位的结果只能是1，之后无需考虑
            mask ^= 1<<i
            res |= 1<<i
        }
    }
    return res
}
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

87、滑动窗口进阶问题

• 滑动窗口有两种：
• 一种是，right每次往右走，只要不满足条件，left就一直收敛。
• 一种是，right每次往右走，如果不满足条件，left最多收敛一次（进阶）。
• 前者用res维护最长子字符串，后者用r-l+1维护最长子字符串，如果当前情况没有贡献，子字符串长度就不变

/*
滑动窗口有两种： 
一种是，right每次往右走，只要不满足条件，left就一直收敛。 
一种是，right每次往右走，如果不满足条件，left最多收敛一次（进阶）。
前者用res维护最长子字符串，后者用r-l+1维护最长子字符串，如果当前情况没有贡献，子字符串长度就不变
*/
func characterReplacement(s string, k int) int {
    cnt := [26]int{}
    l,maxn := 0,0
    for r,c := range s{
        cnt[int(c)-65]++
        // maxn表示的是所有情况下区间最好的元素个数，类似传统解法的res
        // 如果本次情况区间中最大元素个数小于maxn，那计算的子字符串长度必不可能是最长的
        maxn = max(maxn,cnt[int(c)-65])
        // 这里只挪动一次，表示本次右指针移动没有对结果产生贡献
        if r-l+1-maxn>k{
            cnt[int(s[l])-65]--
            l++
        }
    }
    return len(s)-l
    // 传统的滑动窗口解法，遍历r，移动l直到满足条件，维护最长子字符串
    // l,res := 0,0
    // for r,c := range s{
    //     cnt[int(c)-65]++
    //     maxn := -1
    //     for _,x := range cnt{
    //         maxn = max(maxn,x)
    //     }
    //     for lk{
    //         cnt[int(s[l])-65]--
    //         l++
    //         for _,x := range cnt{
    //             maxn = max(maxn,x)
    //         }
    //     }
    //     res = max(res,r-l+1)
    // }
    // return res
}
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

88、Go中快速二分函数

从[0,n]中找到最小的符合条件的数字

func arrangeCoins(n int) int {
    // l,r := 1,n
    // for l
    //     m := (l+r)/2
    //     if cal(m)>n{
    //         r = m
    //     }else{
    //         l = m
    //     }
    // }
    // return l
    return sort.Search(n, func(m int)bool{m++; return cal(m)>n})
}
1
2
3
4
5
6
7
8
9
10
11
12
13

89、归并排序计算逆序对

• 归并排序有两个过程，先递归，后合并，在合并的时候可以同步计算逆序对，示意图如下所示
• 

func reversePairs(record []int) int {
    // 在归并排序的合并阶段统计「逆序对」数量
    // 完成归并排序时，也随之完成所有逆序对的统计
    n := len(record)
    var dfs func(int,int)int
    dfs = func(l,r int)int{
        if l>=r-1{
            return 0
        }
        m := (l+r)/2
        cnt := dfs(l,m)+dfs(m,r)
        // 从temp中选值填入record
        n1,n2 := m-l,r-l
        temp := make([]int,n2)
        copy(temp,record[l:r])
        i,j,idx := 0,m-l,l
        for i<n1 && j<n2{
            if temp[i]<=temp[j]{
                record[idx] = temp[i]
                idx++
                i++
            }else{
                record[idx] = temp[j]
                idx++
                j++
                // 左大右小，将逆序对添加到结果中
                cnt += n1-i
            }
        }
        // 剩下一堆大的直接覆盖到record中即可，逆序对已经在遍历时更新过了
        if i<n1{
            copy(record[idx:r],temp[i:n1])
        }
        if j<n2{
            copy(record[idx:r],temp[j:n2])
        }
        // fmt.Println(cnt,record)
        return cnt
    }
    return dfs(0,n)
}
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

90、寻找132，遍历1单调栈记录3出栈为2

• 遍历i，从后往前遍历，如果当前遍历元素大于k就不能成为i，如果当前遍历元素大于j就有潜力成为j，用一个单调递减栈维护j，遍历的元素入栈，将栈中小的元素值出栈，并赋给k，这样就能保证j>k，且k是j之下的最大值，给i的选择留足了空间
• 从右往左遍历元素，先后判断当前元素能否成为i,j,k，保证了三个元素的相对顺序
• j的可能取值是由一个单调递减栈维护的，不需要知道j的确切数值，只需要确保如果遍历过程出现了一个大值，会先进入j的单调栈中，直到另一个比这个值还大的数出现，才会出栈释放给k，最后单调栈中应该有一个生效的大值成为j，前面有一些略过的值，后面有一些没用到的值
• 例如[1,3,2,4,5,6,7,8,9,10]，单调递减栈是[10 9 8 7 6 5 4 3]，2出栈成为了k，只有最后一个3成为了j，而i是1

func find132pattern(nums []int) bool {
    // 遍历i，单调递减栈记录最大值j
    // 当前元素如果要入栈成为j，栈内更小的元素出栈成为k
    // 出栈的所有元素中将最大值赋给k，以便i有更多选择空间
    n := len(nums)
    if n<=2{
        return false
    }
    stack := []int{nums[n-1]}
    k := int(-1e9)
    for i:=n-2;i>=0;i--{
        x := nums[i]
        if x<k{
            // 按照上示解法，默认k
            return true
        }
        for len(stack)>0 && x>stack[len(stack)-1]{
            // 从单调栈中舍去的j赋给k，这样就保证了k
            // 如果i==j不能舍去，否则会导致j==k
            k = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        if x>k{
            // 如果i>k，则i有潜力成为j
            stack = append(stack,x)
        }
    }
    return false
}
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

91、小猪验毒药，动态规划

• 题目的意思是，根据示例一，测试时间60，死亡时间15，一共可以测试60/15=4轮，4轮内用多少只小猪可以从1000桶水中找到无毒的？答案是5只。

• 如上图所示，将1000桶水中的500桶平分成5*5份，如果没有猪死掉，那毒药在另外500桶里，重复上述操作。如果死1只猪，那第二轮4只猪喝20桶水。如果死两只猪，假如猪3和猪4死了，那他俩喝的那20份水有问题，第二轮3只猪喝20份水，分成2*(3*3+1)，要么3只猪喝2桶水，要么2只猪喝2桶水，要么1只猪喝2桶水，第三轮只需喝一桶水，死了这桶是毒药，没死另外一桶是毒药。

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    // 如果只有1个桶，按照题目条件必有一桶毒药，那直接秒了
    if buckets==1{
        return 0
    }
    // 最多n轮得出结果
    n := minutesToTest/minutesToDie
    // dp(i,j) 表示 i 只小猪测试 j 轮最多可以在多少桶液体中确定有毒的是哪一桶
    // 在确定最大测试轮数为 n 的情况下，需要计算使得 dp(i,n)≥buckets 成立的最小的 i
    // buckets个桶最坏情况需要buckets只猪进行buckets轮测试
    dp := make([][]int,buckets+1)
    for i := range dp{
        dp[i] = make([]int,buckets+1)
        // 初始条件，0只猪或者0轮测试只可以判断1桶
        dp[i][0] = 1
    }
    for j := range dp[0]{
        dp[0][j] = 1
    }
    // 对于dp(i,j)，测试1轮存活k只猪，k=0~i，i只存活k只，毒液的位置一共有C(i,k)种可能，则有
    // dp(i,j) = sum(dp(k,j-1)*C(i,k))
    for i:=1;i<=buckets;i++{
        for j:=1;j<=n;j++{
            for k:=0;k<=i;k++{
                dp[i][j] += dp[k][j-1]*C(i,k)
            }
            if dp[i][j]>=buckets{
                return i
            }
        }
    }
    return -1
}
// 从n中选x，概率论
func C(n,x int)int{
    // n*...*(n-(x-1))/x!
    res := 1
    for i:=0;i<x;i++{
        res = res*(n-i)/(i+1)
    }
    return res
}
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

• 还有一种以香农信息论解题的思路，但是对于buckets=125，n=4得到的结果是4，但是答案是3，作为一种额外的思路参考在下面

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    n := minutesToTest/minutesToDie
    // 一只小猪能有多少种状态？第一轮就死、第二轮死、...、第n轮死，以及生还，所以一共有n + 1种状态
    // n + 1种状态所携带的信息为log_2(n + 1)比特，这也是一只小猪最多提供的信息量
    // k只小猪一共可以提供 k*log_2(n + 1) 比特信息量
    // buckets瓶液体中哪一瓶是毒这件事，也有buckets种可能性，所以需要的信息量是log_2(buckets)
    for k:=0.0;;k++{
        if k*log2(n+1)>=log2(buckets){
            return int(k)
        }
    }
}
func log2(x int)float64{
    // Log()以自然常数e为底，用换底公式
    return math.Log(float64(x))/math.Log(2)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

92、快速判断字符串是否由重复子串构成

• 第一眼想法是模拟，遍历子串长度1~n/2，一个个对比
• 但还有更快解法，假设s由某个子串至少重复2次构成，则s+s中至少包含1个s

func repeatedSubstringPattern(s string) bool {
    // 假设s由某个子串至少重复2次构成，则s+s中至少包含1个s
    str := s+s
    return strings.Contains(str[1:len(str)-1],s)
}
1
2
3
4
5

93、快速计算汉明距离

func hammingDistance(x int, y int) int {
    z := x^y
    // 方法一，直接使用bits包
    return bits.OnesCount(uint(z))
    // 方法二，不断将最低位的1加入答案
    res := 0
    for z>0{
        res += z&1
        z>>=1
    }
    return res
    // 方法三，方法二中需要一位一位的右移，能不能一次统计多个位上的1
    // 分治的思想，分别统计两位二进制数中的低位数字中1的数量和高位数字中1的数量
    // 例如13=0x1101，13&0x5 = 1101&0101 = 0101，13>>1&0x5 = 110&0101 = 0100
    // 二者相加，0101+0100=1001，即高两位有10，即2个1，低两位有01，即1个1
    // 这是一次统计两位的，然后一次统计四位的、八位的、16位的、32位的，最后得到结果
    // 5=0000_0101，3=0000_0011，0f=0000_1111，ff=1111_1111
    z = (z & 0x55555555) + ((z >> 1) & 0x55555555)
	z = (z & 0x33333333) + ((z >> 2) & 0x33333333)
	z = (z & 0x0f0f0f0f) + ((z >> 4) & 0x0f0f0f0f)
	z = (z & 0x00ff00ff) + ((z >> 8) & 0x00ff00ff)
	z = (z & 0x0000ffff) + ((z >> 16) & 0x0000ffff)
    return z
    // 方法四，Brian Kernighan算法，x&(x-1)==x去掉最低位的1，这样只遍历1不遍历0
    res := 0
    for z:=x^y;z>0;z&=z-1{
        res++
    }
    return res
}
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

94、数组元素相等所需最小代价

• 结论题，代价最小所锚定的值是数组的中位数
• 证明：
  • 首先，x一定在[min,max]这个区间内，排序之后就是在[1:n]之中
  • 其次，x在[1:n]中任意一点对于这两点的代价是恒等的，在[2:n-1]、在[3:n-2]…
  • 取到最后一个最小的区间就是[n/2,n/2+1]，或者[n/2,n/2]
  • x取最小的区间对于nums中所有两两成对数的代价是恒定且最小的

func minMoves2(nums []int) int {
    // 结论，x取数组排序后的中间值，所需代价最小
    // 首先，x一定在[min,max]这个区间内，排序之后就是在[1:n]之中
    // 其次，x在[1:n]中任意一点对于这两点的代价是恒等的，在[2:n-1]、在[3:n-2]...
    // 取到最后一个最小的区间就是[n/2,n/2+1]，或者[n/2,n/2]
    // x取最小的区间对于nums中所有两两成对数的代价是恒定且最小的
    sort.Ints(nums)
    mid := nums[len(nums)/2]
    res := 0
    for _,x := range nums{
        res += abs(x-mid)
    }
    return res
}
func abs(x int)int{if x<0{return -x}else{return x}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

95、用rand7模拟rand10

• rand7是1_{7这7个数的等概分布，如何模拟1}10的等概分布

func rand10() (res int) {
    // rand7是1~7等概分布，要求1~10等概分布
    // 构造1~49等概分布，只取前10，此时1~10是等概分布
    // 如何构造1~49，如果直接rand7*rand7，那是49个有重复的数字，例如1*4==2*2
    // 把一个1~7当成基准量，那我们只需构建出每7步的偏移0/7/14/21/28/35/42
    for {
        // 1~49等概分布
        res = (rand7()-1)*7+rand7()
        if res<=10{
            // 1~10等概率分布
            return res
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

96、二维背包问题

• 二维背包问题还是第一次见，思路和一维的01背包问题相似

func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int,m+1)
    for i := range dp{
        dp[i] = make([]int,n+1)
    }
    for _,s := range strs{
        c0,c1 := 0,0
        for _,c := range s{
            if c-'0'==0{
                c0++
            }else{
                c1++
            }
        }
        // 二维背包问题
        for i:=m;i>=c0;i--{
            for j:=n;j>=c1;j--{
                dp[i][j] = max(dp[i][j],dp[i-c0][j-c1]+1)
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

97、在特定形状中生成均匀随机点

• 在一个圆内生成均匀的随机点，一个思路是拒绝采样，在一个矩形内均匀生成点，如果点在圆内就采用，否则拒绝采样并重新生成随机点。
• 另一个思路是根据圆的分布函数来计算，x=rcosθ, y=rsinθ。注意如果直接在 [0,1) 范围内生成 r 以及 [0,2π) 范围内生成 θ，得到的随机点是不均匀的，设想半径围绕圆心均匀转动，离圆心越近，点越密集，而float64是有精度的，所以离圆心越近点越密集，被随机到的可能越高。
• 正确做法是，在单位圆中随机生成一个点，将半径开方得到 r，求得rcos和rsin之后等比放大、平移即可

func RandPoint(radius, xCenter, yCenter float64) []float64 {
    // 单位圆
    r := math.Sqrt(rand.Float64())
    sin, cos := math.Sincos(rand.Float64() * 2 * math.Pi)
    return []float64{xCenter + r*cos*radius, yCenter + r*sin*radius}
}
1
2
3
4
5
6

98、维护数据流的中位数

• 维护两个数组，一个数组保存小于等于中位数的值，一个数组保存大于中位数的值，那中位数就等于数组1的最大值，或者数组1最大值和数组2最小值的平均，所以一个数组用最大堆，一个用最小堆
• 当添加元素时，和数组1的最大值进行比较，大于就添加到数组2，小于就添加到数组1，为了查找中位数，这两个数组的长度要么相等，要么数组1比数组2大1，所以在添加元素后维护一下数组长度，数组1长了就把最大值移到数组2，反之亦然。
• 注意：Python的最小堆只维护堆顶元素，试图返回nums[n/2]是行不通的
• 注意：Python中类的写法，类中属性变量的定义方式，self.x

class MedianFinder:
    # 维护一个最大堆min记录比中位数小的值，和一个最小堆max记录比中位数大的值
    # 中位数是max(min)，或者(max(min)+min(max))/2
    # 所以min长度等于max，或者比max大1
    # 注意：python的最大堆只维护堆顶元素，直接返回nums[n/2]是行不通的

    def __init__(self):
        self.minArr = list()
        self.maxArr = list()

    def addNum(self, num: int) -> None:
        minArr_,maxArr_ = self.minArr,self.maxArr
        if not minArr_ or num<=-minArr_[0]:
            # 初始化，或者小于等于minArr中最大值就加到minArr中
            # 最大堆
            heappush(minArr_,-num)
            # 两个堆的长度最多相差1，这样求出来的才是中位数
            if len(maxArr_)<len(minArr_)-1:
                heappush(maxArr_,-heappop(minArr_))
        else:
            # 最小堆
            heappush(maxArr_,num)
            # 根据约定好的，minArr长度要么等于、要么比max大1，不可能大于
            if len(maxArr_)>len(minArr_):
                heappush(minArr_,-heappop(maxArr_))

    def findMedian(self) -> float:
        minArr_,maxArr_ = self.minArr,self.maxArr
        if len(minArr_)==len(maxArr_):
            return (-minArr_[0] + maxArr_[0])/2
        else:
            return -minArr_[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

99、维护滑动窗口的中位数

• 这道题与上一题类似，都是要用到两个堆，中位数等于两个堆顶元素的平均，或者小于堆的堆顶元素
• 但是这道题是滑动窗口，限制了数据量，有一个删除元素的操作，但是最小堆只维护堆顶，如果实时遍历删除元素会超时，所以要延迟删除，记录滑动窗口左侧移除的元素，在某些时刻和两个堆堆顶元素进行比较，并删除
• 如果要延迟删除，那堆中就会有一些无效数据存在，还需要额外两个变量记录两个堆中有效元素个数，每次添加和删除元素都需要维护长度变量，并根据长度变量来移动堆顶元素，max<=min<=max+1。
• 什么时候延迟删除？堆顶元素发生变化时，删除、维护长度。注意添加也可能改变堆顶元素，但如果发生改变，只可能是添加的元素成为堆顶，而新添加的元素不能是延迟删除的。
• 什么时候维护长度？堆的有效长度发生变化时，添加、删除。
• 此外注意Python中类和函数的写法，函数和变量的声明和调用(self)，以及变量生命周期

class DualHeap:
    # 注意初始化方法的函数名，左右各两个_
    def __init__(self, k:int):
        # 维护两个堆，分别记录大于和小于中位数的值，
        # 中位数就是小于中的最大值，或者其和大于中的最小值的平均
        # 由于堆只维护堆顶元素，所以延迟删除旧值，用Counter维护，只删除堆顶的元素
        # 由于延迟删除，所以要额外记录两个堆中元素个数，用于判断是否移动堆顶到另一个堆
        # 相当于记录有效元素个数，堆中存在无效元素，成为堆顶时会被延迟删除
        self.min,self.max = list(),list()
        # # 记录两个堆中应有的元素个数
        self.minn,self.maxn = 0,0
        # # 延迟删除
        self.delay = Counter()
        self.k = k
    
    def delete(self, hp:List[int]):
        k,min_,max_,delay = self.k,self.min,self.max,self.delay
        while hp:
            num = -hp[0] if hp is self.min else hp[0]
            if delay[num]>0:
                delay[num]-=1
                heappop(hp)
            else:
                break

    # 调整两个堆中元素个数
    def balence(self):
        k,min_,max_,delay = self.k,self.min,self.max,self.delay
        # 加入元素之后，调整两个堆元素个数
        if self.minn>self.maxn+1:
            heappush(max_, -min_[0])
            heappop(min_)
            # print("min -> max")
            self.minn-=1
            self.maxn+=1
            # min_堆顶元素调走后可能需要删除
            self.delete(min_)
        elif self.maxn>self.minn:
            heappush(min_, -max_[0])
            heappop(max_)
            # print("max -> min")
            self.minn+=1
            self.maxn-=1
            # max_堆顶元素调走后可能需要删除
            self.delete(max_)
    
    # 向堆中加入元素
    def add(self, x:int):
        k,min_,max_,delay = self.k,self.min,self.max,self.delay
        if not min_ or x<=-min_[0]:
            heappush(min_, -x)
            self.minn+=1
        else:
            heappush(max_, x)
            self.maxn+=1
        # 堆元素个数发生改变
        self.balence()
      
    # 从堆中删除元素
    def remove(self, x:int):
        k,min_,max_,delay = self.k,self.min,self.max,self.delay
        delay[x]+=1
        if x<=-min_[0]:
            self.minn-=1
            # 从min_中删除
            self.delete(min_)
        else:
            self.maxn-=1
            # 从max_中删除
            self.delete(max_)
        # 堆元素个数发生改变
        self.balence()

    # 获得中位数
    def getMedian(self) -> float:
        k,min_,max_ = self.k,self.min,self.max
        return -min_[0] if k%2==1 else (-min_[0]+max_[0])/2

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        # 对方法进行封装，调用添加，删除，获得中位数这三个方法
        dualHeap = DualHeap(k)
        # 先把前k个加入到min_中
        for x in nums[:k]:
            # 加入新元素
            dualHeap.add(x)
        res = [dualHeap.getMedian()]
        # 加入新元素，删除旧元素，将中间值加入res
        for i,x in enumerate(nums[k:]):
            # 加入新元素
            dualHeap.add(x)
            # 删除旧元素
            dualHeap.remove(nums[i])
            # 获取中位数
            res.append(dualHeap.getMedian())
        return res
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

100、求能让n转化成全1的最小进制

• 求最小的进制数，使得n可以转化成111…111的形式

func smallestGoodBase(n string) string {
    // 假设n可以转化成k进制长为m的111..111，求最小的k

    // 值n的大小固定的情况下，k越小，m越大
    // k最小是2，2^m<=n，n最大10^18，大概是2^10*(18/3)=2^60，m最大60，最小是1
    // 注意：在go中我们可以直接求出n二进制的位数，就不用手动计算60了

    // 从大到小枚举m，对固定的m，k越小，值越小，呈单调性
    // 所以对k进行二分，如果有正好等于n的就return，如果大于n了就continue
    // k最大是n-1，最小是2，即2<=k<=n-1

    // 知道了进制k和长度m如何求十进制的值呢？
    // res=k^m-1+k^m-2+...+k+1，即每轮res*k+1，重复m轮即可
    num,_ := strconv.Atoi(n)
    cal := func(k,m int)int{
        // 进制k长为m的111..111，返回十进制
        res := 0
        // k进制怎么算？res=k^m-1+k^m-2+...+k+1，即每轮res*k+1
        for i:=0;i<m;i++{
            // 判断是否超过num，一方面剪枝，一方面防止溢出
            if res>(num-1)/k{
                // 9223372036854775807
                return math.MaxInt
            }
            res = res*k+1
        }
        return res
    }
    for m:=bits.Len(uint(num));m>=1;m--{
        // k=[2,n-1]
        l,r := 2,num
        for l<r-1{
            k := (l+r)/2
            if cal(k,m)>num{
                r = k
            }else{
                l = k
            }
        }
        if cal(l,m)==num{
            return strconv.Itoa(l)
        }
        // fmt.Println(l,m,cal(l,m),num)
    }
    return strconv.Itoa(num-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

101、祖玛游戏

• 这道题要思考的问题比较多，首先求最少球数，想到用二分来做，但是每次二分，看用m个球是否能消除board是绕远路了，直接广度或者深度+记忆化搜索更直接
• 广度每次保存状态，用vis=100101不如直接把字符串当状态要方便，每次放球和消除相当于重新构建一个字符串，状态由board、hand、已用球数这三个变量构建
• 每次放球放在哪里？直接说结果，放在可消除连续球的一边，或者两个相同球的中间，详见代码
• 每次放完球如何重复消除？用栈维护遍历的连续球，遍历时维护球的种类和个数，如果在一段相同球遍历结束后，前一段个数大于3，就消除，例如1122211，中间的222在第3个1时消除，第3个1遍历时还能把个数加到前面的连续段中，从而实现连续消除

func findMinStep(board string, hand string) int {
    // 每轮，用哪个球？放在哪个位置最优？
    // 红+红红、红红+红、红+红+红，这三种情况没有区别，那设定统一放左边
    // 每轮放球只有三种可能，与右球颜色相同，与两侧球颜色不同、且两侧球颜色相同，与两侧球颜色不同、且两侧球颜色不同
    // 前两种情况都有可能达成最优解，第三种情况并不比前两种更优，下面分别给出两个示例
    // 11223311 - 1123，插2插3，只需两个即可消除
    // 1122113311 - 23，插2插3，112211(3)331(2)1，直接全消除，所需两个
    
    // 如何实现连续消除？
    // 遍历桌上球cur，用一个栈维护遍历球的种类和数量，栈中最后一种球last
    // 每次遍历到cur回头检查last是否颜色不同且超过3个，true则出栈，如果栈空或者cur与last不同，cur入栈且cur++，否则last++
    clean := func(s string)string{
        n := len(s)
        // 分别记录种类和数量
        stack1 := make([]byte, n)
        stack2 := make([]int, n)
        idx := 0
        for i := range s{
            cur := s[i]
            for idx>0 && cur!=stack1[idx-1] && stack2[idx-1]>=3{
                idx--
            }
            if idx==0 || cur!=stack1[idx-1]{
                stack1[idx] = cur
                stack2[idx] = 1
                idx++
            }else if cur==stack1[idx-1]{
                stack2[idx-1]++
            }
        }
        for idx>0 && stack2[idx-1]>=3{
            idx--
        }
        res := ""
        for i:=0;i<idx;i++{
            res += strings.Repeat(string(stack1[i]), stack2[i])
        }
        return res
    }

    // 假设board+hand组成一种状态，不同顺序放球所达到的状态有可能是相同的
    // 穷尽所有情况求最少放球数，用广度优先遍历，或者深度+记忆化搜索，我们用广度

    // 状态用字符串表示，方便插入消除字符
    type states struct{
        board string
        hand string
        step int
    }
    q := []states{states{board,hand,1}}
    // 已访问过的状态
    cnt := map[string]bool{(board+"-"+hand): true}
    for len(q)>0{
        curBoard,curHand,step := q[0].board,q[0].hand,q[0].step
        for i,c1 := range curBoard{
            isUsed := map[byte]bool{}
            for j,c2 := range curHand{
                // 剪枝，对于同一个位置，每种球用几次都是一样的
                if isUsed[byte(c2)]{
                    continue
                }
                isUsed[byte(c2)] = true
                // 两种情况才放球：与右球颜色相同，与两侧球颜色不同、且两侧球颜色相同
                if c1==c2 || (c1!=c2 && i>0 && byte(c1)==curBoard[i-1]){
                    // 将c2插入c1前面
                    newBoard := curBoard[:i]+string(c2)+curBoard[i:]
                    // 重复消除
                    newBoard = clean(newBoard)
                    newHand := curHand[:j]+curHand[j+1:]
                    if len(newBoard)==0{
                        // 全部消除，广度的第一个结果就是最短的
                        return step
                    }
                    if !cnt[newBoard+"-"+newHand]{
                        cnt[newBoard+"-"+newHand] = true
                        q = append(q, states{newBoard,newHand,step+1})
                    }
                }
            }
        }
        fmt.Println(step)
        q = q[1:]
    }
    return -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
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