1101-1200-Easy

1103.分糖果 II(3)

• 题目

排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，
依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。
注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，
以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：输入：candies = 7, num_people = 4 输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：输入：candies = 10, num_people = 3 输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
    1 <= candies <= 10^9
    1 <= num_people <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^(1/2))	O(n)
02	暴力法	O(n^(1/2))	O(n)
03	等差数列求和公式	O(n^(1/2))	O(n)

func distributeCandies(candies int, num_people int) []int {
	res := make([]int, num_people)
	i := 0
	count := 0
	for candies > 0 {
		count++
		if candies >= count {
			res[i%num_people] += count
		} else {
			res[i%num_people] += candies
		}
		i++
		candies = candies - count
	}
	return res
}

#
func distributeCandies(candies int, num_people int) []int {
	res := make([]int, num_people)
	count := 1
	for candies > 0 {
		for i := 0; i < num_people; i++ {
			if candies >= count {
				res[i] = res[i] + count
				candies = candies - count
			} else {
				res[i] = res[i] + candies
				candies = 0
			}
			count++
		}
	}
	return res
}

#
func distributeCandies(candies int, num_people int) []int {
	res := make([]int, num_people)
	times := 1
	for times*(times+1)/2 <= candies {
		times++
	}
	// 计算出当前糖果最多可以发给多少个人,剩下最后一个人多少颗糖
	times--
	last := candies - times*(times+1)/2
	for i := 0; i < num_people; i++ {
		n := times / num_people
		if times%num_people > i {
			n = n + 1
		}
		// 等差数列{an}的通项公式为：an=a1+(n-1)d。
		// 前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
		// Sn=n(a1+a1+(n-1)d)/2=n(2a1+(n-1)d)/2
		// (i+1)为首项，num_people为公差，n为数列长度，的等差数列的和
		res[i] = n * (2*(i+1) + (n-1)*num_people) / 2
		if times%num_people == i {
			res[i] = res[i] + last
		}
	}
	return res
}

1108.IP地址无效化(2)

• 题目

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。
示例 1：输入：address = "1.1.1.1" 输出："1[.]1[.]1[.]1"
示例 2：输入：address = "255.100.50.0" 输出："255[.]100[.]50[.]0"
提示：
    给出的 address 是一个有效的 IPv4 地址

• 解题思路

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

func defangIPaddr(address string) string {
	return strings.ReplaceAll(address, ".", "[.]")
}

#
func defangIPaddr(address string) string {
	res := ""
	for i := range address {
		if address[i] == '.' {
			res = res + "[.]"
		} else {
			res = res + string(address[i])
		}
	}
	return res
}

1122.数组的相对排序(3)

• 题目

给你两个数组，arr1 和 arr2，
    arr2 中的元素各不相同
    arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
    arr1.length, arr2.length <= 1000
    0 <= arr1[i], arr2[i] <= 1000
    arr2 中的元素 arr2[i] 各不相同
    arr2 中的每个元素 arr2[i] 都出现在 arr1 中

• 解题思路

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

func relativeSortArray(arr1 []int, arr2 []int) []int {
	if len(arr2) == 0 {
		sort.Ints(arr1)
		return arr1
	}
	res := make([]int, 0)
	m := make(map[int]int)
	for i := range arr1 {
		m[arr1[i]]++
	}
	for i := 0; i < len(arr2); i++ {
		for j := 0; j < m[arr2[i]]; j++ {
			res = append(res, arr2[i])
		}
		m[arr2[i]] = 0
	}
	tempArr := make([]int, 0)
	for key, value := range m {
		for value > 0 {
			tempArr = append(tempArr, key)
			value--
		}
	}
	sort.Ints(tempArr)
	res = append(res, tempArr...)
	return res
}

#
func relativeSortArray(arr1 []int, arr2 []int) []int {
	count := 0
	for i := 0; i < len(arr2); i++ {
		for j := count; j < len(arr1); j++ {
			if arr2[i] == arr1[j] {
				arr1[count], arr1[j] = arr1[j], arr1[count]
				count++
			}
		}
	}
	sort.Ints(arr1[count:])
	return arr1
}

#
func relativeSortArray(arr1 []int, arr2 []int) []int {
	temp := make([]int, 1001)
	for i := range arr1 {
		temp[arr1[i]]++
	}
	count := 0
	for i := range arr2 {
		for temp[arr2[i]] > 0 {
			arr1[count] = arr2[i]
			temp[arr2[i]]--
			count++
		}
	}
	for i := 0; i < len(temp); i++ {
		for temp[i] > 0 {
			arr1[count] = i
			temp[i]--
			count++
		}
	}
	return arr1
}

1128.等价多米诺骨牌对的数量(2)

• 题目

给你一个由一些多米诺骨牌组成的列表 dominoes。
如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 
等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
在 0 <= i < j < dominoes.length 的前提下，
找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例：输入：dominoes = [[1,2],[2,1],[3,4],[5,6]] 输出：1
提示：
    1 <= dominoes.length <= 40000
    1 <= dominoes[i][j] <= 9

• 解题思路

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

func numEquivDominoPairs(dominoes [][]int) int {
	m := make(map[string]int)
	for i := 0; i < len(dominoes); i++ {
		a := dominoes[i][0]
		b := dominoes[i][1]
		if a > b {
			a, b = b, a
		}
		m[fmt.Sprintf("%d,%d", a, b)]++
	}
	res := 0
	for _, v := range m {
		res = res + v*(v-1)/2
	}
	return res
}

#
func numEquivDominoPairs(dominoes [][]int) int {
	res := 0
	arr := make([]int, 101)
	for i := 0; i < len(dominoes); i++ {
		a := dominoes[i][0]
		b := dominoes[i][1]
		if a > b {
			a, b = b, a
		}
		res = res + arr[a*10+b]
		arr[a*10+b]++
	}
	return res
}

1137.第N个泰波那契数(3)

• 题目

泰波那契序列 Tn 定义如下： 
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：输入：n = 4 输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
    0 <= n <= 37
    答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

• 解题思路

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

func tribonacci(n int) int {
	arr := make([]int, n+3)
	arr[0] = 0
	arr[1] = 1
	arr[2] = 1
	for i := 3; i <= n; i++ {
		arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
	}
	return arr[n]
}

#
func tribonacci(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 || n == 2 {
		return 1
	}
	a := 0
	b := 1
	c := 1
	for i := 3; i <= n; i++ {
		c, b, a = a+b+c, c, b
	}
	return c
}

#
var m map[int]int

func tribonacci(n int) int {
	if m == nil {
		m = make(map[int]int)
	}
	if n == 0 {
		return 0
	}
	if n == 1 || n == 2 {
		return 1
	}
	if value, ok := m[n]; ok {
		return value
	} else {
		value := tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
		m[n] = value
	}
	return m[n]
}

1154.一年中的第几天(2)

• 题目

给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。
通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。
每个月的天数与现行公元纪年法（格里高利历）一致。
示例 1：输入：date = "2019-01-09" 输出：9
示例 2：输入：date = "2019-02-10" 输出：41
示例 3：输入：date = "2003-03-01" 输出：60
示例 4：输入：date = "2004-03-01" 输出：61
提示：
    date.length == 10
    date[4] == date[7] == '-'，其他的 date[i] 都是数字。
    date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日。

• 解题思路

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

func dayOfYear(date string) int {
	arr := strings.Split(date, "-")
	year, _ := strconv.Atoi(arr[0])
	month, _ := strconv.Atoi(arr[1])
	day, _ := strconv.Atoi(arr[2])
	res := 0
	for i := 0; i < month; i++ {
		switch i {
		case 1, 3, 5, 7, 8, 10, 12:
			res = res + 31
		case 4, 6, 9, 11:
			res = res + 30
		case 2:
			res = res + 28
			if year%400 == 0 || (year%4 == 0 && year%100 != 0) {
				res = res + 1
			}
		}
	}
	res = res + day
	return res
}

#
func dayOfYear(date string) int {
	format := "2006-01-02"
	t, _ := time.Parse(format, date)
	return t.YearDay()
}

1160.拼写单词(3)

• 题目

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），
那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1：输入：words = ["cat","bt","hat","tree"], chars = "atach" 输出：6
解释：  可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
示例 2：输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr" 输出：10
解释： 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
提示：
    1 <= words.length <= 1000
    1 <= words[i].length, chars.length <= 100
    所有字符串中都仅包含小写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n^2)	O(1)
02	遍历-内置函数	O(n^2)	O(1)
03	数组辅助	O(n^2)	O(1)

func countCharacters(words []string, chars string) int {
	m := make(map[byte]int)
	for i := range chars {
		m[chars[i]]++
	}
	res := 0
	for i := 0; i < len(words); i++ {
		temp := make(map[byte]int)
		flag := true
		for j := range words[i] {
			temp[words[i][j]]++
		}
		if len(temp) > len(m) {
			continue
		}
		for k, v := range temp {
			if v > m[k] {
				flag = false
				break
			}
		}
		if flag == true {
			res = res + len(words[i])
		}
	}
	return res
}

#
func countCharacters(words []string, chars string) int {
	res := 0
	for i := 0; i < len(words); i++ {
		flag := true
		for _, v := range words[i] {
			if strings.Count(words[i], string(v)) > strings.Count(chars, string(v)) {
				flag = false
				continue
			}
		}
		if flag == true {
			res = res + len(words[i])
		}
	}
	return res
}

#
func countCharacters(words []string, chars string) int {
	m := make([]int, 26)
	for i := range chars {
		m[chars[i]-'a']++
	}
	res := 0
	for i := 0; i < len(words); i++ {
		temp := make([]int, 26)
		flag := true
		for j := range words[i] {
			temp[words[i][j]-'a']++
		}
		if len(temp) > len(m) {
			continue
		}
		for k, v := range temp {
			if v > m[k] {
				flag = false
				break
			}
		}
		if flag == true {
			res = res + len(words[i])
		}
	}
	return res
}

1170.比较字符串最小字母出现频次(2)

• 题目

我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；
该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，
其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
示例 1：输入：queries = ["cbd"], words = ["zaaaz"] 输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
示例 2：输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] 输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
提示：
    1 <= queries.length <= 2000
    1 <= words.length <= 2000
    1 <= queries[i].length, words[i].length <= 10
    queries[i][j], words[i][j] 都是小写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n^2)	O(n)
02	排序+二分查找	O(nlog(n))	O(n)

func numSmallerByFrequency(queries []string, words []string) []int {
	queriesArr := make([]int, len(queries))
	wordsArr := make([]int, len(words))
	res := make([]int, 0)
	for i := 0; i < len(words); i++ {
		wordsArr[i] = f(words[i])
	}
	for i := 0; i < len(queries); i++ {
		queriesArr[i] = f(queries[i])
		count := 0
		for j := 0; j < len(wordsArr); j++ {
			if queriesArr[i] < wordsArr[j] {
				count++
			}
		}
		res = append(res, count)
	}
	return res
}

func f(str string) int {
	min := str[0]
	count := 1
	for i := 1; i < len(str); i++ {
		if str[i] < min {
			min = str[i]
			count = 1
		} else if str[i] == min{
			count++
		}
	}
	return count
}

#
func numSmallerByFrequency(queries []string, words []string) []int {
	wordsArr := make([]int, len(words))
	res := make([]int, 0)
	for i := 0; i < len(words); i++ {
		wordsArr[i] = f(words[i])
	}
	sort.Ints(wordsArr)
	for i := 0; i < len(queries); i++ {
		value := f(queries[i])
		count := binarySearch(value, wordsArr)
		res = append(res, count)
	}
	return res
}

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

func f(str string) int {
	min := str[0]
	count := 1
	for i := 1; i < len(str); i++ {
		if str[i] < min {
			min = str[i]
			count = 1
		} else if str[i] == min {
			count++
		}
	}
	return count
}

1175.质数排列(1)

• 题目

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；
你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：输入：n = 5 输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，
因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
示例 2：输入：n = 100 输出：682289015
提示：
    1 <= n <= 100

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历-全排列	O(n^3/2)	O(1)

func numPrimeArrangements(n int) int {
	primeNum := 0
	for i := 2; i <= n; i++ {
		if isPrime(i) {
			primeNum++
		}
	}
	a := 1
	for i := 2; i <= primeNum; i++ {
		a = a * i % 1000000007
	}
	for i := 2; i <= n-primeNum; i++ {
		a = a * i % 1000000007
	}
	return a
}

func isPrime(n int) bool {
	if n == 2 || n == 3 {
		return true
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

1184.公交站间的距离(2)

• 题目

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。
我们已知每一对相邻公交站之间的距离，
distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：输入：distance = [1,2,3,4], start = 0, destination = 1 输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例 2：输入：distance = [1,2,3,4], start = 0, destination = 2 输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例 3：输入：distance = [1,2,3,4], start = 0, destination = 3 输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
    1 <= n <= 10^4
    distance.length == n
    0 <= start, destination < n
    0 <= distance[i] <= 10^4

• 解题思路

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

func distanceBetweenBusStops(distance []int, start int, destination int) int {
	x := 0
	y := 0
	for i := start; i != destination; i = (i + 1) % len(distance) {
		x = x + distance[i]
	}
	for i := destination; i != start; i = (i + 1) % len(distance) {
		y = y + distance[i]
	}
	if x > y {
		return y
	}
	return x
}

#
func distanceBetweenBusStops(distance []int, start int, destination int) int {
	x := 0
	sum := 0
	for i := 0; i < len(distance); i++ {
		sum = sum + distance[i]
		if start < destination {
			if i >= start && i < destination {
				x = x + distance[i]
			}
		} else {
			if i >= destination && i < start {
				x = x + distance[i]
			}
		}
	}
	if sum-x > x {
		return x
	}
	return sum - x
}

1185.一周中的第几天(3)

• 题目

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。
输入为三个整数：day、month 和 year，分别表示日、月、年。
您返回的结果必须是这几个值中的一个 
{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。
示例 1：输入：day = 31, month = 8, year = 2019 输出："Saturday"
示例 2：输入：day = 18, month = 7, year = 1999 输出："Sunday"
示例 3：输入：day = 15, month = 8, year = 1993 输出："Sunday"
提示：
    给出的日期一定是在 1971 到 2100 年之间的有效日期。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(1)	O(1)
02	公式	O(1)	O(1)
03	遍历	O(1)	O(1)

func dayOfTheWeek(day int, month int, year int) string {
	t, _ := time.Parse("2006-01-02", fmt.Sprintf("%04d-%02d-%02d", year, month, day))
	return t.Weekday().String()
}

#
// 蔡勒公式
// 基姆拉尔森计算公式
// https://baike.baidu.com/item/%E8%94%A1%E5%8B%92%E5%85%AC%E5%BC%8F
// https://www.cnblogs.com/SeekHit/p/7498408.html
// Week = (y+y/4-y/100+y/400+2*m+3*(m+1)/5+d) mod 7；
func dayOfTheWeek(day int, month int, year int) string {
	arr := []string{"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"}
	if month == 1 || month == 2 {
		month = month + 12
		year--
	}
	week := (year + year/4 - year/100 + year/400 + 2*month + 3*(month+1)/5 + day) % 7
	return arr[week]
}

#
var arr = []string{"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"}
var monthDate = []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

func dayOfTheWeek(day int, month int, year int) string {
	day1 := totalDay(1993, 8, 15)
	day2 := totalDay(year, month, day)
	diff := 6 - day1%7
	return arr[(day2+diff)%7]
}

func totalDay(year, month, day int) int {
	total := 0
	for i := 1971; i < year; i++ {
		total = total + 365
		if isLeap(i) {
			total = total + 1
		}
	}
	for i := 0; i < month-1; i++ {
		total = total + monthDate[i]
		if i == 1 && isLeap(year) {
			total = total + 1
		}
	}
	total = total + day
	return total
}

func isLeap(year int) bool {
	return year%400 == 0 || (year%4 == 0 && year%100 != 0)
}

1189.“气球”的最大数量(3)

• 题目

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
示例 1：输入：text = "nlaebolko" 输出：1
示例 2：输入：text = "loonbalxballpoon" 输出：2
示例 3：输入：text = "leetcode" 输出：0
提示：
    1 <= text.length <= 10^4
    text 全部由小写英文字母组成

• 解题思路

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

func maxNumberOfBalloons(text string) int {
	m := make([]int, 26)
	str := "ablon"
	for i := 0; i < len(str); i++ {
		m[str[i]-'a']++
	}
	for i := 0; i < len(text); i++ {
		if m[text[i]-'a'] > 0 {
			m[text[i]-'a']++
		}
	}
	min := math.MaxInt32
	for k, v := range m {
		if v == 0 {
			continue
		}
		if k+'a' == 'l' || k+'a' == 'o' {
			v = (v - 1) / 2
		} else {
			v = v - 1
		}
		if v < min {
			min = v
		}
	}
	return min
}

#
func maxNumberOfBalloons(text string) int {
	m := make([]int, 26)
	for i := 0; i < len(text); i++ {
		m[text[i]-'a']++
	}
	res := 0
	str := "balloon"
	for {
		for i := 0; i < len(str); i++ {
			m[str[i]-'a']--
			if m[str[i]-'a'] < 0 {
				return res
			}
		}
		res++
	}
}

#
func maxNumberOfBalloons(text string) int {
	arr := make([]int, 0)
	str := "ablon"
	for i := 0; i < len(str); i++ {
		if str[i] == 'l' || str[i] == 'o' {
			arr = append(arr, strings.Count(text, string(str[i]))/2)
		} else {
			arr = append(arr, strings.Count(text, string(str[i])))
		}
	}
	min := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] < min {
			min = arr[i]
		}
	}
	return min
}

1200.最小绝对差(2)

• 题目

给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]
示例 2：输入：arr = [1,3,6,10,15] 输出：[[1,3]]
示例 3：输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
提示：
    2 <= arr.length <= 10^5
    -10^6 <= arr[i] <= 10^6

• 解题思路

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

func minimumAbsDifference(arr []int) [][]int {
	sort.Ints(arr)
	result := make([][]int, 0)
	min := arr[1] - arr[0]
	result = append(result, []int{arr[0], arr[1]})
	for i := 2; i < len(arr); i++ {
		value := arr[i] - arr[i-1]
		if value < min {
			min = value
			result = make([][]int, 0)
			result = append(result, []int{arr[i-1], arr[i]})
		} else if value == min {
			result = append(result, []int{arr[i-1], arr[i]})
		}
	}
	return result
}

#
func minimumAbsDifference(arr []int) [][]int {
	sort.Ints(arr)
	result := make([][]int, 0)
	min := arr[1] - arr[0]
	for i := 2; i < len(arr); i++ {
		if min > arr[i]-arr[i-1] {
			min = arr[i] - arr[i-1]
		}
	}
	for i := 1; i < len(arr); i++ {
		if min == arr[i]-arr[i-1] {
			result = append(result, []int{arr[i-1], arr[i]})
		}
	}
	return result
}

1101-1200-Medium

1104.二叉树寻路(3)

• 题目

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按“之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，
该路径是由途经的节点标号所组成的。
示例 1：输入：label = 14 输出：[1,3,4,14]
示例 2：输入：label = 26 输出：[1,2,6,10,26]
提示：1 <= label <= 10^6

• 解题思路

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

func pathInZigZagTree(label int) []int {
	res := make([]int, 0)
	for label > 0 {
		res = append(res, label)
		label = label / 2
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	i := 1
	if len(res)%2 == 0 {
		i = 2
	}
	for ; i < len(res); i = i + 2 {
		res[i] = (1<<i)*3 - 1 - res[i]
	}
	return res
}

# 2
func pathInZigZagTree(label int) []int {
	length := int(math.Log2(float64(label)))
	res := make([]int, length+1)
	res[length] = label
	length--
	i := 1
	for length >= 0 {
		target := int(math.Pow(2, float64(length+1))) + int(math.Pow(2, float64(length))) - 1
		if i%2 == 1 {
			res[length] = target - label/2
		} else {
			res[length] = label / 2
		}
		i++
		length--
		label = label / 2
	}
	return res
}

# 3
func pathInZigZagTree(label int) []int {
	res := make([]int, 0)
	for label > 1 {
		res = append([]int{label}, res...)
		label = label / 2
		length := bits.Len32(uint32(label)) - 1
		label = label ^ ((1 << length) - 1) // 7^3=4 => 111^11=100
	}
	res = append([]int{1}, res...)
	return res
}

1105.填充书架(1)

• 题目

附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。
你把要摆放的书 books都整理好，叠成一摞：
从上往下，第 i本书的厚度为 books[i][0]，高度为 books[i][1]。
按顺序将这些书摆放到总宽度为shelf_width 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。
重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。 
例如，如果这里有 5 本书，那么可能的一种摆放情况是：
第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
示例：输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4 输出：6
解释：3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
提示：1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

• 解题思路

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

func minHeightShelves(books [][]int, shelf_width int) int {
	n := len(books)
	dp := make([]int, n+1) // 以第i本书作为结尾的总高度
	for i := 1; i <= n; i++ {
		w, h := books[i-1][0], books[i-1][1]
		dp[i] = dp[i-1] + h // 当前这本书单独一层的高度
		for j := i - 1; j > 0; j-- {
			if w+books[j-1][0] <= shelf_width {
				w = w + books[j-1][0]
				h = max(h, books[j-1][1])
				dp[i] = min(dp[i], dp[j-1]+h)
			} else {
				break
			}
		}
	}
	return dp[n]
}

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
}

1109.航班预订统计(2)

• 题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表，
表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。
请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。
示例：输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10,55,45,25,25]
提示：1 <= bookings.length <= 20000
    1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
    1 <= bookings[i][2] <= 10000

• 解题思路

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

func corpFlightBookings(bookings [][]int, n int) []int {
	arr := make([]int, n+1)
	for i := 0; i < len(bookings); i++ {
		start := bookings[i][0] - 1
		end := bookings[i][1] - 1
		count := bookings[i][2]
		arr[start] = arr[start] + count
		arr[end+1] = arr[end+1] - count
	}
	res := make([]int, 0)
	total := 0
	for i := 0; i < n; i++ {
		total = total + arr[i]
		res = append(res, total)
	}
	return res
}

# 2
func corpFlightBookings(bookings [][]int, n int) []int {
	arr := make([]int, n)
	for i := 0; i < len(bookings); i++ {
		start := bookings[i][0]
		end := bookings[i][1]
		count := bookings[i][2]
		arr[start-1] = arr[start-1] + count
		if end < n {
			arr[end] = arr[end] - count
		}
	}
	for i := 1; i < n; i++ {
		arr[i] = arr[i] + arr[i-1]
	}
	return arr
}

1110.删点成林(1)

• 题目

给出二叉树的根节点root，树上每个节点都有一个不同的值。
如果节点值在to_delete中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例：输入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出：[[1,2,null,4],[6],[7]]
提示：树中的节点数最大为1000。
每个节点都有一个介于1 到1000之间的值，且各不相同。
to_delete.length <= 1000
to_delete 包含一些从1 到1000、各不相同的值。

• 解题思路

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

var res []*TreeNode
var m map[int]bool

func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
	res = make([]*TreeNode, 0)
	m = make(map[int]bool)
	for i := 0; i < len(to_delete); i++ {
		m[to_delete[i]] = true
	}
	root = dfs(root)
	if root != nil {
		res = append(res, root)
	}
	return res
}

func dfs(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = dfs(root.Left)
	root.Right = dfs(root.Right)
	if m[root.Val] == true {
		if root.Left != nil {
			res = append(res, root.Left)
		}
		if root.Right != nil {
			res = append(res, root.Right)
		}
		return nil
	}
	return root
}

1111.有效括号的嵌套深度(3)

• 题目

有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。
详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。
详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：
给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，
并使这两个字符串的深度最小。
    不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
    A 或 B 中的元素在原字符串中可以不连续。
    A.length + B.length = seq.length
    深度最小：max(depth(A), depth(B)) 的可能取值最小。 
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
    answer[i] = 0，seq[i] 分给 A 。
    answer[i] = 1，seq[i] 分给 B 。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
示例 1：输入：seq = "(()())" 输出：[0,1,1,1,1,0]
示例 2：输入：seq = "()(())()" 输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。 
提示：1 < seq.size <= 10000
有效括号字符串：仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：
  1. 空字符串
  2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串
嵌套深度：类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：
  1. s 为空时，depth("") = 0
  2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串
例如：""，"()()"，和 "()(()())" 都是有效括号字符串，
嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	统计	O(n)	O(n)
02	找规律	O(n)	O(n)
03	找规律	O(n)	O(n)

func maxDepthAfterSplit(seq string) []int {
	res := make([]int, 0)
	level := 0
	for i := 0; i < len(seq); i++ {
		if seq[i] == '(' {
			level++
			res = append(res, level%2)
		} else {
			res = append(res, level%2)
			level--
		}
	}
	return res
}

# 2
func maxDepthAfterSplit(seq string) []int {
	res := make([]int, 0)
	for i := 0; i < len(seq); i++ {
		if seq[i] == '(' {
			res = append(res, i%2)
		} else {
			res = append(res, 1-i%2)
		}
	}
	return res
}

# 3
func maxDepthAfterSplit(seq string) []int {
	res := make([]int, 0)
	a, b := 0, 0
	for i := 0; i < len(seq); i++ {
		if seq[i] == '(' {
			// 谁少给谁
			if a <= b {
				a++
				res = append(res, 0)
			} else {
				b++
				res = append(res, 1)
			}
		} else {
			// 谁多减谁
			if a > b {
				a--
				res = append(res, 0)
			} else {
				b--
				res = append(res, 1)
			}
		}
	}
	return res
}

1123.最深叶节点的最近公共祖先(2)

• 题目

给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的深度为0，如果某一节点的深度为d，那它的子节点的深度就是d+1
如果我们假定 A 是一组节点S的 最近公共祖先，S中的每个节点都在以 A 为根节点的子树中，
且 A的深度达到此条件下可能的最大值。
注意：本题与力扣 865 重复：
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：输入：root = [1] 输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：输入：root = [0,1,3,null,2] 输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：给你的树中将有1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。
每个节点的值都是独一无二的。

• 解题思路

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

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	res, _ := dfs(root, 0)
	return res
}

func dfs(root *TreeNode, level int) (*TreeNode, int) {
	if root == nil {
		return root, level
	}
	leftNode, left := dfs(root.Left, level+1)
	rightNode, right := dfs(root.Right, level+1)
	if left == right {
		return root, left + 1
	} else if left > right {
		return leftNode, left + 1
	}
	return rightNode, right + 1
}

# 2
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	if root == nil{
		return nil
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	if left == right{
		return root
	}else if left > right{
		return lcaDeepestLeaves(root.Left)
	}
	return lcaDeepestLeaves(root.Right)
}

func dfs(root *TreeNode) (int) {
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	return 1+max(left,right)
}

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

1124.表现良好的最长时间段(3)

• 题目

给你一份工作时间表hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：输入：hours = [9,9,6,0,6,6,9] 输出：3
解释：最长的表现良好时间段是 [9,9,6]。
提示：1 <= hours.length <= 10000
0 <= hours[i] <= 16

• 解题思路

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

func longestWPI(hours []int) int {
	arr := make([]int, 0)
	for i := 0; i < len(hours); i++ {
		if hours[i] > 8 {
			arr = append(arr, 1)
		} else {
			arr = append(arr, -1)
		}
	}
	temp := make([]int, len(hours)+1)
	for i := 1; i <= len(hours); i++ {
		temp[i] = temp[i-1] + arr[i-1]
	}
	stack := make([]int, 0)
	// 单调栈
	for i := 0; i < len(temp); i++ {
		if len(stack) == 0 || temp[stack[len(stack)-1]] > temp[i] {
			stack = append(stack, i)
		}
	}
	res := 0
	for i := len(temp) - 1; i >= 0; i-- {
		if len(stack) == 0 {
			break
		}
		for len(stack) > 0 && temp[i] > temp[stack[len(stack)-1]] {
			if i-stack[len(stack)-1] > res {
				res = i - stack[len(stack)-1]
			}
			stack = stack[:len(stack)-1]
		}
	}
	return res
}

# 2
func longestWPI(hours []int) int {
	arr := make([]int, 0)
	for i := 0; i < len(hours); i++ {
		if hours[i] > 8 {
			arr = append(arr, 1)
		} else {
			arr = append(arr, -1)
		}
	}
	temp := make([]int, len(hours)+1)
	for i := 1; i <= len(hours); i++ {
		temp[i] = temp[i-1] + arr[i-1]
	}
	res := 0
	for i := 0; i < len(hours); i++ {
		for j := i; j < len(hours); j++ {
			count := temp[j+1] - temp[i]
			if count > 0 {
				res = max(res, j-i+1)
			}
		}
	}
	return res
}

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

# 3
func longestWPI(hours []int) int {
	m := make(map[int]int)
	count := 0
	res := 0
	for i := 0; i < len(hours); i++ {
		if hours[i] > 8 {
			count++
		} else {
			count--
		}
		if count > 0 {
			res = i + 1
		} else {
			if _, ok := m[count]; ok == false {
				m[count] = i
			}
			// (count-(count-1))=1>0
			if _, ok := m[count-1]; ok == true {
				res = max(res, i-m[count-1])
			}

		}
	}
	return res
}

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

1129.颜色交替的最短路径(2)

• 题目

在一个有向图中，节点分别标记为0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色，且存在自环或平行边。
red_edges中的每一个[i, j]对表示从节点 i 到节点 j 的红色有向边。
类似地，blue_edges中的每一个[i, j]对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组answer，其中answer[X]是从节点0到节点X的红色边和蓝色边交替出现的最短路径的长度。
如果不存在这样的路径，那么 answer[x] = -1。
示例 1：输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = [] 输出：[0,1,-1]
示例 2：输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]] 输出：[0,1,-1]
示例 3：输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]] 输出：[0,-1,-1]
示例 4：输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]] 输出：[0,1,2]
示例 5：输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]] 输出：[0,1,1]
提示：1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

• 解题思路

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

var redArr [][]int
var blueArr [][]int
var res []int

func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
	redArr = make([][]int, n)
	blueArr = make([][]int, n)
	for i := 0; i < len(red_edges); i++ {
		a, b := red_edges[i][0], red_edges[i][1]
		redArr[a] = append(redArr[a], b)
	}
	for i := 0; i < len(blue_edges); i++ {
		a, b := blue_edges[i][0], blue_edges[i][1]
		blueArr[a] = append(blueArr[a], b)
	}
	res = make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = -1
	}
	res[0] = 0
	bfs(n, 0) // 红
	bfs(n, 1) // 蓝
	return res
}

func bfs(n int, color int) {
	visited := make([][2]bool, n)
	visited[0][color] = true
	queue := make([]int, 0)
	queue = append(queue, 0)
	count := 0
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			node := queue[i]
			targetColor := count % 2
			if targetColor == color { //偶数次和当前颜色一致
				for i := 0; i < len(redArr[node]); i++ {
					next := redArr[node][i]
					if visited[next][targetColor] == false {
						visited[next][targetColor] = true
						if res[next] == -1 || res[next] > count+1 {
							res[next] = count + 1
						}
						queue = append(queue, next)
					}
				}
			} else {
				for i := 0; i < len(blueArr[node]); i++ {
					next := blueArr[node][i]
					if visited[next][targetColor] == false {
						visited[next][targetColor] = true
						if res[next] == -1 || res[next] > count+1 {
							res[next] = count + 1
						}
						queue = append(queue, next)
					}
				}
			}
		}
		queue = queue[length:]
		count++
	}
}

# 2
func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
	redArr, blueArr := make([][]int, n), make([][]int, n)
	for i := 0; i < len(red_edges); i++ {
		a, b := red_edges[i][0], red_edges[i][1]
		redArr[a] = append(redArr[a], b)
	}
	for i := 0; i < len(blue_edges); i++ {
		a, b := blue_edges[i][0], blue_edges[i][1]
		blueArr[a] = append(blueArr[a], b)
	}
	res := make([]int, n) // res[0] = 0
	for i := 1; i < n; i++ {
		res[i] = -1
	}
	queue, visited := make([][2]int, 0), make([][2]bool, n)
	for i := 0; i < len(redArr[0]); i++ {
		queue = append(queue, [2]int{redArr[0][i], 0})
	}
	for i := 0; i < len(blueArr[0]); i++ {
		queue = append(queue, [2]int{blueArr[0][i], 1})
	}
	count := 1
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			node, targetColor := queue[i][0], queue[i][1]
			if res[node] == -1 {
				res[node] = count
			}
			if targetColor == 0 && visited[node][targetColor] == false {
				visited[node][targetColor] = true
				for j := 0; j < len(blueArr[node]); j++ {
					queue = append(queue, [2]int{blueArr[node][j], 1})
				}
			}
			if targetColor == 1 && visited[node][targetColor] == false {
				visited[node][targetColor] = true
				for j := 0; j < len(redArr[node]); j++ {
					queue = append(queue, [2]int{redArr[node][j], 0})
				}
			}
		}
		queue = queue[length:]
		count++
	}
	return res
}

1130.叶值的最小代价生成树(3)

• 题目

给你一个正整数数组arr，考虑所有满足以下条件的二叉树：
每个节点都有 0 个或是 2 个子节点。
数组arr中的值与树的中序遍历中每个叶节点的值一一对应。
（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个32 位整数。
示例：输入：arr = [6,2,4] 输出：32
解释： 有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4
提示：2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于2^31。

• 解题思路

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

func mctFromLeafValues(arr []int) int {
	res := 0
	stack := make([]int, 0) // 单调递减栈
	stack = append(stack, math.MaxInt32)
	for i := 0; i < len(arr); i++ {
		for len(stack) > 0 && arr[i] >= stack[len(stack)-1] { // 大于栈顶
			middle := stack[len(stack)-1] // 中间
			stack = stack[:len(stack)-1]
			left := stack[len(stack)-1]
			right := arr[i]
			res = res + middle*min(left, right)
		}
		stack = append(stack, arr[i])
	}
	for len(stack) > 2 {
		a := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		b := stack[len(stack)-1]
		res = res + a*b
	}
	return res
}

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

# 2
func mctFromLeafValues(arr []int) int {
	n := len(arr)
	maxArr := make([][]int, n)
	for i := 0; i < n; i++ {
		maxArr[i] = make([]int, n)
		maxValue := arr[i]
		for j := i; j < n; j++ {
			maxValue = max(maxValue, arr[j])
			maxArr[i][j] = maxValue // i到j之间的最大值
		}
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for j := 0; j < n; j++ {
		for i := j - 1; i >= 0; i-- {
			dp[i][j] = math.MaxInt32
			for k := i; k+1 <= j; k++ {
				// dp[i][j]代表从i到j之间的最小代价
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+maxArr[i][k]*maxArr[k+1][j])
			}
		}
	}
	return dp[0][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
}

# 3
func mctFromLeafValues(arr []int) int {
	res := 0
	stack := make([]int, 0) // 单调递减栈
	for i := 0; i < len(arr); i++ {
		for len(stack) > 0 && arr[i] >= stack[len(stack)-1] { // 大于栈顶
			middle := stack[len(stack)-1] // 中间
			stack = stack[:len(stack)-1]
			right := arr[i]
			var left int
			if len(stack) == 0 {
				left = math.MaxInt32
			} else {
				left = stack[len(stack)-1]
			}
			res = res + middle*min(left, right)
		}
		stack = append(stack, arr[i])
	}
	for len(stack) >= 2 {
		a := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		b := stack[len(stack)-1]
		res = res + a*b
	}
	return res
}

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

1131.绝对值表达式的最大值(2)

• 题目

给你两个长度相等的整数数组，返回下面表达式的最大值：
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
其中下标 i，j 满足0 <= i, j < arr1.length。
示例 1：输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6] 输出：13
示例 2：输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] 输出：20
提示：2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

• 解题思路

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

func maxAbsValExpr(arr1 []int, arr2 []int) int {
	/*
		|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
		=  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)
		=  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)
		=  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)
		=  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)
		= -(arr1[i] + arr2[i] + i) + (arr1[j] + arr2[j] + j)
		= -(arr1[i] + arr2[i] - i) + (arr1[j] + arr2[j] - j)
		= -(arr1[i] - arr2[i] + i) + (arr1[j] - arr2[j] + j)
		= -(arr1[i] - arr2[i] - i) + (arr1[j] - arr2[j] - j)
		其中：
		A = arr1[i] + arr2[i] + i
		B = arr1[i] + arr2[i] - i
		C = arr1[i] - arr2[i] + i
		D = arr1[i] - arr2[i] - i
		结果：
		max( |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|)
		= max(max(A) - min(A),max(B) - min(B),max(C) - min(C), max(D) - min(D))
	*/
	arr := make([][]int, 4)
	for i := 0; i < len(arr1); i++ {
		a, b := arr1[i], arr2[i]
		arr[0] = append(arr[0], a+b+i)
		arr[1] = append(arr[1], a+b-i)
		arr[2] = append(arr[2], a-b+i)
		arr[3] = append(arr[3], a-b-i)
	}
	a, b, c, d := getValue(arr[0]), getValue(arr[1]), getValue(arr[2]), getValue(arr[3])
	return max(a, max(b, max(c, d)))
}

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

func getValue(arr []int) int {
	minValue, maxValue := arr[0], arr[0]
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxValue {
			maxValue = arr[i]
		}
		if arr[i] < minValue {
			minValue = arr[i]
		}
	}
	return maxValue - minValue
}

# 2
func maxAbsValExpr(arr1 []int, arr2 []int) int {
	aMaxValue, bMaxValue, cMaxValue, dMaxValue := math.MinInt32, math.MinInt32, math.MinInt32, math.MinInt32
	aMinValue, bMinValue, cMinValue, dMinValue := math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32
	for i := 0; i < len(arr1); i++ {
		aMaxValue = max(aMaxValue, arr1[i]+arr2[i]+i)
		aMinValue = min(aMinValue, arr1[i]+arr2[i]+i)
		bMaxValue = max(bMaxValue, arr1[i]+arr2[i]-i)
		bMinValue = min(bMinValue, arr1[i]+arr2[i]-i)
		cMaxValue = max(cMaxValue, arr1[i]-arr2[i]+i)
		cMinValue = min(cMinValue, arr1[i]-arr2[i]+i)
		dMaxValue = max(dMaxValue, arr1[i]-arr2[i]-i)
		dMinValue = min(dMinValue, arr1[i]-arr2[i]-i)
	}
	a, b := aMaxValue-aMinValue, bMaxValue-bMinValue
	c, d := cMaxValue-cMinValue, dMaxValue-dMinValue
	return max(a, max(b, max(c, d)))
}

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
}

1138.字母板上的路径(1)

• 题目

我们从一块字母板上的位置(0, 0)出发，该坐标对应的字符为board[0][0]。
在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。
我们可以按下面的指令规则行动：
如果方格存在，'U'意味着将我们的位置上移一行；
如果方格存在，'D'意味着将我们的位置下移一行；
如果方格存在，'L'意味着将我们的位置左移一列；
如果方格存在，'R'意味着将我们的位置右移一列；
'!'会把在我们当前位置 (r, c) 的字符board[r][c]添加到答案中。
（注意，字母板上只存在有字母的位置。）
返回指令序列，用最小的行动次数让答案和目标target相同。你可以返回任何达成目标的路径。
示例 1：输入：target = "leet" 输出："DDR!UURRR!!DDD!"
示例 2：输入：target = "code" 输出："RR!DDRR!UUL!R!"
提示：1 <= target.length <= 100
target仅含有小写英文字母。

• 解题思路

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

func alphabetBoardPath(target string) string {
	res := ""
	x, y := 0, 0
	for i := 0; i < len(target); i++ {
		newX := int(target[i]-'a') / 5
		newY := int(target[i]-'a') % 5
		if x > newX {
			res = res + strings.Repeat("U", x-newX) // 优先向上：从Z往上
		}
		if y > newY {
			res = res + strings.Repeat("L", y-newY) // 优先向左：往Z走
		}
		if y < newY {
			res = res + strings.Repeat("R", newY-y) // 向右
		}
		if x < newX {
			res = res + strings.Repeat("D", newX-x) // 向下
		}
		res = res + "!"
		x, y = newX, newY
	}
	return res
}

1139.最大的以1为边界的正方形(1)

• 题目

给你一个由若干 0 和 1 组成的二维网格grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。
如果不存在，则返回 0。
示例 1：输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
示例 2：输入：grid = [[1,1,0,0]] 输出：1
提示：1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为0或1

• 解题思路

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

func largest1BorderedSquare(grid [][]int) int {
	res := 0
	arr := [100][100][2]int{}
	n, m := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 0 {
				continue
			}
			if i == 0 {
				arr[i][j][0] = 1
			} else {
				arr[i][j][0] = arr[i-1][j][0] + 1 // 当前坐标上边1的长度
			}
			if j == 0 {
				arr[i][j][1] = 1
			} else {
				arr[i][j][1] = arr[i][j-1][1] + 1 // 当前坐标左边1的长度
			}
			minValue := min(arr[i][j][0], arr[i][j][1]) // 左边、上边连续1选短的
			for k := minValue; k > res; k-- {
				if arr[i][j-k+1][0] >= k && arr[i-k+1][j][1] >= k { // 判断另外2条边
					res = k
					break
				}
			}
		}
	}
	return res * res
}

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

1140.石子游戏II(2)

• 题目

亚历克斯和李继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子piles[i]。
游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其中1 <= X <= 2M。
然后，令M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：输入：piles = [2,7,9,4,4] 输出：10
解释：如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。
在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。
在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。 
提示：1 <= piles.length <= 100
1 <= piles[i]<= 10 ^ 4

• 解题思路

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

func stoneGameII(piles []int) int {
	n := len(piles)
	dp := make([][]int, n+1) // dp[i][j]=>有piles[i:]，M=j的情况下得分
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	sum := 0
	for i := n - 1; i >= 0; i-- {
		sum = sum + piles[i]
		for M := 1; M <= n; M++ {
			if i+2*M >= n { // 可以全部拿走
				dp[i][M] = sum
			} else {
				for j := 1; j <= 2*M; j++ { // 尝试不同拿法，dp[i+j][max(j, M)]其中M=max(j,M)
					dp[i][M] = max(dp[i][M], sum-dp[i+j][max(j, M)])
				}
			}
		}
	}
	return dp[0][1]
}

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

# 2
var dp [][]int

func stoneGameII(piles []int) int {
	n := len(piles)
	dp = make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := n - 2; i >= 0; i-- {
		piles[i] = piles[i] + piles[i+1]
	}
	return dfs(piles, 0, 1)
}

func dfs(piles []int, index, M int) int {
	if index >= len(piles) {
		return 0
	}
	if index+2*M >= len(piles) { // 可以全部拿走
		return piles[index]
	}
	if dp[index][M] > 0 {
		return dp[index][M]
	}
	res := 0
	for i := 1; i <= 2*M; i++ { // 尝试不同拿法
		res = max(res, piles[index]-dfs(piles, index+i, max(M, i)))
	}
	dp[index][M] = res
	return dp[index][M]
}

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

1143.最长公共子序列(3)

• 题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:输入：text1 = "abcde", text2 = "ace"  输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:输入：text1 = "abc", text2 = "abc" 输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:输入：text1 = "abc", text2 = "def" 输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:
    1 <= text1.length <= 1000
    1 <= text2.length <= 1000
    输入的字符串只含有小写英文字符。

• 解题思路

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

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

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

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

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

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

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

1144.递减元素使数组呈锯齿状(2)

• 题目

给你一个整数数组nums，每次 操作会从中选择一个元素并 将该元素的值减少1。
如果符合下列情况之一，则数组A就是 锯齿数组：
每个偶数索引对应的元素都大于相邻的元素，即A[0] > A[1] < A[2] > A[3] < A[4] > ...
或者，每个奇数索引对应的元素都大于相邻的元素，即A[0] < A[1] > A[2] < A[3] > A[4] < ...
返回将数组nums转换为锯齿数组所需的最小操作次数。
示例 1：输入：nums = [1,2,3] 输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：输入：nums = [9,6,1,6,2] 输出：4
提示：1 <= nums.length <= 1000
1 <= nums[i] <= 1000

• 解题思路

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

func movesToMakeZigzag(nums []int) int {
	n := len(nums)
	a, b := 0, 0
	for i := 0; i < n; i++ {
		if i%2 == 0 { // 偶数下标小，如果大于左右两边数，需要减去
			left, right := 0, 0
			if i > 0 && nums[i] >= nums[i-1] {
				left = nums[i] - nums[i-1] + 1
			}
			if i < n-1 && nums[i] >= nums[i+1] {
				right = nums[i] - nums[i+1] + 1
			}
			a = a + max(left, right)
		} else { // 奇数下标小，如果大于左右两边数，需要减去
			left, right := 0, 0
			if nums[i] >= nums[i-1] {
				left = nums[i] - nums[i-1] + 1
			}
			if i < n-1 && nums[i] >= nums[i+1] {
				right = nums[i] - nums[i+1] + 1
			}
			b = b + max(left, right)
		}
	}
	return min(a, b)
}

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

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

# 2
func movesToMakeZigzag(nums []int) int {
	n := len(nums)
	a, b := 0, 0
	for i := 0; i < n; i = i + 2 { // 偶数下标小，如果大于左右两边数，需要减去
		left, right := 0, 0
		if i > 0 && nums[i] >= nums[i-1] {
			left = nums[i] - nums[i-1] + 1
		}
		if i < n-1 && nums[i] >= nums[i+1] {
			right = nums[i] - nums[i+1] + 1
		}
		a = a + max(left, right)
	}
	for i := 1; i < n; i = i + 2 { // 奇数下标小，如果大于左右两边数，需要减去
		left, right := 0, 0
		if nums[i] >= nums[i-1] {
			left = nums[i] - nums[i-1] + 1
		}
		if i < n-1 && nums[i] >= nums[i+1] {
			right = nums[i] - nums[i+1] + 1
		}
		b = b + max(left, right)
	}
	return min(a, b)
}

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

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

1145.二叉树着色游戏(2)

• 题目

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，
给出二叉树的根节点root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从1 到n各不相同。
游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，
「一号」玩家从 [1, n]中取一个值x（1 <= x <= n）；
「二号」玩家也从[1, n]中取一个值y（1 <= y <= n）且y != x。
「一号」玩家给值为x的节点染上红色，而「二号」玩家给值为y的节点染上蓝色。
之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，
将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。
如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。
若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个y值可以确保你赢得这场游戏，则返回true；
若无法获胜，就请返回 false。
示例：输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3 输出：True
解释：第二个玩家可以选择值为 2 的节点。
提示：二叉树的根节点为root，树上由 n 个节点，节点上的值从 1 到 n 各不相同。
n 为奇数。
1 <= x <= n<= 100

• 解题思路

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

var targetNode *TreeNode

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
	dfsTarget(root, x)
	// 统计根节点、目标节点左子树、目标节点右子树
	return dfs(root) > n/2 || dfs(targetNode.Left) > n/2 || dfs(targetNode.Right) > n/2
}

func dfsTarget(root *TreeNode, target int) {
	if root != nil {
		if root.Val == target {
			targetNode = root
			return
		}
		dfsTarget(root.Left, target)
		dfsTarget(root.Right, target)
	}
}

func dfs(root *TreeNode) int {
	if root == nil || root == targetNode {
		return 0
	}
	return 1 + dfs(root.Left) + dfs(root.Right)
}

# 2
var leftSum, rightSum int

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
	leftSum = 0
	rightSum = 0
	total := dfs(root, x)
	return leftSum > n/2 || rightSum > n/2 || (total-1-leftSum-rightSum) > n/2
}

func dfs(root *TreeNode, x int) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left, x)
	right := dfs(root.Right, x)
	if root.Val == x {
		leftSum = left
		rightSum = right
	}
	return 1 + left + right
}

1146.快照数组(3)

• 题目

实现支持下列接口的「快照数组」-SnapshotArray：
SnapshotArray(int length)- 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于0。
void set(index, val)- 会将指定索引index处的元素设置为val。
int snap()- 获取该数组的快照，并返回快照的编号snap_id（快照号是调用snap()的总次数减去1）。
int get(index, snap_id)- 根据指定的snap_id选择快照，并返回该快照指定索引 index的值。
示例：输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
提示：1 <= length<= 50000
题目最多进行50000 次set，snap，和get的调用 。
0 <= index<length
0 <=snap_id <我们调用snap()的总次数
0 <=val <= 10^9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n)	O(n^2)
02	哈希辅助	O(n)	O(n^2)
03	数组辅助+二分查找	O(log(n))	O(n^2)

type SnapshotArray struct {
	id  int
	arr [][]Snap
}

type Snap struct {
	id    int
	value int
}

func Constructor(length int) SnapshotArray {
	return SnapshotArray{
		id:  0,
		arr: make([][]Snap, length),
	}
}

func (this *SnapshotArray) Set(index int, val int) {
	// 保存的是index的操作记录
	this.arr[index] = append(this.arr[index], Snap{
		id:    this.id,
		value: val,
	})
}

func (this *SnapshotArray) Snap() int {
	id := this.id
	this.id++
	return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
	n := len(this.arr[index])
	i := 0
	// 根据index的历史记录，找到最后1个id为snap_id的记录
	// 其中id为snap_id的记录可能有多个
	for i < n && this.arr[index][i].id <= snap_id {
		i++
	}
	if i == 0 {
		return 0
	}
	i--
	return this.arr[index][i].value
}

# 2
type SnapshotArray struct {
	id  int
	arr []map[int]int
}

func Constructor(length int) SnapshotArray {
	return SnapshotArray{
		id:  0,
		arr: make([]map[int]int, length),
	}
}

func (this *SnapshotArray) Set(index int, val int) {
	if this.arr[index] == nil {
		this.arr[index] = make(map[int]int)
	}
	this.arr[index][this.id] = val
}

func (this *SnapshotArray) Snap() int {
	id := this.id
	this.id++
	return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
	if this.arr[index] == nil {
		return 0
	}
	for ; snap_id >= 0; snap_id-- {
		if v, ok := this.arr[index][snap_id]; ok {
			return v
		}
	}
	return 0
}

# 3
type SnapshotArray struct {
	id  int
	arr [][]Snap
}

type Snap struct {
	id    int
	value int
}

func Constructor(length int) SnapshotArray {
	nums := make([][]Snap, length)
	for i := 0; i < length; i++ {
		nums[i] = []Snap{{ // 填充0
			id:    0,
			value: 0,
		}}
	}
	return SnapshotArray{
		id:  0,
		arr: nums,
	}
}

func (this *SnapshotArray) Set(index int, val int) {
	n := len(this.arr[index])
	if this.arr[index][n-1].id == this.id {
		this.arr[index][n-1].value = val
		return
	}
	this.arr[index] = append(this.arr[index], Snap{
		id:    this.id,
		value: val,
	})
}

func (this *SnapshotArray) Snap() int {
	id := this.id
	this.id++
	return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
	n := len(this.arr[index])
	arr := this.arr[index]
	left, right := 0, n-1
	for left < right {
		mid := left + (right-left)/2
		if snap_id <= arr[mid].id {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if left == n || arr[left].id > snap_id {
		return arr[left-1].value
	}
	return arr[left].value
}

1155.掷骰子的N种方法(2)

• 题目

这里有d个一样的骰子，每个骰子上都有f个面，分别标号为1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），
模10^9 + 7后返回。
示例 1：输入：d = 1, f = 6, target = 3 输出：1
示例 2：输入：d = 2, f = 6, target = 7 输出：6
示例 3：输入：d = 2, f = 5, target = 10 输出：1
示例 4：输入：d = 1, f = 2, target = 3 输出：0
示例 5：输入：d = 30, f = 30, target = 500 输出：222616187
提示：1 <= d, f <= 30
1 <= target <= 1000

• 解题思路

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

func numRollsToTarget(d int, f int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 0; i < d; i++ {
		next := make([]int, target+1)
		for j := 1; j <= f; j++ {
			for k := 0; k <= target-j; k++ {
				next[k+j] = (next[k+j] + dp[k]) % 1000000007
			}
		}
		dp = next
	}
	return dp[target]
}

# 2
func numRollsToTarget(d int, f int, target int) int {
	dp := make([][]int, d+1)
	for i := 0; i <= d; i++ {
		dp[i] = make([]int, target+1)
	}
	dp[0][0] = 1
	for i := 1; i <= d; i++ {
		for j := i; j <= target; j++ {
			for k := 1; k <= f; k++ {
				if j >= k {
					dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000007
				}
			}
		}
	}
	return dp[d][target]
}

1156.单字符重复子串的最大长度(1)

• 题目

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
示例 1：输入：text = "ababa" 输出：3
示例 2：输入：text = "aaabaaa" 输出：6
示例 3：输入：text = "aaabbaaa" 输出：4
示例 4：输入：text = "aaaaa" 输出：5
示例 5：输入：text = "abcdef" 输出：1
提示：1 <= text.length <= 20000
text 仅由小写英文字母组成。

• 解题思路

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

func maxRepOpt1(text string) int {
	res := 0
	n := len(text)
	arr := [26]int{}
	for i := 0; i < n; i++ {
		v := int(text[i] - 'a')
		arr[v]++ // 统计每个字母出现的次数
	}
	for i := 0; i < n; {
		v := int(text[i] - 'a')
		countA := 0 // 统计相同的个数
		for i+countA < n && text[i] == text[i+countA] {
			countA++
		}
		j := i + countA + 1
		countB := 0 // 统计相隔1个不同字符往后连续的次数
		for j+countB < n && text[i] == text[j+countB] {
			countB++
		}
		// 2种情况
		// 1、a...axa...ay..a 可以拿1个来补齐:+1
		// 2、没有多余的补齐，可以拿第二段右侧最后一个点或者第一段左侧第一个点来补:+0
		total := min(countA+countB+1, arr[v]) // 取较少的
		res = max(res, total)                 // 更新结果
		i = i + countA                        // 窗口后移

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

1161.最大层内元素和(2)

• 题目

给你一个二叉树的根节点root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中最小 的那个。
示例 1：输入：root = [1,7,0,7,-8,null,null] 输出：2
解释：第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。
示例 2：输入：root = [989,null,10250,98693,-89388,null,null,null,-32127] 输出：2
提示：树中的节点数介于1和10^4之间
-10^5 <= node.val <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	层序遍历	O(n)	O(n)
02	递归	O(n)	O(n)

func maxLevelSum(root *TreeNode) int {
	res := 0
	maxValue := math.MinInt32
	if root == nil {
		return 0
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	level := 1
	for len(queue) > 0 {
		length := len(queue)
		sum := 0
		for i := 0; i < length; i++ {
			node := queue[i]
			sum = sum + node.Val
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		if sum > maxValue {
			maxValue = sum
			res = level
		}
		queue = queue[length:]
		level++
	}
	return res
}

# 2
var arr [][]int

func maxLevelSum(root *TreeNode) int {
	arr = make([][]int, 0)
	if root == nil {
		return 0
	}
	dfs(root, 0)
	res := 0
	maxValue := math.MinInt32
	for i := 0; i < len(arr); i++ {
		sum := 0
		for j := 0; j < len(arr[i]); j++ {
			sum = sum + arr[i][j]
		}
		if sum > maxValue {
			maxValue = sum
			res = i + 1
		}
	}
	return res
}

func dfs(root *TreeNode, level int) {
	if root == nil {
		return
	}
	if level == len(arr) {
		arr = append(arr, []int{})
	}
	arr[level] = append(arr[level], root.Val)
	dfs(root.Left, level+1)
	dfs(root.Right, level+1)
}

1162.地图分析(2)

• 题目

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。
其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
如果网格上只有陆地或者海洋，请返回 -1。
示例 1：输入：[[1,0,1],[0,0,0],[1,0,1]] 输出：2
解释：海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例 2：输入：[[1,0,0],[0,0,0],[0,0,0]] 输出：4
解释：  海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
提示： 1 <= grid.length == grid[0].length <= 100
    grid[i][j] 不是 0 就是 1。

• 解题思路

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

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

func maxDistance(grid [][]int) int {
	queue := make([][2]int, 0)
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 {
				queue = append(queue, [2]int{i, j})
			}
		}
	}
	if len(queue) == 0 || len(queue) == len(grid)*len(grid[0]) {
		return -1
	}
	res := -1
	for len(queue) > 0 {
		res++
		length := len(queue)
		for i := 0; i < length; i++ {
			x1 := queue[i][0]
			y1 := queue[i][1]
			for i := 0; i < 4; i++ {
				x := x1 + dx[i]
				y := y1 + dy[i]
				if 0 <= x && x < len(grid) && 0 <= y && y < len(grid[0]) && grid[x][y] == 0 {
					queue = append(queue, [2]int{x, y})
					grid[x][y] = 2
				}
			}
		}
		queue = queue[length:]
	}
	return res
}

# 2
func maxDistance(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return -1
	}
	n := len(grid)
	m := len(grid[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				dp[i][j] = 0
			} else {
				dp[i][j] = math.MaxInt32
			}
		}
	}
	// 从上往下
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				continue
			}
			if i >= 1 {
				dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
			}
			if j >= 1 {
				dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
			}
		}
	}
	// 从下往上
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if grid[i][j] == 1 {
				continue
			}
			if i < n-1 {
				dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
			}
			if j < m-1 {
				dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
			}
		}
	}
	res := -1
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				continue
			}
			res = max(res, dp[i][j])
		}
	}
	if res == math.MaxInt32 {
		return -1
	}
	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
}

1169.查询无效交易(2)

• 题目

如果出现下述两种情况，交易 可能无效：
交易金额超过 ¥1000
或者，它和另一个城市中同名的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）
每个交易字符串transactions[i]由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。
给你一份交易清单transactions，返回可能无效的交易列表。你可以按任何顺序返回答案。
示例 1：输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出：["alice,20,800,mtv","alice,50,100,beijing"]
解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。
示例 2：输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] 输出：["alice,50,1200,mtv"]
示例 3：输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"] 输出：["bob,50,1200,mtv"]
提示：transactions.length <= 1000
每笔交易transactions[i]按"{name},{time},{amount},{city}"的格式进行记录
每个交易名称{name}和城市{city}都由小写英文字母组成，长度在1到10之间
每个交易时间{time}由一些数字组成，表示一个0到1000之间的整数
每笔交易金额{amount}由一些数字组成，表示一个0 到2000之间的整数

• 解题思路

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

type Node struct {
	Name   string
	Time   int
	Amount int
	City   string
	Index  int
	Flag   bool
}

func invalidTransactions(transactions []string) []string {
	res := make([]string, 0)
	m := make(map[string][]Node)
	n := len(transactions)
	for i := 0; i < n; i++ {
		arr := strings.Split(transactions[i], ",")
		name, city := arr[0], arr[3]
		t, _ := strconv.Atoi(arr[1])
		amount, _ := strconv.Atoi(arr[2])
		m[name] = append(m[name], Node{Name: name, Time: t,
			Amount: amount, City: city, Index: i,
		})
	}
	for _, v := range m {
		sort.Slice(v, func(i, j int) bool {
			return v[i].Time < v[j].Time
		})
		for i := 0; i < len(v); i++ {
			if v[i].Amount > 1000 {
				v[i].Flag = true
			}
			for j := i + 1; j < len(v); j++ {
				if v[j].Time-v[i].Time <= 60 {
					if v[i].City != v[j].City {
						v[i].Flag = true
						v[j].Flag = true
					}
				} else {
					break
				}
			}
		}
	}
	for _, v := range m {
		for i := 0; i < len(v); i++ {
			if v[i].Flag == true {
				res = append(res, transactions[v[i].Index])
			}
		}
	}
	return res
}

# 2
type Node struct {
	Name   string
	Time   int
	Amount int
	City   string
}

func invalidTransactions(transactions []string) []string {
	res := make([]string, 0)
	arr := make([]Node, 0)
	n := len(transactions)
	for i := 0; i < n; i++ {
		temp := strings.Split(transactions[i], ",")
		name, city := temp[0], temp[3]
		t, _ := strconv.Atoi(temp[1])
		amount, _ := strconv.Atoi(temp[2])
		arr = append(arr, Node{Name: name, Time: t, Amount: amount, City: city})
	}
	for i := 0; i < n; i++ {
		if arr[i].Amount > 1000 {
			res = append(res, transactions[i])
			continue
		}
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			if arr[i].Name == arr[j].Name && arr[i].City != arr[j].City &&
				abs(arr[i].Time-arr[j].Time) <= 60 {
				res = append(res, transactions[i])
				break
			}
		}
	}
	return res
}

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

1171.从链表中删去总和值为零的连续节点(4)

• 题目

给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，
直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
示例 1：输入：head = [1,2,-3,3,1] 输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
示例 2：输入：head = [1,2,3,-3,4] 输出：[1,2,4]
示例 3：输入：head = [1,2,3,-3,-2] 输出：[1]
提示：给你的链表中可能有 1 到1000个节点。 
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	遍历	O(n)	O(1)
03	哈希辅助	O(n)	O(n)
04	递归	O(n^2)	O(n)

func removeZeroSumSublists(head *ListNode) *ListNode {
	m := make(map[int]*ListNode)
	res := head
	sum := 0
	for cur := head; cur != nil; cur = cur.Next {
		sum = sum + cur.Val
		if sum == 0 { // 当前都为0
			res = cur.Next
			m = make(map[int]*ListNode)
			continue
		}
		if _, ok := m[sum]; ok == false {
			m[sum] = cur
			continue
		}
		// 出现重复
		first := m[sum]
		tempSum := sum
		for temp := first.Next; temp != cur; temp = temp.Next {
			tempSum = tempSum + temp.Val
			delete(m, tempSum)
		}
		first.Next = cur.Next
	}
	return res
}

# 2
func removeZeroSumSublists(head *ListNode) *ListNode {
	res := &ListNode{Next: head}
	for cur := res; cur != nil; {
		sum := 0
		for temp := cur.Next; temp != nil; temp = temp.Next {
			sum = sum + temp.Val
			if sum == 0 {
				cur.Next = temp.Next // 调整指针
			}
		}
		cur = cur.Next
	}
	return res.Next
}

# 3
func removeZeroSumSublists(head *ListNode) *ListNode {
	res := &ListNode{Next: head}
	m := make(map[int]*ListNode)
	sum := 0
	for cur := res; cur != nil; cur = cur.Next {
		sum = sum + cur.Val
		m[sum] = cur
	}
	sum = 0
	for cur := res; cur != nil; cur = cur.Next {
		sum = sum + cur.Val
		cur.Next = m[sum].Next
	}
	return res.Next
}

# 4
func removeZeroSumSublists(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	sum := 0
	for cur := head; cur != nil; cur = cur.Next {
		sum = sum + cur.Val
		if sum == 0 {
			return removeZeroSumSublists(cur.Next)
		}
	}
	head.Next = removeZeroSumSublists(head.Next)
	return head
}

1177.构建回文串检测(1)

• 题目

给你一个字符串s，请你对s的子串进行检测。
每次检测，待检子串都可以表示为queries[i] = [left, right, k]。
我们可以 重新排列 子串s[left], ..., s[right]，并从中选择 最多 k项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为true，否则结果为false。
返回答案数组answer[]，其中answer[i]是第i个待检子串queries[i]的检测结果。
注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，
也就是说，如果s[left..right] = "aaa"且k = 2，我们只能替换其中的两个字母。
（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
示例：输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] 输出：[true,false,false,true,true]
解释：queries[0] : 子串 = "d"，回文。
queries[1] :子串 = "bc"，不是回文。
queries[2] :子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] :子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] :子串 = "abcda"，可以变成回文的 "abcba"。
提示：1 <= s.length,queries.length<= 10^5
0 <= queries[i][0] <= queries[i][1] <s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+位运算	O(n)	O(n)

func canMakePaliQueries(s string, queries [][]int) []bool {
	n := len(s)
	arr := make([]int, n+1)
	cur := 0
	for i := 0; i < n; i++ {
		value := int(s[i] - 'a')
		cur = cur ^ (1 << value)
		arr[i+1] = cur
	}
	res := make([]bool, len(queries))
	for i := 0; i < len(queries); i++ {
		a, b, c := queries[i][0], queries[i][1], queries[i][2]
		status := arr[b+1] ^ arr[a]
		if bits.OnesCount(uint(status)) <= 2*c+1 { // 奇数次字母的个数，重新排列后最多允许2*c+1个
			res[i] = true
		}
	}
	return res
}

1186.删除一次得到子数组最大和(2)

• 题目

给你一个整数数组，返回它的某个非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），
（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
请看示例：
示例 1：输入：arr = [1,-2,0,3] 输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：输入：arr = [1,-2,-2,3] 输出：3
解释：我们直接选出 [3]，这就是最大和。
示例 3：输入：arr = [-1,-1,-1,-1] 输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
提示：1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

• 解题思路

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

func maximumSum(arr []int) int {
	n := len(arr)
	dp := make([][2]int, n)
	dp[0][0] = arr[0] // 不删
	dp[0][1] = 0      // 删除
	res := dp[0][0]   // 长度为1，不删除
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0]+arr[i], arr[i])
		dp[i][1] = max(dp[i-1][1]+arr[i], dp[i-1][0])
		res = max(res, max(dp[i][0], dp[i][1]))
	}
	return res
}

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

# 2
func maximumSum(arr []int) int {
	n := len(arr)
	a := arr[0] // 不删
	b := 0      // 删除
	res := a    // 长度为1，不删除
	for i := 1; i < n; i++ {
		a, b = max(a+arr[i], arr[i]), max(b+arr[i], a)
		res = max(res, max(a, b))
	}
	return res
}

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

1190.反转每对括号间的子串(2)

• 题目

给出一个字符串s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例 1：输入：s = "(abcd)" 输出："dcba"
示例 2：输入：s = "(u(love)i)" 输出："iloveu"
示例 3：输入：s = "(ed(et(oc))el)" 输出："leetcode"
示例 4：输入：s = "a(bcdefghijkl(mno)p)q" 输出："apmnolkjihgfedcbq"
提示：0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

• 解题思路

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

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

func reverse(arr []byte, i, j int) {
	for i < j {
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
}

# 2
func reverseParentheses(s string) string {
	stack := make([]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else if s[i] == ')' {
			last := stack[len(stack)-1]
			m[i] = last
			m[last] = i
			stack = stack[:len(stack)-1]
		}
	}
	dir := 1
	res := make([]byte, 0)
	for i := 0; i < len(s); i = i + dir {
		if s[i] == '(' || s[i] == ')' {
			i = m[i]   // 从反方向遍历
			dir = -dir // 变换方向，+1/-1
		} else {
			res = append(res, s[i])
		}
	}
	return string(res)
}

1191.K次串联后最大子数组之和(1)

• 题目

给你一个整数数组 arr 和一个整数 k。
首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
    举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后，请你返回修改后的数组中的最大的子数组之和。
注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。 
示例 1：输入：arr = [1,2], k = 3 输出：9
示例 2：输入：arr = [1,-2,1], k = 5 输出：2
示例 3：输入：arr = [-1,-2], k = 7 输出：0
提示：
    1 <= arr.length <= 10^5
    1 <= k <= 10^5
    -10^4 <= arr[i] <= 10^4

• 解题思路

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

func kConcatenationMaxSum(arr []int, k int) int {
	cur := 0
	sum := 0
	res := 0
	for i := 0; i < len(arr); i++ {
		sum = sum + arr[i]
		cur = max(cur+arr[i], arr[i])
		res = max(res, cur)
	}
	for i := 0; i < len(arr); i++ {
		cur = max(cur+arr[i], arr[i])
		res = max(res, cur)
	}
	if sum <= 0 {
		return res % 1000000007
	}
	return (res + (k-2)*sum) % 1000000007
}

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

1101-1200-Hard

1147.段式回文(2)

• 题目

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符而不是 单个字母。
举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把"volvo" 分为 "vo"、"l"、"vo" 三段，
则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。
给你一个字符串text，在确保它满足段式回文的前提下，请你返回 段 的最大数量k。
如果段的最大数量为k，那么存在满足以下条件的a_1, a_2, ..., a_k：
每个a_i都是一个非空字符串；
将这些字符串首位相连的结果a_1 + a_2 + ... + a_k和原始字符串text相同；
对于所有1 <= i <= k，都有a_i = a_{k+1 - i}。
示例 1：输入：text = "ghiabcdefhelloadamhelloabcdefghi" 输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
示例 2：输入：text = "merchant" 输出：1
解释：我们可以把字符串拆分成 "(merchant)"。
示例 3：输入：text = "antaprezatepzapreanta" 输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。
示例 4：输入：text = "aaa" 输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。
提示：text仅由小写英文字符组成。
1 <= text.length <= 1000

• 解题思路

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

func longestDecomposition(text string) int {
	n := len(text)
	if n <= 1 {
		return n
	}
	for i := 1; i <= n/2; i++ {
		if text[:i] == text[n-i:] {
			return 2 + longestDecomposition(text[i:n-i])
		}
	}
	return 1
}

# 2
func longestDecomposition(text string) int {
	n := len(text)
	if n <= 1 {
		return n
	}
	res := 0
	left, right := 0, n
	for left < right {
		for k := 1; ; k++ {
			if k > (right-left)/2 { // 长度超过剩下的1/2
				res++
				return res
			}
			if text[left:left+k] == text[right-k:right] {
				res = res + 2 // 可以切割，长度+2
				left = left + k
				right = right - k
				break
			}
		}
	}
	return res
}

1187.使数组严格递增

题目

给你两个整数数组arr1 和 arr2，返回使arr1严格递增所需要的最小「操作」数（可能为 0）。
每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，
分别为i 和j，0 <=i < arr1.length和0 <= j < arr2.length，然后进行赋值运算arr1[i] = arr2[j]。
如果无法让arr1严格递增，请返回-1。
示例 1：输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] 输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。
示例 2：输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1] 输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。
示例3：输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3] 输出：-1
解释：无法使 arr1 严格递增。
提示：1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

解题思路

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