1701-1800-Easy¶

1704.判断字符串的两半是否相似(1)¶

题目

给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半，前一半为 a ，后一半为 b 。
两个字符串 相似 的前提是它们都含有相同数目的元音（'a'，'e'，'i'，'o'，'u'，'A'，'E'，'I'，'O'，'U'）。注意，s 可能同时含有大写和小写字母。
如果 a 和 b 相似，返回 true ；否则，返回 false 。
示例 1：输入：s = "book" 输出：true
解释：a = "bo" 且 b = "ok" 。a 中有 1 个元音，b 也有 1 个元音。所以，a 和 b 相似。
示例 2：输入：s = "textbook" 输出：false
解释：a = "text" 且 b = "book" 。a 中有 1 个元音，b 中有 2 个元音。因此，a 和 b 不相似。
注意，元音 o 在 b 中出现两次，记为 2 个。
示例 3：输入：s = "MerryChristmas" 输出：false
示例 4：输入：s = "AbCdEfGh" 输出：true
提示：2 <= s.length <= 1000
s.length 是偶数
s 由 大写和小写 字母组成

解题思路

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

func halvesAreAlike(s string) bool {
	s = strings.ToLower(s)
	total := 0
	for i := 0; i < len(s); i++ {
		if isVowel(s[i]) == true {
			if i < len(s)/2 {
				total++
			} else {
				total--
			}
		}
	}
	return total == 0
}

func isVowel(b byte) bool {
	return b == 'a' || b == 'e' ||
		b == 'i' || b == 'o' || b == 'u'
}

1710.卡车上的最大单元数(1)¶

题目

请你将一些箱子装在 一辆卡车 上。
给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。
只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载单元 的 最大 总数。
示例 1：输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
示例 2：输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 输出：91
提示：1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106

解题思路

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

func maximumUnits(boxTypes [][]int, truckSize int) int {
	sort.Slice(boxTypes, func(i, j int) bool {
		return boxTypes[i][1] > boxTypes[j][1]
	})
	res := 0
	for i := 0; i < len(boxTypes); i++ {
		if boxTypes[i][0] <= truckSize {
			res = res + boxTypes[i][0]*boxTypes[i][1]
		} else {
			res = res + truckSize*boxTypes[i][1]
			break
		}
		truckSize = truckSize - boxTypes[i][0]
	}
	return res
}

1716.计算力扣银行的钱(2)¶

题目

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
最开始，他在周一的时候存入 1块钱。从周二到周日，他每天都比前一天多存入 1块钱。
在接下来每一个周一，他都会比 前一个周一 多存入 1块钱。
给你n，请你返回在第 n天结束的时候他在力扣银行总共存了多少块钱。
示例 1：输入：n = 4 输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。
示例 2：输入：n = 10 输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。
注意到第二个星期一，Hercy 存入 2 块钱。
示例 3：输入：n = 20 输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) +
(2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。
提示：1 <= n <= 1000

解题思路

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

func totalMoney(n int) int {
	res := 0
	for i := 0; i < n; i++ {
		a, b := i/7, i%7+1
		res = res + a + b
	}
	return res
}

# 2
func totalMoney(n int) int {
	res := 0
	a, b := n/7, n%7
	res = res + (28+(a-1)*7+28)*a/2
	res = res + (a+1+a+b)*b/2
	return res
}

1720.解码异或后的数组(1)¶

题目

未知 整数数组 arr 由 n 个非负整数组成。
经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。
例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
示例 1：输入：encoded = [1,2,3], first = 1 输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，
那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
示例 2：输入：encoded = [6,2,7,3], first = 4 输出：[4,2,0,7,4]
提示：2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105

解题思路

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

func decode(encoded []int, first int) []int {
	res := make([]int, 0)
	res = append(res, first)
	for i := 0; i < len(encoded); i++ {
		res = append(res, encoded[i]^res[len(res)-1])
	}
	return res
}

1725.可以形成最大正方形的矩形数目(1)¶

题目

给你一个数组 rectangles ，其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。
如果存在 k 同时满足 k <= li 和 k <= wi ，就可以将第 i 个矩形切成边长为 k 的正方形。
例如，矩形 [4,6] 可以切成边长最大为 4 的正方形。
设 maxLen 为可以从矩形数组rectangles 切分得到的 最大正方形 的边长。
返回可以切出边长为 maxLen 的正方形的矩形 数目 。
示例 1：输入：rectangles = [[5,8],[3,9],[5,12],[16,5]] 输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。
示例 2：输入：rectangles = [[2,3],[3,7],[4,3],[3,7]] 输出：3
提示：1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi

解题思路

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

func countGoodRectangles(rectangles [][]int) int {
	res := 0
	maxValue := 0
	for i := 0; i < len(rectangles); i++ {
		minValue := min(rectangles[i][0], rectangles[i][1])
		if minValue > maxValue {
			res = 1
			maxValue = minValue
		} else if minValue == maxValue {
			res++
		}
	}
	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
}

1732.找到最高海拔(1)¶

题目

有一个自行车手打算进行一场公路骑行，这条路线总共由n + 1个不同海拔的点组成。
自行车手从海拔为 0的点0开始骑行。
给你一个长度为 n的整数数组gain，
其中 gain[i]是点 i和点 i + 1的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。
示例 1：输入：gain = [-5,1,5,0,-7] 输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
示例 2：输入：gain = [-4,-3,-2,-1,4,3,2] 输出：0
解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。
提示：n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

解题思路

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

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

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

1736.替换隐藏数字得到的最晚时间(1)¶

题目

给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。
替换time 中隐藏的数字，返回你可以得到的最晚有效时间。
示例 1：输入：time = "2?:?0" 输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。
示例 2：输入：time = "0?:3?" 输出："09:39"
示例 3：输入：time = "1?:22" 输出："19:22"
提示：time 的格式为 hh:mm
题目数据保证你可以由输入的字符串生成有效的时间

解题思路

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

func maximumTime(time string) string {
   res := []byte(time)
   for i := 0; i < len(res); i++ {
   	if res[i] == '?' {
   		if i == 0 && (('0' <= time[1] && time[1] <= '3') || time[1] == '?') {
   			res[i] = '2'
   		} else {
   			res[i] = '1'
   		}
   		if i == 1 {
   			if time[0] == '2' || res[0] == '2' {
   				res[i] = '3'
   			} else {
   				res[i] = '9'
   			}
   		}
   		if i == 3 {
   			res[i] = '5'
   		}
   		if i == 4 {
   			res[i] = '9'
   		}
   	}
   }
   return string(res)
}

1742.盒子中小球的最大数量(1)¶

题目

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，
到 highLimit 结束（包括 lowLimit 和highLimit ，即n == highLimit - lowLimit + 1）。
另有无限数量的盒子，编号从 1 到 infinity 。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。
例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，
而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。
如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
示例 1：输入：lowLimit = 1, highLimit = 10 输出：2
解释：盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。
示例 2：输入：lowLimit = 5, highLimit = 15 输出：2
解释：盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。
示例 3：输入：lowLimit = 19, highLimit = 28 输出：2
解释：盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。
提示：1 <= lowLimit <= highLimit <= 105

解题思路

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

func countBalls(lowLimit int, highLimit int) int {
	res := 0
	m := make(map[int]int)
	for i := lowLimit; i <= highLimit; i++ {
		sum := getSum(i)
		m[sum]++
		if m[sum] > res {
			res = m[sum]
		}
	}
	return res
}

func getSum(i int) int {
	sum := 0
	for i > 0 {
		sum = sum + i%10
		i = i / 10
	}
	return sum
}

1748.唯一元素的和(1)¶

题目

给你一个整数数组nums。数组中唯一元素是那些只出现恰好一次的元素。
请你返回 nums中唯一元素的 和。
示例 1：输入：nums = [1,2,3,2] 输出：4
解释：唯一元素为 [1,3] ，和为 4 。
示例 2：输入：nums = [1,1,1,1,1] 输出：0
解释：没有唯一元素，和为 0 。
示例 3 ：输入：nums = [1,2,3,4,5] 输出：15
解释：唯一元素为 [1,2,3,4,5] ，和为 15 。
提示：1 <= nums.length <= 100
1 <= nums[i] <= 100

解题思路

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

func sumOfUnique(nums []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	for k, v := range m {
		if v == 1 {
			res = res + k
		}
	}
	return res
}

1752.检查数组是否经排序和轮转得到(2)¶

题目

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，
当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
示例 1：输入：nums = [3,4,5,1,2] 输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
示例 2：输入：nums = [2,1,3,4] 输出：false
解释：源数组无法经轮转得到 nums 。
示例 3：输入：nums = [1,2,3] 输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。
示例 4：输入：nums = [1,1,1] 输出：true
解释：[1,1,1] 为有序的源数组。
轮转任意个位置都可以得到 nums 。
示例 5：输入：nums = [2,1] 输出：true
解释：[1,2] 为有序的源数组。
可以轮转 x = 5 个位置，使新数组从值为 2 的元素开始：[2,1] 。
提示：1 <= nums.length <= 100
1 <= nums[i] <= 100

解题思路

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

func check(nums []int) bool {
	temp := make([]int, len(nums))
	copy(temp, nums)
	sort.Ints(temp)
	nums = append(nums, nums...)
	a := change(temp)
	b := change(nums)
	if strings.Contains(b, a) {
		return true
	}
	return false
}

func change(arr []int) string {
	res := ""
	for i := 0; i < len(arr); i++ {
		res = res + strconv.Itoa(arr[i]) + ","
	}
	res = strings.TrimRight(res, ",")
	return res
}

# 2
func check(nums []int) bool {
	count := 0
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] > nums[i+1] {
			count++
			if count > 1 {
				return false
			}
			if nums[0] < nums[len(nums)-1] {
				return false
			}
		}
	}
	return true
}

1758.生成交替二进制字符串的最少操作数(2)¶

题目

给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。
一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。
交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。
例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
示例 1：输入：s = "0100" 输出：1
解释：如果将最后一个字符变为 '1' ，s 就变成 "0101" ，即符合交替字符串定义。
示例 2：输入：s = "10" 输出：0
解释：s 已经是交替字符串。
示例 3：输入：s = "1111" 输出：2
解释：需要 2 步操作得到 "0101" 或 "1010" 。
提示：1 <= s.length <= 104
s[i] 是 '0' 或 '1'

解题思路

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

func minOperations(s string) int {
	a, b := 0, 0
	for i := 0; i < len(s); i++ {
		if i%2 == 0 && s[i] == '1' { // a以偶0，奇1
			a++
		} else if i%2 == 1 && s[i] == '0' {
			a++
		}
		if i%2 == 0 && s[i] == '0' { // b以偶1，奇0
			b++
		} else if i%2 == 1 && s[i] == '1' {
			b++
		}
	}
	if a > b {
		return b
	}
	return a
}

# 2
func minOperations(s string) int {
	a, b := 0, 0
	for i := 0; i < len(s); i++ {
		if int(s[i]-'0')%2 != i%2 {
			a++
		} else {
			b++
		}
	}
	if a > b {
		return b
	}
	return a
}

1763.最长的美好子字符串(1)¶

题目

当一个字符串 s包含的每一种字母的大写和小写形式 同时出现在 s中，就称这个字符串s是 美好 字符串。
比方说，"abABB"是美好字符串，因为'A' 和'a'同时出现了，且'B' 和'b'也同时出现了。
然而，"abA"不是美好字符串因为'b'出现了，而'B'没有出现。
给你一个字符串s，请你返回s最长的美好子字符串。
如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。
示例 1：输入：s = "YazaAay" 输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。
示例 2：输入：s = "Bb" 输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。
示例 3：输入：s = "c" 输出：""
解释：没有美好子字符串。
示例 4：输入：s = "dDzeE" 输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。
提示：1 <= s.length <= 100
s只包含大写和小写英文字母。

解题思路

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

func longestNiceSubstring(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		for j := i + 1; j <= len(s); j++ {
			if judge(s[i:j]) == true && len(s[i:j]) > len(res) {
				res = s[i:j]
			}
		}
	}
	return res
}

func judge(str string) bool {
	a := [26]int{}
	A := [26]int{}
	for i := 0; i < len(str); i++ {
		if 'a' <= str[i] && str[i] <= 'z' {
			a[str[i]-'a']++
		} else {
			A[str[i]-'A']++
		}
	}
	for i := 0; i < 26; i++ {
		if (a[i] > 0 && A[i] == 0) || (a[i] == 0 && A[i] > 0) {
			return false
		}
	}
	return true
}

1768.交替合并字符串(2)¶

题目

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。
如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
返回 合并后的字符串 。
示例 1：输入：word1 = "abc", word2 = "pqr" 输出："apbqcr"
解释：字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r
示例 2：输入：word1 = "ab", word2 = "pqrs" 输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s
示例 3：输入：word1 = "abcd", word2 = "pq" 输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d
提示：1 <= word1.length, word2.length <= 100
word1 和 word2 由小写英文字母组成

解题思路

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

func mergeAlternately(word1 string, word2 string) string {
	res := ""
	i, j := 0, 0
	for i < len(word1) && j < len(word2) {
		res = res + string(word1[i])
		res = res + string(word2[j])
		i++
		j++
	}
	if i < len(word1) {
		res = res + string(word1[i:])
	}
	if j < len(word2) {
		res = res + string(word2[j:])
	}
	return res
}

# 2
func mergeAlternately(word1 string, word2 string) string {
	res := ""
	for i := 0; i < len(word1) || i < len(word2); i++ {
		if i < len(word1) {
			res = res + string(word1[i])
		}
		if i < len(word2) {
			res = res + string(word2[i])
		}
	}
	return res
}

1773.统计匹配检索规则的物品数量(1)¶

题目

给你一个数组 items ，其中items[i] = [typei, colori, namei] ，
描述第 i 件物品的类型、颜色以及名称。
另给你一条由两个字符串ruleKey 和 ruleValue 表示的检索规则。
如果第 i 件物品能满足下述条件之一，则认为该物品与给定的检索规则 匹配 ：
ruleKey == "type" 且 ruleValue == typei 。
ruleKey == "color" 且 ruleValue == colori 。
ruleKey == "name" 且 ruleValue == namei 。
统计并返回 匹配检索规则的物品数量 。
示例 1：输入：items = [["phone","blue","pixel"],["computer","silver","lenovo"],
["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
输出：1 解释：只有一件物品匹配检索规则，这件物品是 ["computer","silver","lenovo"] 。
示例 2：输入：items = [["phone","blue","pixel"],["computer","silver","phone"],
["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
输出：2 解释：只有两件物品匹配检索规则，这两件物品分别是 ["phone","blue","pixel"] 和 ["phone","gold","iphone"] 。
注意，["computer","silver","phone"] 未匹配检索规则。
提示：1 <= items.length <= 104
1 <= typei.length, colori.length, namei.length, ruleValue.length <= 10
ruleKey 等于 "type"、"color" 或 "name"
所有字符串仅由小写字母组成

解题思路

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

func countMatches(items [][]string, ruleKey string, ruleValue string) int {
	res := 0
	for i := 0; i < len(items); i++ {
		if ruleKey == "type" && items[i][0] == ruleValue {
			res++
		} else if ruleKey == "color" && items[i][1] == ruleValue {
			res++
		} else if ruleKey == "name" && items[i][2] == ruleValue {
			res++
		}
	}
	return res
}

1779.找到最近的有相同X或Y坐标的点(1)¶

题目

给你两个整数x 和y，表示你在一个笛卡尔坐标系下的(x, y)处。
同时，在同一个坐标系下给你一个数组points，其中points[i] = [ai, bi]表示在(ai, bi)处有一个点。
当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的。
请返回距离你当前位置曼哈顿距离最近的有效点的下标（下标从 0 开始）。
如果有多个最近的有效点，请返回下标最小的一个。如果没有有效点，请返回-1。
两个点 (x1, y1)和 (x2, y2)之间的 曼哈顿距离为abs(x1 - x2) + abs(y1 - y2)。
示例 1：输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] 输出：2
解释：所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。
有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。
示例 2：输入：x = 3, y = 4, points = [[3,4]] 输出：0
提示：答案可以与你当前所在位置坐标相同。
示例 3：输入：x = 3, y = 4, points = [[2,3]] 输出：-1
解释：没有有效点。
提示：1 <= points.length <= 104
points[i].length == 2
1 <= x, y, ai, bi <= 104

解题思路

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

func nearestValidPoint(x int, y int, points [][]int) int {
	res := -1
	maxValue := math.MaxInt32
	for i := 0; i < len(points); i++ {
		a, b := points[i][0], points[i][1]
		if a == x || b == y {
			value := abs(a-x) + abs(b-y)
			if value < maxValue {
				res = i
				maxValue = value
			}
		}
	}
	return res
}

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

1784.检查二进制字符串字段(3)¶

题目

给你一个二进制字符串 s ，该字符串 不含前导零 。
如果 s 最多包含 一个由连续的 '1' 组成的字段 ，返回 true 。否则，返回 false 。
示例 1：输入：s = "1001" 输出：false
解释：字符串中的 1 没有形成一个连续字段。
示例 2：输入：s = "110" 输出：true
提示：1 <= s.length <= 100
s[i]为 '0' 或 '1'
s[0] 为 '1'

解题思路

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

func checkOnesSegment(s string) bool {
	flag := true
	for i := 0; i < len(s); i++ {
		if s[i] == '0' {
			flag = false
		}
		if flag == false && s[i] == '1' {
			return false
		}
	}
	return true
}

# 2
func checkOnesSegment(s string) bool {
	if strings.Contains(s, "01") {
		return false
	}
	return true
}

# 3
func checkOnesSegment(s string) bool {
	arr := strings.Split(s, "0")
	return len(arr) == 1
}

1790.仅执行一次字符串交换能否使两个字符串相等(1)¶

题目

给你长度相等的两个字符串 s1 和 s2 。
一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
示例 1：输入：s1 = "bank", s2 = "kanb" 输出：true
解释：例如，交换 s2 中的第一个和最后一个字符可以得到 "bank"
示例 2：输入：s1 = "attack", s2 = "defend" 输出：false
解释：一次字符串交换无法使两个字符串相等
示例 3：输入：s1 = "kelb", s2 = "kelb" 输出：true
解释：两个字符串已经相等，所以不需要进行字符串交换
示例 4：输入：s1 = "abcd", s2 = "dcba" 输出：false
提示：1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成

解题思路

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

func areAlmostEqual(s1 string, s2 string) bool {
	if s1 == s2 {
		return true
	}
	if len(s1) != len(s2) {
		return false
	}
	arr := make([]int, 0)
	count := 0
	for i := 0; i < len(s1); i++ {
		if s1[i] != s2[i] {
			arr = append(arr, i)
			count++
		}
	}
	if count != 2 {
		return false
	}
	if s1[arr[0]] == s2[arr[1]] && s1[arr[1]] == s2[arr[0]] {
		return true
	}
	return false
}

1796.字符串中第二大的数字(1)¶

题目

给你一个混合字符串s，请你返回 s中 第二大 的数字，如果不存在第二大的数字，请你返回 -1。
混合字符串 由小写英文字母和数字组成。
示例 1：输入：s = "dfa12321afd" 输出：2
解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
示例 2：输入：s = "abc1111" 输出：-1
解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。
提示：1 <= s.length <= 500
s只包含小写英文字母和（或）数字。

解题思路

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

func secondHighest(s string) int {
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		if '0' <= s[i] && s[i] <= '9' {
			m[int(s[i]-'0')]++
		}
	}
	count := 0
	for i := 9; i >= 0; i-- {
		if m[i] > 0 {
			count++
			if count == 2 {
				return i
			}
		}
	}
	return -1
}

1800.最大升序子数组和(2)¶

题目

给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。
子数组是数组中的一个连续数字序列。
已知子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，若对所有 i（l <= i < r），
numsi < numsi+1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。
示例 1：输入：nums = [10,20,30,5,10,50] 输出：65
解释：[5,10,50] 是元素和最大的升序子数组，最大元素和为 65 。
示例 2：输入：nums = [10,20,30,40,50] 输出：150
解释：[10,20,30,40,50] 是元素和最大的升序子数组，最大元素和为 150 。 
示例 3：输入：nums = [12,17,15,13,10,11,12] 输出：33
解释：[10,11,12] 是元素和最大的升序子数组，最大元素和为 33 。 
示例 4：输入：nums = [100,10,1] 输出：100
提示：1 <= nums.length <= 100
1 <= nums[i] <= 100

解题思路

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

func maxAscendingSum(nums []int) int {
	res, sum := nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i-1] < nums[i] {
			sum = sum + nums[i]
		} else {
			sum = nums[i]
		}
		res = max(res, sum)
	}
	return res
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

# 2
func maxAscendingSum(nums []int) int {
	res := nums[0]
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i-1] < nums[i] {
			dp[i] = dp[i-1] + nums[i]
		} else {
			dp[i] = nums[i]
		}
		res = max(res, dp[i])
	}
	return res
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

1701-1800-Medium¶

1701.平均等待时间(1)¶

题目

有一个餐厅，只有一位厨师。你有一个顾客数组customers，其中customers[i] = [arrivali, timei]：
arrivali是第i位顾客到达的时间，到达时间按 非递减 顺序排列。
timei是给第 i位顾客做菜需要的时间。
当一位顾客到达时，他将他的订单给厨师，厨师一旦空闲的时候就开始做这位顾客的菜。
每位顾客会一直等待到厨师完成他的订单。
厨师同时只能做一个人的订单。厨师会严格按照 订单给他的顺序做菜。
请你返回所有顾客需要等待的 平均时间。与标准答案误差在10-5范围以内，都视为正确结果。
示例 1：输入：customers = [[1,2],[2,5],[4,3]] 输出：5.00000
解释：1) 第一位顾客在时刻 1 到达，厨师拿到他的订单并在时刻 1 立马开始做菜，
并在时刻 3 完成，第一位顾客等待时间为 3 - 1 = 2 。
2) 第二位顾客在时刻 2 到达，厨师在时刻 3 开始为他做菜，
并在时刻 8 完成，第二位顾客等待时间为 8 - 2 = 6 。
3) 第三位顾客在时刻 4 到达，厨师在时刻 8 开始为他做菜，并在时刻 11 完成，
第三位顾客等待时间为 11 - 4 = 7 。
平均等待时间为 (2 + 6 + 7) / 3 = 5 。
示例 2：输入：customers = [[5,2],[5,4],[10,3],[20,1]] 输出：3.25000
解释：1) 第一位顾客在时刻 5 到达，厨师拿到他的订单并在时刻 5 立马开始做菜，
并在时刻 7 完成，第一位顾客等待时间为 7 - 5 = 2 。
2) 第二位顾客在时刻 5 到达，厨师在时刻 7 开始为他做菜，并在时刻 11 完成，
第二位顾客等待时间为 11 - 5 = 6 。
3) 第三位顾客在时刻 10 到达，厨师在时刻 11 开始为他做菜，并在时刻 14 完成，
第三位顾客等待时间为 14 - 10 = 4 。
4) 第四位顾客在时刻 20 到达，厨师拿到他的订单并在时刻 20 立马开始做菜，
并在时刻 21 完成，第四位顾客等待时间为 21 - 20 = 1 。
平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。
提示：1 <= customers.length <= 105
1 <= arrivali, timei <= 104
arrivali<= arrivali+1

解题思路

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

func averageWaitingTime(customers [][]int) float64 {
	sum := 0
	cur := customers[0][0]
	for i := 0; i < len(customers); i++ {
		if cur < customers[i][0] {
			cur = customers[i][0] + customers[i][1]
		} else {
			cur = cur + customers[i][1] // 做菜时间
		}
		wait := cur - customers[i][0] // 等待时间
		sum = sum + wait
	}
	return float64(sum) / float64(len(customers))
}

1702.修改后的最大二进制字符串(2)¶

题目

给你一个二进制字符串binary，它仅有0或者1组成。你可以使用下面的操作任意次对它进行修改：
操作 1 ：如果二进制串包含子字符串"00"，你可以用"10"将其替换。
比方说，"00010" -> "10010"
操作 2 ：如果二进制串包含子字符串"10"，你可以用"01"将其替换。
比方说，"00010" -> "00001"
请你返回执行上述操作任意次以后能得到的 最大二进制字符串。
如果二进制字符串 x对应的十进制数字大于二进制字符串 y对应的十进制数字，
那么我们称二进制字符串x大于二进制字符串y。
示例 1：输入：binary = "000110" 输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"
示例 2：输入：binary = "01" 输出："01"
解释："01" 没办法进行任何转换。
提示：1 <= binary.length <= 105
binary 仅包含'0' 和'1' 。

解题思路

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

func maximumBinaryString(binary string) string {
	flag := true
	rightOne := 0 // 记录第1个0后面1的数量
	for i := 0; i < len(binary); i++ {
		if binary[i] == '0' {
			flag = false
		} else {
			if flag == false {
				rightOne++
			}
		}
	}
	if flag == true { // 全是1，直接返回
		return binary
	}
	// 首先：第1个0之前的1不需要移动。
	// 然后：把第1个0之后的1移到后面，后移：10=>01。
	// 最后：然后把中间的000，都变成110，00=>10。
	arr := make([]byte, len(binary))
	for i := 0; i < len(arr); i++ {
		arr[i] = '1'
	}
	arr[len(arr)-1-rightOne] = '0'
	return string(arr)
}

# 2
func maximumBinaryString(binary string) string {
	n := len(binary)
	count := strings.Count(binary, "1")
	if count >= n-1 {
		return binary
	}
	indexZero := strings.IndexByte(binary, '0')
	count = count - indexZero
	return strings.Repeat("1", n-1-count) + "0" + strings.Repeat("1", count)
}

1705.吃苹果的最大数目(2)¶

题目

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。
在第 i 天，树上会长出 apples[i] 个苹果，
这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。
也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
示例 1：输入：apples = [1,2,3,5,2], days = [3,2,1,4,2] 输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。
示例 2：输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2] 输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。
提示：apples.length == n
days.length == n
1 <= n <= 2 * 104
0 <= apples[i], days[i] <= 2 * 104
只有在 apples[i] = 0 时，days[i] = 0 才成立

解题思路

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

func eatenApples(apples []int, days []int) int {
	res := 0
	nodeHeap := make(NodeHeap, 0)
	heap.Init(&nodeHeap)
	for i := 0; i < len(apples) || nodeHeap.Len() > 0; i++ {
		if i < len(apples) && apples[i] > 0 {
			heap.Push(&nodeHeap, Node{
				date: days[i] + i,
				num:  apples[i],
			})
		}
		for nodeHeap.Len() > 0 && nodeHeap[0].date == i {
			heap.Pop(&nodeHeap)
		}
		if nodeHeap.Len() > 0 && nodeHeap[0].num > 0 {
			res++
			nodeHeap[0].num--
			if nodeHeap[0].num == 0 {
				heap.Pop(&nodeHeap)
			}
		}
	}
	return res
}

type Node struct {
	date int
	num  int
}

type NodeHeap []Node

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

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

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

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

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

# 2
func eatenApples(apples []int, days []int) int {
	arr := make([]int, 40000)
	res := 0
	left, right := 0, 0
	for i := 0; ; i++ {
		if i < len(apples) {
			target := i + days[i] // 保质期内
			arr[target] = arr[target] + apples[i]
			if target > right {
				right = target
			}
			if left > target {
				left = target
			}
		} else {
			if left > right {
				break
			}
		}
		// 吃苹果
		for left = i + 1; left <= right; left++ {
			if arr[left] > 0 {
				res++
				arr[left]--
				break
			}
		}
	}
	return res
}

1706.球会落何处(3)¶

题目

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。
将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。
如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
返回一个大小为 n 的数组 answer ，
其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。
示例 1：
输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
示例 2：输入：grid = [[-1]] 输出：[-1]
解释：球被卡在箱子左侧边上。
示例 3：输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 为 1 或 -1

解题思路

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

func findBall(grid [][]int) []int {
	n, m := len(grid), len(grid[0])
	res := make([]int, m)
	for i := 0; i < m; i++ {
		res[i] = i
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if res[j] != -1 {
				if res[j] != m-1 && grid[i][res[j]] == 1 && grid[i][res[j]+1] == 1 { // 向右侧 \
					res[j] = res[j] + 1 // 坐标向右+1
				} else if res[j] != 0 && grid[i][res[j]] == -1 && grid[i][res[j]-1] == -1 { // 向左侧 /
					res[j] = res[j] - 1 // 坐标向左-1
				} else {
					res[j] = -1
				}
			}
		}
	}
	return res
}

# 2
func findBall(grid [][]int) []int {
	n, m := len(grid), len(grid[0])
	res := make([]int, 0)
	for j := 0; j < m; j++ { // 每列模拟
		index := j
		for i := 0; i < n; i++ {
			if (grid[i][index] == 1 && (index == m-1 || grid[i][index+1] == -1)) ||
				(grid[i][index] == -1 && (index == 0 || grid[i][index-1] == 1)) {
				index = -1
				break
			}
			index = index + grid[i][index]
		}
		res = append(res, index)
	}
	return res
}

# 3
func findBall(grid [][]int) []int {
	n, m := len(grid), len(grid[0])
	res := make([]int, m)
	for i := 0; i < m; i++ {
		res[i] = i
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if res[j] == -1 {
				continue
			}
			if (grid[i][res[j]] == 1 && (res[j] == m-1 || grid[i][res[j]+1] == -1)) ||
				(grid[i][res[j]] == -1 && (res[j] == 0 || grid[i][res[j]-1] == 1)) {
				res[j] = -1
				continue
			}
			res[j] = res[j] + grid[i][res[j]]
		}
	}
	return res
}

1711.大餐计数(1)¶

题目

大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i道餐品的美味程度，
返回你可以用数组中的餐品做出的不同大餐的数量。
结果需要对 109 + 7 取余。
注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
示例 1：输入：deliciousness = [1,3,5,7,9] 输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
示例 2：输入：deliciousness = [1,1,1,3,3,3,7] 输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。
提示：1 <= deliciousness.length <= 105
0 <= deliciousness[i] <= 220

解题思路

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

func countPairs(deliciousness []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(deliciousness); i++ {
		total := 1
		for j := 0; j <= 21; j++ {
			if m[total-deliciousness[i]] > 0 {
				res = res + m[total-deliciousness[i]]
			}
			total = total * 2
		}
		m[deliciousness[i]]++
	}
	return res % 1000000007
}

1712.将数组分成三个子数组的方案数(2)¶

题目

我们称一个分割整数数组的方案是 好的，当它满足：
数组被分成三个 非空连续子数组，从左至右分别命名为left，mid，right。
left中元素和小于等于mid中元素和，mid中元素和小于等于right中元素和。
给你一个 非负 整数数组nums，请你返回好的 分割 nums方案数目。
由于答案可能会很大，请你将结果对 109+ 7取余后返回。
示例 1：输入：nums = [1,1,1] 输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2：输入：nums = [1,2,2,2,5,0] 输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
示例 3：输入：nums = [3,2,1] 输出：0
解释：没有好的分割方案。
提示：3 <= nums.length <= 105
0 <= nums[i] <= 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+双指针	O(n)	O(n)
02	前缀和+二分查找	O(nlog(n))	O(n)

func waysToSplit(nums []int) int {
	res := 0
	n := len(nums)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + nums[i]
	}
	left, right := 2, 2
	for i := 1; i <= n-1; i++ {
		first := arr[i] // 第1个数
		left = max(left, i+1)
		right = max(right, i+1)
		for left <= n-1 && arr[left]-first < first { // 找到第一个满足的中间数组左边坐标
			left++
		}
		for right <= n-1 && arr[right]-first <= arr[n]-arr[right] {
			right++
		}
		if left <= right {
			res = (res + right - left) % 1000000007
		}
	}
	return res % 1000000007
}

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

# 2
func waysToSplit(nums []int) int {
	res := 0
	n := len(nums)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + nums[i]
	}
	for i := 1; i <= n-1; i++ {
		first := arr[i] // 第1个数
		if first*3 > arr[n] {
			break
		}
		left, right := i+1, n-1
		for left <= right {
			mid := left + (right-left)/2
			if arr[n]-arr[mid] < arr[mid]-first {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		b := left
		left, right = i+1, n-1
		for left <= right {
			mid := left + (right-left)/2
			if arr[mid]-first < first {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
		a := left
		res = (res + b - a) % 1000000007
	}
	return res % 1000000007
}

1717.删除子字符串的最大得分(2)¶

题目

给你一个字符串s和两个整数x 和y。你可以执行下面两种操作任意次。
删除子字符串"ab"并得到x分。
比方说，从"cabxbae"删除 ab，得到"cxbae"。
删除子字符串"ba"并得到y分。
比方说，从"cabxbae"删除 ba，得到"cabxe"。
请返回对 s字符串执行上面操作若干次能得到的最大得分。
示例 1：输入：s = "cdbcbbaaabab", x = 4, y = 5 输出：19
解释：- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。
示例 2：输入：s = "aabbaaxybbaabb", x = 5, y = 4 输出：20
提示：1 <= s.length <= 105
1 <= x, y <= 104
s只包含小写英文字母。

解题思路

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

func maximumGain(s string, x int, y int) int {
	if x > y {
		x, y = y, x
		s = reverse(s)
	}
	res := 0
	stack := make([]byte, 0)
	// 先处理ba,y分多
	for i := 0; i < len(s); i++ {
		if s[i] != 'a' {
			stack = append(stack, s[i])
		} else {
			if len(stack) > 0 && stack[len(stack)-1] == 'b' {
				stack = stack[:len(stack)-1]
				res = res + y
			} else {
				stack = append(stack, s[i])
			}
		}
	}
	// 处理ab
	temp := make([]byte, 0)
	for len(stack) > 0 {
		c := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if c != 'a' {
			temp = append(temp, c)
		} else {
			if len(temp) > 0 && temp[len(temp)-1] == 'b' {
				temp = temp[:len(temp)-1]
				res = res + x
			} else {
				temp = append(temp, c)
			}
		}
	}
	return res
}

func reverse(s string) string {
	arr := []byte(s)
	for i := 0; i < len(s)/2; i++ {
		arr[i], arr[len(s)-1-i] = arr[len(s)-1-i], arr[i]
	}
	return string(arr)
}

# 2
func maximumGain(s string, x int, y int) int {
	if x > y {
		x, y = y, x
		s = reverse(s)
	}
	res := 0
	a, b := 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'a' || s[i] == 'b' {
			if s[i] == 'a' {
				a++
			} else {
				b++
			}
			// 处理ba
			if s[i] == 'a' && b > 0 {
				a--
				b--
				res = res + y
			}
		} else {
			res = res + x*min(a, b) // 处理ab
			a, b = 0, 0
		}
	}
	res = res + x*min(a, b) // 处理ab
	return res
}

func reverse(s string) string {
	arr := []byte(s)
	for i := 0; i < len(s)/2; i++ {
		arr[i], arr[len(s)-1-i] = arr[len(s)-1-i], arr[i]
	}
	return string(arr)
}

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

1718.构建字典序最大的可行序列(1)¶

题目

给你一个整数n，请你找到满足下面条件的一个序列：
整数1在序列中只出现一次。
2到n之间每个整数都恰好出现两次。
对于每个2到n之间的整数i，两个i之间出现的距离恰好为i。
序列里面两个数 a[i]和 a[j]之间的 距离，我们定义为它们下标绝对值之差|j - i|。
请你返回满足上述条件中字典序最大的序列。题目保证在给定限制条件下，一定存在解。
一个序列a被认为比序列b（两者长度相同）字典序更大的条件是：
a 和b中第一个不一样的数字处，a序列的数字比b序列的数字大。
比方说，[0,1,9,0]比[0,1,5,6]字典序更大，因为第一个不同的位置是第三个数字，且9比5大。
示例 1：输入：n = 3 输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。
示例 2：输入：n = 5 输出：[5,3,1,4,3,5,2,4,2]
提示：1 <= n <= 20

解题思路

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

var res []int

func constructDistancedSequence(n int) []int {
	path := make([]int, 2*n-1)
	res = make([]int, 2*n-1)
	visited := make([]bool, n+1)
	dfs(n, 0, &path, &visited)
	return res
}

func dfs(n int, cur int, path *[]int, visited *[]bool) bool {
	if cur == 2*n-1 {
		copy(res, *path)
		return true
	}
	if (*path)[cur] > 0 {
		return dfs(n, cur+1, path, visited)
	}
	for i := n; i > 0; i-- { // 从大的开始尝试
		next := cur + i
		if (*visited)[i] == true {
			continue
		}
		if i > 1 && (next >= 2*n-1 || (*path)[next] > 0) {
			continue
		}
		a, b := cur, next
		if i == 1 { // 1特判
			a, b = cur, cur
		}
		(*visited)[i] = true
		(*path)[a] = i
		(*path)[b] = i
		if dfs(n, cur+1, path, visited) == true {
			return true
		}
		(*path)[a] = 0
		(*path)[b] = 0
		(*visited)[i] = false
	}
	return false
}

1721.交换链表中的节点(2)¶

题目

给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1：输入：head = [1,2,3,4,5], k = 2 输出：[1,4,3,2,5]
示例 2：输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5 输出：[7,9,6,6,8,7,3,0,9,5]
示例 3：输入：head = [1], k = 1 输出：[1]
示例 4：输入：head = [1,2], k = 1 输出：[2,1]
示例 5：输入：head = [1,2,3], k = 2 输出：[1,2,3]
提示：链表中节点的数目是 n
1 <= k <= n <= 105
0 <= Node.val <= 100

解题思路

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

func swapNodes(head *ListNode, k int) *ListNode {
	slow, fast := head, head
	for i := 0; i < k-1; i++ {
		fast = fast.Next
	}
	a := fast
	for fast != nil && fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Val, a.Val = a.Val, slow.Val
	return head
}

# 2
func swapNodes(head *ListNode, k int) *ListNode {
	res := make([]*ListNode, 0)
	cur := head
	for cur != nil {
		res = append(res, cur)
		cur = cur.Next
	}
	res[k-1].Val, res[len(res)-k].Val = res[len(res)-k].Val, res[k-1].Val
	return head
}

1722.执行交换操作后的最小汉明距离(1)¶

题目

给你两个整数数组 source 和 target ，长度都是 n 。
还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 
表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。
注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组source 和 target 间的 汉明距离 是元素不同的下标数量。
形式上，其值等于满足source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。
在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
示例 1：输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]] 输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
示例 2：输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [] 输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：输入：source = [5,1,2,4,3], target = [1,5,4,2,3], 
allowedSwaps = [[0,4],[4,2],[1,3],[1,4]] 输出：0
提示：n == source.length == target.length
1 <= n <= 105
1 <= source[i], target[i] <= 105
0 <= allowedSwaps.length <= 105
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

解题思路

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

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int {
	n := len(source)
	fa = Init(n)
	for i := 0; i < len(allowedSwaps); i++ {
		a, b := allowedSwaps[i][0], allowedSwaps[i][1]
		union(a, b)
	}
	m := make(map[int]map[int]int)
	res := 0
	for i := 0; i < len(source); i++ {
		v := find(i)
		if m[v] == nil {
			m[v] = make(map[int]int)
		}
		m[v][source[i]]++
	}
	for i := 0; i < len(target); i++ {
		v := find(i)
		if m[v][target[i]] == 0 {
			res++
		} else {
			m[v][target[i]]--
		}
	}
	return res
}

var fa []int

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

// 查询
func find(x int) int {
	if fa[x] != x {
		fa[x] = find(fa[x])
	}
	return fa[x]
}

// 合并
func union(i, j int) {
	fa[find(i)] = find(j)
}

1726.同积元组(1)¶

题目

给你一个由 不同 正整数组成的数组 nums ，请你返回满足a * b = c * d 的元组 (a, b, c, d) 的数量。
其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。
示例 1：输入：nums = [2,3,4,6] 输出：8
解释：存在 8 个满足题意的元组：
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (3,4,2,6) , (3,4,6,2) , (4,3,6,2)
示例 2：输入：nums = [1,2,4,5,10] 输出：16
解释：存在 16 个满足题意的元组：
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
示例 3：输入：nums = [2,3,4,6,8,12] 输出：40
示例 4：输入：nums = [2,3,5,7] 输出：0
提示：1 <= nums.length <= 1000
1 <= nums[i] <= 104
nums 中的所有元素 互不相同

解题思路

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

func tupleSameProduct(nums []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			total := nums[i] * nums[j]
			m[total]++
		}
	}
	for _, v := range m {
		if v >= 2 {
			res = res + v*(v-1)/2*8
		}
	}
	return res
}

1727.重新排列后的最大子矩阵(1)¶

题目

给你一个二进制矩阵matrix，它的大小为m x n，你可以将 matrix中的 列按任意顺序重新排列。
请你返回最优方案下将 matrix重新排列后，全是 1的子矩阵面积。
示例 1：输入：matrix = [[0,0,1],[1,1,1],[1,0,1]] 输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。
示例 2：输入：matrix = [[1,0,1,0,1]] 输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。
示例 3：输入：matrix = [[1,1,0],[1,0,1]] 输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。
示例 4：输入：matrix = [[0,0],[0,0]] 输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
提示：m == matrix.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j]要么是0，要么是1 。

解题思路

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

func largestSubmatrix(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	for i := 1; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] == 1 { // 统计以该行为基连续1的个数
				matrix[i][j] = matrix[i][j] + matrix[i-1][j]
			}
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		sort.Ints(matrix[i])
		for j := m - 1; j >= 0; j-- {
			height := matrix[i][j] // 高度有序，右边最高=>高度取决于左边
			width := m - j
			if height*width > res {
				res = height * width
			}
		}
	}
	return res
}

1733.需要教语言的最少人数(1)¶

题目

在一个由m个用户组成的社交网络里，我们获取到一些用户之间的好友关系。
两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数n，数组languages和数组friendships，它们的含义如下：
总共有n种语言，编号从1 到n。
languages[i]是第 i位用户掌握的语言集合。
friendships[i] = [ui, vi]表示ui和vi为好友关系。
你可以选择 一门语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少需要教会多少名用户。
请注意，好友关系没有传递性，也就是说如果x 和y是好友，且y和z是好友，x 和z不一定是好友。
示例 1：输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]] 输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
示例 2：
输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
提示：2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= ui < vi <= languages.length
1 <= friendships.length <= 500
所有的好友关系(ui, vi)都是唯一的。
languages[i]中包含的值互不相同。

解题思路

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

func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
	m := make(map[int]map[int]int)
	for i := 0; i < len(languages); i++ {
		a := i + 1
		m[a] = make(map[int]int)
		for j := 0; j < len(languages[i]); j++ {
			b := languages[i][j]
			m[a][b] = 1
		}
	}
	need := make(map[int]bool) // 需要沟通的人列表
	for i := 0; i < len(friendships); i++ {
		a, b := friendships[i][0], friendships[i][1]
		flag := false
		for j := 1; j <= n; j++ {
			if m[a][j] == 1 && m[b][j] == 1 {
				flag = true
				break
			}
		}
		if flag == false {
			need[a] = true
			need[b] = true
		}
	}
	res := 0
	for i := 1; i <= n; i++ {
		count := 0
		for k := range need {
			if m[k][i] == 1 {
				count++
			}
		}
		if count > res {
			res = count
		}
	}
	return len(need) - res
}

1734.解码异或后的排列(2)¶

题目

给你一个整数数组perm，它是前n个正整数的排列，且n是个 奇数。
它被加密成另一个长度为 n - 1的整数数组encoded，满足encoded[i] = perm[i] XOR perm[i + 1]。
比方说，如果perm = [1,3,2]，那么encoded = [2,1]。
给你encoded数组，请你返回原始数组perm。题目保证答案存在且唯一。
示例 1：输入：encoded = [3,1] 输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2：输入：encoded = [6,5,4,6] 输出：[2,4,1,5,3]
提示：3 <= n <105
n是奇数。
encoded.length == n - 1

解题思路

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

func decode(encoded []int) []int {
	n := len(encoded)
	temp := make([]int, n)
	copy(temp, encoded)
	first := encoded[0]
	for i := 1; i < n; i++ {
		temp[i] = encoded[i] ^ temp[i-1]
		first = first ^ temp[i]
	}
	for i := 1; i <= n+1; i++ {
		first = first ^ i
	}

	res := make([]int, n+1)
	res[0] = first
	for i := 0; i < n; i++ {
		res[i+1] = encoded[i] ^ res[i]
	}
	return res
}

# 2
func decode(encoded []int) []int {
	n := len(encoded)
	first := 0
	for i := 1; i <= n+1; i++ {
		first = first ^ i
	}
	for i := 1; i <= n; i = i + 2 {
		first = first ^ encoded[i]
	}
	res := make([]int, n+1)
	res[0] = first
	for i := 0; i < n; i++ {
		res[i+1] = encoded[i] ^ res[i]
	}
	return res
}

1737.满足三条件之一需改变的最少字符数(1)¶

题目

给你两个字符串 a 和 b ，二者均由小写字母组成。
一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。
操作的最终目标是满足下列三个条件 之一 ：
a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
a 和 b 都 由 同一个 字母组成。
返回达成目标所需的 最少 操作数。
示例 1：输入：a = "aba", b = "caa" 输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。
示例 2：输入：a = "dabadd", b = "cda" 输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。
提示：1 <= a.length, b.length <= 105
a 和 b 只由小写字母组成

解题思路

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

func minCharacters(a string, b string) int {
	arrA, arrB := [26]int{}, [26]int{}
	for i := 0; i < len(a); i++ {
		arrA[a[i]-'a']++
	}
	for i := 0; i < len(b); i++ {
		arrB[b[i]-'a']++
	}
	res := math.MaxInt32
	lengthA, lengthB := len(a), len(b)
	sumA, sumB := 0, 0
	// a-y的情况
	for i := 0; i < 25; i++ {
		sumA = sumA + arrA[i]
		sumB = sumB + arrB[i]
		res = min(res, lengthA-sumA+sumB)               // 条件1：a<b
		res = min(res, sumA+lengthB-sumB)               // 条件2: b<a
		res = min(res, lengthA-arrA[i]+lengthB-arrB[i]) // 条件3：全都相同
	}
	res = min(res, lengthA-arrA[25]+lengthB-arrB[25]) // z全都相同
	return res
}

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

1738.找出第K大的异或坐标值(2)¶

题目

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 
matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：输入：matrix = [[5,2],[1,6]], k = 1 输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
示例 2：输入：matrix = [[5,2],[1,6]], k = 2 输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
示例 3：输入：matrix = [[5,2],[1,6]], k = 3 输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
示例 4：输入：matrix = [[5,2],[1,6]], k = 4 输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
提示：m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 106
1 <= k <= m * n

解题思路

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

func kthLargestValue(matrix [][]int, k int) int {
	m := len(matrix)
	n := len(matrix[0])
	arr := make([]int, 0)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j > 0 {
				matrix[i][j] = matrix[i][j-1] ^ matrix[i][j]
			} else if i > 0 && j == 0 {
				matrix[i][j] = matrix[i-1][j] ^ matrix[i][j]
			} else if i > 0 && j > 0 {
				matrix[i][j] = matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i][j] ^ matrix[i-1][j-1]
			}
			arr = append(arr, matrix[i][j])
		}
	}
	sort.Ints(arr)
	return arr[len(arr)-k]
}

# 2
func kthLargestValue(matrix [][]int, k int) int {
	m := len(matrix)
	n := len(matrix[0])
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j > 0 {
				matrix[i][j] = matrix[i][j-1] ^ matrix[i][j]
			} else if i > 0 && j == 0 {
				matrix[i][j] = matrix[i-1][j] ^ matrix[i][j]
			} else if i > 0 && j > 0 {
				matrix[i][j] = matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i][j] ^ matrix[i-1][j-1]
			}
			heap.Push(&intHeap, matrix[i][j])
			if intHeap.Len() > k {
				heap.Pop(&intHeap)
			}
		}
	}
	return intHeap[0]
}

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
}

1743.从相邻元素对还原数组(2)¶

题目

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。
好在你还记得 nums 中的每一对相邻元素。
给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，
其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，
存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。
这些相邻元素对可以 按任意顺序 出现。
返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
示例 1：输入：adjacentPairs = [[2,1],[3,4],[3,2]] 输出：[1,2,3,4]
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。
示例 2：输入：adjacentPairs = [[4,-2],[1,4],[-3,1]] 输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
示例 3：输入：adjacentPairs = [[100000,-100000]] 输出：[100000,-100000]
提示：nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
题目数据保证存在一些以adjacentPairs 作为元素对的数组 nums

解题思路

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

var res []int
var m map[int][]int

func restoreArray(adjacentPairs [][]int) []int {
	m = make(map[int][]int)
	for i := 0; i < len(adjacentPairs); i++ {
		a, b := adjacentPairs[i][0], adjacentPairs[i][1]
		m[a] = append(m[a], b)
		m[b] = append(m[b], a)
	}
	arr := make([]int, 0)
	for k, v := range m {
		if len(v) == 1 {
			arr = append(arr, k)
		}
	}
	res = make([]int, 0)
	dfs(arr[0], make(map[int]bool))
	return res
}

func dfs(cur int, visited map[int]bool) {
	res = append(res, cur)
	visited[cur] = true
	for i := range m[cur] {
		if visited[m[cur][i]] == false {
			dfs(m[cur][i], visited)
		}
	}
}

# 2
func restoreArray(adjacentPairs [][]int) []int {
	m := make(map[int][]int)
	for i := 0; i < len(adjacentPairs); i++ {
		a, b := adjacentPairs[i][0], adjacentPairs[i][1]
		m[a] = append(m[a], b)
		m[b] = append(m[b], a)
	}
	prev := 0
	cur := 0
	for k, v := range m {
		if len(v) == 1 {
			prev = k
			cur = v[0]
			break
		}
	}
	res := make([]int, 0)
	res = append(res, prev)
	n := len(adjacentPairs) + 1
	for n > len(res) {
		res = append(res, cur)
		for i := 0; i < len(m[cur]); i++ {
			if m[cur][i] != prev {
				prev = cur
				cur = m[cur][i]
				break
			}
		}
	}
	return res
}

1744.你能在你最喜欢的那天吃到你最喜欢的糖果吗？(1)¶

题目

给你一个下标从 0 开始的正整数数组candiesCount，
其中candiesCount[i]表示你拥有的第i类糖果的数目。
同时给你一个二维数组queries，其中queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]。
你按照如下规则进行一场游戏：
你从第0天开始吃糖果。
你在吃完 所有第 i - 1类糖果之前，不能吃任何一颗第 i类糖果。
在吃完所有糖果之前，你必须每天 至少吃 一颗糖果。
请你构建一个布尔型数组answer，满足answer.length == queries.length 。
answer[i]为true的条件是：在每天吃 不超过 dailyCapi颗糖果的前提下，
你可以在第favoriteDayi天吃到第favoriteTypei类糖果；否则 answer[i]为 false。
注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。
请你返回得到的数组answer。
示例 1：输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），
你也没办法在第 2 天吃到类型 4 的糖果。
换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。
示例 2：输入：candiesCount = [5,2,6,4,1], 
queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]
提示：1 <= candiesCount.length <= 105
1 <= candiesCount[i] <= 105
1 <= queries.length <= 105
queries[i].length == 3
0 <= favoriteTypei < candiesCount.length
0 <= favoriteDayi <= 109
1 <= dailyCapi <= 109

解题思路

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

func canEat(candiesCount []int, queries [][]int) []bool {
	arr := make([]int, len(candiesCount)+1)
	for i := 1; i <= len(candiesCount); i++ {
		arr[i] = arr[i-1] + candiesCount[i-1]
	}
	res := make([]bool, len(queries))
	for i := 0; i < len(queries); i++ {
		a := queries[i][0] // 第几类
		b := queries[i][1] // 第几天，到第n天共n+1天
		c := queries[i][2] // 每天最多吃c颗
		total := arr[a+1]
		if total <= b { // 最少一天一颗
			continue
		}
		if c*(b+1) <= arr[a] { // 最多每天吃c颗
			continue
		}
		res[i] = true
	}
	return res
}

1749.任意子数组和的绝对值的最大值(3)¶

题目

给你一个整数数组nums。一个子数组[numsl, numsl+1, ..., numsr-1, numsr]
的 和的绝对值为abs(numsl + numsl+1 + ... + numsr-1 + numsr)。
请你找出 nums中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值。
abs(x)定义如下：
如果x是负整数，那么abs(x) = -x。
如果x是非负整数，那么abs(x) = x。
示例 1：输入：nums = [1,-3,2,3,-4] 输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
示例 2：输入：nums = [2,-5,1,-4,3,-2] 输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。
提示：1 <= nums.length <= 105
-104 <= nums[i] <= 104

解题思路

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

func maxAbsoluteSum(nums []int) int {
	arr := make([]int, len(nums)+1)
	for i := 1; i <= len(nums); i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	sort.Ints(arr)
	return arr[len(nums)] - arr[0]
}

# 2
func maxAbsoluteSum(nums []int) int {
	arr := make([]int, len(nums)+1)
	for i := 1; i <= len(nums); i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	maxValue, minValue := 0, 0
	res := 0
	for i := 1; i < len(arr); i++ {
		res = max(res, abs(arr[i]-maxValue))
		res = max(res, abs(arr[i]-minValue))
		maxValue = max(maxValue, arr[i])
		minValue = min(minValue, arr[i])
	}
	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
}

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

# 3
func maxAbsoluteSum(nums []int) int {
	maxValue, minValue := 0, 0
	res := 0
	for i := 0; i < len(nums); i++ {
		if maxValue >= 0 {
			maxValue = maxValue + nums[i]
		} else {
			maxValue = nums[i]
		}
		if minValue <= 0 {
			minValue = minValue + nums[i]
		} else {
			minValue = nums[i]
		}
		res = max(res, abs(maxValue))
		res = max(res, abs(minValue))
	}
	return res
}

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

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

1750.删除字符串两端相同字符后的最短长度(2)¶

题目

给你一个只包含字符 'a'，'b'和 'c'的字符串s，你可以执行下面这个操作（5 个步骤）任意次：
选择字符串 s一个 非空 的前缀，这个前缀的所有字符都相同。
选择字符串 s一个 非空 的后缀，这个后缀的所有字符都相同。
前缀和后缀在字符串中任意位置都不能有交集。
前缀和后缀包含的所有字符都要相同。
同时删除前缀和后缀。
请你返回对字符串 s执行上面操作任意次以后（可能 0 次），能得到的 最短长度。
示例 1：输入：s = "ca" 输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。
示例 2：输入：s = "cabaabac" 输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。
示例 3：输入：s = "aabccabba" 输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，得到 s = "cca" 。
提示：1 <= s.length <= 105
s只包含字符'a'，'b'和'c'。

解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(n)	O(n)
02	双指针	O(n)	O(1)

func minimumLength(s string) int {
	for len(s) > 0 {
		if s[0] == s[len(s)-1] && len(s) != 1 {
			temp := string(s[0])
			s = strings.TrimLeft(s, temp)
			s = strings.TrimRight(s, temp)
		} else {
			break
		}
	}
	return len(s)
}

# 2
func minimumLength(s string) int {
	left, right := 0, len(s)-1
	for left < right {
		if s[left] != s[right] {
			break
		}
		temp := s[left]
		for left <= right && s[left] == temp {
			left++
		}
		for left <= right && s[right] == temp {
			right--
		}
	}
	return right - left + 1
}

1753.移除石子的最大得分(2)¶

题目

你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c的 三堆 石子。
每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。当存在 两个或更多 的空堆时，游戏停止。
给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
示例 1：输入：a = 2, b = 4, c = 6 输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
- 从第一和第三堆取，石子状态现在是 (1, 4, 5)
- 从第一和第三堆取，石子状态现在是 (0, 4, 4)
- 从第二和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：6 分 。
示例 2：输入：a = 4, b = 4, c = 6 输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：
- 从第一和第二堆取，石子状态现在是 (3, 3, 6)
- 从第一和第三堆取，石子状态现在是 (2, 3, 5)
- 从第一和第三堆取，石子状态现在是 (1, 3, 4)
- 从第一和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：7 分 。
示例 3：输入：a = 1, b = 8, c = 8 输出：8
解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。
注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。
提示：1 <= a, b, c <= 105

解题思路

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

func maximumScore(a int, b int, c int) int {
	res := 0
	arr := []int{a, b, c}
	for {
		sort.Ints(arr)
		if arr[2] > 0 && arr[1] > 0 {
			arr[2]--
			arr[1]--
			res++
		} else {
			break
		}
	}
	return res
}

# 2
func maximumScore(a int, b int, c int) int {
	arr := []int{a, b, c}
	sort.Ints(arr)
	if arr[0]+arr[1] <= arr[2] {
		return arr[0] + arr[1]
	}
	return (arr[0] + arr[1] + arr[2]) / 2
}

1754.构造字典序最大的合并字符串(1)¶

题目

给你两个字符串 word1 和 word2 。
你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作：
如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
例如，word1 = "abc" 且 merge = "dv" ，在执行此选项操作之后，word1 = "bc" ，同时 merge = "dva" 。
如果 word2 非空，将 word2 中的第一个字符附加到 merge 的末尾，并将其从 word2 中移除。
例如，word2 = "abc" 且 merge = "" ，在执行此选项操作之后，word2 = "bc" ，同时 merge = "a" 。
返回你可以构造的字典序 最大 的合并字符串 merge 。
长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，
a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字符串 b 更大。
例如，"abcd" 按字典序比 "abcc" 更大，因为两个字符串出现不同的第一个位置是第四个字符，
而 d 在字母表中的出现顺序位于 c 之后。
示例 1：输入：word1 = "cabaa", word2 = "bcaaa" 输出："cbcabaaaaa"
解释：构造字典序最大的合并字符串，可行的一种方法如下所示：
- 从 word1 中取第一个字符：merge = "c"，word1 = "abaa"，word2 = "bcaaa"
- 从 word2 中取第一个字符：merge = "cb"，word1 = "abaa"，word2 = "caaa"
- 从 word2 中取第一个字符：merge = "cbc"，word1 = "abaa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbca"，word1 = "baa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbcab"，word1 = "aa"，word2 = "aaa"
- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。
示例 2：输入：word1 = "abcabc", word2 = "abdcaba" 输出："abdcabcabcaba"
提示：1 <= word1.length, word2.length <= 3000
word1 和 word2 仅由小写英文组成

解题思路

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

func largestMerge(word1 string, word2 string) string {
	res := make([]byte, len(word1)+len(word2))
	for i := 0; i < len(res); i++ {
		if word1 < word2 {
			res[i], word2 = word2[0], word2[1:]
		} else {
			res[i], word1 = word1[0], word1[1:]
		}
	}
	return string(res)
}

1759.统计同构子字符串的数目(3)¶

题目

给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "abbcccaa" 输出：13
解释：同构子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
示例 2：输入：s = "xy" 输出：2
解释：同构子字符串是 "x" 和 "y" 。
示例 3：输入：s = "zzzzz" 输出：15
提示：1 <= s.length <= 105
s 由小写字符串组成

解题思路

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

func countHomogenous(s string) int {
	res := 0
	left, right := 0, 0
	for right < len(s) {
		if s[left] == s[right] {
			right++
		} else {
			length := right - left
			res = res + length*(length+1)/2
			left = right
			right++
		}
	}
	length := right - left
	res = res + length*(length+1)/2
	return res % 1000000007
}

# 2
func countHomogenous(s string) int {
	res := 0
	left, right := 0, 0
	for right < len(s) {
		if s[left] != s[right] {
			left = right
		} else {
			res = res + (right-left+1)%1000000007
			right++
		}
	}
	return res % 1000000007
}

# 3
func countHomogenous(s string) int {
	res := 1
	count := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			count = 1
		}
		res = res + count
	}
	return res % 1000000007
}

1760.袋子里最少数目的球(3)¶

题目

给你一个整数数组nums，其中nums[i]表示第i个袋子里球的数目。同时给你一个整数maxOperations。
你可以进行如下操作至多maxOperations次：
选择任意一个袋子，并将袋子里的球分到2 个新的袋子中，每个袋子里都有 正整数个球。
比方说，一个袋子里有5个球，你可以把它们分到两个新袋子里，
分别有 1个和 4个球，或者分别有 2个和 3个球。
你的开销是单个袋子里球数目的 最大值，你想要 最小化开销。
请你返回进行上述操作后的最小开销。
示例 1：输入：nums = [9], maxOperations = 2 输出：3
解释：- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。
示例 2：输入：nums = [2,4,8,2], maxOperations = 4 输出：2
解释：- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。
示例 3：输入：nums = [7,17], maxOperations = 2 输出：7
提示：1 <= nums.length <= 105
1 <= maxOperations, nums[i] <= 109

解题思路

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

func minimumSize(nums []int, maxOperations int) int {
	sort.Ints(nums)
	left := 1
	right := nums[len(nums)-1]
	res := 0
	for left <= right {
		mid := (left + right) / 2
		count := getCount(nums, mid)
		if count <= maxOperations {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

func getCount(nums []int, per int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		if nums[i]%per == 0 {
			count = count + nums[i]/per - 1
		} else {
			count = count + nums[i]/per
		}
	}
	return count
}

# 2
func minimumSize(nums []int, maxOperations int) int {
	sort.Ints(nums)
	left := 1
	right := nums[len(nums)-1]
	res := 0
	for left <= right {
		mid := (left + right) / 2
		count := getCount(nums, mid)
		if count <= maxOperations {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

func getCount(nums []int, per int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		count = count + (nums[i]-1)/per
	}
	return count
}

# 3
func minimumSize(nums []int, maxOperations int) int {
	left := 1
	right := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] > right {
			right = nums[i]
		}
	}
	res := 0
	for left <= right {
		mid := (left + right) / 2
		count := getCount(nums, mid)
		if count <= maxOperations {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

func getCount(nums []int, per int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		count = count + (nums[i]-1)/per
	}
	return count
}

1764.通过连接另一个数组的子数组得到一个数组(1)¶

题目

给你一个长度为 n的二维整数数组groups，同时给你一个整数数组nums。
你是否可以从 nums中选出 n个 不相交 的子数组，
使得第 i个子数组与 groups[i]（下标从 0开始）完全相同，且如果i > 0，
那么第(i-1)个子数组在 nums中出现的位置在第 i个子数组前面。
（也就是说，这些子数组在 nums中出现的顺序需要与 groups 顺序相同）
如果你可以找出这样的 n 个子数组，请你返回true ，否则返回false。
如果不存在下标为 k的元素 nums[k]属于不止一个子数组，就称这些子数组是 不相交 的。
子数组指的是原数组中连续元素组成的一个序列。
示例 1：输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0] 输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0]
和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。
示例 2：输入：groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2] 输出：false
解释：选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的，
因为它们出现的顺序与 groups 中顺序不同。
[10,-2] 必须出现在 [1,2,3,4] 之前。
示例 3：输入：groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7] 输出：false
解释：选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确的，因为它们不是不相交子数组。
它们有一个共同的元素 nums[4] （下标从 0 开始）。
提示：groups.length == n
1 <= n <= 103
1 <= groups[i].length, sum(groups[i].length) <= 103
1 <= nums.length <= 103

解题思路

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

func canChoose(groups [][]int, nums []int) bool {
	count := 0
	for i := 0; i < len(groups); i++ {
		arr := groups[i]
		flag := false
		for count+len(arr) <= len(nums) {
			if judge(arr, nums[count:count+len(arr)]) == true {
				count = count + len(arr)
				flag = true
				break
			} else {
				count = count + 1
			}
		}
		if flag == false {
			return false
		}
	}
	return true
}

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

1765.地图中的最高点(1)¶

题目

给你一个大小为m x n的整数矩阵isWater，它代表了一个由 陆地和 水域单元格组成的地图。
如果isWater[i][j] == 0，格子(i, j)是一个 陆地格子。
如果isWater[i][j] == 1，格子(i, j)是一个 水域格子。
你需要按照如下规则给每个单元格安排高度：
每个格子的高度都必须是非负的。
如果一个格子是是 水域，那么它的高度必须为 0。
任意相邻的格子高度差 至多为 1。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。
（也就是说它们有一条公共边）
找到一种安排高度的方案，使得矩阵中的最高高度值最大。
请你返回一个大小为m x n的整数矩阵 height，其中 height[i][j]是格子 (i, j)的高度。
如果有多种解法，请返回任意一个。
示例 1：输入：isWater = [[0,1],[0,0]] 输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。
示例 2：输入：isWater = [[0,0,1],[1,0,0],[0,0,0]] 输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。
提示：m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j]要么是0，要么是1。
至少有 1个水域格子。

解题思路

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

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

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

1769.移动所有球到每个盒子所需的最小操作数(3)¶

题目

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，
其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。
在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。
第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。
注意，操作执行后，某些盒子中可能会存在不止一个小球。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。
每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
示例 1：输入：boxes = "110" 输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。
示例 2：输入：boxes = "001011" 输出：[11,8,5,4,3,4]
提示：n == boxes.length
1 <= n <= 2000
boxes[i] 为 '0' 或 '1'

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(n)
02	前缀和+后缀和	O(n)	O(n)
03	暴力法	O(n^2)	O(n)

func minOperations(boxes string) []int {
	n := len(boxes)
	res := make([]int, n)
	right, rightCount := 0, 0
	for i := 0; i < n; i++ {
		if boxes[i] == '1' {
			right = right + i
			rightCount++
		}
	}
	left, leftCount := 0, 0
	for i := 0; i < n; i++ {
		res[i] = left + right
		if boxes[i] == '1' {
			leftCount++
			rightCount--
		}
		left = left + leftCount
		right = right - rightCount
	}
	return res
}

# 2
func minOperations(boxes string) []int {
	n := len(boxes)
	res := make([]int, n)
	pre := make([]int, n)
	count, sum := 0, 0
	for i := 0; i < n; i++ {
		pre[i] = sum
		if boxes[i] == '1' {
			count++
		}
		sum = sum + count
	}
	suf := make([]int, n)
	count, sum = 0, 0
	for i := n - 1; i >= 0; i-- {
		suf[i] = sum
		if boxes[i] == '1' {
			count++
		}
		sum = sum + count
	}
	for i := 0; i < n; i++ {
		res[i] = pre[i] + suf[i]
	}
	return res
}

# 3
func minOperations(boxes string) []int {
	n := len(boxes)
	res := make([]int, n)
	arr := make([]int, 0)
	for i := 0; i < n; i++ {
		if boxes[i] == '1' {
			arr = append(arr, i)
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < len(arr); j++ {
			res[i] = res[i] + abs(arr[j]-i)
		}
	}
	return res
}

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

1770.执行乘法运算的最大分数(3)¶

题目

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。
初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：
选择数组 nums 开头处或者末尾处 的整数 x 。
你获得 multipliers[i] * x 分，并累加到你的分数中。
将 x 从数组 nums 中移除。
在执行 m 步操作后，返回 最大 分数。
示例 1：输入：nums = [1,2,3], multipliers = [3,2,1] 输出：14
解释：一种最优解决方案如下：
- 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
- 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
- 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。
总分数为 9 + 4 + 1 = 14 。
示例 2：输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6] 输出：102
解释：一种最优解决方案如下：
- 选择开头处的整数 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。
- 选择末尾处的整数 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。
- 选择末尾处的整数 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。
提示：n == nums.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000

解题思路

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

func maximumScore(nums []int, multipliers []int) int {
	n, m := len(nums), len(multipliers)
	dp := make([][]int, m+1) // dp[i][j] 左i右j的值
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, m+1)
	}
	dp[0][0] = 0
	for i := 1; i <= m; i++ {
		dp[i][0] = dp[i-1][0] + nums[i-1]*multipliers[i-1] // 左i右0
		dp[0][i] = dp[0][i-1] + nums[n-i]*multipliers[i-1] // 左0右i
	}
	for i := 1; i <= m; i++ {
		for j := 1; i+j <= m; j++ {
			left := dp[i-1][j] + nums[i-1]*multipliers[i+j-1]
			right := dp[i][j-1] + nums[n-j]*multipliers[i+j-1]
			dp[i][j] = max(left, right)
		}
	}
	res := math.MinInt32
	for i := 0; i <= m; i++ {
		res = max(res, dp[i][m-i])
	}
	return res
}

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

# 2
func maximumScore(nums []int, multipliers []int) int {
	n, m := len(nums), len(multipliers)
	dp := make([][]int, m+1) // dp[i][j] 左i右j的值
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, m+1)
	}
	res := math.MinInt32
	for k := 1; k <= m; k++ {
		for i := 0; i <= k; i++ {
			left := i
			right := k - i
			if i == 0 {
				dp[left][right] = dp[left][right-1] + nums[n-right]*multipliers[k-1]
			} else if i == k {
				dp[left][right] = dp[left-1][right] + nums[left-1]*multipliers[k-1]
			} else {
				l := dp[left][right-1] + nums[n-right]*multipliers[k-1]
				r := dp[left-1][right] + nums[left-1]*multipliers[k-1]
				dp[left][right] = max(l, r)
			}
			if k == m {
				res = max(res, dp[left][right])
			}
		}
	}
	return res
}

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

# 3
var dp [][]int

func maximumScore(nums []int, multipliers []int) int {
	n, m := len(nums), len(multipliers)
	dp = make([][]int, m) // dp[i][j] 左i右j的值
	for i := 0; i < m; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = math.MinInt32
		}
	}
	res := dfs(nums, multipliers, 0, n-1)
	return res
}

func dfs(nums []int, multipliers []int, i, j int) int {
	n, m := len(nums), len(multipliers)
	if dp[i][j-n+m] != math.MinInt32 {
		return dp[i][j-n+m]
	}
	if j-i == n-m {
		dp[i][j-n+m] = max(dp[i][j-n+m], nums[i]*multipliers[m-1])
		dp[i][j-n+m] = max(dp[i][j-n+m], nums[j]*multipliers[m-1])
		return dp[i][j-n+m]
	}
	k := i + n - 1 - j
	left := dfs(nums, multipliers, i+1, j) + nums[i]*multipliers[k]
	right := dfs(nums, multipliers, i, j-1) + nums[j]*multipliers[k]
	dp[i][j-n+m] = max(left, right)
	return dp[i][j-n+m]
}

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

1774.最接近目标价格的甜点成本(2)¶

题目

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。
而制作甜点需要遵循以下几条规则：
必须选择 一种 冰激凌基料。
可以添加 一种或多种 配料，也可以不添加任何配料。
每种类型的配料 最多两份 。
给你以下三个输入：
baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
target ，一个整数，表示你制作甜点的目标价格。
你希望自己做的甜点总成本尽可能接近目标价格 target 。
返回最接近 target 的甜点成本。如果有多种方案，返回成本相对较低 的一种。
示例 1：输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10 输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。
示例 2：输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18 输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。
示例 3：输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9 输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。
示例 4：输入：baseCosts = [10], toppingCosts = [1], target = 1 输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。
提示：n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104

解题思路

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

var res int

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	res = math.MaxInt32
	for i := 0; i < len(baseCosts); i++ {
		dfs(toppingCosts, target, baseCosts[i], 0)
	}
	return res
}

func dfs(toppingCosts []int, target int, sum int, index int) {
	if abs(res-target) > abs(sum-target) {
		res = sum
	} else if abs(res-target) == abs(sum-target) && sum < res {
		res = sum
	}
	if sum > target {
		return
	}
	if index == len(toppingCosts) {
		return
	}
	dfs(toppingCosts, target, sum, index+1)
	dfs(toppingCosts, target, sum+toppingCosts[index], index+1)
	dfs(toppingCosts, target, sum+2*toppingCosts[index], index+1)
}

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

# 2
func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	res := math.MaxInt32
	n, m := len(baseCosts), len(toppingCosts)
	for i := 0; i < n; i++ {
		for j := 0; j < (1 << m); j++ { // 选择第1次
			for k := j; k < (1 << m); k++ { // 选择第2次
				total := baseCosts[i]
				for l := 0; l < m; l++ {
					if j&(1<<l) != 0 {
						total = total + toppingCosts[l]
					}
					if k&(1<<l) != 0 {
						total = total + toppingCosts[l]
					}
				}
				if abs(res-target) > abs(total-target) {
					res = total
				} else if abs(res-target) == abs(total-target) && total < res {
					res = total
				}
			}
		}
	}
	return res
}

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

1775.通过最少操作次数使数组的和相等(2)¶

题目

给你两个长度可能不等的整数数组nums1 和nums2。两个数组中的所有值都在1到6之间（包含1和6）。
每次操作中，你可以选择 任意数组中的任意一个整数，将它变成 1到 6之间 任意的值（包含 1和 6）。
请你返回使 nums1中所有数的和与nums2中所有数的和相等的最少操作次数。
如果无法使两个数组的和相等，请返回 -1。
示例 1：输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2] 输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。
示例 2：输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6] 输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。
示例 3：输入：nums1 = [6,6], nums2 = [1] 输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。
提示：1 <= nums1.length, nums2.length <= 105
1 <= nums1[i], nums2[i] <= 6

解题思路

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

func minOperations(nums1 []int, nums2 []int) int {
	aMin, bMin := len(nums1), len(nums2)
	aMax, bMax := aMin*6, bMin*6
	if aMin > bMax || aMax < bMin {
		return -1
	}
	a, b := 0, 0
	arrA, arrB := [7]int{}, [7]int{}
	for i := 0; i < len(nums1); i++ {
		a = a + nums1[i]
		arrA[nums1[i]]++
	}
	for i := 0; i < len(nums2); i++ {
		b = b + nums2[i]
		arrB[nums2[i]]++
	}
	if a == b {
		return 0
	}
	if b > a {
		arrA, arrB = arrB, arrA
		a, b = b, a
	}
	arr := make([]int, 0) // 存储
	for i := 1; i < 6; i++ {
		if arrA[7-i] > arrB[i] {
			arr = append(arr, arrA[7-i], arrB[i])
		} else {
			arr = append(arr, arrB[i], arrA[7-i])
		}
	}
	res := 0
	total := a - b
	for i := 0; i < len(arr); i++ {
		diff := 6 - (i+2)/2
		if total-diff*arr[i] > 0 {
			total = total - diff*arr[i]
			res = res + arr[i]
		} else {
			if total%diff == 0 {
				res = res + total/diff
			} else {
				res = res + total/diff + 1
			}
			return res
		}
	}
	return res
}

# 2
func minOperations(nums1 []int, nums2 []int) int {
	aMin, bMin := len(nums1), len(nums2)
	aMax, bMax := aMin*6, bMin*6
	if aMin > bMax || aMax < bMin {
		return -1
	}
	a, b := 0, 0
	arrA, arrB := [7]int{}, [7]int{}
	for i := 0; i < len(nums1); i++ {
		a = a + nums1[i]
		arrA[nums1[i]]++
	}
	for i := 0; i < len(nums2); i++ {
		b = b + nums2[i]
		arrB[nums2[i]]++
	}
	if a == b {
		return 0
	}
	if b > a {
		arrA, arrB = arrB, arrA
		a, b = b, a
	}
	arr := make([]int, 6) // 存储
	for i := 1; i < 6; i++ {
		arr[i-1] = arr[i-1] + arrA[7-i] + arrB[i]
	}
	res, total := 0, a-b
	for i := 0; i < len(arr); i++ {
		diff := 5 - i
		if total-diff*arr[i] > 0 {
			total = total - diff*arr[i]
			res = res + arr[i]
		} else {
			if total%diff == 0 {
				res = res + total/diff
			} else {
				res = res + total/diff + 1
			}
			return res
		}
	}
	return res
}

1780.判断一个数字是否可以表示成三的幂的和(2)¶

题目

给你一个整数n，如果你可以将n表示成若干个不同的三的幂之和，请你返回true，否则请返回 false。
对于一个整数 y，如果存在整数 x满足 y == 3x，我们称这个整数 y是三的幂。
示例 1：输入：n = 12 输出：true
解释：12 = 31 + 32
示例 2：输入：n = 91 输出：true
解释：91 = 30 + 32 + 34
示例 3：输入：n = 21 输出：false
提示：1 <= n <= 107

解题思路

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

func checkPowersOfThree(n int) bool {
	arr := make([]int, 0)
	arr = append(arr, 1)
	sum := 1
	for i := 0; i < 15; i++ {
		sum = sum * 3
		arr = append(arr, sum)
	}
	for i := len(arr) - 1; i >= 0; i-- {
		if n > arr[i] {
			n = n - arr[i]
		} else if n == arr[i] {
			return true
		}
	}
	return false
}

# 2
func checkPowersOfThree(n int) bool {
	for n > 0 {
		if n%3 == 2 { // 转换为3进制，n*3^x，其中n为0或者1，不会为2
			return false
		}
		n = n / 3
	}
	return true
}

1781.所有子字符串美丽值之和(1)¶

题目

一个字符串的 美丽值定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
比方说，"abaacc"的美丽值为3 - 1 = 2。
给你一个字符串s，请你返回它所有子字符串的美丽值之和。
示例 1：输入：s = "aabcb" 输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
示例 2：输入：s = "aabcbaa" 输出：17
提示：1 <= s.length <= 500
s只包含小写英文字母。

解题思路

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

func beautySum(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		arr := [26]int{}
		arr[s[i]-'a']++
		for j := i + 2; j <= len(s); j++ {
			arr[s[j-1]-'a']++
			res = res + getCount(arr)
		}
	}
	return res
}

func getCount(arr [26]int) int {
	maxValue, minValue := math.MinInt32, math.MaxInt32
	for i := 0; i < 26; i++ {
		if arr[i] > 0 {
			if arr[i] > maxValue {
				maxValue = arr[i]
			}
			if arr[i] < minValue {
				minValue = arr[i]
			}
		}
	}
	return maxValue - minValue
}

1785.构成特定和需要添加的最少元素(2)¶

题目

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：
abs(nums[i]) <= limit 。
返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，
添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。
注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。
示例 1：输入：nums = [1,-1,1], limit = 3, goal = -4 输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。
示例 2：输入：nums = [1,-10,9,1], limit = 100, goal = 0 输出：1
提示：1 <= nums.length <= 105
1 <= limit <= 106
-limit <= nums[i] <= limit
-109 <= goal <= 109

解题思路

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

func minElements(nums []int, limit int, goal int) int {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	left := abs(goal - sum)
	a := left / limit
	b := left % limit
	if b != 0 {
		a = a + 1
	}
	return a
}

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

# 2
func minElements(nums []int, limit int, goal int) int {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	res := abs(goal - sum)
	return (res - 1 + limit) / limit
}

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

1786.从第一个节点出发到最后一个节点的受限路径数¶

题目¶

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；
另给你一个数组 edges ，其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边，
这条边的权重为 weighti 。
从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列，
满足 z0 = start 、zk = end 且在所有符合 0 <= i <= k-1 的节点 zi 和 zi+1 之间存在一条边。
路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。
受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径，其中 0 <= i <= k-1 。
返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大，请返回对 109 + 7 取余 的结果。
示例 1：输入：n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]] 输出：3
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5
示例 2：输入：n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]] 输出：1
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是：1 --> 3 --> 7 。
提示：1 <= n <= 2 * 104
n - 1 <= edges.length <= 4 * 104
edges[i].length == 3
1 <= ui, vi <= n
ui != vi
1 <= weighti <= 105
任意两个节点之间至多存在一条边
任意两个节点之间至少存在一条路径

解题思路¶

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

1791.找出星型图的中心节点(2)¶

题目

有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。
星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges ，其中edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。
请你找出并返回edges 所表示星型图的中心节点。
示例 1：输入：edges = [[1,2],[2,3],[4,2]] 输出：2
解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。
示例 2：输入：edges = [[1,2],[5,1],[1,3],[1,4]] 输出：1
提示：3 <= n <= 105
edges.length == n - 1
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
题目数据给出的 edges 表示一个有效的星型图

解题思路

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

func findCenter(edges [][]int) int {
	m := make(map[int]int)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		m[a]++
		m[b]++
	}
	for k, v := range m {
		if v == len(edges) {
			return k
		}
	}
	return -1
}

# 2
func findCenter(edges [][]int) int {
	if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
		return edges[0][0]
	}
	return edges[0][1]
}

1792.最大平均通过率(1)¶

题目

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。
给你一个二维数组 classes，其中classes[i] = [passi, totali]，
表示你提前知道了第i个班级总共有totali个学生，其中只有passi个学生可以通过考试。
给你一个整数extraStudents，表示额外有extraStudents个聪明的学生，
他们 一定能通过任何班级的期末考。
你需要给这extraStudents个学生每人都安排一个班级，使得 所有班级的 平均通过率 最大。
一个班级的通过率等于这个班级通过考试的学生人数除以这个班级的总人数。
平均通过率是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大平均通过率。
与标准答案误差范围在10-5以内的结果都会视为正确结果。
示例 1：输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2 输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2：输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4 输出：0.53485
提示：1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105

解题思路

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

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	nodeHeap := make(NodeHeap, 0)
	heap.Init(&nodeHeap)
	for i := 0; i < len(classes); i++ {
		x, y := float64(classes[i][0]), float64(classes[i][1])
		a := x / y
		b := (x + 1) / (y + 1)
		heap.Push(&nodeHeap, Node{
			id:    i,
			ratio: b - a,
		})
	}
	for i := 0; i < extraStudents; i++ {
		node := heap.Pop(&nodeHeap).(Node)
		id := node.id
		classes[id][0]++
		classes[id][1]++
		x, y := float64(classes[id][0]), float64(classes[id][1])
		a := x / y
		b := (x + 1) / (y + 1)
		heap.Push(&nodeHeap, Node{
			id:    id,
			ratio: b - a,
		})
	}
	sum := float64(0)
	for i := 0; i < len(classes); i++ {
		x, y := float64(classes[i][0]), float64(classes[i][1])
		sum = sum + x/y
	}
	return sum / float64(len(classes))
}

type Node struct {
	id    int
	ratio float64
}

type NodeHeap []Node

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

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

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

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

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

1797.设计一个验证系统(2)¶

题目

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，
这个验证码在 currentTime时刻之后 timeToLive秒过期。
如果验证码被更新了，那么它会在 currentTime（可能与之前的 currentTime不同）时刻延长timeToLive秒。
请你实现AuthenticationManager类：
AuthenticationManager(int timeToLive)构造AuthenticationManager并设置timeToLive参数。
generate(string tokenId, int currentTime)给定 tokenId，
在当前时间currentTime 生成一个新的验证码。
renew(string tokenId, int currentTime)将给定 tokenId
且 未过期的验证码在 currentTime时刻更新。
如果给定tokenId对应的验证码不存在或已过期，请你忽略该操作，不会有任何更新操作发生。
countUnexpiredTokens(int currentTime)请返回在给定currentTime时刻，未过期的验证码数目。
如果一个验证码在时刻t过期，且另一个操作恰好在时刻t发生（renew或者countUnexpiredTokens操作），
过期事件优先于其他操作。
示例 1：输入：["AuthenticationManager", "renew", "generate", 
"countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"]
[[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
输出：[null, null, null, 1, null, null, null, 0]
解释：AuthenticationManager authenticationManager = new AuthenticationManager(5); 
// 构造 AuthenticationManager ，设置 timeToLive = 5 秒。
authenticationManager.renew("aaa", 1); 
// 时刻 1 时，没有验证码的 tokenId 为 "aaa" ，没有验证码被更新。
authenticationManager.generate("aaa", 2); 
// 时刻 2 时，生成一个 tokenId 为 "aaa" 的新验证码。
authenticationManager.countUnexpiredTokens(6); 
// 时刻 6 时，只有 tokenId 为 "aaa" 的验证码未过期，所以返回 1 。
authenticationManager.generate("bbb", 7); 
// 时刻 7 时，生成一个 tokenId 为 "bbb" 的新验证码。
authenticationManager.renew("aaa", 8); 
// tokenId 为 "aaa" 的验证码在时刻 7 过期，
且 8 >= 7 ，所以时刻 8 的renew 操作被忽略，没有验证码被更新。
authenticationManager.renew("bbb", 10);
// tokenId 为 "bbb" 的验证码在时刻 10 没有过期，所以 renew 操作会执行，该 token 将在时刻 15 过期。
authenticationManager.countUnexpiredTokens(15);
// tokenId 为 "bbb" 的验证码在时刻 15 过期，
tokenId 为 "aaa" 的验证码在时刻 7 过期，所有验证码均已过期，所以返回 0 。
提示：1 <= timeToLive <= 108
1 <= currentTime <= 108
1 <= tokenId.length <= 5
tokenId只包含小写英文字母。
所有generate函数的调用都会包含独一无二的tokenId值。
所有函数调用中，currentTime的值 严格递增。
所有函数的调用次数总共不超过2000次。

解题思路

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

type AuthenticationManager struct {
	m          map[string]int
	timeToLive int
}

func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{
		m:          make(map[string]int),
		timeToLive: timeToLive,
	}
}

func (this *AuthenticationManager) Generate(tokenId string, currentTime int) {
	this.m[tokenId] = currentTime + this.timeToLive
}

func (this *AuthenticationManager) Renew(tokenId string, currentTime int) {
	if v, ok := this.m[tokenId]; ok {
		if v <= currentTime {
			delete(this.m, tokenId)
		} else {
			this.m[tokenId] = currentTime + this.timeToLive
		}
	}
}

func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	count := 0
	arr := make([]string, 0)
	for k, v := range this.m {
		if v > currentTime {
			count++
		} else {
			arr = append(arr, k)
		}
	}
	for i := 0; i < len(arr); i++ {
		delete(this.m, arr[i])
	}
	return count
}

# 2
type AuthenticationManager struct {
	m          map[string]int
	timeToLive int
}

func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{
		m:          make(map[string]int),
		timeToLive: timeToLive,
	}
}

func (this *AuthenticationManager) Generate(tokenId string, currentTime int) {
	this.m[tokenId] = currentTime + this.timeToLive
}

func (this *AuthenticationManager) Renew(tokenId string, currentTime int) {
	if v, ok := this.m[tokenId]; ok {
		if v <= currentTime {
			delete(this.m, tokenId)
		} else {
			this.m[tokenId] = currentTime + this.timeToLive
		}
	}
}

func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	count := 0
	for _, v := range this.m {
		if v > currentTime {
			count++
		}
	}
	return count
}

1798.你能构造出连续值的最大数目(2)¶

题目

给你一个长度为 n的整数数组coins，它代表你拥有的n个硬币。第i个硬币的值为coins[i]。
如果你从这些硬币中选出一部分硬币，它们的和为x，那么称，你可以构造出x。
请返回从 0开始（包括0），你最多能构造出多少个连续整数。
你可能有多个相同值的硬币。
示例 1：输入：coins = [1,3] 输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 2 个连续整数。
示例 2：输入：coins = [1,1,1,4] 输出：8
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
- 2：取 [1,1]
- 3：取 [1,1,1]
- 4：取 [4]
- 5：取 [4,1]
- 6：取 [4,1,1]
- 7：取 [4,1,1,1]
从 0 开始，你可以构造出 8 个连续整数。
示例 3：输入：nums = [1,4,10,3,1] 输出：20
提示：coins.length == n
1 <= n <= 4 * 104
1 <= coins[i] <= 4 * 104

解题思路¶

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

func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)
	res := 1
	target := 1
	sum := 0
	for i := 0; i < len(coins); i++ {
		sum = sum + coins[i]
		if coins[i] <= target {
			target = sum + 1
			res = target
		} else {
			break
		}
	}
	return res
}

# 2
func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)
	res := 0
	for i := 0; i < len(coins); i++ {
		if res >= coins[i]-1 {
			res = res + coins[i]
		}else {
			break
		}
	}
	return res + 1
}

1701-1800-Hard¶

1703.得到连续K个1的最少相邻交换次数¶

题目¶

给你一个整数数组nums和一个整数k。nums 仅包含0和1。每一次移动，你可以选择 相邻两个数字并将它们交换。
请你返回使nums中包含k个 连续1的 最少交换次数。
示例 1：输入：nums = [1,0,0,1,0,1], k = 2 输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
示例 2：输入：nums = [1,0,0,0,0,0,1,1], k = 3 输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
示例 3：输入：nums = [1,1,0,1], k = 2 输出：0
解释：nums 已经有连续 2 个 1 了。
提示：1 <= nums.length <= 105
nums[i] 要么是0，要么是1。
1 <= k <= sum(nums)

解题思路¶

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

1707.与数组中元素的最大异或值(2)¶

题目

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。
换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。
如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] 输出：[3,3,7]
解释：1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
示例 2：输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]] 输出：[15,-1,5]
提示：1 <= nums.length, queries.length <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109

解题思路

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

func maximizeXor(nums []int, queries [][]int) []int {
	sort.Ints(nums)
	n := len(queries)
	for i := 0; i < n; i++ {
		queries[i] = append(queries[i], i) // 每个查询添加1个下标方便排序后找到原来的位置
	}
	sort.Slice(queries, func(i, j int) bool {
		return queries[i][1] < queries[j][1] // 按照mi从小到大排序
	})
	root := &Trie{next: make([]*Trie, 2)}
	res := make([]int, n)
	var j int
	for i := 0; i < n; i++ {
		target, mi, index := queries[i][0], queries[i][1], queries[i][2]
		for j < len(nums) && nums[j] <= mi { // 插入小于等于mi的数
			root.Insert(nums[j])
			j++
		}
		if j == 0 {
			res[index] = -1
		} else {
			res[index] = root.getMaxValue(target)
		}
	}
	return res
}

type Trie struct {
	next []*Trie // 0或者1
}

// 插入num
func (t *Trie) Insert(num int) {
	temp := t
	for i := 31; i >= 0; i-- {
		value := (num >> i) & 1
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next: make([]*Trie, 2),
			}
		}
		temp = temp.next[value]
	}
}

// 查找异或对应的最大值
func (t *Trie) getMaxValue(num int) int {
	res := 0
	temp := t
	for i := 31; i >= 0; i-- {
		value := (num >> i) & 1
		if temp.next[1-value] != nil { // 能取到1
			res = res | (1 << i) // 结果在该位可以为1，该为置为1
			temp = temp.next[1-value]
		} else {
			temp = temp.next[value]
		}
	}
	return res
}

# 2
type Trie struct {
	next     []*Trie // 0或者1
	minValue int     // 小于当前节点的最小值
}

// 插入num
func (t *Trie) Insert(num int) {
	temp := t
	if num < temp.minValue {
		temp.minValue = num
	}
	for i := 31; i >= 0; i-- {
		value := (num >> i) & 1
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next:     make([]*Trie, 2),
				minValue: num,
			}
		}
		temp = temp.next[value]
		if num < temp.minValue {
			temp.minValue = num
		}
	}
}

func (t *Trie) getMaxValueWithLimit(num int, limit int) int {
	res := 0
	temp := t
	if temp.minValue > limit {
		return -1
	}
	for i := 31; i >= 0; i-- {
		value := (num >> i) & 1
		if temp.next[1-value] != nil && temp.next[1-value].minValue <= limit { // 能取到1
			res = res | (1 << i) // 结果在该位可以为1，该为置为1
			temp = temp.next[1-value]
		} else {
			temp = temp.next[value]
		}
	}
	return res
}

1713.得到子序列的最少操作次数(1)¶

题目

给你一个数组target，包含若干 互不相同的整数，以及另一个整数数组arr，arr可能 包含重复元素。
每一次操作中，你可以在 arr的任意位置插入任一整数。比方说，如果arr = [1,4,1,2]，
那么你可以在中间添加 3得到[1,4,3,1,2]。你可以在数组最开始或最后面添加整数。
请你返回 最少操作次数，使得target成为arr的一个子序列。
一个数组的 子序列指的是删除原数组的某些元素（可能一个元素都不删除），
同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4]是[4,2,3,7,2,1,4]的子序列（加粗元素），
但[2,4,2]不是子序列。
示例 1：输入：target = [5,1,3], arr = [9,4,2,3,4] 输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例 2：输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1] 输出：3
提示：1 <= target.length, arr.length <= 105
1 <= target[i], arr[i] <= 109
target不包含任何重复元素。

解题思路

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

func minOperations(target []int, arr []int) int {
	m := make(map[int]int)
	for i := 0; i < len(target); i++ {
		m[target[i]] = i
	}
	nums := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		if v, ok := m[arr[i]]; ok {
			nums = append(nums, v)
		}
	}
	res := lengthOfLIS(nums) // leetcode 300.最长上升子序列
	return len(target) - res
}

func lengthOfLIS(nums []int) int {
	if len(nums) < 2 {
		return len(nums)
	}
	arr := make([]int, len(nums)+1)
	arr[1] = nums[0]
	res := 1
	for i := 1; i < len(nums); i++ {
		if arr[res] < nums[i] {
			res++
			arr[res] = nums[i]
		} else {
			left, right := 1, res
			index := 0
			for left <= right {
				mid := left + (right-left)/2
				if arr[mid] < nums[i] {
					index = mid
					left = mid + 1
				} else {
					right = mid - 1
				}
			}
			arr[index+1] = nums[i]
		}
	}
	return res
}

1723.完成所有工作的最短时间(4)¶

题目

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：输入：jobs = [3,2,3], k = 3 输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：输入：jobs = [1,2,4,7,8], k = 2 输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。
提示：1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 107

解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找+回溯	O(log(n)n^n)	O(n)
02	二分查找+内置函数+回溯	O(log(n)n^n)	O(n)
03	动态规划+状态压缩	O(n*3^n)	O(n*2^n)
04	回溯	O(n^n)	O(n)

func minimumTimeRequired(jobs []int, k int) int {
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i] > jobs[j]
	})
	sum := 0
	for i := 0; i < len(jobs); i++ {
		sum = sum + jobs[i]
	}
	left, right := jobs[0], sum
	for left < right {
		mid := left + (right-left)/2
		if dfs(jobs, make([]int, k), mid, 0) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func dfs(jobs []int, arr []int, limit int, index int) bool {
	if index >= len(jobs) {
		return true
	}
	for i := 0; i < len(arr); i++ {
		if arr[i]+jobs[index] <= limit {
			arr[i] = arr[i] + jobs[index]
			if dfs(jobs, arr, limit, index+1) == true {
				return true
			}
			arr[i] = arr[i] - jobs[index]
		}
		// 当前没有被分配 | 当前分配达到上线 => 不需要尝试继续分配
		// 剪枝:去除也可以过
		if arr[i] == 0 || arr[i]+jobs[index] == limit {
			break
		}
	}
	return false
}

# 2
func minimumTimeRequired(jobs []int, k int) int {
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i] > jobs[j]
	})
	sum := 0
	for i := 0; i < len(jobs); i++ {
		sum = sum + jobs[i]
	}
	left, right := jobs[0], sum
	return left + sort.Search(right-left, func(limit int) bool {
		return dfs(jobs, make([]int, k), limit+left, 0)
	})
}

func dfs(jobs []int, arr []int, limit int, index int) bool {
	if index >= len(jobs) {
		return true
	}
	for i := 0; i < len(arr); i++ {
		if arr[i]+jobs[index] <= limit {
			arr[i] = arr[i] + jobs[index]
			if dfs(jobs, arr, limit, index+1) == true {
				return true
			}
			arr[i] = arr[i] - jobs[index]
		}
		// 当前没有被分配 | 当前分配达到上线 => 不需要尝试继续分配
		// 剪枝:去除也可以过
		if arr[i] == 0 || arr[i]+jobs[index] == limit {
			break
		}
	}
	return false
}

# 3
func minimumTimeRequired(jobs []int, k int) int {
	n := len(jobs)
	total := 1 << n
	sum := make([]int, total)
	for i := 0; i < n; i++ { // 预处理：任务的状态和，分配给某一个人的和
		count := 1 << i
		for j := 0; j < count; j++ {
			sum[count|j] = sum[j] + jobs[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
		}
	}
	dp := make([][]int, k) // f[i][j]=>给前i个人分配工作，工作的分配情况为j时，完成所有工作的最短时间
	for i := 0; i < k; i++ {
		dp[i] = make([]int, total)
	}
	for i := 0; i < total; i++ { // 第0个人的时候
		dp[0][i] = sum[i]
	}
	for i := 1; i < k; i++ {
		for j := 0; j < total; j++ {
			minValue := math.MaxInt32            // dp[i][j]未赋值，为0
			for a := j; a > 0; a = (a - 1) & j { // 遍历得到比较小的子集：数字j二进制为1位置上的非0子集
				// 取子集的补集：j-a 或者 使用异或j^a
				// minValue = min(minValue, max(dp[i-1][j-a], sum[a]))
				minValue = min(minValue, max(dp[i-1][j^a], sum[a]))
			}
			dp[i][j] = minValue
		}
	}
	return dp[k-1][total-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
}

# 4
var res int

func minimumTimeRequired(jobs []int, k int) int {
	res = math.MaxInt32
	dfs(jobs, make([]int, k), 0, 0, 0)
	return res
}

// index => job的下标；count => 已经分配工人数组的个数
func dfs(jobs []int, arr []int, index int, maxValue int, count int) {
	if maxValue > res { // 剪枝
		return
	}
	if index == len(jobs) {
		res = maxValue
		return
	}
	if count < len(arr) { // 分配给空闲的
		arr[count] = jobs[index]
		dfs(jobs, arr, index+1, max(maxValue, arr[count]), count+1)
		arr[count] = 0
	}
	for i := 0; i < count; i++ { // 分配给非空闲的
		arr[i] = arr[i] + jobs[index]
		dfs(jobs, arr, index+1, max(maxValue, arr[i]), count)
		arr[i] = arr[i] - jobs[index]
	}
}

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

1739.放置盒子(2)¶

题目

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
示例 1：输入：n = 3 输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 2：输入：n = 4 输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 3：输入：n = 10 输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。
提示：1 <= n <= 109

解题思路

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

func minimumBoxes(n int) int {
	res := 0
	k := 1 // 第几层
	total := 0
	for {
		count := k * (k + 1) / 2 // 第几层数量
		if total+count > n {     // 大于n就不加了
			break
		}
		total = total + count
		k++
	}
	k--
	res = k * (k + 1) / 2 // 最底层
	k = 1
	for total < n { // 底层再从一条边上往墙角叠加
		total = total + k
		k++
		res++
	}
	return res
}

# 2
func minimumBoxes(n int) int {
	res := 0
	left, right := 1, 3000
	for left < right {
		mid := left + (right-left)/2
		if mid*(mid+1)*(mid+2)/6 < n {
			left = mid + 1
		} else {
			right = mid
		}
	}
	left = left - 1
	res = (1 + left) * left / 2
	n = n - left*(left+1)*(left+2)/6
	left, right = 0, n
	for left < right {
		mid := left + (right-left)/2
		target := mid * (mid + 1) / 2
		if target < n {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return res + left
}

1745.回文串分割IV(2)¶

题目

给你一个字符串s，如果可以将它分割成三个非空回文子字符串，那么返回true，否则返回false。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：输入：s = "abcbdd" 输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：输入：s = "bcbddxy" 输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：3 <= s.length <= 2000
s只包含小写英文字母。

解题思路

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

func checkPartitioning(s string) bool {
	for i := 1; i < len(s)-1; i++ {
		a := s[0:i]
		if check(a) == false {
			continue
		}
		for j := len(s) - 1; j > i; j-- {
			c := s[j:]
			if check(c) == false {
				continue
			}
			b := s[i:j]
			if check(b) == true {
				return true
			}
		}
	}
	return false
}

func check(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

# 2
func checkPartitioning(s string) bool {
	n := len(s)
	dp := make([][]bool, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if i == j {
				dp[i][j] = true
			} else if i+1 == j && s[i] == s[j] {
				dp[i][j] = true
			} else {
				if s[i] == s[j] && dp[i+1][j-1] == true {
					dp[i][j] = true
				}
			}
		}
	}
	for i := 0; i < n-2; i++ {
		if dp[0][i] == false {
			continue
		}
		for j := i + 1; j < n-1; j++ {
			if dp[i+1][j] && dp[j+1][n-1] {
				return true
			}
		}
	}
	return false
}

1751.最多可以参加的会议数目II(2)¶

题目

给你一个events数组，其中events[i] = [startDayi, endDayi, valuei]，表示第i个会议在startDayi天开始，
第endDayi天结束，如果你参加这个会议，你能得到价值valuei。同时给你一个整数k表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整地参加完这个会议。
会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值最大和。
示例 1： 输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2 输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2 输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不需要参加满 k 个会议。
示例 3：输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3 输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
提示：1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+二分查找	O(n^2*log(n))	O(1)
02	排序+动态规划	O(n^2)	O(1)

func maxValue(events [][]int, k int) int {
	n := len(events)
	sort.Slice(events, func(i, j int) bool {
		if events[i][1] == events[j][1] {
			return events[i][2] < events[j][2]
		}
		return events[i][1] < events[j][1]
	})
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			dp[i][j] = dp[i-1][j]
			left, right := 0, i-1
			for left < right {
				mid := left + (right-left)/2
				if events[mid][1] < events[i-1][0] {
					left = mid + 1
				} else {
					right = mid
				}
			}
			dp[i][j] = max(dp[i][j], dp[right][j-1]+events[i-1][2])
		}
	}
	res := 0
	for i := 1; i <= k; i++ {
		res = max(res, dp[n][i])
	}
	return res
}

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

# 2
func maxValue(events [][]int, k int) int {
	n := len(events)
	sort.Slice(events, func(i, j int) bool {
		if events[i][1] == events[j][1] {
			return events[i][2] < events[j][2]
		}
		return events[i][1] < events[j][1]
	})
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		index := 0
		for j := i - 1; j >= 1; j-- {
			if events[j-1][1] < events[i-1][0] {
				index = j
				break
			}
		}
		for j := 1; j <= k; j++ {
			dp[i][j] = max(dp[i-1][j], dp[index][j-1]+events[i-1][2])
		}
	}
	return dp[n][k]
}

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

1755.最接近目标值的子序列和¶

题目¶

给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。
也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的 最小值 。
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
示例 1：输入：nums = [5,-7,3,5], goal = 6 输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。
示例 2：输入：nums = [7,-9,15,-2], goal = -5 输出：1
解释：选出子序列 [7,-9,-2] ，元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。
示例 3：输入：nums = [1,2,3], goal = -7 输出：7
提示：1 <= nums.length <= 40
-107 <= nums[i] <= 107
-109 <= goal <= 109

解题思路¶

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

1761.一个图中连通三元组的最小度数(1)¶

题目

给你一个无向图，整数 n表示图中节点的数目，edges数组表示图中的边，
其中edges[i] = [ui, vi]，表示ui 和vi之间有一条无向边。
一个 连通三元组指的是 三个节点组成的集合且这三个点之间 两两有边。
连通三元组的度数是所有满足此条件的边的数目：一个顶点在三元组内，而另一个顶点不在三元组内。
请你返回所有连通三元组中度数的 最小值，如果图中没有连通三元组，那么返回 -1。
示例 1：输入：n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]] 输出：3
解释：只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。
示例 2：输入：n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]] 输出：0
解释：有 3 个三元组：
1) [1,4,3]，度数为 0 。
2) [2,5,6]，度数为 2 。
3) [5,6,7]，度数为 2 。
提示：2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。

解题思路

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

func minTrioDegree(n int, edges [][]int) int {
	arr := make([]int, 401)
	m := make(map[int]bool)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a]++
		arr[b]++
		m[getValue(a, b)] = true
	}
	res := math.MaxInt32
	for i := 1; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if m[getValue(i, j)] == true {
				for k := j + 1; k <= n; k++ {
					if m[getValue(i, k)] == true && m[getValue(j, k)] == true {
						if arr[i]+arr[j]+arr[k]-6 < res {
							res = arr[i] + arr[j] + arr[k] - 6
						}
					}
				}
			}
		}
	}
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

func getValue(a, b int) int {
	if a > b {
		a, b = b, a
	}
	return a*1000 + b
}

1766.互质树(1)¶

题目

给你一个 n个节点的树（也就是一个无环连通无向图），节点编号从 0到 n - 1，且恰好有 n - 1条边，每个节点有一个值。
树的 根节点为 0 号点。
给你一个整数数组nums和一个二维数组edges来表示这棵树。nums[i]表示第i个点的值，
edges[j] = [uj, vj]表示节点uj和节点vj在树中有一条边。
当gcd(x, y) == 1，我们称两个数x 和y是 互质的，其中gcd(x, y)是 x和 y的 最大公约数。
从节点i到 根最短路径上的点都是节点 i的祖先节点。一个节点 不是 它自己的祖先节点。
请你返回一个大小为 n的数组 ans，其中ans[i]是离节点i最近的祖先节点且满足nums[i] 和nums[ans[i]]是 互质的，
如果不存在这样的祖先节点，ans[i]为 -1。
示例 1：输入：nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]] 输出：[-1,0,0,1]
解释：上图中，每个节点的值在括号中表示。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。
- 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。
- 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。
它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。
示例 2：输入：nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] 输出：[-1,0,-1,0,0,0,-1]
提示：nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj

解题思路

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

var res []int             // 结果
var arr [][]int           // 邻接表
var path map[int][][2]int // 路径：以每个值做区分来记录path，每个值取最新的path来比较即可

func getCoprimes(nums []int, edges [][]int) []int {
	n := len(nums)
	res = make([]int, n)
	arr = make([][]int, n)
	path = make(map[int][][2]int)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a] = append(arr[a], b)
		arr[b] = append(arr[b], a)
	}
	dfs(nums, 0, -1, 0)
	return res
}

func dfs(nums []int, cur int, prev int, level int) {
	index, depth := -1, -1
	for i := 1; i <= 50; i++ {
		if len(path[i]) > 0 {
			a, b := path[i][len(path[i])-1][0], path[i][len(path[i])-1][1] // 遍历每个值最近
			if a > depth && gcd(i, nums[cur]) == 1 {                       // 更新：更近+互质
				depth = a
				index = b
			}
		}
	}
	res[cur] = index
	for i := 0; i < len(arr[cur]); i++ {
		value := nums[cur]
		next := arr[cur][i]
		if next != prev {
			path[value] = append(path[value], [2]int{level, cur})
			dfs(nums, next, cur, level+1)
			path[value] = path[value][:len(path[value])-1]
		}
	}
}

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

1771.由子序列构造的最长回文串的长度(3)¶

题目

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：
从 word1 中选出某个 非空 子序列 subsequence1 。
从 word2 中选出某个 非空 子序列 subsequence2 。
连接两个子序列 subsequence1 + subsequence2 ，得到字符串。
返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。
字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。
回文串 是正着读和反着读结果一致的字符串。
示例 1：输入：word1 = "cacb", word2 = "cbba" 输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。
示例 2：输入：word1 = "ab", word2 = "ab" 输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。
示例 3：输入：word1 = "aa", word2 = "bb" 输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。
提示：1 <= word1.length, word2.length <= 1000
word1 和 word2 由小写英文字母组成

解题思路

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

func longestPalindrome(word1 string, word2 string) int {
	s := word1 + word2
	a := len(word1)
	n := len(s)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	res := 0
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2 // 内层+2
				if i < a && j >= a {
					res = max(res, dp[i][j])
				}
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}
	return res
}

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

# 2
func longestPalindrome(word1 string, word2 string) int {
	s := word1 + word2
	a := len(word1)
	n := len(s)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
	}
	res := 0
	for i := n - 1; i >= 0; i-- {
		prev := 0
		for j := i + 1; j < n; j++ {
			temp := dp[j]
			if s[i] == s[j] {
				dp[j] = prev + 2 // 内层+2
				if i < a && j >= a {
					res = max(res, dp[j])
				}
			} else {
				dp[j] = max(dp[j], dp[j-1])
			}
			prev = temp
		}
	}
	return res
}

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

# 3
var dp [][]int
var a int
var res int

func longestPalindrome(word1 string, word2 string) int {
	s := word1 + word2
	a = len(word1)
	res = 0
	n := len(s)
	dp = make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	dfs(s, 0, n-1)
	return res
}

func dfs(s string, i, j int) int {
	if i == j {
		return 1
	}
	if i > j {
		return 0
	}
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	if s[i] == s[j] {
		dp[i][j] = dfs(s, i+1, j-1) + 2
		if i < a && j >= a {
			res = max(res, dp[i][j])
		}
	} else {
		dp[i][j] = max(dfs(s, i+1, j), dfs(s, i, j-1))
	}
	return dp[i][j]
}

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

1776.车队II(2)¶

题目

在一条单车道上有 n辆车，它们朝着同样的方向行驶。
给你一个长度为 n的数组 cars，其中cars[i] = [positioni, speedi]，它表示：
positioni是第 i辆车和道路起点之间的距离（单位：米）。题目保证positioni < positioni+1。
speedi是第 i辆车的初始速度（单位：米/秒）。
简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。
一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里最慢一辆车的速度。
请你返回一个数组answer，其中answer[i]是第 i辆车与下一辆车相遇的时间（单位：秒），
如果这辆车不会与下一辆车相遇，则 answer[i]为 -1。答案精度误差需在 10-5以内。
示例 1：输入：cars = [[1,2],[2,1],[4,3],[7,2]] 输出：[1.00000,-1.00000,3.00000,-1.00000]
解释：经过恰好 1 秒以后，第一辆车会与第二辆车相遇，并形成一个 1 m/s 的车队。
经过恰好 3 秒以后，第三辆车会与第四辆车相遇，并形成一个 2 m/s 的车队。
示例 2：输入：cars = [[3,4],[5,4],[6,3],[9,1]] 输出：[2.00000,1.00000,1.50000,-1.00000]
提示：1 <= cars.length <= 105
1 <= positioni, speedi <= 106
positioni < positioni+1

解题思路

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

func getCollisionTimes(cars [][]int) []float64 {
	n := len(cars)
	res := make([]float64, n)
	stack := make([]int, 0) // 单调栈
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 {
			top := stack[len(stack)-1]
			a := float64(cars[top][0] - cars[i][0]) // 距离差
			b := float64(cars[i][1] - cars[top][1]) // 速度差
			if (cars[i][1] <= cars[top][1]) ||      // 1、永远追不上栈顶车
				(res[top] > 0 && a/b > res[top]) { // 2、可以在栈顶车追上更前面车之前追上栈顶车
				stack = stack[:len(stack)-1]
			} else {
				break
			}
		}
		if len(stack) == 0 {
			res[i] = -1
		} else { // 可以追上
			top := stack[len(stack)-1]
			a := float64(cars[top][0] - cars[i][0]) // 距离差
			b := float64(cars[i][1] - cars[top][1]) // 速度差
			res[i] = a / b
		}
		stack = append(stack, i)
	}
	return res
}

# 2
func getCollisionTimes(cars [][]int) []float64 {
	n := len(cars)
	res := make([]float64, n)
	stack := make([]int, 0) // 单调栈
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 {
			top := stack[len(stack)-1]
			if cars[i][1] <= cars[top][1] { // 1、永远追不上栈顶车
				stack = stack[:len(stack)-1]
			} else {
				a := float64(cars[top][0] - cars[i][0]) // 距离差
				b := float64(cars[i][1] - cars[top][1]) // 速度差
				if res[top] < 0 {
					break
				} else if res[top] > 0 && a/b > res[top] { // 2、可以在栈顶车追上更前面车之前追上栈顶车
					stack = stack[:len(stack)-1]
				} else {
					break
				}
			}
		}
		if len(stack) == 0 {
			res[i] = -1
		} else { // 可以追上
			top := stack[len(stack)-1]
			a := float64(cars[top][0] - cars[i][0]) // 距离差
			b := float64(cars[i][1] - cars[top][1]) // 速度差
			res[i] = a / b
		}
		stack = append(stack, i)
	}
	return res
}

1782.统计点对的数目(1)¶

题目

给你一个无向图，无向图由整数n，表示图中节点的数目，和edges组成，
其中edges[i] = [ui, vi]表示ui 和vi之间有一条无向边。同时给你一个代表查询的整数数组queries。
第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：
a < b
cnt是与 a或者b相连的边的数目，且 cnt严格大于queries[j]。
请你返回一个数组answers，其中answers.length == queries.length 且answers[j]是第 j个查询的答案。
请注意，图中可能会有 重复边。
示例 1：输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3] 输出：[6,5]
解释：每个点对中，与至少一个点相连的边的数目如上图所示。
示例 2：输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
输出：[10,10,9,8,6]
提示：2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length

解题思路

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

func countPairs(n int, edges [][]int, queries []int) []int {
	degree := make([]int, n+1) // 点=>相连边的次数
	m := make(map[[2]int]int)  // 边的出现次数
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		if a > b { // 调整为a<b
			a, b = b, a
		}
		m[[2]int{a, b}]++
		degree[a]++
		degree[b]++
	}
	arr := make([]int, n+1) // 使用临时数组来排序
	copy(arr, degree)
	sort.Ints(arr)
	res := make([]int, len(queries))
	for i := 0; i < len(queries); i++ {
		target := queries[i]
		left, right := 1, n // 双指针=>2数之和
		for left < right {
			if target < arr[left]+arr[right] {
				res[i] = res[i] + right - left // 计算对数
				right--
			} else {
				left++
			}
		}
		for k, v := range m { // 遍历边：减去2点之间的重复边的数量后不满足要求，数目-1
			a, b := k[0], k[1]
			if target < degree[a]+degree[b] && target >= degree[a]+degree[b]-v {
				res[i]--
			}
		}
	}
	return res
}

1787.使所有区间的异或结果为零¶

题目¶

给你一个整数数组 nums和一个整数 k 。区间 [left, right]（left <= right）的 异或结果 
是对下标位于left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：
nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。
返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
示例 1：输入：nums = [1,2,0,3,0], k = 1 输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
示例 2：输入：nums = [3,4,5,2,1,7,3,4,7], k = 3 输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]
示例 3：输入：nums = [1,2,4,1,2,5,1,2,6], k = 3 输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]
提示：1 <= k <= nums.length <= 2000
0 <= nums[i] < 210

解题思路¶

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

1793.好子数组的最大分数(2)¶

题目

给你一个整数数组nums（下标从 0 开始）和一个整数k。
一个子数组 (i, j)的 分数定义为min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)。
一个好子数组的两个端点下标需要满足i <= k <= j。
请你返回 好子数组的最大可能 分数。
示例 1：输入：nums = [1,4,3,7,4,5], k = 3 输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
示例 2：输入：nums = [5,5,4,5,4,1,1,1], k = 0 输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length

解题思路

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

func maximumScore(nums []int, k int) int {
	left, right := k, k
	res := 0
	for minValue := nums[k]; minValue >= 1; minValue-- {
		for left >= 0 && nums[left] >= minValue {
			left--
		}
		for right < len(nums) && nums[right] >= minValue {
			right++
		}
		left++  // left注意+1
		right-- // right注意-1
		res = max(res, minValue*(right-left+1))
	}
	return res
}

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

# 2
func maximumScore(nums []int, k int) int {
	res := 0
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	stack := make([]int, 0)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			left[i] = -1
		} else {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	stack = make([]int, 0)
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			right[i] = n
		} else {
			right[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i := 0; i < n; i++ {
		if left[i] < k && right[i] > k {
			res = max(res, nums[i]*(right[i]-left[i]-1))
		}
	}
	return res
}

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

1799.N次操作后的最大分数和(3)¶

题目

给你nums，它是一个大小为2 * n的正整数数组。你必须对这个数组执行 n次操作。
在第i次操作时（操作编号从 1开始），你需要：
选择两个元素x 和y。
获得分数i * gcd(x, y)。
将x和y 从nums中删除。
请你返回 n次操作后你能获得的分数和最大为多少。
函数gcd(x, y)是x 和y的最大公约数。
示例 1：输入：nums = [1,2] 输出：1
解释：最优操作是：(1 * gcd(1, 2)) = 1
示例 2：输入：nums = [3,4,6,8] 输出：11
解释：最优操作是：(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
示例 3：输入：nums = [1,2,3,4,5,6] 输出：14
解释：最优操作是：(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
提示：1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 106

解题思路

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

func maxScore(nums []int) int {
	n := len(nums)
	total := 1 << n
	dp := make([]int, total)
	arr := [14][14]int{}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			value := gcd(nums[i], nums[j])
			arr[i][j] = value
			arr[j][i] = value
		}
	}
	for i := 0; i < total; i++ { // 枚举状态：以当前状态推出后面的状态
		count := bits.OnesCount(uint(i)) // i对应二进制1个数
		if count%2 == 1 {                // 可去除；剪枝：1的个数为奇数个
			continue
		}
		count = count / 2 // 第count次操作
		for j := 0; j < n; j++ {
			for k := j + 1; k < n; k++ {
				if i&(1<<j) == 0 && i&(1<<k) == 0 { // i的第j位和第k位都为0
					next := i | (1 << j) | (1 << k) // 按位或运算：把i的第j位和第k位补1
					value := dp[i] + (count+1)*arr[j][k]
					if value > dp[next] {
						dp[next] = value
					}
				}
			}
		}
	}
	return dp[total-1]
}

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

# 2
func maxScore(nums []int) int {
	n := len(nums)
	total := 1 << n
	dp := make([]int, total)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			status := (1 << i) | (1 << j) // 把第i位和第j位置1
			dp[status] = gcd(nums[i], nums[j])
		}
	}
	for i := 0; i < total; i++ { // 枚举状态：当前状态依赖之前的
		a := bits.OnesCount(uint(i))
		if a%2 == 1 { // 可去除；剪枝：1的个数为奇数个
			continue
		}
		for j := i; j > 0; j = (j - 1) & i { // 遍历i二进制中位置1的子集
			b := bits.OnesCount(uint(j))
			if a-b == 2 { // 1的个数相差2
				dp[i] = max(dp[i], dp[j]+a/2*dp[i^j]) // 取补集-异或操作：i^j
			}
		}
	}
	return dp[total-1]
}

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

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

# 3
var dp []int
var temp []int

func maxScore(nums []int) int {
	n := len(nums)
	total := 1 << n
	dp = make([]int, total)
	temp = make([]int, total)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			status := (1 << i) | (1 << j) // 把第i位和第j位置1
			temp[status] = gcd(nums[i], nums[j])
		}
	}
	return dfs(nums, total-1, 0) // 从目标往前推
}

func dfs(nums []int, status int, count int) int {
	if dp[status] > 0 {
		return dp[status]
	}
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if (status>>i)&1 == 0 || (status>>j)&1 == 0 { // status的第i或者第j位为0
				continue
			}
			cur := (1 << i) | (1 << j)
			prev := status ^ (1 << i) ^ (1 << j) // 异或操作：把status都为1的第i,j位变为0
			dp[status] = max(dp[status], dfs(nums, prev, count+1)+(count+1)*temp[cur])
		}
	}
	return dp[status]
}

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

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