0901-1000-Easy

905.按奇偶排序数组(4)

• 题目

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
示例：输入：[3,1,2,4] 输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
提示：
    1 <= A.length <= 5000
    0 <= A[i] <= 5000

• 解题思路

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

func sortArrayByParity(A []int) []int {
	i := 0
	j := len(A)-1
	for i < j{
		if A[i] % 2== 0{
			i++
		}else if A[j] % 2 == 1{
			j--
		}else {
			A[i], A[j] = A[j], A[i]
		}
	}
	return A
}

#
func sortArrayByParity(A []int) []int {
	i := 0
	j := len(A) - 1
	for i < j {
		for i < j && A[i]%2 == 0 {
			i++
		}
		for i < j && A[j]%2 == 1 {
			j--
		}
		A[i], A[j] = A[j], A[i]
	}
	return A
}

#
func sortArrayByParity(A []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(A); i++ {
		if A[i]%2 == 0 {
			res = append(res, A[i])
		}
	}
	for i := 0; i < len(A); i++ {
		if A[i]%2 == 1 {
			res = append(res, A[i])
		}
	}
	return res
}

#
func sortArrayByParity(A []int) []int {
	count := 0
	for i := 0; i < len(A); i++{
		if A[i] % 2 == 0{
			A[count],A[i] = A[i], A[count]
			count++
		}
	}
	return A
}

908.最小差值I(2)

• 题目

给你一个整数数组 A，对于每个整数 A[i]，我们可以选择处于区间 [-K, K] 中的任意数 x ，
将 x 与 A[i] 相加，结果存入 A[i] 。
在此过程之后，我们得到一些数组 B。
返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
示例 1：输入：A = [1], K = 0 输出：0
解释：B = [1]
示例 2：输入：A = [0,10], K = 2 输出：6
解释：B = [2,8]
示例 3：输入：A = [1,3,6], K = 3 输出：0
解释：B = [3,3,3] 或 B = [4,4,4]
提示：
    1 <= A.length <= 10000
    0 <= A[i] <= 10000
    0 <= K <= 10000

• 解题思路

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

func smallestRangeI(A []int, K int) int {
	if len(A) == 1 {
		return 0
	}
	sort.Ints(A)
	if A[len(A)-1]-A[0] > 2*K {
		return A[len(A)-1] - A[0] - 2*K
	}
	return 0
}

#
func smallestRangeI(A []int, K int) int {
	if len(A) == 1 {
		return 0
	}
	min := A[0]
	max := A[0]
	for i := 0; i < len(A); i++ {
		if A[i] > max {
			max = A[i]
		}
		if A[i] < min {
			min = A[i]
		}
	}
	if max-min > 2*K {
		return max - min - 2*K
	}
	return 0
}

914.卡牌分组

• 题目

给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
    每组都有 X 张牌。
    组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。

示例 1：输入：[1,2,3,4,4,3,2,1] 输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4] 
示例 2：输入：[1,1,1,2,2,2,3,3] 输出：false
解释：没有满足要求的分组。
示例 3：输入：[1] 输出：false
解释：没有满足要求的分组。
示例 4：输入：[1,1] 输出：true
解释：可行的分组是 [1,1]
示例 5：输入：[1,1,2,2,2,2] 输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]
提示：
    1 <= deck.length <= 10000
    0 <= deck[i] < 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助+求公约数	O(nlog(n))	O(n)
02	暴力法	O(n^2)	O(n)

func hasGroupsSizeX(deck []int) bool {
	if len(deck) < 2 {
		return false
	}
	m := make(map[int]int)
	for i := 0; i < len(deck); i++ {
		m[deck[i]]++
	}
	v := m[deck[0]]
	for _, value := range m {
		v = gcd(v, value)
		if v < 2 {
			return false
		}
	}
	return true
}

func gcd(x, y int) int {
	a := x % y
	if a > 0 {
		return gcd(y, a)
	}
	return y
}

#
func hasGroupsSizeX(deck []int) bool {
	if len(deck) < 2 {
		return false
	}
	m := make(map[int]int)
	for i := 0; i < len(deck); i++ {
		m[deck[i]]++
	}
	for i := 2; i <= len(deck); i++ {
		flag := true
		if len(deck)%i == 0 {
			for _, v := range m {
				if v%i != 0 {
					flag = false
					break
				}
			}
			if flag == true {
				return true
			}
		}
	}
	return false
}

917.仅仅反转字母(4)

• 题目

给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例 1：输入："ab-cd" 输出："dc-ba"
示例 2：输入："a-bC-dEf-ghIj" 输出："j-Ih-gfE-dCba"
示例 3：输入："Test1ng-Leet=code-Q!" 输出："Qedo1ct-eeLg=ntse-T!"
提示：
    S.length <= 100
    33 <= S[i].ASCIIcode <= 122 
    S 中不包含 \ or "

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(n)
02	双指针	O(n)	O(n)
03	双指针-内置函数	O(n)	O(n)
04	栈辅助	O(n)	O(n)

func reverseOnlyLetters(S string) string {
	i := 0
	j := len(S) - 1
	arr := []byte(S)
	for i < j {
		for i < j && !isLetter(arr[i]) {
			i++
		}
		for i < j && !isLetter(arr[j]) {
			j--
		}
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
	return string(arr)
}

func isLetter(b byte) bool {
	if (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') {
		return true
	}
	return false
}

#
func reverseOnlyLetters(S string) string {
	i := 0
	j := len(S) - 1
	arr := []byte(S)
	for i < j {
		if !isLetter(arr[i]) {
			i++
		} else if !isLetter(arr[j]) {
			j--
		} else {
			arr[i], arr[j] = arr[j], arr[i]
			i++
			j--
		}
	}
	return string(arr)
}

func isLetter(b byte) bool {
	if (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') {
		return true
	}
	return false
}

#
func reverseOnlyLetters(S string) string {
	i := 0
	j := len(S) - 1
	arr := []rune(S)
	for i < j {
		if !unicode.IsLetter(arr[i]) {
			i++
		} else if !unicode.IsLetter(arr[j]) {
			j--
		} else {
			arr[i], arr[j] = arr[j], arr[i]
			i++
			j--
		}
	}
	return string(arr)
}

#
func reverseOnlyLetters(S string) string {
	stack := make([]rune, 0)
	res := make([]rune, 0)
	arr := []rune(S)
	for i := 0; i < len(arr); i++ {
		if unicode.IsLetter(arr[i]) {
			stack = append(stack, arr[i])
		}
	}
	for i := 0; i < len(arr); i++ {
		if unicode.IsLetter(arr[i]) {
			res = append(res, stack[len(stack)-1])
			stack = stack[:len(stack)-1]
		} else {
			res = append(res, arr[i])
		}
	}
	return string(res)
}

922.按奇偶排序数组 II(3)

• 题目

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：输入：[4,2,5,7]输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。 
提示：
    2 <= A.length <= 20000
    A.length % 2 == 0
    0 <= A[i] <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	双指针	O(n)	O(1)
03	数组辅助	O(n)	O(n)

func sortArrayByParityII(A []int) []int {
	i := 0
	j := 1
	for i < len(A) || j < len(A) {
		for i < len(A) && A[i]%2 == 0 {
			i = i + 2
		}
		for j < len(A) && A[j]%2 == 1 {
			j = j + 2
		}
		if i >= len(A) || j >= len(A) {
			break
		}
		A[i], A[j] = A[j], A[i]
	}
	return A
}

#
func sortArrayByParityII(A []int) []int {
	i := 0
	j := 1
	for i < len(A) {
		for A[i]%2 != 0 {
			if A[j]%2 == 0 {
				A[i], A[j] = A[j], A[i]
			} else {
				j = j + 2
			}
		}
		i = i + 2
	}
	return A
}

#
func sortArrayByParityII(A []int) []int {
	i := 0
	j := 1
	res := make([]int, len(A))
	for k := 0; k < len(A); k++ {
		if A[k]%2 == 0 {
			res[i] = A[k]
			i = i + 2
		} else {
			res[j] = A[k]
			j = j + 2
		}
	}
	return res
}

925.长按键入(2)

• 题目

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，
而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。
如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例 1： 输入：name = "alex", typed = "aaleex" 输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。
示例 2： 输入：name = "saeed", typed = "ssaaedd" 输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。
示例 3： 输入：name = "leelee", typed = "lleeelee" 输出：true
示例 4： 输入：name = "laiden", typed = "laiden" 输出：true
解释：长按名字中的字符并不是必要的。
提示：
    name.length <= 1000
    typed.length <= 1000
    name 和 typed 的字符都是小写字母。

• 解题思路

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

func isLongPressedName(name string, typed string) bool {
	i := 0
	j := 0
	for j < len(typed) {
		if i == len(name) {
			i = len(name) - 1
		}
		if name[i] == typed[j] {
			// 正确的话，保证i == len(name) && j == len(typed)
			i++
			j++
		} else {
			if i == 0 {
				return false
			}
			if name[i-1] != typed[j] {
				return false
			} else {
				j++
			}
		}
	}
	return i == len(name) && j == len(typed)
}

#
func isLongPressedName(name string, typed string) bool {
	i := 1
	j := 1
	countI := 0
	countJ := 0
	for i < len(name) || j < len(typed) {
		for i < len(name) && name[i] == name[i-1] {
			i++
			countI++
		}
		for j < len(typed) && typed[j] == typed[j-1] {
			j++
			countJ++
		}
		if name[i-1] != typed[j-1] || countJ < countI {
			return false
		}
		i++
		j++
		countI = 0
		countJ = 0
	}
	return name[len(name)-1] == typed[len(typed)-1]
}

929.独特的电子邮件地址(2)

• 题目

每封电子邮件都由一个本地名称和一个域名组成，以 @ 符号分隔。
例如，在 alice@leetcode.com中， alice 是本地名称，而 leetcode.com 是域名。
除了小写字母，这些电子邮件还可能包含 '.' 或 '+'。
如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'），
则发往那里的邮件将会转发到本地名称中没有点的同一地址。
例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。 
（请注意，此规则不适用于域名。）
如果在本地名称中添加加号（'+'），则会忽略第一个加号后面的所有内容。
这允许过滤某些电子邮件，例如 m.y+name@email.com 将转发到 my@email.com。 
（同样，此规则不适用于域名。）
可以同时使用这两个规则。
给定电子邮件列表 emails，我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少？
示例：
输入：["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com",
"testemail+david@lee.tcode.com"]
输出：2
解释：实际收到邮件的是 "testemail@leetcode.com" 和 "testemail@lee.tcode.com"。
提示：
    1 <= emails[i].length <= 100
    1 <= emails.length <= 100
    每封 emails[i] 都包含有且仅有一个 '@' 字符。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助+内置函数	O(n^2)	O(n)
02	哈希辅助	O(n^2)	O(n)

func numUniqueEmails(emails []string) int {
	m := make(map[string]bool)
	for i := 0; i < len(emails); i++ {
		addr := ""
		arr := strings.Split(emails[i], "@")
		for j := 0; j < len(arr[0]); j++ {
			if arr[0][j] == '+' {
				break
			} else if arr[0][j] == '.' {
				continue
			} else {
				addr = addr + string(arr[0][j])
			}
		}
		m[addr+"@"+arr[1]] = true
	}
	return len(m)
}

#
func numUniqueEmails(emails []string) int {
	m := make(map[string]bool)
	for i := 0; i < len(emails); i++ {
		addr := ""
		isBreak := false
		for j := 0; j < len(emails[i]); j++ {
			if emails[i][j] == '+' {
				isBreak = true
			} else if emails[i][j] == '.' {
				continue
			} else if emails[i][j] == '@' {
				addr = addr + emails[i][j:]
				break
			} else if isBreak == true {
			} else {
				addr = addr + string(emails[i][j])
			}
		}
		m[addr] = true
	}
	return len(m)
}

933.最近的请求次数(2)

• 题目

写一个 RecentCounter 类来计算最近的请求。
它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。

示例：
输入：inputs = ["RecentCounter","ping","ping","ping","ping"], 
inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]
提示：
    每个测试用例最多调用 10000 次 ping。
    每个测试用例会使用严格递增的 t 值来调用 ping。
    每次调用 ping 都有 1 <= t <= 10^9。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组操作	O(n)	O(1)
02	数组操作	O(n)	O(1)

type RecentCounter struct {
	arr []int
}

func Constructor() RecentCounter {
	return RecentCounter{
		arr: make([]int, 0),
	}
}

func (r *RecentCounter) Ping(t int) int {
	r.arr = append(r.arr, t)
	res := 1
	for i := len(r.arr) - 2; i >= 0; i-- {
		if t-r.arr[i] <= 3000 {
			res++
		} else {
			r.arr = r.arr[i+1:]
			break
		}
	}
	return res
}

#
type RecentCounter struct {
	arr []int
}

func Constructor() RecentCounter {
	return RecentCounter{
		arr: make([]int, 0),
	}
}

func (r *RecentCounter) Ping(t int) int {
	r.arr = append(r.arr, t)
	start := t - 3000
	for len(r.arr) > 0 && r.arr[0] < start {
		r.arr = r.arr[1:]
	}
	return len(r.arr)
}

937.重新排列日志文件(2)

• 题目

你有一个日志数组 logs。每条日志都是以空格分隔的字串。
对于每条日志，其第一个字为字母与数字混合的 标识符。
    除标识符之外，所有字均由小写字母组成的，称为 字母日志
    除标识符之外，所有字均由数字组成的，称为 数字日志
题目所用数据保证每个日志在其标识符后面至少有一个字。
请按下述规则将日志重新排序：
    所有 字母日志 都排在 数字日志 之前。
    字母日志 在内容不同时，忽略标识符后，按内容字母顺序排序；在内容相同时，按标识符排序；
    数字日志 应该按原来的顺序排列。
返回日志的最终顺序。
示例 ：
输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
提示：
    0 <= logs.length <= 100
    3 <= logs[i].length <= 100
    logs[i] 保证有一个标识符，并且标识符后面有一个字。

• 解题思路

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

func reorderLogFiles(logs []string) []string {
	numLogs := make([]string, 0)
	wordLogs := make([]string, 0)
	for key := range logs {
		for i := 0; i < len(logs[key]); i++ {
			if logs[key][i] == ' ' && i != len(logs[key])-1 {
				if strings.ContainsAny(logs[key][i+1:], "0123456789") {
					numLogs = append(numLogs, logs[key])
				} else {
					wordLogs = append(wordLogs, logs[key])
				}
				break
			}
		}
	}
	sort.Slice(wordLogs, func(i, j int) bool {
		firstIndex := strings.Index(wordLogs[i], " ")
		secondIndex := strings.Index(wordLogs[j], " ")
		if wordLogs[i][firstIndex+1:] == wordLogs[j][secondIndex+1:] {
			return wordLogs[i][:firstIndex] < wordLogs[j][:secondIndex]
		}
		return wordLogs[i][firstIndex+1:] < wordLogs[j][secondIndex+1:]
	})
	return append(wordLogs, numLogs...)
}

#
type Logs []string

func (l Logs) Len() int {
	return len(l)
}

func (l Logs) Less(i, j int) bool {
	firstIndex := strings.Index(l[i], " ")
	secondIndex := strings.Index(l[j], " ")
	if l[i][firstIndex+1:] == l[j][secondIndex+1:] {
		return l[i][:firstIndex] < l[j][:secondIndex]
	}
	return l[i][firstIndex+1:] < l[j][secondIndex+1:]
}

func (l Logs) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}

func reorderLogFiles(logs []string) []string {
	numLogs := make([]string, 0)
	wordLogs := make([]string, 0)
	for key := range logs {
		for i := 0; i < len(logs[key]); i++ {
			if logs[key][i] == ' ' && i != len(logs[key])-1 {
				if strings.ContainsAny(logs[key][i+1:], "0123456789") {
					numLogs = append(numLogs, logs[key])
				} else {
					wordLogs = append(wordLogs, logs[key])
				}
				break
			}
		}
	}
	sort.Sort(Logs(wordLogs))
	return append(wordLogs, numLogs...)
}

938.二叉搜索树的范围和(2)

• 题目

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1：输入：root = [10,5,15,3,7,null,18], L = 7, R = 15 输出：32
示例 2：输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 输出：23
提示：
    树中的结点数量最多为 10000 个。
    最终的答案保证小于 2^31。

• 解题思路

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

func rangeSumBST(root *TreeNode, L int, R int) int {
	if root == nil {
		return 0
	}
	if root.Val < L {
		return rangeSumBST(root.Right, L, R)
	}
	if root.Val > R {
		return rangeSumBST(root.Left, L, R)
	}
	return root.Val + rangeSumBST(root.Right, L, R) + rangeSumBST(root.Left, L, R)
}

#
func rangeSumBST(root *TreeNode, L int, R int) int {
	if root == nil {
		return 0
	}
	stack := make([]*TreeNode, 0)
	if root.Val > R && root.Left != nil {
		stack = append(stack, root.Left)
	} else if root.Val < L && root.Right != nil {
		stack = append(stack, root.Right)
	} else {
		stack = append(stack, root)
	}
	res := 0
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node.Val <= R && node.Val >= L {
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			res = res + node.Val
		} else if node.Val > R && node.Left != nil {
			stack = append(stack, node.Left)
		} else if node.Val < L && node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return res
}

941.有效的山脉数组(2)

• 题目

定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 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]
示例 1：输入：[2,1] 输出：false
示例 2：输入：[3,5,5] 输出：false
示例 3：输入：[0,3,2,1] 输出：true
提示：
    0 <= A.length <= 10000
    0 <= A[i] <= 10000 

• 解题思路

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

func validMountainArray(A []int) bool {
	if len(A) < 3 {
		return false
	}
	pre := A[0]
	i := 0
	for i = 1; i < len(A); i++ {
		if pre < A[i] {
			pre = A[i]
		} else if pre == A[i] {
			return false
		} else {
			break
		}
	}
	if i >= len(A) || i == 1 {
		return false
	}
	for ; i < len(A); i++ {
		if pre > A[i] {
			pre = A[i]
		} else if pre == A[i] {
			return false
		} else {
			return false
		}
	}
	return true
}

#
func validMountainArray(A []int) bool {
	if len(A) < 3 {
		return false
	}
	i := 0
	j := len(A) - 1
	for i < j && A[i] < A[i+1] {
		i++
	}
	for i < j && A[j] < A[j-1] {
		j--
	}
	return i == j && i != 0 && j != len(A)-1
}

942.增减字符串匹配(1)

• 题目

给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
    如果 S[i] == "I"，那么 A[i] < A[i+1]
    如果 S[i] == "D"，那么 A[i] > A[i+1]
示例 1：输出："IDID" 输出：[0,4,1,3,2]
示例 2：输出："III" 输出：[0,1,2,3]
示例 3：输出："DDI" 输出：[3,2,0,1]
提示： 1 <= S.length <= 10000  S 只包含字符 "I" 或 "D"。

• 解题思路

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

func diStringMatch(S string) []int {
	res := make([]int, len(S)+1)
	left := 0
	right := len(S)
	for i := 0; i < len(S); i++ {
		if S[i] == 'I' {
			res[i] = left
			left++
		} else {
			res[i] = right
			right--
		}
	}
	res[len(S)] = left
	return res
}

944.删列造序(1)

• 题目

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。
你需要选出一组要删掉的列 D，对 A 执行删除操作，使 A 中剩余的每一列都是 非降序 排列的，
然后请你返回 D.length 的最小可能值。
删除 操作的定义是：选出一组要删掉的列，删去 A 中对应列中的所有字符，
形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。（可以参见 删除操作范例）
示例 1：输入：["cba", "daf", "ghi"] 输出：1
解释： 当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。
示例 2：输入：["a", "b"] 输出：0 解释：D = {}
示例 3：输入：["zyx", "wvu", "tsr"] 输出：3 解释：D = {0, 1, 2}
提示：
    1 <= A.length <= 100
    1 <= A[i].length <= 1000
删除操作范例：
比如，有 A = ["abcdef", "uvwxyz"]，
要删掉的列为 {0, 2, 3}，删除后 A 为["bef", "vyz"]， 
A 的列分别为["b","v"], ["e","y"], ["f","z"]。

• 解题思路

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

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

949.给定数字能组成的最大时间(2)

• 题目

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。
最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。
以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
示例 1：输入：[1,2,3,4] 输出："23:41"
示例 2：输入：[5,5,5,5] 输出：""
提示：
    A.length == 4
    0 <= A[i] <= 9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(1)	O(1)
02	全排列	O(1)	O(1)

func largestTimeFromDigits(A []int) string {
	res := ""
	for i := 0; i < 4; i++ {
		for j := 0; j < 4; j++ {
			for k := 0; k < 4; k++ {
				for l := 0; l < 4; l++ {
					if i != j && i != k && i != l &&
						j != k && j != l && k != l {
						hour := A[i]*10 + A[j]
						minute := A[k]*10 + A[l]
						if hour <= 23 && minute <= 59 {
							ans := fmt.Sprintf("%02d:%02d", hour, minute)
							if ans > res && res != "" {
								res = ans
							} else if res == "" {
								res = ans
							}
						}
					}
				}
			}
		}
	}
	return res
}

#
var arr []string

func largestTimeFromDigits(A []int) string {
	res := ""
	arr = make([]string, 0)
	dfs(A, 0, len(A)-1)
	for i := range arr {
		if (arr[i] > res && res != "") || (res == "") {
			res = arr[i]
		}
	}
	return res
}

func dfs(A []int, start, length int) {
	if start == length {
		hour := A[0]*10 + A[1]
		minute := A[2]*10 + A[3]
		if hour <= 23 && minute <= 59 {
			ans := fmt.Sprintf("%02d:%02d", hour, minute)
			arr = append(arr, ans)
		}
	} else {
		for i := start; i <= length; i++ {
			A[i], A[start] = A[start], A[i]
			dfs(A, start+1, length)
			A[i], A[start] = A[start], A[i]
		}
	}
}

953.验证外星语词典(2)

• 题目

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，
返回 true；否则，返回 false。
示例 1：
输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
示例 2：
输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
示例 3：
输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
提示：
    1 <= words.length <= 100
    1 <= words[i].length <= 20
    order.length == 26
    在 words[i] 和 order 中的所有字符都是英文小写字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助-替换	O(n)	O(n)
02	遍历比较	O(n)	O(1)

func isAlienSorted(words []string, order string) bool {
	newWords := make([]string, len(words))
	m := make(map[byte]int)
	for i := 0; i < len(order); i++ {
		m[order[i]] = i
	}
	for i := 0; i < len(words); i++ {
		str := ""
		for j := 0; j < len(words[i]); j++ {
			str = str + string(m[words[i][j]]+'a')
		}
		newWords[i] = str
	}
	for i := 0; i < len(newWords)-1; i++ {
		if newWords[i] > newWords[i+1] {
			return false
		}
	}
	return true
}

#
func isAlienSorted(words []string, order string) bool {
	m := make(map[byte]int)
	for i := 0; i < len(order); i++ {
		m[order[i]] = i
	}

	for i := 0; i < len(words)-1; i++ {
		length := len(words[i])
		if len(words[i+1]) < length {
			length = len(words[i+1])
		}
		for j := 0; j < length; j++ {
			if m[words[i][j]] < m[words[i+1][j]] {
				break
			}
			if m[words[i][j]] > m[words[i+1][j]] {
				return false
			}
			if j == length-1 {
				if len(words[i]) > len(words[i+1]) {
					return false
				}
			}
		}
	}
	return true
}

961.重复 N 次的元素(5)

• 题目

在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。
返回重复了 N 次的那个元素。
示例 1：输入：[1,2,3,3] 输出：3
示例 2：输入：[2,1,2,5,3,2] 输出：2
示例 3：输入：[5,1,5,2,5,3,5,4] 输出：5
提示：
    4 <= A.length <= 10000
    0 <= A[i] < 10000
    A.length 为偶数

• 解题思路

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

func repeatedNTimes(A []int) int {
	m := make(map[int]int)
	for i := 0; i < len(A); i++ {
		if _, ok := m[A[i]]; ok {
			return A[i]
		}
		m[A[i]]++
	}
	return 0
}

#
func repeatedNTimes(A []int) int {
	m := make(map[int]int)
	for i := 0; i < len(A); i++ {
		if _, ok := m[A[i]]; ok {
			return A[i]
		}
		m[A[i]]++
	}
	return 0
}

#
func repeatedNTimes(A []int) int {
	m := make(map[int]int)
	for i := 0; i < len(A); i++ {
		m[A[i]]++
	}
	for key, value := range m {
		if value == len(A)/2 {
			return key
		}
	}
	return 0
}

# 4
func repeatedNTimes(A []int) int {
	for i := 0; i < len(A)-2; i++ {
		if A[i] == A[i+1] || A[i] == A[i+2] {
			return A[i]
		}
	}
	return A[len(A)-1]
}

# 5
func repeatedNTimes(A []int) int {
	for i := 0; i < len(A); i++ {
		for j := i + 1; j < len(A); j++ {
			if A[i] == A[j] {
				return A[i]
			}
		}
	}
	return A[len(A)-1]
}

965.单值二叉树(4)

• 题目

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：输入：[1,1,1,1,1,null,1] 输出：true
示例 2：输入：[2,2,2,5,2] 输出：false
提示：
    给定树的节点数范围是 [1, 100]。
    每个节点的值都是整数，范围为 [0, 99] 。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归-数组辅助	O(n)	O(n)
02	递归	O(n)	O(log(n))
03	递归	O(n)	O(log(n))
04	迭代	O(n)	O(n)

var arr []int

func isUnivalTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	arr = make([]int, 0)
	dfs(root)
	for i := 1; i < len(arr); i++ {
		if arr[i] != arr[i-1] {
			return false
		}
	}
	return true
}

func dfs(root *TreeNode) {
	if root != nil {
		arr = append(arr, root.Val)
		dfs(root.Left)
		dfs(root.Right)
	}
}

#
var value int
var res bool

func isUnivalTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	res = true
	value = root.Val
	dfs(root)
	return res
}

func dfs(root *TreeNode) {
	if root != nil {
		if root.Val != value {
			res = false
			return
		}
		dfs(root.Left)
		dfs(root.Right)
	}
}

#
func isUnivalTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if (root.Left != nil && root.Left.Val != root.Val) ||
		(root.Right != nil && root.Right.Val != root.Val) {
		return false
	}
	return isUnivalTree(root.Left) && isUnivalTree(root.Right)
}

#
func isUnivalTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	value := root.Val
	for len(queue) > 0 {
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		if node.Val != value {
			return false
		}
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return true
}

970.强整数(2)

• 题目

给定两个正整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，
那么我们认为该整数是一个强整数。
返回值小于或等于 bound 的所有强整数组成的列表。
你可以按任何顺序返回答案。在你的回答中，每个值最多出现一次。
示例 1：输入：x = 2, y = 3, bound = 10 输出：[2,3,4,5,7,9,10]
解释： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2
示例 2：输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]
提示：
    1 <= x <= 100
    1 <= y <= 100
    0 <= bound <= 10^6

• 解题思路

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

func powerfulIntegers(x int, y int, bound int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	if bound < 2 {
		return res
	}
	for i := 1; i < bound; i = i * x {
		for j := 1; i+j <= bound; j = j * y {
			if _, ok := m[i+j]; !ok {
				res = append(res, i+j)
				m[i+j] = 1
			}
			if y == 1 {
				break
			}
		}
		if x == 1 {
			break
		}
	}
	return res
}

#
func powerfulIntegers(x int, y int, bound int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	if bound < 2 {
		return res
	}
	xArr := make([]int, 0)
	yArr := make([]int, 0)
	for i := 1; i < bound; i = i * x {
		xArr = append(xArr, i)
		if x == 1 {
			break
		}
	}
	for i := 1; i < bound; i = i * y {
		yArr = append(yArr, i)
		if y == 1 {
			break
		}
	}
	for i := 0; i < len(xArr); i++ {
		for j := 0; j < len(yArr); j++ {
			if xArr[i]+yArr[j] <= bound && m[xArr[i]+yArr[j]] == 0 {
				res = append(res, xArr[i]+yArr[j])
				m[xArr[i]+yArr[j]] = 1
			}
		}
	}
	return res
}

976.三角形的最大周长(2)

• 题目

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
示例 1：输入：[2,1,2] 输出：5
示例 2：输入：[1,2,1] 输出：0
示例 3：输入：[3,2,3,4] 输出：10
示例 4：输入：[3,6,2,3] 输出：8
提示： 
3 <= A.length <= 10000
1 <= A[i] <= 10^6

• 解题思路

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

func largestPerimeter(A []int) int {
	sort.Ints(A)
	for i := len(A) - 3; i >= 0; i-- {
		if A[i]+A[i+1] > A[i+2] {
			return A[i] + A[i+1] + A[i+2]
		}
	}
	return 0
}

#
func largestPerimeter(A []int) int {
	if len(A) < 3 {
		return 0
	}
	for i := 0; i < len(A)-1; i++ {
		for j := 0; j < len(A)-1-i; j++ {
			if A[j] > A[j+1] {
				A[j], A[j+1] = A[j+1], A[j]
			}
		}
		if i >= 2 {
			index := len(A) - 1 - i
			if A[index]+A[index+1] > A[index+2] {
				return A[index] + A[index+1] + A[index+2]
			}
		}
	}
	if A[0]+A[1] > A[2] {
		return A[0] + A[1] + A[2]
	}
	return 0
}

977.有序数组的平方(3)

• 题目

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：输入：[-4,-1,0,3,10] 输出：[0,1,9,16,100]
示例 2：输入：[-7,-3,2,3,11] 输出：[4,9,9,49,121]
提示：
    1 <= A.length <= 10000
    -10000 <= A[i] <= 10000
    A 已按非递减顺序排序。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(n)
02	排序	O(nlog(n))	O(n)
03	直接插入排序	O(n^2)	O(n)

func sortedSquares(A []int) []int {
	res := make([]int, len(A))
	i := 0
	j := len(A) - 1
	index := len(A) - 1
	for i <= j {
		if A[i]*A[i] < A[j]*A[j] {
			res[index] = A[j] * A[j]
			j--
		} else {
			res[index] = A[i] * A[i]
			i++
		}
		index--
	}
	return res
}

#
func sortedSquares(A []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(A); i++ {
		res = append(res, A[i]*A[i])
	}
	sort.Ints(res)
	return res
}

#
func sortedSquares(A []int) []int {
	res := make([]int, len(A))
	res[0] = A[0] * A[0]
	j := 0
	for i := 1; i < len(A); i++ {
		value := A[i] * A[i]
		for j = i - 1; j >= 0; j-- {
			if value < res[j] {
				res[j+1] = res[j]
			} else {
				break
			}
		}
		res[j+1] = value
	}
	return res
}

985.查询后的偶数和(1)

• 题目

给出一个整数数组 A 和一个查询数组 queries。
对于第 i 次查询，有 val = queries[i][0], index = queries[i][1]，
我们会把 val 加到 A[index] 上。然后，第 i 次查询的答案是 A 中偶数值的和。
（此处给定的 index = queries[i][1] 是从 0 开始的索引，每次查询都会永久修改数组 A。）
返回所有查询的答案。你的答案应当以数组 answer 给出，answer[i] 为第 i 次查询的答案。
示例：输入：A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出：[8,6,2,4]
解释：开始时，数组为 [1,2,3,4]。
将 1 加到 A[0] 上之后，数组为 [2,2,3,4]，偶数值之和为 2 + 2 + 4 = 8。
将 -3 加到 A[1] 上之后，数组为 [2,-1,3,4]，偶数值之和为 2 + 4 = 6。
将 -4 加到 A[0] 上之后，数组为 [-2,-1,3,4]，偶数值之和为 -2 + 4 = 2。
将 2 加到 A[3] 上之后，数组为 [-2,-1,3,6]，偶数值之和为 -2 + 6 = 4。

提示：
    1 <= A.length <= 10000
    -10000 <= A[i] <= 10000
    1 <= queries.length <= 10000
    -10000 <= queries[i][0] <= 10000
    0 <= queries[i][1] < A.length

• 解题思路

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

func sumEvenAfterQueries(A []int, queries [][]int) []int {
	res := make([]int, 0)
	sum := 0
	for _, value := range A {
		if value%2 == 0 {
			sum = sum + value
		}
	}
	for i := 0; i < len(queries); i++ {
		value := queries[i][0]
		index := queries[i][1]
		if A[index]%2 == 0 {
			sum = sum - A[index]
		}
		A[index] = A[index] + value
		if A[index]%2 == 0 {
			sum = sum + A[index]
		}
		res = append(res, sum)
	}
	return res
}

989.数组形式的整数加法(4)

• 题目

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
示例 1：输入：A = [1,2,0,0], K = 34 输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：
输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：
输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

示例 4：
输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000

提示：
    1 <= A.length <= 10000
    0 <= A[i] <= 9
    0 <= K <= 10000
    如果 A.length > 1，那么 A[0] != 0

• 解题思路

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

func addToArrayForm(A []int, K int) []int {
	B := make([]int, 0)
	for K > 0 {
		B = append([]int{K % 10}, B...)
		K = K / 10
	}
	length := len(A)
	if len(B) > len(A) {
		length = len(B)
	}
	res := make([]int, length)
	flag := 0
	i := len(A) - 1
	j := len(B) - 1
	count := 0
	for i >= 0 && j >= 0 {
		sum := A[i] + B[j] + flag
		if sum >= 10 {
			sum = sum - 10
			flag = 1
		} else {
			flag = 0
		}
		res[length-1-count] = sum
		i--
		j--
		count++
	}
	for i >= 0 {
		sum := A[i] + flag
		if sum >= 10 {
			sum = sum - 10
			flag = 1
		} else {
			flag = 0
		}
		res[length-1-count] = sum
		i--
		count++
	}
	for j >= 0 {
		sum := B[j] + flag
		if sum >= 10 {
			sum = sum - 10
			flag = 1
		} else {
			flag = 0
		}
		res[length-1-count] = sum
		j--
		count++
	}
	if flag == 1 {
		return append([]int{1}, res...)
	}
	return res
}

#
func addToArrayForm(A []int, K int) []int {
	A[len(A)-1] = A[len(A)-1] + K
	carry := 0
	for i := len(A) - 1; i >= 0; i-- {
		carry = A[i] / 10
		A[i] = A[i] % 10
		if i > 0 {
			A[i-1] = A[i-1] + carry
		}
	}
	for carry > 0 {
		A = append([]int{carry % 10}, A...)
		carry = carry / 10
	}
	return A
}

#
func addToArrayForm(A []int, K int) []int {
	i := len(A) - 1
	res := make([]int, 0)
	for i >= 0 || K > 0 {
		if i >= 0 {
			K = K + A[i]
		}
		res = append(res, K%10)
		K = K / 10
		i--
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

#
func addToArrayForm(A []int, K int) []int {
	i := len(A) - 1
	res := make([]int, 0)
	for i >= 0 || K > 0 {
		if i >= 0 {
			K = K + A[i]
		}
		res = append([]int{K % 10}, res...)
		K = K / 10
		i--
	}
	return res
}

993.二叉树的堂兄弟节点(2)

• 题目

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
示例 1：输入：root = [1,2,3,4], x = 4, y = 3 输出：false
示例 2：输入：root = [1,2,3,null,4,null,5], x = 5, y = 4 输出：true
示例 3：输入：root = [1,2,3,null,4], x = 2, y = 3 输出：false

提示：
    二叉树的节点数介于 2 到 100 之间。
    每个节点的值都是唯一的、范围为 1 到 100 的整数。

• 解题思路

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

func isCousins(root *TreeNode, x int, y int) bool {
	xNode, xDepth := dfs(root, x, 0)
	yNode, yDepth := dfs(root, y, 0)
	return xDepth == yDepth && xNode != yNode
}

func dfs(root *TreeNode, value int, level int) (*TreeNode, int) {
	if root == nil {
		return nil, -1
	}
	if root.Val == value {
		return nil, 0
	}
	if (root.Left != nil && root.Left.Val == value) ||
		(root.Right != nil && root.Right.Val == value) {
		return root, level + 1
	}
	leftNode, leftLevel := dfs(root.Left, value, level+1)
	if leftNode != nil {
		return leftNode, leftLevel
	}
	return dfs(root.Right, value, level+1)
}

#
func isCousins(root *TreeNode, x int, y int) bool {
	if root == nil {
		return true
	}
	fatherM := make(map[int]int)
	levelM := make(map[int]int)
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	level := 0
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			node := queue[i]
			levelM[node.Val] = level
			if node.Left != nil {
				fatherM[node.Left.Val] = node.Val
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				fatherM[node.Right.Val] = node.Val
				queue = append(queue, node.Right)
			}
		}
		queue = queue[length:]
		level++
	}
	return levelM[x] == levelM[y] && fatherM[x] != fatherM[y]
}

#
var fatherM map[int]int
var levelM map[int]int

func isCousins(root *TreeNode, x int, y int) bool {
	fatherM = make(map[int]int)
	levelM = make(map[int]int)
	dfs(root, nil, 0)
	return levelM[x] == levelM[y] && fatherM[x] != fatherM[y]
}

func dfs(root *TreeNode, father *TreeNode, level int) {
	if root == nil {
		return
	}
	if father == nil {
		fatherM[root.Val] = 0
	} else {
		fatherM[root.Val] = father.Val
	}
	levelM[root.Val] = level
	dfs(root.Left, root, level+1)
	dfs(root.Right, root, level+1)
}

997.找到小镇的法官(2)

• 题目

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：
    小镇的法官不相信任何人。
    每个人（除了小镇法官外）都信任小镇的法官。
    只有一个人同时满足属性 1 和属性 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。
示例 1：输入：N = 2, trust = [[1,2]] 输出：2
示例 2：输入：N = 3, trust = [[1,3],[2,3]] 输出：3
示例 3：输入：N = 3, trust = [[1,3],[2,3],[3,1]] 输出：-1
示例 4：输入：N = 3, trust = [[1,2],[2,3]] 输出：-1
示例 5：输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] 输出：3
提示：
    1 <= N <= 1000
    trust.length <= 10000
    trust[i] 是完全不同的
    trust[i][0] != trust[i][1]
    1 <= trust[i][0], trust[i][1] <= N

• 解题思路

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

func findJudge(N int, trust [][]int) int {
	arr := make([]int, N+1)
	for i := range trust {
		arr[trust[i][0]] = -1
		if arr[trust[i][1]] == -1 {
			continue
		}
		arr[trust[i][1]]++
	}
	for i := 1; i <= N; i++ {
		if arr[i] == N-1 {
			return i
		}
	}
	return -1
}

#
func findJudge(N int, trust [][]int) int {
	out := make([]int, N+1)
	in := make([]int, N+1)
	for i := range trust {
		out[trust[i][0]] = -1
		in[trust[i][1]]++
	}
	for i := 1; i <= N; i++ {
		// 出度为0，入度为N-1
		if out[i] == 0 && in[i] == N-1 {
			return i
		}
	}
	return -1
}

999.可以被一步捕获的棋子数(2)

• 题目

在一个 8 x 8 的棋盘上，有一个白色的车（Rook），用字符 'R' 表示。棋盘上还可能存在空方块，
白色的象（Bishop）以及黑色的卒（pawn），分别用字符 '.'，'B' 和 'p' 表示。
不难看出，大写字符表示的是白棋，小写字符表示的是黑棋。

车按国际象棋中的规则移动。东，西，南，北四个基本方向任选其一，然后一直向选定的方向移动，
直到满足下列四个条件之一：
    棋手选择主动停下来。
    棋子因到达棋盘的边缘而停下。
    棋子移动到某一方格来捕获位于该方格上敌方（黑色）的卒，停在该方格内。
    车不能进入/越过已经放有其他友方棋子（白色的象）的方格，停在友方棋子前。
你现在可以控制车移动一次，请你统计有多少敌方的卒处于你的捕获范围内（即，可以被一步捕获的棋子数）。
示例 1：输入：
[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],
[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],
[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：在本例中，车能够捕获所有的卒。
示例 2：输入：
[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],
[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],
[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],
[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：象阻止了车捕获任何卒。
示例 3：输入：
[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],
[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],
[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],
[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释： 车可以捕获位置 b5，d6 和 f5 的卒。
提示：
    board.length == board[i].length == 8
    board[i][j] 可以是 'R'，'.'，'B' 或 'p'
    只有一个格子上存在 board[i][j] == 'R'

• 解题思路

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

func numRookCaptures(board [][]byte) int {
	res := 0
	var x, y int
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == 'R' {
				x = i
				y = j
				break
			}
		}
	}
	// 向右
	for i := y; i < 8 && board[x][i] != 'B'; i++ {
		if board[x][i] == 'p' {
			res++
			break
		}
	}
	// 向左
	for i := y; i >= 0 && board[x][i] != 'B'; i-- {
		if board[x][i] == 'p' {
			res++
			break
		}
	}
	// 向下
	for i := x; i < 8 && board[i][y] != 'B'; i++ {
		if board[i][y] == 'p' {
			res++
			break
		}
	}
	// 向上
	for i := x; i >= 0 && board[i][y] != 'B'; i-- {
		if board[i][y] == 'p' {
			res++
			break
		}
	}
	return res
}

#
func numRookCaptures(board [][]byte) int {
	res := 0
	var x, y int
	var dx = []int{-1, 1, 0, 0}
	var dy = []int{0, 0, -1, 1}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == 'R' {
				x = i
				y = j
				break
			}
		}
	}
	for i := 0; i < 4; i++ {
		newX := x + dx[i]
		newY := y + dy[i]
		for newX >= 0 && newX < len(board) && newY >= 0 && newY < len(board[0]) {
			if board[newX][newY] == 'B' {
				break
			}
			if board[newX][newY] == 'p' {
				res++
				break
			}
			newX = newX + dx[i]
			newY = newY + dy[i]
		}
	}
	return res
}

0901-1000-Medium

901.股票价格跨度(1)

• 题目

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，
那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], 
[[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
提示：
    调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
    每个测试用例最多可以调用  10000 次 StockSpanner.next。
    在所有测试用例中，最多调用 150000 次 StockSpanner.next。
    此问题的总时间限制减少了 50%。

• 解题思路

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

type StockSpanner struct {
	prices []int
	count  []int
}

func Constructor() StockSpanner {
	return StockSpanner{
		prices: make([]int, 0),
		count:  make([]int, 0),
	}
}

func (this *StockSpanner) Next(price int) int {
	res := 1
	for len(this.prices) > 0 && this.prices[len(this.prices)-1] <= price {
		this.prices = this.prices[:len(this.prices)-1]
		temp := this.count[len(this.count)-1]
		this.count = this.count[:len(this.count)-1]
		res = res + temp
	}
	this.prices = append(this.prices, price)
	this.count = append(this.count, res)
	return res
}

904.水果成篮(1)

• 题目

在一排树中，第 i 棵树产生tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：
你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果树的最大总量是多少？
示例 1：输入：[1,2,1] 输出：3
解释：我们可以收集 [1,2,1]。
示例 2：输入：[0,1,2,2] 输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：输入：[1,2,3,2,2] 输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：输入：[3,3,3,1,2,1,1,2,3,3,4] 输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。
提示：1 <= tree.length <= 40000
0 <= tree[i] < tree.length

• 解题思路

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

func totalFruit(tree []int) int {
	res := 0
	m := make(map[int]int)
	left := 0
	total := 0
	for i := 0; i < len(tree); i++ {
		target := tree[i]
		if _, ok := m[target]; ok {
			m[target]++
		} else {
			for len(m) >= 2 {
				m[tree[left]]--
				total--
				if m[tree[left]] == 0 {
					delete(m, tree[left])
				}
				left++
			}
			m[target] = 1
		}
		total++
		if total > res {
			res = total
		}
	}
	return res
}

907.子数组的最小值之和(3)

• 题目

给定一个整数数组 A，找到 min(B)的总和，其中 B 的范围为A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
示例：输入：[3,1,2,4] 输出：17
解释：子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
提示：1 <= A <= 30000
1 <= A[i] <= 30000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	分治-超时	O(nlog(n))	O(log(n))
02	单调栈	O(n)	O(n)
03	单调栈	O(n)	O(n)
04	中心扩展	O(n^2)	O(1)

func sumSubarrayMins(arr []int) int {
	if len(arr) == 0 {
		return 0
	}
	if len(arr) == 1 {
		return arr[0]
	}
	index := findMinValue(arr)
	left := index
	right := len(arr) - 1 - index
	// 1是自己，left是左边left个数+自己，right是右边right个数+自己，left*right是左边+自己+右边的个数
	count := 1 + left + right + left*right
	res := arr[index] * count % 1000000007
	res = res + sumSubarrayMins(arr[:index]) // 左边
	if index < len(arr)-1 {
		res = res + sumSubarrayMins(arr[index+1:]) // 右边
	}
	return res % 1000000007
}

func findMinValue(arr []int) int {
	minValue := arr[0]
	minIndex := 0
	for i := 1; i < len(arr); i++ {
		if arr[i] < minValue {
			minValue = arr[i]
			minIndex = i
		}
	}
	return minIndex
}

# 2
func sumSubarrayMins(arr []int) int {
	res := 0
	stack := make([]int, 0) // 递增栈
	stack = append(stack, -1)
	total := 0
	for i := 0; i < len(arr); i++ {
		for len(stack) > 1 && arr[i] < arr[stack[len(stack)-1]] { // 小于栈顶
			prev := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			total = total - arr[prev]*(prev-stack[len(stack)-1])
		}
		stack = append(stack, i)
		total = total + arr[i]*(i-stack[len(stack)-2])
		res = (res + total) % 1000000007
	}
	return res % 1000000007
}

# 3
func sumSubarrayMins(arr []int) int {
	res := 0
	stack := make([][2]int, 0) // 递增栈
	sum := 0
	for i := 0; i < len(arr); i++ {
		count := 1
		for len(stack) > 0 && arr[i] < stack[len(stack)-1][0] { // 小于栈顶
			prev := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			sum = sum - prev[0]*prev[1]
			count = count + prev[1]
		}
		stack = append(stack, [2]int{arr[i], count})
		sum = sum + arr[i]*count
		res = (res + sum) % 1000000007
	}
	return res % 1000000007
}

# 4
func sumSubarrayMins(arr []int) int {
	res := 0
	for i := 0; i < len(arr); i++ {
		left, right := i-1, i+1
		for ; left >= 0; left-- {
			if arr[left] < arr[i] {
				break
			}
		}
		for ; right < len(arr); right++ {
			if arr[right] <= arr[i] { // 注意边界
				break
			}
		}
		sum := arr[i] * (i - left) * (right - i)
		res = (res + sum) % 1000000007
	}
	return res % 1000000007
}

909.蛇梯棋(1)

• 题目

N x N 的棋盘board 上，按从1 到 N*N的数字给方格编号，编号 从左下角开始，每一行交替方向。
例如，一块 6 x 6 大小的棋盘，编号如下：
r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；
如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。
玩家从棋盘上的方格1 （总是在最后一行、第一列）开始出发。
每一回合，玩家需要从当前方格 x 开始出发，按下述要求前进：
选定目标方格：选择从编号 x+1，x+2，x+3，x+4，x+5，或者 x+6 的方格中选出一个目标方格 s ，目标方格的编号 <= N*N。
该选择模拟了掷骰子的情景，无论棋盘大小如何，你的目的地范围也只能处于区间 [x+1, x+6] 之间。
传送玩家：如果目标方格 S 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 S。
注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，你也不会继续移动。
返回达到方格 N*N 所需的最少移动次数，如果不可能，则返回 -1。
示例：输入：[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
输出：4
解释：首先，从方格 1 [第 5 行，第 0 列] 开始。
你决定移动到方格 2，并必须爬过梯子移动到到方格 15。
然后你决定移动到方格 17 [第 3 行，第 5 列]，必须爬过蛇到方格 13。
然后你决定移动到方格 14，且必须通过梯子移动到方格 35。
然后你决定移动到方格 36, 游戏结束。
可以证明你需要至少 4 次移动才能到达第 N*N 个方格，所以答案是 4。
提示：2 <= board.length = board[0].length<= 20
board[i][j]介于1和N*N之间或者等于-1。
编号为1的方格上没有蛇或梯子。
编号为N*N的方格上没有蛇或梯子。

• 解题思路

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

func snakesAndLadders(board [][]int) int {
	n := len(board)
	m := make(map[int]int) // 保存到达坐标对应的移动次数
	m[1] = 0
	queue := make([]int, 0)
	queue = append(queue, 1)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == n*n {
			return m[node]
		}
		for i := node + 1; i <= node+6 && i <= n*n; i++ {
			_, a, b := getIndex(i, n)
			next := -1
			if board[a][b] == -1 {
				next = i
			} else {
				next = board[a][b]
			}
			if _, ok := m[next]; !ok {
				m[next] = m[node] + 1
				queue = append(queue, next)
			}
		}
	}
	return -1
}

func getIndex(i int, n int) (int, int, int) {
	var x, y int
	x = (i - 1) / n // 行
	y = (i - 1) % n // 列
	if x%2 == 1 { // 奇数行需要反转
		y = n - 1 - y // 反转
	}
	x = n - 1 - x // 反转
	return x*n + y, x, y
}

910.最小差值II(1)

• 题目

给你一个整数数组 A，对于每个整数 A[i]，可以选择x = -K或是x = K （K 总是非负整数），
并将x加到A[i]中。
在此过程之后，得到数组B。
返回 B的最大值和 B的最小值之间可能存在的最小差值。
示例 1：输入：A = [1], K = 0 输出：0
解释：B = [1]
示例 2：输入：A = [0,10], K = 2 输出：6
解释：B = [2,8]
示例 3：输入：A = [1,3,6], K = 3 输出：3
解释：B = [4,6,3]
提示：1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

• 解题思路

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

func smallestRangeII(A []int, K int) int {
	sort.Ints(A)
	n := len(A)
	res := A[n-1] - A[0]
	// 排序后，为了最小差值，必定是A[0,i]+K,A[i+1:]-K
	// 最小值落在A[0]+K，A[i+1]-K之中
	// 最大值落在A[n-1]-K，A[i]+K之中
	for i := 0; i < n-1; i++ {
		minValue := min(A[0]+K, A[i+1]-K)
		maxValue := max(A[n-1]-K, A[i]+K)
		res = min(maxValue-minValue, res)
	}
	return res
}

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
}

911.在线选举(2)

• 题目

在选举中，第i张票是在时间为times[i]时投给persons[i]的。
现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在t 时刻主导选举的候选人的编号。
在t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
示例：输入：["TopVotedCandidate","q","q","q","q","q","q"], 
[[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
输出：[null,0,1,1,0,0,1]
解释：时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。
时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。
时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。
在时间 15、24 和 8 处继续执行 3 个查询。
提示：1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times是严格递增的数组，所有元素都在[0, 10^9]范围中。
每个测试用例最多调用10000次TopVotedCandidate.q。
TopVotedCandidate.q(int t)被调用时总是满足t >= times[0]。

• 解题思路

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

type TopVotedCandidate struct {
	result []int // 存放对应时间的候选人
	times  []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	n := len(persons)
	arr := make([]int, n+1)
	maxCount := 0
	index := persons[0]
	res := make([]int, n)
	for i := 0; i < n; i++ {
		id := persons[i]
		arr[id]++
		if arr[id] >= maxCount {
			maxCount = arr[id]
			index = id
		}
		res[i] = index
	}
	return TopVotedCandidate{
		result: res,
		times:  times,
	}
}

func (this *TopVotedCandidate) Q(t int) int {
	left, right := 0, len(this.times)
	for left < right {
		mid := left + (right-left)/2
		if this.times[mid] == t {
			return this.result[mid]
		} else if this.times[mid] > t {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return this.result[left-1]
}

# 2
type TopVotedCandidate struct {
	result []int // 存放对应时间的候选人
	times  []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	n := len(persons)
	arr := make([]int, n+1)
	maxCount := 0
	index := persons[0]
	res := make([]int, n)
	for i := 0; i < n; i++ {
		id := persons[i]
		arr[id]++
		if arr[id] >= maxCount {
			maxCount = arr[id]
			index = id
		}
		res[i] = index
	}
	return TopVotedCandidate{
		result: res,
		times:  times,
	}
}

func (this *TopVotedCandidate) Q(t int) int {
	left, right := 0, len(this.times)-1
	for left <= right {
		mid := left + (right-left)/2
		if this.times[mid] > t {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return this.result[left-1]
}

912.排序数组(7)

• 题目

给你一个整数数组 nums，请你将该数组升序排列。
示例 1：输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：1 <= nums.length <= 50000
    -50000 <= nums[i] <= 50000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(nlog(n))	O(1)
02	插入排序	O(n^2)	O(1)
03	希尔排序	O(n^1.3)	O(1)
04	归并排序	O(nlog(n))	O(n)
05	快速排序	O(nlog(n))	O(log(n))
06	堆排序-内置heap	O(nlog(n))	O(n)
07	堆排序	O(nlog(n))	O(log(n))

func sortArray(nums []int) []int {
	sort.Ints(nums)
	return nums
}

# 2
func sortArray(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		pos := i - 1 // 已经有序的最后一个下标
		cur := nums[i]
		for pos >= 0 && nums[pos] > cur {
			nums[pos+1] = nums[pos] // 后移
			pos--
		}
		nums[pos+1] = cur
	}
	return nums
}

# 3
func sortArray(nums []int) []int {
	n := len(nums)
	for gap := n / 2; gap > 0; gap = gap / 2 {
		for i := gap; i < n; i++ {
			j := i
			cur := nums[i]
			for j-gap >= 0 && cur < nums[j-gap] {
				nums[j] = nums[j-gap]
				j = j - gap
			}
			nums[j] = cur
		}
	}
	return nums
}

# 4
func sortArray(nums []int) []int {
	n := len(nums)
	if n < 2 {
		return nums
	}
	return merge(sortArray(nums[:len(nums)/2]), sortArray(nums[len(nums)/2:]))
}

func merge(left, right []int) []int {
	res := make([]int, 0)
	for len(left) > 0 && len(right) > 0 {
		if left[0] <= right[0] {
			res = append(res, left[0])
			left = left[1:]
		} else {
			res = append(res, right[0])
			right = right[1:]
		}
	}
	if len(left) > 0 {
		res = append(res, left...)
	}
	if len(right) > 0 {
		res = append(res, right...)
	}
	return res
}

# 5
func sortArray(nums []int) []int {
	quick(nums, 0, len(nums)-1)
	return nums
}

func quick(arr []int, left, right int) {
	if left >= right {
		return
	}
	index := partition(arr, left, right)
	quick(arr, left, index-1)
	quick(arr, index+1, right)
}

func partition(arr []int, left, right int) int {
	baseValue := arr[left] // 基准值
	for left < right {
		for baseValue <= arr[right] && left < right {
			right-- // 依次查找大于基准值的位置
		}
		arr[left] = arr[right]
		for arr[left] <= baseValue && left < right {
			left++ // 依次查找小于基准值的位置
		}
		arr[right] = arr[left]
	}
	arr[right] = baseValue
	return right
}

# 6
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 sortArray(nums []int) []int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < len(nums); i++ {
		heap.Push(&intHeap, nums[i])
	}
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		value := heap.Pop(&intHeap).(int)
		res = append(res, value)
	}
	return res
}

# 7
func sortArray(nums []int) []int {
	buildHeap(nums, len(nums))
	for i := len(nums) - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		heapModify(nums, 0, i-1)
	}
	return nums
}

func buildHeap(arr []int, length int) {
	for i := len(arr)/2 - 1; i >= 0; i-- {
		heapModify(arr, i, length-1)
	}
}

func heapModify(arr []int, start, end int) {
	temp := arr[start]
	for left := 2*start + 1; left <= end; left = 2*left + 1 {
		if left < end && arr[left] < arr[left+1] {
			left++
		}
		if arr[start] < arr[left] {
			arr[start] = arr[left]
			start = left
		}
		arr[start] = temp
	}
}

915.分割数组(2)

• 题目

给定一个数组A，将其划分为两个不相交（没有公共元素）的连续子数组left和right，使得：
left中的每个元素都小于或等于right中的每个元素。
left 和right都是非空的。
left要尽可能小。
在完成这样的分组后返回left的长度。可以保证存在这样的划分方法。
示例 1：输入：[5,0,3,8,6] 输出：3
解释：left = [5,0,3]，right = [8,6]
示例 2：输入：[1,1,1,0,6,12] 输出：4
解释：left = [1,1,1,0]，right = [6,12]
提示：2 <= A.length<= 30000
0 <= A[i] <= 10^6
可以保证至少有一种方法能够按题目所描述的那样对 A 进行划分。

• 解题思路

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

func partitionDisjoint(A []int) int {
	n := len(A)
	maxLeft := make([]int, n)
	minRight := make([]int, n)
	maxValue := A[0]
	for i := 0; i < n; i++ {
		if maxValue < A[i] {
			maxValue = A[i]
		}
		maxLeft[i] = maxValue
	}
	minValue := A[n-1]
	for i := n - 1; i >= 0; i-- {
		if minValue > A[i] {
			minValue = A[i]
		}
		minRight[i] = minValue
	}
	for i := 1; i < n; i++ {
		if maxLeft[i-1] <= minRight[i] {
			return i
		}
	}
	return -1
}

# 2
func partitionDisjoint(A []int) int {
	n := len(A)
	res := 0
	maxLeft := A[0]
	maxValue := A[0]
	for i := 1; i < n; i++ {
		maxValue = max(maxValue, A[i])
		if A[i] < maxLeft {
			res = i
			maxLeft = maxValue
		}
	}
	return res + 1
}

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

916.单词子集(1)

• 题目

我们给出两个单词数组 A和B。每个单词都是一串小写字母。
现在，如果b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 
例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。
如果对 B 中的每一个单词b，b 都是 a 的子集，那么我们称A 中的单词 a 是通用的。
你可以按任意顺序以列表形式返回A 中所有的通用单词。
示例 1： 输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]
示例 2：输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出：["apple","google","leetcode"]
示例 3：输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]
示例 4：输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出：["google","leetcode"]
示例 5：输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出：["facebook","leetcode"]
提示：1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length<= 10
A[i]和B[i]只由小写字母组成。
A[i]中所有的单词都是独一无二的，也就是说不存在i != j使得A[i] == A[j]。

• 解题思路

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

func wordSubsets(A []string, B []string) []string {
	maxArr := make([]int, 26) // B中的字母的最大频次
	for i := 0; i < len(B); i++ {
		temp := count(B[i])
		for i := 0; i < 26; i++ {
			maxArr[i] = max(maxArr[i], temp[i])
		}
	}
	res := make([]string, 0)
	for i := 0; i < len(A); i++ {
		temp := count(A[i])
		flag := true
		for i := 0; i < 26; i++ {
			if temp[i] < maxArr[i] {
				flag = false
				break
			}
		}
		if flag == true {
			res = append(res, A[i])
		}
	}
	return res
}

func count(str string) [26]int {
	arr := [26]int{}
	for i := 0; i < len(str); i++ {
		arr[str[i]-'a']++
	}
	return arr
}

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

918.环形子数组的最大和(1)

• 题目

给定一个由整数数组 A表示的环形数组 C，求 C的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。
（形式上，当0 <= i < A.length时C[i] = A[i]，且当i >= 0时C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A中的每个元素一次。
（形式上，对于子数组C[i], C[i+1], ..., C[j]，
不存在i <= k1, k2 <= j其中k1 % A.length= k2 % A.length）
示例 1：输入：[1,-2,3,-2] 输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：输入：[5,-3,5] 输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：输入：[3,-1,2,-1] 输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：输入：[3,-2,2,-3] 输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：输入：[-2,-3,-1] 输出：-1
解释：从子数组 [-1] 得到最大和 -1
提示：-30000 <= A[i] <= 30000
1 <= A.length <= 30000

• 解题思路

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

func maxSubarraySumCircular(A []int) int {
	n := len(A)
	// leetcode53.最大子序和 的变形
	total := A[0]                  // 总和
	minValue, sumMin := A[0], A[0] // 找到连续数组之和的最小值
	maxValue, sumMax := A[0], A[0] // 找到连续数组之和的最大值
	for i := 1; i < n; i++ {
		total = total + A[i]
		sumMin = min(sumMin+A[i], A[i])
		minValue = min(minValue, sumMin)
		sumMax = max(sumMax+A[i], A[i])
		maxValue = max(maxValue, sumMax)
	}
	// 2种情况：取最大值即可
	// 1：目标数组不需要环，求最大值
	// 2: 需要成环，总和减去最小值
	if total == minValue { // 极端情况全小于0：如果和=最小值，返回最大值
		return maxValue
	}
	return max(maxValue, total-minValue)
}

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

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

919.完全二叉树插入器(1)

• 题目

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root)使用头节点为root的给定树初始化该数据结构；
CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。
使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的头节点。
示例 1：输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]] 输出：[null,1,[1,2]]
示例 2：输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]
提示：最初给定的树是完全二叉树，且包含1到1000个节点。
每个测试用例最多调用CBTInserter.insert 操作10000次。
给定节点或插入节点的每个值都在0到5000之间。

• 解题思路

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

type CBTInserter struct {
	root *TreeNode
	arr  []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
	arr := make([]*TreeNode, 0)
	queue := make([]*TreeNode, 0)
	arr = append(arr, root)
	queue = append(queue, root)
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
				arr = append(arr, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
				arr = append(arr, queue[i].Right)
			}
		}
		queue = queue[length:]
	}
	return CBTInserter{root: root, arr: arr}
}

func (this *CBTInserter) Insert(v int) int {
	newNode := &TreeNode{Val: v}
	this.arr = append(this.arr, newNode)
	n := len(this.arr)
	target := this.arr[n/2-1]
	if n%2 == 0 {
		target.Left = newNode
	} else {
		target.Right = newNode
	}
	return target.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
	return this.root
}

921.使括号有效的最少添加(3)

• 题目

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），
以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
    它是一个空字符串，或者
    它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
    它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：输入："())" 输出：1
示例 2：输入："(((" 输出：3
示例 3：输入："()" 输出：0
示例 4：输入："()))((" 输出：4
提示：S.length <= 1000  S 只包含 '(' 和 ')' 字符。

• 解题思路

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

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

# 2
func minAddToMakeValid(S string) int {
	left := 0
	right := 0
	for i := 0; i < len(S); i++ {
		if S[i] == '(' {
			left++
		} else {
			if left > 0 {
				left--
			} else {
				right++
			}
		}
	}
	return left + right
}

# 3
func minAddToMakeValid(S string) int {
	for strings.Contains(S, "()") == true {
		S = strings.ReplaceAll(S, "()", "")
	}
	return len(S)
}

923.三数之和的多种可能(4)

• 题目

给定一个整数数组A，以及一个整数target作为目标值，
返回满足 i < j < k 且A[i] + A[j] + A[k] == target的元组i, j, k的数量。
由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。
示例 1：输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8 输出：20
解释：按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。
示例 2：输入：A = [1,1,2,2,2,2], target = 5 输出：12
解释：A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。
提示：3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序双指针	O(n^2)	O(1)
02	数学	O(1)	O(1)
03	哈希辅助	O(n^2)	O(n)
04	动态规划	O(n^2)	O(n^2)

func threeSumMulti(arr []int, target int) int {
	res := 0
	sort.Ints(arr)
	for i := 0; i < len(arr)-2; i++ {
		targetTemp := target - arr[i]
		j := i + 1
		k := len(arr) - 1
		for j < k {
			if arr[j]+arr[k] < targetTemp {
				j++
			} else if arr[j]+arr[k] > targetTemp {
				k--
			} else {
				if arr[j] != arr[k] { // 2数不重复
					left, right := 1, 1
					for j+1 < k && arr[j] == arr[j+1] {
						left++
						j++
					}
					for j+1 < k && arr[k] == arr[k-1] {
						right++
						k--
					}
					res = (res + left*right) % 1000000007
					j++
					k--
				} else { // 2数重复
					res = (res + (k-j+1)*(k-j)/2) % 1000000007
					break
				}
			}
		}
	}
	return res % 1000000007
}

# 2
func threeSumMulti(arr []int, target int) int {
	res := 0
	countArr := make([]int, 101)
	for i := 0; i < len(arr); i++ {
		countArr[arr[i]]++
	}
	for i := 0; i <= 100; i++ {
		// i < j < k
		for j := i + 1; j <= 100; j++ {
			k := target - i - j
			if j < k && k <= 100 {
				res = (res + countArr[i]*countArr[j]*countArr[k]) % 1000000007
			}
		}
		// i == j < k
		k := target - 2*i
		if i < k && k <= 100 {
			res = (res + countArr[i]*(countArr[i]-1)/2*countArr[k]) % 1000000007
		}
		// i < j == k
		if (target-i)%2 == 0 {
			j := (target - i) / 2
			if i < j && j <= 100 {
				res = (res + countArr[i]*countArr[j]*(countArr[j]-1)/2) % 1000000007
			}
		}
	}
	// i==j==k
	if target%3 == 0 {
		i := target / 3
		if 0 <= i && i <= 100 {
			res = (res + countArr[i]*(countArr[i]-1)*(countArr[i]-2)/6) % 1000000007
		}
	}
	return res % 1000000007
}

# 3
func threeSumMulti(arr []int, target int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(arr); i++ {
		res = (res + m[target-arr[i]]) % 1000000007 // 以当前i为k，求有多少i+j
		for j := 0; j < i; j++ {
			m[arr[i]+arr[j]]++
		}
	}
	return res % 1000000007
}

# 4
func threeSumMulti(arr []int, target int) int {
	n := len(arr)
	dp := make([][4][]int, n+1) // 虑前i个数时，从中选出j个数，组成k大小的方案数
	for i := 0; i <= n; i++ {
		dp[i] = [4][]int{}
		for j := 0; j < 4; j++ {
			dp[i][j] = make([]int, target+1)
		}
	}
	for i := 0; i <= n; i++ {
		dp[i][0][0] = 1
	}
	for i := 1; i <= n; i++ {
		for j := 1; j < 4; j++ {
			for k := 0; k <= target; k++ {
				if k >= arr[i-1] { // 可选
					dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k-arr[i-1]]) % 1000000007
				}
				dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k]) % 1000000007 // 不选
			}
		}
	}
	return dp[n][3][target]
}

926.将字符串翻转到单调递增(3)

• 题目

如果一个由'0' 和 '1'组成的字符串，
是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。
我们给出一个由字符 '0' 和 '1'组成的字符串S，我们可以将任何'0' 翻转为'1'或者将'1'翻转为'0'。
返回使 S 单调递增的最小翻转次数。
示例 1：输入："00110" 输出：1
解释：我们翻转最后一位得到 00111.
示例 2：输入："010110" 输出：2
解释：我们翻转得到 011111，或者是 000111。
示例 3：输入："00011000" 输出：2
解释：我们翻转得到 00000000。
提示：1 <= S.length <= 20000
S 中只包含字符'0'和'1'

• 解题思路

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

func minFlipsMonoIncr(S string) int {
   n := len(S)
   dpA := make([]int, n) // 0 结尾
   dpB := make([]int, n) // 1 结尾
   if S[0] == '1' {
   	dpA[0] = 1
   } else {
   	dpB[0] = 1
   }
   for i := 1; i < n; i++ {
   	if S[i] == '1' {
   		dpA[i] = dpA[i-1] + 1            // 需要改为0
   		dpB[i] = min(dpB[i-1], dpA[i-1]) // 1结尾和0结尾的最小值
   	} else {
   		dpA[i] = dpA[i-1]                    // 不需要改为0
   		dpB[i] = min(dpB[i-1], dpA[i-1]) + 1 // 1结尾和0结尾的最小值+1
   	}
   }
   return min(dpA[n-1], dpB[n-1])
}

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

# 2
func minFlipsMonoIncr(S string) int {
   n := len(S)
   a := 0 // 0 结尾
   b := 0 // 1 结尾
   if S[0] == '1' {
   	a = 1
   } else {
   	b = 1
   }
   for i := 1; i < n; i++ {
   	if S[i] == '1' {
   		a, b = a+1, min(a, b)
   	} else {
   		a, b = a, min(a, b)+1
   	}
   }
   return min(a, b)
}

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

# 3
func minFlipsMonoIncr(S string) int {
   n := len(S)
   arr := make([]int, n+1)
   for i := 1; i <= n; i++ {
   	arr[i] = arr[i-1]
   	if S[i-1] == '1' {
   		arr[i]++
   	}
   }
   res := n
   for i := 0; i <= n; i++ {
   	left := arr[i]
   	right := n - i - (arr[n] - arr[i])
   	res = min(res, left+right)
   }
   return res
}

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

930.和相同的二元子数组(3)

• 题目

在由若干0和1 组成的数组A中，有多少个和为 S的非空子数组。
示例：输入：A = [1,0,1,0,1], S = 2 输出：4
解释： 如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
提示：A.length <= 30000
0 <= S <= A.length
A[i]为0或1

• 解题思路

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

func numSubarraysWithSum(A []int, S int) int {
	m := make(map[int]int)
	res := 0
	sum := 0
	for i := 0; i < len(A); i++ {
		sum = sum + A[i]
		if sum == S {
			res++
		}
		res = res + m[sum-S]
		m[sum]++
	}
	return res
}

# 2
func numSubarraysWithSum(A []int, S int) int {
	m := make(map[int]int)
	res := 0
	sum := 0
	m[0] = 1
	for i := 0; i < len(A); i++ {
		sum = sum + A[i]
		res = res + m[sum-S]
		m[sum]++
	}
	return res
}

# 3
func numSubarraysWithSum(A []int, S int) int {
	res := 0
	sum := 0
	left := 0
	for i := 0; i < len(A); i++ {
		sum = sum + A[i]
		if sum > S { // 左指针右移
			for left < i && sum != S {
				sum = sum - A[left]
				left++
			}
		}
		if S == sum {
			tempSum := sum
			j := left
			for j <= i && tempSum == S { // 以该节点为结尾有多少个子数组sum==S
				res++
				tempSum = tempSum - A[j]
				j++
			}
		}
	}
	return res
}

931.下降路径最小和(2)

• 题目

给你一个 n x n 的 方形 整数数组matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
具体来说，位置 (row, col) 的下一个元素应当是 
(row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13
解释：下面是两条和最小的下降路径，用加粗标注：
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]
示例 2：输入：matrix = [[-19,57],[-40,-5]] 输出：-59
解释：下面是一条和最小的下降路径，用加粗标注：
[[-19,57],
 [-40,-5]]
示例 3：输入：matrix = [[-48]] 输出：-48
提示：n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

• 解题思路

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

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

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

# 2
func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i == 0 {
				dp[i][j] = matrix[i][j]
				continue
			}
			minValue := dp[i-1][j]
			if j > 0 {
				minValue = min(minValue, dp[i-1][j-1])
			}
			if j < n-1 {
				minValue = min(minValue, dp[i-1][j+1])
			}
			dp[i][j] = dp[i][j] + minValue + matrix[i][j]
		}
	}
	res := dp[n-1][0]
	for i := 0; i < n; i++ {
		res = min(res, dp[n-1][i])
	}
	return res
}

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

932.漂亮数组(3)

• 题目

对于某些固定的N，如果数组A是整数1, 2, ..., N组成的排列，使得：
对于每个i < j，都不存在k 满足i < k < j使得A[k] * 2 = A[i] + A[j]。
那么数组 A是漂亮数组。
给定N，返回任意漂亮数组A（保证存在一个）。
示例 1：输入：4 输出：[2,1,4,3]
示例 2：输入：5 输出：[3,1,2,5,4]
提示：1 <= N <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n^2)	O(n^2)
02	递归	O(n^2)	O(n^2)
03	位排序	O(nlog(n))	O(n)

var m map[int][]int

func beautifulArray(N int) []int {
	m = make(map[int][]int)
	return dfs(N)
}

func dfs(n int) []int {
	if v, ok := m[n]; ok {
		return v
	}
	res := make([]int, n)
	if n == 1 {
		res[0] = 1
	} else {
		// A[k] * 2 = A[i] + A[j], i < k < j
		// 要想等式恒不成立，一个简单的办法就是让i部分的数都是奇数，j部分的数都是偶数。
		index := 0
		for _, v := range dfs((n + 1) / 2) { // 1-N中有(N+1)/2个奇数
			res[index] = 2*v - 1
			index++
		}
		for _, v := range dfs(n / 2) { // 1-N中有N/2个偶数
			res[index] = 2 * v
			index++
		}
	}
	m[n] = res
	return res
}

# 2
func beautifulArray(N int) []int {
	if N == 1 {
		return []int{1}
	}
	res := make([]int, 0)
	a := beautifulArray((N + 1) / 2)
	b := beautifulArray(N / 2)
	for i := 0; i < len(a); i++ {
		res = append(res, a[i]*2-1)
	}
	for i := 0; i < len(b); i++ {
		res = append(res, b[i]*2)
	}
	return res
}

# 3
func beautifulArray(N int) []int {
	res := make([]int, N)
	for i := 0; i < N; i++ {
		res[i] = i + 1
	}
	sort.Slice(res, func(i, j int) bool {
		k := 0
		for res[i]&k == res[j]&k {
			k++
		}
		return res[i]&k < res[j]&k
	})
	return res
}

934.最短的桥(1)

• 题目

在给定的二维二进制数组A中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将0变为1，以使两座岛连接起来，变成一座岛。
返回必须翻转的0 的最小数目。（可以保证答案至少是 1 。）
示例 1：输入：A = [[0,1],[1,0]] 输出：1
示例 2：输入：A = [[0,1,0],[0,0,0],[0,0,1]] 输出：2
示例 3：输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] 输出：1
提示：2 <= A.length == A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1

• 解题思路

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

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

func shortestBridge(grid [][]int) int {
	n = len(grid)
	queue = make([][2]int, 0)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				dfs(grid, i, j)  // 深度优先搜索找边界
				return bfs(grid) // 广度优先搜索找距离
			}
		}
	}
	return 0
}

func dfs(grid [][]int, i, j int) {
	if i < 0 || i >= n || j < 0 || j >= n {
		return
	}
	if grid[i][j] == 0 {
		queue = append(queue, [2]int{i, j}) // 加入边界
	} else if grid[i][j] == 1 {
		grid[i][j] = 2 // 标记为2
		for k := 0; k < 4; k++ {
			x, y := i+dx[k], j+dy[k]
			dfs(grid, x, y)
		}
	}
}

func bfs(grid [][]int) int {
	res := 0
	for len(queue) > 0 {
		res++
		length := len(queue)
		for i := 0; i < length; i++ {
			a, b := queue[i][0], queue[i][1]
			for j := 0; j < 4; j++ {
				x, y := a+dx[j], b+dy[j]
				if 0 <= x && x < n && 0 <= y && y < n {
					if grid[x][y] == 2 {
						continue
					}
					if grid[x][y] == 1 {
						return res
					}
					queue = append(queue, [2]int{x, y})
					grid[x][y] = 2
				}
			}
		}
		queue = queue[length:]
	}
	return res
}

935.骑士拨号器(1)

• 题目

国际象棋中的骑士可以按下图所示进行移动：.     
这一次，我们将“骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳N-1 步。
每一步必须是从一个数字键跳到另一个数字键。
每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下N 位数字。
你能用这种方式拨出多少个不同的号码？
因为答案可能很大，所以输出答案模10^9 + 7。
示例 1：输入：1 输出：10
示例 2：输入：2 输出：20
示例 3：输入：3 输出：46
提示：1 <= N <= 5000

• 解题思路

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

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

939.最小面积矩形(2)

• 题目

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：输入：[[1,1],[1,3],[3,1],[3,3],[2,2]] 输出：4
示例 2：输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] 输出：2
提示：1 <= points.length <= 500
0 <=points[i][0] <=40000
0 <=points[i][1] <=40000
所有的点都是不同的。

• 解题思路

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

func minAreaRect(points [][]int) int {
	res := math.MaxInt32
	m := make(map[string]bool)
	n := len(points)
	for i := 0; i < n; i++ {
		a, b := points[i][0], points[i][1]
		m[fmt.Sprintf("%d,%d", a, b)] = true
	}
	for i := 0; i < n; i++ {
		a, b := points[i][0], points[i][1]
		for j := i + 1; j < n; j++ {
			c, d := points[j][0], points[j][1]
			if a == c || b == d {
				continue
			}
			area := abs((a - c) * (b - d))
			target1 := fmt.Sprintf("%d,%d", a, d) // 枚举另外2个点
			target2 := fmt.Sprintf("%d,%d", c, b)
			if area < res && m[target1] == true && m[target2] == true {
				res = area
			}
		}
	}
	if res == math.MaxInt32 {
		return 0
	}
	return res
}

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

# 2
func minAreaRect(points [][]int) int {
	res := math.MaxInt32
	m := make(map[int][]int)
	n := len(points)
	for i := 0; i < n; i++ {
		a, b := points[i][0], points[i][1]
		m[a] = append(m[a], b) // 列分组
	}
	rows := make([]int, 0)
	for k := range m {
		rows = append(rows, k)
	}
	sort.Ints(rows)
	prevM := make(map[string]int)
	for _, v := range rows { // 按列枚举
		arr := m[v]
		sort.Ints(arr)
		for i := 0; i < len(arr); i++ {
			for j := i + 1; j < len(arr); j++ {
				y1, y2 := arr[i], arr[j]
				target := fmt.Sprintf("%d,%d", y1, y2)
				if index, ok := prevM[target]; ok {
					area := (y2 - y1) * (v - index)
					res = min(res, area)
				}
				prevM[target] = v
			}
		}
	}
	if res == math.MaxInt32 {
		return 0
	}
	return res
}

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

945.使数组唯一的最小增量(3)

• 题目

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。
示例 1:输入：[1,2,2] 输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
示例 2:输入：[3,2,1,2,1,7] 输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示：
    0 <= A.length <= 40000
    0 <= A[i] < 40000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序遍历	O(nlog(n))	O(1)
02	计数	O(n)	O(n)
03	状态探测-递归	O(n)	O(n)

func minIncrementForUnique(A []int) int {
	res := 0
	sort.Ints(A)
	for i := 0; i < len(A)-1; i++ {
		if A[i] >= A[i+1] {
			value := A[i] - A[i+1] + 1
			res = res + value
			A[i+1] = A[i+1] + value
		}
	}
	return res
}

# 2
func minIncrementForUnique(A []int) int {
	res := 0
	arr := make([]int, 80001)
	for i := 0; i < len(A); i++ {
		arr[A[i]]++
	}
	sum := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] >= 2 {
			sum = sum + arr[i] - 1
			res = res - i*(arr[i]-1)
		} else if arr[i] == 0 && sum > 0 {
			sum--
			res = res + i
		}
	}
	return res
}

# 3
var arr []int

func minIncrementForUnique(A []int) int {
	res := 0
	arr = make([]int, 21)
	for i := 0; i < len(arr); i++ {
		arr[i] = -1
	}
	for i := 0; i < len(A); i++ {
		b := findNext(A[i])
		res = res + b - A[i]
	}
	return res
}

func findNext(a int) int {
	b := arr[a]
	if b == -1 {
		arr[a] = a
		return a
	}
	b = findNext(b + 1)
	arr[a] = b
	return b
}

946.验证栈序列(2)

• 题目

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，
只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false
解释：1 不能在 2 之前弹出。
提示：
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。

• 解题思路

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

func validateStackSequences(pushed []int, popped []int) bool {
	stack := make([]int, 0)
	j := 0
	for i := 0; i < len(pushed); i++ {
		stack = append(stack, pushed[i])
		for len(stack) > 0 && stack[len(stack)-1] == popped[j] {
			stack = stack[:len(stack)-1]
			j++
		}
	}
	if len(stack) == 0 {
		return true
	}
	return false
}

# 2
func validateStackSequences(pushed []int, popped []int) bool {
	stack := make([]int, 0)
	res := false
	i := 0
	j := 0
	for j < len(popped) {
		for len(stack) == 0 || stack[len(stack)-1] != popped[j] {
			if i == len(pushed) {
				break
			}
			stack = append(stack, pushed[i])
			i++
		}
		if stack[len(stack)-1] != popped[j] {
			break
		}
		stack = stack[:len(stack)-1]
		j++
	}
	if len(stack) == 0 && j == len(popped) {
		res = true
	}
	return res
}

947.移除最多的同行或同列石头(2)

• 题目

我们将石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。
请你设计一个算法，计算最多能执行多少次 move 操作？
示例 1：输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 输出：5
示例 2：输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 输出：3
示例 3：输入：stones = [[0,0]] 输出：0
提示：1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

• 解题思路

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

func removeStones(stones [][]int) int {
	fa := make([]int, 20000)
	for i := 0; i < 20000; i++ {
		fa[i] = i
	}
	for i := 0; i < len(stones); i++ {
		a, b := stones[i][0], stones[i][1]
		// 连接同一行、列
		union(fa, a, b+10000)
	}
	m := make(map[int]bool)
	for i := 0; i < len(stones); i++ {
		a := stones[i][0]
		m[find(fa, a)] = true
	}
	return len(stones) - len(m)
}

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
}

# 2
var arr [][]int
var m []bool

func removeStones(stones [][]int) int {
	n := len(stones)
	arr = make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, 0)
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if stones[i][0] == stones[j][0] || // 同行
				stones[i][1] == stones[j][1] { // 同列
				arr[i] = append(arr[i], j)
				arr[j] = append(arr[j], i)
			}
		}
	}
	m = make([]bool, n)
	count := 0
	for i := 0; i < n; i++ {
		count = count + dfs(i)
	}
	return len(stones) - count
}

func dfs(index int) int {
	if m[index] == true {
		return 0
	}
	m[index] = true
	for i := 0; i < len(arr[index]); i++ {
		dfs(arr[index][i])
	}
	return 1
}

948.令牌放置(1)

• 题目

你的初始 能量 为P，初始 分数 为0，只有一包令牌 tokens 。
其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
令牌可能的两种使用方法如下：
如果你至少有token[i]点 能量 ，可以将令牌 i 置为正面朝上，失去token[i]点 能量 ，并得到1分 。
如果我们至少有1分 ，可以将令牌 i 置为反面朝上，获得token[i] 点 能量 ，并失去1分 。
每个令牌 最多 只能使用一次，使用 顺序不限 ，不需 使用所有令牌。
在使用任意数量的令牌后，返回我们可以得到的最大 分数 。
示例 1：输入：tokens = [100], P = 50 输出：0
解释：无法使用唯一的令牌，因为能量和分数都太少了。
示例 2：输入：tokens = [100,200], P = 150 输出：1
解释：令牌 0 正面朝上，能量变为 50，分数变为 1 。不必使用令牌 1 ，因为你无法使用它来提高分数。
示例 3：输入：tokens = [100,200,300,400], P = 200 输出：2
解释：按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 正面朝上，能量变为 0 ，分数变为 2
提示：0 <= tokens.length <= 1000
0 <= tokens[i],P < 104

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序双指针	O(nlog(n))	O(1)

func bagOfTokensScore(tokens []int, P int) int {
	sort.Ints(tokens)
	res := 0
	maxValue := 0
	left, right := 0, len(tokens)-1
	for left <= right {
		if tokens[left] <= P { // 分够：消耗分数，增加能量
			P = P - tokens[left]
			left++
			maxValue++
		} else if maxValue > 0 { // 分不够：消耗能量，增加分数
			P = P + tokens[right]
			right--
			maxValue--
		} else {
			break
		}
		if maxValue > res {
			res = maxValue
		}
	}
	return res
}

950.按递增顺序显示卡牌(3)

• 题目

牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：
从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。
返回能以递增顺序显示卡牌的牌组顺序。
答案中的第一张牌被认为处于牌堆顶部。
示例：输入：[17,13,11,2,3,5,7] 输出：[2,13,3,11,5,17,7]
解释：我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。
提示：1 <= A.length <= 1000
1 <= A[i] <= 10^6
对于所有的i != j，A[i] != A[j]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	模拟	O(nlog(n))	O(n)
02	模拟	O(nlog(n))	O(n)
03	模拟	O(nlog(n))	O(n)

func deckRevealedIncreasing(deck []int) []int {
	n := len(deck)
	sort.Ints(deck)
	res := make([]int, n)
	temp := make([]int, n)
	for i := 0; i < n; i++ {
		temp[i] = i
	}
	for i := 0; i < n; i++ {
		first := temp[0]
		temp = temp[1:]
		res[first] = deck[i]
		if len(temp) > 0 {
			first := temp[0]
			temp = temp[1:]
			temp = append(temp, first)
		}
	}
	return res
}

# 2
func deckRevealedIncreasing(deck []int) []int {
	n := len(deck)
	sort.Ints(deck)
	if n <= 2 {
		return deck
	}
	res := make([]int, 0)
	res = append(res, deck[n-1])
	for i := n - 2; i >= 0; i-- {
		// 插入一个数a，要将序列尾部的数b拿出来，组成[a,b]放入序列头部，形成新序列。
		last := res[len(res)-1]
		res = res[:len(res)-1]
		res = append([]int{deck[i], last}, res...)
	}
	return res
}

# 3
func deckRevealedIncreasing(deck []int) []int {
	n := len(deck)
	sort.Ints(deck)
	if n <= 2 {
		return deck
	}
	res := make([]int, 0)
	res = append(res, deck[n-1])
	for i := n - 2; i >= 0; i-- {
		res = append(res, deck[i])
		first := res[0]
		res = res[1:]
		res = append(res, first)
	}
	last := res[len(res)-1]
	res = res[:len(res)-1]
	res = append([]int{last}, res...)
	for i := 0; i < n/2; i++ {
		res[i], res[n-1-i] = res[n-1-i], res[i]
	}
	return res
}

951.翻转等价二叉树(1)

• 题目

我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。
编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。
示例：输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], 
root2 =[1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：我们翻转值为 1，3 以及 5 的三个节点。
提示：每棵树最多有 100 个节点。
    每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数。

• 解题思路

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

func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
	if root1 == nil && root2 == nil {
		return true
	}
	if (root1 == nil && root2 != nil) || (root1 != nil && root2 == nil) {
		return false
	}
	if root1.Val == root2.Val {
		return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) ||
			(flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
	}
	return false
}

954.二倍数对数组(1)

• 题目

给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 “对于每个 0 <= i < len(A) / 2，
都有 A[2 * i + 1] = 2 * A[2 * i]” 时，返回 true；否则，返回 false。
示例 1：输入：[3,1,3,6] 输出：false
示例 2：输入：[2,1,2,6] 输出：false
示例 3：输入：[4,-2,2,-4] 输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
示例 4：输入：[1,2,4,16,8,4] 输出：false
提示：0 <= A.length <= 30000
    A.length 为偶数
    -100000 <= A[i] <= 100000

• 解题思路

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

func canReorderDoubled(A []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(A); i++ {
		m[A[i]]++
	}
	sort.Slice(A, func(i, j int) bool {
		return abs(A[i]) < abs(A[j])
	})
	for i := 0; i < len(A); i++ {
		if m[A[i]] == 0 {
			continue
		}
		if m[2*A[i]] == 0 {
			return false
		}
		m[A[i]]--
		m[2*A[i]]--
	}
	return true
}

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

955.删列造序II(1)

• 题目

给定由 n 个字符串组成的数组 strs，其中每个字符串长度相等。
选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。
比如，有 strs = ["abcdef", "uvwxyz"]，删除索引序列{0, 2, 3}，删除后 strs 为["bef", "vyz"]。
假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 
字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，
然后请你返回 answer.length的最小可能值。
示例 1：输入：strs = ["ca","bb","ac"] 输出：1
解释： 删除第一列后，strs = ["a", "b", "c"]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。
示例 2：输入：strs = ["xc","yb","za"] 输出：0
解释：strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。
示例 3：输入：strs = ["zyx","wvu","tsr"] 输出：3
解释：我们必须删掉每一列。
提示：n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] 由小写英文字母组成

• 解题思路

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

func minDeletionSize(strs []string) int {
	res := 0
	cur := make([]string, len(strs))
	for i := 0; i < len(strs[0]); i++ {
		temp := make([]string, len(strs))
		copy(temp, cur)
		for j := 0; j < len(temp); j++ {
			temp[j] = temp[j] + string(strs[j][i])
		}
		if judge(temp) == true { // 加上当前列后，是升序的就用，不是就删除
			cur = temp
		} else {
			res++
		}
	}
	return res
}

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

957.N天后的牢房

题目

8 间牢房排成一排，每间牢房不是有人住就是空着。
每天，无论牢房是被占用或空置，都会根据以下规则进行更改：
如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
否则，它就会被空置。
（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）
我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0。
根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。
示例 1：输入：cells = [0,1,0,1,1,0,0,1], N = 7 输出：[0,0,1,1,0,0,0,0]
解释：下表概述了监狱每天的状况：
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
示例 2：输入：cells = [1,0,0,1,0,0,1,0], N = 1000000000 输出：[0,0,1,1,1,1,1,0]
提示：cells.length == 8
cells[i]的值为 0 或 1
1 <= N <= 10^9

解题思路

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

958.二叉树的完全性检验(2)

• 题目

给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
示例 1：输入：[1,2,3,4,5,6] 输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），
且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
示例 2：输入：[1,2,3,4,5,null,7] 输出：false
解释：值为 7 的结点没有尽可能靠向左侧。
提示：树中将会有 1 到 100 个结点。

• 解题思路

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

var m map[int]bool

func isCompleteTree(root *TreeNode) bool {
	m = make(map[int]bool)
	dfs(root, 1)
	for i := 1; i <= len(m); i++ {
		if m[i] == false {
			return false
		}
	}
	return true
}

func dfs(root *TreeNode, id int) {
	if root == nil {
		return
	}
	m[id] = true
	dfs(root.Left, id*2)
	dfs(root.Right, id*2+1)
}

# 2
func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	prev := root
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if prev == nil && node != nil {
			return false
		}
		if node != nil {
			queue = append(queue, node.Left)
			queue = append(queue, node.Right)
		}
		prev = node
	}
	return true
}

959.由斜杠划分区域(2)

• 题目

在由 1 x 1 方格组成的 N x N 网格grid 中，每个 1 x 1方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\\"表示。）。
返回区域的数目。
示例 1：输入：
[
 " /",
 "/ "
]
输出：2
解释：2x2 网格如下：
示例 2：输入：
[
 " /",
 "  "
]
输出：1
解释：2x2 网格如下：
示例 3：输入：
[
 "\\/",
 "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：
示例 4：输入：
[
 "/\\",
 "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：
示例 5：输入：
[
 "//",
 "/ "
]
输出：3
解释：2x2 网格如下：
提示：1 <= grid.length == grid[0].length <= 30
grid[i][j] 是'/'、'\'、或' '。

• 解题思路

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

func regionsBySlashes(grid []string) int {
	n := len(grid)
	fa = Init(n * n * 4)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			index := 4 * (i*n + j) // 扩大4倍，每个格子拆分为4个：0、1、2、3（顺时针）
			if grid[i][j] == '/' {
				union(index, index+3)   // 合并0、3
				union(index+1, index+2) // 合并1、2
			} else if grid[i][j] == '\\' {
				union(index, index+1)   // 合并0、1
				union(index+2, index+3) // 合并2、3
			} else {
				union(index, index+1) // 合并0、1、2、3
				union(index+1, index+2)
				union(index+2, index+3)
			}
			if j < n-1 {
				union(index+1, index+7) // 向右合并
			}
			if i < n-1 {
				union(index+2, index+4*n) // 向下合并
			}
		}
	}
	return getCount()
}

var fa []int
var count int

// 初始化
func Init(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = i
	}
	count = n
	return arr
}

// 查询
func find(x int) int {
	if fa[x] == x {
		return x
	}
	// 路径压缩
	fa[x] = find(fa[x])
	return fa[x]
}

// 合并
func union(i, j int) {
	x, y := find(i), find(j)
	if x != y {
		fa[x] = y
		count--
	}
}

func query(i, j int) bool {
	return find(i) == find(j)
}

func getCount() int {
	return count
}

# 2
func regionsBySlashes(grid []string) int {
	n := len(grid)
	arr := make([][]int, 3*n)
	for i := 0; i < 3*n; i++ {
		arr[i] = make([]int, 3*n)
	}
	for i := 0; i < n; i++ { // 放大处理
		for j := 0; j < n; j++ {
			if grid[i][j] == '/' { // 9宫格
				arr[i*3+2][j*3] = 1
				arr[i*3+1][j*3+1] = 1
				arr[i*3][j*3+2] = 1
			} else if grid[i][j] == '\\' {
				arr[i*3+2][j*3+2] = 1
				arr[i*3+1][j*3+1] = 1
				arr[i*3][j*3] = 1
			}
		}
	}
	res := 0
	for i := 0; i < 3*n; i++ {
		for j := 0; j < 3*n; j++ {
			if arr[i][j] == 0 {
				dfs(arr, i, j)
				res++
			}
		}
	}
	return res
}

func dfs(arr [][]int, i, j int) {
	if 0 <= i && i < len(arr) && 0 <= j && j < len(arr[0]) && arr[i][j] == 0 {
		arr[i][j] = 1
		dfs(arr, i+1, j)
		dfs(arr, i-1, j)
		dfs(arr, i, j-1)
		dfs(arr, i, j+1)
	}
}

962.最大宽度坡(4)

• 题目

给定一个整数数组A，坡是元组(i, j)，其中i < j且A[i] <= A[j]。这样的坡的宽度为j - i。
找出A中的坡的最大宽度，如果不存在，返回 0 。
示例 1：输入：[6,0,8,2,1,5] 输出：4
解释： 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
示例 2：输入：[9,8,1,0,1,9,4,0,4,1] 输出：7
解释：最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
提示：2 <= A.length <= 50000
0 <= A[i] <= 50000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	自定义排序	O(nlog(n))	O(n)
02	二分查找	O(nlog(n))	O(n)
03	单调栈	O(n)	O(n)
04	暴力法	O(n^2)	O(1)

type Node struct {
   Value int
   Index int
}

func maxWidthRamp(A []int) int {
   res := 0
   n := len(A)
   arr := make([]Node, n)
   for i := 0; i < n; i++ {
   	arr[i] = Node{
   		Value: A[i],
   		Index: i,
   	}
   }
   sort.Slice(arr, func(i, j int) bool {
   	if arr[i].Value == arr[j].Value {
   		return arr[i].Index < arr[j].Index
   	}
   	return arr[i].Value < arr[j].Value
   })
   minIndex := n // 保存当前遇到的最小下标
   for i := 0; i < n; i++ {
   	res = max(res, arr[i].Index-minIndex)
   	minIndex = min(minIndex, arr[i].Index)
   }
   return res
}

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

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

# 2
type Node struct {
   Value int
   Index int
}

func maxWidthRamp(A []int) int {
   res := 0
   n := len(A)
   arr := make([]Node, 0) // Value递增数组
   arr = append(arr, Node{
   	Value: A[n-1],
   	Index: n - 1,
   })
   for i := n - 2; i >= 0; i-- {
   	left, right := 0, len(arr)
   	for left < right {
   		mid := left + (right-left)/2
   		if arr[mid].Value < A[i] { // 不满足条件
   			left = mid + 1
   		} else {
   			right = mid
   		}
   	}
   	if left < len(arr) {
   		index := arr[left].Index
   		res = max(res, index-i)
   	} else {
   		arr = append(arr, Node{
   			Value: A[i],
   			Index: i,
   		})
   	}
   }
   return res
}

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

# 3
func maxWidthRamp(A []int) int {
   res := 0
   n := len(A)
   stack := make([]int, 0) // 递减栈
   for i := 0; i < n; i++ {
   	if len(stack) == 0 || A[stack[len(stack)-1]] > A[i] {
   		stack = append(stack, i)
   	}
   }
   for i := n - 1; i >= 0; i-- {
   	for len(stack) > 0 && A[stack[len(stack)-1]] <= A[i] {
   		index := stack[len(stack)-1] // 坡底index能形成的最大宽度
   		stack = stack[:len(stack)-1]
   		res = max(res, i-index)
   	}
   }
   return res
}

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

# 4
func maxWidthRamp(A []int) int {
   res := 0
   for i := 0; i < len(A); i++ {
   	for j := len(A) - 1; j > i+res; j-- {
   		if A[i] <= A[j] {
   			res = max(res, j-i)
   			break
   		}
   	}
   }
   return res
}

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

963.最小面积矩形II

题目

给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：输入：[[1,2],[2,1],[1,0],[0,1]] 输出：2.00000
解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。
示例 2：输入：[[0,1],[2,1],[1,1],[1,0],[2,0]] 输出：1.00000
解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。
示例 3：输入：[[0,3],[1,2],[3,1],[1,3],[2,1]] 输出：0
解释：没法从这些点中组成任何矩形。
示例 4：输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]] 输出：2.00000
解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。
提示：1 <= points.length <= 50
0 <=points[i][0] <=40000
0 <=points[i][1] <=40000
所有的点都是不同的。
与真实值误差不超过 10^-5的答案将视为正确结果。

解题思路

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

966.元音拼写检查器(1)

• 题目

在给定单词列表wordlist的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。
对于给定的查询单词query，拼写检查器将会处理两类拼写错误：
大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"
元音错误：如果在将查询单词中的元音（‘a’、‘e’、‘i’、‘o’、‘u’）分别替换为任何元音后，
能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）
此外，拼写检查器还按照以下优先级规则操作：
当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
如果该查询在单词列表中没有匹配项，则应返回空字符串。
给出一些查询 queries，返回一个单词列表 answer，
其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。
示例：输入：wordlist = ["KiTe","kite","hare","Hare"], 
queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
提示：1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
wordlist 和queries中的所有字符串仅由英文字母组成。

• 解题思路

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

func spellchecker(wordlist []string, queries []string) []string {
	m := make(map[string]bool)
	mLower := make(map[string]string)
	mVowel := make(map[string]string)
	for i := 0; i < len(wordlist); i++ {
		m[wordlist[i]] = true
		lowerStr := strings.ToLower(wordlist[i])
		if _, ok := mLower[lowerStr]; ok == false {
			mLower[lowerStr] = wordlist[i]
		}
		vowelStr := changeVowel(lowerStr)
		if _, ok := mVowel[vowelStr]; ok == false {
			mVowel[vowelStr] = wordlist[i]
		}
	}
	for i := 0; i < len(queries); i++ {
		if m[queries[i]] == true {
			continue
		}
		lowerStr := strings.ToLower(queries[i])
		if v, ok := mLower[lowerStr]; ok {
			queries[i] = v
			continue
		}
		vowelStr := changeVowel(lowerStr)
		if v, ok := mVowel[vowelStr]; ok {
			queries[i] = v
			continue
		}
		queries[i] = ""
	}
	return queries
}

func changeVowel(str string) string {
	str = strings.ReplaceAll(str, "a", "?")
	str = strings.ReplaceAll(str, "e", "?")
	str = strings.ReplaceAll(str, "i", "?")
	str = strings.ReplaceAll(str, "o", "?")
	str = strings.ReplaceAll(str, "u", "?")
	return str
}

967.连续差相同的数字(2)

• 题目

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。
例如，01 有一个前导零，所以是无效的；但 0是有效的。
你可以按 任何顺序 返回答案。
示例 1：输入：n = 3, k = 7 输出：[181,292,707,818,929]
解释：注意，070 不是一个有效的数字，因为它有前导零。
示例 2：输入：n = 2, k = 1 输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
示例 3：输入：n = 2, k = 0 输出：[11,22,33,44,55,66,77,88,99]
示例 4：输入：n = 2, k = 1
输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
示例 5：输入：n = 2, k = 2
输出：[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]
提示：2 <= n <= 9
0 <= k <= 9

• 解题思路

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

var res []int

func numsSameConsecDiff(n int, k int) []int {
	res = make([]int, 0)
	for i := 1; i <= 9; i++ {
		dfs(i, n, k, i)
	}
	return res
}

func dfs(index, n, k, value int) {
	if n == 1 {
		res = append(res, value)
		return
	}
	a := index + k
	if 0 <= a && a <= 9 && k != 0 {
		value = value*10 + a
		dfs(a, n-1, k, value)
		value = (value - a) / 10
	}
	b := index - k
	if 0 <= b && b <= 9 {
		value = value*10 + b
		dfs(b, n-1, k, value)
		value = (value - b) / 10
	}
}

# 2
func numsSameConsecDiff(n int, k int) []int {
	dp := make([][]int, n)
	dp[0] = []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	for i := 1; i < n; i++ {
		temp := make([]int, 0)
		for j := 0; j < len(dp[i-1]); j++ {
			num := dp[i-1][j]
			a := num%10 - k
			if a >= 0 {
				temp = append(temp, num*10+a)
			}
			b := num%10 + k
			if b <= 9 && k > 0 {
				temp = append(temp, num*10+b)
			}
		}
		dp[i] = temp
	}
	return dp[n-1]
}

969.煎饼排序(1)

• 题目

给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，
然后反转 A 的前 k 个元素的顺序。
我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。
返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。
任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。
示例 1：输入：[3,2,4,1] 输出：[4,2,4,3]
解释：我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4]，此时已完成排序。 
示例 2：输入：[1,2,3] 输出：[]
解释：输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如[3，3]，也将被接受。
提示：1 <= A.length <= 100
    A[i] 是 [1, 2, ..., A.length] 的排列

• 解题思路

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

func pancakeSort(arr []int) []int {
	res := make([]int, 0)
	n := len(arr) - 1
	for n >= 0 {
		maxValue := arr[0]
		index := 0
		for i := 1; i <= n; i++ {
			if arr[i] > maxValue {
				maxValue = arr[i]
				index = i
			}
		}
		if index == n {
			n--
			continue
		}
		if index != 0 {
			res = append(res, index+1)
			reverse(arr, 0, index)
		}
		res = append(res, n+1)
		reverse(arr, 0, n)
		n--
	}
	return res
}

func reverse(arr []int, left, right int) {
	for left < right {
		arr[left], arr[right] = arr[right], arr[left]
		left++
		right--
	}
}

971.翻转二叉树以匹配先序遍历(2)

• 题目

给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。
另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。
通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：
请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程voyage相匹配 。
如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。
示例 1：输入：root = [1,2], voyage = [2,1] 输出：[-1]
解释：翻转节点无法令先序遍历匹配预期行程。
示例 2：输入：root = [1,2,3], voyage = [1,3,2] 输出：[1]
解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。
示例 3：输入：root = [1,2,3], voyage = [1,2,3] 输出：[]
解释：先序遍历已经匹配预期行程，所以不需要翻转节点。
提示：树中的节点数目为 n
n == voyage.length
1 <= n <= 100
1 <= Node.val, voyage[i] <= n
树中的所有值 互不相同
voyage 中的所有值 互不相同

• 解题思路

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

var res []int
var arr []int

func flipMatchVoyage(root *TreeNode, voyage []int) []int {
	res = make([]int, 0)
	arr = make([]int, len(voyage))
	copy(arr, voyage)
	dfs(root)
	return res
}

func dfs(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if root.Val != arr[0] { // 根不满足直接返回
		res = []int{-1}
		return false
	}
	if root.Left != nil && root.Right != nil && root.Right.Val == arr[1] { // 交换
		res = append(res, root.Val)
		root.Left, root.Right = root.Right, root.Left
	}
	arr = arr[1:]
	if dfs(root.Left) == false {
		return false
	}
	return dfs(root.Right)
}

# 2
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
	res := make([]int, 0)
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	index := 0
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node == nil {
			continue
		}
		if node.Val != voyage[index] {
			return []int{-1}
		}
		index++
		if node.Left != nil && node.Right != nil && node.Left.Val != voyage[index] {
			res = append(res, node.Val)
			stack = append(stack, node.Left) // 翻转
			stack = append(stack, node.Right)
		} else {
			stack = append(stack, node.Right)
			stack = append(stack, node.Left)
		}
	}
	return res
}

973.最接近原点的K个点(3)

• 题目

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例 1：输入：points = [[1,3],[-2,2]], K = 1 输出：[[-2,2]]
解释： (1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
示例 2：输入：points = [[3,3],[5,-1],[-2,4]], K = 2 输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）
提示： 1 <= K <= points.length <= 10000
    -10000 < points[i][0] < 10000
    -10000 < points[i][1] < 10000

• 解题思路

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

func kClosest(points [][]int, K int) [][]int {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0]*points[i][0]+points[i][1]*points[i][1] <
			points[j][0]*points[j][0]+points[j][1]*points[j][1]
	})
	return points[:K]
}

# 2
func kClosest(points [][]int, K int) [][]int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < len(points); i++ {
		heap.Push(&intHeap, points[i])
	}
	res := make([][]int, 0)
	for i := 0; i < K; i++ {
		value := heap.Pop(&intHeap).([]int)
		res = append(res, value)
	}
	return res
}

type IntHeap [][]int

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

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

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
}

# 3
func kClosest(points [][]int, K int) [][]int {
	quick(points, 0, len(points)-1, K)
	return points[:K]
}

func quick(points [][]int, left, right int, K int) {
	if left >= right {
		return
	}
	for {
		target := partition(points, left, right)
		if target == K-1 {
			return
		}
		if target < K-1 {
			left = target + 1
		} else {
			right = target - 1
		}
	}
}

func partition(points [][]int, left, right int) int {
	baseValue := points[left]
	for left < right {
		for left < right && dist(baseValue) <= dist(points[right]) {
			right--
		}
		points[left] = points[right]
		for left < right && dist(points[left]) <= dist(baseValue) {
			left++
		}
		points[right] = points[left]
	}
	points[right] = baseValue
	return right
}

func dist(points []int) int {
	return points[0]*points[0] + points[1]*points[1]
}

974.和可被K整除的子数组(2)

• 题目

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
示例：输入：A = [4,5,0,-2,-3,1], K = 5 输出：7
解释： 有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示： 1 <= A.length <= 30000
    -10000 <= A[i] <= 10000
    2 <= K <= 10000

• 解题思路

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

func subarraysDivByK(A []int, K int) int {
	m := make(map[int]int)
	m[0] = 1
	sum := 0
	res := 0
	for i := 0; i < len(A); i++ {
		sum = sum + A[i]
		value := (sum%K + K) % K
		res = res + m[value]
		m[value]++
	}
	return res
}

# 2
func subarraysDivByK(A []int, K int) int {
	m := make(map[int]int)
	m[0] = 1
	sum := 0
	res := 0
	for i := 0; i < len(A); i++ {
		sum = sum + A[i]
		value := (sum%K + K) % K
		m[value]++
	}
	for _, v := range m {
		res = res + v*(v-1)/2
	}
	return res
}

978.最长湍流子数组(3)

• 题目

当 A的子数组A[i], A[i+1], ..., A[j]满足下列条件时，我们称其为湍流子数组：
若i <= k < j，当 k为奇数时，A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
或 若i <= k < j，当 k 为偶数时，A[k] > A[k+1]，且当 k为奇数时，A[k] < A[k+1]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
示例 1：输入：[9,4,2,10,7,8,8,1,9] 输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2：输入：[4,8,12,16] 输出：2
示例 3：输入：[100] 输出：1
提示：1 <= A.length <= 40000
0 <= A[i] <= 10^9

• 解题思路

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

func maxTurbulenceSize(arr []int) int {
	n := len(arr)
	up := make([]int, n)
	down := make([]int, n)
	up[0] = 1
	down[0] = 1
	for i := 1; i < n; i++ {
		down[i] = 1
		up[i] = 1
		if arr[i] > arr[i-1] {
			up[i] = down[i-1] + 1
		} else if arr[i] < arr[i-1] {
			down[i] = up[i-1] + 1
		}
	}
	res := 1
	for i := 0; i < n; i++ {
		res = max(res, up[i])
		res = max(res, down[i])
	}
	return res
}

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

# 2
func maxTurbulenceSize(arr []int) int {
	n := len(arr)
	up := 1
	down := 1
	res := 1
	for i := 1; i < n; i++ {
		if arr[i] > arr[i-1] {
			up, down = down+1, 1
		} else if arr[i] < arr[i-1] {
			up, down = 1, up+1
		} else {
			up, down = 1, 1
		}
		res = max(res, max(up, down))
	}
	return res
}

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

# 3
func maxTurbulenceSize(arr []int) int {
	n := len(arr)
	res := 1
	left, right := 0, 0
	for right < n-1 {
		if left == right {
			if arr[left] == arr[left+1] {
				left++
			}
			right++
		} else {
			if arr[right-1] < arr[right] && arr[right] > arr[right+1] {
				right++
			} else if arr[right-1] > arr[right] && arr[right] < arr[right+1] {
				right++
			} else {
				left = right
			}
		}
		res = max(res, right-left+1)
	}
	return res
}

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

979.在二叉树中分配硬币(1)

• 题目

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，
并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。
(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
示例 1：输入：[3,0,0] 输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
示例 2：输入：[0,3,0] 输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。
然后，我们把一枚硬币从根结点移到右子结点上。
示例 3：输入：[1,0,2] 输出：2
示例 4：输入：[1,0,0,null,3] 输出：4
提示：1<= N <= 100
0 <= node.val <= N

• 解题思路

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

var res int

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

func dfs(root *TreeNode) int { // 该节点子树多余/需要金币数量
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	res = res + abs(left) + abs(right)
	return left + right + root.Val - 1
}

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

981.基于时间的键值存储(1)

• 题目

创建一个基于时间的键值存储类TimeMap，它支持下面两个操作：
1. set(string key, string value, int timestamp)
存储键key、值value，以及给定的时间戳timestamp。
2. get(string key, int timestamp)
返回先前调用set(key, value, timestamp_prev)所存储的值，其中timestamp_prev <= timestamp。
如果有多个这样的值，则返回对应最大的timestamp_prev的那个值。
如果没有值，则返回空字符串（""）。
示例 1：输入：inputs = ["TimeMap","set","get","get","set","get","get"], 
inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出：[null,null,"bar","bar",null,"bar2","bar2"]
解释： TimeMap kv;  
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1  
kv.get("foo", 1);  // 输出 "bar"  
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，
所以唯一的值位于时间戳 1 处（即 "bar"）  kv.set("foo", "bar2", 4);  
kv.get("foo", 4); // 输出 "bar2"  
kv.get("foo", 5); // 输出 "bar2"  
示例 2：输入：inputs = ["TimeMap","set","set","get","get","get","get","get"], 
inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],
["love",15],["love",20],["love",25]]
输出：[null,null,null,"","high","high","low","low"]
提示：所有的键/值字符串都是小写的。
所有的键/值字符串长度都在[1, 100]范围内。
所有TimeMap.set操作中的时间戳timestamps 都是严格递增的。
1 <= timestamp <= 10^7
TimeMap.set 和TimeMap.get函数在每个测试用例中将（组合）调用总计120000 次。

• 解题思路

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

type Node struct {
	timestamp int
	str       string
}

type TimeMap struct {
	m map[string][]Node
}

func Constructor() TimeMap {
	return TimeMap{m: make(map[string][]Node)}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	this.m[key] = append(this.m[key], Node{
		timestamp: timestamp,
		str:       value,
	})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	arr := this.m[key]
	n := len(arr)
	if n == 0 || (timestamp < arr[0].timestamp) {
		return ""
	}
	if timestamp >= arr[n-1].timestamp {
		return arr[n-1].str
	}
	left, right := 0, n
	for left < right {
		mid := left + (right-left)/2
		if arr[mid].timestamp == timestamp {
			return arr[mid].str
		} else if arr[mid].timestamp < timestamp {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return arr[left].str
}

983.最低票价(3)

• 题目

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
    一张为期一天的通行证售价为 costs[0] 美元；
    一张为期七天的通行证售价为 costs[1] 美元；
    一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，
那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
示例 1：输入：days = [1,4,6,7,8,20], costs = [2,7,15] 输出：11
解释：  例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。
示例 2：输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] 输出：17
解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。
提示：1 <= days.length <= 365
    1 <= days[i] <= 365
    days 按顺序严格递增
    costs.length == 3
    1 <= costs[i] <= 1000

• 解题思路

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

var dp [366]int
var m map[int]bool

func mincostTickets(days []int, costs []int) int {
	dp = [366]int{}
	m = make(map[int]bool)
	for i := 0; i < len(days); i++ {
		m[days[i]] = true
	}
	return dfs(1, costs)
}

func dfs(day int, costs []int) int {
	if day > 365 {
		return 0
	}
	if dp[day] > 0 {
		return dp[day]
	}
	if m[day] == true {
		dp[day] = min(min(dfs(day+1, costs)+costs[0], dfs(day+7, costs)+costs[1]),
			dfs(day+30, costs)+costs[2])
	} else {
		dp[day] = dfs(day+1, costs)
	}
	return dp[day]
}

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

# 2
var dp [366]int
var duration = []int{1, 7, 30}

func mincostTickets(days []int, costs []int) int {
	dp = [366]int{}
	return dfs(0, costs, days)
}

func dfs(day int, costs []int, days []int) int {
	if day >= len(days) {
		return 0
	}
	if dp[day] > 0 {
		return dp[day]
	}
	dp[day] = math.MaxInt32
	j := day
	for i := 0; i < 3; i++ {
		for ; j < len(days) && days[j] < days[day]+duration[i]; j++ {
		}
		dp[day] = min(dp[day], dfs(j, costs, days)+costs[i])
	}
	return dp[day]
}

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

# 3
func mincostTickets(days []int, costs []int) int {
	n := days[len(days)-1] + 1
	dp := make([]int, n)
	for i := 0; i < len(days); i++ {
		dp[days[i]] = 1 // 出行日
	}
	for i := 1; i < n; i++ {
		if dp[i] > 0 {
			dp[i] = min(dp[i-1]+costs[0],
				min(dp[max(i-7, 0)]+costs[1], dp[max(i-30, 0)]+costs[2]))
		} else {
			dp[i] = dp[i-1]
		}
	}
	return dp[n-1]
}

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

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

984.不含AAA或BBB的字符串(2)

• 题目

给定两个整数A和B，返回任意字符串 S，要求满足：
S 的长度为A + B，且正好包含A个 'a'字母与B个 'b'字母；
子串'aaa'没有出现在S中；
子串'bbb' 没有出现在S中。
示例 1：输入：A = 1, B = 2 输出："abb"
解释："abb", "bab" 和 "bba" 都是正确答案。
示例 2：输入：A = 4, B = 1 输出："aabaa"
提示：0 <= A <= 100
0 <= B <= 100
对于给定的 A 和 B，保证存在满足要求的 S。

• 解题思路

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

func strWithout3a3b(a int, b int) string {
	res := make([]byte, 0)
	for a > 0 || b > 0 {
		flagA := false
		if len(res) >= 2 && res[len(res)-1] == res[len(res)-2] {
			if res[len(res)-1] == 'b' {
				flagA = true
			}
		} else if a >= b {
			flagA = true
		}
		if flagA == true {
			res = append(res, 'a')
			a--
		} else {
			res = append(res, 'b')
			b--
		}
	}
	return string(res)
}

# 2
func strWithout3a3b(a int, b int) string {
	res := make([]byte, 0)
	for a > 0 && b > 0 {
		if a > b {
			res = append(res, []byte{'a', 'a', 'b'}...)
			a = a - 2
			b--
		} else if a == b {
			res = append(res, []byte{'a', 'b'}...)
			a--
			b--
		} else {
			res = append(res, []byte{'b', 'b', 'a'}...)
			a--
			b = b - 2
		}
	}
	for a > 0 {
		res = append(res, 'a')
		a--
	}
	for b > 0 {
		res = append(res, 'b')
		b--
	}
	return string(res)
}

986.区间列表的交集(2)

• 题目

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，
其中 firstList[i] = [starti, endi] 而secondList[j] = [startj, endj] 。
每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间[a, b]（其中a <= b）表示实数x的集合，而a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
示例 1：输入：firstList = [[0,2],[5,10],[13,23],[24,25]],
secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2：输入：firstList = [[1,3],[5,9]], secondList = [] 输出：[]
示例 3：输入：firstList = [], secondList = [[4,8],[10,12]] 输出：[]
示例 4：输入：firstList = [[1,7]], secondList = [[3,10]] 输出：[[3,7]]
提示：0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1

• 解题思路

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

func intervalIntersection(A [][]int, B [][]int) [][]int {
	res := make([][]int, 0)
	i, j := 0, 0
	for i < len(A) && j < len(B) {
		if A[i][0] <= B[j][1] && B[j][0] <= A[i][1] {
			left := max(A[i][0], B[j][0])
			right := min(A[i][1], B[j][1])
			res = append(res, []int{left, right})
		}
		if A[i][1] < B[j][1] {
			i++
		} else {
			j++
		}
	}
	return res
}

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

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

# 2
func intervalIntersection(A [][]int, B [][]int) [][]int {
	res := make([][]int, 0)
	i, j := 0, 0
	for i < len(A) && j < len(B) {
		left := max(A[i][0], B[j][0])
		right := min(A[i][1], B[j][1])
		if left <= right {
			res = append(res, []int{left, right})
		}
		if A[i][1] < B[j][1] {
			i++
		} else {
			j++
		}
	}
	return res
}

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

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

987.二叉树的垂序遍历(2)

• 题目

给定二叉树，按垂序遍历返回其结点值。
对位于(X, Y)的每个结点而言，其左右子结点分别位于(X-1, Y-1)和(X+1, Y-1)。
把一条垂线从X = -infinity移动到X = +infinity，
每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按X坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
示例 1：输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]]
解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
然后，值为 9 的结点出现在 (-1, -1)；
值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
值为 20 的结点出现在 (1, -1)；
值为 7 的结点出现在 (2, -2)。
示例 2：输入：[1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]]
解释：根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。
然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。
提示：树的结点数介于 1和1000之间。
每个结点值介于0和1000之间。

• 解题思路

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

var m map[int][][2]int

func verticalTraversal(root *TreeNode) [][]int {
	m = make(map[int][][2]int)
	res := make([][]int, 0)
	dfs(root, 0, 0)
	arr := make([]int, 0)
	for k := range m {
		arr = append(arr, k)
	}
	sort.Ints(arr)
	for i := 0; i < len(arr); i++ {
		temp := m[arr[i]]
		sort.Slice(temp, func(i, j int) bool {
			if temp[i][1] == temp[j][1] {
				return temp[i][0] < temp[j][0]
			}
			return temp[i][1] < temp[j][1]
		})
		tempArr := make([]int, 0)
		for j := 0; j < len(temp); j++ {
			tempArr = append(tempArr, temp[j][0])
		}
		res = append(res, tempArr)
	}
	return res
}

func dfs(root *TreeNode, x, y int) {
	if root == nil {
		return
	}
	m[x] = append(m[x], [2]int{root.Val, y})
	dfs(root.Left, x-1, y+1)
	dfs(root.Right, x+1, y+1)
}

# 2
var m map[int][][2]int

func verticalTraversal(root *TreeNode) [][]int {
	m = make(map[int][][2]int)
	res := make([][]int, 0)
	bfs(root, 0, 0)
	arr := make([]int, 0)
	for k := range m {
		arr = append(arr, k)
	}
	sort.Ints(arr)
	for i := 0; i < len(arr); i++ {
		temp := m[arr[i]]
		sort.Slice(temp, func(i, j int) bool {
			if temp[i][1] == temp[j][1] {
				return temp[i][0] < temp[j][0]
			}
			return temp[i][1] < temp[j][1]
		})
		tempArr := make([]int, 0)
		for j := 0; j < len(temp); j++ {
			tempArr = append(tempArr, temp[j][0])
		}
		res = append(res, tempArr)
	}
	return res
}

func bfs(root *TreeNode, x, y int) {
	if root == nil {
		return
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	queueArr := make([][2]int, 0)
	queueArr = append(queueArr, [2]int{0, 0})
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			node := queue[i]
			x, y := queueArr[i][0], queueArr[i][1]
			m[x] = append(m[x], [2]int{node.Val, y})
			if node.Left != nil {
				queue = append(queue, node.Left)
				queueArr = append(queueArr, [2]int{x - 1, y + 1})
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
				queueArr = append(queueArr, [2]int{x + 1, y + 1})
			}
		}
		queue = queue[length:]
		queueArr = queueArr[length:]
	}
}

988.从叶结点开始的最小字符串(2)

• 题目

给定一颗根结点为root的二叉树，树中的每一个结点都有一个从0 到25的值，
分别代表字母'a' 到'z'：值0 代表'a'，值1代表'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上"ab" 比"aba"要小。叶结点是指没有子结点的结点。）
示例 1：输入：[0,1,2,3,4,3,4] 输出："dba"
示例 2：输入：[25,1,3,1,3,0,2] 输出："adz"
示例 3：输入：[2,2,1,null,1,0,null,0] 输出："abc"
提示：给定树的结点数介于1 和8500之间。
树中的每个结点都有一个介于0和25之间的值。

• 解题思路

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

var res string

func smallestFromLeaf(root *TreeNode) string {
	res = ""
	dfs(root, make([]byte, 0))
	return res
}

func dfs(root *TreeNode, arr []byte) {
	if root == nil {
		return
	}
	arr = append(arr, byte('a'+root.Val))
	if root.Left == nil && root.Right == nil {
		for i := 0; i < len(arr)/2; i++ {
			arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
		}
		if string(arr) < res || res == "" {
			res = string(arr)
		}
		for i := 0; i < len(arr)/2; i++ {
			arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
		}
		return
	}
	dfs(root.Left, arr)
	dfs(root.Right, arr)
}

# 2
var res string

func smallestFromLeaf(root *TreeNode) string {
	res = ""
	dfs(root, make([]byte, 0))
	return res
}

func dfs(root *TreeNode, arr []byte) {
	if root == nil {
		return
	}
	arr = append([]byte{byte('a' + root.Val)}, arr...)
	if root.Left == nil && root.Right == nil {
		if string(arr) < res || res == "" {
			res = string(arr)
		}
		return
	}
	dfs(root.Left, arr)
	dfs(root.Right, arr)
}

990.等式方程的可满足性(1)

• 题目

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，
并采用两种不同的形式之一："a==b" 或"a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回true，否则返回 false。
示例 1：输入：["a==b","b!=a"] 输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。
没有办法分配变量同时满足这两个方程。
示例 2：输入：["b==a","a==b"] 输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：输入：["a==b","b==c","a==c"] 输出：true
示例 4：输入：["a==b","b!=c","c==a"] 输出：false
示例 5：输入：["c==c","b==d","x!=z"] 输出：true
提示：1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和equations[i][3]是小写字母
equations[i][1] 要么是'='，要么是'!'
equations[i][2]是'='

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	并查集	O(n)	O(1)

func equationsPossible(equations []string) bool {
	fa := make([]int, 26)
	for i := 0; i < 26; i++ {
		fa[i] = i
	}
	for i := 0; i < len(equations); i++ {
		if equations[i][1] == '=' {
			a, b := int(equations[i][0]-'a'), int(equations[i][3]-'a')
			union(fa, a, b)
		}
	}
	for i := 0; i < len(equations); i++ {
		if equations[i][1] == '!' {
			a, b := int(equations[i][0]-'a'), int(equations[i][3]-'a')
			if find(fa, a) == find(fa, b) {
				return false
			}
		}
	}
	return true
}

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
}

991.坏了的计算器(2)

• 题目

在显示着数字的坏计算器上，我们可以执行以下两种操作：
双倍（Double）：将显示屏上的数字乘 2；
递减（Decrement）：将显示屏上的数字减 1 。
最初，计算器显示数字X。
返回显示数字Y所需的最小操作数。
示例 1：输入：X = 2, Y = 3 输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.
示例 2：输入：X = 5, Y = 8 输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
示例 3：输入：X = 3, Y = 10 输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.
示例 4：输入：X = 1024, Y = 1 输出：1023
解释：执行递减运算 1023 次
提示：1 <= X <= 10^9
1 <= Y <= 10^9

• 解题思路

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

func brokenCalc(X int, Y int) int {
	if X > Y {
		return X - Y
	}
	res := 0
	for X < Y {
		if Y%2 == 0 {
			Y = Y / 2
			res++
		} else {
			Y = (Y + 1) / 2
			res = res + 2
		}
	}
	return res + X - Y
}

# 2
func brokenCalc(X int, Y int) int {
	if X > Y {
		return X - Y
	}
	res := 0
	for X < Y {
		res++
		if Y%2 == 1 {
			Y++
		} else {
			Y = Y / 2
		}
	}
	return res + X - Y
}

994.腐烂的橘子(2)

• 题目

在给定的网格中，每个单元格可以有以下三个值之一：
    值 0 代表空单元格；
    值 1 代表新鲜橘子；
    值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：输入：[[2,1,1],[1,1,0],[0,1,1]] 输出：4
示例 2：输入：[[2,1,1],[0,1,1],[1,0,1]] 输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：输入：[[0,2]] 输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
    1 <= grid.length <= 10
    1 <= grid[0].length <= 10
    grid[i][j] 仅为 0、1 或 2

• 解题思路

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

// 上、右、下、左
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func orangesRotting(grid [][]int) int {
	queue := make([][]int, 0)
	count := 0
	times := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 2 {
				queue = append(queue, []int{i, j})
			} else if grid[i][j] == 1 {
				count = count + 1
			}
		}
	}
	for len(queue) > 0 && count > 0 {
		times++
		length := len(queue)
		for i := 0; i < length; i++ {
			for j := 0; j < 4; j++ {
				x := queue[i][0] + dx[j]
				y := queue[i][1] + dy[j]
				if x >= 0 && x < len(grid) && 
					y >= 0 && y < len(grid[0]) && grid[x][y] == 1 {
					grid[x][y] = 2
					queue = append(queue, []int{x, y})
					count--
				}
			}
		}
		queue = queue[length:]
	}
	if count > 0 {
		return -1
	}
	return times
}

# 2
// 上、右、下、左
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func orangesRotting(grid [][]int) int {
	queue := make([][]int, 0)
	count := 0
	times := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 2 {
				queue = append(queue, []int{i, j})
			} else if grid[i][j] == 1 {
				count = count + 1
			}
		}
	}
	for len(queue) > 0 {
		times++
		length := len(queue)
		for i := 0; i < length; i++ {
			for j := 0; j < 4; j++ {
				x := queue[i][0] + dx[j]
				y := queue[i][1] + dy[j]
				if x >= 0 && x < len(grid) &&
					y >= 0 && y < len(grid[0]) && grid[x][y] == 1 {
					grid[x][y] = 2
					queue = append(queue, []int{x, y})
					count--
				}
			}
		}
		queue = queue[length:]
		if len(queue) == 0 {
			times--
		}
	}
	if count > 0 {
		return -1
	}
	return times
}

998.最大二叉树II(2)

• 题目

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。
给出最大树的根节点 root。
就像之前的问题那样，给定的树是从列表A（root = Construct(A)）
递归地使用下述Construct(A)例程构造的：
如果A为空，返回null
否则，令A[i]作为 A 的最大元素。创建一个值为A[i]的根节点 root
root的左子树将被构建为Construct([A[0], A[1], ..., A[i-1]])
root的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
返回root
请注意，我们没有直接给定A，只有一个根节点root = Construct(A).
假设 B 是 A 的副本，并在末尾附加值 val。题目数据保证 B中的值是不同的。
返回Construct(B)。
示例 1：输入：root = [4,1,3,null,null,2], val = 5 输出：[5,4,null,1,3,null,null,2]
解释：A = [1,4,2,3], B = [1,4,2,3,5]
示例 2：输入：root = [5,2,4,null,1], val = 3 输出：[5,2,4,null,1,null,3]
解释：A = [2,1,5,4], B = [2,1,5,4,3]
示例 3：输入：root = [5,2,3,null,1], val = 4 输出：[5,2,4,null,1,3]
解释：A = [2,1,5,3], B = [2,1,5,3,4]
提示：1 <= B.length <= 100

• 解题思路

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

func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
   if root == nil {
   	return &TreeNode{
   		Val:   val,
   	}
   }
   if val > root.Val {
   	return &TreeNode{
   		Val:   val,
   		Left:  root,
   	}
   }
   root.Right = insertIntoMaxTree(root.Right, val)
   return root
}

# 2
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
   newRoot := root
   if root.Val < val {
   	newRoot = &TreeNode{
   		Val:  val,
   		Left: root,
   	}
   } else if root.Right == nil {
   	root.Right = &TreeNode{Val: val}
   } else {
   	root.Right = insertIntoMaxTree(root.Right, val)
   }
   return newRoot
}

0901-1000-Hard

902.最大为N的数字组合(1)

• 题目

我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'}的非空子集。（请注意，'0' 不包括在内。）
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。
例如D = {'1','3','5'}，我们可以写出像'13', '551', '1351315'这样的数字。
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
示例 1：输入：D = ["1","3","5","7"], N = 100 输出：20
解释：可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：输入：D = ["1","4","9"], N = 1000000000 输出：29523
解释：我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。
提示：D 是按排序顺序的数字 '1'-'9' 的子集。
1 <= N <= 10^9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-数位dp	O(log(n))	O(log(n))

func atMostNGivenDigitSet(digits []string, n int) int {
	str := fmt.Sprintf("%d", n)
	m := len(digits)
	k := len(str)
	dp := make([]int, k+1) // dp[i] 表示 长度为i的N（最后i位）的个数
	dp[0] = 1
	// 1、考虑k位数的可能
	for i := 1; i <= k; i++ {
		value := str[k-i] - '0'
		for j := 0; j < len(digits); j++ {
			v := digits[j][0] - '0'
			if v < value { // 小于，剩下i-1位随便用：+  m^(i-1)
				dp[i] = dp[i] + int(math.Pow(float64(m), float64(i-1)))
			} else if v == value { // 等于：考虑i-1位
				dp[i] = dp[i] + dp[i-1]
			}
		}
	}
	// 2、考虑非k位数的可能
	for i := 1; i < k; i++ {
		dp[k] = dp[k] + int(math.Pow(float64(m), float64(i))) // + m^i
	}
	return dp[k]
}

927.三等分(1)

• 题目

给定一个由 0 和 1 组成的数组A，将数组分成 3个非空的部分，使得所有这些部分表示相同的二进制值。
如果可以做到，请返回任何[i, j]，其中 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, -1]。
注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0]表示十进制中的6，而不会是3。
此外，前导零也是被允许的，所以[0,1,1] 和[1,1]表示相同的值。
示例 1：输入：[1,0,1,0,1] 输出：[0,3]
示例 2：输出：[1,1,0,1,1] 输出：[-1,-1]
提示：3 <= A.length <= 30000
A[i] == 0或A[i] == 1

• 解题思路

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

func threeEqualParts(arr []int) []int {
	res := []int{-1, -1}
	n := len(arr)
	indexArr := make([]int, 0)
	for i := 0; i < n; i++ {
		if arr[i] == 1 {
			indexArr = append(indexArr, i)
		}
	}
	count := len(indexArr)
	if count == 0 {
		return []int{0, 2}
	}
	if count%3 != 0 {
		return res
	}
	// 3个部分，每个部分的1的个数都是一样的
	a, b := count/3, count/3*2 // 第2、3组开始的位置
	i, j, k := indexArr[0], indexArr[a], indexArr[b]
	for k < n && arr[i] == arr[j] && arr[j] == arr[k] {
		i++
		j++
		k++
	}
	if k == n {
		return []int{i - 1, j}
	}
	return res
}

940.不同的子序列II(3)

• 题目

给定一个字符串S，计算S的不同非空子序列的个数。
因为结果可能很大，所以返回答案模 10^9 + 7.
示例 1：输入："abc" 输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：输入："aba" 输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：输入："aaa" 输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：S只包含小写字母。
1 <= S.length <= 2000

• 解题思路

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

var mod = 1000000007

func distinctSubseqII(s string) int {
	n := len(s)
	dp := make([]int, n+1)  // dp[i] 表示s[0:i+1]的不同子序列数
	m := make(map[byte]int) // 保存上次出现的下标
	for i := 0; i < n; i++ {
		if index, ok := m[s[i]]; ok { // 该字符出现过，取上次坐标
			dp[i+1] = (2*dp[i] - dp[index] + mod) % mod // 减去重复的
		} else {
			dp[i+1] = (2*dp[i] + 1) % mod // 这个不包含空序列
		}
		m[s[i]] = i
	}
	return dp[n] % mod
}

# 2
var mod = 1000000007

func distinctSubseqII(s string) int {
	n := len(s)
	dp := make([]int, n+1)  // dp[i] 表示s[0:i+1]的不同子序列数
	dp[0] = 1               // 空序列
	m := make(map[byte]int) // 保存上次出现的下标
	for i := 0; i < n; i++ {
		if index, ok := m[s[i]]; ok { // 该字符出现过，取上次坐标
			dp[i+1] = (2*dp[i] - dp[index] + mod) % mod // 减去重复的
		} else {
			// 如 ab 含有4种情况: "" "a" "b" "ab"
			// 如加入c后的abc 含有8种情况："" "a" "b" "ab" "c" "ac" "bc" "abc"
			dp[i+1] = 2 * dp[i] % mod // 不重复翻倍
		}
		m[s[i]] = i
	}
	return (dp[n] - 1) % mod // 去除空序列
}

# 3
var mod = 1000000007

func distinctSubseqII(s string) int {
	n := len(s)
	dp := make([]int, n+1) // dp[i]表示：长度为i的组合数
	dp[0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j < i; j++ {
			if s[i-1] != s[j-1] {
				dp[i] = (dp[i] + dp[j]) % mod
			}
		}
		dp[i]++ // 当前dp[i]时：最长为i只有1种
	}
	res := 0
	for i := 1; i <= n; i++ {
		res = (res + dp[i]) % mod
	}
	return res
}

956.最高的广告牌(5)

• 题目

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。
举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回广告牌的最大可能安装高度。如果没法安装广告牌，请返回 0。
示例 1：输入：[1,2,3,6] 输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。
示例 2：输入：[1,2,3,4,5,6] 输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。
示例 3：输入：[1,2] 输出：0
解释：没法安装广告牌，所以返回 0。
提示：0 <= rods.length <= 20
    1 <= rods[i] <= 1000
    钢筋的长度总和最多为 5000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-递归	O(3^n)	O(n^2)
02	动态规划	O(3^n)	O(n)
03	动态规划	O(3^n)	O(n)
04	动态规划	O(3^n)	O(n^2)
05	折半搜索	O(3^(n/2))	O(3^(n/2))

const MinValue = math.MinInt32 / 100

// 官方题解(从后往前比较难理解)
// dp[i][s] 表示当我们可以使用 rods[j] (j >= i) 时能得到的最大 score
// dp[i][s] = max(dp[i+1][s], dp[i+1][s-rods[i]], rods[i] + dp[i+1][s+rods[i]])
// 例如:rods=[1,2,3,6],可以有dp[1][1]=5,
// 在写下1之后,可以写下+2,+3,-6使得剩下的rods[i:]获得score为5
var dp [][]int

func tallestBillboard(rods []int) int {
	dp = make([][]int, len(rods))
	for i := 0; i < len(rods); i++ {
		dp[i] = make([]int, 10001)
	}
	res := dfs(rods, 0, 5000)
	return res
}

func dfs(rods []int, index, total int) int {
	if index == len(rods) {
		if total == 5000 {
			return 0
		}
		return MinValue
	}
	if dp[index][total] != 0 {
		return dp[index][total]
	}
	res := dfs(rods, index+1, total)
	res = max(res, dfs(rods, index+1, total-rods[index]))
	res = max(res, dfs(rods, index+1, total+rods[index])+rods[index])
	dp[index][total] = res
	return res
}

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

# 2
func tallestBillboard(rods []int) int {
	dp := make(map[int]int) // 保存和为i中正整数的和
	dp[0] = 0
	// 每个rods[i]有3个选择，+rods[i]、-rods[i]、0
	for i := 0; i < len(rods); i++ {
		value := rods[i]
		temp := make(map[int]int)
		for k, v := range dp {
			temp[k+value] = max(temp[k+value], v+value) // +value>0，是正整数，需要加上
			temp[k] = max(temp[k], v)
			temp[k-value] = max(temp[k-value], v) // -value<0，不需要加上
		}
		dp = temp
	}
	return dp[0]
}

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

# 3
func tallestBillboard(rods []int) int {
	dp := make(map[int]int) // 保存高度差为i时最低一边的高度
	dp[0] = 0
	// 每个rods[i]有3个选择，+rods[i]、-rods[i]、0
	for i := 0; i < len(rods); i++ {
		temp := make(map[int]int)
		for k, v := range dp {
			temp[k] = v
		}
		for k, v := range temp {
			dp[k+rods[i]] = max(dp[k+rods[i]], v)                           // 往高的一侧加，高度差变大，但最低一边高度不变
			dp[k] = dp[k]                                                   // 不加，高度差不变，可忽略
			dp[abs(k-rods[i])] = max(dp[abs(k-rods[i])], v+min(k, rods[i])) // 往低的一侧加，高度差有变化，高度差有增长
		}
	}
	return dp[0]
}

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

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
}

# 4
// dp[i][s] 表示当我们可以使用 rods[j] (j >= i) 时能得到的最大 score
// dp[i][s] = max(dp[i+1][s], dp[i+1][s-rods[i]], rods[i] + dp[i+1][s+rods[i]])
// 例如:rods=[1,2,3,6],可以有dp[1][1]=5,
// 在写下1之后,可以写下+2,+3,-6使得剩下的rods[i:]获得score为5
const MinValue = math.MinInt32 / 100

func tallestBillboard(rods []int) int {
	dp := make([][]int, len(rods)+1)
	for i := 0; i < len(rods)+1; i++ {
		dp[i] = make([]int, 10001)
	}
	for j := 0; j < len(dp[len(rods)]); j++ {
		dp[len(rods)][j] = MinValue
	}
	sum := 0
	for i := 0; i < len(rods); i++ {
		sum = sum + rods[i]
	}
	m := 2*sum
	dp[len(rods)][sum] = 0
	for i := len(rods) - 1; i >= 0; i-- {
		for s := rods[i]; s <= m-rods[i]; s++ {
			dp[i][s] = max(dp[i+1][s], max(dp[i+1][s-rods[i]], rods[i]+dp[i+1][s+rods[i]]))
		}
	}
	return dp[0][sum]
}

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

# 5
func tallestBillboard(rods []int) int {
	leftM := makeM(rods, 0, len(rods)/2)
	rightM := makeM(rods, len(rods)/2, len(rods))
	res := 0
	for k := range leftM {
		if rightM[k] > 0 {
			res = max(res, leftM[k]+rightM[-k])
		}
	}
	return res
}

func makeM(rods []int, left, right int) map[int]int {
	dp := make([][2]int, 100001)
	dp[0] = [2]int{0, 0}
	count := 1
	for i := left; i < right; i++ {
		length := count
		for j := 0; j < length; j++ {
			dp[count] = [2]int{dp[j][0] + rods[i], dp[j][1]}
			count++
			dp[count] = [2]int{dp[j][0], dp[j][1] + rods[i]}
			count++
		}
	}
	m := make(map[int]int)
	for i := 0; i < count; i++ {
		a := dp[i][0]
		b := dp[i][1]
		m[a-b] = max(m[a-b], a)
	}
	return m
}

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

968.监控二叉树(2)

• 题目

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：输入：[0,0,null,0,0] 输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：输入：[0,0,null,0,null,0,null,null,0] 输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：给定树的节点数的范围是[1, 1000]。 每个节点的值都是 0。

• 解题思路

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

var maxValue = math.MaxInt32 / 10

func minCameraCover(root *TreeNode) int {
	_, res, _ := dfs(root)
	return res
}

func dfs(root *TreeNode) (a, b, c int) {
	if root == nil {
		return maxValue, 0, 0
	}
	la, lb, lc := dfs(root.Left)
	ra, rb, rc := dfs(root.Right)
	a = lc + rc + 1               // root必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
	b = min(a, min(la+rb, ra+lb)) // 覆盖整棵树需要的摄像头数目,无论root是否放置摄像头。
	c = min(a, lb+rb)             // 覆盖两棵子树需要的摄像头数目,无论节点root本身是否被监控到。
	return a, b, c
}

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

# 2
var res int

func minCameraCover(root *TreeNode) int {
	res = 0
	if dfs(root) == 0 { // root未被监控
		res++
	}
	return res
}

// 0=>未被监控， 1=>已监控， 2=>安装监控
func dfs(root *TreeNode) int {
	if root == nil {
		return 1 // 空节点假设有监控
	}
	left, right := dfs(root.Left), dfs(root.Right)
	if left == 1 && right == 1 { // 左右节点都有监控，比如都是空节点，那么当前节点是无未被监控
		return 0
	}
	if left+right >= 3 { // 1+2 / 2+1 / 2+2 => 当前节点已经被监控
		return 1
	}
	res++ // 1+0, 0+1, 0+2, 2+0, 0+0 => 需要安装监控
	return 2
}

980.不同路径III(1)

• 题目

在二维网格 grid 上，有 4 种类型的方格：
1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出：4
解释：我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3：输入：[[0,1],[2,0]] 输出：0
解释：没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
提示：1 <= grid.length * grid[0].length <= 20

• 解题思路

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

var res int
var n, m int

func uniquePathsIII(grid [][]int) int {
	res = 0
	n, m = len(grid), len(grid[0])
	visited := make([][]bool, n)
	for i := 0; i < n; i++ {
		visited[i] = make([]bool, m)
	}
	x, y := 0, 0
	count := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				x, y = i, j
				continue
			}
			if grid[i][j] == 0 {
				count++
			}
		}
	}
	dfs(grid, x, y, visited, count)
	return res
}

func dfs(grid [][]int, i, j int, visited [][]bool, count int) {
	if i < 0 || i >= n || j < 0 || j >= m ||
		grid[i][j] == -1 || visited[i][j] == true {
		return
	}
	if grid[i][j] == 2 {
		if count == -1 { // 包括起始点1
			res++
		}
		return
	}
	visited[i][j] = true
	dfs(grid, i, j+1, visited, count-1)
	dfs(grid, i, j-1, visited, count-1)
	dfs(grid, i+1, j, visited, count-1)
	dfs(grid, i-1, j, visited, count-1)
	visited[i][j] = false
}

992.K个不同整数的子数组(2)

• 题目

给定一个正整数数组 A，如果 A的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
（例如，[1,2,3,1,2] 中有3个不同的整数：1，2，以及3。）
返回A中好子数组的数目。
示例 1：输入：A = [1,2,1,2,3], K = 2 输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：输入：A = [1,2,1,3,4], K = 3 输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
提示：1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

• 解题思路

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

func subarraysWithKDistinct(nums []int, k int) int {
	return getK(nums, k) - getK(nums, k-1) // 恰好K个不同=最多K个不同-最多K-1个不同
}

// 求最多K个不同
func getK(nums []int, k int) int {
	res := 0
	n := len(nums)
	m := make(map[int]int)
	left, right := 0, 0
	count := 0
	for ; right < n; right++ {
		cur := nums[right]
		if m[cur] == 0 {
			count++ // 次数+1
		}
		m[cur]++
		for count > k {
			m[nums[left]]--
			if m[nums[left]] == 0 {
				count--
			}
			left++
		}
		res = res + right - left
	}
	return res
}

# 2
func subarraysWithKDistinct(nums []int, k int) int {
	res := 0
	n := len(nums)
	m1 := make(map[int]int)
	m2 := make(map[int]int)
	left1, left2 := 0, 0
	count1, count2 := 0, 0
	for i := 0; i < n; i++ {
		cur := nums[i]
		if m1[cur] == 0 {
			count1++
		}
		if m2[cur] == 0 {
			count2++
		}
		m1[cur]++
		m2[cur]++
		for count1 > k {
			m1[nums[left1]]--
			if m1[nums[left1]] == 0 {
				count1--
			}
			left1++
		}
		for count2 > k-1 {
			m2[nums[left2]]--
			if m2[nums[left2]] == 0 {
				count2--
			}
			left2++
		}
		res = res + left2 - left1
	}
	return res
}

995.K连续位的最小翻转次数(4)

• 题目

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，
同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
示例 1：输入：A = [0,1,0], K = 1 输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：输入：A = [1,1,0], K = 2 输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：输入：A = [0,0,0,1,0,1,1,0], K = 3 输出：3
解释：翻转 A[0],A[1],A[2]:A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]:A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]:A变成 [1,1,1,1,1,1,1,1]
提示：1 <= A.length <=30000
1 <= K <= A.length

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	差分数组	O(n)	O(n)
02	暴力法	O(n^2)	O(1)
03	差分数组	O(n)	O(n)
04	滑动窗口	O(n)	O(1)

func minKBitFlips(nums []int, k int) int {
	n := len(nums)
	arr := make([]int, n+1) // 差分数组
	res := 0
	count := 0 // 翻转奇数偶数次
	for i := 0; i < n; i++ {
		count = count + arr[i]
		if (count+nums[i])%2 == 0 { // 当前位置翻转count次后是0
			if i+k > n { // 剩下达不到k个一组
				return -1
			}
			count++    // 翻转+1
			arr[i]++   // 差分数组i 加1
			arr[i+k]-- // 差分数组i+k 减1
			res++
		}
	}
	return res
}

# 2
func minKBitFlips(nums []int, k int) int {
	n := len(nums)
	res := 0
	for i := 0; i < n; i++ {
		if nums[i] == 0 {
			if i+k > n {
				return -1
			}
			for j := i; j < i+k; j++ {
				nums[j] = 1 - nums[j]
			}
			res++
		}
	}
	return res
}

# 3
func minKBitFlips(nums []int, k int) int {
	n := len(nums)
	arr := make([]int, n+1) // 差分数组
	res := 0
	count := 0 // 翻转奇数偶数次
	for i := 0; i < n; i++ {
		count = (count + arr[i]) % 2
		if (count+nums[i])%2 == 0 { // 当前位置翻转count次后是0
			if i+k > n { // 剩下达不到k个一组
				return -1
			}
			count = 1 - count // 翻转+1
			arr[i]++          // 差分数组i 加1
			arr[i+k]--        // 差分数组i+k 减1
			res++
		}
	}
	return res
}

# 4
func minKBitFlips(nums []int, k int) int {
	n := len(nums)
	res := 0
	count := 0 // 翻转奇数偶数次
	for i := 0; i < n; i++ {
		if i >= k && nums[i-k] > 1 {
			count = 1 - count
		}
		if (nums[i]+count)%2 == 0 { // 是1翻转奇数次变为1，是0翻转偶数次为0
			if i+k > n {
				return -1
			}
			res++
			count = 1 - count
			nums[i] = nums[i] + 2 // 标记
		}
	}
	return res
}

996.正方形数组的数目

题目

给定一个非负整数数组A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。



示例 1：

输入：[1,17,8]
输出：2
解释：
[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2：

输入：[2,2,2]
输出：1


提示：

1 <= A.length <= 12
0 <= A[i] <= 1e9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-squareful-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

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