1801-1900-Easy¶

1805.字符串中不同整数的数目(2)¶

题目

给你一个字符串 word ，该字符串由数字和小写英文字母组成。
请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。
注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）："123"、"34"、"8" 和 "34" 。
返回对 word 完成替换后形成的 不同 整数的数目。
只有当两个整数的 不含前导零 的十进制表示不同， 才认为这两个整数也不同。
示例 1：输入：word = "a123bc34d8ef34" 输出：3
解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。
示例 2：输入：word = "leet1234code234" 输出：2
示例 3：输入：word = "a1b01c001" 输出：1
解释："1"、"01" 和 "001" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。
提示：1 <= word.length <= 1000
word 由数字和小写英文字母组成

解题思路

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

func numDifferentIntegers(word string) int {
	m := make(map[string]bool)
	arr := strings.FieldsFunc(word, func(r rune) bool {
		return 'a' <= r && r <= 'z'
	})
	for i := 0; i < len(arr); i++ {
		s := strings.Trim(arr[i], " ")
		for len(s) > 0 && s[0] == '0' {
			s = s[1:]
		}
		m[s] = true
	}
	return len(m)
}

# 2
func numDifferentIntegers(word string) int {
	m := make(map[int]bool)
	for i := 0; i < len(word); i++ {
		if '0' <= word[i] && word[i] <= '9' {
			value := int(word[i] - '0')
			for i+1 < len(word) && '0' <= word[i+1] && word[i+1] <= '9' {
				i++
				value = value*10 + int(word[i]-'0')
			}
			m[value] = true
		}
	}
	return len(m)
}

1812.判断国际象棋棋盘中一个格子的颜色(2)¶

题目

给你一个坐标coordinates，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。
如果所给格子的颜色是白色，请你返回true，如果是黑色，请返回false。
给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母，第二个字符是数字。
示例 1：输入：coordinates = "a1" 输出：false
解释：如上图棋盘所示，"a1" 坐标的格子是黑色的，所以返回 false 。
示例 2：输入：coordinates = "h3" 输出：true
解释：如上图棋盘所示，"h3" 坐标的格子是白色的，所以返回 true 。
示例 3：输入：coordinates = "c7" 输出：false
提示：coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

解题思路

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

func squareIsWhite(coordinates string) bool {
	a := int(coordinates[0] - 'a')
	b := int(coordinates[1] - '1')
	return (a+b)%2 != 0
}

# 2
func squareIsWhite(coordinates string) bool {
	// a => 97  1 => 49
	return (coordinates[0]+coordinates[1])%2 != 0
}

1816.截断句子(2)¶

题目

句子 是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。
每个单词仅由大小写英文字母组成（不含标点符号）。
例如，"Hello World"、"HELLO" 和 "hello world hello world" 都是句子。
给你一个句子 s和一个整数 k，请你将 s截断 ，使截断后的句子仅含 前 k个单词。
返回 截断 s后得到的句子。
示例 1：输入：s = "Hello how are you Contestant", k = 4 输出："Hello how are you"
解释：s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
前 4 个单词为 ["Hello", "how", "are", "you"]
因此，应当返回 "Hello how are you"
示例 2：输入：s = "What is the solution to this problem", k = 4
输出："What is the solution"
解释：s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]
前 4 个单词为 ["What", "is", "the", "solution"]
因此，应当返回 "What is the solution"
示例 3：输入：s = "chopper is not a tanuki", k = 5 输出："chopper is not a tanuki"
提示：1 <= s.length <= 500
k 的取值范围是 [1, s 中单词的数目]
s 仅由大小写英文字母和空格组成
s 中的单词之间由单个空格隔开
不存在前导或尾随空格

解题思路

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

func truncateSentence(s string, k int) string {
	arr := strings.Split(s, " ")
	if k < len(arr) {
		return strings.Join(arr[:k], " ")
	}
	return s
}

# 2
func truncateSentence(s string, k int) string {
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			count++
			if count == k {
				return s[:i]
			}
		}
	}
	return s
}

1822.数组元素积的符号(1)¶

题目

已知函数signFunc(x) 将会根据 x 的正负返回特定值：
如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。
返回 signFunc(product) 。
示例 1：输入：nums = [-1,-2,-3,-4,3,2,1] 输出：1
解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1
示例 2：输入：nums = [1,5,0,2,-3] 输出：0
解释：数组中所有值的乘积是 0 ，且 signFunc(0) = 0
示例 3：输入：nums = [-1,1,-1,1,-1] 输出：-1
解释：数组中所有值的乘积是 -1 ，且 signFunc(-1) = -1
提示：1 <= nums.length <= 1000
-100 <= nums[i] <= 100

解题思路

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

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

1827.最少操作使数组递增(2)¶

题目

给你一个整数数组nums（下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加1。
比方说，如果nums = [1,2,3]，你可以选择增加nums[1]得到nums = [1,3,3]。
请你返回使 nums严格递增的 最少操作次数。
我们称数组nums是 严格递增的，当它满足对于所有的0 <= i < nums.length - 1都有
nums[i] < nums[i+1]。一个长度为 1的数组是严格递增的一种特殊情况。
示例 1：输入：nums = [1,1,1] 输出：3
解释：你可以进行如下操作：
1) 增加 nums[2] ，数组变为 [1,1,2] 。
2) 增加 nums[1] ，数组变为 [1,2,2] 。
3) 增加 nums[2] ，数组变为 [1,2,3] 。
示例 2：输入：nums = [1,5,2,4,1] 输出：14
示例 3：输入：nums = [8] 输出：0
提示：1 <= nums.length <= 5000
1 <= nums[i] <= 104

解题思路

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

func minOperations(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	res := 0
	for i := 1; i < n; i++ {
		if nums[i-1] >= nums[i] {
			res = res + nums[i-1] + 1 - nums[i]
			nums[i] = nums[i-1] + 1
		}
	}
	return res
}

# 2
func minOperations(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	res := 0
	target := nums[0]
	for i := 1; i < n; i++ {
		if target >= nums[i] {
			res = res + target + 1 - nums[i]
			target = target + 1
		} else {
			target = nums[i]
		}
	}
	return res
}

1832.判断句子是否为全字母句(3)¶

题目

全字母句 指包含英语字母表中每个字母至少一次的句子。
给你一个仅由小写英文字母组成的字符串 sentence ，请你判断sentence 是否为 全字母句 。
如果是，返回 true ；否则，返回 false 。
示例 1：输入：sentence = "thequickbrownfoxjumpsoverthelazydog" 输出：true
解释：sentence 包含英语字母表中每个字母至少一次。
示例 2：输入：sentence = "leetcode" 输出：false
提示：1 <= sentence.length <= 1000
sentence 由小写英语字母组成

解题思路

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

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

# 2
func checkIfPangram(sentence string) bool {
	res := 0
	target := 1 << 26 -1
	for i := 0; i < len(sentence); i++{
		res = res |  1 << (sentence[i]-'a')
	}
	return res == target
}

# 3
func checkIfPangram(sentence string) bool {
	m := make(map[byte]int)
	for i := 0; i < len(sentence); i++ {
		m[sentence[i]-'a']++
	}
	return len(m) == 26
}

1837.K进制表示下的各位数字总和(1)¶

题目

给你一个整数 n（10 进制）和一个基数 k ，请你将 n 从 10 进制表示转换为 k 进制表示，
计算并返回转换后各位数字的 总和 。
转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。
示例 1：输入：n = 34, k = 6 输出：9
解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
示例 2：输入：n = 10, k = 10 输出：1
解释：n 本身就是 10 进制。 1 + 0 = 1 。
提示：1 <= n <= 100
2 <= k <= 10

解题思路

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

func sumBase(n int, k int) int {
	res := 0
	for n > 0 {
		res = res + n%k
		n = n / k
	}
	return res
}

1844.将所有数字用字符替换(1)¶

题目

给你一个下标从 0开始的字符串 s，它的 偶数 下标处为小写英文字母，奇数下标处为数字。
定义一个函数shift(c, x)，其中c是一个字符且x是一个数字，函数返回字母表中c后面第 x个字符。
比方说，shift('a', 5) = 'f'和shift('x', 0) = 'x'。
对于每个 奇数下标i，你需要将数字s[i] 用shift(s[i-1], s[i])替换。
请你替换所有数字以后，将字符串 s返回。题目 保证shift(s[i-1], s[i])不会超过 'z'。
示例 1：输入：s = "a1c1e1" 输出："abcdef"
解释：数字被替换结果如下：
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('c',1) = 'd'
- s[5] -> shift('e',1) = 'f'
示例 2：输入：s = "a1b2c3d4e" 输出："abbdcfdhe"
解释：数字被替换结果如下：
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('b',2) = 'd'
- s[5] -> shift('c',3) = 'f'
- s[7] -> shift('d',4) = 'h'
提示：1 <= s.length <= 100
s只包含小写英文字母和数字。
对所有 奇数 下标处的i，满足shift(s[i-1], s[i]) <= 'z'。

解题思路

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

func replaceDigits(s string) string {
	res := []byte(s)
	for i := 1; i < len(s); i = i + 2 {
		res[i] = s[i-1] + s[i] - '0'
	}
	return string(res)
}

1848.到目标元素的最小距离(1)¶

题目

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，
满足 nums[i] == target 且 abs(i - start) 最小化 。注意：abs(x) 表示 x 的绝对值。
返回 abs(i - start) 。
题目数据保证 target 存在于 nums 中。
示例 1：输入：nums = [1,2,3,4,5], target = 5, start = 3 输出：1
解释：nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。
示例 2：输入：nums = [1], target = 1, start = 0 输出：0
解释：nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 1 。
示例 3：输入：nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0 输出：0
解释：nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。
提示：1 <= nums.length <= 1000
1 <= nums[i] <= 104
0 <= start < nums.length
target 存在于 nums 中

解题思路

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

func getMinDistance(nums []int, target int, start int) int {
	res := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			res = min(res, abs(i-start))
		}
	}
	return res
}

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
}

1854.人口最多的年份(2)¶

题目

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。
年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：
x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。
返回 人口最多 且 最早 的年份。
示例 1：输入：logs = [[1993,1999],[2000,2010]] 输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。
示例 2：输入：logs = [[1950,1961],[1960,1971],[1970,1981]] 输出：1960
解释： 人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。
提示：1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050

解题思路

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

func maximumPopulation(logs [][]int) int {
	arr := [101]int{}
	for i := 0; i < len(logs); i++ {
		a, b := logs[i][0], logs[i][1]
		arr[a-1950]++
		arr[b-1950]--
	}
	res := 0
	sum := 0
	count := 0
	for i := 0; i < len(arr); i++ {
		sum = sum + arr[i]
		if sum > count {
			count = sum
			res = i + 1950
		}
	}
	return res
}

# 2
func maximumPopulation(logs [][]int) int {
	arr := [101]int{}
	for i := 0; i < len(logs); i++ {
		a, b := logs[i][0], logs[i][1]
		for j := a; j < b; j++ {
			arr[j-1950]++
		}
	}
	res := 0
	count := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] > count {
			count = arr[i]
			res = i + 1950
		}
	}
	return res
}

1859.将句子排序(2)¶

题目

一个 句子指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。
我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词打乱顺序。
比方说，句子"This is a sentence"可以被打乱顺序得到"sentence4 a3 is2 This1"或者"is2 sentence4 This1 a3"。
给你一个 打乱顺序的句子s，它包含的单词不超过9个，请你重新构造并得到原本顺序的句子。
示例 1：输入：s = "is2 sentence4 This1 a3"
输出："This is a sentence"
解释：将 s 中的单词按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后删除数字。
示例 2：输入：s = "Myself2 Me1 I4 and3"
输出："Me Myself and I"
解释：将 s 中的单词按照初始位置排序，得到 "Me1 Myself2 and3 I4" ，然后删除数字。
提示：2 <= s.length <= 200
s只包含小写和大写英文字母、空格以及从1到9的数字。
s中单词数目为1到9个。
s中的单词由单个空格分隔。
s不包含任何前导或者后缀空格。

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+内置函数	O(nlog(n))	O(n)
02	内置函数	O(n)	O(n)

func sortSentence(s string) string {
	arr := strings.Split(s, " ")
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][len(arr[i])-1] < arr[j][len(arr[j])-1]
	})
	for i := 0; i < len(arr); i++ {
		arr[i] = arr[i][:len(arr[i])-1]
	}
	return strings.Join(arr, " ")
}

# 2
func sortSentence(s string) string {
	arr := strings.Split(s, " ")
	temp := make([]string, len(arr)+1)
	for i := 0; i < len(arr); i++ {
		index, _ := strconv.Atoi(string(arr[i][len(arr[i])-1]))
		temp[index] = arr[i][:len(arr[i])-1]
	}
	return strings.Join(temp[1:], " ")
}

1863.找出所有子集的异或总和再求和(4)¶

题目

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
例如，数组[2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
示例 1：输入：nums = [1,3] 输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6
示例 2：输入：nums = [5,1,6] 输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
示例 3：输入：nums = [3,4,5,6,7,8] 输出：480
解释：每个子集的全部异或总和值之和为 480 。
提示：1 <= nums.length <= 12
1 <= nums[i] <= 20

解题思路

No.	思路	时间复杂度	空间复杂度
01	子集-回溯	O(n*2^n)	O(1)
02	位运算	O(n*2^n)	O(1)
03	位运算	O(n*2^n)	O(1)
04	数学	O(n)	O(1)

var res int

func subsetXORSum(nums []int) int {
	res = 0
	dfs(nums, 0, 0)
	return res
}

func dfs(nums []int, sum int, index int) {
	if index >= len(nums) {
		res = res + sum
		return
	}
	dfs(nums, sum, index+1)
	dfs(nums, sum^nums[index], index+1)
}

# 2
func subsetXORSum(nums []int) int {
	res := 0
	n := len(nums)
	left := 1 << n
	right := 1 << (n + 1)
	for i := left; i < right; i++ {
		sum := 0
		for j := 0; j < n; j++ {
			if i&(1<<j) != 0 {
				sum = sum ^ nums[j]
			}
		}
		res = res + sum
	}
	return res
}

# 3
func subsetXORSum(nums []int) int {
	res := 0
	n := len(nums)
	total := 1 << n
	for i := 0; i < total; i++ {
		sum := 0
		for j := 0; j < n; j++ {
			if (i>>j)&1 == 1 {
				sum = sum ^ nums[j]
			}
		}
		res = res + sum
	}
	return res
}

# 4
func subsetXORSum(nums []int) int {
	// 对于任意一位，2^n个子集异或结果中
	// 如果nums中任何一个数字在这一位上都是0，则任何一个子集的异或结果在这一位上都是0
	// 如果nums中有一个数字在这一位上是1，则所有子集异或结果中在这一位上，一半是0，一半是1
	n := len(nums)
	temp := 0
	for i := 0; i < n; i++ {
		temp = temp | nums[i]
	}
	return temp << (n - 1)
}

1869.哪种连续子字符串更长(3)¶

题目

给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；
否则，返回 false 。
例如，s = "110100010" 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。
注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。
示例 1：输入：s = "1101" 输出：true
解释：由 1 组成的最长连续子字符串的长度是 2："1101"
由 0 组成的最长连续子字符串的长度是 1："1101"
由 1 组成的子字符串更长，故返回 true 。
示例 2：输入：s = "111000" 输出：false
解释：由 1 组成的最长连续子字符串的长度是 3："111000"
由 0 组成的最长连续子字符串的长度是 3："111000"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。
示例 3：输入：s = "110100010" 输出：false
解释：由 1 组成的最长连续子字符串的长度是 2："110100010"
由 0 组成的最长连续子字符串的长度是 3："110100010"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。
提示：1 <= s.length <= 100
s[i] 不是 '0' 就是 '1'

解题思路

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

func checkZeroOnes(s string) bool {
	a, b := 0, 0
	prev := uint8(' ')
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == prev {
			count++
		} else {
			if prev == '0' {
				a = max(a, count)
			} else if prev == '1' {
				b = max(b, count)
			}
			count = 1
		}
		prev = s[i]
	}
	if prev == '0' {
		a = max(a, count)
	} else if prev == '1' {
		b = max(b, count)
	}
	return b > a
}

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

# 2
func checkZeroOnes(s string) bool {
	a, b := 0, 0
	aMax, bMax := 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == '0' {
			a++
			b = 0
		} else if s[i] == '1' {
			a = 0
			b++
		}
		aMax = max(aMax, a)
		bMax = max(bMax, b)
	}
	return bMax > aMax
}

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

# 3
func checkZeroOnes(s string) bool {
	a, b := 0, 0
	for _, v := range strings.Split(s, "1") {
		b = max(b, len(v))
	}
	for _, v := range strings.Split(s, "0") {
		a = max(a, len(v))
	}
	return b > a
}

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

1876.长度为三且各字符不同的子字符串(1)¶

题目

如果一个字符串不含有任何重复字符，我们称这个字符串为 好字符串。
给你一个字符串 s，请你返回 s中长度为 3的 好子字符串 的数量。
注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。
示例 1：输入：s = "xyzzaz" 输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。
示例 2：输入：s = "aababcabc" 输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。
提示：1 <= s.length <= 100
s只包含小写英文字母。

解题思路

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

func countGoodSubstrings(s string) int {
	res := 0
	for i := 2; i < len(s); i++ {
		if s[i-2] != s[i-1] && s[i-2] != s[i] && s[i-1] != s[i] {
			res++
		}
	}
	return res
}

1880.检查某单词是否等于两单词之和(2)¶

题目

字母的 字母值 取决于字母在字母表中的位置，从 0 开始 计数。即，'a' -> 0、'b' -> 1、'c' -> 2，以此类推。
对某个由小写字母组成的字符串s 而言，其 数值 就等于将 s 中每个字母的 字母值 按顺序 连接 并 转换 成对应整数。
例如，s = "acb" ，依次连接每个字母的字母值可以得到 "021" ，转换为整数得到 21 。
给你三个字符串 firstWord、secondWord 和 targetWord ，每个字符串都由从 'a' 到 'j' （含'a' 和 'j' ）的小写英文字母组成。
如果firstWord 和 secondWord 的 数值之和 等于 targetWord 的数值，返回 true ；否则，返回 false 。
示例 1：输入：firstWord = "acb", secondWord = "cba", targetWord = "cdb" 输出：true
解释：firstWord 的数值为 "acb" -> "021" -> 21
secondWord 的数值为 "cba" -> "210" -> 210
targetWord 的数值为 "cdb" -> "231" -> 231
由于 21 + 210 == 231 ，返回 true
示例 2：输入：firstWord = "aaa", secondWord = "a", targetWord = "aab" 输出：false
解释：firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aab" -> "001" -> 1
由于 0 + 0 != 1 ，返回 false
示例 3：输入：firstWord = "aaa", secondWord = "a", targetWord = "aaaa" 输出：true
解释：firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aaaa" -> "0000" -> 0
由于 0 + 0 == 0 ，返回 true
提示：1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord、secondWord 和 targetWord 仅由从 'a' 到 'j' （含'a' 和 'j' ）的小写英文字母组成。

解题思路

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

func isSumEqual(firstWord string, secondWord string, targetWord string) bool {
	a := 0
	b := 0
	c := 0
	for i := 0; i < len(firstWord); i++ {
		a = a*10 + int(firstWord[i]-'a')
	}
	for i := 0; i < len(secondWord); i++ {
		b = b*10 + int(secondWord[i]-'a')
	}
	for i := 0; i < len(targetWord); i++ {
		c = c*10 + int(targetWord[i]-'a')
	}
	return a+b == c
}

# 2
func isSumEqual(firstWord string, secondWord string, targetWord string) bool {
	return getValue(firstWord)+getValue(secondWord) == getValue(targetWord)
}

func getValue(str string) int {
	res := 0
	for i := 0; i < len(str); i++ {
		res = res*10 + int(str[i]-'a')
	}
	return res
}

1886.判断矩阵经轮转后是否一致(1)¶

题目

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。
现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与target 一致，返回 true ；否则，返回 false 。
示例 1：输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]] 输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。
示例 2：输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]] 输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。
示例 3：输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]] 输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。
提示：n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 不是 0 就是 1

解题思路

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

func findRotation(mat [][]int, target [][]int) bool {
	for i := 0; i < 4; i++ {
		rotate(mat)
		if compare(mat, target) == true {
			return true
		}
	}
	return false
}

// leetcode 48.旋转图像
func rotate(matrix [][]int) {
	n := len(matrix)
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			arr[j][n-1-i] = matrix[i][j]
		}
	}
	copy(matrix, arr)
}

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

1893.检查是否区域内所有整数都被覆盖(3)¶

题目

给你一个二维整数数组ranges和两个整数left和right。
每个ranges[i] = [starti, endi]表示一个从starti到endi的闭区间。
如果闭区间[left, right]内每个整数都被ranges中至少一个区间覆盖，那么请你返回true，否则返回false。
已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi，那么我们称整数x被覆盖了。
示例 1：输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5 输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。
示例 2：输入：ranges = [[1,10],[10,20]], left = 21, right = 21 输出：false
解释：21 没有被任何一个区间覆盖。
提示：1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50

解题思路

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

func isCovered(ranges [][]int, left int, right int) bool {
	arr := make([]bool, 51)
	for i := 0; i < len(ranges); i++ {
		a, b := ranges[i][0], ranges[i][1]
		for j := a; j <= b; j++ {
			arr[j] = true
		}
	}
	for i := left; i <= right; i++ {
		if arr[i] == false {
			return false
		}
	}
	return true
}

# 2
func isCovered(ranges [][]int, left int, right int) bool {
	arr := make([]int, 52)
	for i := 0; i < len(ranges); i++ {
		a, b := ranges[i][0], ranges[i][1]
		arr[a]++
		arr[b+1]--
	}
	sum := 0
	for i := 0; i <= 50; i++ {
		sum = sum + arr[i]
		if left <= i && i <= right && sum <= 0 {
			return false
		}
	}
	return true
}

# 3
func isCovered(ranges [][]int, left int, right int) bool {
	for i := 0; i < len(ranges); i++ {
		a, b := ranges[i][0], ranges[i][1]
		if a <= left { // a到left已经覆盖：left移动到b后面
			left = b + 1
		}
		if b >= right { // right到b已经覆盖：right移动到a前面
			right = a - 1
		}
		if left > right {
			return true
		}
	}
	return false
}

1897.重新分配字符使所有字符串都相等(1)¶

题目

给你一个字符串数组 words（下标 从 0 开始 计数）。
在一步操作中，需先选出两个 不同 下标 i 和 j，其中 words[i] 是一个非空字符串，
接着将 words[i] 中的 任一 字符移动到 words[j] 中的 任一 位置上。
如果执行任意步操作可以使 words 中的每个字符串都相等，返回 true ；否则，返回 false 。
示例 1：输入：words = ["abc","aabc","bc"] 输出：true
解释：将 words[1] 中的第一个 'a' 移动到 words[2] 的最前面。
使 words[1] = "abc" 且 words[2] = "abc" 。
所有字符串都等于 "abc" ，所以返回 true 。
示例 2：输入：words = ["ab","a"] 输出：false
解释：执行操作无法使所有字符串都相等。
提示：1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成

解题思路

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

func makeEqual(words []string) bool {
	arr := [26]int{}
	n := len(words)
	for i := 0; i < n; i++ {
		for j := 0; j < len(words[i]); j++ {
			arr[int(words[i][j]-'a')]++
		}
	}
	for i := 0; i < 26; i++ {
		if arr[i]%n != 0 {
			return false
		}
	}
	return true
}

1801-1900-Medium¶

1801.积压订单中的订单总数(1)¶

题目

给你一个二维整数数组 orders ，其中每个 orders[i] = [pricei, amounti, orderTypei] 
表示有 amounti 笔类型为orderTypei 、价格为pricei 的订单。
订单类型 orderTypei 可以分为两种：
0 表示这是一批采购订单 buy
1 表示这是一批销售订单 sell
注意，orders[i] 表示一批共计 amounti 笔的独立订单，这些订单的价格和类型相同。
对于所有有效的 i ，由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。
存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时，会发生以下情况：
如果该订单是一笔采购订单 buy ，则可以查看积压订单中价格 最低 的销售订单 sell 。
如果该销售订单 sell 的价格 低于或等于 当前采购订单 buy 的价格，
则匹配并执行这两笔订单，并将销售订单 sell 从积压订单中删除。否则，采购订单 buy 将会添加到积压订单中。
反之亦然，如果该订单是一笔销售订单 sell ，则可以查看积压订单中价格 最高 的采购订单 buy 。
如果该采购订单 buy 的价格 高于或等于 当前销售订单 sell 的价格，
则匹配并执行这两笔订单，并将采购订单 buy 从积压订单中删除。否则，销售订单 sell 将会添加到积压订单中。
输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 109 + 7 取余的结果。
示例 1：输入：orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] 输出：6
解释：输入订单后会发生下述情况：
- 提交 5 笔采购订单，价格为 10 。没有销售订单，所以这 5 笔订单添加到积压订单中。
- 提交 2 笔销售订单，价格为 15 。没有采购订单的价格大于或等于 15 ，所以这 2 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 25 。没有采购订单的价格大于或等于 25 ，所以这 1 笔订单添加到积压订单中。
- 提交 4 笔采购订单，价格为 30 。前 2 笔采购订单与价格最低（价格为 15）的 2 笔销售订单匹配，
从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配，销售订单价格为 25 ，
从积压订单中删除这 1 笔销售订单。积压订单中不存在更多销售订单，所以第 4 笔采购订单需要添加到积压订单中。
最终，积压订单中有 5 笔价格为 10 的采购订单，和 1 笔价格为 30 的采购订单。
所以积压订单中的订单总数为 6 。
示例 2：输入：orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]] 输出：999999984
解释：输入订单后会发生下述情况：
- 提交 109 笔销售订单，价格为 7 。没有采购订单，所以这 109 笔订单添加到积压订单中。
- 提交 3 笔采购订单，价格为 15 。这些采购订单与价格最低（价格为 7 ）的 3 笔销售订单匹配，
从积压订单中删除这 3 笔销售订单。
- 提交 999999995 笔采购订单，价格为 5 。销售订单的最低价为 7 ，
所以这 999999995 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 5 。这笔销售订单与价格最高（价格为 5 ）的 1 笔采购订单匹配，
从积压订单中删除这 1 笔采购订单。
最终，积压订单中有 (1000000000-3) 笔价格为 7 的销售订单，和 (999999995-1) 笔价格为 5 的采购订单。
所以积压订单中的订单总数为 1999999991 ，等于 999999984 % (109 + 7) 。
提示：1 <= orders.length <= 105
orders[i].length == 3
1 <= pricei, amounti <= 109
orderTypei 为 0 或 1

解题思路

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

func getNumberOfBacklogOrders(orders [][]int) int {
	res := 0
	buyHeap := make(BuyHeap, 0)
	sellHeap := make(SellHeap, 0)
	heap.Init(&buyHeap)
	heap.Init(&sellHeap)
	for i := 0; i < len(orders); i++ {
		price := orders[i][0]
		count := orders[i][1]
		typeInt := orders[i][2]
		if typeInt == 1 { // sell
			for buyHeap.Len() > 0 {
				node := heap.Pop(&buyHeap).(Node)
				if node.price < price {
					heap.Push(&buyHeap, node)
					break
				}
				if node.count > count { // 数量大于
					node.count = node.count - count
					count = 0
					heap.Push(&buyHeap, node)
					break
				}
				count = count - node.count
			}
			if count > 0 {
				heap.Push(&sellHeap, Node{
					count: count,
					price: price,
				})
			}
		} else { // buy
			for sellHeap.Len() > 0 {
				node := heap.Pop(&sellHeap).(Node)
				if node.price > price {
					heap.Push(&sellHeap, node)
					break
				}
				if node.count > count { // 数量小于
					node.count = node.count - count
					count = 0
					heap.Push(&sellHeap, node)
					break
				}
				count = count - node.count
			}
			if count > 0 {
				heap.Push(&buyHeap, Node{
					count: count,
					price: price,
				})
			}
		}
	}
	for buyHeap.Len() > 0 {
		node := heap.Pop(&buyHeap).(Node)
		res = res + node.count
	}
	for sellHeap.Len() > 0 {
		node := heap.Pop(&sellHeap).(Node)
		res = res + node.count
	}
	return res % 1000000007
}

type Node struct {
	count int
	price int
}
type SellHeap []Node

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

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

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

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

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

type BuyHeap []Node

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

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

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

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

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

1802.有界数组中指定下标处的最大值(2)¶

题目

给你三个正整数 n、index 和 maxSum 。
你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
nums.length == n
nums[i] 是 正整数 ，其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被 最大化
返回你所构造的数组中的 nums[index] 。
注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。
示例 1：输入：n = 4, index = 2,  maxSum = 6 输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2：输入：n = 6, index = 1,  maxSum = 10 输出：3
提示：1 <= n <= maxSum <= 109
0 <= index < n

解题思路

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

func maxValue(n int, index int, maxSum int) int {
	if n == 1 {
		return maxSum
	}
	res := 1
	leftTotal, rightTotal := index, n-index-1
	left, right := 1, maxSum
	for left < right {
		mid := left + (right-left)/2
		l := getTotal(mid, leftTotal)
		r := getTotal(mid, rightTotal)
		if l+r+mid <= maxSum {
			left = mid + 1
			res = mid
		} else {
			right = mid
		}
	}
	return res
}

func getTotal(high int, total int) int {
	need := high - 1
	if need >= total {
		return total * (need + high - total) / 2
	}
	return need*(1+need)/2 + total - need
}

# 2
func maxValue(n int, index int, maxSum int) int {
	res := 1
	leftTotal, rightTotal := index, n-index-1
	left, right := 1, maxSum+1
	for left < right {
		mid := left + (right-left)/2
		l := getTotal(mid, leftTotal)
		r := getTotal(mid, rightTotal)
		if l+r+mid <= maxSum {
			left = mid + 1
			res = mid
		} else {
			right = mid
		}
	}
	return res
}

func getTotal(high int, total int) int {
	need := high - 1
	if need >= total {
		return total * (need + high - total) / 2
	}
	return need*(1+need)/2 + total - need
}

1806.还原排列的最少操作步数(3)¶

题目

给你一个偶数 n，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i（下标 从 0 开始 计数）。
一步操作中，你将创建一个新数组 arr ，对于每个 i ：
如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]
然后将 arr赋值给 perm 。
要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。
示例 1：输入：n = 2 输出：1
解释：最初，perm = [0,1]
第 1步操作后，perm = [0,1]
所以，仅需执行 1 步操作
示例 2：输入：n = 4 输出：2
解释：最初，perm = [0,1,2,3]
第 1步操作后，perm = [0,2,1,3]
第 2步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作
示例 3：输入：n = 6 输出：4
提示：2 <= n <= 1000
n是一个偶数

解题思路

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

func reinitializePermutation(n int) int {
	res := 0
	target := make([]int, n)
	perm := make([]int, n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		perm[i] = i
	}
	copy(target, perm)
	for {
		for i := 0; i < n; i++ {
			if i%2 == 0 {
				arr[i] = perm[i/2]
			} else {
				arr[i] = perm[n/2+(i-1)/2]
			}
		}
		res++
		if reflect.DeepEqual(target, arr) {
			break
		}
		copy(perm, arr)
	}
	return res
}

# 2
func reinitializePermutation(n int) int {
	res := 0
	target := make([]int, n)
	perm := make([]int, n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		perm[i] = i
	}
	copy(target, perm)
	for {
		for i := 0; i < n; i++ {
			if i%2 == 0 {
				arr[i] = perm[i/2]
			} else {
				arr[i] = perm[n/2+(i-1)/2]
			}
		}
		res++
		flag := true
		for i := 0; i < n; i++ {
			if arr[i] != target[i] {
				flag = false
				break
			}
		}
		if flag == true {
			break
		}
		copy(perm, arr)
	}
	return res
}

# 3
func reinitializePermutation(n int) int {
	res := 0
	target := 1
	// 反向思路，只考虑1的变换
	for {
		if target*2 < n {
			target = target * 2
		} else {
			target = target*2 + 1 - n
		}
		res++
		if target == 1 {
			break
		}
	}
	return res
}

1807.替换字符串中的括号内容(1)¶

题目

给你一个字符串s，它包含一些括号对，每个括号中包含一个 非空的键。
比方说，字符串"(name)is(age)yearsold"中，有两个括号对，分别包含键"name" 和"age"。
你知道许多键对应的值，这些关系由二维字符串数组knowledge表示，
其中knowledge[i] = [keyi, valuei]，表示键keyi对应的值为valuei。
你需要替换 所有的括号对。当你替换一个括号对，且它包含的键为keyi时，你需要：
将keyi和括号用对应的值valuei替换。
如果从 knowledge中无法得知某个键对应的值，你需要将keyi和括号用问号"?"替换（不需要引号）。
knowledge中每个键最多只会出现一次。s中不会有嵌套的括号。
请你返回替换 所有括号对后的结果字符串。
示例 1：输入：s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
输出："bobistwoyearsold"
解释：键 "name" 对应的值为 "bob" ，所以将 "(name)" 替换为 "bob" 。
键 "age" 对应的值为 "two" ，所以将 "(age)" 替换为 "two" 。
示例 2：输入：s = "hi(name)", knowledge = [["a","b"]] 输出："hi?"
解释：由于不知道键 "name" 对应的值，所以用 "?" 替换 "(name)" 。
示例 3：输入：s = "(a)(a)(a)aaa", knowledge = [["a","yes"]] 输出："yesyesyesaaa"
解释：相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ，所以将所有的 "(a)" 替换为 "yes" 。
注意，不在括号里的 "a" 不需要被替换。
示例 4：输入：s = "(a)(b)", knowledge = [["a","b"],["b","a"]] 输出："ba"
提示：1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s只包含小写英文字母和圆括号'('和')'。
s中每一个左圆括号'('都有对应的右圆括号')'。
s中每对括号内的键都不会为空。
s中不会有嵌套括号对。
keyi和valuei只包含小写英文字母。
knowledge中的keyi不会重复。

解题思路

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

func evaluate(s string, knowledge [][]string) string {
	m := make(map[string]string)
	for i := 0; i < len(knowledge); i++ {
		a, b := knowledge[i][0], knowledge[i][1]
		m[a] = b
	}
	res := ""
	left := -1
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left = i
		} else if s[i] == ')' {
			str := s[left+1 : i]
			if v, ok := m[str]; ok {
				res = res + v
			} else {
				res = res + "?"
			}
			left = -1
		} else if left == -1 {
			res = res + string(s[i])
		}
	}
	return res
}

1813.句子相似性III(1)¶

题目

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。
比方说，"Hello World"，"HELLO"，"hello world hello world"都是句子。
每个单词都 只包含大写和小写英文字母。
如果两个句子sentence1 和sentence2，
可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的。
比方说，sentence1 = "Hello my name is Jane" 且sentence2 = "Hello Jane"，
我们可以往 sentence2中"Hello" 和"Jane"之间插入"my name is"得到 sentence1。
给你两个句子sentence1 和sentence2，如果sentence1 和sentence2 是相似的，
请你返回true，否则返回false。
示例 1：输入：sentence1 = "My name is Haley", sentence2 = "My Haley" 输出：true
解释：可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ，得到 sentence1 。
示例 2：输入：sentence1 = "of", sentence2 = "A lot of words" 输出：false
解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。
示例 3：输入：sentence1 = "Eating right now", sentence2 = "Eating" 输出：true
解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。
示例 4：输入：sentence1 = "Luky", sentence2 = "Lucccky" 输出：false
提示：1 <= sentence1.length, sentence2.length <= 100
sentence1和sentence2都只包含大小写英文字母和空格。
sentence1和sentence2中的单词都只由单个空格隔开。

解题思路

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

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
	if len(sentence1) > len(sentence2) { // 交换保证 1 < 2
		sentence1, sentence2 = sentence2, sentence1
	}
	// 4种情况：
	// 1、全等： AB = AB
	// 2、头部等于：AXX = A
	// 3、尾部等于：XXA = A
	// 4、首尾相等：AXXB = AB
	a := strings.Fields(sentence1)
	b := strings.Fields(sentence2)
	i, j := 0, 0
	for i < len(a) && a[i] == b[i] { // 从开头统计
		i++
	}
	for 0 <= len(a)-1-j && a[len(a)-1-j] == b[len(b)-1-j] { // 从结尾统计
		j++
	}
	return i+j >= len(a) // 大于等于较短的长度
}

1814.统计一个数组中好对子的数目(1)¶

题目

给你一个数组nums，数组中只包含非负整数。定义rev(x)的值为将整数x各个数字位反转得到的结果。
比方说rev(123) = 321，rev(120) = 21。我们称满足下面条件的下标对(i, j) 是好的：
0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
请你返回好下标对的数目。由于结果可能会很大，请将结果对109 + 7取余后返回。
示例 1：输入：nums = [42,11,1,97] 输出：2
解释：两个坐标对为：
 - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。
示例 2：输入：nums = [13,10,35,24,76] 输出：4
提示：1 <= nums.length <= 105
0 <= nums[i] <= 109

解题思路

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

func countNicePairs(nums []int) int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]-reverse(nums[i])]++
	}
	res := 0
	for _, v := range m {
		res = (res + v*(v-1)/2) % 1000000007
	}
	return res
}

func reverse(num int) int {
	res := 0
	for num > 0 {
		res = res*10 + num%10
		num = num / 10
	}
	return res
}

1817.查找用户活跃分钟数(1)¶

题目

给你用户在 LeetCode 的操作日志，和一个整数 k 。日志用一个二维整数数组 logs 表示，
其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。
多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作 。
指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数 。
即使一分钟内执行多个操作，也只能按一分钟计数。
请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ，
对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。
返回上面描述的答案数组 answer 。
示例 1：输入：logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5 输出：[0,2,0,0,0]
解释：
ID=0 的用户执行操作的分钟分别是：5 、2 和 5 。因此，该用户的用户活跃分钟数为 2（分钟 5 只计数一次）
ID=1 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
2 个用户的用户活跃分钟数都是 2 ，answer[2] 为 2 ，其余 answer[j] 的值都是 0
示例 2：输入：logs = [[1,1],[2,2],[2,3]], k = 4 输出：[1,1,0,0]
解释： ID=1 的用户仅在分钟 1 执行单个操作。因此，该用户的用户活跃分钟数为 1
ID=2 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
1 个用户的用户活跃分钟数是 1 ，1 个用户的用户活跃分钟数是 2 
因此，answer[1] = 1 ，answer[2] = 1 ，其余的值都是 0
提示：1 <= logs.length <= 104
0 <= IDi <= 109
1 <= timei <= 105
k 的取值范围是 [用户的最大用户活跃分钟数, 105]

解题思路

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

func findingUsersActiveMinutes(logs [][]int, k int) []int {
	m := make(map[int]map[int]int)
	for i := 0; i < len(logs); i++{
		a, b := logs[i][0], logs[i][1]
		if _, ok := m[a]; ok == false{
			m[a] = make(map[int]int)
		}
		m[a][b]++
	}
	res := make([]int, k)
	for _, v := range m{
		value := len(v)
		res[value-1]++
	}
	return res
}

1818.绝对差值和(1)¶

题目

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 
总和（下标从 0 开始）。
你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。
因为答案可能很大，所以需要对 109 + 7 取余 后返回。
|x| 定义为：如果 x >= 0 ，值为 x ，或者
如果 x <= 0 ，值为 -x
示例 1：输入：nums1 = [1,7,5], nums2 = [2,3,5] 输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3
示例 2：输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] 输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0
示例 3：输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4] 输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
提示：n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105

解题思路

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

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
	arr := make([]int, len(nums1))
	sum := 0
	for i := 0; i < len(nums1); i++ {
		arr[i] = nums1[i]
		sum = (sum + abs(nums1[i]-nums2[i])) % 1000000007
	}
	sort.Ints(arr)
	maxValue := 0
	for i := 0; i < len(arr); i++ {
		if nums1[i] == nums2[i] {
			continue
		}
		b := nums2[i]
		target := search(arr, b)
		maxValue = max(maxValue, abs(nums1[i]-b)-abs(target-b))
	}
	return (sum - maxValue+ 1000000007) % 1000000007
}

func search(arr []int, target int) int {
	res := 0
	if arr[0] > target {
		return arr[0]
	}
	if arr[len(arr)-1] < target {
		return arr[len(arr)-1]
	}
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		if target < arr[mid] {
			right = mid - 1
			if abs(res-target) > abs(target-arr[mid]) {
				res = arr[mid]
			}
		} else if target == arr[mid] {
			return target
		} else if target > arr[mid] {
			left = mid + 1
			if abs(res-target) > abs(target-arr[mid]) {
				res = arr[mid]
			}
		}
	}
	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
}

1823.找出游戏的获胜者(2)¶

题目

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。
确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，
从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：
从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。
逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。
示例 1：输入：n = 5, k = 2 输出：3
解释：游戏运行步骤如下：
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
示例 2：输入：n = 6, k = 5 输出：1
解释：小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。
提示：1 <= k <= n <= 500

解题思路

No.	思路	时间复杂度	空间复杂度
01	约瑟夫环	O(n)	O(1)
02	模拟	O(n^2)	O(n)

func findTheWinner(n int, k int) int {
	idx := 0
	for i := 2; i <= n; i++ {
		idx = (idx + k) % i
	}
	return idx + 1
}

# 2
func findTheWinner(n int, k int) int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = i
	}
	last := 0
	for len(arr) > 1 {
		index := (last + k - 1) % len(arr)
		arr = remove(arr, index)
		last = index
	}
	return arr[0] + 1
}

func remove(arr []int, index int) []int {
	if index == 0 {
		return arr[1:]
	}
	if index == len(arr)-1 {
		return arr[:len(arr)-1]
	}
	return append(arr[:index], arr[index+1:]...)
}

1824.最少侧跳次数(2)¶

题目

给你一个长度为n的3 跑道道路，它总共包含n + 1个点，编号为0到n。
一只青蛙从0号点第二条跑道出发，它想要跳到点n处。然而道路上可能有一些障碍。
给你一个长度为 n + 1的数组obstacles，其中obstacles[i]（取值范围从 0 到 3）
表示在点 i处的obstacles[i]跑道上有一个障碍。
如果obstacles[i] == 0，那么点i处没有障碍。任何一个点的三条跑道中最多有一个障碍。
比方说，如果obstacles[2] == 1，那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i跳到点 i + 1且跑道不变的前提是点 i + 1的同一跑道上没有障碍。
为了躲避障碍，这只青蛙也可以在同一个点处侧跳到 另外一条跑道（这两条跑道可以不相邻），
但前提是跳过去的跑道该点处没有障碍。
比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2出发，并想到达点 n处的 任一跑道 ，请你返回 最少侧跳次数。
注意：点 0处和点 n处的任一跑道都不会有障碍。
示例 1：输入：obstacles = [0,1,2,3,0] 输出：2 
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
示例 2：输入：obstacles = [0,1,1,3,3,0] 输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
示例 3：输入：obstacles = [0,2,1,0,3,0] 输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。
提示：obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

解题思路

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

func minSideJumps(obstacles []int) int {
	n := len(obstacles)
	dp := make([][3]int, n) // dp[i][j] 到达第i，下标为j的跑道最少次数
	for i := 0; i < n; i++ {
		for j := 0; j < 3; j++ {
			dp[i][j] = math.MaxInt32 / 10
		}
	}
	dp[0][0] = 1
	dp[0][1] = 0
	dp[0][2] = 1
	for i := 1; i < n; i++ {
		// 当前位置无障碍物，继承之前的次数，次数不变
		if obstacles[i] != 1 {
			dp[i][0] = dp[i-1][0]
		}
		if obstacles[i] != 2 {
			dp[i][1] = dp[i-1][1]
		}
		if obstacles[i] != 3 {
			dp[i][2] = dp[i-1][2]
		}
		// 从其它位置跳过来
		if obstacles[i] != 1 {
			dp[i][0] = min(dp[i][0], min(dp[i][1], dp[i][2])+1)
		}
		if obstacles[i] != 2 {
			dp[i][1] = min(dp[i][1], min(dp[i][0], dp[i][2])+1)
		}
		if obstacles[i] != 3 {
			dp[i][2] = min(dp[i][2], min(dp[i][0], dp[i][1])+1)
		}
	}
	return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))
}

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

# 2
func minSideJumps(obstacles []int) int {
	n := len(obstacles)
	dp := make([][3]int, n) // dp[i][j] 到达第i，下标为j的跑道最少次数
	for i := 0; i < n; i++ {
		for j := 0; j < 3; j++ {
			dp[i][j] = math.MaxInt32 / 10
		}
	}
	dp[0][0] = 1
	dp[0][1] = 0
	dp[0][2] = 1
	for i := 1; i < n; i++ {
		if obstacles[i] == 0 { // 没有障碍物，从其它2条道跳过来
			dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])+1)
			dp[i][1] = min(dp[i-1][1], min(dp[i-1][0], dp[i-1][2])+1)
			dp[i][2] = min(dp[i-1][2], min(dp[i-1][0], dp[i-1][1])+1)
		} else {
			a := obstacles[i] - 1
			b := (obstacles[i]) % 3
			c := (obstacles[i] + 1) % 3
			dp[i][a] = math.MaxInt32 / 10 // 不可达
			dp[i][b] = min(dp[i-1][b], dp[i-1][c]+1)
			dp[i][c] = min(dp[i-1][c], dp[i-1][b]+1)
		}

	}
	return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))
}

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

1828.统计一个圆中点的数目(1)¶

题目

给你一个数组points，其中points[i] = [xi, yi]，表示第i个点在二维平面上的坐标。
多个点可能会有 相同的坐标。
同时给你一个数组queries，其中queries[j] = [xj, yj, rj]，
表示一个圆心在(xj, yj)且半径为rj的圆。
对于每一个查询queries[j]，计算在第 j个圆 内点的数目。
如果一个点在圆的 边界上，我们同样认为它在圆内。
请你返回一个数组answer，其中answer[j]是第j个查询的答案。
示例 1： 输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。
示例 2：输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], 
queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]] 输出：[2,3,2,4]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。
提示：1 <= points.length <= 500
points[i].length == 2
0 <= xi, yi <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= xj, yj <= 500
1 <= rj <= 500
所有的坐标都是整数。

解题思路

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

func countPoints(points [][]int, queries [][]int) []int {
	n := len(queries)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		count := 0
		for j := 0; j < len(points); j++ {
			if judge(queries[i], points[j]) == true {
				count++
			}
		}
		res[i] = count
	}
	return res
}

func judge(query []int, point []int) bool {
	x, y, r := query[0], query[1], query[2]
	x1, y1 := point[0], point[1]
	return (x-x1)*(x-x1)+(y-y1)*(y-y1) <= r*r
}

1829.每个查询的最大异或值(2)¶

题目

给你一个 有序数组nums，它由n个非负整数组成，同时给你一个整数maximumBit。
你需要执行以下查询 n次：
找到一个非负整数k < 2maximumBit，
使得nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k的结果 最大化。
k是第 i个查询的答案。
从当前数组nums删除最后一个元素。
请你返回一个数组answer，其中answer[i]是第i个查询的结果。
示例 1：输入：nums = [0,1,1,3], maximumBit = 2 输出：[0,3,2,3]
解释：查询的答案如下：
第一个查询：nums = [0,1,1,3]，k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二个查询：nums = [0,1,1]，k = 3，因为 0 XOR 1 XOR 1 XOR 3 = 3 。
第三个查询：nums = [0,1]，k = 2，因为 0 XOR 1 XOR 2 = 3 。
第四个查询：nums = [0]，k = 3，因为 0 XOR 3 = 3 。
示例 2：输入：nums = [2,3,4,7], maximumBit = 3 输出：[5,2,6,5]
解释：查询的答案如下：
第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。
第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。
第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。
示例 3：输入：nums = [0,1,2,2,5,7], maximumBit = 3 输出：[4,3,6,4,6,7]
提示：nums.length == n
1 <= n <= 105
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums中的数字已经按升序排好序。

解题思路

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

func getMaximumXor(nums []int, maximumBit int) []int {
	n := len(nums)
	res := make([]int, n)
	temp := nums[0]
	res[n-1] = temp
	for i := 1; i < n; i++ {
		temp = temp ^ nums[i]
		res[n-1-i] = temp
	}
	target := 1<<maximumBit - 1
	for i := 0; i < n; i++ {
		res[i] = res[i] ^ target
	}
	return res
}

# 2
func getMaximumXor(nums []int, maximumBit int) []int {
	n := len(nums)
	res := make([]int, 0)
	temp := nums[0]
	for i := 1; i < n; i++ {
		temp = temp ^ nums[i]
	}
	target := 1<<maximumBit - 1
	for i := n - 1; i >= 0; i-- {
		res = append(res, temp^target)
		temp = temp ^ nums[i]
	}
	return res
}

1833.雪糕的最大数量(1)¶

题目

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。
Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
注意：Tony 可以按任意顺序购买雪糕。
示例 1：输入：costs = [1,3,2,4,1], coins = 7 输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7
示例 2：输入：costs = [10,6,8,7,7,8], coins = 5 输出：0
解释：Tony 没有足够的钱买任何一支雪糕。
示例 3：输入：costs = [1,6,3,1,2,5], coins = 20 输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。
提示：costs.length == n
1 <= n <= 105
1 <= costs[i] <= 105
1 <= coins <= 108

解题思路

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

func maxIceCream(costs []int, coins int) int {
	sort.Ints(costs)
	for i := 0; i < len(costs); i++ {
		if costs[i] <= coins {
			coins = coins - costs[i]
		} else {
			return i
		}
	}
	return len(costs)
}

1834.单线程CPU(1)¶

题目

给你一个二维数组 tasks ，用于表示 n项从 0 到 n - 1 编号的任务。
其中 tasks[i] = [enqueueTimei, processingTimei] 意味着
第 i项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。
如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
CPU 可以在完成一项任务后，立即开始执行一项新任务。
返回 CPU 处理任务的顺序。
示例 1：输入：tasks = [[1,2],[2,4],[3,2],[4,1]] 输出：[0,2,3,1]
解释：事件按下述流程运行： 
- time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
- 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
- time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
- time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
- 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
- time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
- time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
- time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
- time = 10 ，CPU 完成任务 1 并进入空闲状态
示例 2：输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] 输出：[4,3,2,0,1]
解释：事件按下述流程运行： 
- time = 7 ，所有任务同时进入任务队列，可执行任务项  = {0,1,2,3,4}
- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
- time = 40 ，CPU 完成任务 1 并进入空闲状态
提示：tasks.length == n
1 <= n <= 105
1 <= enqueueTimei, processingTimei <= 109

解题思路

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

func getOrder(tasks [][]int) []int {
	n := len(tasks)
	res := make([]int, 0)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			Id:             i,
			StartTime:      tasks[i][0],
			ProcessingTime: tasks[i][1],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].StartTime < arr[j].StartTime
	})
	nodeHeap := make(NodeHeap, 0)
	heap.Init(&nodeHeap)
	curTime := 0
	cur := 0
	for i := 0; i < n; i++ { // 每次处理1个任务
		if nodeHeap.Len() == 0 { // 空任务
			curTime = max(curTime, tasks[arr[cur].Id][0]) // 时间移动
		}
		for ; cur < n && arr[cur].StartTime <= curTime; cur++ { // 加入优先队列：将小于等于时间戳的任务加入堆
			heap.Push(&nodeHeap, arr[cur])
		}
		node := heap.Pop(&nodeHeap).(Node)      // 选择任务：选择处理时间小的任务
		curTime = curTime + node.ProcessingTime // 时间处理
		res = append(res, node.Id)
	}
	return res
}

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

type Node struct {
	Id             int
	StartTime      int
	ProcessingTime int
}

type NodeHeap []Node

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

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

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
}

1838.最高频元素的频数(3)¶

题目

元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，
并将该下标对应元素的值增加 1 。
执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。
示例 1：输入：nums = [1,2,4], k = 5 输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。
示例 2：输入：nums = [1,4,8,13], k = 5 输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。
示例 3：输入：nums = [3,9,6], k = 2 输出：1
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 105

解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+双指针	O(nlog(n))	O(n)
02	排序+双指针	O(nlog(n))	O(1)
03	前缀和+内置函数	O(nlog(n))	O(n)

func maxFrequency(nums []int, k int) int {
	n := len(nums)
	sort.Ints(nums)
	arr := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	res := 1
	i := 0
	for j := 0; j < n; j++ {
		for nums[j]*(j-i)-(arr[j]-arr[i]) > k {
			i++
		}
		if j-i+1 > res {
			res = j - i + 1
		}
	}
	return res
}

# 2
func maxFrequency(nums []int, k int) int {
	n := len(nums)
	sort.Ints(nums)
	res := 1
	total := 0
	i := 0
	for j := 1; j < n; j++ {
		total = total + (nums[j]-nums[j-1])*(j-i) // 累加
		for total > k {
			total = total - (nums[j] - nums[i]) // 不满足，要减去
			i++
		}
		if j-i+1 > res {
			res = j - i + 1
		}
	}
	return res
}

# 3
func maxFrequency(nums []int, k int) int {
	n := len(nums)
	sort.Ints(nums)
	arr := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	res := 1
	for j := 0; j < n; j++ {
		i := sort.Search(j, func(i int) bool {
			return nums[j]*(j-i)-(arr[j]-arr[i]) <= k
		})
		if j-i+1 > res {
			res = j - i + 1
		}
	}
	return res
}

1839.所有元音按顺序排布的最长子字符串(1)¶

题目

当一个字符串满足如下条件时，我们称它是 美丽的：
所有 5 个英文元音字母（'a'，'e'，'i'，'o'，'u'）都必须至少出现一次。
这些元音字母的顺序都必须按照 字典序升序排布（也就是说所有的 'a'都在 'e'前面，
所有的 'e'都在 'i'前面，以此类推）
比方说，字符串"aeiou" 和"aaaaaaeiiiioou"都是 美丽的，
但是"uaeio"，"aeoiu"和"aaaeeeooo"不是美丽的。
给你一个只包含英文元音字母的字符串word，请你返回word 中 最长美丽子字符串的长度。
如果不存在这样的子字符串，请返回 0。
子字符串 是字符串中一个连续的字符序列。
示例 1：输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" 输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。
示例 2：输入：word = "aeeeiiiioooauuuaeiou" 输出：5
解释：最长子字符串是 "aeiou" ，长度为 5 。
示例 3：输入：word = "a" 输出：0
解释：没有美丽子字符串，所以返回 0 。
提示：1 <= word.length <= 5 * 105
word只包含字符'a'，'e'，'i'，'o'和'u'。

解题思路

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

func longestBeautifulSubstring(word string) int {
	res := 0
	count := 1
	i := 0
	for j := 1; j < len(word); j++ { // 题目保证了全是目标元素，而且顺序是有序的
		if word[j] < word[j-1] { // 大小不对，窗口右移，重新计数
			i = j
			count = 1
		} else if word[j] > word[j-1] {
			count++
		}
		if count == 5 { // 长度为5
			res = max(res, j-i+1)
		}
	}
	return res
}

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

1845.座位预约管理系统(1)¶

题目

请你设计一个管理 n个座位预约的系统，座位编号从1到n。
请你实现SeatManager类：
SeatManager(int n)初始化一个SeatManager对象，它管理从 1到 n编号的n个座位。所有座位初始都是可预约的。
int reserve()返回可以预约座位的最小编号，此座位变为不可预约。
void unreserve(int seatNumber)将给定编号seatNumber对应的座位变成可以预约。
示例 1：输入：["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", 
"reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
输出： [null, 1, 2, null, 2, 3, 4, 5, null]
解释：
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5 个座位。
seatManager.reserve();    // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.reserve();    // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
seatManager.reserve();    // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
seatManager.reserve();    // 唯一可以预约的是座位 5 ，所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。
提示：1 <= n <= 105
1 <= seatNumber <= n
每一次对reserve的调用，题目保证至少存在一个可以预约的座位。
每一次对unreserve的调用，题目保证seatNumber在调用函数前都是被预约状态。
对reserve 和unreserve的调用总共不超过105次。

解题思路

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

type SeatManager struct {
	intHeap IntHeap
}

func Constructor(n int) SeatManager {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 1; i <= n; i++ {
		heap.Push(&intHeap, i)
	}
	return SeatManager{intHeap: intHeap}
}

func (this *SeatManager) Reserve() int {
	top := heap.Pop(&this.intHeap).(int)
	return top
}

func (this *SeatManager) Unreserve(seatNumber int) {
	heap.Push(&this.intHeap, seatNumber)
}

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
}

1846.减小和重新排列数组后的最大元素(2)¶

题目

给你一个正整数数组arr。请你对 arr执行一些操作（也可以不进行任何操作），使得数组满足以下条件：
arr中 第一个元素必须为1。
任意相邻两个元素的差的绝对值 小于等于1，也就是说，对于任意的 1 <= i < arr.length（数组下标从 0 开始），
都满足abs(arr[i] - arr[i - 1]) <= 1。abs(x)为x的绝对值。
你可以执行以下 2 种操作任意次：
减小 arr中任意元素的值，使其变为一个 更小的正整数。
重新排列arr中的元素，你可以以任意顺序重新排列。
请你返回执行以上操作后，在满足前文所述的条件下，arr中可能的 最大值。
示例 1：输入：arr = [2,2,1,2,1] 输出：2
解释：我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。
示例 2：输入：arr = [100,1,1000] 输出：3
解释：一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。
示例 3：输入：arr = [1,2,3,4,5] 输出：5
解释：数组已经满足所有条件，最大元素为 5 。
提示：1 <= arr.length <= 105
1 <= arr[i] <= 109

解题思路

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

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

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

# 2
func maximumElementAfterDecrementingAndRearranging(arr []int) int {
	sort.Ints(arr)
	res := 0
	for i := 0; i < len(arr); i++ {
		if res < arr[i] {
			res++
		}
	}
	return res
}

1849.将字符串拆分为递减的连续值(3)¶

题目

给你一个仅由数字组成的字符串 s 。
请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的 数值 按 降序 排列，且每两个 相邻子字符串 的数值之 差 等于 1 。
例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为 [90,89] 。
这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。
然而，所有这些拆分方法都不可行，因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。
如果可以按要求拆分 s ，返回 true ；否则，返回 false 。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "1234" 输出：false
解释：不存在拆分 s 的可行方法。
示例 2：输入：s = "050043" 输出：true
解释：s 可以拆分为 ["05", "004", "3"] ，对应数值为 [5,4,3] 。
满足按降序排列，且相邻值相差 1 。
示例 3：输入：s = "9080701" 输出：false
解释：不存在拆分 s 的可行方法。
示例 4：输入：s = "10009998" 输出：true
解释：s 可以拆分为 ["100", "099", "98"] ，对应数值为 [100,99,98] 。
满足按降序排列，且相邻值相差 1 。
提示：1 <= s.length <= 20
s 仅由数字组成

解题思路

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

func splitString(s string) bool {
	for i := 0; i < len(s); i++ {
		value, _ := strconv.Atoi(s[:i+1])
		if s[i+1:] != "" && dfs(s[i+1:], value-1) == true {
			return true
		}
	}
	return false
}

func dfs(s string, target int) bool {
	value, _ := strconv.Atoi(s)
	if s == "" || value == target {
		return true
	}
	for i := 0; i < len(s); i++ {
		v, _ := strconv.Atoi(s[:i+1])
		if v < target {
			continue
		}
		if v > target {
			return false
		}
		if v == target {
			if dfs(s[i+1:], target-1) == true {
				return true
			}
			return false
		}
	}
	return false
}

# 2
func splitString(s string) bool {
	return dfs([]byte(s), 0, 0, 0)
}

func dfs(arr []byte, index int, count int, target int) bool {
	if index == len(arr) {
		return count > 1
	}
	value := 0
	for i := index; i < len(arr); i++ {
		value = value*10 + int(arr[i]-'0')
		if count == 0 || value == target-1 {
			if dfs(arr, i+1, count+1, value) == true {
				return true
			}
		}
	}
	return false
}

# 3
func splitString(s string) bool {
	n := len(s)
	for i := 0; i < n-1; i++ {
		a, _ := strconv.Atoi(s[0 : i+1])
		index := i
		for j := i + 1; j < n; j++ {
			b, _ := strconv.Atoi(s[index+1 : j+1])
			c, _ := strconv.Atoi(s[index+1 : n])
			if c == a-1 {
				return true
			}
			if b == a-1 {
				index = j
				a = b
				c, _ := strconv.Atoi(s[index+1 : n])
				if c == a-1 {
					return true
				}
			} else if b > a-1 {
				break
			}
		}
	}
	return false
}

1850.邻位交换的最小次数(1)¶

题目

给你一个表示大整数的字符串 num ，和一个整数 k 。
如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。
可能存在很多妙数，但是只需要关注 值最小 的那些。
例如，num = "5489355142" ：
第 1 个最小妙数是 "5489355214"
第 2 个最小妙数是 "5489355241"
第 3 个最小妙数是 "5489355412"
第 4 个最小妙数是 "5489355421"
返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。
测试用例是按存在第 k 个最小妙数而生成的。
示例 1：输入：num = "5489355142", k = 4 输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
- 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
- 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"
示例 2：输入：num = "11112", k = 4 输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："11112" -> "11121"
- 交换下标 2 和下标 3 对应的位："11121" -> "11211"
- 交换下标 1 和下标 2 对应的位："11211" -> "12111"
- 交换下标 0 和下标 1 对应的位："12111" -> "21111"
示例 3：输入：num = "00123", k = 1 输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："00123" -> "00132"
提示：2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成

解题思路

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

func getMinSwaps(num string, k int) int {
	target := []byte(num)
	n := len(target)
	res := 0
	for i := 1; i <= k; i++ { // 求接下来的第k个排列
		nextPermutation(target)
	}
	// 统计交换次数
	arr := []byte(num)
	for i := 0; i < n; i++ {
		if arr[i] != target[i] {
			for j := i + 1; j < n; j++ {
				if arr[j] == target[i] { // 找到交换
					for k := j - 1; k >= i; k-- { // 把arr[j]交换到前面去
						arr[k], arr[k+1] = arr[k+1], arr[k]
						res++
					}
					break
				}
			}
		}
	}
	return res
}

// leetcode31.下一个排列
func nextPermutation(nums []byte) {
	n := len(nums)
	left := n - 2
	// 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
	for left >= 0 && nums[left] >= nums[left+1] {
		left--
	}
	if left >= 0 { // 存在升序的情况
		right := n - 1
		// 从后往前，找到第一个大于目标值的数，如6>5，然后交换
		for right >= 0 && nums[right] <= nums[left] {
			right--
		}
		nums[left], nums[right] = nums[right], nums[left]
	}
	reverse(nums, left+1, n-1)
}

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

1855.下标对中的最大距离(3)¶

题目

给你两个 非递增 的整数数组 nums1和 nums2，数组下标均 从 0 开始 计数。
下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i。
返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。
一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。
示例 1：输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] 输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。
示例 2：输入：nums1 = [2,2,2], nums2 = [10,10,1] 输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。
示例 3：输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25] 输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。
示例 4：输入：nums1 = [5,4], nums2 = [3,2] 输出：0
解释：不存在有效下标对，所以返回 0 。
提示：1 <= nums1.length <= 105
1 <= nums2.length <= 105
1 <= nums1[i], nums2[j] <= 105
nums1 和 nums2 都是 非递增 数组

解题思路

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

func maxDistance(nums1 []int, nums2 []int) int {
	res := 0
	i := 0
	for j := 0; j < len(nums2); j++ {
		for i < len(nums1) && nums2[j] < nums1[i] {
			i++
		}
		if i < len(nums1) {
			if j-i > res {
				res = j - i
			}
		}
	}
	return res
}

# 2
func maxDistance(nums1 []int, nums2 []int) int {
	res := 0
	for j := 0; j < len(nums2); j++ {
		n := min(j, len(nums1))
		i := sort.Search(n, func(i int) bool {
			return nums1[i] <= nums2[j]
		})
		if i < n {
			if j-i > res {
				res = j - i
			}
		}
	}
	return res
}

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

# 3
func maxDistance(nums1 []int, nums2 []int) int {
	res := 0
	j := 0
	for i := 0; i < len(nums1); i++ {
		for j < len(nums2) && nums1[i] <= nums2[j] {
			j++
		}
		if j-i-1 > res {
			res = j - i - 1
		}
	}
	return res
}

1856.子数组最小乘积的最大值(2)¶

题目

一个数组的 最小乘积定义为这个数组中 最小值乘以数组的 和。
比方说，数组[3,2,5]（最小值是2）的最小乘积为2 * (3+2+5) = 2 * 10 = 20。
给你一个正整数数组nums，请你返回nums任意非空子数组的最小乘积的最大值。
由于答案可能很大，请你返回答案对109 + 7取余的结果。
请注意，最小乘积的最大值考虑的是取余操作 之前的结果。
题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数保存。
子数组定义为一个数组的 连续部分。
示例 1：输入：nums = [1,2,3,2] 输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。
示例 2：输入：nums = [2,3,3,1,2] 输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。
示例 3：输入：nums = [3,1,5,6,4,2] 输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 107

解题思路

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

var mod = 1000000007

func maxSumMinProduct(nums []int) int {
	res := 0
	n := len(nums)
	arr := make([]int, n+1) // 前缀和
	for i := 1; i <= n; i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	left := make([]int, n)  // 左侧最近的严格小于nums[i]的元素下标
	right := make([]int, n) // 右侧最近的小于等于nums[i]的元素下标
	for i := 0; i < n; i++ {
		left[i] = 0      // 默认是最左边
		right[i] = n - 1 // 默认是最右边
	}
	stack := make([]int, 0) // 单调递减栈
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			right[stack[len(stack)-1]] = i - 1
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 {
			left[i] = stack[len(stack)-1] + 1
		}
		stack = append(stack, i)
	}
	for i := 0; i < n; i++ {
		target := (arr[right[i]+1] - arr[left[i]]) * nums[i]
		res = max(res, target)
	}
	return res % mod
}

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

# 2
var mod = 1000000007

func maxSumMinProduct(nums []int) int {
	res := 0
	n := len(nums)
	arr := make([]int, n+1) // 前缀和
	for i := 1; i <= n; i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	left, right := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		left[i] = -1 // 默认是最左边
		right[i] = n // 默认是最右边
	}
	stack := make([]int, 0) // 双栈：leetcode 84.柱状图中最大的矩形
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
			right[stack[len(stack)-1]] = i
			stack = 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] {
			left[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i := 0; i < n; i++ {
		target := (arr[right[i]] - arr[left[i]+1]) * nums[i]
		res = max(res, target)
	}
	return res % mod
}

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

1860.增长的内存泄露(2)¶

题目

给你两个整数memory1 和memory2分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。
在第i秒（秒数从 1 开始），有 i位内存被分配到剩余内存较多的内存条（如果两者一样多，则分配到第一个内存条）。
如果两者剩余内存都不足 i位，那么程序将 意外退出。
请你返回一个数组，包含 [crashTime, memory1crash, memory2crash]，
其中crashTime是程序意外退出的时间（单位为秒），memory1crash 和memory2crash分别是两个内存条最后剩余内存的位数。
示例 1：输入：memory1 = 2, memory2 = 2 输出：[3,1,0]
解释：内存分配如下：
- 第 1 秒，内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
- 第 3 秒，程序意外退出，两个内存条分别有 1 位和 0 位剩余可用内存。
示例 2：输入：memory1 = 8, memory2 = 11 输出：[6,0,4]
解释：内存分配如下：
- 第 1 秒，内存条 2 被占用 1 位内存，内存条 2 现在有 10 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存，内存条 2 现在有 8 位剩余可用内存。
- 第 3 秒，内存条 1 被占用 3 位内存，内存条 1 现在有 5 位剩余可用内存。
- 第 4 秒，内存条 2 被占用 4 位内存，内存条 2 现在有 4 位剩余可用内存。
- 第 5 秒，内存条 1 被占用 5 位内存，内存条 1 现在有 0 位剩余可用内存。
- 第 6 秒，程序意外退出，两个内存条分别有 0 位和 4 位剩余可用内存。
提示：0 <= memory1, memory2 <= 231 - 1

解题思路

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

func memLeak(memory1 int, memory2 int) []int {
	i := 1
	for {
		if i <= memory1 || i <= memory2 {
			if memory1 < memory2 {
				memory2 = memory2 - i
			} else {
				memory1 = memory1 - i
			}
		} else {
			break
		}
		i++
	}
	return []int{i, memory1, memory2}
}

# 2
func memLeak(memory1 int, memory2 int) []int {
	i := 1
	for ; i <= memory1 || i <= memory2; i++ {
		if memory1 < memory2 {
			memory2 = memory2 - i
		} else {
			memory1 = memory1 - i
		}
	}
	return []int{i, memory1, memory2}
}

1861.旋转盒子(3)¶

题目

给你一个m x n的字符矩阵box，它表示一个箱子的侧视图。箱子的每一个格子可能为：
'#'表示石头
'*'表示固定的障碍物
'.'表示空位置
这个箱子被 顺时针旋转 90 度，由于重力原因，部分石头的位置会发生改变。
每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。
重力 不会影响障碍物的位置，同时箱子旋转不会产生惯性，也就是说石头的水平位置不会发生改变。
题目保证初始时box中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。
请你返回一个n x m的矩阵，表示按照上述旋转后，箱子内的结果。
示例 1：输入：box = [["#",".","#"]]
输出：[["."],
     ["#"],
     ["#"]]
示例 2：输入：box = [["#",".","*","."],
           ["#","#","*","."]]
输出：[["#","."],
     ["#","#"],
     ["*","*"],
     [".","."]]
示例 3：输入：box = [["#","#","*",".","*","."],
           ["#","#","#","*",".","."],
           ["#","#","#",".","#","."]]
输出：[[".","#","#"],
     [".","#","#"],
     ["#","#","*"],
     ["#","*","."],
     ["#",".","*"],
     ["#",".","."]]
提示：m == box.length
n == box[i].length
1 <= m, n <= 500
box[i][j]只可能是'#'，'*'或者'.'。

解题思路

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

func rotateTheBox(box [][]byte) [][]byte {
	n, m := len(box), len(box[0])
	res := make([][]byte, m)
	for i := 0; i < m; i++ {
		res[i] = make([]byte, n)
		for j := 0; j < n; j++ {
			res[i][j] = '.'
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			count := 0 // 统计一行中#的个数
			for ; j < m && box[i][j] != '*'; j++ {
				if box[i][j] == '#' {
					count++
				}
			}
			if j < m {
				res[j][n-1-i] = '*' // 填充*
			}
			// 移动# => 填充#
			for k := j - 1; count > 0; k-- {
				res[k][n-1-i] = '#'
				count--
			}
		}
	}
	return res
}

# 2
func rotateTheBox(box [][]byte) [][]byte {
	n, m := len(box), len(box[0])
	for i := 0; i < n; i++ {
		queue := make([]int, 0)
		for j := m - 1; j >= 0; j-- {
			if box[i][j] == '*' {
				queue = make([]int, 0) // 维护可移动的y坐标
			} else if box[i][j] == '#' {
				if len(queue) > 0 { // 石头落下
					first := queue[0]        // 最右边能落下的位置
					queue = queue[1:]        // 退出队列
					box[i][first] = '#'      // 落下
					box[i][j] = '.'          // 原位置为空
					queue = append(queue, j) // 置空后进入队列
				}
			} else {
				queue = append(queue, j)
			}
		}
	}
	res := make([][]byte, m)
	for i := 0; i < m; i++ {
		res[i] = make([]byte, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			res[j][n-1-i] = box[i][j]
		}
	}
	return res
}

# 3
func rotateTheBox(box [][]byte) [][]byte {
	n, m := len(box), len(box[0])
	for i := 0; i < n; i++ {
		last := m - 1 // 最后1个空位
		for j := m - 1; j >= 0; j-- {
			if box[i][j] == '*' {
				last = j - 1 // 有障碍，最后空位更新
			} else if box[i][j] == '#' {
				if last > j { // 可以移动
					box[i][last] = '#'
					box[i][j] = '.'
					last--
				} else { // 当前位置不可以移动
					last = j - 1
				}
			}
		}
	}
	res := make([][]byte, m)
	for i := 0; i < m; i++ {
		res[i] = make([]byte, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			res[j][n-1-i] = box[i][j]
		}
	}
	return res
}

1864.构成交替字符串需要的最小交换次数(1)¶

题目

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。
请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。
交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。
任意两个字符都可以进行交换，不必相邻 。
示例 1：输入：s = "111000" 输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。
示例 2：输入：s = "010" 输出：0
解释：字符串已经是交替字符串了，不需要交换。
示例 3：输入：s = "1110" 输出：-1
提示：1 <= s.length <= 1000
s[i] 的值为 '0' 或 '1'

解题思路

No.	思路	时间复杂度	空间复杂度
01	分情况讨论	O(n)	O(1)

func minSwaps(s string) int {
	a, b := strings.Count(s, "1"), strings.Count(s, "0")
	if a-b > 1 || b-a > 1 {
		return -1
	}
	n := len(s)
	res := math.MaxInt32
	if a == (n+1)/2 && b == n/2 { // 以1开头：1010xxx
		count := 0
		for i := 0; i < n; i++ {
			if int(s[i]-'0') == i%2 { // 0在偶数下标位置，1在奇数下标位置
				count++
			}
		}
		res = min(res, count/2)
	}
	if b == (n+1)/2 && a == n/2 { // 以0开头：0101xxx
		count := 0
		for i := 0; i < n; i++ {
			if int(s[i]-'0') != i%2 { // 1在偶数下标位置，0在奇数下标位置
				count++
			}
		}
		res = min(res, count/2)
	}
	return res
}

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

1865.找出和为指定值的下标对(1)¶

题目

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：
累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目
（0 <= i < nums1.length 且 0 <= j < nums2.length）。
实现 FindSumPairs 类：
FindSumPairs(int[] nums1, int[] nums2) 使用整数数组nums1 和 nums2 初始化 FindSumPairs 对象。
void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
int count(int tot) 返回满足nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。
示例：输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：[null, 8, null, 2, 1, null, null, 11]
解释：FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，
下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 
满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7
提示：1 <= nums1.length <= 1000
1 <= nums2.length <= 105
1 <= nums1[i] <= 109
1 <= nums2[i] <= 105
0 <= index < nums2.length
1 <= val <= 105
1 <= tot <= 109
最多调用add 和 count 函数各 1000 次

解题思路

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

type FindSumPairs struct {
	nums1, nums2 []int
	m            map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
	m := make(map[int]int)
	for i := 0; i < len(nums2); i++ {
		m[nums2[i]]++
	}
	return FindSumPairs{
		nums1: nums1,
		nums2: nums2,
		m:     m,
	}
}

func (this *FindSumPairs) Add(index int, val int) {
	this.m[this.nums2[index]]--
	this.nums2[index] = this.nums2[index] + val
	this.m[this.nums2[index]]++
}

func (this *FindSumPairs) Count(tot int) int {
	res := 0
	for i := 0; i < len(this.nums1); i++ {
		res = res + this.m[tot-this.nums1[i]]
	}
	return res
}

1870.准时到达的列车最小时速(1)¶

题目

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。
另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。
示例 1：输入：dist = [1,3,2], hour = 6 输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。
示例 2：输入：dist = [1,3,2], hour = 2.7 输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。
示例 3：输入：dist = [1,3,2], hour = 1.9 输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。
提示：n == dist.length
1 <= n <= 105
1 <= dist[i] <= 105
1 <= hour <= 109
hours 中，小数点后最多存在两位数字

解题思路

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

func minSpeedOnTime(dist []int, hour float64) int {
	n := len(dist)
	if float64(n-1) > hour {
		return -1
	}
	left, right := 1, math.MaxInt32
	for left <= right {
		mid := left + (right-left)/2
		if judge(dist, float64(mid)) <= hour {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func judge(arr []int, speed float64) float64 {
	n := len(arr)
	res := float64(0)
	for i := 0; i < n-1; i++ {
		res = res + math.Ceil(float64(arr[i])/speed) // 向上取整
	}
	res = res + float64(arr[n-1])/speed // 注意：最后一个不需要等待
	return res
}

1871.跳跃游戏VII(4)¶

题目

给你一个下标从 0 开始的二进制字符串s和两个整数minJump 和maxJump。
一开始，你在下标0处，且该位置的值一定为'0'。
当同时满足如下条件时，你可以从下标i移动到下标j处：
i + minJump <= j <= min(i + maxJump, s.length - 1)且 s[j] == '0'.
如果你可以到达 s的下标s.length - 1处，请你返回true，否则返回false。
示例 1：输入：s = "011010", minJump = 2, maxJump = 3 输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。
示例 2：输入：s = "01101110", minJump = 2, maxJump = 3 输出：false
提示：2 <= s.length <= 105
s[i]要么是'0'，要么是'1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	动态规划+滑动窗口	O(n)	O(n)
03	动态规划+前缀和	O(n)	O(n)
04	差分数组	O(n)	O(n)

func canReach(s string, minJump int, maxJump int) bool {
	n := len(s)
	if s[n-1] == '1' {
		return false
	}
	minDis, maxDis := 0, 0 // 更新最后可达到的最小+最大坐标的范围
	for i := 0; i < n-1; i++ {
		if s[i] == '0' && minDis <= i && i <= maxDis {
			minDis = i + minJump
			maxDis = i + maxJump
		}
		if minDis <= n-1 && n-1 <= maxDis {
			return true
		}
	}
	return false
}

# 2
func canReach(s string, minJump int, maxJump int) bool {
	n := len(s)
	if s[n-1] == '1' {
		return false
	}
	dp := make([]bool, n) // dp[i] => 下标i是否可达
	dp[0] = true
	count := 1 // 滑动窗口里面可达数量
	for i := minJump; i < n; i++ {
		if s[i] == '0' && count > 0 { // 当前可达
			dp[i] = true
		}
		if maxJump <= i && dp[i-maxJump] == true { // 滑动窗口左端点:-1
			count--
		}
		if dp[i-minJump+1] == true { // 滑动窗口右端点：+1
			count++
		}
	}
	return dp[n-1]
}

# 3
func canReach(s string, minJump int, maxJump int) bool {
	n := len(s)
	if s[n-1] == '1' {
		return false
	}
	dp := make([]int, n) // dp[i] => 下标i是否可达
	dp[0] = 1
	arr := make([]int, n)
	for i := 0; i < minJump; i++ { // 前缀和从minJump开始
		arr[i] = 1
	}
	for i := minJump; i < n; i++ {
		left := i - maxJump
		right := i - minJump
		if s[i] == '0' {
			var total int
			if left <= 0 {
				total = arr[right]
			} else {
				total = arr[right] - arr[left-1]
			}
			if total > 0 { // 通过前缀和计算，范围内存在多少满足条件的坐标
				dp[i] = 1
			}
		}
		arr[i] = arr[i-1] + dp[i]
	}
	return dp[n-1] > 0
}

# 4
func canReach(s string, minJump int, maxJump int) bool {
	n := len(s)
	if s[n-1] == '1' {
		return false
	}
	arr := make([]int, n+1)
	arr[0] = 1
	arr[1] = -1
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + arr[i]
		if s[i] == '0' && sum > 0 {
			arr[min(i+minJump, n)]++
			arr[min(i+maxJump+1, n)]--
		}
	}
	return sum > 0 // 计算范围内可达到最后有几个坐标满足条件
}

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

1877.数组中最大数对和的最小值(1)¶

题目

一个数对(a,b)的 数对和等于a + b。最大数对和是一个数对数组中最大的数对和。
比方说，如果我们有数对(1,5)，(2,3)和(4,4)，最大数对和为max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8。
给你一个长度为 偶数n的数组nums，请你将 nums中的元素分成 n / 2个数对，使得：
nums中每个元素恰好在 一个数对中，且
最大数对和的值 最小。
请你在最优数对划分的方案下，返回最小的 最大数对和。
示例 1：输入：nums = [3,5,2,3] 输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
示例 2：输入：nums = [3,5,4,2,4,6] 输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。
提示：n == nums.length
2 <= n <= 105
n是 偶数。
1 <= nums[i] <= 105

解题思路

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

func minPairSum(nums []int) int {
	n := len(nums)
	sort.Ints(nums)
	res := 0
	for i := 0; i < n/2; i++ {
		res = max(res, nums[i]+nums[n-1-i])
	}
	return res
}

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

1878.矩阵中最大的三个菱形和(2)¶

题目

给你一个m x n的整数矩阵grid。
菱形和 指的是 grid中一个正菱形 边界上的元素之和。
本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。
下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。
注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。
请你按照 降序返回 grid中三个最大的互不相同的菱形和。如果不同的和少于三个，则将它们全部返回。
示例 1：输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]] 输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211
示例 2：输入：grid = [[1,2,3],[4,5,6],[7,8,9]] 输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）
示例 3：输入：grid = [[7,7,7]] 输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 105

解题思路

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

func getBiggestThree(grid [][]int) []int {
	arr := make([]int, 0)
	n, m := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr = append(arr, grid[i][j]) // 单独一个
			for k := 1; k < n; k++ {      // 枚举增加的长度
				left := i - k
				right := i + k
				button := j + 2*k
				mid := j + k
				if left < 0 || right > n-1 || button > m-1 {
					break
				}
				sum := 0
				b := mid
				for a := left; a < i; a++ { // 左到上
					sum = sum + grid[a][b]
					b--
				}
				for a := i; a < right; a++ { // 上到右
					sum = sum + grid[a][b]
					b++
				}
				for a := right; a > i; a-- { // 右到下
					sum = sum + grid[a][b]
					b++
				}
				for a := i; a > left; a-- { // 下到左
					sum = sum + grid[a][b]
					b--
				}
				arr = append(arr, sum)
			}
		}
	}
	sort.Ints(arr)
	res := make([]int, 0)
	res = append(res, arr[len(arr)-1])
	for i := len(arr) - 2; i >= 0; i-- {
		if arr[i] != arr[i+1] && len(res) < 3 {
			res = append(res, arr[i])
		}
	}
	return res
}

# 2
func getBiggestThree(grid [][]int) []int {
	arr := make([]int, 0)
	n, m := len(grid), len(grid[0])
	sum1, sum2 := make([][]int, n+2), make([][]int, n+2)
	for i := 0; i <= n+1; i++ {
		sum1[i], sum2[i] = make([]int, m+2), make([]int, m+2)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1] // 下到右的斜线
			sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1] // 下到左的斜线
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr = append(arr, grid[i][j])      // 单独一个
			for k := i + 2; k < n; k = k + 2 { // 上下长度
				aX, aY := i, j               // 上顶点
				bX, bY := k, j               // 下顶点
				cX, cY := (i+k)/2, j-(k-i)/2 // 左顶点
				dX, dY := (i+k)/2, j+(k-i)/2 // 右顶点
				if cY < 0 || dY >= m {
					break
				}
				sum := (sum2[cX+1][cY+1] - sum2[aX+1-1][aY+1+1]) + // 左到上
					(sum2[bX+1][bY+1] - sum2[dX+1-1][dY+1+1]) + // 下到右
					(sum1[bX+1][bY+1] - sum1[cX+1-1][cY+1-1]) + // 下到左
					(sum1[dX+1][dY+1] - sum1[aX+1-1][aY+1-1]) - // 右到上
					(grid[aX][aY] + grid[bX][bY] + grid[cX][cY] + grid[dX][dY])
				arr = append(arr, sum)
			}
		}
	}
	sort.Ints(arr)
	res := make([]int, 0)
	res = append(res, arr[len(arr)-1])
	for i := len(arr) - 2; i >= 0; i-- {
		if arr[i] != arr[i+1] && len(res) < 3 {
			res = append(res, arr[i])
		}
	}
	return res
}

1881.插入后的最大值(1)¶

题目

给你一个非常大的整数 n 和一个整数数字 x ，大整数 n用一个字符串表示。
n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中，且 n 可能表示一个 负数 。
你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的 数值。但 不能 在负号的左边插入 x 。
例如，如果 n = 73 且 x = 6 ，那么最佳方案是将 6 插入 7 和 3 之间，使 n = 763 。
如果 n = -55 且 x = 2 ，那么最佳方案是将 2 插在第一个 5 之前，使 n = -255 。
返回插入操作后，用字符串表示的n 的最大值。
示例 1：输入：n = "99", x = 9 输出："999"
解释：不管在哪里插入 9 ，结果都是相同的。
示例 2：输入：n = "-13", x = 2 输出："-123"
解释：向 n 中插入 x 可以得到 -213、-123 或者 -132 ，三者中最大的是 -123 。
提示：1 <= n.length <= 105
1 <= x <= 9
n中每一位的数字都在闭区间 [1, 9] 中。
n代表一个有效的整数。
当 n 表示负数时，将会以字符 '-' 开始。

解题思路

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

func maxValue(n string, x int) string {
	if strings.Contains(n, "-") {
		for i := 1; i < len(n); i++ {
			if x < int(n[i]-'0') {
				return n[:i] + string(x+'0') + n[i:]
			}
		}
	} else {
		for i := 0; i < len(n); i++ {
			if x > int(n[i]-'0') {
				return n[:i] + string(x+'0') + n[i:]
			}
		}
	}
	return n + string(x+'0')
}

1882.使用服务器处理任务(1)¶

题目

给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n和 m。
servers[i] 是第i台服务器的 权重 ，而 tasks[j] 是处理第j项任务 所需要的时间（单位：秒）。
你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。
第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j秒可以开始处理。
处理第 j 项任务时，你需要为它分配一台 权重最小 的空闲服务器。
如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。
如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。
如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早地处理剩余任务。 
如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。
如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。
构建长度为m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。
返回答案数组 ans。
示例 1：输入：servers = [3,3,2], tasks = [1,2,3,2,1,2] 输出：[2,2,0,2,1,2]
解释：事件按时间顺序如下：
- 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。
- 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。
- 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。
- 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。
- 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。
- 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。
示例 2：输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1] 输出：[1,4,1,4,1,3,2]
解释：事件按时间顺序如下：
- 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。
- 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。
- 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。
- 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。
- 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。
- 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。
- 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。
提示：servers.length == n
tasks.length == m
1 <= n, m <= 2 * 105
1 <= servers[i], tasks[j] <= 2 * 105

解题思路

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

func assignTasks(servers []int, tasks []int) []int {
	res := make([]int, 0)
	n := len(servers)
	waitHeap := make(WaitHeap, 0)
	heap.Init(&waitHeap)
	runHeap := make(RunHeap, 0)
	heap.Init(&runHeap)
	for i := 0; i < n; i++ {
		heap.Push(&waitHeap, Node{
			Id:   i,
			Rank: servers[i],
		})
	}
	curTime := 0
	for i := 0; i < len(tasks); i++ {
		curTime = max(curTime, i)
		if waitHeap.Len() == 0 { // 无服务器可用，时间移动
			endTime := runHeap[0].EndTime // 最小的结束时间的出来
			for runHeap.Len() > 0 && runHeap[0].EndTime == endTime {
				node := heap.Pop(&runHeap).(Node)
				heap.Push(&waitHeap, node)
			}
			curTime = max(curTime, endTime)
		} else {
			for runHeap.Len() > 0 && runHeap[0].EndTime <= curTime {
				node := heap.Pop(&runHeap).(Node)
				heap.Push(&waitHeap, node)
			}
		}
		node := heap.Pop(&waitHeap).(Node)
		res = append(res, node.Id)
		heap.Push(&runHeap, Node{
			Id:      node.Id,
			Rank:    node.Rank,
			EndTime: curTime + tasks[i],
		})
	}
	return res
}

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

type Node struct {
	Id      int
	Rank    int // 权重
	EndTime int
}

// 运行堆
type RunHeap []Node

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

// 小根堆<,大根堆变换方向>
func (h RunHeap) Less(i, j int) bool {
	return h[i].EndTime < h[j].EndTime // 按照时间排序
}

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

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

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

// 等待堆
type WaitHeap []Node

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

// 小根堆<,大根堆变换方向>
func (h WaitHeap) Less(i, j int) bool {
	if h[i].Rank == h[j].Rank {
		return h[i].Id < h[j].Id
	}
	return h[i].Rank < h[j].Rank
}

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

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

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

1884.鸡蛋掉落-两枚鸡蛋(2)¶

题目

给你 2枚相同 的鸡蛋，和一栋从第 1层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，
从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。
每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。
如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：输入：n = 2 输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。
示例 2：输入：n = 100 输出：14
解释：一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。
将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。
将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 
99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。
提示：1 <= n <= 1000

解题思路

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

func twoEggDrop(n int) int {
	dp := [3][]int{} // dp[i][j] 有i枚鸡蛋，验证j层楼需要的最少操作次数
	for i := 0; i < 3; i++ {
		dp[i] = make([]int, n+1)
		for j := 1; j < n+1; j++ {
			dp[i][j] = math.MaxInt32
			if i == 1 {
				dp[1][j] = j // 1个鸡蛋，需要j次
			}
		}
	}
	// 值为0
	// dp[1][0], dp[2][0] = 0,0
	for j := 1; j <= n; j++ {
		for k := 1; k <= j; k++ { //
			// a := k              //  假设在k层破碎：剩下1枚鸡蛋,求k-1层结果，(k-1)+1
			a := dp[1][k-1] + 1 //  假设在k层破碎。剩下1枚鸡蛋 求k-1层结果
			b := dp[2][j-k] + 1 //  假设在k层没有破碎：剩余2枚鸡蛋求j-k层结果
			dp[2][j] = min(dp[2][j], max(a, b))
		}
	}
	return dp[2][n]
}

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

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

# 2
func twoEggDrop(n int) int {
	dp := make([]int, n+1) // dp[j]验证j层楼需要的最少操作次数
	for j := 1; j < n+1; j++ {
		dp[j] = math.MaxInt32
	}
	// 值为0
	// dp[0] = 0
	for j := 1; j <= n; j++ {
		for k := 1; k <= j; k++ {
			a := k           //  假设在k层破碎：剩下1枚鸡蛋,求k-1层结果，(k-1)+1
			b := dp[j-k] + 1 //  假设在k层没有破碎：剩余2枚鸡蛋求j-k层结果
			dp[j] = min(dp[j], max(a, b))
		}
	}
	return dp[n]
}

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

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

1887.使数组元素相等的减少操作次数(2)¶

题目

给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：
找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。
如果有多个元素都是最大值，则取最小的 i 。
找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
将 nums[i] 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。
示例 1：输入：nums = [5,1,3] 输出：3
解释：需要 3 次操作使 nums 中的所有元素相等：
1. largest = 5 下标为 0 。nextLargest = 3 。将 nums[0] 减少到 3 。nums = [3,1,3] 。
2. largest = 3 下标为 0 。nextLargest = 1 。将 nums[0] 减少到 1 。nums = [1,1,3] 。
3. largest = 3 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1] 。
示例 2：输入：nums = [1,1,1] 输出：0
解释：nums 中的所有元素已经是相等的。
示例 3：输入：nums = [1,1,2,2,3] 输出：4
解释：需要 4 次操作使 nums 中的所有元素相等：
1. largest = 3 下标为 4 。nextLargest = 2 。将 nums[4] 减少到 2 。nums = [1,1,2,2,2] 。
2. largest = 2 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1,2,2] 。 
3. largest = 2 下标为 3 。nextLargest = 1 。将 nums[3] 减少到 1 。nums = [1,1,1,1,2] 。 
4. largest = 2 下标为 4 。nextLargest = 1 。将 nums[4] 减少到 1 。nums = [1,1,1,1,1] 。
提示：1 <= nums.length <= 5 * 104
1 <= nums[i] <= 5 * 104

解题思路

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

func reductionOperations(nums []int) int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	res := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[i-1] {
			res = res + i
		}
	}
	return res
}

# 2

func reductionOperations(nums []int) int {
	sort.Ints(nums)
	res := 0
	count := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[i-1] {
			count++
		}
		res = res + count
	}
	return res
}

1888.使二进制字符串字符交替的最少反转次数¶

题目¶

解题思路¶

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

1894.找到需要补充粉笔的学生编号(1)¶

题目

一个班级里有n个学生，编号为 0到 n - 1。每个学生会依次回答问题，编号为 0的学生先回答，然后是编号为 1的学生，
以此类推，直到编号为 n - 1的学生，然后老师会重复这个过程，重新从编号为 0的学生开始回答问题。
给你一个长度为 n且下标从 0开始的整数数组chalk和一个整数k。一开始粉笔盒里总共有k支粉笔。
当编号为i的学生回答问题时，他会消耗 chalk[i]支粉笔。如果剩余粉笔数量 严格小于chalk[i]，那么学生 i需要 补充粉笔。
请你返回需要 补充粉笔的学生 编号。
示例 1：输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。
示例 2：输入：chalk = [3,4,1,2], k = 25 输出：1
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。
提示：chalk.length == n
1 <= n <= 105
1 <= chalk[i] <= 105
1 <= k <= 109

解题思路

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

func chalkReplacer(chalk []int, k int) int {
	res := 0
	n := len(chalk)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + chalk[i]
	}
	k = k % sum // 求余
	for i := 0; i < n; i++ {
		if k < chalk[i] {
			return i
		}
		k = k - chalk[i]
	}
	return res
}

1895.最大的幻方(2)¶

题目

一个k x k的幻方指的是一个k x k填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等。
幻方中的整数 不需要互不相同。显然，每个1 x 1的方格都是一个幻方。
给你一个m x n的整数矩阵grid，请你返回矩阵中最大幻方的尺寸（即边长 k）。
示例 1：输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]] 输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12
示例 2：输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]] 输出：2
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 106

解题思路

No.	思路	时间复杂度	空间复杂度
01	枚举+前缀和	O(n^4)	O(n^2)
02	枚举+前缀和	O(n^4)	O(n^2)

func largestMagicSquare(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	rowArr := make([][]int, n) // 行前缀和
	colArr := make([][]int, n) // 列前缀和
	for i := 0; i < n; i++ {
		rowArr[i] = make([]int, m)
		colArr[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		rowArr[i][0] = grid[i][0]
		for j := 1; j < m; j++ {
			rowArr[i][j] = rowArr[i][j-1] + grid[i][j]
		}
	}
	for j := 0; j < m; j++ {
		colArr[0][j] = grid[0][j]
		for i := 1; i < n; i++ {
			colArr[i][j] = colArr[i-1][j] + grid[i][j]
		}
	}
	for length := min(n, m); length >= 2; length-- { // 枚举边长
		for i := 0; i+length <= n; i++ {
			for j := 0; j+length <= m; j++ {
				var target int // 以行目标和
				if j == 0 {
					target = rowArr[i][j+length-1]
				} else {
					target = rowArr[i][j+length-1] - rowArr[i][j-1]
				}
				flag := true
				for k := i + 1; k < i+length; k++ { // 继续检查行
					var temp int
					if j == 0 {
						temp = rowArr[k][j+length-1]
					} else {
						temp = rowArr[k][j+length-1] - rowArr[k][j-1]
					}
					if temp != target {
						flag = false
						break
					}
				}
				if flag == false {
					continue
				}
				for k := j; k < j+length; k++ { // 检查列
					var temp int
					if i == 0 {
						temp = colArr[i+length-1][k]
					} else {
						temp = colArr[i+length-1][k] - colArr[i-1][k]
					}
					if temp != target {
						flag = false
						break
					}
				}
				if flag == false {
					continue
				}
				var left, right int // 左右对角线
				for k := 0; k < length; k++ {
					left = left + grid[i+k][j+k]
					right = right + grid[i+k][j+length-1-k]
				}
				if target == left && target == right {
					return length
				}
			}
		}
	}
	return 1
}

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

# 2
func largestMagicSquare(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	rowArr := make([][]int, n+1)   // 行前缀和
	colArr := make([][]int, n+1)   // 列前缀和
	leftArr := make([][]int, n+1)  // 对角线
	rightArr := make([][]int, n+1) // 对角线
	for i := 0; i <= n; i++ {
		rowArr[i] = make([]int, m+1)
		colArr[i] = make([]int, m+1)
		leftArr[i] = make([]int, m+1)
		rightArr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			rowArr[i][j+1] = rowArr[i][j] + grid[i][j]
			colArr[i+1][j] = colArr[i][j] + grid[i][j]
			leftArr[i+1][j+1] = leftArr[i][j] + grid[i][j]
			rightArr[i+1][j] = rightArr[i][j+1] + grid[i][j]
		}
	}
	for length := min(n, m); length >= 2; length-- { // 枚举边长
		for i := 0; i+length <= n; i++ {
			for j := 0; j+length <= m; j++ {
				target := leftArr[i+length][j+length] - leftArr[i][j]
				if rightArr[i+length][j]-rightArr[i][j+length] != target {
					continue
				}
				flag := true
				for k := i; k < i+length; k++ { // 检查行
					temp := rowArr[k][j+length] - rowArr[k][j]
					if temp != target {
						flag = false
						break
					}
				}
				if flag == false {
					continue
				}
				for k := j; k < j+length; k++ { // 检查列
					temp := colArr[i+length][k] - colArr[i][k]
					if temp != target {
						flag = false
						break
					}
				}
				if flag == true {
					return length
				}
			}
		}
	}
	return 1
}

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

1898.可移除字符的最大数目(3)¶

题目

给你两个字符串 s 和 p ，其中 p 是 s 的一个 子序列 。
同时，给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组removable ，
该数组是 s 中下标的一个子集（s 的下标也 从 0 开始 计数）。
请你找出一个整数 k（0 <= k <= removable.length），选出removable 中的 前 k 个下标，
然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足：在执行完上述步骤后， p 仍然是 s 的一个 子序列 。
更正式的解释是，对于每个 0 <= i < k ，先标记出位于 s[removable[i]] 的字符，
接着移除所有标记过的字符，然后检查 p 是否仍然是 s 的一个子序列。
返回你可以找出的 最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串，
生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。
示例 1：输入：s = "abcacb", p = "ab", removable = [3,1,0] 输出：2
解释：在移除下标 3 和 1 对应的字符后，"abcacb" 变成 "accb" 。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后，"abcacb" 变成 "ccb" ，那么 "ab" 就不再是 s 的一个子序列。
因此，最大的 k 是 2 。
示例 2：输入：s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] 输出：1
解释：在移除下标 3 对应的字符后，"abcbddddd" 变成 "abcddddd" 。
"abcd" 是 "abcddddd" 的一个子序列。
示例 3：输入：s = "abcab", p = "abc", removable = [0,1,2,3,4] 输出：0
解释：如果移除数组 removable 的第一个下标，"abc" 就不再是 s 的一个子序列。
提示：1 <= p.length <= s.length <= 105
0 <= removable.length < s.length
0 <= removable[i] < s.length
p 是 s 的一个 子字符串
s 和 p 都由小写英文字母组成
removable 中的元素 互不相同

解题思路

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

func maximumRemovals(s string, p string, removable []int) int {
	n := len(removable)
	left, right := 0, n
	for left < right {
		mid := left + (right-left)/2
		if judge(s, p, removable, mid) == true {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
	m := make(map[int]bool)
	for i := 0; i < len(removable[:index+1]); i++ {
		m[removable[i]] = true
	}
	i, j := 0, 0
	for i < len(p) && j < len(s) {
		if p[i] == s[j] && m[j] == false {
			i++
		}
		j++
	}
	return i == len(p)
}

# 2
func maximumRemovals(s string, p string, removable []int) int {
	n := len(removable)
	left, right := 0, n+1
	for left < right {
		mid := left + (right-left)/2
		if judge(s, p, removable, mid) == true {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left - 1
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
	m := make(map[int]bool)
	for i := 0; i < len(removable[:index]); i++ {
		m[removable[i]] = true
	}
	i, j := 0, 0
	for i < len(p) && j < len(s) {
		if p[i] == s[j] && m[j] == false {
			i++
		}
		j++
	}
	return i == len(p)
}

# 3
func maximumRemovals(s string, p string, removable []int) int {
	n := len(removable)
	return sort.Search(n, func(index int) bool {
		m := make(map[int]bool)
		for i := 0; i < len(removable[:index+1]); i++ {
			m[removable[i]] = true
		}
		i, j := 0, 0
		for i < len(p) && j < len(s) {
			if p[i] == s[j] && m[j] == false {
				i++
			}
			j++
		}
		return i != len(p)
	})
}

1899.合并若干三元组以形成目标三元组(2)¶

题目

三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。
同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。
为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：
选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），
并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
例如，triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]，
triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。
如果通过以上操作我们可以使得目标 三元组target成为triplets 的一个 元素，则返回 true ；否则，返回 false 。
示例 1：输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] 输出：true
解释：执行下述操作：
- 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。
更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
目标三元组 [2,7,5] 现在是 triplets 的一个元素。
示例 2：输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8] 输出：true
解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。
示例 3：输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] 输出：true
解释：执行下述操作：
- 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。
更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。
triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
- 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。
triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
目标三元组 [5,5,5] 现在是 triplets 的一个元素。
示例 4：输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5] 输出：false
解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。
提示：1 <= triplets.length <= 105
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000

解题思路

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

func mergeTriplets(triplets [][]int, target []int) bool {
	x, y, z := target[0], target[1], target[2]
	a, b, c := 0, 0, 0
	for i := 0; i < len(triplets); i++ {
		a1, b1, c1 := triplets[i][0], triplets[i][1], triplets[i][2]
		if a1 <= x && b1 <= y && c1 <= z {
			a = max(a, a1)
			b = max(b, b1)
			c = max(c, c1)
		}
	}
	return a == x && b == y && c == z
}

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

# 2
func mergeTriplets(triplets [][]int, target []int) bool {
	x, y, z := target[0], target[1], target[2]
	a, b, c := false, false, false
	for i := 0; i < len(triplets); i++ {
		a1, b1, c1 := triplets[i][0], triplets[i][1], triplets[i][2]
		if a1 <= x && b1 <= y && c1 <= z {
			if a1 == x {
				a = true
			}
			if b1 == y {
				b = true
			}
			if c1 == z {
				c = true
			}
		}
	}
	return a == true && b == true && c == true
}

1801-1900-Hard¶

1803.统计异或值在范围内的数对有多少(1)¶

题目

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。
示例 1：输入：nums = [1,4,2,7], low = 2, high = 6 输出：6
解释：所有漂亮数对 (i, j) 列出如下：
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5
示例 2：输入：nums = [9,8,4,2,1], low = 5, high = 14 输出：8
解释：所有漂亮数对 (i, j) 列出如下：
    - (0, 2): nums[0] XOR nums[2] = 13
   - (0, 3): nums[0] XOR nums[3] = 11
   - (0, 4): nums[0] XOR nums[4] = 8
   - (1, 2): nums[1] XOR nums[2] = 12
   - (1, 3): nums[1] XOR nums[3] = 10
   - (1, 4): nums[1] XOR nums[4] = 9
   - (2, 3): nums[2] XOR nums[3] = 6
   - (2, 4): nums[2] XOR nums[4] = 5
提示：1 <= nums.length <= 2 * 104
1 <= nums[i] <= 2 * 104
1 <= low <= high <= 2 * 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	trie树	O(n)	O(n)

func countPairs(nums []int, low int, high int) int {
	res := 0
	n := len(nums)
	root := &Trie{next: make([]*Trie, 2)}
	for i := 0; i < n; i++ {
		// 先查询，再插入
		res = res + root.Search(nums[i], high+1) - root.Search(nums[i], low)
		root.Insert(nums[i])
	}
	return res
}

type Trie struct {
	next []*Trie // 0或者1
	size int     // 次数
}

// 插入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]
		temp.size++
	}
}

// 查找小于target的数量
func (t *Trie) Search(num int, target int) int {
	res := 0
	temp := t
	for i := 31; i >= 0; i-- {
		if temp == nil { // 直接返回
			return res
		}
		value := (num >> i) & 1
		targetValue := (target >> i) & 1
		if targetValue > 0 { // target该位为1
			if temp.next[value] != nil {
				res = res + temp.next[value].size
			}
			temp = temp.next[1-value] // value ^ (1-value) = 1 => 往1-value走
		} else {
			temp = temp.next[value] // value ^ value = 0 // 往value走
		}
	}
	return res
}

1808.好因子的最大数目(1)¶

题目

给你一个正整数primeFactors。你需要构造一个正整数n，它满足以下条件：
n质因数（质因数需要考虑重复的情况）的数目 不超过primeFactors个。
n好因子的数目最大化。如果 n的一个因子可以被 n的每一个质因数整除，我们称这个因子是 好因子 。
比方说，如果n = 12，那么它的质因数为[2,2,3]，那么6和12是好因子，但3 和4不是。
请你返回n的好因子的数目。由于答案可能会很大，请返回答案对109 + 7取余的结果。
请注意，一个质数的定义是大于 1，且不能被分解为两个小于该数的自然数相乘。
一个数 n的质因子是将 n分解为若干个质因子，且它们的乘积为 n。
示例 1：输入：primeFactors = 5 输出：6
解释：200 是一个可行的 n 。
它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。
示例 2：输入：primeFactors = 8 输出：18
提示：1 <= primeFactors <= 109

解题思路

No.	思路	时间复杂度	空间复杂度
01	快速幂	O(log(n))	O(1)

/*
由题意有: n=a1^k1 * a2^k2 *...*an^kn(如12=2^2 * 3^1)
其中
1、a1,a2,...,an是不同的质数(2,3不重复)
2、k1+k2+...+kn <=primeFactors
3、n的好因子,要能被每一个质因数(a1,a2,a3,...,an)整除，即好因子必须含有a1*a2*...*an作为因数
=>好因子的个数 k = k1*k2*...*kn =>求k最大，其中k1+..kn=primeFactors
等价于343题，整数拆分
*/

var mod = 1000000007

func maxNiceDivisors(primeFactors int) int {
	n := primeFactors
	if n <= 3 {
		return n
	}
	if n%3 == 0 {
		return pow(3, n/3) % mod
	} else if n%3 == 1 {
		return pow(3, (n-4)/3) * 4 % mod
	}
	return pow(3, n/3) * 2 % mod
}

func pow(a, b int) int {
	res := 1
	for b > 0 {
		if b%2 == 1 {
			res = res * a % mod
		}
		a = a * a % mod
		b = b / 2
	}
	return res
}

1835.所有数对按位与结果的异或和(2)¶

题目

列表的 异或和（XOR sum）指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素，那么其 异或和 就等于该元素。
例如，[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ，而 [3] 的 异或和 等于 3 。
给你两个下标 从 0 开始 计数的数组 arr1 和 arr2 ，两数组均由非负整数组成。
根据每个(i, j) 数对，构造一个由 arr1[i] AND arr2[j]（按位 AND 运算）结果组成的列表。
其中 0 <= i < arr1.length 且 0 <= j < arr2.length 。
返回上述列表的 异或和 。
示例 1：输入：arr1 = [1,2,3], arr2 = [6,5] 输出：0
解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ，
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。
示例 2：输入：arr1 = [12], arr2 = [4] 输出：4
解释：列表 = [12 AND 4] = [4] ，异或和 = 4 。
提示：1 <= arr1.length, arr2.length <= 105
0 <= arr1[i], arr2[j] <= 109

解题思路

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

func getXORSum(arr1 []int, arr2 []int) int {
	res := 0
	n, m := len(arr1), len(arr2)
	for i := 31; i >= 0; i-- {
		a, b := 0, 0
		for j := 0; j < n; j++ {
			if (arr1[j] & (1 << i)) > 0 {
				a++
			}
		}
		for j := 0; j < m; j++ {
			if (arr2[j] & (1 << i)) > 0 {
				b++
			}
		}
		if a%2 == 1 && b%2 == 1 { // 在该位1的次数都为奇数：奇数x奇数=奇数
			res = res | (1 << i)
		}
	}
	return res
}

# 2
func getXORSum(arr1 []int, arr2 []int) int {
	a, b := 0, 0
	for i := 0; i < len(arr1); i++ {
		a = a ^ arr1[i]
	}
	for i := 0; i < len(arr2); i++ {
		b = b ^ arr2[i]
	}
	return a & b // 位与操作：相同位数都是1，则该结果返回1
}

1857.有向图中最大颜色值(1)¶

题目

给你一个有向图，它含有n个节点和 m条边。节点编号从0 到n - 1。
给你一个字符串colors ，其中colors[i]是小写英文字母，表示图中第 i个节点的 颜色（下标从 0开始）。
同时给你一个二维数组edges，其中edges[j] = [aj, bj]表示从节点aj到节点bj有一条有向边。
图中一条有效 路径是一个点序列x1 -> x2 -> x3 -> ... -> xk，对于所有1 <= i < k，从xi 到xi+1在图中有一条有向边。
路径的 颜色值是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的最大颜色值。如果图中含有环，请返回 -1。
示例 1：输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]] 输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点（上图中的红色节点）。
示例 2：输入：colors = "a", edges = [[0,0]] 输出：-1
解释：从 0 到 0 有一个环。
提示：n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors只含有小写英文字母。
0 <= aj, bj< n

解题思路

No.	思路	时间复杂度	空间复杂度
01	拓扑排序+动态规划	O(n)	O(n)

func largestPathValue(colors string, edges [][]int) int {
	n := len(colors)
	arr := make([][]int, n)  // 邻接表
	degree := make([]int, n) // 入度
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1] // a=>b
		arr[a] = append(arr[a], b)
		degree[b]++
	}
	queue := make([]int, 0)
	for i := 0; i < n; i++ {
		if degree[i] == 0 { // 入度为0
			queue = append(queue, i)
		}
	}
	dp := make([][26]int, n) // dp[i][j] => 到节点i颜色j出现的次数
	count := 0
	for len(queue) > 0 {
		count++ // 节点+1
		node := queue[0]
		queue = queue[1:]
		dp[node][int(colors[node]-'a')]++ // 该节点颜色+1
		for i := 0; i < len(arr[node]); i++ {
			next := arr[node][i]
			degree[next]--
			if degree[next] == 0 {
				queue = append(queue, next)
			}
			// 更新次数
			for j := 0; j < 26; j++ {
				dp[next][j] = max(dp[next][j], dp[node][j])
			}
		}
	}
	if count != n { // 判断环
		return -1
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < 26; j++ {
			res = max(res, dp[i][j])
		}
	}
	return res
}

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

1862.向下取整数对和(1)¶

题目

给你一个整数数组nums，请你返回所有下标对0 <= i, j < nums.length的floor(nums[i] / nums[j])结果之和。
由于答案可能会很大，请你返回答案对109 + 7取余的结果。
函数floor()返回输入数字的整数部分。
示例 1：输入：nums = [2,5,9] 输出：10
解释：floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。
示例 2：输入：nums = [7,7,7,7,7,7,7] 输出：49
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105

解题思路

No.	思路	时间复杂度	空间复杂度
01	枚举	O(n^3/2)	O(n)

func sumOfFlooredPairs(nums []int) int {
	n := len(nums)
	count := make([]int, 200001)
	for i := 0; i < n; i++ {
		count[nums[i]]++
	}
	arr := make([]int, 200001+1) // 前缀和
	for i := 0; i < len(count); i++ {
		arr[i+1] = arr[i] + count[i]
	}
	res := 0
	// a/b = c
	for i := 0; i < len(count); i++ { // 枚举b
		if count[i] > 0 { // i个数大于0
			for j := 1; i*j <= 100000; j++ { // 枚举c
				// b的个数 X c X 目标范围内的数字个数
				total := count[i] * j * (arr[i*(j+1)] - arr[i*j])
				res = (res + total) % 1000000007
			}
		}
	}
	return res
}

1866.恰有K根木棍可以看到的排列数目(1)¶

题目

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。
请你将这些木棍排成一排，并满足从左侧 可以看到恰好 k 根木棍。
从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。
给你 n 和 k ，返回符合题目要求的排列 数目 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
示例 1：输入：n = 3, k = 2 输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。
示例 2：输入：n = 5, k = 5 输出：1
解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。
示例 3：输入：n = 20, k = 11 输出：647427950
解释：总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。
提示：1 <= n <= 1000
1 <= k <= n

解题思路

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

func rearrangeSticks(n int, k int) int {
	dp := make([][]int, n+1) // dp[i][j]代表i根棍子能看到j根；假设每次插入1，假设上一轮的数为：2到n
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
	}
	dp[0][0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			a := dp[i-1][j-1]                        // i-1根棍子里面已经看到了j-1根，插入到最前面
			b := ((i - 1) * dp[i-1][j]) % 1000000007 // i-1根棍子里面已经看到了j根，插入到除最前面的其它i-1个地方都行
			dp[i][j] = (a + b) % 1000000007
		}
	}
	return dp[n][k]
}

1872.石子游戏VIII¶

题目¶

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手。
总共有n个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1，他将执行以下操作：
选择一个整数x > 1，并且 移除最左边的x个石子。
将移除的石子价值之 和累加到该玩家的分数中。
将一个 新的石子放在最左边，且新石子的值为被移除石子值之和。
当只剩下 一个石子时，游戏结束。
Alice 和 Bob 的 分数之差为(Alice 的分数- Bob 的分数)。
Alice 的目标是最大化分数差，Bob 的目标是 最小化分数差。
给你一个长度为 n的整数数组stones，其中stones[i]是 从左边起第i个石子的价值。
请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。
示例 1：输入：stones = [-1,2,-3,4,-5] 输出：5
解释：- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。
stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。
示例 2：输入：stones = [7,-6,5,10,5,-2,-6] 输出：13
解释：- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，
并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。
示例 3：输入：stones = [-10,-12] 输出：-22
解释：- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。
stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。
提示：n == stones.length
2 <= n <= 105
-104 <= stones[i] <= 104

解题思路¶

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

1889.装包裹的最小浪费空间(3)¶

题目

给你n个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。
总共有m个供应商提供 不同尺寸的箱子（每个规格都有无数个箱子）。
如果一个包裹的尺寸 小于等于一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。
包裹的尺寸用一个整数数组packages表示，其中packages[i]是第i个包裹的尺寸。
供应商用二维数组boxes表示，其中boxes[j]是第 j个供应商提供的所有箱子尺寸的数组。
你想要选择 一个供应商并只使用该供应商提供的箱子，使得 总浪费空间最小。
对于每个装了包裹的箱子，我们定义 浪费的空间等于 箱子的尺寸 - 包裹的尺寸。总浪费空间为所有箱子中浪费空间的总和。
比方说，如果你想要用尺寸数组为[4,8]的箱子装下尺寸为[2,3,5]的包裹，
你可以将尺寸为 2和 3的两个包裹装入两个尺寸为 4的箱子中，同时把尺寸为 5的包裹装入尺寸为 8的箱子中。
总浪费空间为(4-2) + (4-3) + (8-5) = 6。
请你选择 最优箱子供应商，使得 总浪费空间最小。如果 无法 将所有包裹放入箱子中，请你返回 -1。
由于答案可能会 很大，请返回它对109 + 7取余的结果。
示例 1：输入：packages = [2,3,5], boxes = [[4,8],[2,8]] 输出：6
解释：选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。
总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。
示例 2：输入：packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]] 输出：-1
解释：没有箱子能装下尺寸为 5 的包裹。
示例 3：输入：packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]] 输出：9
解释：选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。
总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。
提示：n == packages.length
m == boxes.length
1 <= n <= 105
1 <= m <= 105
1 <= packages[i] <= 105
1 <= boxes[j].length <= 105
1 <= boxes[j][k] <= 105
sum(boxes[j].length) <= 105
boxes[j]中的元素 互不相同。

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+二分查找	O(nlog(n))	O(1)
02	排序+二分查找+内置函数	O(nlog(n))	O(1)
03	排序+前缀和+二分查找	O(nlog(n))	O(n)

var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
	sort.Ints(packages)
	n := len(packages)
	res := math.MaxInt64
	for i := 0; i < len(boxes); i++ {
		temp := boxes[i]
		sort.Ints(temp)
		if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
			continue
		}
		sum := 0
		left := 0
		for j := 0; j < len(temp); j++ { // 枚举箱子
			right := binarySearch(packages, temp[j]) // 选择当前箱子能装下的位置
			sum = sum + (right-left)*temp[j]         // 累加：个数*箱子大小
			left = right
		}
		res = min(res, sum)
	}
	if res == math.MaxInt64 {
		return -1
	}
	for i := 0; i < n; i++ {
		res = res - packages[i]
	}
	return res % mod
}

// 找到第一个大于target的位置
func binarySearch(arr []int, target int) int {
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] <= target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

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

# 2
var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
	sort.Ints(packages)
	n := len(packages)
	res := math.MaxInt64
	for i := 0; i < len(boxes); i++ {
		temp := boxes[i]
		sort.Ints(temp)
		if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
			continue
		}
		sum := 0
		left := 0
		for j := 0; j < len(temp); j++ { // 枚举箱子
			// 找到第一个大于target的位置
			right := sort.SearchInts(packages, temp[j]+1) // 选择当前箱子能装下的位置
			sum = sum + (right-left)*temp[j]              // 累加：个数*箱子大小
			left = right
		}
		res = min(res, sum)
	}
	if res == math.MaxInt64 {
		return -1
	}
	for i := 0; i < n; i++ {
		res = res - packages[i]
	}
	return res % mod
}

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

# 3
var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
	sort.Ints(packages)
	n := len(packages)
	arr := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arr[i] = arr[i-1] + packages[i-1]
	}
	res := math.MaxInt64
	for i := 0; i < len(boxes); i++ {
		temp := boxes[i]
		sort.Ints(temp)
		if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
			continue
		}
		sum := 0
		left := 0
		for j := 0; j < len(temp); j++ { // 枚举箱子
			right := binarySearch(packages, temp[j], left) // 选择当前箱子能装下的位置
			sum = sum + (right-left)*temp[j] - (arr[right] - arr[left])
			left = right
		}
		res = min(res, sum)
	}
	if res == math.MaxInt64 {
		return -1
	}
	return res % mod
}

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

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