1201-1300-Easy

1207.独一无二的出现次数(2)

• 题目

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
示例 1：输入：arr = [1,2,2,1,1,3] 输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：输入：arr = [1,2] 输出：false
示例 3：输入：arr = [-3,0,1,-3,1,1,1,-3,10,0] 输出：true
提示：
    1 <= arr.length <= 1000
    -1000 <= arr[i] <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(1)
02	数组辅助	O(n)	O(1)

func uniqueOccurrences(arr []int) bool {
	m := make(map[int]int)
	for _, v := range arr {
		m[v]++
	}
	temp := make(map[int]bool)
	for _, v := range m {
		if temp[v] == true {
			return false
		}
		temp[v] = true
	}
	return true
}

#
func uniqueOccurrences(arr []int) bool {
	tempArr := make([]int,2001)
	for _, v := range arr {
		tempArr[v+1000]++
	}
	temp := make(map[int]bool)
	for _, v := range tempArr {
		if v == 0{
			continue
		}
		if temp[v] == true {
			return false
		}
		temp[v] = true
	}
	return true
}

1217.玩筹码(1)

• 题目

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
    将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
    将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
示例 1：输入：chips = [1,2,3] 输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
示例 2：输入：chips = [2,2,2,3,3] 输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。
提示：
    1 <= chips.length <= 100
    1 <= chips[i] <= 10^9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	奇偶计数	O(n)	O(1)

/*
1、所有偶数移动到同一偶数位置，花费0
2、所有奇数移动到同一奇数位置，花费0
3、将较小移动到较多的位置。
*/
func minCostToMoveChips(chips []int) int {
	odd := 0
	even := 0
	for i := 0; i < len(chips); i++ {
		if chips[i]%2 == 1 {
			odd++
		} else {
			even++
		}
	}
	if odd > even {
		return even
	}
	return odd
}

1221.分割平衡字符串(3)

• 题目

在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。
示例 1：输入：s = "RLRRLLRLRL" 输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 2：输入：s = "RLLLLRRRLR" 输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 3：输入：s = "LLLLRRRR" 输出：1
解释：s 只能保持原样 "LLLLRRRR".
提示：
    1 <= s.length <= 1000
    s[i] = 'L' 或 'R'
    分割得到的每个字符串都必须是平衡字符串。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	栈辅助	O(n)	O(n)
02	遍历	O(n)	O(1)
03	遍历	O(n)	O(1)

func balancedStringSplit(s string) int {
	res := 0
	if len(s) == 0 {
		return res
	}
	stack := make([]byte, 0)
	stack = append(stack, s[0])
	for i := 1; i < len(s); i++ {
		if len(stack) > 0 &&
			((s[i] == 'L' && stack[len(stack)-1] == 'R') ||
				(s[i] == 'R' && stack[len(stack)-1] == 'L')) {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				res++
			}
		} else {
			stack = append(stack, s[i])
		}
	}
	return res
}

#
func balancedStringSplit(s string) int {
	res := 0
	if len(s) == 0 {
		return res
	}
	count := 0
	if s[0] == 'L' {
		count++
	} else {
		count--
	}
	for i := 1; i < len(s); i++ {
		if s[i] == 'L' {
			count++
		} else {
			count--
		}
		if count == 0 {
			res++
		}
	}
	return res
}

#
func balancedStringSplit(s string) int {
	res := 0
	if len(s) == 0 {
		return res
	}
	left := 0
	right := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'L' {
			left++
		} else {
			right++
		}
		if left == right {
			res++
		}
	}
	return res
}

1232.缀点成线(3)

• 题目

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，
其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。
请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
示例 1：输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] 输出：true
示例 2：输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] 输出：false
提示：
    2 <= coordinates.length <= 1000
    coordinates[i].length == 2
    -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
    coordinates 中不含重复的点

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	斜率公式	O(n)	O(1)
02	鞋带公式	O(n)	O(1)
03	判断三边长	O(n)	O(1)

// k=y/x k1=y1/x1 => xy1=x1y
func checkStraightLine(coordinates [][]int) bool {
	x, y := coordinates[1][0]-coordinates[0][0], coordinates[1][1]-coordinates[0][1]
	for i := 2; i < len(coordinates); i++ {
		x1, y1 := coordinates[i][0]-coordinates[i-1][0], coordinates[i][1]-coordinates[i-1][1]
		if x*y1 != x1*y {
			return false
		}
	}
	return true
}

#
// 鞋带公式
// S=|(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1)|/2
// S==0组成一条直线
func checkStraightLine(coordinates [][]int) bool {
	for i := 2; i < len(coordinates); i++ {
		x1 := coordinates[i-2][0]*coordinates[i-1][1] +
			coordinates[i-1][0]*coordinates[i][1] + coordinates[i][0]*coordinates[i-2][1]
		x2 := coordinates[i-2][1]*coordinates[i-1][0] +
			coordinates[i-1][1]*coordinates[i][0] + coordinates[i][1]*coordinates[i-2][0]
		if x1 != x2 {
			return false
		}
	}
	return true
}

#
func checkStraightLine(coordinates [][]int) bool {
	for i := 2; i < len(coordinates); i++ {
		side1 := side(coordinates[i], coordinates[i-1])
		side2 := side(coordinates[i-1], coordinates[i-2])
		side3 := side(coordinates[i], coordinates[i-2])
		arr := []float64{side1, side2, side3}
		sort.Float64s(arr)
		if arr[2]-arr[1]-arr[0] > 0.00000005 || arr[2]-arr[1]-arr[0] < -0.00000005 {
			return false
		}
	}
	return true
}

func side(arr1, arr2 []int) float64 {
	res := (arr1[0]-arr2[0])*(arr1[0]-arr2[0]) +
		(arr1[1]-arr2[1])*(arr1[1]-arr2[1])
	return math.Sqrt(float64(res))
}

1237.找出给定方程的正整数解(3)

• 题目

给出一个函数  f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。
给定函数是严格单调的，也就是说：
    f(x, y) < f(x + 1, y)
    f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};
如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，
其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。  
你可以将满足条件的 结果数对 按任意顺序返回。
示例 1：
输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 表示 f(x, y) = x + y
示例 2：
输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 表示 f(x, y) = x * y
提示：
    1 <= function_id <= 9
    1 <= z <= 100
    题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
    在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(n)
02	双指针	O(n)	O(n)
03	暴力法	O(n^2)	O(n)

func findSolution(customFunction func(int, int) int, z int) [][]int {
	res := make([][]int, 0)
	for i := 1; i <= 1000; i++ {
		left := 1
		right := 1000
		v1, v2 := customFunction(i, left), customFunction(i, right)
		if z < v1 || z > v2 {
			continue
		}
		for left <= right {
			mid := left + (right-left)/2
			v := customFunction(i, mid)
			if z == v {
				res = append(res, []int{i, mid})
				break
			} else if z > v {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return res
}

#
func findSolution(customFunction func(int, int) int, z int) [][]int {
	res := make([][]int, 0)
	i := 1
	j := 1000
	for i <= 1000 && j >= 1 {
		if customFunction(i, j) == z {
			res = append(res, []int{i, j})
			i++
			j--
		} else if customFunction(i, j) > z {
			j--
		} else {
			i++
		}
	}
	return res
}

#
func findSolution(customFunction func(int, int) int, z int) [][]int {
	res := make([][]int, 0)
	for i := 1; i <= 1000; i++ {
		for j := 1; j < 1000; j++ {
			if customFunction(i, j) == z {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

1252.奇数值单元格的数目(3)

• 题目

给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。
另有一个索引数组 indices，indices[i] = [ri, ci] 中的 
ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。
示例 1：输入：n = 2, m = 3, indices = [[0,1],[1,1]] 输出：6
解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
第一次增量操作后得到 [[1,2,1],[0,1,0]]。
最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
示例 2：输入：n = 2, m = 2, indices = [[1,1],[0,0]] 输出：0
解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
提示：
    1 <= n <= 50
    1 <= m <= 50
    1 <= indices.length <= 100
    0 <= indices[i][0] < n
    0 <= indices[i][1] < m

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历模拟	O(n^2)	O(n^2)
02	统计行列	O(n)	O(n)
03	统计行列-遍历	O(n^2)	O(n)

func oddCells(n int, m int, indices [][]int) int {
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
	}
	for i := 0; i < len(indices); i++ {
		r := indices[i][0]
		c := indices[i][1]
		for j := 0; j < m; j++ {
			arr[r][j]++
		}
		for j := 0; j < n; j++ {
			arr[j][c]++
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if arr[i][j]%2 == 1 {
				res++
			}
		}
	}
	return res
}

#
func oddCells(n int, m int, indices [][]int) int {
	rows := make([]int, n)
	cols := make([]int, m)
	for i := 0; i < len(indices); i++ {
		rows[indices[i][0]]++
		cols[indices[i][1]]++
	}
	numRows := 0
	for i := 0; i < n; i++ {
		if rows[i]%2 == 0 {
			numRows++
		}
	}
	res := 0
	for i := 0; i < m; i++ {
		if cols[i]%2 == 0 {
			res = res + n - numRows
		} else {
			res = res + numRows
		}
	}
	return res
}

#
func oddCells(n int, m int, indices [][]int) int {
	rows := make([]int, n)
	cols := make([]int, m)
	for i := 0; i < len(indices); i++ {
		rows[indices[i][0]]++
		cols[indices[i][1]]++
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if (rows[i]+cols[j])%2 == 1 {
				res++
			}
		}
	}
	return res
}

1260.二维网格迁移(2)

• 题目

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
    位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
    位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
    位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。
示例 1：输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 输出：[[9,1,2],[3,4,5],[6,7,8]]
示例 2：输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
示例 3：输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9 输出：[[1,2,3],[4,5,6],[7,8,9]]
提示：
    1 <= grid.length <= 50
    1 <= grid[i].length <= 50
    -1000 <= grid[i][j] <= 1000
    0 <= k <= 100

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历模拟	O(n^2)	O(n^2)
02	计算下标	O(n^2)	O(n^2)

func shiftGrid(grid [][]int, k int) [][]int {
	for i := 0; i < k; i++ {
		temp := make([][]int, len(grid))
		for i := 0; i < len(temp); i++ {
			temp[i] = make([]int, len(grid[i]))
		}
		for i := 0; i < len(grid); i++ {
			for j := 0; j < len(grid[i])-1; j++ {
				temp[i][j+1] = grid[i][j]
			}
		}
		for i := 0; i < len(grid)-1; i++ {
			temp[i+1][0] = grid[i][len(grid[0])-1]
		}
		temp[0][0] = grid[len(grid)-1][len(grid[0])-1]
		grid = temp
	}
	return grid
}

#
func shiftGrid(grid [][]int, k int) [][]int {
	n := len(grid)
	m := len(grid[0])
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			x := ((i*m + j) + k) % (n * m) / m
			y := ((i*m + j) + k) % (n * m) % m
			// x := (i + (j+k)/m) % n
			// y := (j + k) % m
			res[x][y] = grid[i][j]
		}
	}
	return res
}

1266.访问所有点的最小时间(1)

• 题目

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。
请你计算访问所有这些点需要的最小时间（以秒为单位）。
你可以按照下面的规则在平面上移动：
    每一秒沿水平或者竖直方向移动一个单位长度，
    或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
    必须按照数组中出现的顺序来访问这些点。
示例 1：输入：points = [[1,1],[3,4],[-1,0]] 输出：7
解释：一条最佳的访问路径是： 
[1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒
示例 2：输入：points = [[3,2],[-2,2]] 输出：5
提示：
    points.length == n
    1 <= n <= 100
    points[i].length == 2
    -1000 <= points[i][0], points[i][1] <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)

func minTimeToVisitAllPoints(points [][]int) int {
	res := 0
	for i := 1; i < len(points); i++ {
		x := length(points[i][0], points[i-1][0])
		y := length(points[i][1], points[i-1][1])
		if x > y {
			res = res + x
		} else {
			res = res + y
		}
	}
	return res
}

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

1275.找出井字棋的获胜者(2)

• 题目

A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下：
    玩家轮流将棋子放在空方格 (" ") 上。
    第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。
    "X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。
    只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
    如果所有方块都放满棋子（不为空），游戏也会结束。
    游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），
它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。

如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；
如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。
示例 1：输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 输出："A"
解释："A" 获胜，他总是先走。
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"
示例 2：输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] 输出："B"
解释："B" 获胜。
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "
示例 3：输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] 输出："Draw"
输出：由于没有办法再行动，游戏以平局结束。
"XXO"
"OOX"
"XOX"
示例 4：输入：moves = [[0,0],[1,1]] 输出："Pending"
解释：游戏还没有结束。
"X  "
" O "
"   "
提示：
    1 <= moves.length <= 9
    moves[i].length == 2
    0 <= moves[i][j] <= 2
    moves 里没有重复的元素。
    moves 遵循井字棋的规则。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历模拟	O(1)	O(1)
02	遍历模拟	O(1)	O(1)

func tictactoe(moves [][]int) string {
	arrA := make([]int, 0)
	arrB := make([]int, 0)
	for i := 0; i < len(moves); i++ {
		value := moves[i][0]*3 + moves[i][1] + 1
		if i%2 == 0 {
			arrA = append(arrA, value)
			if check(arrA) {
				return "A"
			}
		} else {
			arrB = append(arrB, value)
			if check(arrB) {
				return "B"
			}
		}
	}
	if len(moves) == 9 {
		return "Draw"
	}
	return "Pending"
}

var state = [][]int{
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9},
	{1, 4, 7},
	{2, 5, 8},
	{3, 6, 9},
	{1, 5, 9},
	{3, 5, 7},
}

func check(arr []int) bool {
	if len(arr) < 3 {
		return false
	}
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			for k := j + 1; k < len(arr); k++ {
				temp := []int{arr[i], arr[j], arr[k]}
				sort.Ints(temp)
				for n := 0; n < len(state); n++ {
					if temp[0] == state[n][0] &&
						temp[1] == state[n][1] &&
						temp[2] == state[n][2] {
						return true
					}
				}
			}
		}
	}
	return false
}

#
func tictactoe(moves [][]int) string {
	arr := make([][]int, 4)
	for i := 0; i < len(arr); i++ {
		arr[i] = make([]int, 4)
	}
	for i := 0; i < len(moves); i++ {
		x := moves[i][0] + 1
		y := moves[i][1] + 1
		if i%2 == 0 {
			arr[x][y]++
		} else {
			arr[x][y]--
		}
	}
	sum1 := arr[1][1] + arr[2][2] + arr[3][3]
	sum2 := arr[1][3] + arr[2][2] + arr[3][1]
	if sum1 == 3 || sum2 == 3 {
		return "A"
	} else if sum1 == -3 || sum2 == -3 {
		return "B"
	}
	for i := 1; i <= 3; i++ {
		sum1 := arr[i][1] + arr[i][2] + arr[i][3]
		sum2 := arr[1][i] + arr[2][i] + arr[3][i]
		if sum1 == 3 || sum2 == 3 {
			return "A"
		} else if sum1 == -3 || sum2 == -3 {
			return "B"
		}
	}
	if len(moves) == 9 {
		return "Draw"
	}
	return "Pending"
}

1281.整数的各位积和之差(2)

• 题目

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1：输入：n = 234 输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15
示例 2：输入：n = 4421 输出：21
解释： 
各位数之积 = 4 * 4 * 2 * 1 = 32 
各位数之和 = 4 + 4 + 2 + 1 = 11 
结果 = 32 - 11 = 21
提示：
    1 <= n <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(log(n))	O(1)
02	转字符串遍历	O(log(n))	O(1)

func subtractProductAndSum(n int) int {
	sum := 0
	mul := 1
	for n > 0 {
		value := n % 10
		n = n / 10
		sum = sum + value
		mul = mul * value
	}
	return mul - sum
}

func subtractProductAndSum(n int) int {
	sum := 0
	mul := 1
	str := strconv.Itoa(n)
	for i := 0; i < len(str); i++ {
		value := int(str[i] - '0')
		sum = sum + value
		mul = mul * value
	}
	return mul - sum
}

1287.有序数组中出现次数超过25%的元素(4)

• 题目

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6
提示：
    1 <= arr.length <= 10^4
    0 <= arr[i] <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历统计	O(n)	O(1)
02	遍历	O(n)	O(1)
03	二分查找	O(log(n))	O(1)
04	遍历	O(n)	O(1)

func findSpecialInteger(arr []int) int {
	count := 1
	res := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] == arr[i-1] {
			count++
			if count > len(arr)/4 {
				return arr[i]
			}
		} else {
			res = arr[i]
			count = 1
		}
	}
	return res
}

#
func findSpecialInteger(arr []int) int {
	step := len(arr) / 4
	for i := 0; i < len(arr)-step; i++ {
		if arr[i] == arr[i+step] {
			return arr[i]
		}
	}
	return -1
}

#
func findSpecialInteger(arr []int) int {
	length := len(arr) / 4
	for i := 1; i <= 2; i++ {
		value := arr[length*i]
		left := leftSearch(arr, value)
		right := rightSearch(arr, value)
		if right-left+1 > length {
			return value
		}
	}
	return arr[3*length]
}

func leftSearch(arr []int, value int) int {
	left := 0
	right := len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] >= value {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func rightSearch(arr []int, value int) int {
	left := 0
	right := len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] > value {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return right - 1
}

#
func findSpecialInteger(arr []int) int {
	length := len(arr) / 4
	for i := 1; i <= 2; i++ {
		value := arr[length*i]
		left := length * i
		for left > 0 {
			if arr[left] == arr[left-1] {
				left--
			} else {
				break
			}
		}
		right := length * i
		for right < len(arr)-1 {
			if arr[right] == arr[right+1] {
				right++
			} else {
				break
			}
		}
		if right-left+1 > length {
			return value
		}
	}
	return arr[3*length]
}

1290.二进制链表转整数(3)

• 题目

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。
已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1：输入：head = [1,0,1] 输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：输入：head = [0] 输出：0
示例 3：输入：head = [1] 输出：1
示例 4：输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] 输出：18880
示例 5：输入：head = [0,0] 输出：0
提示：
    链表不为空。
    链表的结点总数不超过 30。
    每个结点的值不是 0 就是 1。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n)	O(n)
02	遍历	O(n)	O(1)
03	递归	O(n)	O(n)

func getDecimalValue(head *ListNode) int {
	arr := make([]int, 0)
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	res := 0
	for i := 0; i < len(arr); i++ {
		res = res * 2
		res = res + arr[i]
	}
	return res
}

#
func getDecimalValue(head *ListNode) int {
	res := 0
	for head != nil {
		res = res*2 + head.Val
		head = head.Next
	}
	return res
}

#
var count = 0

func getDecimalValue(head *ListNode) int {
	if head == nil {
		count = 0
		return 0
	}
	value := getDecimalValue(head.Next)
	res := head.Val*int(math.Pow(2, float64(count))) + value
	count++
	return res
}

1295.统计位数为偶数的数字(2)

• 题目

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
示例 1：输入：nums = [12,345,2,6,7896] 输出：2
解释： 12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字
示例 2：输入：nums = [555,901,482,1771]输出：1 
解释：  只有 1771 是位数为偶数的数字。
提示：
    1 <= nums.length <= 500
    1 <= nums[i] <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	转字符串	O(n)	O(1)

func findNumbers(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		count := 0
		value := nums[i]
		for value > 0 {
			value = value / 10
			count++
		}
		if count%2 == 0 {
			res++
		}
	}
	return res
}

#
func findNumbers(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		value := strconv.Itoa(nums[i])
		if len(value)%2 == 0 {
			res++
		}
	}
	return res
}

1299.将每个元素替换为右侧最大元素(3)

• 题目

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例：输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1]
提示：
    1 <= arr.length <= 10^4
    1 <= arr[i] <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	暴力法	O(n^2)	O(1)
03	遍历-数组辅助	O(n)	O(n)

func replaceElements(arr []int) []int {
	max := -1
	for i := len(arr) - 1; i >= 0; i-- {
		if arr[i] > max {
			arr[i], max = max, arr[i]
		} else {
			arr[i] = max
		}
	}
	return arr
}

#
func replaceElements(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		max := -1
		for j := i + 1; j < len(arr); j++ {
			if arr[j] > max {
				max = arr[j]
			}
		}
		arr[i] = max
	}
	return arr
}

#
func replaceElements(arr []int) []int {
	res := make([]int, len(arr))
	res[len(res)-1] = -1
	for i := len(arr) - 2; i >= 0; i-- {
		if arr[i+1] > res[i+1] {
			res[i] = arr[i+1]
		} else {
			res[i] = res[i+1]
		}
	}
	return res
}

1201-1300-Medium

1201.丑数III(2)

• 题目

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第n个丑数。
丑数是可以被a或b或 c整除的 正整数 。
示例 1：输入：n = 3, a = 2, b = 3, c = 5 输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：输入：n = 4, a = 2, b = 3, c = 4 输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
示例 3：输入：n = 5, a = 2, b = 11, c = 13 输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
示例 4：输入：n = 1000000000, a = 2, b = 217983653, c = 336916467 输出：1999999984
提示：1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在[1,2 * 10^9]的范围内

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(log(n))	O(1)
02	二分查找	O(log(n))	O(1)

func nthUglyNumber(n int, a int, b int, c int) int {
	ab, ac, bc := lcm(a, b), lcm(a, c), lcm(b, c)
	abc := lcm(ab, c)
	left := 1
	right := 2000000000
	for left <= right {
		mid := left + (right-left)/2
		total := mid/a + mid/b + mid/c - mid/ab - mid/ac - mid/bc + mid/abc
		if total == n {
			if mid%a == 0 || mid%b == 0 || mid%c == 0 {
				return mid
			}
			right = mid - 1
		} else if total < n {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

// 求最小公倍数
func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

// 求最大公约数
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	if a%b == 0 {
		return b
	}
	return gcd(a%b, b)
}

# 2
func nthUglyNumber(n int, a int, b int, c int) int {
	ab, ac, bc := lcm(a, b), lcm(a, c), lcm(b, c)
	abc := lcm(ab, c)
	left := 0
	right := 2000000000
	for left < right {
		mid := left + (right-left)/2
		total := mid/a + mid/b + mid/c - mid/ab - mid/ac - mid/bc + mid/abc
		if total >= n {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

// 求最小公倍数
func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

// 求最大公约数
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	if a%b == 0 {
		return b
	}
	return gcd(a%b, b)
}

1202.交换字符串中的元素(1)

• 题目

给你一个字符串s，以及该字符串中的一些「索引对」数组pairs，
其中pairs[i] =[a, b]表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在pairs中任意一对索引处的字符。
返回在经过若干次交换后，s可以变成的按字典序最小的字符串。
示例 1:输入：s = "dcab", pairs = [[0,3],[1,2]] 输出："bacd"
解释： 交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]] 输出："abcd"
解释：交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：输入：s = "cba", pairs = [[0,1],[1,2]] 输出："abc"
解释：交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
提示：1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] <s.length
s中只含有小写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	并查集+排序	O(nlog(n))	O(n)

func smallestStringWithSwaps(s string, pairs [][]int) string {
	n := len(s)
	fa := make([]int, n)
	for i := 0; i < n; i++ {
		fa[i] = i
	}
	for i := 0; i < len(pairs); i++ {
		a, b := pairs[i][0], pairs[i][1]
		union(fa, a, b)
	}
	m := make(map[int][]int)
	for i := 0; i < len(s); i++ {
		target := find(fa, i)
		m[target] = append(m[target], i)
	}
	res := []byte(s)
	for _, v := range m {
		arr := make([]int, 0)
		for i := 0; i < len(v); i++ {
			arr = append(arr, int(s[v[i]]))
		}
		sort.Ints(arr)
		for i := 0; i < len(v); i++ {
			res[v[i]] = byte(arr[i])
		}
	}
	return string(res)
}

func union(fa []int, a, b int) {
	fa[find(fa, a)] = find(fa, b)
}

func find(fa []int, a int) int {
	for fa[a] != a {
		fa[a] = fa[fa[a]]
		a = fa[a]
	}
	return a
}

1208.尽可能使字符串相等(4)

• 题目

给你两个长度相同的字符串，s 和 t。
将 s中的第i个字符变到t中的第 i 个字符需要|s[i] - t[i]|的开销（开销可能为 0），
也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是maxCost。
在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：输入：s = "abcd", t = "bcdf", cost = 3 输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
示例 2：输入：s = "abcd", t = "cdef", cost = 3 输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：输入：s = "abcd", t = "acde", cost = 0 输出：1
解释：你无法作出任何改动，所以最大长度为 1。
提示：1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s 和t都只含小写英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(n)
02	双指针	O(n)	O(1)
03	暴力法	O(n^2)	O(1)
04	前缀和+二分查找	O(nlog(n))	O(n)

func equalSubstring(s string, t string, maxCost int) int {
	arr := make([]int, len(s))
	for i := 0; i < len(s); i++ {
		arr[i] = getValue(s[i], t[i])
	}
	left, right := 0, 0
	total := 0
	res := 0
	for right < len(s) {
		for total+arr[right] > maxCost {
			total = total - arr[left]
			left++
		}
		total = total + arr[right]
		if right-left+1 > res {
			res = right - left + 1
		}
		right++
	}
	return res
}

func getValue(a, b byte) int {
	res := int(a) - int(b)
	if res < 0 {
		return -res
	}
	return res
}

# 2
func equalSubstring(s string, t string, maxCost int) int {
	left := 0
	total := 0
	for right := 0; right < len(s); right++ {
		total = total + getValue(s[right], t[right])
		if total > maxCost {
			total = total - getValue(s[left], t[left])
			left++
		}
	}
	return len(s) - left
}

func getValue(a, b byte) int {
	res := int(a) - int(b)
	if res < 0 {
		return -res
	}
	return res
}

# 3
func equalSubstring(s string, t string, maxCost int) int {
	res := 0
	for i := 0; i < len(s); i++ {
		total := 0
		count := 0
		for j := i; j < len(s); j++ {
			total = total + getValue(s[j], t[j])
			if total > maxCost {
				break
			}
			count++
		}
		if count > res {
			res = count
		}
	}
	return res
}

func getValue(a, b byte) int {
	res := int(a) - int(b)
	if res < 0 {
		return -res
	}
	return res
}

# 4
func equalSubstring(s string, t string, maxCost int) int {
	res := 0
	arr := make([]int, len(s)+1)
	for i := 0; i < len(s); i++ {
		arr[i+1] = arr[i] + getValue(s[i], t[i])
	}
	for i := 1; i <= len(s); i++ {
		index := sort.SearchInts(arr[:i], arr[i]-maxCost)
		if i-index > res {
			res = i - index
		}
	}
	return res
}

func getValue(a, b byte) int {
	res := int(a) - int(b)
	if res < 0 {
		return -res
	}
	return res
}

1209.删除字符串中的所有相邻重复项II(2)

• 题目

给你一个字符串s，「k 倍重复项删除操作」将会从 s中选择k个相邻且相等的字母，
并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对s重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：输入：s = "abcd", k = 2 输出："abcd"
解释：没有要删除的内容。
示例 2：输入：s = "deeedbbcccbdaa", k = 3 输出："aa"
解释： 先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
示例 3：输入：s = "pbbcggttciiippooaais", k = 2 输出："ps"
提示：1 <= s.length <= 10^5
2 <= k <= 10^4
s中只含有小写英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n^2)	O(n)
02	栈	O(n^2)	O(n)

func removeDuplicates(s string, k int) string {
	if len(s) < k {
		return s
	}
	res := ""
	for i := 0; i < len(s); i++ {
		res = res + string(s[i])
		if len(res) >= k && res[len(res)-k:] == strings.Repeat(string(s[i]), k) {
			res = res[:len(res)-k]
		}
	}
	return res
}

# 2
func removeDuplicates(s string, k int) string {
	if len(s) < k {
		return s
	}
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		stack = append(stack, s[i])
		if len(stack) >= k {
			a := string(stack[len(stack)-k:])
			b := strings.Repeat(string(s[i]), k)
			if a == b {
				stack = stack[:len(stack)-k]
			}
		}
	}
	return string(stack)
}

1218.最长定差子序列(2)

• 题目

给你一个整数数组arr和一个整数difference，请你找出并返回 arr中最长等差子序列的长度，
该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1：输入：arr = [1,2,3,4], difference = 1 输出：4
解释：最长的等差子序列是 [1,2,3,4]。
示例2：输入：arr = [1,3,5,7], difference = 1 输出：1
解释：最长的等差子序列是任意单个元素。
示例 3：输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2 输出：4
解释：最长的等差子序列是 [7,5,3,1]。
提示：1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n)	O(n)
02	动态规划	O(n)	O(n)

func longestSubsequence(arr []int, difference int) int {
	res := 0
	dp := make(map[int]int)
	for i := 0; i < len(arr); i++ {
		dp[arr[i]] = dp[arr[i]-difference] + 1
		if dp[arr[i]] > res {
			res = dp[arr[i]]
		}
	}
	return res
}

# 2
func longestSubsequence(arr []int, difference int) int {
	res := 0
	dp := make([]int, 40001)
	for i := 0; i < len(arr); i++ {
		index := arr[i] + 20000
		dp[index] = dp[index-difference] + 1
		if dp[index] > res {
			res = dp[index]
		}
	}
	return res
}

1219.黄金矿工(1)

• 题目

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为m * n 的网格 grid 进行了标注。
每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
为了使收益最大化，矿工需要按以下规则来开采黄金：
每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
示例 1：输入：grid = [[0,6,0],[5,8,7],[0,9,0]] 输出：24
解释：[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
提示：1 <= grid.length,grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯	O(n^4)	O(n^2)

var res int

func getMaximumGold(grid [][]int) int {
	res = 0
	visited := make([][]bool, len(grid))
	for i := 0; i < len(grid); i++ {
		visited[i] = make([]bool, len(grid[i]))
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] > 0 {
				dfs(grid, i, j, 0, visited)
			}
		}
	}
	return res
}

func dfs(grid [][]int, i, j int, sum int, visited [][]bool) {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) ||
		grid[i][j] == 0 || visited[i][j] == true {
		return
	}
	visited[i][j] = true
	sum = sum + grid[i][j]
	if sum > res {
		res = sum
	}
	dfs(grid, i+1, j, sum, visited)
	dfs(grid, i-1, j, sum, visited)
	dfs(grid, i, j+1, sum, visited)
	dfs(grid, i, j-1, sum, visited)
	visited[i][j] = false
}

1222.可以攻击国王的皇后(1)

• 题目

在一个8x8的棋盘上，放置着若干「黑皇后」和一个「白国王」。
「黑皇后」在棋盘上的位置分布用整数坐标数组queens表示，「白国王」的坐标用数组 king 表示。
「黑皇后」的行棋规定是：横、直、斜都可以走，步数不受限制，但是，不能越子行棋。
请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标（任意顺序）。
示例 1：输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释： [0,1] 的皇后可以攻击到国王，因为他们在同一行上。 
[1,0] 的皇后可以攻击到国王，因为他们在同一列上。 
[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。 
[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。 
[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。 
[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。
示例 2：输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出：[[2,2],[3,4],[4,4]]
示例 3：输入：queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],
[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],
[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
提示：1 <= queens.length<= 63
queens[i].length == 2
0 <= queens[i][j] <8
king.length == 2
0 <= king[0], king[1] < 8
一个棋盘格上最多只能放置一枚棋子。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(1)	O(1)

var dir = [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}

func queensAttacktheKing(queens [][]int, king []int) [][]int {
	arr := make([][]int, 8)
	for i := 0; i < 8; i++ {
		arr[i] = make([]int, 8)
	}
	for i := 0; i < len(queens); i++ {
		a, b := queens[i][0], queens[i][1]
		arr[a][b] = 1
	}
	res := make([][]int, 0)
	for i := 0; i < len(dir); i++ {
		x := dir[i][0] + king[0]
		y := dir[i][1] + king[1]
		for 0 <= x && x < 8 && 0 <= y && y < 8 {
			if arr[x][y] == 1 {
				res = append(res, []int{x, y})
				break
			}
			x = x + dir[i][0]
			y = y + dir[i][1]
		}
	}
	return res
}

1223.掷骰子模拟(2)

• 题目

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，
连续 掷出数字i的次数不能超过rollMax[i]（i从 1 开始编号）。
现在，给你一个整数数组rollMax和一个整数n，请你来计算掷n次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。
由于答案可能很大，所以请返回 模10^9 + 7之后的结果。
示例 1：输入：n = 2, rollMax = [1,1,2,2,2,3] 输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。
但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。
因此，最终答案是 36-2 = 34。
示例 2：输入：n = 2, rollMax = [1,1,1,1,1,1] 输出：30
示例 3：输入：n = 3, rollMax = [1,1,1,2,2,3] 输出：181
提示：1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n)	O(n)
02	动态规划	O(n)	O(1)

func dieSimulator(n int, rollMax []int) int {
	dp := make([][7][16]int, n+1) // 第i轮,以j结尾,出现k次
	for j := 1; j <= 6; j++ {
		dp[1][j][1] = 1
	}
	for i := 2; i <= n; i++ {
		for j := 1; j <= 6; j++ {
			for k := 1; k <= rollMax[j-1] && k <= i; k++ {
				if k == 1 { // 不同情况
					for a := 1; a <= 6; a++ {
						if a != j { // 考虑不同的情况
							for b := 1; b <= rollMax[a-1] && b <= i-1; b++ {
								dp[i][j][k] = (dp[i][j][k] + dp[i-1][a][b]) % 1000000007
							}
						}
					}
				} else { // 直接同上一个
					dp[i][j][k] = dp[i-1][j][k-1]
				}
			}
		}
	}
	res := 0
	for j := 1; j <= 6; j++ {
		for k := 1; k <= 15; k++ {
			res = (res + dp[n][j][k]) % 1000000007
		}
	}
	return res
}

# 2
func dieSimulator(n int, rollMax []int) int {
	dp := [7][16]int{} // 以j结尾,出现k次
	for j := 1; j <= 6; j++ {
		dp[j][1] = 1
	}
	for i := 2; i <= n; i++ {
		temp := [7][16]int{}
		for j := 1; j <= 6; j++ {
			for k := 1; k <= rollMax[j-1] && k <= i; k++ {
				if k == 1 { // 不同情况
					for a := 1; a <= 6; a++ {
						if a != j { // 考虑不同的情况
							for b := 1; b <= rollMax[a-1] && b <= i-1; b++ {
								temp[j][k] = (temp[j][k] + dp[a][b]) % 1000000007
							}
						}
					}
				} else { // 直接同上一个
					temp[j][k] = dp[j][k-1]
				}
			}
		}
		dp = temp
	}
	res := 0
	for j := 1; j <= 6; j++ {
		for k := 1; k <= 15; k++ {
			res = (res + dp[j][k]) % 1000000007
		}
	}
	return res
}

1227.飞机座位分配概率(2)

• 题目

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
剩下的乘客将会：如果他们自己的座位还空着，就坐到自己的座位上，
    当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？
示例 1：输入：n = 1 输出：1.00000
解释：第一个人只会坐在自己的位置上。
示例 2：输入: n = 2 输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
提示：1 <= n <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	找规律/数学	O(1)	O(1)
02	递推	O(n)	O(1)

func nthPersonGetsNthSeat(n int) float64 {
	if n == 1 {
		return 1
	}
	return 0.5
}

# 2
func nthPersonGetsNthSeat(n int) float64 {
	res := 1.0
	sum := 1.0
	// f(n) = 1/n * (f(n-1)+f(n-2)+f(n-3)+...+f(2)+1)
	for i := 2; i <= n; i++ {
		nth := 1.0 / float64(i)
		res = nth * sum
		sum += res
	}
	return res
}

1233.删除子文件夹(2)

• 题目

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，
并以 任意顺序 返回剩下的文件夹。
我们这样定义「子文件夹」：
如果文件夹folder[i]位于另一个文件夹folder[j]下，那么folder[i]就是folder[j]的子文件夹。
文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：
/后跟一个或者多个小写英文字母。
例如，/leetcode和/leetcode/problems都是有效的路径，而空字符串和/不是。
示例 1：输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b/" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。
示例 2：输入：folder = ["/a","/a/b/c","/a/b/d"] 输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d/" 都会被删除，因为它们都是 "/a" 的子文件夹。
示例 3：输入：folder = ["/a/b/c","/a/b/d","/a/b/ca"]
输出：["/a/b/c","/a/b/ca","/a/b/d"]
提示：1 <= folder.length<= 4 * 10^4
2 <= folder[i].length <= 100
folder[i]只包含小写字母和 /
folder[i]总是以字符 /起始
每个文件夹名都是唯一的

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(n)
02	哈希	O(n^2)	O(n)

func removeSubfolders(folder []string) []string {
	sort.Strings(folder)
	res := make([]string, 0)
	res = append(res, folder[0])
	prev := folder[0]
	for i := 1; i < len(folder); i++ {
		// 加'/'避免/a/b => /a/bb的情况
		if strings.HasPrefix(folder[i], prev+"/") == false {
			res = append(res, folder[i])
			prev = folder[i]
		}
	}
	return res
}

# 2
func removeSubfolders(folder []string) []string {
	res := make([]string, 0)
	m := make(map[string]bool)
	for i := 0; i < len(folder); i++ {
		m[folder[i]] = true
	}
	arr := make([]int, len(folder))
	for i := 0; i < len(folder); i++ {
		for j := 0; j < len(folder[i]); j++ {
			if folder[i][j] == '/' && j > 0 && m[folder[i][:j]] == true {
				arr[i] = 1
				break
			}
		}
	}
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			res = append(res, folder[i])
		}
	}
	return res
}

1234.替换子串得到平衡字符串(2)

• 题目

有一个只含有'Q', 'W', 'E','R'四种字符，且长度为 n的字符串。
假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例 1：输入：s = "QWER" 输出：0
解释：s 已经是平衡的了。
示例 2：输入：s = "QQWE" 输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：输入：s = "QQQW" 输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。 
示例 4：输入：s = "QQQQ" 输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
提示：1 <= s.length <= 10^5
s.length是4的倍数
s中只含有'Q', 'W', 'E','R'四种字符

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	滑动窗口	O(n)	O(1)
02	滑动窗口	O(n)	O(1)

func balancedString(s string) int {
	n := len(s)
	target := n / 4
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	if m['Q'] == target && m['W'] == target && m['E'] == target && m['R'] == target {
		return 0
	}
	res := n
	left := 0
	for right := 0; right < n; right++ {
		m[s[right]]--
		for left < n && left <= right && // [left,right]之间子串都是需要替换的（减去），使得m[x]<=target
			m['Q'] <= target && m['W'] <= target &&
			m['E'] <= target && m['R'] <= target {
			res = min(res, right-left+1)
			m[s[left]]++
			left++
		}
	}
	return res
}

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

# 2
func balancedString(s string) int {
	n := len(s)
	target := n / 4
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	if m['Q'] == target && m['W'] == target && m['E'] == target && m['R'] == target {
		return 0
	}
	res := n
	left := 0
	right := 0
	for left < n {
		if m['Q'] > target || m['W'] > target || m['E'] > target || m['R'] > target {
			if right < n {
				m[s[right]]--
				right++
			} else {
				break
			}
		} else {
			res = min(res, right-left)
			m[s[left]]++
			left++
		}
	}
	return res
}

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

1238.循环码排列(2)

• 题目

给你两个整数n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
p[0] = start
p[i] 和 p[i+1]的二进制表示形式只有一位不同
p[0] 和 p[2^n -1]的二进制表示形式也只有一位不同
示例 1：输入：n = 2, start = 3 输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]
示例 2：输出：n = 3, start = 2 输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)
提示：1 <= n <= 16
0 <= start<2^n

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	格雷码+位运算	O(2^n)	O(2^n)
02	格雷码+位移	O(2^n)	O(2^n)

func circularPermutation(n int, start int) []int {
	total := 1 << n
	res := make([]int, total)
	for i := 0; i < total; i++ {
		// 计算格雷码：leetcode89.格雷编码
		res[i] = i ^ (i >> 1) ^ start // 在计算格雷码的基础上，再与start异或
	}
	return res
}

# 2
func circularPermutation(n int, start int) []int {
	total := 1 << n
	res := []int{0, 1}
	for i := 2; i <= n; i++ {
		// 计算格雷码：leetcode89.格雷编码
		for j := len(res) - 1; j >= 0; j-- {
			res = append(res, res[j]+(1<<(i-1)))
		}
	}
	index := 0
	for i := 0; i < total; i++ {
		if res[i] == start {
			index = i
			break
		}
	}
	return append(res[index:], res[:index]...)
}

1239.串联字符串的最大长度(3)

• 题目

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，
如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1：输入：arr = ["un","iq","ue"] 输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
示例 2：输入：arr = ["cha","r","act","ers"] 输出：6
解释：可能的解答有 "chaers" 和 "acters"。
示例 3：输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26
提示：1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i]中只含有小写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯-子集	O(n*2^n)	O(n*2^n)
02	回溯	O(n*2^n)	O(n)
03	回溯	O(n*2^n)	O(n)

var res []string

func maxLength(arr []string) int {
	res = make([]string, 0)
	dfs(arr, "", 0)
	maxValue := 0
	for i := 0; i < len(res); i++ {
		if check(res[i]) == true && len(res[i]) > maxValue {
			maxValue = len(res[i])
		}
	}
	return maxValue
}

func dfs(arr []string, path string, index int) {
	res = append(res, path)
	for i := index; i < len(arr); i++ {
		dfs(arr, path+arr[i], i+1)
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

# 2
var res int

func maxLength(arr []string) int {
	res = 0
	dfs(arr, "", 0)
	return res
}

func dfs(arr []string, path string, index int) {
	if check(path) == true && len(path) > res {
		res = len(path)
	}
	for i := index; i < len(arr); i++ {
		dfs(arr, path+arr[i], i+1)
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

# 3
var res int

func maxLength(arr []string) int {
	res = 0
	dfs(arr, "", 0)
	return res
}

func dfs(arr []string, path string, index int) {
	for i := index; i < len(arr); i++ {
		newStr := path + arr[i]
		if check(newStr) == true {
			if len(newStr) > res {
				res = len(newStr)
			}
			dfs(arr, path+arr[i], i+1)
		}
	}
}

func check(s string) bool {
	arr := [26]int{}
	for i := 0; i < len(s); i++ {
		value := int(s[i] - 'a')
		arr[value]++
		if arr[value] > 1 {
			return false
		}
	}
	return true
}

1247.交换字符使得字符串相同(1)

• 题目

有两个长度相同的字符串s1 和s2，且它们其中只含有字符"x" 和"y"，
你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。
也就是说，我们可以交换s1[i] 和s2[j]，但不能交换s1[i] 和s1[j]。
最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回-1 。
示例 1：输入：s1 = "xx", s2 = "yy" 输出：1
解释：交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。
示例 2：输入：s1 = "xy", s2 = "yx" 输出：2
解释：交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。
示例 3：输入：s1 = "xx", s2 = "xy" 输出：-1
示例 4：输入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx" 输出：4
提示：1 <= s1.length, s2.length <= 1000
s1, s2只包含'x'或'y'。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)

func minimumSwap(s1 string, s2 string) int {
	a, b := 0, 0
	for i := 0; i < len(s1); i++ {
		if s1[i] == s2[i] { // 相同不需要交换
			continue
		}
		if s1[i] == 'x' {
			a++
		} else {
			b++
		}
	}
	// a => x y
	// b => y x
	if a%2+b%2 == 1 {
		return -1
	}
	return a/2 + b/2 + 2*(a%2)
}

1248.统计「优美子数组」(4)

• 题目

给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：输入：nums = [1,1,2,1,1], k = 3 输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：输入：nums = [2,4,6], k = 1 输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2 输出：16
提示：1 <= nums.length <= 50000
    1 <= nums[i] <= 10^5
    1 <= k <= nums.length

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	统计奇数	O(n)	O(n)
02	前缀和	O(n)	O(n)
03	滑动窗口	O(n)	O(1)
04	动态规划	O(n)	O(n)

func numberOfSubarrays(nums []int, k int) int {
	res := 0
	arr := make([]int, 0)
	arr = append(arr, -1)
	for i := 0; i < len(nums); i++ {
		if nums[i]%2 == 1 {
			arr = append(arr, i)
		}
	}
	arr = append(arr, len(nums))
	for i := 1; i+k < len(arr); i++ {
		res = res + (arr[i]-arr[i-1])*(arr[i+k]-arr[i+k-1])
	}
	return res
}

# 2
func numberOfSubarrays(nums []int, k int) int {
	res := 0
	arr := make([]int, len(nums)+1)
	arr[0] = 1
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]%2
		arr[sum]++
		if sum >= k {
			res = res + arr[sum-k]
		}
	}
	return res
}

# 3
func numberOfSubarrays(nums []int, k int) int {
	res := 0
	left, right := 0, 0
	count := 0
	for right < len(nums) {
		if nums[right]%2 == 1 {
			count++
		}
		right++
		if count == k {
			temp := right
			for right < len(nums) && nums[right]%2 == 0 {
				right++
			}
			totalRight := right - temp + 1
			totalLeft := 1
			for nums[left]%2 == 0 {
				left++
				totalLeft++
			}
			res = res + totalLeft*totalRight
			count--
			left++
		}
	}
	return res
}

# 4
func numberOfSubarrays(nums []int, k int) int {
	res := 0
	dp := make([]int, 0)
	count := 0
	for i := 0; i < len(nums); i++ {
		count++
		if nums[i]%2 == 1 {
			dp = append(dp, count)
			count = 0
		}
		if len(dp) >= k {
			res = res + dp[len(dp)-k]
		}
	}
	return res
}

1249.移除无效的括号(2)

• 题目

给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
    空字符串或只包含小写字母的字符串
    可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
    可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
示例 1：输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：输入：s = "a)b(c)d" 输出："ab(c)d"
示例 3：输入：s = "))((" 输出：""
解释：空字符串也是有效的
示例 4：输入：s = "(a(b(c)d)" 输出："a(b(c)d)"
提示：1 <= s.length <= 10^5
    s[i] 可能是 '('、')' 或英文小写字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(n)
02	栈辅助	O(n)	O(n)

func minRemoveToMakeValid(s string) string {
	arr := []byte(s)
	sum := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] == '(' {
			sum++
		} else if arr[i] == ')' {
			sum--
			if sum < 0 {
				arr[i] = ' '
				sum = 0
			}
		}
	}
	sum = 0
	for i := len(arr) - 1; i >= 0; i-- {
		if arr[i] == ')' {
			sum++
		} else if arr[i] == '(' {
			sum--
			if sum < 0 {
				arr[i] = ' '
				sum = 0
			}
		}
	}
	return strings.ReplaceAll(string(arr), " ", "")
}

# 2
func minRemoveToMakeValid(s string) string {
	arr := []byte(s)
	stack := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		if arr[i] == '(' {
			stack = append(stack, i)
		} else if arr[i] == ')' {
			if len(stack) == 0 {
				arr[i] = ' '
			} else {
				stack = stack[:len(stack)-1]
			}
		}
	}
	for i := 0; i < len(stack); i++ {
		arr[stack[i]] = ' '
	}
	return strings.ReplaceAll(string(arr), " ", "")
}

1253.重构2行二进制矩阵(2)

• 题目

给你一个2行 n 列的二进制数组：
矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是0就是1。
第 0 行的元素之和为upper。
第 1 行的元素之和为 lower。
第 i 列（从 0 开始编号）的元素之和为colsum[i]，colsum是一个长度为n的整数数组。
你需要利用upper，lower和colsum来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
示例 1：输入：upper = 2, lower = 1, colsum = [1,1,1] 输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。
示例 2：输入：upper = 2, lower = 3, colsum = [2,2,1,1] 输出：[]
示例 3：输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
提示：1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	贪心	O(n)	O(n)
02	贪心	O(n)	O(n)

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
	res := make([][]int, 0)
	total := 0
	two := 0
	for i := 0; i < len(colsum); i++ {
		total = total + colsum[i]
		if colsum[i] == 2 {
			two++
		}
	}
	if total != upper+lower || two > upper || two > lower {
		return nil
	}
	up := make([]int, len(colsum))
	down := make([]int, len(colsum))
	upper = upper - two // 上面数组单独1的个数
	for i := 0; i < len(colsum); i++ {
		if colsum[i] == 2 { // 2=>各填充1
			up[i] = 1
			down[i] = 1
			lower--
		} else if colsum[i] == 1 {
			if upper > 0 { // 先填充上面数组
				up[i] = 1
				upper--
			} else {
				down[i] = 1
			}
		}
	}
	res = append(res, up, down)
	return res
}

# 2
func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
	res := make([][]int, 0)
	up := make([]int, len(colsum))
	down := make([]int, len(colsum))
	upSum := 0
	lowSum := 0
	total := 0
	for i := 0; i < len(colsum); i++ {
		total = total + colsum[i]
		if colsum[i] == 2 { // 2=>各填充1
			up[i] = 1
			down[i] = 1
			upSum++
			lowSum++
		}
	}
	if upSum > upper || lowSum > lower || total != upper+lower {
		return nil
	}
	for i := 0; i < len(colsum); i++ {
		if colsum[i] == 1 {
			if upSum < upper {
				up[i] = 1
				upSum++
			} else {
				down[i] = 1
			}
		}
	}
	res = append(res, up, down)
	return res
}

1254.统计封闭岛屿的数目(2)

• 题目

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
示例 1：输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],
[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] 输出：2
解释：灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例 2：输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] 输出：1
示例 3：输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2
提示： 1 <= grid.length, grid[0].length <= 100
    0 <= grid[i][j] <=1

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)
02	广度优先搜索	O(n^2)	O(n)

func closedIsland(grid [][]int) int {
	res := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 0 && dfs(grid, i, j) == true {
				res++
			}
		}
	}
	return res
}

func dfs(grid [][]int, i, j int) bool {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) {
		return false
	}
	if grid[i][j] == 1 {
		return true
	}
	grid[i][j] = 1
	up := dfs(grid, i, j+1)
	down := dfs(grid, i, j-1)
	left := dfs(grid, i-1, j)
	right := dfs(grid, i+1, j)
	return up && down && left && right
}

# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}

func closedIsland(grid [][]int) int {
	res := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 0 {
				flag := true
				queue := make([][2]int, 0)
				queue = append(queue, [2]int{i, j})
				if i == 0 || j == 0 || i == len(grid)-1 || j == len(grid[i])-1 {
					flag = false
				}
				for len(queue) > 0 {
					node := queue[0]
					queue = queue[1:]
					for k := 0; k < 4; k++ {
						x := dx[k] + node[0]
						y := dy[k] + node[1]
						if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[i]) {
							continue
						}
						if grid[x][y] == 1 {
							continue
						}
						if x == 0 || y == 0 || x == len(grid)-1 || y == len(grid[i])-1 {
							flag = false
						}
						queue = append(queue, [2]int{x, y})
						grid[x][y] = 1
					}
				}
				if flag == true {
					res++
				}
			}
		}
	}
	return res
}

1261.在受污染的二叉树中查找元素(2)

• 题目

给出一个满足下述规则的二叉树：
root.val == 0
如果 treeNode.val == x 且treeNode.left != null，那么treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的treeNode.val都变成了-1。
请你先还原二叉树，然后实现FindElements类：
FindElements(TreeNode* root)用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target)判断目标值target是否存在于还原后的二叉树中并返回结果。
示例 1：输入： ["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：[null,false,true]
解释：FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 
示例 2：输入： ["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：[null,true,true,false]
解释：FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
示例 3：输入： ["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：[null,true,false,false,true]
解释：FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True
提示：TreeNode.val == -1
二叉树的高度不超过20
节点的总数在[1,10^4]之间
调用find()的总次数在[1,10^4]之间
0 <= target <= 10^6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	数组辅助	O(n)	O(n)

type FindElements struct {
	m map[int]bool
}

type Node struct {
	root  *TreeNode
	index int
}

func Constructor(root *TreeNode) FindElements {
	if root == nil {
		return FindElements{m: map[int]bool{}}
	}
	m := make(map[int]bool)
	m[0] = true
	queue := make([]Node, 0)
	queue = append(queue, Node{root: root, index: 0})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		var temp Node
		if node.root.Left != nil {
			temp = Node{
				root:  node.root.Left,
				index: node.index*2 + 1,
			}
			m[node.index*2+1] = true
		}
		if node.root.Right != nil {
			temp = Node{
				root:  node.root.Right,
				index: node.index*2 + 2,
			}
			m[node.index*2+2] = true
		}
		queue = append(queue, temp)
	}
	return FindElements{m: m}
}

func (this *FindElements) Find(target int) bool {
	return this.m[target]
}

# 2
type FindElements struct {
	num []int
}

type Node struct {
	root  *TreeNode
	index int
}

func Constructor(root *TreeNode) FindElements {
	if root == nil {
		return FindElements{num: []int{}}
	}
	num := make([]int, 0)
	num = append(num, 0)
	queue := make([]Node, 0)
	queue = append(queue, Node{
		root:  root,
		index: 0,
	})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node.root.Left != nil {
			temp := Node{
				root:  node.root.Left,
				index: node.index*2 + 1,
			}
			num = append(num, node.index*2+1)
			queue = append(queue, temp)
		}
		if node.root.Right != nil {
			temp := Node{
				root:  node.root.Right,
				index: node.index*2 + 2,
			}
			num = append(num, node.index*2+2)
			queue = append(queue, temp)
		}
	}
	return FindElements{num: num}
}

func (this *FindElements) Find(target int) bool {
	for i := 0; i < len(this.num); i++ {
		if this.num[i] == target {
			return true
		}
	}
	return false
}

1262.可被三整除的最大和(1)

• 题目

给你一个整数数组nums，请你找出并返回能被三整除的元素最大和。
示例 1：输入：nums = [3,6,5,1,8] 输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：输入：nums = [4] 输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：输入：nums = [1,2,3,4,4] 输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
提示：1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n)	O(1)

func maxSumDivThree(nums []int) int {
	dp := [3]int{}
	for i := 0; i < len(nums); i++ {
		for _, v := range dp {
			value := v + nums[i]
			dp[value%3] = max(dp[value%3], value)
		}
	}
	return dp[0]
}

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

1267.统计参与通信的服务器(1)

• 题目

这里有一幅服务器分布图，服务器的位置标识在m * n的整数矩阵网格grid中，
1 表示单元格上有服务器，0 表示没有。
如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
示例 1：输入：grid = [[1,0],[0,1]] 输出：0
解释：没有一台服务器能与其他服务器进行通信。
示例 2：输入：grid = [[1,0],[1,1]] 输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。
示例 3：输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]] 输出：4
解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。
提示：m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n^2)	O(n)

func countServers(grid [][]int) int {
	a := make(map[int]int) // 行
	b := make(map[int]int) // 列
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 {
				a[i]++
				b[j]++
			}
		}
	}
	res := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 && (a[i] > 1 || b[j] > 1) {
				res++
			}
		}
	}
	return res
}

1268.搜索推荐系统(2)

• 题目

给你一个产品数组products和一个字符串searchWord，products 数组中每个产品都是一个字符串。
请你设计一个推荐系统，在依次输入单词searchWord 的每一个字母后，推荐products 数组中前缀与searchWord 相同的最多三个产品。
如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
请你以二维列表的形式，返回在输入searchWord每个字母后相应的推荐产品的列表。
示例 1：输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]
示例 2：输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
示例 3：输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
示例 4：输入：products = ["havana"], searchWord = "tatiana" 输出：[[],[],[],[],[],[],[]]
提示：1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i]中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord中所有字符都是小写英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(n^2)	O(n^2)
02	trie树	O(n^2)	O(n^2)

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)
	res := make([][]string, 0)
	for i := 0; i < len(searchWord); i++ {
		target := searchWord[:i+1]
		arr := make([]string, 0)
		for j := 0; j < len(products); j++ {
			if len(products[j]) >= len(target) && products[j][:i+1] == target {
				arr = append(arr, products[j])
			}
			if len(arr) == 3 {
				break
			}
		}
		res = append(res, arr)
	}
	return res
}

# 2
func suggestedProducts(products []string, searchWord string) [][]string {
	res := make([][]string, len(searchWord))
	t := &Trie{}
	for i := 0; i < len(products); i++ {
		t.Insert(products[i])
	}
	for i := 0; i < len(searchWord); i++ {
		res[i] = t.StartsWith(searchWord[:i+1])
	}
	return res
}

type Trie struct {
	next [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
	str  string
}

// 插入word
func (this *Trie) Insert(word string) {
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next: [26]*Trie{},
			}
		}
		temp = temp.next[value]
	}
	temp.str = word
}

// 查找前缀
func (this *Trie) StartsWith(prefix string) []string {
	temp := this
	for _, v := range prefix {
		value := v - 'a'
		if temp = temp.next[value]; temp == nil {
			return nil
		}
	}
	res := make([]string, 0)
	temp.dfs(&res)
	return res
}

func (this *Trie) dfs(res *[]string) {
	if len(*res) == 3 {
		return
	}
	if this.str != "" {
		*res = append(*res, this.str)
	}
	for _, v := range this.next {
		if len(*res) == 3 {
			return
		}
		if v == nil {
			continue
		}
		v.dfs(res)
	}
}

1276.不浪费原料的汉堡制作方案(1)

• 题目

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。
给你两个整数tomatoSlices和cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：
巨无霸汉堡：4 片番茄和 1 片奶酪
小皇堡：2 片番茄和1 片奶酪
请你以[total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，
使得剩下的番茄片tomatoSlices和奶酪片cheeseSlices的数量都是0。
如果无法使剩下的番茄片tomatoSlices和奶酪片cheeseSlices的数量为0，就请返回[]。
示例 1：输入：tomatoSlices = 16, cheeseSlices = 7 输出：[1,6]
解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 4*1 + 2*6 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。
示例 2：输入：tomatoSlices = 17, cheeseSlices = 4 输出：[]
解释：只制作小皇堡和巨无霸汉堡无法用光全部原料。
示例 3：输入：tomatoSlices = 4, cheeseSlices = 17 输出：[]
解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。
示例 4：输入：tomatoSlices = 0, cheeseSlices = 0 输出：[0,0]
示例 5：输入：tomatoSlices = 2, cheeseSlices = 1 输出：[0,1]
提示：0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数学	O(1)	O(1)

func numOfBurgers(tomatoSlices int, cheeseSlices int) []int {
	a, b := tomatoSlices, cheeseSlices
	c := a - 2*b
	if c%2 == 0 && c/2 <= b && 0 <= c {
		return []int{c / 2, b - c/2}
	}
	return nil
}

1277.统计全为1的正方形子矩阵(3)

• 题目

给你一个m * n的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：输入：matrix =
[
 [0,1,1,1],
 [1,1,1,1],
 [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
提示：1 <= arr.length<= 300
1 <= arr[0].length<= 300
0 <= arr[i][j] <= 1

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n^2)
02	动态规划	O(n^2)	O(n)
03	动态规划	O(n^2)	O(1)

func countSquares(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 || j == 0 {
				dp[i][j] = matrix[i][j]
			} else if matrix[i][j] == 0 {
				dp[i][j] = 0
			} else {
				dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1
			}
			res = res + dp[i][j]
		}
	}
	return res
}

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

# 2
func countSquares(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	dp := make([]int, m)
	res := 0
	for i := 0; i < n; i++ {
		temp := make([]int, m)
		for j := 0; j < m; j++ {
			if i == 0 || j == 0 {
				temp[j] = matrix[i][j]
			} else if matrix[i][j] == 0 {
				temp[j] = 0
			} else {
				temp[j] = min(min(temp[j-1], dp[j]), dp[j-1]) + 1
			}
			res = res + temp[j]
		}
		copy(dp, temp)
	}
	return res
}

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

# 3
func countSquares(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i > 0 && j > 0 && matrix[i][j] > 0 {
				matrix[i][j] = min(min(matrix[i][j-1], matrix[i-1][j]), matrix[i-1][j-1]) + 1
			}
			res = res + matrix[i][j]
		}
	}
	return res
}

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

1282.用户分组(2)

• 题目

有n位用户参加活动，他们的ID从 0 到 n - 1，每位用户都 恰好 属于某一用户组。
给你一个长度为 n 的数组groupSizes，其中包含每位用户所处的用户组的大小，
请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。
你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
示例 1：输入：groupSizes = [3,3,3,3,3,1,3] 输出：[[5],[0,1,2],[3,4,6]]
解释： 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
示例 2：输入：groupSizes = [2,1,3,3,3,2] 输出：[[1],[0,5],[2,3,4]]
提示：groupSizes.length == n
1 <= n<= 500
1 <=groupSizes[i] <= n

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	哈希辅助	O(n)	O(n)

func groupThePeople(groupSizes []int) [][]int {
	res := make([][]int, 0)
	m := make(map[int][]int)
	for i := 0; i < len(groupSizes); i++ {
		m[groupSizes[i]] = append(m[groupSizes[i]], i)
	}
	for k, v := range m {
		for i := 0; i < len(v); i = i + k {
			res = append(res, v[i:i+k])
		}
	}
	return res
}

# 2
func groupThePeople(groupSizes []int) [][]int {
	res := make([][]int, 0)
	m := make(map[int][]int)
	for i := 0; i < len(groupSizes); i++ {
		m[groupSizes[i]] = append(m[groupSizes[i]], i)
		if groupSizes[i] == len(m[groupSizes[i]]) {
			res = append(res, m[groupSizes[i]])
			m[groupSizes[i]] = []int{}
		}
	}
	return res
}

1283.使结果不超过阈值的最小除数(1)

• 题目

给你一个整数数组nums 和一个正整数threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
请你找出能够使上述结果小于等于阈值threshold的除数中 最小 的那个。
每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
题目保证一定有解。
示例 1：输入：nums = [1,2,5,9], threshold = 6 输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
示例 2：输入：nums = [2,3,5,7,11], threshold = 11 输出：3
示例 3：输入：nums = [19], threshold = 5 输出：4
提示：1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <=threshold <= 10^6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(1)

func smallestDivisor(nums []int, threshold int) int {
	left, right := 1, math.MaxInt32/10
	res := 0
	for left <= right {
		mid := left + (right-left)/2
		count := getValue(nums, mid)
		if count > threshold {
			left = mid + 1
		} else {
			right = mid - 1
			res = mid
		}
	}
	return res
}

func getValue(nums []int, target int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		res = res + (nums[i]+target-1)/target // 向上取整
	}
	return res
}

1286.字母组合迭代器(2)

• 题目

请你设计一个迭代器类，包括以下内容：
一个构造函数，输入参数包括：一个有序且字符唯一的字符串characters（该字符串只包含小写英文字母）和一个数字combinationLength。
函数next()，按字典序返回长度为combinationLength 的下一个字母组合。
函数hasNext()，只有存在长度为combinationLength 的下一个字母组合时，才返回True；否则，返回 False。
示例：CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator
iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false
提示：1 <= combinationLength <=characters.length <= 15
每组测试数据最多包含10^4次函数调用。
题目保证每次调用函数next时都存在下一个字母组合。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	模拟	O(n)	O(n)
02	递归	O(n!)	O(n!)

type CombinationIterator struct {
	flag bool
	s    string
	arr  []int
}

func Constructor(characters string, combinationLength int) CombinationIterator {
	arr := make([]int, combinationLength)
	for i := 0; i < combinationLength; i++ {
		arr[i] = i
	}
	return CombinationIterator{
		flag: false,
		s:    characters,
		arr:  arr,
	}
}

func (this *CombinationIterator) Next() string {
	res := ""
	for i := 0; i < len(this.arr); i++ {
		res = res + string(this.s[this.arr[i]])
	}
	index := -1
	for i := len(this.arr) - 1; i >= 0; i-- {
		// 正常情况下：以abcdef 3 为例子
		// 0 1 5 => abf  下一个 acd
		// 6-3+2 = 5
		// 6-3+1 != 1 => index = 1
		// 然后: arr[index]+1，后面递增
		target := len(this.s) - len(this.arr) + i
		if this.arr[i] != target { // 从右到左边：找到
			index = i
			break
		}
	}
	if index == -1 { // 没有更大的
		this.flag = true
	} else {
		this.arr[index]++
		for i := index + 1; i < len(this.arr); i++ {
			this.arr[i] = this.arr[i-1] + 1
		}
	}
	return res
}

func (this *CombinationIterator) HasNext() bool {
	return this.flag == false
}

# 2
type CombinationIterator struct {
	arr   []string
	index int
}

func dfs(str string, k int, index int, cur string, res *[]string) {
	if len(cur) == k {
		*res = append(*res, cur)
		return
	}
	for i := index; i < len(str); i++ {
		dfs(str, k, i+1, cur+string(str[i]), res)
	}
}
func Constructor(characters string, combinationLength int) CombinationIterator {
	res := make([]string, 0)
	dfs(characters, combinationLength, 0, "", &res)
	return CombinationIterator{
		arr:   res,
		index: 0,
	}
}

func (this *CombinationIterator) Next() string {
	if this.index < len(this.arr) {
		this.index++
		return this.arr[this.index-1]
	}
	return ""
}

func (this *CombinationIterator) HasNext() bool {
	return this.index < len(this.arr)
}

1288.删除被覆盖区间(4)

• 题目

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当c <= a且b <= d时，我们才认为区间[a,b) 被区间[c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。
示例：输入：intervals = [[1,4],[3,6],[2,8]] 输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
提示：1 <= intervals.length <= 1000
0 <= intervals[i][0] <intervals[i][1] <= 10^5
对于所有的i != j：intervals[i] != intervals[j]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序遍历	O(nlog(n))	O(1)
02	排序遍历	O(nlog(n))	O(1)
03	排序遍历	O(nlog(n))	O(1)
04	暴力法	O(n^2)	O(1)

func removeCoveredIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] > intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	res := 0
	maxValue := intervals[0][1]
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] == intervals[i-1][0] { // 合并
			res++
			continue
		}
		if intervals[i][1] > maxValue {
			maxValue = intervals[i][1] // 更新
		} else {
			res++ // 合并
		}
	}
	return len(intervals) - res
}

# 2
func removeCoveredIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] > intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	res := 0
	left := intervals[0][0]
	right := intervals[0][1]
	for i := 1; i < len(intervals); i++ {
		l, r := intervals[i][0], intervals[i][1]
		if left <= l && r <= right { // 合并
			res++
		}
		if right < r { // 更新
			left = l
			right = r
		}
	}
	return len(intervals) - res
}

# 3
func removeCoveredIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] > intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	res := 0
	maxValue := 0
	for i := 0; i < len(intervals); i++ {
		if maxValue < intervals[i][1] {
			res++
			maxValue = intervals[i][1]
		}
	}
	return res
}

# 4
func removeCoveredIntervals(intervals [][]int) int {
	res := len(intervals)
	for i := 0; i < len(intervals); i++ {
		for j := 0; j < len(intervals); j++ {
			if i != j && intervals[j][0] <= intervals[i][0] &&
				intervals[i][1] <= intervals[j][1] {
				res--
				break
			}
		}
	}
	return res
}

1291.顺次数(2)

• 题目

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。
示例 1：输出：low = 100, high = 300输出：[123,234]
示例 2：输出：low = 1000, high = 13000 输出：[1234,2345,3456,4567,5678,6789,12345]
提示： 10 <= low <= high <= 10^9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	枚举	O(1)	O(1)
02	枚举	O(1)	O(1)

func sequentialDigits(low int, high int) []int {
	res := make([]int, 0)
	for i := 1; i <= 9; i++ {
		num := i
		for j := i + 1; j <= 9; j++ {
			num = num*10 + j
			if num >= low && num <= high {
				res = append(res, num)
			}
		}
	}
	sort.Ints(res)
	return res
}

# 2
func sequentialDigits(low int, high int) []int {
	res := make([]int, 0)
	str := "123456789"
	for i := 0; i <= 9; i++ {
		for j := i + 1; j <= 9; j++ {
			num, _ := strconv.Atoi(str[i:j])
			if num >= low && num <= high {
				res = append(res, num)
			}
		}
	}
	sort.Ints(res)
	return res
}

1292.元素和小于等于阈值的正方形的最大边长(3)

• 题目

给你一个大小为m x n的矩阵mat和一个整数阈值threshold。
请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0。
示例 1：输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。
示例 2：输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 输出：0
示例 3：输入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 输出：3
示例 4：输入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 输出：2
提示：1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold<= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+二分查找	O(n^2log(n))	O(n^2)
02	前缀和	O(n^3)	O(n^2)
03	前缀和	O(n^3)	O(n^2)

func maxSideLength(mat [][]int, threshold int) int {
	n, m := len(mat), len(mat[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
		}
	}
	res := min(n, m)
	left, right := 0, res // res可以为0
	for left <= right {
		mid := left + (right-left)/2
		if check(arr, mid, threshold) == true {
			left = mid + 1
			res = mid
		} else {
			right = mid - 1
		}
	}
	return res
}

func check(arr [][]int, mid int, threshold int) bool {
	for i := 1; i+mid <= len(arr); i++ {
		for j := 1; j+mid <= len(arr[i]); j++ {
			sum := arr[i+mid-1][j+mid-1] - arr[i+mid-1][j-1] - arr[i-1][j+mid-1] + arr[i-1][j-1]
			if sum <= threshold {
				return true
			}
		}
	}
	return false
}

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

# 2
func maxSideLength(mat [][]int, threshold int) int {
	n, m := len(mat), len(mat[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
		}
	}
	res := 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for k := 0; i+k <= n && j+k <= m; k++ {
				value := arr[i+k][j+k] - arr[i-1][j+k] - arr[i+k][j-1] + arr[i-1][j-1]
				if value <= threshold && res < k+1 {
					res = k + 1
				}
				if value > threshold {
					break
				}
			}
		}
	}
	return res
}

# 3
func maxSideLength(mat [][]int, threshold int) int {
	n, m := len(mat), len(mat[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
		}
	}
	res := 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for k := min(i, j); k > res; k-- {
				value := arr[i][j] - arr[i-k][j] - arr[i][j-k] + arr[i-k][j-k]
				if value <= threshold && res < k {
					res = k
					break
				}
			}
		}
	}
	return res
}

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

1296.划分数组为连续数字的集合(3)

• 题目

给你一个整数数组nums和一个正整数k，请你判断是否可以把这个数组划分成一些由k个连续数字组成的集合。
如果可以，请返回True；否则，返回False。
注意：此题目与 846 重复
示例 1：输入：nums = [1,2,3,3,4,4,5,6], k = 4 输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。
示例 2：输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。
示例 3：输入：nums = [3,3,2,2,1,1], k = 3 输出：true
示例 4：输入：nums = [1,2,3,4], k = 3 输出：false
解释：数组不能分成几个大小为 3 的子数组。
提示：1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序遍历	O(nlog(n))	O(1)
02	哈希辅助	O(nlog(n))	O(n)
03	哈希辅助	O(nlog(n))	O(n)

func isPossibleDivide(nums []int, k int) bool {
	n := len(nums)
	if n%k != 0 {
		return false
	}
	if k == 1 {
		return true
	}
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		if nums[i] >= 0 {
			count := 1
			for j := i + 1; j < n; j++ {
				if nums[j] > nums[i]+count {
					break
				}
				if nums[j] >= 0 && nums[j] == nums[i]+count {
					nums[j] = -1
					count++
					if count == k {
						break
					}
				}
			}
			if count != k {
				return false
			}
			nums[i] = -1
		}
	}
	return true
}

# 2
func isPossibleDivide(nums []int, k int) bool {
	n := len(nums)
	if n%k != 0 {
		return false
	}
	if k == 1 {
		return true
	}
	arr := make([]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if m[nums[i]] == 0 {
			arr = append(arr,nums[i])
		}
		m[nums[i]]++
	}
	sort.Ints(arr)
	for i := 0; i < len(arr); i++ {
		if m[arr[i]] > 0 {
			for j := 1; j < k; j++ {
				value := arr[i] + j
				m[value] = m[value] - m[arr[i]]
				if m[value] < 0 {
					return false
				}
			}
		}
	}
	return true
}

# 3
func isPossibleDivide(nums []int, k int) bool {
	n := len(nums)
	if n%k != 0 {
		return false
	}
	if k == 1 {
		return true
	}
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	sort.Ints(nums)
	for i := 0; i < len(nums); i++ {
		value := m[nums[i]]
		if value > 0 {
			for j := 0; j < k; j++ {
				if m[nums[i]+j] < value {
					return false
				}
				m[nums[i]+j] = m[nums[i]+j] - value
			}
		}
	}
	return true
}

1297.子串的最大出现次数(2)

• 题目

给你一个字符串s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：
子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于minSize 且小于等于maxSize 。
示例 1：输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4 输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。
示例 2：输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3 输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。
示例 3：输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3 输出：3
示例 4：输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3 输出：0
提示：1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s只包含小写英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	滑动窗口	O(n)	O(n)
02	固定窗口	O(n^2)	O(n)

func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
	res := 0
	m := make(map[string]int)
	window := make(map[byte]int)
	count := 0
	left := 0
	for i := 0; i < len(s); i++ {
		window[s[i]]++
		if window[s[i]] == 1 {
			count++
		}
		length := i - left + 1
		if length < minSize {
			continue
		}
		if length > minSize { // 滑动窗口左边=>右移
			window[s[left]]--
			if window[s[left]] == 0 {
				count--
			}
			left++
			length--
		}
		// 只考虑最小值minSize，例如：minSize=2, maxSize=3
		// 如果abc出现3次，那么代表ab至少出现>=3次
		if count <= maxLetters {
			m[s[left:i+1]]++
		}
	}
	for _, v := range m {
		res = max(res, v)
	}
	return res
}

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

# 2
func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
	res := 0
	m := make(map[string]int)
	for i := 0; i <= len(s)-minSize; i++ {
		str := s[i : i+minSize]
		count := getCount(str)
		// 只考虑最小值minSize，例如：minSize=2, maxSize=3
		// 如果abc出现3次，那么代表ab至少出现>=3次
		if count <= maxLetters {
			m[str]++
		}
	}
	for _, v := range m {
		res = max(res, v)
	}
	return res
}

func getCount(str string) int {
	m := make(map[byte]int)
	for i := 0; i < len(str); i++ {
		m[str[i]]++
	}
	return len(m)
}

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

1300.转变数组后最接近目标值的数组和(3)

• 题目

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，
使得将数组中所有大于 value 的值变成 value 后，
数组的和最接近  target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。
示例 1：输入：arr = [4,9,3], target = 10 输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
示例 2：输入：arr = [2,3,5], target = 10 输出：5
示例 3：输入：arr = [60864,25176,27249,21296,20204], target = 56803 输出：11361
提示：
    1 <= arr.length <= 10^4
    1 <= arr[i], target <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(n)
02	二分查找	O(nlog(n))	O(n)
03	遍历	O(n^2)	O(1)

func findBestValue(arr []int, target int) int {
	sort.Ints(arr)
	n := len(arr)
	temp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		temp[i] = temp[i-1] + arr[i-1]
	}
	right := arr[n-1]
	res := 0
	diff := target
	for i := 1; i <= right; i++ {
		index := sort.SearchInts(arr, i)
		if index < 0 {
			index = abs(index) - 1
		}
		total := temp[index] + (n-index)*i
		if abs(total-target) < diff {
			diff = abs(total - target)
			res = i
		}
	}
	return res
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

# 2
func findBestValue(arr []int, target int) int {
	sort.Ints(arr)
	n := len(arr)
	temp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		temp[i] = temp[i-1] + arr[i-1]
	}
	left, right := 0, arr[n-1]
	res := 0
	for left <= right {
		mid := left + (right-left)/2
		index := sort.SearchInts(arr, mid)
		if index < 0 {
			index = abs(index) - 1
		}
		total := temp[index] + (n-index)*mid
		if total <= target {
			res = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	a := getSum(arr, res)
	b := getSum(arr, res+1)
	if abs(a-target) > abs(b-target) {
		return res + 1
	}
	return res
}

func getSum(nums []int, target int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] <= target {
			res = res + nums[i]
		} else {
			res = res + target
		}
	}
	return res
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

# 3
func findBestValue(arr []int, target int) int {
	sort.Ints(arr)
	n := len(arr)
	res := target / n
	diff := target + 1
	for {
		a := getSum(arr, res)
		if diff <= abs(target-a) {
			return res - 1
		}
		diff = abs(target - a)
		res = res + 1
	}
	return res
}

func getSum(nums []int, target int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] <= target {
			res = res + nums[i]
		} else {
			res = res + target
		}
	}
	return res
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

1201-1300-Hard

1220.统计元音字母序列的数目(1)

• 题目

给你一个整数n，请你帮忙统计一下我们可以按下述规则形成多少个长度为n的字符串：
字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音'a'后面都只能跟着'e'
每个元音'e'后面只能跟着'a'或者是'i'
每个元音'i'后面不能 再跟着另一个'i'
每个元音'o'后面只能跟着'i'或者是'u'
每个元音'u'后面只能跟着'a'
由于答案可能会很大，所以请你返回 模10^9 + 7之后的结果。
示例 1：输入：n = 1 输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
示例 2：输入：n = 2 输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
示例 3：输入：n = 5 输出：68
提示：1 <= n <= 2 * 10^4

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n)	O(1)

var mod = 1000000007

func countVowelPermutation(n int) int {
	a, e, i, o, u := 1, 1, 1, 1, 1
	for k := 2; k <= n; k++ {
		tempA := (e + i + u) % mod
		tempE := (a + i) % mod
		tempI := (e + o) % mod
		tempO := i % mod
		tempU := (i + o) % mod
		a, e, i, o, u = tempA, tempE, tempI, tempO, tempU
	}
	return (a + e + i + o + u) % mod
}

1235.规划兼职工作(4)

• 题目

你打算利用空闲时间来做兼职工作赚些零花钱。
这里有n份兼职工作，每份工作预计从startTime[i]开始到endTime[i]结束，报酬为profit[i]。
给你一份兼职工作表，包含开始时间startTime，
结束时间endTime和预计报酬profit三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作。
示例 1：输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] 输出：120
解释：我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。
示例 2：输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：我们选择第 1，4，5 份工作。 
共获得报酬 150 = 20 + 70 + 60。
示例 3：输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] 输出：6
提示：1 <= startTime.length == endTime.length ==profit.length<= 5 * 10^4
1 <=startTime[i] <endTime[i] <= 10^9
1 <=profit[i] <= 10^4

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)
02	内置函数	O(nlog(n))	O(n)
03	动态规划	O(n^2)	O(n)
04	二分查找	O(nlog(n))	O(n)

type Node struct {
	startTime int
	endTime   int
	profit    int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(startTime)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			startTime: startTime[i],
			endTime:   endTime[i],
			profit:    profit[i],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].endTime == arr[j].endTime {
			return arr[i].startTime < arr[j].startTime
		}
		return arr[i].endTime < arr[j].endTime
	})
	dp := make([]int, n)
	maxValue := 0
	for i := 0; i < n; i++ {
		dp[i] = arr[i].profit
		for j := i - 1; j >= 0; j-- {
			if arr[j].endTime <= arr[i].startTime {
				dp[i] = max(dp[i], dp[j]+arr[i].profit)
				break
			}
		}
		dp[i] = max(dp[i], maxValue)
		maxValue = max(maxValue, dp[i])
	}
	return dp[n-1]
}

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

# 2
type Node struct {
	startTime int
	endTime   int
	profit    int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(startTime)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			startTime: startTime[i],
			endTime:   endTime[i],
			profit:    profit[i],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].endTime == arr[j].endTime {
			return arr[i].startTime < arr[j].startTime
		}
		return arr[i].endTime < arr[j].endTime
	})
	for i := 1; i < n; i++ {
		target := sort.Search(i, func(j int) bool {
			return arr[j].endTime > arr[i].startTime
		})
		if target == 0 {
			arr[i].profit = max(arr[i].profit, arr[i-1].profit)
		} else {
			arr[i].profit = max(arr[i].profit+arr[target-1].profit, arr[i-1].profit)
		}
	}
	return arr[n-1].profit
}

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

# 3
type Node struct {
	startTime int
	endTime   int
	profit    int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(startTime)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			startTime: startTime[i],
			endTime:   endTime[i],
			profit:    profit[i],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].endTime == arr[j].endTime {
			return arr[i].startTime < arr[j].startTime
		}
		return arr[i].endTime < arr[j].endTime
	})
	dp := make([]int, n)
	dp[0] = arr[0].profit
	for i := 1; i < n; i++ {
		dp[i] = dp[i-1] 
		dp[i] = max(dp[i], arr[i].profit)
		for j := i - 1; j >= 0; j-- {
			if arr[j].endTime <= arr[i].startTime {
				dp[i] = max(dp[i], dp[j]+arr[i].profit) 
				break
			}
		}
	}
	return dp[n-1]
}

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

# 4
type Node struct {
	startTime int
	endTime   int
	profit    int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(startTime)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			startTime: startTime[i],
			endTime:   endTime[i],
			profit:    profit[i],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].endTime == arr[j].endTime {
			return arr[i].startTime < arr[j].startTime
		}
		return arr[i].endTime < arr[j].endTime
	})
	dp := make([]int, n)
	dp[0] = arr[0].profit
	for i := 1; i < n; i++ {
		left, right := 0, i-1
		for left < right {
			mid := left + (right-left)/2
			if arr[mid+1].endTime <= arr[i].startTime {
				left = mid + 1
			} else {
				right = mid
			}
		}
		if arr[left].endTime <= arr[i].startTime {
			dp[i] = max(dp[i-1], dp[left]+arr[i].profit)
		} else {
			dp[i] = max(dp[i-1], arr[i].profit)
		}
	}
	return dp[n-1]
}

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

1255.得分最高的单词集合(3)

• 题目

你将会得到一份单词表words，一个字母表letters（可能会有重复字母），以及每个字母对应的得分情况表score。
请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：
能够由letters里的字母拼写出的任意属于 words单词子集中，分数最高的单词集合的得分。
单词拼写游戏的规则概述如下：
玩家需要用字母表letters 里的字母来拼写单词表words中的单词。
可以只使用字母表letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a','b','c', ... ,'z' 对应的得分分别为 score[0], score[1],...,score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。
示例 1：输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], 
score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。
示例 2：输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], 
score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10] 输出：27
解释：字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。
示例 3：输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"],
score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0] 输出：0
解释：字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。
提示：1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length ==26
0 <= score[i] <= 10
words[i]和letters[i]只包含小写的英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	状态压缩	O(2^n)	O(1)
02	回溯	O(n*2^n)	O(n)
03	递归	O(n*2^n)	O(n)

func maxScoreWords(words []string, letters []byte, score []int) int {
	count := [26]int{}
	for i := 0; i < len(letters); i++ {
		count[int(letters[i]-'a')]++ // 统计字符出现的次数
	}
	n := len(words)
	total := 1 << n // 总状态数
	res := 0
	for i := 0; i < total; i++ { // 枚举所有状态
		arr := getStatus(words, i)                  // 统计每种状态所需字符个数
		res = max(res, getScore(score, count, arr)) // 计算得分
	}
	return res
}

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

// 统计该状态每个字符多少个
func getStatus(words []string, status int) [26]int {
	arr := [26]int{}
	for i := 0; i < len(words); i++ {
		if status&(1<<i) > 0 {
			for j := 0; j < len(words[i]); j++ {
				arr[int(words[i][j]-'a')]++
			}
		}
	}
	return arr
}

func getScore(score []int, count, arr [26]int) int {
	res := 0
	for i := 0; i < 26; i++ {
		if count[i] < arr[i] {
			return 0
		}
		res = res + score[i]*arr[i]
	}
	return res
}

# 2
var res int
var count [26]int

func maxScoreWords(words []string, letters []byte, score []int) int {
	res = 0
	count = [26]int{}
	for i := 0; i < len(letters); i++ {
		count[int(letters[i]-'a')]++ // 统计字符出现的次数
	}
	dfs(words, score, 0, [26]int{})
	return res
}

func dfs(words []string, score []int, index int, arr [26]int) {
	sum := 0
	for i := 0; i < 26; i++ {
		if arr[i] > count[i] {
			return
		}
		sum = sum + arr[i]*score[i]
	}
	res = max(res, sum)
	for i := index; i < len(words); i++ {
		for j := 0; j < len(words[i]); j++ {
			arr[int(words[i][j]-'a')]++
		}
		dfs(words, score, i+1, arr)
		for j := 0; j < len(words[i]); j++ {
			arr[int(words[i][j]-'a')]--
		}
	}
}

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

# 3
var res int
var count [26]int

func maxScoreWords(words []string, letters []byte, score []int) int {
	res = 0
	count = [26]int{}
	for i := 0; i < len(letters); i++ {
		count[int(letters[i]-'a')]++ // 统计字符出现的次数
	}
	dfs(words, score, 0, [26]int{})
	return res
}

func dfs(words []string, score []int, index int, arr [26]int) {
	sum := 0
	for i := 0; i < 26; i++ {
		if arr[i] > count[i] {
			return
		}
		sum = sum + arr[i]*score[i]
	}
	res = max(res, sum)
	if index >= len(words) {
		return
	}
	dfs(words, score, index+1, arr) // 不选
	for j := 0; j < len(words[index]); j++ {
		arr[int(words[index][j]-'a')]++
	}
	dfs(words, score, index+1, arr) // 选
}

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

1269.停在原地的方案数(2)

• 题目

有一个长度为arrLen的数组，开始有一个指针在索引0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数steps 和arrLen ，请你计算并返回：在恰好执行steps次操作以后，指针仍然指向索引0 处的方案数。
由于答案可能会很大，请返回方案数 模10^9 + 7 后的结果。
示例 1：输入：steps = 3, arrLen = 2 输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
示例 2：输入：steps = 2, arrLen = 4 输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
示例 3：输入：steps = 4, arrLen = 2 输出：8
提示：1 <= steps <= 500
1 <= arrLen<= 10^6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n^2)
02	动态规划	O(n^2)	O(n)

var mod = 1000000007

func numWays(steps int, arrLen int) int {
	length := min(arrLen-1, steps)
	dp := make([][]int, steps+1) // dp[i][j] => 在i步操作之后，指针位于下标j的方案数
	for i := 0; i <= steps; i++ {
		dp[i] = make([]int, length+1)
	}
	dp[0][0] = 1
	for i := 1; i <= steps; i++ {
		for j := 0; j <= length; j++ {
			dp[i][j] = dp[i-1][j] // 不动
			if j >= 1 {
				dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod // 右移
			}
			if j <= length-1 {
				dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod // 左移
			}
		}
	}
	return dp[steps][0]
}

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

# 2
var mod = 1000000007

func numWays(steps int, arrLen int) int {
	length := min(arrLen-1, steps)
	dp := make([]int, length+1) // dp[j] => 指针位于下标j的方案数
	dp[0] = 1
	for i := 1; i <= steps; i++ {
		temp := make([]int, length+1)
		for j := 0; j <= length; j++ {
			temp[j] = dp[j] // 不动
			if j >= 1 {
				temp[j] = (temp[j] + dp[j-1]) % mod // 右移
			}
			if j <= length-1 {
				temp[j] = (temp[j] + dp[j+1]) % mod // 左移
			}
		}
		dp = temp
	}
	return dp[0]
}

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

1289.下降路径最小和II(3)

• 题目

给你一个整数方阵arr，定义「非零偏移下降路径」为：
从arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。
示例 1：输入：arr = [[1,2,3],[4,5,6],[7,8,9]] 输出：13
解释：所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是[1,5,7] ，所以答案是13 。
提示：1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(1)
02	动态规划	O(n^3)	O(n^2)
03	排序遍历	O(n^2log(n))	O(n)

func minFallingPathSum(arr [][]int) int {
	n := len(arr)
	firstMin, secondMin := 0, 0
	firstIndex := -1
	for i := 0; i < n; i++ {
		fMin, sMin := math.MaxInt32, math.MaxInt32
		fIndex := -1
		for j := 0; j < n; j++ {
			sum := 0
			if firstIndex != j { // 不等于最小值所在行，就+最小值
				sum = firstMin + arr[i][j]
			} else { // 等于最小值所在行，就+次小值
				sum = secondMin + arr[i][j]
			}
			if sum < fMin {
				sMin = fMin
				fMin = sum
				fIndex = j
			} else if sum < sMin {
				sMin = sum
			}
		}
		firstMin = fMin
		secondMin = sMin
		firstIndex = fIndex
	}
	return firstMin
}

# 2
func minFallingPathSum(arr [][]int) int {
	n := len(arr)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for j := 0; j < n; j++ {
		dp[0][j] = arr[0][j]
	}
	for i := 1; i < n; i++ {
		for j := 0; j < n; j++ {
			dp[i][j] = math.MaxInt32
			for k := 0; k < n; k++ {
				if j != k {
					dp[i][j] = min(dp[i][j], dp[i-1][k]+arr[i][j])
				}
			}
		}
	}
	res := math.MaxInt32
	for j := 0; j < n; j++ {
		res = min(res, dp[n-1][j])
	}
	return res
}

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

# 3
func minFallingPathSum(arr [][]int) int {
	n := len(arr)
	for i := 1; i < n; i++ {
		temp := make([][2]int, n)
		for j := 0; j < n; j++ {
			temp[j] = [2]int{arr[i-1][j], j}
		}
		sort.Slice(temp, func(i, j int) bool {
			return temp[i][0] < temp[j][0]
		})
		for j := 0; j < n; j++ {
			if temp[0][1] != j {
				arr[i][j] = arr[i][j] + temp[0][0]
			} else {
				arr[i][j] = arr[i][j] + temp[1][0]
			}
		}
	}
	res := math.MaxInt32
	for j := 0; j < n; j++ {
		res = min(res, arr[n-1][j])
	}
	return res
}

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

1293.网格中的最短路径(1)

• 题目

给你一个m * n的网格，其中每个单元格不是0（空）就是1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。
如果找不到这样的路径，则返回 -1。
示例 1：输入： grid = 
[[0,0,0],
[1,1,0],
 [0,0,0],
[0,1,1],
 [0,0,0]], 
k = 1
输出：6
解释：不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
示例 2：输入：grid = 
[[0,1,1],
[1,1,1],
[1,0,0]], 
k = 1
输出：-1
解释：我们至少需要消除两个障碍才能找到这样的路径。
提示：grid.length== m
grid[0].length== n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

解题思路

No.	思路	时间复杂度	空间复杂度
01	广度优先搜索	O(n^3)	O(n^3)

var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}

func shortestPath(grid [][]int, k int) int {
	n, m := len(grid), len(grid[0])
	if n == 1 && m == 1 {
		return 0
	}
	k = min(k, n+m-3) // 缩小k的范围
	visited := make([][][]bool, n)
	for i := 0; i < n; i++ {
		visited[i] = make([][]bool, m)
		for j := 0; j < m; j++ {
			visited[i][j] = make([]bool, k+1)
		}
	}
	count := 1
	queue := make([][3]int, 0)
	queue = append(queue, [3]int{0, 0, k})
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			a, b, c := queue[i][0], queue[i][1], queue[i][2]
			for j := 0; j < 4; j++ {
				x, y := a+dx[j], b+dy[j]
				if 0 <= x && x < n && 0 <= y && y < m {
					if grid[x][y] == 0 && visited[x][y][c] == false {
						if x == n-1 && y == m-1 { // 走到终点
							return count
						}
						queue = append(queue, [3]int{x, y, c})
						visited[x][y][c] = true
					} else if grid[x][y] == 1 && c > 0 && visited[x][y][c-1] == false {
						queue = append(queue, [3]int{x, y, c - 1})
						visited[x][y][c-1] = true
					}
				}
			}
		}
		queue = queue[length:]
		count++
	}
	return -1
}

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

1298.你能从盒子里获得的最大糖果数

题目

给你n个盒子，每个盒子的格式为[status, candies, keys, containedBoxes]，其中：
状态字status[i]：整数，如果box[i]是开的，那么是 1，否则是 0。
糖果数candies[i]: 整数，表示box[i] 中糖果的数目。
钥匙keys[i]：数组，表示你打开box[i]后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。
内含的盒子containedBoxes[i]：整数，表示放在box[i]里的盒子所对应的下标。
给你一个initialBoxes 数组，表示你现在得到的盒子，你可以获得里面的糖果，
也可以用盒子里的钥匙打开新的盒子，还可以继续探索从这个盒子里找到的其他盒子。
请你按照上述规则，返回可以获得糖果的 最大数目。
示例 1：输入：status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], 
containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
输出：16
解释：一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。
盒子 1 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。
在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。
你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。
示例 2：输入：status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], 
keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
输出：6
解释：你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。
打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 6 个。
示例 3：输入：status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], 
containedBoxes = [[],[],[]], initialBoxes = [1] 输出：1
示例 4：输入：status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = [] 输出：0
示例 5：输入：status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], 
containedBoxes = [[],[],[]], initialBoxes = [2,1,0] 输出：7
提示：1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] 要么是0要么是1 。
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
keys[i]中的值都是互不相同的。
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
containedBoxes[i]中的值都是互不相同的。
每个盒子最多被一个盒子包含。
0 <= initialBoxes.length<= status.length
0 <= initialBoxes[i] < status.length

解题思路

No.	思路	时间复杂度	空间复杂度
01	广度优先搜索	O(n^3)	O(n^3)