1001-1100-Easy

1002.查找常用字符(2)

• 题目

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。
例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：输入：["bella","label","roller"] 输出：["e","l","l"]
示例 2：输入：["cool","lock","cook"] 输出：["c","o"]
提示：
    1 <= A.length <= 100
    1 <= A[i].length <= 100
    A[i][j] 是小写字母

• 解题思路

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

func commonChars(A []string) []string {
	arr := [26]int{}
	for _, v := range A[0] {
		arr[v-'a']++
	}
	for i := 1; i < len(A); i++ {
		temp := [26]int{}
		for _, v := range A[i] {
			temp[v-'a']++
		}
		for i := 0; i < len(arr); i++ {
			arr[i] = min(arr[i], temp[i])
		}
	}
	res := make([]string, 0)
	for i := 0; i < len(arr); i++ {
		if arr[i] > 0 {
			for j := 0; j < arr[i]; j++ {
				res = append(res, string('a'+i))
			}
		}
	}
	return res
}

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

#
func commonChars(A []string) []string {
	arr := make([][26]int, len(A))
	for i := 0; i < len(A); i++ {
		for j := 0; j < len(A[i]); j++ {
			arr[i][A[i][j]-'a']++
		}
	}
	res := make([]string, 0)
	for j := 0; j < 26; j++ {
		minValue := arr[0][j]
		for i := 1; i < len(arr); i++ {
			minValue = min(minValue, arr[i][j])
		}
		for minValue > 0 {
			res = append(res, string(j+'a'))
			minValue--
		}
	}
	return res
}

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

1005.K次取反后最大化的数组和(4)

• 题目

给定一个整数数组 A，我们只能用以下方法修改该数组：
我们选择某个个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。
（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：输入：A = [4,2,3], K = 1 输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：输入：A = [3,-1,0,2], K = 3 输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：输入：A = [2,-3,-1,5,-4], K = 2 输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
    1 <= A.length <= 10000
    1 <= K <= 10000
    -100 <= A[i] <= 100

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+贪心	O(nlog(n))	O(1)
02	排序+贪心	O(nlog(n))	O(1)
03	数组辅助	O(n)	O(1)
04	遍历-找最小	O(n^2)	O(1)

func largestSumAfterKNegations(A []int, K int) int {
	sort.Ints(A)
	i := 0
	for i < len(A) && K > 0 {
		if A[i] < 0 {
			A[i] = -A[i]
			i++
			K--
		} else {
			break
		}
	}
	sort.Ints(A)
	if K%2 == 1 {
		A[0] = -A[0]
	}
	return sum(A)
}

func sum(A []int) int {
	res := 0
	for i := 0; i < len(A); i++ {
		res = res + A[i]
	}
	return res
}

# 2
func largestSumAfterKNegations(A []int, K int) int {
	sort.Ints(A)
	i := 0
	for i < len(A)-1 && K > 0 {
		A[i] = -A[i]
		if A[i] > 0 && A[i] > A[i+1] {
			i++
		}
		K--
	}
	return sum(A)
}

func sum(A []int) int {
	res := 0
	for i := 0; i < len(A); i++ {
		res = res + A[i]
	}
	return res
}

# 3
func largestSumAfterKNegations(A []int, K int) int {
	arr := make([]int, 201)
	for i := 0; i < len(A); i++ {
		arr[A[i]+100]++
	}
	i := 0
	for K > 0 {
		for arr[i] == 0 {
			i++
		}
		if i > 100 {
			break
		}
		arr[i]--
		arr[200-i]++
		K--
	}
	if K%2 == 1 && i != 100 {
		for j := i; j < len(arr); j++ {
			if arr[j] > 0 {
				arr[j]--
				arr[200-j]++
				break
			}
		}
	}
	res := 0
	for i := 0; i < len(arr); i++ {
		res = res + (i-100)*arr[i]
	}
	return res
}

# 4
func largestSumAfterKNegations(A []int, K int) int {
	for K > 0 {
		minIndex, minValue := findMin(A)
		if minValue > 0 {
			break
		}
		A[minIndex] = -A[minIndex]
		K--
	}
	if K%2 == 1 {
		minIndex, _ := findMin(A)
		A[minIndex] = -A[minIndex]
	}
	res := 0
	for i := 0; i < len(A); i++ {
		res = res + A[i]
	}
	return res
}

func findMin(A []int) (int, int) {
	res := A[0]
	index := 0
	for i := 1; i < len(A); i++ {
		if res > A[i] {
			res = A[i]
			index = i
		}
	}
	return index, res
}

1009.十进制整数的反码(3)

• 题目

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，
依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。
示例 1：输入：5 输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
示例 2：输入：7 输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
示例 3：输入：10 输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
提示：
    0 <= N < 10^9
    本题与 476：https://leetcode.cn/problems/number-complement/ 相同

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	位运算	O(log(n))	O(1)
02	位运算	O(log(n))	O(1)
03	遍历	O(log(n))	O(1)

/*
101+010=1000=111+1
*/
func bitwiseComplement(N int) int {
	temp := 2
	for N >= temp {
		temp = temp << 1
	}
	return temp - 1 - N
}

#
/*
101^111=010
*/
func bitwiseComplement(N int) int {
	temp := N
	res := 1
	for temp > 1 {
		temp = temp >> 1
		res = res << 1
		res++
	}
	return res ^ N
}

#
func bitwiseComplement(N int) int {
	res := 0
	if N == 0 {
		return 1
	}
	if N == 1 {
		return 0
	}
	exp := 1
	for N > 0 {
		if N%2 == 0 {
			res = res + exp
		}
		exp = exp * 2
		N = N / 2
	}
	return res
}

1010.总持续时间可被60整除的歌曲(2)

• 题目

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。
形式上，我们希望索引的数字 i 和 j 满足  i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：输入：[30,20,150,100,40] 输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：输入：[60,60,60] 输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
提示：
    1 <= time.length <= 60000
    1 <= time[i] <= 500

• 解题思路

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

func numPairsDivisibleBy60(time []int) int {
	m := make(map[int]int)
	for i := 0; i < len(time); i++ {
		m[time[i]%60]++
	}
	res := 0
	for key, value := range m {
		if key == 0 || key == 30 {
			res = res + (value-1)*value/2
		} else {
			if v, ok := m[60-key]; ok && v > 0 {
				res = res + v*value
				m[key] = 0
				m[60-key] = 0
			}
		}
	}
	return res
}

#
func numPairsDivisibleBy60(time []int) int {
	res := 0
	arr := make([]int,60)
	for i := range time{
		if time[i] % 60 == 0{
			res = res + arr[0]
		}else {
			res = res + arr[60-time[i]%60]
		}
		arr[time[i]%60]++
	}
	return res
}

1013.将数组分成和相等的三个部分(2)

• 题目

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] 
== A[i+1] + A[i+2] + ... + A[j-1] 
== A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
示例 1：输入：[0,2,1,-6,6,-7,9,1,2,0,1] 输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：输入：[0,2,1,-6,6,7,9,-1,2,0,1] 输出：false
示例 3：输入：[3,3,6,5,-2,2,5,1,-9,4] 输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示：
    3 <= A.length <= 50000
    -10^4 <= A[i] <= 10^4

• 解题思路

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

func canThreePartsEqualSum(A []int) bool {
	length := len(A)
	if length < 3 {
		return false
	}
	sum := 0
	for i := 0; i < length; i++ {
		sum = sum + A[i]
	}
	if sum%3 != 0 {
		return false
	}
	target := sum / 3
	count := 0
	temp := 0
	for i := 0; i < len(A); i++ {
		temp = temp + A[i]
		if temp == target {
			temp = 0
			count++
		}
	}
	if count >= 3 {
		return true
	}
	return false
}

#
func canThreePartsEqualSum(A []int) bool {
	length := len(A)
	if length < 3 {
		return false
	}
	sum := 0
	for i := 0; i < length; i++ {
		sum = sum + A[i]
	}
	if sum%3 != 0 {
		return false
	}
	target := sum / 3
	left, right := 1, len(A)-2
	leftValue, rightValue := A[0], A[len(A)-1]
	for left < right {
		for left < right && leftValue != target {
			leftValue = leftValue + A[left]
			left++
		}
		for left < right && rightValue != target {
			rightValue = rightValue + A[right]
			right--
		}
		if leftValue == target && rightValue == target {
			return true
		}
	}
	return false
}

1018.可被5整除的二进制前缀(1)

• 题目

给定由若干 0 和 1 组成的数组 A。我们定义 N_i：
从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
示例 1：输入：[0,1,1] 输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
示例 2：输入：[1,1,1] 输出：[false,false,false]
示例 3：输入：[0,1,1,1,1,1] 输出：[true,false,false,false,true,false]
示例 4：输入：[1,1,1,0,1] 输出：[false,false,false,false,false]
提示：
    1 <= A.length <= 30000
    A[i] 为 0 或 1

• 解题思路

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

func prefixesDivBy5(A []int) []bool {
	res := make([]bool, len(A))
	temp := 0
	for i := 0; i < len(A); i++ {
		temp = (temp*2 + A[i]) % 5
		if temp == 0 {
			res[i] = true
		}
	}
	return res
}

1021.删除最外层的括号(3)

• 题目

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），
其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，
使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：输入："(()())(())" 输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：输入："(()())(())(()(()))" 输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：输入："()()" 输出：""
解释： 输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
提示：
    S.length <= 10000
    S[i] 为 "(" 或 ")"
    S 是一个有效括号字符串

• 解题思路

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

func removeOuterParentheses(S string) string {
	if len(S) == 0 {
		return ""
	}
	res := ""
	stack := make([]byte, 0)
	stack = append(stack, S[0])
	last := 0
	for i := 1; i < len(S); i++ {
		if len(stack) > 0 && S[i] == ')' && stack[len(stack)-1] == '(' {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				res = res + S[last+1:i]
				last = i + 1
			}
		} else {
			stack = append(stack, S[i])
		}
	}
	return res
}

#
func removeOuterParentheses(S string) string {
	res := ""
	count := 0
	last := 0
	for i := 0; i < len(S); i++ {
		if S[i] == '(' {
			count++
		} else {
			count--
		}
		if count == 1 && S[i] == '(' {
			last = i
		}
		if count == 0 {
			res = res + S[last+1:i]
		}
	}
	return res
}

#
func removeOuterParentheses(S string) string {
	if len(S) == 0 {
		return ""
	}
	res := ""
	stack := make([]byte, 0)
	for i := 0; i < len(S); i++ {
		if S[i] == ')' {
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 {
			res = res + string(S[i])
		}
		if S[i] == '(' {
			stack = append(stack, S[i])
		}
	}
	return res
}

1022.从根到叶的二进制数之和(2)

• 题目

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
以 10^9 + 7 为模，返回这些数字之和。
示例：输入：[1,0,1,0,1,0,1] 输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
提示：
    树中的结点数介于 1 和 1000 之间。
    node.val 为 0 或 1 。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

var res int

func sumRootToLeaf(root *TreeNode) int {
	res = 0
	dfs(root, 0)
	return res
}

func dfs(root *TreeNode, sum int) {
	if root == nil {
		return
	}
	sum = sum*2 + root.Val
	if root.Left == nil && root.Right == nil {
		res = (res + sum) % 1000000007
	}
	dfs(root.Left, sum)
	dfs(root.Right, sum)
}

#
type Node struct {
	node *TreeNode
	sum  int
}

func sumRootToLeaf(root *TreeNode) int {
	res := 0
	stack := make([]Node, 0)
	stack = append(stack, Node{
		node: root,
		sum:  0,
	})
	for len(stack) > 0 {
		node, sum := stack[len(stack)-1].node, stack[len(stack)-1].sum
		stack = stack[:len(stack)-1]
		sum = sum*2 + node.Val
		if node.Left == nil && node.Right == nil {
			res = (res + sum) % 1000000007
		}
		if node.Left != nil {
			stack = append(stack, Node{
				node: node.Left,
				sum:  sum,
			})
		}
		if node.Right != nil {
			stack = append(stack, Node{
				node: node.Right,
				sum:  sum,
			})
		}
	}
	return res
}

1025.除数博弈(2)

• 题目

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
    选出任一 x，满足 0 < x < N 且 N % x == 0 。
    用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：输入：2 输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：输入：3 输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
提示：
    1 <= N <= 1000

• 解题思路

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

func divisorGame(N int) bool {
	return N % 2 == 0
}

#
func divisorGame(N int) bool {
	dp := make([]bool, N+1)
	dp[1] = false // 1的时候爱丽丝没有选择，失败
	for i := 2; i <= N; i++ {
		for j := 1; j < i; j++ {
			if i%j == 0 && dp[i-j] == false {
				dp[i] = true
			}
		}
	}
	return dp[N]
}

1029.两地调度(2)

• 题目

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
示例：输入：[[10,20],[30,200],[400,50],[30,20]] 输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
    1 <= costs.length <= 100
    costs.length 为偶数
    1 <= costs[i][0], costs[i][1] <= 1000

• 解题思路

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

func twoCitySchedCost(costs [][]int) int {
	sort.Slice(costs, func(i, j int) bool {
		return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
	})
	res := 0
	for i := 0; i < len(costs); i++ {
		if i < len(costs)/2 {
			res = res + costs[i][0]
		} else {
			res = res + costs[i][1]
		}
	}
	return res
}

#
func twoCitySchedCost(costs [][]int) int {
	n := len(costs)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
		for j := i + 1; j <= n; j++ {
			// dp[i][j]表示i个人飞往A市的次数为j的最低费用
			// 无效掉j>i的情况，比如i=3, j=4
			// 因为不存在3个人飞往A市次数为4次的情况
			dp[i][j] = 100000000
		}
	}
	for i := 1; i <= n; i++ {
		dp[i][0] = dp[i-1][0] + costs[i-1][1]
		for j := 1; j <= i; j++ {
			// dp[i][j]表示i个人飞往A市的次数为j的最低费用
			// 其中i-1个人飞往A市的次数为j+当前飞往B市的费用
			// 其中i-1个人飞往A市的次数为j-1+当前飞往A市的费用
			dp[i][j] = min(dp[i-1][j]+costs[i-1][1], dp[i-1][j-1]+costs[i-1][0])
		}
	}
	return dp[n][n/2]
}

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

1030.距离顺序排列矩阵单元格(3)

• 题目

给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，
其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。
（你可以按任何满足此条件的顺序返回答案。）
示例 1：输入：R = 1, C = 2, r0 = 0, c0 = 0 输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：输入：R = 2, C = 2, r0 = 0, c0 = 1 输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：输入：R = 2, C = 3, r0 = 1, c0 = 2 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
提示：
    1 <= R <= 100
    1 <= C <= 100
    0 <= r0 < R
    0 <= c0 < C

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	广度优先搜索	O(n^2)	O(n^2)
02	排序	O(nlog(n))	O(n^2)
03	哈希辅助	O(n^2)	I

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

func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int {
	res := make([][]int, 0)
	visited := make([][]bool, R)
	for i := 0; i < R; i++ {
		visited[i] = make([]bool, C)
	}
	list := make([][]int, 0)
	list = append(list, []int{r0, c0})
	visited[r0][c0] = true
	for len(list) > 0 {
		x1, y1 := list[0][0], list[0][1]
		res = append(res, []int{x1, y1})
		list = list[1:]
		for i := 0; i < 4; i++ {
			x := x1 + dx[i]
			y := y1 + dy[i]
			if (0 <= x && x < R && 0 <= y && y < C) && visited[x][y] == false {
				visited[x][y] = true
				list = append(list, []int{x, y})
			}
		}
	}
	return res
}

#
func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int {
	res := make([][]int, 0)
	for i := 0; i < R; i++ {
		for j := 0; j < C; j++ {
			res = append(res, []int{i, j})
		}
	}
	sort.Slice(res, func(i, j int) bool {
		return abs(res[i][0], r0)+abs(res[i][1], c0) <
			abs(res[j][0], r0)+abs(res[j][1], c0)
	})
	return res
}

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

#
func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int {
	res := make([][]int, 0)
	m := make(map[int][][]int)
	max := 0
	for i := 0; i < R; i++ {
		for j := 0; j < C; j++ {
			length := abs(i, r0) + abs(j, c0)
			m[length] = append(m[length], []int{i, j})
			if length > max {
				max = length
			}
		}
	}
	for i := 0; i <= max; i++ {
		for j := 0; j < len(m[i]); j++ {
			res = append(res, m[i][j])
		}
	}
	return res
}

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

1033.移动石子直到连续(2)

• 题目

三枚石子放置在数轴上，位置分别为 a，b，c。
每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。
从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：
answer = [minimum_moves, maximum_moves]
示例 1：输入：a = 1, b = 2, c = 5 输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。
示例 2：输入：a = 4, b = 3, c = 2 输出：[0, 0]
解释：我们无法进行任何移动。
提示：
    1 <= a <= 100
    1 <= b <= 100
    1 <= c <= 100
    a != b, b != c, c != a

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	找规律	O(1)	O(1)
02	找规律	O(1)	O(1)

func numMovesStones(a int, b int, c int) []int {
	arr := []int{a, b, c}
	sort.Ints(arr)
	a, b, c = arr[0], arr[1], arr[2]
	if a < b && b < c {
		if b-a == 1 && c-b == 1 {
			return []int{0, 0}
		} else if b-a > 2 && c-b > 2 {
			return []int{2, c - a - 2}
		} else {
			return []int{1, c - a - 2}
		}
	}
	return []int{0, 0}
}

#
func numMovesStones(a int, b int, c int) []int {
	if a > b {
		a, b = b, a
	}
	if b > c {
		b, c = c, b
	}
	if a > b {
		a, b = b, a
	}
	if a < b && b < c {
		if b-a == 1 && c-b == 1 {
			return []int{0, 0}
		} else if b-a > 2 && c-b > 2 {
			return []int{2, c - a - 2}
		} else {
			return []int{1, c - a - 2}
		}
	}
	return []int{0, 0}
}

1037.有效的回旋镖(3)

• 题目

回旋镖定义为一组三个点，这些点各不相同且不在一条直线上。
给出平面上三个点组成的列表，判断这些点是否可以构成回旋镖。
示例 1：输入：[[1,1],[2,3],[3,2]] 输出：true
示例 2：输入：[[1,1],[2,2],[3,3]] 输出：false
提示：
    points.length == 3
    points[i].length == 2
    0 <= points[i][j] <= 100

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	斜率公式	O(1)	O(1)
02	鞋带公式	O(1)	O(1)
03	判断是否组成三角形	O(1)	O(1)

// k1=(y1-y0)/(x1-x0) = k2 = (y2-y1)/(x2-x1)
// (x1-x0)*(y2-y1) = (x2-x1)*(y1-y0)
func isBoomerang(points [][]int) bool {
	return (points[1][0]-points[0][0])*(points[2][1]-points[1][1]) !=
		(points[2][0]-points[1][0])*(points[1][1]-points[0][1])
}

#
// 鞋带公式
// S=|(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1)|/2
// S!=0组成三角形
func isBoomerang(points [][]int) bool {
	return points[0][0]*points[1][1]+points[1][0]*points[2][1]+points[2][0]*points[0][1] !=
		points[0][1]*points[1][0]+points[1][1]*points[2][0]+points[2][1]*points[0][0]
}

#
func isBoomerang(points [][]int) bool {
	side1 := side(points[0], points[1])
	side2 := side(points[1], points[2])
	side3 := side(points[0], points[2])
	return side1+side2 > side3 &&
		side2+side3 > side1 &&
		side1+side3 > side2
}

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))
}

1039.多边形三角剖分的最低得分(3)

• 题目

给定N，想象一个凸N边多边形，其顶点按顺时针顺序依次标记为A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，
三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1：输入：[1,2,3] 输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：输入：[3,7,4,5] 输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
示例 3：输入：[1,3,1,4,1,5] 输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
提示：3 <= A.length <= 50
1 <= A[i] <= 100

• 解题思路

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

func minScoreTriangulation(values []int) int {
	n := len(values)
	dp := make([][]int, n) // dp[i][j]表示从i到j序列的最低分
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	// 点0和n-1，因为总有某个点j与点0和n-1构成三角形
	// 这样就把1个多边形，转换为2个或者3个区域
	// dp[0][n-1] = min(dp[0][j] + dp[j][n-1] + A[0]*A[k]*A[n-1])
	for i := n - 3; i >= 0; i-- {
		for j := i + 2; j < n; j++ {
			for k := i + 1; k < j; k++ {
				sum := dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]
				if dp[i][j] == 0 {
					dp[i][j] = sum
				} else {
					dp[i][j] = min(dp[i][j], sum)
				}
			}
		}
	}
	return dp[0][n-1]
}

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

# 2
func minScoreTriangulation(values []int) int {
	n := len(values)
	dp := make([][]int, n) // dp[i][j]表示从i到j序列的最低分
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	// 点0和n-1，因为总有某个点j与点0和n-1构成三角形
	// 这样就把1个多边形，转换为2个或者3个区域
	// dp[0][n-1] = min(dp[0][j] + dp[j][n-1] + A[0]*A[k]*A[n-1])
	for j := 2; j < n; j++ {
		for i := j - 2; i >= 0; i-- {
			for k := i + 1; k < j; k++ {
				sum := dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]
				if dp[i][j] == 0 {
					dp[i][j] = sum
				} else {
					dp[i][j] = min(dp[i][j], sum)
				}
			}
		}
	}
	return dp[0][n-1]
}

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

# 3
var dp [][]int

func minScoreTriangulation(values []int) int {
	n := len(values)
	dp = make([][]int, n) // dp[i][j]表示从i到j序列的最低分
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	return dfs(values, 0, n-1)
}

func dfs(values []int, i, j int) int {
	if i+1 == j {
		return 0
	}
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	res := math.MaxInt32
	for k := i + 1; k < j; k++ {
		sum := dfs(values, i, k) + dfs(values, k, j) + values[i]*values[k]*values[j]
		res = min(res, sum)
	}
	dp[i][j] = res
	return res
}

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

1042.不邻接植花(1)

• 题目

有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外，没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。
花的种类用  1, 2, 3, 4 表示。保证存在答案。
示例 1：输入：N = 3, paths = [[1,2],[2,3],[3,1]] 输出：[1,2,3]
示例 2：输入：N = 4, paths = [[1,2],[3,4]] 输出：[1,2,1,2]
示例 3：输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] 输出：[1,2,3,4]
提示：
    1 <= N <= 10000
    0 <= paths.size <= 20000
    不存在花园有 4 条或者更多路径可以进入或离开。
    保证存在答案。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	邻接表	O(n^2)	O(n)

func gardenNoAdj(N int, paths [][]int) []int {
	res := make([]int, N+1)
	arr := make([][]int, N+1)
	for i := 0; i < len(paths); i++ {
		arr[paths[i][0]] = append(arr[paths[i][0]], paths[i][1])
		arr[paths[i][1]] = append(arr[paths[i][1]], paths[i][0])
	}
	for i := 1; i <= N; i++ {
		m := map[int]int{
			1: 1,
			2: 2,
			3: 3,
			4: 4,
		}
		for j := 0; j < len(arr[i]); j++ {
			if res[arr[i][j]] > 0 {
				delete(m, res[arr[i][j]])
			}
		}
		for k := range m {
			res[i] = k
			break
		}
	}
	return res[1:]
}

1046.最后一块石头的重量(2)

• 题目

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。
那么粉碎的可能结果如下：
    如果 x == y，那么两块石头都会被完全粉碎；
    如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：输入：[2,7,4,1,8,1] 输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
    1 <= stones.length <= 30
    1 <= stones[i] <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	内置堆	O(nlog(n))	O(n)
02	排序	O(n^2*log(n))	O(1)

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

func lastStoneWeight(stones []int) int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < len(stones); i++ {
		heap.Push(&intHeap, stones[i])
	}
	for intHeap.Len() > 1 {
		a := heap.Pop(&intHeap).(int)
		b := heap.Pop(&intHeap).(int)
		if a > b {
			heap.Push(&intHeap, a-b)
		}
	}
	if intHeap.Len() > 0 {
		res := heap.Pop(&intHeap).(int)
		return res
	}
	return 0
}

#
func lastStoneWeight(stones []int) int {
	length := len(stones)
	if length == 1 {
		return stones[0]
	}
	sort.Ints(stones)
	for stones[length-2] != 0 {
		stones[length-1] = stones[length-1] - stones[length-2]
		stones[length-2] = 0
		sort.Ints(stones)
	}
	return stones[length-1]
}

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

• 题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：输入："abbaca" 输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
    1 <= S.length <= 20000
    S 仅由小写英文字母组成。

• 解题思路

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

func removeDuplicates(S string) string {
	stack := make([]int32, 0)
	for _, v := range S {
		stack = append(stack, v)
		for len(stack) > 1 && stack[len(stack)-1] == stack[len(stack)-2] {
			stack = stack[:len(stack)-2]
		}
	}
	return string(stack)
}

#
func removeDuplicates(S string) string {
	arr := []byte(S)
	for {
		flag := false
		for i := 0; i < len(arr)-1; i++ {
			if arr[i] == arr[i+1] {
				if i+2 != len(arr) {
					arr = append(arr[:i], arr[i+2:]...)
				} else {
					arr = arr[:i]
				}
				flag = true
				break
			}
		}
		if flag == false {
			break
		}
	}
	return string(arr)
}

1051.高度检查器(2)

• 题目

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。
注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。
示例：输入：heights = [1,1,4,2,1,3] 输出：3 
解释：当前数组：[1,1,4,2,1,3] 目标数组：[1,1,1,2,3,4]
在下标 2 处（从 0 开始计数）出现 4 vs 1 ，所以我们必须移动这名学生。
在下标 4 处（从 0 开始计数）出现 1 vs 3 ，所以我们必须移动这名学生。
在下标 5 处（从 0 开始计数）出现 3 vs 4 ，所以我们必须移动这名学生。
示例 2：输入：heights = [5,1,2,3,4] 输出：5
示例 3：输入：heights = [1,2,3,4,5] 输出：0
提示：
    1 <= heights.length <= 100
    1 <= heights[i] <= 100

• 解题思路

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

func heightChecker(heights []int) int {
	temp := make([]int, len(heights))
	copy(temp, heights)
	sort.Ints(temp)
	res := 0
	for i := 0; i < len(temp); i++ {
		if temp[i] != heights[i] {
			res++
		}
	}
	return res
}

#
func heightChecker(heights []int) int {
	arr := make([]int, 101)
	for i := 0; i < len(heights); i++ {
		arr[heights[i]]++
	}
	res := 0
	j := 0
	for i := 1; i <= 100; i++ {
		for arr[i] > 0 {
			if heights[j] != i {
				res++
			}
			arr[i]--
			j++
		}
	}
	return res
}

1071.字符串的最大公因子(2)

• 题目

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
示例 2：输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
示例 3：输入：str1 = "LEET", str2 = "CODE" 输出：""
提示：
    1 <= str1.length <= 1000
    1 <= str2.length <= 1000
    str1[i] 和 str2[i] 为大写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	辗转相除法	O(n)	O(n)
02	遍历	O(n^2)	O(n)

func gcdOfStrings(str1 string, str2 string) string {
	if str1+str2 != str2+str1 {
		return ""
	}
	if str1 > str2 {
		str1, str2 = str2, str1
	}
	return str1[:gcd(len(str2), len(str1))]
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

#
func gcdOfStrings(str1 string, str2 string) string {
	min := len(str1)
	if min > len(str2) {
		min = len(str2)
	}
	for i := len(str2); i >= 1; i-- {
		if len(str1)%i == 0 && len(str2)%i == 0 && str1[:i] == str2[:i] {
			a := strings.Repeat(str1[:i], len(str1)/i)
			b := strings.Repeat(str2[:i], len(str2)/i)
			if a == str1 && b == str2 {
				return str1[:i]
			}
		}
	}
	return ""
}

1078.Bigram 分词(1)

• 题目

给出第一个词 first 和第二个词 second，
考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，
其中 second 紧随 first 出现，third 紧随 second 出现。
对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。
示例 1：
输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
输出：["girl","student"]
示例 2：
输入：text = "we will we will rock you", first = "we", second = "will"
输出：["we","rock"]
提示：
    1 <= text.length <= 1000
    text 由一些用空格分隔的单词组成，每个单词都由小写英文字母组成
    1 <= first.length, second.length <= 10
    first 和 second 由小写英文字母组成

• 解题思路

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

func findOcurrences(text string, first string, second string) []string {
	arr := strings.Fields(text)
	res := make([]string, 0)
	for i := 0; i < len(arr)-2; i++ {
		if arr[i] == first && arr[i+1] == second {
			res = append(res, arr[i+2])
		}
	}
	return res
}

1089.复写零(3)

• 题目

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。
要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：输入：[1,0,2,3,0,4,5,0] 输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：输入：[1,2,3] 输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]
提示：
    1 <= arr.length <= 10000
    0 <= arr[i] <= 9

• 解题思路

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

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

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

#
func duplicateZeros(arr []int) {
	newArr := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			newArr = append(newArr, 0)
		}
		newArr = append(newArr, arr[i])
	}
	for i := 0; i < len(arr); i++ {
		arr[i] = newArr[i]
	}
}

1001-1100-Medium

1003.检查替换后的词是否有效(2)

• 题目

给定有效字符串"abc"。
对于任何有效的字符串 V，我们可以将 V 分成两个部分 X 和 Y，使得 X + Y（X 与 Y 连接）等于 V。
（X或 Y 可以为空。）那么，X + "abc" + Y 也同样是有效的。
例如，如果 S = "abc"，则有效字符串的示例是："abc"，"aabcbc"，"abcabc"，"abcabcababcc"。
无效字符串的示例是："abccba"，"ab"，"cababc"，"bac"。
如果给定字符串 S 有效，则返回 true；否则，返回 false。
示例 1：输入："aabcbc" 输出：true
解释：从有效字符串 "abc" 开始。
然后我们可以在 "a" 和 "bc" 之间插入另一个 "abc"，产生 "a" + "abc" + "bc"，即 "aabcbc"。
示例 2：输入："abcabcababcc" 输出：true
解释："abcabcabc" 是有效的，它可以视作在原串后连续插入 "abc"。
然后我们可以在最后一个字母之前插入 "abc"，产生 "abcabcab" + "abc" + "c"，即 "abcabcababcc"。
示例 3：输入："abccba" 输出：false
示例 4：输入："cababc" 输出：false
提示：1 <= S.length <= 20000
S[i] 为'a'、'b'、或'c'

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	栈辅助	O(n)	O(n)
02	内置函数	O(n)	O(n)

func isValid(s string) bool {
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		stack = append(stack, s[i])
		if len(stack) >= 3 && string(stack[len(stack)-3:]) == "abc" {
			stack = stack[:len(stack)-3]
		}
	}
	return len(stack) == 0
}

# 2
func isValid(s string) bool {
	for strings.Contains(s, "abc") {
		s = strings.ReplaceAll(s, "abc", "")
	}
	return s == ""
}

1004.最大连续1的个数III(2)

• 题目

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2输出：6
解释： [1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：1 <= A.length <= 20000
    0 <= K <= A.length
    A[i] 为 0 或 1 

• 解题思路

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

func longestOnes(A []int, K int) int {
	res := 0
	left, right := 0, 0
	for right < len(A) {
		if A[right] == 1 {
			right++
		} else {
			if K > 0 {
				right++
				K--
			} else {
				res = max(res, right-left)
				if A[left] == 0 {
					K++
				}
				left++
			}
		}
	}
	res = max(res, right-left)
	return res
}

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

# 2
func longestOnes(A []int, K int) int {
	res := 0
	left, right := 0, 0
	count := 0
	for right = 0; right < len(A); right++ {
		if A[right] == 0 {
			count++
		}
		for count > K {
			if A[left] == 0 {
				count--
			}
			left++
		}
		res = max(res, right-left+1)
	}
	return res
}

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

1006.笨阶乘(1)

• 题目

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。
例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。
相反，我们设计了一个笨阶乘 clumsy：
在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：
乘法(*)，除法(/)，加法(+)和减法(-)。
例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。
然而，这些运算仍然使用通常的算术运算顺序：
我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。
另外，我们使用的除法是地板除法（floor division），所以10 * 9 / 8等于11。这保证结果是一个整数。
实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。
示例 1：输入：4 输出：7
解释：7 = 4 * 3 / 2 + 1
示例 2：输入：10 输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
提示：1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

• 解题思路

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

func clumsy(N int) int {
	res := 0
	sum := 1
	for i := N; i > 0; i = i - 4 {
		if i == 1 {
			sum = sum * 1
		} else if i == 2 {
			sum = sum * 2 * 1
		} else if i == 3 {
			sum = sum * 3 * 2 / 1
		} else {
			sum = sum*i*(i-1)/(i-2) + (i - 3)
		}
		res = res + sum
		sum = -1
	}
	return res
}

1007.行相等的最少多米诺旋转(2)

• 题目

在一排多米诺骨牌中，A[i] 和 B[i]分别代表第 i 个多米诺骨牌的上半部分和下半部分。
（一个多米诺是两个从 1 到 6 的数字同列平铺形成的—— 该平铺的每一半上都有一个数字。）
我们可以旋转第i张多米诺，使得A[i] 和B[i]的值交换。
返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
如果无法做到，返回-1.
示例 1：输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2] 输出：2
解释：图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
示例 2：输入：A = [3,5,1,2,3], B = [3,6,3,3,4] 输出：-1
解释：在这种情况下，不可能旋转多米诺牌使一行的值相等。
提示：1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000

• 解题思路

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

func minDominoRotations(A []int, B []int) int {
	a, b := A[0], B[0]
	resA := check(A, B, a)
	resB := check(A, B, b)
	if resA > 0 && resB > 0 { // 都行选最少
		return min(resA, resB)
	}
	return max(resA, resB) // 不行选最多
}

func check(A []int, B []int, target int) int {
	a, b := 0, 0
	for i := 0; i < len(A); i++ {
		if A[i] != target && B[i] != target { // 都不满足直接返回-1
			return -1
		} else if A[i] != target { // A[i]不满足，需要交换
			a++
		} else if B[i] != target { // B[i]不满足，需要交换
			b++
		}
	}
	return min(a, b)
}

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

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

# 2
func minDominoRotations(A []int, B []int) int {
	var arr, arrA, arrB [7]int
	for i := 0; i < len(A); i++ {
		if A[i] == B[i] {
			arr[A[i]]++
		} else {
			arr[A[i]]++
			arr[B[i]]++
			arrA[A[i]]++
			arrB[B[i]]++
		}
	}
	for i := 0; i < len(arr); i++ {
		if arr[i] == len(A) {
			return min(arrA[i], arrB[i])
		}
	}
	return -1
}

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

1008.前序遍历构造二叉搜索树(2)

• 题目

返回与给定前序遍历preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，
对于node.left的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。
此外，前序遍历首先显示节点node 的值，然后遍历 node.left，接着遍历 node.right。）
题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
示例：输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
提示：1 <= preorder.length <= 100
1 <= preorder[i]<= 10^8
preorder 中的值互不相同

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(nlog(n))	O(log(n))
02	递归	O(n)	O(log(n))

func bstFromPreorder(preorder []int) *TreeNode {
	var root *TreeNode
	for i := 0; i < len(preorder); i++ {
		root = insert(root, &TreeNode{
			Val:   preorder[i],
			Left:  nil,
			Right: nil,
		})
	}
	return root
}

func insert(root *TreeNode, node *TreeNode) *TreeNode {
	if root == nil {
		return node
	}
	if root.Val < node.Val {
		root.Right = insert(root.Right, node)
	} else if root.Val > node.Val {
		root.Left = insert(root.Left, node)
	} else {
		root.Val = node.Val
	}
	return root
}

# 2
func bstFromPreorder(preorder []int) *TreeNode {
	length := len(preorder)
	if length == 0 {
		return nil
	}
	index := length
	for i := 1; i < length; i++ {
		if preorder[i] > preorder[0] {
			index = i
			break
		}
	}
	return &TreeNode{
		Val:   preorder[0],
		Left:  bstFromPreorder(preorder[1:index]),
		Right: bstFromPreorder(preorder[index:]),
	}
}

1011.在D天内送达包裹的能力(1)

• 题目

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。
我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 输出：15
解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 
(2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 
示例 2：输入：weights = [3,2,2,4,1,4], D = 3 输出：6
解释：船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：输入：weights = [1,2,3,1,1], D = 4 输出：3
解释： 第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
提示：1 <= D <= weights.length <= 50000
    1 <= weights[i] <= 500

• 解题思路

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

func shipWithinDays(weights []int, D int) int {
	sum := weights[0]
	maxValue := weights[0]
	for i := 1; i < len(weights); i++ {
		sum = sum + weights[i]
		if weights[i] > maxValue {
			maxValue = weights[i]
		}
	}
	left, right := maxValue, sum
	for left < right {
		mid := left + (right-left)/2
		count := judge(weights, mid)
		if count <= D {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func judge(weights []int, target int) int {
	total := 0
	count := 1
	for i := 0; i < len(weights); i++ {
		if total+weights[i] <= target {
			total = total + weights[i]
		} else {
			count++
			total = weights[i]
		}
	}
	return count
}

1014.最佳观光组合(1)

• 题目

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例：输入：[8,1,5,2,6] 输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
提示：2 <= A.length <= 50000
    1 <= A[i] <= 1000

• 解题思路

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

func maxScoreSightseeingPair(A []int) int {
	res := 0
	maxValue := A[0] + 0
	// A[i]+A[j]+i-j=> max(A[i]+i)+(A[j]-j) (i<j)
	for j := 1; j < len(A); j++ {
		res = max(res, A[j]-j+maxValue)
		maxValue = max(maxValue, A[j]+j)
	}
	return res
}

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

1015.可被K整除的最小整数(1)

• 题目

给定正整数K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。
返回N的长度。如果不存在这样的N，就返回 -1。
示例 1：输入：1 输出：1
解释：最小的答案是 N = 1，其长度为 1。
示例 2：输入：2 输出：-1
解释：不存在可被 2 整除的正整数 N 。
示例 3：输入：3 输出：3
解释：最小的答案是 N = 111，其长度为 3。
提示：1 <= K <= 10^5

• 解题思路

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

func smallestRepunitDivByK(K int) int {
	if K%2 == 0 || K%5 == 0 {
		return -1
	}
	res := 1
	num := 1
	for {
		if num%K == 0 {
			return res
		}
		num = num % K // (n*10+1)%K = ((n%K)*10+1)%K
		num = 10*num + 1
		res++
	}
	return -1
}

1016.子串能表示从1到N数字的二进制串(2)

• 题目

给定一个二进制字符串S（一个仅由若干'0' 和 '1' 构成的字符串）和一个正整数N，
如果对于从 1 到 N 的每个整数 X，其二进制表示都是S 的子串，就返回 true，否则返回 false。
示例 1：输入：S = "0110", N = 3 输出：true
示例 2：输入：S = "0110", N = 4 输出：false
提示：1 <= S.length <= 1000
1 <= N <= 10^9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(n)
02	暴力法	O(n^2)	O(n)

func queryString(s string, n int) bool {
	for i := 1; i <= n; i++ {
		target := fmt.Sprintf("%b", i)
		if strings.Contains(s, target) == false {
			return false
		}
	}
	return true
}

# 2
func queryString(s string, n int) bool {
	for i := n/2 + 1; i <= n; i++ {
		target := fmt.Sprintf("%b", i)
		if strings.Contains(s, target) == false {
			return false
		}
	}
	return true
}

1017.负二进制转换(2)

• 题目

给出数字N，返回由若干"0"和"1"组成的字符串，该字符串为 N的负二进制（base -2）表示。
除非字符串就是"0"，否则返回的字符串中不能含有前导零。
示例 1：输入：2 输出："110"
解释：(-2) ^ 2 + (-2) ^ 1 = 2
示例 2：输入：3 输出："111"
解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3
示例 3：输入：4 输出："100"
解释：(-2) ^ 2 = 4
提示：0 <= N <= 10^9

• 解题思路

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

func baseNeg2(n int) string {
	res := ""
	if n == 0 {
		return "0"
	}
	for n != 0 {
		if n%2 == 0 { // 偶数
			res = "0" + res
			n = n / -2
		} else { // 奇数
			res = "1" + res
			n = (n - 1) / -2
		}
	}
	return res
}

# 2
func baseNeg2(n int) string {
	res := ""
	if n == 0 {
		return "0"
	}
	for n != 0 {
		if n%2 == 0 { // 偶数
			res = "0" + res
		} else { // 奇数
			res = "1" + res
		}
		// 3 = 111
		// -2做法：-1 / -2 = 0
		// 位做法：-(-1 >> 1) = 1
		n = -(n >> 1) // 除以-2
	}
	return res
}

1019.链表中的下一个更大节点(2)

• 题目

给出一个以头节点head作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于node_i，如果其next_larger(node_i)是node_j.val，那么就有j > i且node_j.val > node_i.val，
而j是可能的选项中最小的那个。如果不存在这样的j，那么下一个更大值为0。
返回整数答案数组answer，其中answer[i] = next_larger(node_{i+1})。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为2，
第二个节点值为 1，第三个节点值为5 。
示例 1：输入：[2,1,5] 输出：[5,5,0]
示例 2：输入：[2,7,4,3,5] 输出：[7,0,5,5,0]
示例 3：输入：[1,7,5,1,9,2,5,1] 输出：[7,9,9,9,0,5,0,0]
提示：对于链表中的每个节点，1 <= node.val<= 10^9
给定列表的长度在 [0, 10000]范围内

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(n)
02	栈辅助	O(n)	O(n)

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

# 2
func nextLargerNodes(head *ListNode) []int {
	arr := make([]int, 0)
	if head == nil {
		return arr
	}
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	res := make([]int, len(arr))
	stack := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		for len(stack) > 0 && arr[i] > arr[stack[len(stack)-1]] {
			last := stack[len(stack)-1]
			res[last] = arr[i]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	return res
}

1020.飞地的数量(2)

• 题目

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 输出：3
解释： 有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] 输出：0
解释：所有 1 都在边界上或可以到达边界。
提示：
    1 <= A.length <= 500
    1 <= A[i].length <= 500
    0 <= A[i][j] <= 1
    所有行的大小都相同

• 解题思路

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

func numEnclaves(A [][]int) int {
	for i := 0; i < len(A); i++ {
		dfs(A, i, 0)
		dfs(A, i, len(A[i])-1)
	}
	for i := 0; i < len(A[0]); i++ {
		dfs(A, 0, i)
		dfs(A, len(A)-1, i)
	}
	res := 0
	for i := 0; i < len(A); i++ {
		for j := 0; j < len(A[i]); j++ {
			if A[i][j] == 1 {
				res++
			}
		}
	}
	return res
}

func dfs(A [][]int, i, j int) {
	if i < 0 || i >= len(A) || j < 0 || j >= len(A[i]) {
		return
	}
	if A[i][j] == 0 {
		return
	}
	A[i][j] = 0
	dfs(A, i, j+1)
	dfs(A, i, j-1)
	dfs(A, i+1, j)
	dfs(A, i-1, j)
}

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

func numEnclaves(A [][]int) int {
	queue := make([][2]int, 0)
	for i := 0; i < len(A); i++ {
		if A[i][0] == 1 {
			A[i][0] = 0
			queue = append(queue, [2]int{i, 0})
		}
		if A[i][len(A[i])-1] == 1 {
			A[i][len(A[i])-1] = 0
			queue = append(queue, [2]int{i, len(A[i]) - 1})
		}
	}
	for i := 0; i < len(A[0]); i++ {
		if A[0][i] == 1 {
			A[0][i] = 0
			queue = append(queue, [2]int{0, i})
		}
		if A[len(A)-1][i] == 1 {
			A[len(A)-1][i] = 0
			queue = append(queue, [2]int{len(A) - 1, i})
		}
	}
	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(A) || y < 0 || y >= len(A[0]) {
				continue
			}
			if A[x][y] == 0 {
				continue
			}
			queue = append(queue, [2]int{x, y})
			A[x][y] = 0
		}
	}
	res := 0
	for i := 0; i < len(A); i++ {
		for j := 0; j < len(A[i]); j++ {
			if A[i][j] == 1 {
				res++
			}
		}
	}
	return res
}

1023.驼峰式匹配(2)

• 题目

如果我们可以将小写字母插入模式串pattern得到待查询项query，那么待查询项与给定模式串匹配。
（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）
给定待查询列表queries，和模式串pattern，返回由布尔值组成的答案列表answer。
只有在待查项queries[i] 与模式串pattern 匹配时，answer[i]才为 true，否则为 false。
示例 1：输入：queries = ["FooBar","FooBarTest","FootBall",
"FrameBuffer","ForceFeedBack"], pattern = "FB"
输出：[true,false,true,true,false]
示例："FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。
"FootBall" 可以这样生成："F" + "oot" + "B" + "all".
"FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer".
示例 2：输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], 
pattern = "FoBa" 输出：[true,false,true,false,false]
解释： "FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".
示例 3：输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"],
pattern = "FoBaT" 输入：[false,true,false,false,false]
解释：  "FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".
提示：1 <= queries.length <= 100
1 <= queries[i].length <= 100
1 <= pattern.length <= 100
所有字符串都仅由大写和小写英文字母组成。

• 解题思路

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

func camelMatch(queries []string, pattern string) []bool {
	n := len(queries)
	res := make([]bool, n)
	for i := 0; i < n; i++ {
		str := queries[i]
		count := 0
		flag := true
		for j := 0; j < len(str); j++ {
			if count < len(pattern) && str[j] == pattern[count] {
				count++
				continue
			}
			if 'A' <= str[j] && str[j] <= 'Z' {
				flag = false
				break
			}
		}
		if flag == true && count == len(pattern) {
			res[i] = true
		}
	}
	return res
}

# 2
func camelMatch(queries []string, pattern string) []bool {
	node := Constructor()
	node.Insert(pattern)
	res := make([]bool, len(queries))
	for i := 0; i < len(queries); i++ {
		res[i] = node.Match(queries[i])
	}
	return res
}

type Trie struct {
	next   map[int32]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
	ending int             // 次数（可以改为bool）
}

func Constructor() *Trie {
	return &Trie{
		next:   make(map[int32]*Trie),
		ending: 0,
	}
}

// 插入word
func (this *Trie) Insert(word string) {
	temp := this
	for _, v := range word {
		value := v
		if _, ok := temp.next[value]; ok == false {
			temp.next[value] = Constructor()
		}
		temp = temp.next[value]
	}
	temp.ending++
}

// 查找
func (this *Trie) Match(word string) bool {
	temp := this
	for _, v := range word {
		value := v
		if _, ok := temp.next[value]; ok == false {
			if value < 'a' {
				return false
			}
		} else {
			temp = temp.next[value]
		}
	}
	if temp.ending > 0 {
		return true
	}
	return false
}

1024.视频拼接(2)

• 题目

你将会获得一系列视频片段，这些片段来自于一项持续时长为T秒的体育赛事。
这些片段可能有所重叠，也可能长度不一。
视频片段clips[i]都用区间进行表示：开始于clips[i][0]并于clips[i][1]结束。
我们甚至可以对这些片段自由地再剪辑，例如片段[0, 7]可以剪切成[0, 1] +[1, 3] + [3, 7]三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。
返回所需片段的最小数目，如果无法完成该任务，则返回-1 。
示例 1：输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 输出：3
解释：我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。
示例 2：输入：clips = [[0,1],[1,2]], T = 5 输出：-1
解释：我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。
示例 3：输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],
[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 输出：3
解释： 我们选取片段 [0,4], [4,7] 和 [6,9] 。
示例 4：输入：clips = [[0,4],[2,8]], T = 5 输出：2
解释：注意，你可能录制超过比赛结束时间的视频。
提示：1 <= clips.length <= 100
0 <= clips[i][0] <=clips[i][1] <= 100
0 <= T <= 100

• 解题思路

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

func videoStitching(clips [][]int, T int) int {
	dp := make([]int, T+1) //dp[i]表示将区间[0,i)覆盖所需的最少子区间的数量
	for i := 0; i <= T; i++ {
		dp[i] = math.MaxInt32 / 10
	}
	dp[0] = 0
	for i := 1; i <= T; i++ {
		for j := 0; j < len(clips); j++ {
			a, b := clips[j][0], clips[j][1]
			if a < i && i <= b && dp[a]+1 < dp[i] {
				dp[i] = dp[a] + 1
			}
		}
	}
	if dp[T] == math.MaxInt32/10 {
		return -1
	}
	return dp[T]
}

# 2
func videoStitching(clips [][]int, T int) int {
	arr := make([]int, T)
	for i := 0; i < len(clips); i++ {
		a, b := clips[i][0], clips[i][1]
		if a < T && arr[a] < b {
			arr[a] = b // 更新当前位置能到达最远的位置
		}
	}
	last := 0
	prev := 0
	res := 0
	// 变成leetcode45.跳跃游戏II的变形
	for i := 0; i < len(arr); i++ {
		if arr[i] > last {
			last = arr[i]
		}
		if i == last { // 无法达到目标
			return -1
		}
		if i == prev {
			res++
			prev = last
		}
	}
	return res
}

1026.节点与其祖先之间的最大差值(2)

• 题目

给定二叉树的根节点root，找出存在于 不同 节点A 和B之间的最大值 V，
其中V = |A.val - B.val|，且A是B的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：输入：root = [8,3,10,1,6,null,14,null,null,4,7,13] 输出：7
解释：  我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
示例 2：输入：root = [1,null,2,null,0,3] 输出：3
提示：树中的节点数在2到5000之间。
0 <= Node.val <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	递归	O(n^2)	O(n)

var res int

func maxAncestorDiff(root *TreeNode) int {
	res = 0
	if root == nil {
		return 0
	}
	dfs(root, root.Val, root.Val)
	return res
}

func dfs(root *TreeNode, minValue, maxValue int) {
	if root == nil {
		return
	}
	if root.Val > maxValue {
		maxValue = root.Val
	}
	if root.Val < minValue {
		minValue = root.Val
	}
	if maxValue-minValue > res {
		res = maxValue - minValue
	}
	dfs(root.Left, minValue, maxValue)
	dfs(root.Right, minValue, maxValue)
}

# 2
var res int

func maxAncestorDiff(root *TreeNode) int {
	res = 0
	if root == nil {
		return 0
	}
	dfs(root, []int{})
	return res
}

func dfs(root *TreeNode, arr []int) {
	if root == nil {
		return
	}
	for i := 0; i < len(arr); i++ {
		if abs(arr[i], root.Val) > res {
			res = abs(arr[i], root.Val)
		}
	}
	arr = append(arr, root.Val)
	dfs(root.Left, arr)
	dfs(root.Right, arr)
}

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

1027.最长等差数列(2)

• 题目

给定一个整数数组A，返回 A中最长等差子序列的长度。
回想一下，A的子序列是列表A[i_1], A[i_2], ..., A[i_k] 
其中0 <= i_1 < i_2 < ... < i_k <= A.length - 1。
并且如果B[i+1] - B[i](0 <= i < B.length - 1) 的值都相同，那么序列B是等差的。
示例 1：输入：[3,6,9,12] 输出：4
解释： 整个数组是公差为 3 的等差数列。
示例 2：输入：[9,4,7,2,10] 输出：3
解释：最长的等差子序列是 [4,7,10]。
示例 3：输入：[20,1,15,3,10,5,8] 输出：4
解释：最长的等差子序列是 [20,15,10,5]。
提示：2 <= A.length <= 2000
0 <= A[i] <= 10000

• 解题思路

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

func longestArithSeqLength(A []int) int {
	n := len(A)
	if n < 3 {
		return 0
	}
	res := 0
	dp := make([]map[int]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make(map[int]int)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			diff := A[i] - A[j]
			if _, ok := dp[j][diff]; ok {
				dp[i][diff] = dp[j][diff] + 1
			} else {
				dp[j][diff] = 1
				dp[i][diff] = dp[j][diff] + 1
			}
			if dp[i][diff] > res {
				res = dp[i][diff]
			}
		}
	}
	return res
}

# 2
func longestArithSeqLength(A []int) int {
	n := len(A)
	if n < 3 {
		return 0
	}
	res := 0
	dp := make([][20001]int, n)
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			diff := A[i] - A[j] + 10001
			if dp[j][diff] > 0 {
				dp[i][diff] = dp[j][diff] + 1
			} else {
				dp[j][diff] = 1
				dp[i][diff] = dp[j][diff] + 1
			}
			if dp[i][diff] > res {
				res = dp[i][diff]
			}
		}
	}
	return res
}

1031.两个非重叠子数组的最大和(3)

• 题目

给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。
（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）
从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) +
(A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1：输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和	O(n^2)	O(n)
02	前缀和	O(n)	O(1)
03	前缀和	O(n)	O(1)

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
	res := 0
	n := len(nums)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + nums[i]
	}
	for i := firstLen; i <= n; i++ { // 枚举L的起始点
		L := arr[i] - arr[i-firstLen]
		M := 0
		for j := secondLen; j <= i-firstLen; j++ { // M在L左边的情况
			M = max(M, arr[j]-arr[j-secondLen])
		}
		for j := n; j >= i+secondLen; j-- { // M在L右边的情况
			M = max(M, arr[j]-arr[j-secondLen])
		}
		res = max(res, L+M)
	}
	return res
}

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

# 2
func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
	res := 0
	n := len(nums)
	a, b := firstLen, secondLen
	for i := 1; i < n; i++ {
		nums[i] = nums[i] + nums[i-1] // 前缀和
	}
	res = nums[a+b-1]
	L, M := nums[a-1], nums[b-1]
	for i := a + b; i < n; i++ { // 枚举以i结尾的数组：分为左边（不固定）+右边（固定长度为a/b）
		L = max(L, nums[i-b]-nums[i-b-a])                     // L为i-b结尾的数组中的L最大值
		M = max(M, nums[i-a]-nums[i-a-b])                     // M为i-a结尾的数组中的M最大值
		temp := max(L+nums[i]-nums[i-b], nums[i]-nums[i-a]+M) // L+M 和 M+L的较大者
		res = max(res, temp)
	}
	return res
}

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

# 3
func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
	res := 0
	n := len(nums)
	a, b := firstLen, secondLen
	for i := 1; i < n; i++ {
		nums[i] = nums[i] + nums[i-1] // 前缀和
	}
	res = nums[a+b-1]
	L, M := nums[a-1], nums[b-1]
	for i := a; i < n-b; i++ { // 枚举L以i结尾+右边（固定长度为b）
		L = max(L, nums[i]-nums[i-a])   // L为结尾的数组中的L最大值
		temp := L + nums[i+b] - nums[i] // L+M
		res = max(res, temp)
	}
	for i := b; i < n-a; i++ { // 枚举M以i结尾+右边（固定长度为a）
		M = max(M, nums[i]-nums[i-b])   // M为i结尾的数组中的M最大值
		temp := nums[i+a] - nums[i] + M //  M+L
		res = max(res, temp)
	}
	return res
}

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

1034.边框着色(3)

• 题目

给出一个二维整数网格grid，网格中的每个值表示该位置处的网格块的颜色。
只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。
连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，
或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。
给出位于(r0, c0)的网格块和颜色color，使用指定颜色color为所给网格块的连通分量的边界进行着色，并返回最终的网格grid 。
示例 1：输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3 输出：[[3, 3], [3, 2]]
示例 2：输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3 输出：[[1, 3, 3], [2, 3, 3]]
示例 3：输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2 
输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]
提示：1 <= grid.length <= 50
1 <= grid[0].length <= 50
1 <= grid[i][j] <= 1000
0 <= r0 < grid.length
0 <= c0 < grid[0].length
1 <= color <= 1000

• 解题思路

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

func colorBorder(grid [][]int, r0 int, c0 int, color int) [][]int {
	dfs(grid, r0, c0, grid[r0][c0])
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] < 0 {
				grid[i][j] = color // 染色
			}
		}
	}
	return grid
}

func dfs(grid [][]int, i, j int, color int) {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) ||
		grid[i][j] != color {
		return
	}
	grid[i][j] = -color // 先标记相反，表示访问过
	dfs(grid, i+1, j, color)
	dfs(grid, i-1, j, color)
	dfs(grid, i, j+1, color)
	dfs(grid, i, j-1, color)
	if 0 < i && i < len(grid)-1 && 0 < j && j < len(grid[0])-1 &&
		color == abs(grid[i-1][j]) && color == abs(grid[i+1][j]) &&
		color == abs(grid[i][j-1]) && color == abs(grid[i][j+1]) {
		grid[i][j] = color // 访问完，内部的联通分量还原，不做改变
	}
}

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

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

func colorBorder(grid [][]int, r0 int, c0 int, color int) [][]int {
	n, m := len(grid), len(grid[0])
	targetColor := grid[r0][c0]
	visited := make([]bool, n*m)
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{r0, c0})
	visited[r0*m+c0] = true
	for len(queue) > 0 {
		a, b := queue[0][0], queue[0][1]
		queue = queue[1:]
		for i := 0; i < 4; i++ {
			x := a + dx[i]
			y := b + dy[i]
			if 0 <= x && x < n && 0 <= y && y < m {
				if visited[x*m+y] == true { // 访问过
					continue
				}
				if grid[x][y] != targetColor { // 颜色不同，边界
					grid[a][b] = color
				} else { // 颜色相同
					visited[x*m+y] = true
					queue = append(queue, [2]int{x, y})
				}
			} else {
				grid[a][b] = color // 边界
			}
		}
	}
	return grid
}

# 3
var visited []bool

func colorBorder(grid [][]int, r0 int, c0 int, color int) [][]int {
	visited = make([]bool, len(grid)*len(grid[0]))
	dfs(grid, r0, c0, grid[r0][c0], color)
	return grid
}

func dfs(grid [][]int, i, j int, targetColor int, color int) int {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) { // 边界
		return 0
	}
	if visited[i*len(grid[0])+j] == true { // 先判断，因为修改了颜色
		return 1
	}
	if grid[i][j] != targetColor {
		return 0
	}
	visited[i*len(grid[0])+j] = true
	a := dfs(grid, i+1, j, targetColor, color)
	b := dfs(grid, i-1, j, targetColor, color)
	c := dfs(grid, i, j+1, targetColor, color)
	d := dfs(grid, i, j-1, targetColor, color)
	if a+b+c+d < 4 {
		grid[i][j] = color
	}
	return 1
}

1035.不相交的线(3)

• 题目

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，
且我们绘制的直线不与任何其他连线（非水平线）相交。
以这种方法绘制线条，并返回我们可以绘制的最大连线数。
示例 1：输入：A = [1,4,2], B = [1,2,4] 输出：2
解释：我们可以画出两条不交叉的线，如上图所示。
我们无法画出第三条不相交的直线，因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
示例 2：输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2] 输出：3
示例 3：输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1] 输出：2
提示：1 <= A.length <= 500
    1 <= B.length <= 500
    1 <= A[i], B[i] <= 2000

• 解题思路

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

func maxUncrossedLines(A []int, B []int) int {
	n, m := len(A), len(B)
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if A[i-1] == B[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[n][m]
}

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

# 2
func maxUncrossedLines(A []int, B []int) int {
	n, m := len(A), len(B)
	prev := make([]int, m+1)
	cur := make([]int, m+1)
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if A[i-1] == B[j-1] {
				cur[j] = prev[j-1] + 1
			} else {
				cur[j] = max(prev[j], cur[j-1])
			}
		}
		copy(prev, cur)
	}
	return cur[m]
}

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

# 3
func maxUncrossedLines(A []int, B []int) int {
	n, m := len(A), len(B)
	cur := make([]int, m+1)
	for i := 1; i <= n; i++ {
		pre := cur[0]
		for j := 1; j <= m; j++ {
			temp := cur[j]
			if A[i-1] == B[j-1] {
				cur[j] = pre + 1
			} else {
				cur[j] = max(cur[j], cur[j-1])
			}
			pre = temp
		}
	}
	return cur[m]
}

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

1038.把二叉搜索树转换为累加树(2)

• 题目

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
使每个节点 node的新值等于原树中大于或等于node.val的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：该题目与 538:相同
示例 1：输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：输入：root = [0,null,1] 输出：[1,null,1]
示例 3：输入：root = [1,0,2] 输出：[3,3,2]
示例 4：输入：root = [3,2,4,1] 输出：[7,9,4,10]
提示：树中的节点数介于 1 和 100 之间。
每个节点的值介于0 和100之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	栈辅助	O(n)	O(n)

func bstToGst(root *TreeNode) *TreeNode {
	sum := 0
	dfs(root, &sum)
	return root
}

func dfs(root *TreeNode, sum *int) {
	if root == nil {
		return
	}
	dfs(root.Right, sum)
	*sum = *sum + root.Val
	root.Val = *sum
	dfs(root.Left, sum)
}

# 2
func bstToGst(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	stack := make([]*TreeNode, 0)
	temp := root
	sum := 0
	for {
		if temp != nil {
			stack = append(stack, temp)
			temp = temp.Right
		} else if len(stack) != 0 {
			temp = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			temp.Val = temp.Val + sum
			sum = temp.Val
			temp = temp.Left
		} else {
			break
		}
	}
	return root
}

1040.移动石子直到连续II(1)

• 题目

在一个长度无限的数轴上，第 i 颗石子的位置为stones[i]。
如果一颗石子的位置最小/最大，那么该石子被称作端点石子。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像stones = [1,2,5]这样，你将无法移动位于位置 5 的端点石子，
因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 
以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。
示例 1：输入：[7,4,9] 输出：[1,2]
解释：我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。
示例2：输入：[6,5,4,3,10] 输出：[2,3]
解释：我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。
示例 3：输入：[100,101,104,102,103] 输出：[0,0]
提示：3 <= stones.length <= 10^4
1 <= stones[i] <= 10^9
stones[i]的值各不相同。

• 解题思路

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

func numMovesStonesII(stones []int) []int {
	n := len(stones)
	sort.Ints(stones)
	maxRes := 0
	// 最大移动次数：可以移动stones[0]和stones[n-1] 2种情况
	// 以移动stones[0]为例：
	// 1、移动stones[0]到stones[1]之后的空位，使得stones[1]、、stones[k]、、stones[0]连续
	// 2、然后移动stones[1]到stones[0]之后的空位，使得stones[2]、、stones[k]、、stones[0]、stones[k+1]、、stones[1]连续
	// 3、重复上述步骤：把连续数组第1个数移动到最后一个数后面得空位上，形成新的连续数组
	length := (stones[n-1] - stones[0] + 1) - n // 最小值与最大值直接的空格数
	a := stones[1] - stones[0] - 1              // 第1次移动stones[0] 浪费的空间
	b := stones[n-1] - stones[n-2] - 1          // 第1次移动stones[n-1] 浪费的空间
	maxRes = length - min(a, b)
	// 最小移动次数：数组在范围n最多有多少数字
	minRes := maxRes
	j := 0
	for i := 0; i < n; i++ {
		for j < n-1 && stones[j+1]-stones[i]+1 <= n {
			j++
		}
		total := j - i + 1 // 连续数字的长度
		// 特例：1，2，3，4，7 => 长度为n-1且连续
		if total == n-1 && stones[j]-stones[i]+1 == n-1 {
			minRes = min(minRes, 2)
		} else {
			minRes = min(minRes, n-total)
		}
	}
	return []int{minRes, maxRes}
}

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

1041.困于环中的机器人(1)

• 题目

在无限的平面上，机器人最初位于(0, 0)处，面朝北方。机器人可以接受下列三条指令之一：
"G"：直走 1 个单位
"L"：左转 90 度
"R"：右转 90 度
机器人按顺序执行指令instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回true。否则，返回 false。
示例 1：输入："GGLLGG" 输出：true
解释：机器人从 (0,0) 移动到 (0,2)，转 180 度，然后回到 (0,0)。
重复这些指令，机器人将保持在以原点为中心，2 为半径的环中进行移动。
示例 2：输入："GG" 输出：false
解释：机器人无限向北移动。
示例 3：输入："GL" 输出：true
解释：机器人按 (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ... 进行移动。
提示：1 <= instructions.length <= 100
instructions[i] 在{'G', 'L', 'R'}中

• 解题思路

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

func isRobotBounded(instructions string) bool {
	var dx = []int{1, 0, -1, 0}
	var dy = []int{0, 1, 0, -1}
	dir := 0
	x, y := 0, 0
	for i := 0; i < len(instructions); i++ {
		if instructions[i] == 'L' {
			dir = (dir + 3) % 4
		} else if instructions[i] == 'R' {
			dir = (dir + 1) % 4
		} else {
			x = x + dx[dir]
			y = y + dy[dir]
		}
	}
	return (x == 0 && y == 0) || dir != 0
}

1043.分隔数组以得到最大和(3)

• 题目

给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。
分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。
注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。
示例 1：输入：arr = [1,15,7,9,2,5,10], k = 3 输出：84
解释：因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10]，结果为 [15,15,15,9,10,10,10]，
和为 84，是该数组所有分隔变换后元素总和最大的。
若是分隔成 [1] [15,7,9] [2,5,10]，
结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和（76）小于上一种。 
示例 2：输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4 输出：83
示例 3：输入：arr = [1], k = 1 输出：1
提示：1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length

• 解题思路

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

func maxSumAfterPartitioning(arr []int, k int) int {
	n := len(arr)
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		start := max(0, i-k)
		maxValue := math.MinInt32
		for j := i; j > start; j-- {
			maxValue = max(maxValue, arr[j-1])
			dp[i] = max(dp[i], dp[j-1]+maxValue*(i-j+1))
		}
	}
	return dp[n]
}

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

# 2
func maxSumAfterPartitioning(arr []int, k int) int {
	n := len(arr)
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		start := max(0, i-k)
		maxValue := math.MinInt32
		for j := i - 1; j >= start; j-- {
			maxValue = max(maxValue, arr[j])
			dp[i] = max(dp[i], dp[j]+maxValue*(i-j))
		}
	}
	return dp[n]
}

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

# 3
func maxSumAfterPartitioning(arr []int, k int) int {
	n := len(arr)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		maxValue := arr[i]
		for j := i; j >= 0 && j > i-k; j-- {
			maxValue = max(maxValue, arr[j])
			if j > 0 {
				dp[i] = max(dp[i], dp[j-1]+maxValue*(i-j+1))
			} else {
				dp[i] = max(dp[i], maxValue*(i+1))
			}
		}
	}
	return dp[n-1]
}

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

1048.最长字符串链(2)

• 题目

给出一个单词列表，其中每个单词都由小写英文字母组成。
如果我们可以在word1的任何地方添加一个字母使其变成word2，那么我们认为word1是word2的前身。
例如，"abc"是"abac"的前身。
词链是单词[word_1, word_2, ..., word_k]组成的序列，
k >= 1，其中word_1是word_2的前身，word_2是word_3的前身，依此类推。
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
示例：输入：["a","b","ba","bca","bda","bdca"] 输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。
提示：1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]仅由小写英文字母组成。

• 解题思路

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

func longestStrChain(words []string) int {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	res := 0
	dp := make(map[string]int)
	for i := 0; i < len(words); i++ {
		str := words[i]
		for j := 0; j < len(words[i]); j++ {
			target := words[i][:j] + words[i][j+1:]
			if dp[target]+1 > dp[str] {
				dp[str] = dp[target] + 1
			}
		}
		if dp[str] > res {
			res = dp[str]
		}
	}
	return res
}

# 2
func longestStrChain(words []string) int {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	res := 0
	dp := make([]int, len(words))
	for i := 0; i < len(words); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if judge(words[i], words[j]) == true && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
			}
		}
		if dp[i] > res {
			res = dp[i]
		}
	}
	return res
}

func judge(a, b string) bool {
	if len(a)-len(b) != 1 {
		return false
	}
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] == b[j] {
			j++
		}
		i++
	}
	return j == len(b)
}

1049.最后一块石头的重量II(2)

• 题目

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。
那么粉碎的可能结果如下：
如果x == y，那么两块石头都会被完全粉碎；
如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：输入：[2,7,4,1,8,1] 输出：1
解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
提示：1 <= stones.length <= 30
1 <= stones[i] <= 1000

• 解题思路

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

func lastStoneWeightII(stones []int) int {
	sum := 0
	for i := 0; i < len(stones); i++ {
		sum = sum + stones[i]
	}
    // 求最后1个最小，把石头分2堆，求差值
	// 题目转换为0-1背包问题，容量为sum/2，能装多大体积
	target := sum / 2
	dp := make([]int, sum/2+1)
	for i := 0; i < len(stones); i++ {
		for j := target; j >= 0; j-- {
			if j-stones[i] >= 0 {
				dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
			}
		}
	}
	return sum - 2*dp[sum/2]
}

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

# 2
func lastStoneWeightII(stones []int) int {
	n := len(stones)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + stones[i]
	}
    // 求最后1个最小，把石头分2堆，求差值
	// 题目转换为0-1背包问题，容量为sum/2，能装多大体积
	target := sum / 2
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, target+1)
		dp[i][0] = 0
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= target; j++ {
			if j-stones[i-1] < 0 {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1])
			}
		}
	}
	return sum - 2*dp[n][sum/2]
}

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

1052.爱生气的书店老板(1)

• 题目

今天，书店老板有一家店打算试营业 customers.length 分钟。
每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 输出：16
解释： 书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
提示： 1 <= X <= customers.length == grumpy.length <= 20000
    0 <= customers[i] <= 1000
    0 <= grumpy[i] <= 1

• 解题思路

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

func maxSatisfied(customers []int, grumpy []int, X int) int {
	n := len(customers)
	total := 0
	res := 0
	for i := 0; i < n; i++ {
		if grumpy[i] == 0 {
			total = total + customers[i]
		}
	}
	window := 0
	for i := 0; i < X; i++ {
		if grumpy[i] == 1 {
			window = window + customers[i]
		}
	}
	res = max(res, total+window)
	for i := X; i < n; i++ {
		window = window + customers[i]*grumpy[i] - customers[i-X]*grumpy[i-X]
		res = max(res, total+window)
	}
	return res
}

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

1053.交换一次的先前排列(2)

• 题目

给你一个正整数的数组 A（其中的元素不一定完全不同），
请你返回可在一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：输入：arr = [3,2,1] 输出：[3,1,2]
解释：交换 2 和 1
示例 2：输入：arr = [1,1,5] 输出：[1,1,5]
解释：已经是最小排列
示例 3：输入：arr = [1,9,4,6,7] 输出：[1,7,4,6,9]
解释：交换 9 和 7
示例 4：输入：arr = [3,1,1,3] 输出：[1,3,1,3]
解释：交换 1 和 3
提示：1 <= arr.length <= 104
1 <= arr[i] <= 104

• 解题思路

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

func prevPermOpt1(arr []int) []int {
	for i := len(arr) - 2; i >= 0; i-- {
		if arr[i] > arr[i+1] { // 找到第一个降序的位置a
			b := -1
			maxValue := -1
			for j := i + 1; j < len(arr); j++ { // 往后找到小于a的最大数第1次出现位置b
				if arr[i] > arr[j] {
					if arr[j] > maxValue {
						maxValue = arr[j]
						b = j
					}
				}
			}
			if b != -1 {
				arr[i], arr[b] = arr[b], arr[i]
				return arr
			}
		}
	}
	return arr
}

# 2
func prevPermOpt1(arr []int) []int {
	a := -1
	b := -1
	var i int
	for i = len(arr) - 2; i >= 0; i-- {
		if arr[i] > arr[i+1] { // 找到第一个降序的位置a
			a = i
			break
		}
	}
	if a == -1 {
		return arr
	}
	maxValue := -1
	for j := i + 1; j < len(arr); j++ { // 往后找到小于a的最大数第1次出现位置b
		if arr[a] > arr[j] {
			if arr[j] > maxValue {
				maxValue = arr[j]
				b = j
			}
		}
	}
	if a != -1 && b != -1 {
		arr[a], arr[b] = arr[b], arr[a]
	}
	return arr
}

1054.距离相等的条形码(2)

• 题目

在一个仓库里，有一排条形码，其中第 i 个条形码为barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 
你可以返回任何满足该要求的答案，此题保证存在答案。
示例 1：输入：[1,1,1,2,2,2] 输出：[2,1,2,1,2,1]
示例 2：输入：[1,1,1,1,2,2,3,3] 输出：[1,3,1,3,2,1,2,1]
提示：1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(n)
02	堆	O(nlog(n))	O(n)

func rearrangeBarcodes(barcodes []int) []int {
	m := make(map[int]int)
	for i := 0; i < len(barcodes); i++ {
		m[barcodes[i]]++
	}
	arr := make([]Node, 0)
	for k, v := range m {
		arr = append(arr, Node{
			k,
			v,
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].num > arr[j].num
	})
	res := make([]int, len(barcodes))
	index := 0
	// 先偶后奇
	for i := 0; i < 2; i++ {
		for j := i; j < len(barcodes); j = j + 2 {
			if arr[index].num == 0 {
				index++
			}
			res[j] = arr[index].value
			arr[index].num--
		}
	}
	return res
}

# 2
func rearrangeBarcodes(barcodes []int) []int {
	n := len(barcodes)
	if n <= 1 {
		return barcodes
	}
	res := make([]int, 0)
	m := make(map[int]int)
	for _, v := range barcodes {
		m[v]++
	}
	nodeHeap := &Heap{}
	heap.Init(nodeHeap)
	for k, v := range m {
		heap.Push(nodeHeap, Node{
			value: k,
			num:   v,
		})
	}
	for nodeHeap.Len() >= 2 {
		node1 := heap.Pop(nodeHeap).(Node)
		node2 := heap.Pop(nodeHeap).(Node)
		res = append(res, node1.value, node2.value)
		node1.num--
		node2.num--
		if node1.num > 0 {
			heap.Push(nodeHeap, node1)
		}
		if node2.num > 0 {
			heap.Push(nodeHeap, node2)
		}
	}
	if nodeHeap.Len() > 0 {
		t := heap.Pop(nodeHeap).(Node)
		res = append(res, t.value)
	}
	return res
}

type Node struct {
	value int
	num   int
}

type Heap []Node

func (h Heap) Len() int {
	return len(h)
}

func (h Heap) Less(i, j int) bool {
	return h[i].num > h[j].num
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *Heap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

1072.按列翻转得到最大值等行数(3)

• 题目

给定由若干 0 和 1 组成的矩阵matrix，从中选出任意数量的列并翻转其上的每个单元格。
翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。
回经过一些翻转后，行与行之间所有值都相等的最大行数。
示例 1：输入：[[0,1],[1,1]] 输出：1
解释：不进行翻转，有 1 行所有值都相等。
示例 2：输入：[[0,1],[1,0]] 输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。
示例 3：输入：[[0,0,0],[0,0,1],[1,1,0]] 输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。
提示：1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
所有 matrix[i].length都相等
matrix[i][j] 为0 或1

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^3)	O(n)
02	哈希辅助	O(n^2)	O(n)
03	哈希辅助	O(n^2)	O(n)

func maxEqualRowsAfterFlips(matrix [][]int) int {
	res := 0
	n := len(matrix)
	m := len(matrix[0])
	for i := 0; i < n; i++ {
		count := 0            // 统计与当前行完全一样的行或者完全不同的行的个数，划分为同一组
		arr := make([]int, m) // 翻转当前行的结果
		for j := 0; j < m; j++ {
			arr[j] = 1 - matrix[i][j]
		}
		for k := 0; k < n; k++ {
			if compare(matrix[k], matrix[i]) || compare(matrix[k], arr) {
				count++
			}
		}
		res = max(res, count) // 翻转最大一组的任意一行中的所有0或者1所在列即可
	}
	return res
}

func compare(a, b []int) bool {
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

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

# 2
func maxEqualRowsAfterFlips(matrix [][]int) int {
	res := 0
	n := len(matrix)
	m := len(matrix[0])
	M := make(map[string]int)
	for i := 0; i < n; i++ {
		a := make([]byte, 0)
		b := make([]byte, 0)
		for j := 0; j < m; j++ {
			if matrix[i][j] == 0 {
				a = append(a, '0')
				b = append(b, '1')
			} else {
				a = append(a, '1')
				b = append(b, '0')
			}
		}
		M[string(a)]++
		M[string(b)]++
	}
	for _, v := range M {
		res = max(res, v)
	}
	return res
}

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

# 3
func maxEqualRowsAfterFlips(matrix [][]int) int {
	res := 0
	n := len(matrix)
	m := len(matrix[0])
	M := make(map[string]int)
	for i := 0; i < n; i++ {
		a := make([]byte, 0)
		if matrix[i][0] == 0 {
			for j := 0; j < m; j++ {
				if matrix[i][j] == 0 {
					a = append(a, '0')
				} else {
					a = append(a, '1')
				}
			}
		} else {
			for j := 0; j < m; j++ {
				if matrix[i][j] == 0 {
					a = append(a, '1')
				} else {
					a = append(a, '0')
				}
			}
		}
		M[string(a)]++
	}
	for _, v := range M {
		res = max(res, v)
	}
	return res
}

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

1073.负二进制数相加(1)

• 题目

给出基数为 -2的两个数arr1 和arr2，返回两数相加的结果。
数字以数组形式给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。
例如，arr= [1,1,0,1]表示数字(-2)^3+ (-2)^2 + (-2)^0 = -3。
数组形式的数字也同样不含前导零：以 arr 为例，这意味着要么arr == [0]，要么arr[0] == 1。
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
示例：输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1] 输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
提示：1 <= arr1.length <= 1000
1 <= arr2.length <= 1000
arr1 和arr2都不含前导零
arr1[i] 为0或1
arr2[i]为0 或1

• 解题思路

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

func addNegabinary(arr1 []int, arr2 []int) []int {
	res := make([]int, 1005)
	last := 1004
	i := len(arr1) - 1
	j := len(arr2) - 1
	carry := 0
	for i >= 0 || j >= 0 || carry != 0 {
		if i >= 0 {
			carry = carry + arr1[i]
			i--
		}
		if j >= 0 {
			carry = carry + arr2[j]
			j--
		}
		// 进位处理：
		// 进位可能：-1（0+0-1）、0、1、2、3（1+1+1）
		// 进位计算：-1 => 1; 0、1 => 0; 2、3=>-1
		res[last] = abs(carry) % 2
		if carry >= 0 {
			carry = -carry / 2
		} else {
			carry = 1
		}
		last--
	}
	for last < len(res)-1 && res[last] == 0 { // 消除多余的0，最后1个0不消除
		last++
	}
	return res[last:]
}

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

1079.活字印刷(1)

• 题目

你有一套活字字模tiles，其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：输入："AAB" 输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：输入："AAABBC" 输出：188
提示：1 <= tiles.length <= 7
tiles 由大写英文字母组成

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯-全排列	O(n!)	O(n!)

var res [][]byte

func numTilePossibilities(tiles string) int {
	res = make([][]byte, 0)
	arr := []byte(tiles)
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	dfs(arr, 0, make([]int, len(arr)), make([]byte, 0))
	return len(res)
}

func dfs(nums []byte, index int, visited []int, arr []byte) {
	if len(arr) > 0 {
		temp := make([]byte, len(arr))
		copy(temp, arr)
		res = append(res, temp)
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == 1 {
			continue
		}
		if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0 {
			continue
		}
		arr = append(arr, nums[i])
		visited[i] = 1
		dfs(nums, index+1, visited, arr)
		visited[i] = 0
		arr = arr[:len(arr)-1]
	}
}

1080.根到叶路径上的不足节点(2)

• 题目

给定一棵二叉树的根 root，请你考虑它所有从根到叶的路径：从根到任何叶的路径。
（所谓一个叶子节点，就是一个没有子节点的节点）
假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。
请你删除所有不足节点，并返回生成的二叉树的根。
示例 1：输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]
示例 2：输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]
示例 3：输入：root = [5,-6,-6], limit = 0 输出：[]
提示：给定的树有1到5000个节点
-10^5<= node.val <= 10^5
-10^9 <= limit<= 10^9

• 解题思路

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

func sufficientSubset(root *TreeNode, limit int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Left == nil && root.Right == nil {
		if root.Val < limit { // 需要删除
			return nil
		}
		return root
	}
	left := sufficientSubset(root.Left, limit-root.Val)
	right := sufficientSubset(root.Right, limit-root.Val)
	if left == nil && right == nil { // 都为nil直接返回
		return nil
	}
	root.Left = left
	root.Right = right
	return root
}

# 2
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
	return dfs(root, limit, 0)
}

func dfs(root *TreeNode, limit, sum int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Left == nil && root.Right == nil {
		if root.Val+sum < limit { // 需要删除
			return nil
		}
		return root
	}
	left := dfs(root.Left, limit, sum+root.Val)
	right := dfs(root.Right, limit, sum+root.Val)
	if left == nil && right == nil { // 都为nil直接返回
		return nil
	}
	root.Left = left
	root.Right = right
	return root
}

1081.不同字符的最小子序列(2)

• 题目

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
示例 1：输入："cdadabcc" 输出："adbc"
示例 2：输入："abcd" 输出："abcd"
示例 3：输入："ecbacba" 输出："eacb"
示例 4：输入："leetcode" 输出："letcod"
提示：
    1 <= text.length <= 1000
    text 由小写英文字母组成
注意：本题目与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	单调栈	O(n)	O(n)
02	递归	O(n)	O(n)

func smallestSubsequence(text string) string {
	stack := make([]byte, 0)
	arr := [256]byte{}
	m := make(map[byte]bool)
	for i := 0; i < len(text); i++ {
		arr[text[i]]++
	}
	for i := 0; i < len(text); i++ {
		if m[text[i]] == true {
			arr[text[i]]--
			continue
		}
		// arr[栈顶]说明有重复元素
		// 栈顶>s[i]:说明字典序不满足
		for len(stack) > 0 && stack[len(stack)-1] > text[i] && arr[stack[len(stack)-1]] > 0 {
			m[stack[len(stack)-1]] = false
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, text[i])
		arr[text[i]]--
		m[text[i]] = true
	}
	return string(stack)
}

# 2
func smallestSubsequence(text string) string {
	arr := [26]int{}
	pos := 0
	for i := 0; i < len(text); i++ {
		arr[text[i]-'a']++
	}
	for i := 0; i < len(text); i++ {
		if text[i] < text[pos] {
			pos = i
		}
		arr[text[i]-'a']--
		if arr[text[i]-'a'] == 0 {
			break
		}
	}
	if len(text) == 0 {
		return ""
	}
	newStr := strings.ReplaceAll(text[pos+1:], string(text[pos]), "")
	return string(text[pos]) + smallestSubsequence(newStr)
}

1090.受标签影响的最大值(1)

• 题目

我们有一个项的集合，其中第i项的值为values[i]，标签为labels[i]。
我们从这些项中选出一个子集S，这样一来：
|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L的项的数目总满足<= use_limit。
返回子集S的最大可能的和。
示例 1：输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。
示例 2：输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。
示例 3：输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。
示例 4：输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。
提示：1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i]<= 20000
1 <= num_wanted, use_limit<= values.length

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	自定义排序	O(nlog(n))	O(n)

func largestValsFromLabels(values []int, labels []int, num_wanted int, use_limit int) int {
	arr := make([][2]int, 0)
	for i := 0; i < len(values); i++ {
		arr = append(arr, [2]int{values[i], labels[i]})
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] > arr[j][0]
	})
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(arr); i++ {
		if m[arr[i][1]] < use_limit {
			res = res + arr[i][0]
			m[arr[i][1]]++
			num_wanted--
		}
		if num_wanted <= 0 {
			break
		}
	}
	return res
}

1091.二进制矩阵中的最短路径(2)

• 题目

在一个N ×N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格C_1, C_2, ..., C_k组成：
相邻单元格C_i 和C_{i+1}在八个方向之一上连通（此时，C_i 和C_{i+1}不同且共享边或角）
C_1 位于(0, 0)（即，值为grid[0][0]）
C_k位于(N-1, N-1)（即，值为grid[N-1][N-1]）
如果 C_i 位于(r, c)，则 grid[r][c]为空（即，grid[r][c] ==0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
示例 1：输入：[[0,1],[1,0]] 输出：2
示例 2：输入：[[0,0,0],[1,1,0],[1,1,0]] 输出：4
提示：1 <= grid.length == grid[0].length <= 100
grid[i][j] 为0 或1

• 解题思路

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

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

func shortestPathBinaryMatrix(grid [][]int) int {
	if grid[0][0] == 1 {
		return -1
	}
	n, m := len(grid), len(grid[0])
	if grid[n-1][m-1] == 1 {
		return -1
	}
	if n == 1 && m == 1 {
		return 1
	}
	visited := make(map[[2]int]bool)
	visited[[2]int{0, 0}] = true
	queue := make([][3]int, 0)
	queue = append(queue, [3]int{0, 0, 1})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		x := node[0]
		y := node[1]
		v := node[2]
		for i := 0; i < 8; i++ {
			newX := x + dx[i]
			newY := y + dy[i]
			if 0 <= newX && newX < n && 0 <= newY && newY < m &&
				grid[newX][newY] == 0 && visited[[2]int{newX, newY}] == false {
				queue = append(queue, [3]int{newX, newY, v + 1})
				visited[[2]int{newX, newY}] = true
				if newX == n-1 && newY == m-1 {
					return v + 1
				}
			}
		}
	}
	return -1
}

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

func shortestPathBinaryMatrix(grid [][]int) int {
	if grid[0][0] == 1 {
		return -1
	}
	n, m := len(grid), len(grid[0])
	if grid[n-1][m-1] == 1 {
		return -1
	}
	if n == 1 && m == 1 {
		return 1
	}
	queue := make([]int, 0)
	queue = append(queue, 0)
	grid[0][0] = 1
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		x := node / m
		y := node % m
		for i := 0; i < 8; i++ {
			newX := x + dx[i]
			newY := y + dy[i]
			if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] == 0 {
				queue = append(queue, newX*m+newY)
				grid[newX][newY] = grid[x][y] + 1
				if newX == n-1 && newY == m-1 {
					return grid[n-1][m-1]
				}
			}
		}
	}
	return -1
}

1093.大样本统计(1)

• 题目

我们对0到255之间的整数进行采样，并将结果存储在数组count中：count[k]就是整数k 的采样个数。
我们以浮点数数组的形式，分别返回样本的最小值、最大值、平均值、中位数和众数。其中，众数是保证唯一的。
我们先来回顾一下中位数的知识：
如果样本中的元素有序，并且元素数量为奇数时，中位数为最中间的那个元素；
如果样本中的元素有序，并且元素数量为偶数时，中位数为中间的两个元素的平均值。
示例 1：输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
示例 2：输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,4.00000,2.18182,2.00000,1.00000]
提示：count.length == 256
1 <= sum(count) <= 10^9
计数表示的众数是唯一的
答案与真实值误差在10^-5以内就会被视为正确答案

• 解题思路

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

func sampleStats(count []int) []float64 {
	maxValue := math.MinInt32
	minValue := math.MaxInt32
	maxTime := 0
	maxTimeValue := 0
	sum := 0
	total := 0
	for i := 0; i < len(count); i++ {
		if count[i] > 0 {
			minValue = i
			break
		}
	}
	for i := len(count) - 1; i >= 0; i-- {
		if count[i] > 0 {
			maxValue = i
			break
		}
	}
	for i := 0; i < len(count); i++ {
		total = total + count[i]
		sum = sum + count[i]*i
		if count[i] > maxTime {
			maxTime = count[i]
			maxTimeValue = i
		}
	}
	a, b := 0, 0
	temp := 0
	for i := 0; i < len(count); i++ {
		if temp <= (total-1)/2 && (total-1)/2 < temp+count[i] {
			a = i
		}
		if temp <= total/2 && total/2 < temp+count[i] {
			b = i
			break
		}
		temp = temp + count[i]
	}
	return []float64{
		float64(minValue),
		float64(maxValue),
		float64(sum) / float64(total),
		float64(a+b) / 2,
		float64(maxTimeValue),
	}
}

1094.拼车(1)

• 题目

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，
车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。
这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = 
[num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：
    必须接送的乘客数量；
    乘客的上车地点；
    以及乘客的下车地点。
这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。
请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务
（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。
示例 1：输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false
示例 2：输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true
示例 3：输入：trips = [[2,1,5],[3,5,7]], capacity = 3 输出：true
示例 4：输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11 输出：true
提示：
    你可以假设乘客会自觉遵守 “先下后上” 的良好素质
    trips.length <= 1000
    trips[i].length == 3
    1 <= trips[i][0] <= 100
    0 <= trips[i][1] < trips[i][2] <= 1000
    1 <= capacity <= 100000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	差分数组	O(n)	O(1)

func carPooling(trips [][]int, capacity int) bool {
	arr := make([]int, 1001)
	for i := 0; i < len(trips); i++ {
		start := trips[i][1]
		end := trips[i][2]
		count := trips[i][0]
		arr[start] = arr[start] + count
		arr[end] = arr[end] - count
	}
	total := 0
	for i := 0; i < len(arr); i++ {
		total = total + arr[i]
		if total > capacity {
			return false
		}
	}
	return true
}

1001-1100-Hard

1028.从先序遍历还原二叉树

题目

我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。
（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。
示例 1：输入："1-2--3--4-5--6--7" 输出：[1,2,5,3,4,6,7]
示例 2：输入："1-2--3---4-5--6---7" 输出：[1,2,5,3,null,6,null,4,null,7]
示例 3：输入："1-401--349---90--88" 输出：[1,401,null,349,88,90]
提示：原始树中的节点数介于 1 和 1000 之间。
    每个节点的值介于 1 和 10 ^ 9 之间。

解题思路

No.	思路	时间复杂度	空间复杂度
01	差分数组	O(n)	O(1)

1074.元素和为目标值的子矩阵数量(3)

• 题目

给出矩阵matrix和目标值target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵x1, y1, x2, y2是满足 x1 <= x <= x2且y1 <= y <= y2的所有单元matrix[x][y]的集合。
如果(x1, y1, x2, y2) 和(x1', y1', x2', y2')两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
示例 1：输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 输出：4
解释：四个只含 0 的 1x1 子矩阵。
示例 2：输入：matrix = [[1,-1],[-1,1]], target = 0 输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
示例 3：输入：matrix = [[904]], target = 0 输出：0
提示：1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+暴力法	O(n^4)	O(n^2)
02	前缀和+哈希	O(n^3)	O(n^2)
03	哈希	O(n^3)	O(n)

func numSubmatrixSumTarget(matrix [][]int, target int) int {
	res := 0
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			arr[i][j] = matrix[i-1][j-1] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1]
		}
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for x := i; x <= n; x++ {
				for y := j; y <= m; y++ {
					if arr[x][y]-arr[i-1][y]-arr[x][j-1]+arr[i-1][j-1] == target {
						res++
					}
				}
			}
		}
	}
	return res
}

# 2
func numSubmatrixSumTarget(matrix [][]int, target int) int {
	res := 0
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			arr[i][j] = matrix[i-1][j-1] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1]
		}
	}
	for a := 1; a <= n; a++ { // 上边界
		for b := a; b <= n; b++ { // 下边界
			temp := make(map[int]int)
			temp[0] = 1
			for j := 1; j <= m; j++ {
				value := arr[b][j] - arr[a-1][j]
				res = res + temp[value-target]
				temp[value]++
			}
		}
	}
	return res
}

# 3
func numSubmatrixSumTarget(matrix [][]int, target int) int {
	res := 0
	n, m := len(matrix), len(matrix[0])
	for a := 0; a < n; a++ { // 上边界
		arr := make([]int, m)    // 每列的和
		for b := a; b < n; b++ { // 下边界
			for j := 0; j < m; j++ {
				arr[j] = arr[j] + matrix[b][j]
			}
			temp := make(map[int]int)
			temp[0] = 1
			sum := 0
			for j := 0; j < m; j++ {
				sum = sum + arr[j]
				res = res + temp[sum-target]
				temp[sum]++
			}
		}
	}
	return res
}

1095.山脉数组中查找目标值

题目

（这是一个 交互式问题）
给你一个 山脉数组mountainArr，
请你返回能够使得mountainArr.get(index)等于target最小的下标 index值。
如果不存在这样的下标 index，就请返回-1。
何为山脉数组？如果数组A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在0 < i< A.length - 1条件下，存在 i 使得：
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]
你将不能直接访问该山脉数组，必须通过MountainArray接口来获取数据：
MountainArray.get(k)- 会返回数组中索引为k的元素（下标从 0 开始）
MountainArray.length()- 会返回该数组的长度
注意：对MountainArray.get发起超过 100 次调用的提交将被视为错误答案。
此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：
https://leetcode.cn/playground/RKhe3ave，请注意这 不是一个正确答案。
示例 1：输入：array = [1,2,3,4,5,3,1], target = 3 输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
示例 2：输入：array = [0,1,2,4,2,1], target = 3 输出：-1
解释：3 在数组中没有出现，返回 -1。
提示：3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <=10^9

解题思路

No.	思路	时间复杂度	空间复杂度
01	差分数组	O(n)	O(1)