2201-2300-Easy¶

2206.将数组划分成相等数对(2)¶

题目

给你一个整数数组nums，它包含2 * n个整数。
你需要将nums 划分成n个数对，满足：
每个元素 只属于一个 数对。
同一数对中的元素 相等。
如果可以将 nums划分成 n个数对，请你返回 true，否则返回 false。
示例 1：输入：nums = [3,2,3,2,2,2] 输出：true
解释：nums中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。
nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。
示例 2：输入：nums = [1,2,3,4] 输出：false
解释：无法将 nums 划分成 4 / 2 = 2 个数对且满足所有要求。
提示：nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

解题思路

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

func divideArray(nums []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	for _, v := range m {
		if v%2 == 1 {
			return false
		}
	}
	return true
}

# 2
func divideArray(nums []int) bool {
	sort.Ints(nums)
	for i := 1; i < len(nums); i = i + 2 {
		if nums[i] != nums[i-1] {
			return false
		}
	}
	return true
}

2210.统计数组中峰和谷的数量(2)¶

题目

给你一个下标从 0 开始的整数数组 nums 。如果两侧距 i 最近的不相等邻居的值均小于 nums[i] ，
则下标 i 是 nums 中，某个峰的一部分。类似地，如果两侧距 i 最近的不相等邻居的值均大于 nums[i] ，
则下标 i 是 nums 中某个谷的一部分。
对于相邻下标i 和 j ，如果nums[i] == nums[j] ， 则认为这两下标属于 同一个 峰或谷。
注意，要使某个下标所做峰或谷的一部分，那么它左右两侧必须 都 存在不相等邻居。
返回 nums 中峰和谷的数量。
示例 1：输入：nums = [2,4,1,1,6,5] 输出：3
解释：在下标 0 ：由于 2 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：4 的最近不相等邻居是 2 和 1 。由于 4 > 2 且 4 > 1 ，下标 1 是一个峰。
在下标 2 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 2 是一个谷。
在下标 3 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，
下标 3 符合谷的定义，但需要注意它和下标 2 是同一个谷的一部分。
在下标 4 ：6 的最近不相等邻居是 1 和 5 。由于 6 > 1 且 6 > 5 ，下标 4 是一个峰。
在下标 5 ：由于 5 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 3 个峰和谷，所以返回 3 。
示例 2：输入：nums = [6,6,5,5,4,1] 输出：0
解释：在下标 0 ：由于 6 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：由于 6 的左侧不存在不相等邻居，所以下标 1 既不是峰也不是谷。
在下标 2 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 2 既不是峰也不是谷。
在下标 3 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 3 既不是峰也不是谷。
在下标 4 ：4 的最近不相等邻居是 5 和 1 。由于 4 < 5 且 4 > 1 ，下标 4 既不是峰也不是谷。
在下标 5 ：由于 1 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 0 个峰和谷，所以返回 0 。
提示：3 <= nums.length <= 100
1 <= nums[i] <= 100

解题思路

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

func countHillValley(nums []int) int {
	res := 0
	n := len(nums)
	for i := 1; i < n-1; i++ {
		if nums[i] == nums[i-1] {
			continue
		}
		a, b := -1, -1
		for j := i - 1; j >= 0; j-- {
			if nums[i] != nums[j] {
				a = nums[j]
				break
			}
		}
		for j := i + 1; j < n; j++ {
			if nums[i] != nums[j] {
				b = nums[j]
				break
			}
		}
		if a == -1 || b == -1 {
			continue
		}
		if (a < nums[i] && b < nums[i]) || (a > nums[i] && b > nums[i]) {
			res++
		}
	}
	return res
}

# 2
func countHillValley(nums []int) int {
	res := 0
	n := len(nums)
	flag := 0 // 1：递增，2：递减
	for i := 1; i < n; i++ {
		if nums[i-1] < nums[i] {
			if flag == 2 {
				res++
			}
			flag = 1
		} else if nums[i-1] > nums[i] {
			if flag == 1 {
				res++
			}
			flag = 2
		}
	}
	return res
}

2215.找出两数组的不同(1)¶

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：
answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
注意：列表中的整数可以按 任意 顺序返回。
示例 1：输入：nums1 = [1,2,3], nums2 = [2,4,6] 输出：[[1,3],[4,6]]
解释：对于 nums1 ，nums1[1] = 2 出现在 nums2 中下标 0 处，然而 nums1[0] = 1 和 nums1[2] = 3 没有出现在 nums2 中。
因此，answer[0] = [1,3]。
对于 nums2 ，nums2[0] = 2 出现在 nums1 中下标 1 处，然而 nums2[1] = 4 和 nums2[2] = 6 没有出现在 nums2 中。
因此，answer[1] = [4,6]。
示例 2：输入：nums1 = [1,2,3,3], nums2 = [1,1,2,2] 输出：[[3],[]]
解释：对于 nums1 ，nums1[2] 和 nums1[3] 没有出现在 nums2 中。
由于 nums1[2] == nums1[3] ，二者的值只需要在 answer[0] 中出现一次，故 answer[0] = [3]。
nums2 中的每个整数都在 nums1 中出现，因此，answer[1] = [] 。 
提示：1 <= nums1.length, nums2.length <= 1000
-1000 <= nums1[i], nums2[i] <= 1000

解题思路

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

func findDifference(nums1 []int, nums2 []int) [][]int {
	m1, m2 := make(map[int]bool), make(map[int]bool)
	a, b := make([]int, 0), make([]int, 0)
	for i := 0; i < len(nums1); i++ {
		m1[nums1[i]] = true
	}
	for i := 0; i < len(nums2); i++ {
		m2[nums2[i]] = true
	}
	for k := range m1 {
		if m2[k] == false {
			a = append(a, k)
		}
	}
	for k := range m2 {
		if m1[k] == false {
			b = append(b, k)
		}
	}
	return [][]int{a, b}
}

2220.转换数字的最少位翻转次数(3)¶

题目

一次 位翻转定义为将数字x二进制中的一个位进行 翻转操作，即将0变成1，或者将1变成0。
比方说，x = 7，二进制表示为111，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。
比方说我们可以翻转最右边一位得到110，或者翻转右边起第二位得到101，
或者翻转右边起第五位（这一位是前导 0 ）得到10111等等。
给你两个整数start 和goal，请你返回将start转变成goal的最少位翻转次数。
示例 1：输入：start = 10, goal = 7 输出：3
解释：10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：
- 翻转右边起第一位得到：1010 -> 1011 。
- 翻转右边起第三位：1011 -> 1111 。
- 翻转右边起第四位：1111 -> 0111 。
我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。
示例 2：输入：start = 3, goal = 4 输出：3
解释：3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：
- 翻转右边起第一位：011 -> 010 。
- 翻转右边起第二位：010 -> 000 。
- 翻转右边起第三位：000 -> 100 。
我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。
提示：0 <= start, goal <= 109

解题思路

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

func minBitFlips(start int, goal int) int {
	res := 0
	a := fmt.Sprintf("%032b", start)
	b := fmt.Sprintf("%032b", goal)
	for i := 0; i < 32; i++ {
		if a[i] != b[i] {
			res++
		}
	}
	return res
}

# 2
func minBitFlips(start int, goal int) int {
	res := 0
	temp := start ^ goal
	for ; temp > 0; temp = temp / 2 {
		res = res + temp%2
	}
	return res
}

# 3
func minBitFlips(start int, goal int) int {
	return bits.OnesCount(uint(start ^ goal))
}

2224.转化时间需要的最少操作数(1)¶

题目

给你两个字符串 current 和 correct ，表示两个 24 小时制时间 。
24 小时制时间 按 "HH:MM" 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59 之间。
最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。
在一步操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作 任意 次数。
返回将current 转化为 correct 需要的 最少操作数 。
示例 1：输入：current = "02:30", correct = "04:35" 输出：3
解释：可以按下述 3 步操作将 current 转换为 correct ：
- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。 
- 为 current 加 5 分钟，current 变为 "04:35" 。
可以证明，无法用少于 3 步操作将 current 转化为 correct 。
示例 2：输入：current = "11:00", correct = "11:01" 输出：1
解释：只需要为 current 加一分钟，所以最小操作数是 1 。
提示：current 和 correct 都符合 "HH:MM" 格式
current <= correct

解题思路

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

func convertTime(current string, correct string) int {
	diff := parseTime(correct) - parseTime(current)
	res := 0
	arr := []int{60, 15, 5, 1}
	for i := 0; i < len(arr); i++ {
		res = res + diff/arr[i]
		diff = diff % arr[i]
	}
	return res
}

func parseTime(s string) int {
	a, b := int(s[0]-'0'), int(s[1]-'0')
	c, d := int(s[3]-'0'), int(s[4]-'0')
	return (a*10+b)*60 + (c*10 + d)
}

2231.按奇偶性交换后的最大数字(1)¶

题目

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
返回交换 任意 次之后 num 的 最大 可能值。
示例 1：输入：num = 1234 输出：3412
解释：交换数字 3 和数字 1 ，结果得到 3214 。
交换数字 2 和数字 4 ，结果得到 3412 。
注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。
注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。
示例 2：输入：num = 65875 输出：87655
解释：交换数字 8 和数字 6 ，结果得到 85675 。
交换数字 5 和数字 7 ，结果得到 87655 。
注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。
提示：1 <= num <= 109

解题思路

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

func largestInteger(num int) int {
	value := []byte(strconv.Itoa(num))
	n := len(value)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if int(value[i]-'0')%2 == int(value[j]-'0')%2 &&
				value[i] < value[j] {
				value[i], value[j] = value[j], value[i]
			}
		}
	}
	res, _ := strconv.Atoi(string(value))
	return res
}

2235.两整数相加(1)¶

题目

给你两个整数num1 和 num2，返回这两个整数的和。
示例 1：输入：num1 = 12, num2 = 5 输出：17
解释：num1 是 12，num2 是 5 ，它们的和是 12 + 5 = 17 ，因此返回 17 。
示例 2：输入：num1 = -10, num2 = 4 输出：-6
解释：num1 + num2 = -6 ，因此返回 -6 。
提示：-100 <= num1, num2 <= 100

解题思路

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

func sum(num1 int, num2 int) int {
	return num1 + num2
}

2236.判断根结点是否等于子结点之和(1)¶

题目

给你一个 二叉树 的根结点root，该二叉树由恰好3个结点组成：根结点、左子结点和右子结点。
如果根结点值等于两个子结点值之和，返回true，否则返回false 。
示例 1：输入：root = [10,4,6] 输出：true
解释：根结点、左子结点和右子结点的值分别是 10 、4 和 6 。
由于 10 等于 4 + 6 ，因此返回 true 。
示例 2：输入：root = [5,3,1] 输出：false
解释：根结点、左子结点和右子结点的值分别是 5 、3 和 1 。
由于 5 不等于 3 + 1 ，因此返回 false 。
提示：树只包含根结点、左子结点和右子结点
-100 <= Node.val <= 100

解题思路

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

func checkTree(root *TreeNode) bool {
	return root.Val == root.Left.Val+root.Right.Val
}

2239.找到最接近0的数字(1)¶

题目

给你一个长度为 n的整数数组nums，请你返回 nums中最 接近0的数字。如果有多个答案，请你返回它们中的 最大值。
示例 1：输入：nums = [-4,-2,1,4,8] 输出：1
解释：-4 到 0 的距离为 |-4| = 4 。
-2 到 0 的距离为 |-2| = 2 。
1 到 0 的距离为 |1| = 1 。
4 到 0 的距离为 |4| = 4 。
8 到 0 的距离为 |8| = 8 。
所以，数组中距离 0 最近的数字为 1 。
示例 2：输入：nums = [2,-1,1] 输出：1
解释：1 和 -1 都是距离 0 最近的数字，所以返回较大值 1 。
提示：1 <= n <= 1000
-105 <= nums[i] <= 105

解题思路

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

func findClosestNumber(nums []int) int {
	res := math.MaxInt32 / 10
	for i := 0; i < len(nums); i++ {
		if abs(nums[i]) < abs(res) {
			res = nums[i]
		} else if abs(nums[i]) == abs(res) {
			res = max(res, nums[i])
		}
	}
	return res
}

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

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

2243.计算字符串的数字和(1)¶

题目

给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。
如果 s 的长度大于 k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作：
将 s 拆分 成长度为 k 的若干 连续数字组 ，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。
注意，最后一个数字组的长度可以小于 k 。
用表示每个数字组中所有数字之和的字符串来 替换 对应的数字组。例如，"346" 会替换为 "13" ，因为 3 + 4 + 6 = 13 。
合并 所有组以形成一个新字符串。如果新字符串的长度大于 k 则重复第一步。
返回在完成所有轮操作后的 s 。
示例 1：输入：s = "11111222223", k = 3 输出："135"
解释：- 第一轮，将 s 分成："111"、"112"、"222" 和 "23" 。
  接着，计算每一组的数字和：1 + 1 + 1 = 3、1 + 1 + 2 = 4、2 + 2 + 2 = 6 和 2 + 3 = 5 。 
 这样，s 在第一轮之后变成 "3" + "4" + "6" + "5" = "3465" 。
- 第二轮，将 s 分成："346" 和 "5" 。
 接着，计算每一组的数字和：3 + 4 + 6 = 13 、5 = 5 。
 这样，s 在第二轮之后变成 "13" + "5" = "135" 。 
现在，s.length <= k ，所以返回 "135" 作为答案。
示例 2：输入：s = "00000000", k = 3输出："000"
解释：将 "000", "000", and "00".
接着，计算每一组的数字和：0 + 0 + 0 = 0 、0 + 0 + 0 = 0 和 0 + 0 = 0 。 
s 变为 "0" + "0" + "0" = "000" ，其长度等于 k ，所以返回 "000" 。
提示：1 <= s.length <= 100
2 <= k <= 100
s 仅由数字（0 - 9）组成。

解题思路

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

func digitSum(s string, k int) string {
	arr := []byte(s)
	for len(arr) > k {
		temp := make([]byte, 0)
		for i := 0; i < len(arr); i = i + k {
			sum := 0
			for j := i; j < i+k && j < len(arr); j++ {
				sum = sum + int(arr[j]-'0')
			}
			temp = append(temp, []byte(strconv.Itoa(sum))...)
		}
		arr = temp
	}
	return string(arr)
}

2248.多个数组求交集(2)¶

题目

给你一个二维整数数组 nums ，其中 nums[i] 是由 不同 正整数组成的一个非空数组，
按 升序排列 返回一个数组，数组中的每个元素在 nums所有数组 中都出现过。
示例 1：输入：nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]] 输出：[3,4]
解释：nums[0] = [3,1,2,4,5]，nums[1] = [1,2,3,4]，nums[2] = [3,4,5,6]，
在 nums 中每个数组中都出现的数字是 3 和 4 ，所以返回 [3,4] 。
示例 2：输入：nums = [[1,2,3],[4,5,6]] 输出：[]
解释：不存在同时出现在 nums[0] 和 nums[1] 的整数，所以返回一个空列表 [] 。
提示：1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
nums[i] 中的所有值 互不相同

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希+排序	O(nlog(n))	O(n)
02	数组	O(n)	O(n)

func intersection(nums [][]int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums[i]); j++ {
			m[nums[i][j]]++
		}
	}
	res := make([]int, 0)
	for k, v := range m {
		if v == len(nums) {
			res = append(res, k)
		}
	}
	sort.Ints(res)
	return res
}

# 2
func intersection(nums [][]int) []int {
	arr := make([]int, 1001)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums[i]); j++ {
			arr[nums[i][j]]++
		}
	}
	res := make([]int, 0)
	for i := 1; i <= 1000; i++ {
		if arr[i] == len(nums) {
			res = append(res, i)
		}
	}
	return res
}

2255.统计是给定字符串前缀的字符串数目(1)¶

题目

给你一个字符串数组words和一个字符串s，其中words[i] 和s只包含 小写英文字母。
请你返回 words中是字符串 s前缀的 字符串数目。
一个字符串的 前缀是出现在字符串开头的子字符串。子字符串是一个字符串中的连续一段字符序列。
示例 1：输入：words = ["a","b","c","ab","bc","abc"], s = "abc" 输出：3
解释：words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。
示例 2：输入：words = ["a","a"], s = "aa" 输出：2
解释：两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。
提示：1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i] 和s只包含小写英文字母。

解题思路

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

func countPrefixes(words []string, s string) int {
	res := 0
	for _, v := range words {
		if strings.HasPrefix(s, v) == true {
			res++
		}
	}
	return res
}

2259.移除指定数字得到的最大结果(2)¶

题目

给你一个表示某个正整数的字符串 number 和一个字符 digit 。
从 number 中 恰好 移除 一个 等于digit 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。
生成的测试用例满足 digit 在 number 中出现至少一次。
示例 1：输入：number = "123", digit = "3" 输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。
示例 2：输入：number = "1231", digit = "1" 输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。
示例 3：输入：number = "551", digit = "5" 输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。
提示：2 <= number.length <= 100
number 由数字 '1' 到 '9' 组成
digit 是 '1' 到 '9' 中的一个数字
digit 在 number 中出现至少一次

解题思路

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

func removeDigit(number string, digit byte) string {
	res := -1
	for i := 0; i < len(number); i++ {
		if number[i] == digit {
			res = i
			if i < len(number)-1 && number[i] < number[i+1] { // 贪心：找到第一个大于后面相邻的数
				break
			}
		}
	}
	return number[:res] + number[res+1:]
}

# 2
func removeDigit(number string, digit byte) string {
	res := ""
	for i := 0; i < len(number); i++ {
		if number[i] == digit {
			v := number[:i] + number[i+1:]
			if v > res {
				res = v
			}
		}
	}
	return res
}

2264.字符串中最大的3位相同数字(2)¶

题目

给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：
该整数是 num 的一个长度为 3 的 子字符串 。
该整数由唯一一个数字重复 3 次组成。
以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。
注意：子字符串 是字符串中的一个连续字符序列。
num 或优质整数中可能存在 前导零 。
示例 1：输入：num = "6777133339" 输出："777"
解释：num 中存在两个优质整数："777" 和 "333" 。
"777" 是最大的那个，所以返回 "777" 。
示例 2：输入：num = "2300019" 输出："000"
解释："000" 是唯一一个优质整数。
示例 3：输入：num = "42352338" 输出：""
解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。
提示：3 <= num.length <= 1000
num 仅由数字（0 - 9）组成

解题思路

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

func largestGoodInteger(num string) string {
	for i := '9'; i >= '0'; i-- {
		target := strings.Repeat(string(i), 3)
		if strings.Contains(num, target) == true {
			return target
		}
	}
	return ""
}

# 2
func largestGoodInteger(num string) string {
	res := ""
	for i := 2; i < len(num); i++ {
		if num[i] == num[i-1] && num[i-1] == num[i-2] && num[i-2:i+1] > res {
			res = num[i-2 : i+1]
		}
	}
	return res
}

2269.找到一个数字的K美丽值(2)¶

题目

一个整数 num的k美丽值定义为num中符合以下条件的子字符串数目：
子字符串长度为k。
子字符串能整除 num 。
给你整数num 和k，请你返回num的 k 美丽值。
注意：允许有前缀0。
0不能整除任何值。
一个 子字符串是一个字符串里的连续一段字符序列。
示例 1：输入：num = 240, k = 2 输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。
示例 2：输入：num = 430043, k = 2 输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。
提示：1 <= num <= 109
1 <= k <= num.length（将num视为字符串）

解题思路

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

func divisorSubstrings(num int, k int) int {
	res := 0
	str := strconv.Itoa(num)
	for i := k; i <= len(str); i++ {
		v, _ := strconv.Atoi(str[i-k : i])
		if v > 0 && num%v == 0 {
			res++
		}
	}
	return res
}

# 2
func divisorSubstrings(num int, k int) int {
	res := 0
	target := int(math.Pow10(k))
	for v := num; v >= target/10; v = v / 10 {
		value := v % target
		if value > 0 && num%value == 0 {
			res++
		}
	}
	return res
}

2273.移除字母异位词后的结果数组(2)¶

题目

给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。
在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：
0 < i < words.length
words[i - 1] 和 words[i] 是 字母异位词 。
只要可以选出满足条件的下标，就一直执行这个操作。
在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
例如，"dacb" 是 "abdc" 的一个字母异位词。
示例 1：输入：words = ["abba","baba","bbaa","cd","cd"] 输出：["abba","cd"]
解释：获取结果数组的方法之一是执行下述步骤：
- 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词，选择下标 2 并删除 words[2] 。
  现在 words = ["abba","baba","cd","cd"] 。
- 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词，选择下标 1 并删除 words[1] 。
  现在 words = ["abba","cd","cd"] 。
- 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词，选择下标 2 并删除 words[2] 。
  现在 words = ["abba","cd"] 。
无法再执行任何操作，所以 ["abba","cd"] 是最终答案。
示例 2：输入：words = ["a","b","c","d","e"] 输出：["a","b","c","d","e"]
解释：words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。
提示：1 <= words.length <= 100
1 <= words[i].length <= 10
words[i] 由小写英文字母组成

解题思路

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

func removeAnagrams(words []string) []string {
	flag := true
	for flag == true {
		for i := len(words) - 1; i >= 0; i-- {
			if i == 0 {
				flag = false
				break
			}
			if judge(words[i], words[i-1]) == true {
				words = append(words[:i], words[i+1:]...)
				flag = true
				break
			}
		}
	}
	return words
}

func judge(a, b string) bool {
	m := make(map[rune]int)
	for _, v := range a {
		m[v]++
	}
	for _, v := range b {
		m[v]--
	}
	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true
}

# 2
func removeAnagrams(words []string) []string {
	res := []string{words[0]}
	for i := 1; i < len(words); i++ {
		if judge(res[len(res)-1], words[i]) == false {
			res = append(res, words[i])
		}
	}
	return res
}

func judge(a, b string) bool {
	arr := [256]int{}
	for _, v := range a {
		arr[v]++
	}
	for _, v := range b {
		arr[v]--
	}
	return arr == [256]int{}
}

2278.字母在字符串中的百分比(2)¶

题目

给你一个字符串 s 和一个字符 letter ，返回在 s 中等于letter字符所占的 百分比 ，向下取整到最接近的百分比。
示例 1：输入：s = "foobar", letter = "o" 输出：33
解释：等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。
示例 2：输入：s = "jjjj", letter = "k" 输出：0
解释：等于字母 'k' 的字符在 s 中占到的百分比是 0% ，所以返回 0 。
提示：1 <= s.length <= 100
s 由小写英文字母组成
letter 是一个小写英文字母

解题思路

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

func percentageLetter(s string, letter byte) int {
	return 100 * strings.Count(s, string(letter)) / len(s)
}

# 2
func percentageLetter(s string, letter byte) int {
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == letter {
			count++
		}
	}
	return 100 * count / len(s)
}

2283.判断一个数的数字计数是否等于数位的值(1)¶

题目

给你一个下标从 0开始长度为 n的字符串num，它只包含数字。
如果对于 每个0 <= i < n的下标i，都满足数位i在 num中出现了num[i]次，那么请你返回true，否则返回false。
示例 1：输入：num = "1210" 输出：true
解释：num[0] = '1' 。数字 0 在 num 中出现了一次。
num[1] = '2' 。数字 1 在 num 中出现了两次。
num[2] = '1' 。数字 2 在 num 中出现了一次。
num[3] = '0' 。数字 3 在 num 中出现了零次。
"1210" 满足题目要求条件，所以返回 true 。
示例 2：输入：num = "030" 输出：false
解释：num[0] = '0' 。数字 0 应该出现 0 次，但是在 num 中出现了一次。
num[1] = '3' 。数字 1 应该出现 3 次，但是在 num 中出现了零次。
num[2] = '0' 。数字 2 在 num 中出现了 0 次。
下标 0 和 1 都违反了题目要求，所以返回 false 。
提示：n == num.length
1 <= n <= 10
num只包含数字。

解题思路

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

func digitCount(num string) bool {
	m := make(map[int]int)
	for i := 0; i < len(num); i++ {
		m[int(num[i]-'0')]++
	}
	for i := 0; i < len(num); i++ {
		if m[i] != int(num[i]-'0') {
			return false
		}
	}
	return true
}

2287.重排字符形成目标字符串(1)¶

题目

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。
从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。
示例 1：输入：s = "ilovecodingonleetcode", target = "code" 输出：2
解释：对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。
示例 2：输入：s = "abcba", target = "abc" 输出：1
解释：选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。
示例 3：输入：s = "abbaccaddaeea", target = "aaaaa" 输出：1
解释：选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。
提示：1 <= s.length <= 100
1 <= target.length <= 10

解题思路

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

func rearrangeCharacters(s string, target string) int {
	m1, m2 := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m1[s[i]]++
	}
	for i := 0; i < len(target); i++ {
		m2[target[i]]++
	}
	res := len(s)
	for k, v := range m2 {
		value := m1[k] / v
		if value < res {
			res = value
		}
	}
	return res
}

2293.极大极小游戏(2)¶

题目

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。
对 nums 执行下述算法：
设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组newNums ，
新数组长度为 n / 2 ，下标从 0 开始。
对于满足0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
对于满足0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
用 newNums 替换 nums 。
从步骤 1 开始 重复 整个过程。
执行算法后，返回 nums 中剩下的那个数字。
示例 1：输入：nums = [1,3,5,2,4,8,2,2] 输出：1
解释：重复执行算法会得到下述数组。
第一轮：nums = [1,5,4,2]
第二轮：nums = [1,4]
第三轮：nums = [1]
1 是最后剩下的那个数字，返回 1 。
示例 2：输入：nums = [3] 输出：3
解释：3 就是最后剩下的数字，返回 3 。
提示：1 <= nums.length <= 1024
1 <= nums[i] <= 109
nums.length 是 2 的幂

解题思路

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

func minMaxGame(nums []int) int {
	for len(nums) > 1 {
		temp := make([]int, len(nums)/2)
		for i := 0; i < len(nums)/2; i++ {
			if i%2 == 0 {
				temp[i] = min(nums[i*2], nums[i*2+1])
			} else {
				temp[i] = max(nums[i*2], nums[i*2+1])
			}
		}
		nums = temp
	}
	return nums[0]
}

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 minMaxGame(nums []int) int {
	n := len(nums)
	for n > 1 {
		for i := 0; i < n/2; i++ {
			if i%2 == 0 {
				nums[i] = min(nums[i*2], nums[i*2+1])
			} else {
				nums[i] = max(nums[i*2], nums[i*2+1])
			}
		}
		n = n / 2
	}
	return nums[0]
}

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
}

2299.强密码检验器II(2)¶

题目

如果一个密码满足以下所有条件，我们称它是一个 强密码：
它有至少 8个字符。
至少包含 一个小写英文字母。
至少包含 一个大写英文字母。
至少包含 一个数字。
至少包含 一个特殊字符。特殊字符为："!@#$%^&*()-+"中的一个。
它 不包含2个连续相同的字符（比方说"aab"不符合该条件，但是"aba"符合该条件）。
给你一个字符串password，如果它是一个强密码，返回true，否则返回false。
示例 1：输入：password = "IloveLe3tcode!" 输出：true
解释：密码满足所有的要求，所以我们返回 true 。
示例 2：输入：password = "Me+You--IsMyDream"  输出：false
解释：密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。
示例 3：输入：password = "1aB!"  输出：false
解释：密码不符合长度要求。所以我们返回 false 。
提示：1 <= password.length <= 100
password包含字母，数字和"!@#$%^&*()-+"这些特殊字符。

解题思路

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

func strongPasswordCheckerII(password string) bool {
	if len(password) < 8 {
		return false
	}
	s := "!@#$%^&*()-+"
	mm := make(map[byte]bool)
	for i := 0; i < len(s); i++ {
		mm[s[i]] = true
	}
	m := make(map[int]int)
	arr := []byte(password)
	for k, v := range arr {
		if k >= 1 {
			if v == arr[k-1] {
				return false
			}
		}
		if '0' <= v && v <= '9' {
			m[1] = 1
		}
		if 'a' <= v && v <= 'z' {
			m[2] = 1
		}
		if 'A' <= v && v <= 'Z' {
			m[3] = 1
		}
		if mm[v] == true {
			m[4] = 1
		}
	}
	return len(m) == 4
}

# 2
func strongPasswordCheckerII(password string) bool {
	if len(password) < 8 {
		return false
	}
	m := make(map[int]int)
	for i := 0; i < len(password); i++ {
		if i >= 1 {
			if password[i] == password[i-1] {
				return false
			}
		}
		v := rune(password[i])
		switch {
		case unicode.IsLower(v):
			m[1] = 1
		case unicode.IsUpper(v):
			m[2] = 1
		case unicode.IsDigit(v):
			m[3] = 1
		default:
			m[4] = 1
		}
	}
	return len(m) == 4
}

2201-2300-Medium¶

2201.统计可以提取的工件(2)¶

题目

存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。
给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，
其中 artifacts[i] = [r1i, c1i, r2i, c2i] 表示第 i 个工件在子网格中的填埋情况：
(r1i, c1i) 是第 i 个工件 左上 单元格的坐标，且
(r2i, c2i) 是第 i 个工件 右下 单元格的坐标。
你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。
如果一个工件的所有部分都都裸露出来，你就可以提取该工件。
给你一个下标从 0 开始的二维整数数组 dig ，其中 dig[i] = [ri, ci] 表示你将会挖掘单元格 (ri, ci) ，返回你可以提取的工件数目。
生成的测试用例满足：
不存在重叠的两个工件。
每个工件最多只覆盖 4 个单元格。
dig 中的元素互不相同。
示例 1：输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]] 输出：1
解释： 不同颜色表示不同的工件。挖掘的单元格用 'D' 在网格中进行标记。
有 1 个工件可以提取，即红色工件。
蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。
因此，返回 1 。
示例 2：输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]] 输出：2
解释：红色工件和蓝色工件的所有部分都裸露出来（用 'D' 标记），都可以提取。因此，返回 2 。 
提示：1 <= n <= 1000
1 <= artifacts.length, dig.length <= min(n2, 105)
artifacts[i].length == 4
dig[i].length == 2
0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
r1i <= r2i
c1i <= c2i
不存在重叠的两个工件
每个工件 最多 只覆盖 4 个单元格
dig 中的元素互不相同

解题思路

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

func digArtifacts(n int, artifacts [][]int, dig [][]int) int {
	res := 0
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < len(dig); i++ {
		a, b := dig[i][0], dig[i][1]
		arr[a][b] = 1
	}
	for i := 0; i < len(artifacts); i++ {
		a, b, c, d := artifacts[i][0], artifacts[i][1], artifacts[i][2], artifacts[i][3]
		flag := true
		for x := a; x <= c; x++ {
			for y := b; y <= d; y++ {
				if arr[x][y] == 0 {
					flag = false
				}
			}
		}
		if flag == true {
			res++
		}
	}
	return res
}

# 2
func digArtifacts(n int, artifacts [][]int, dig [][]int) int {
	res := 0
	m := make(map[[2]int]int)
	for i := 0; i < len(dig); i++ {
		a, b := dig[i][0], dig[i][1]
		m[[2]int{a, b}] = 1
	}
	for i := 0; i < len(artifacts); i++ {
		a, b, c, d := artifacts[i][0], artifacts[i][1], artifacts[i][2], artifacts[i][3]
		flag := true
		for x := a; x <= c; x++ {
			for y := b; y <= d; y++ {
				if m[[2]int{x, y}] == 0 {
					flag = false
				}
			}
		}
		if flag == true {
			res++
		}
	}
	return res
}

2202.K次操作后最大化顶端元素(1)¶

题目

给你一个下标从 0开始的整数数组nums，它表示一个 栈 ，其中 nums[0]是栈顶的元素。
每一次操作中，你可以执行以下操作 之一：
如果栈非空，那么 删除栈顶端的元素。
如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加回栈顶，这个元素成为新的栈顶元素。
同时给你一个整数k，它表示你总共需要执行操作的次数。
请你返回 恰好执行 k次操作以后，栈顶元素的 最大值。如果执行完 k次操作以后，栈一定为空，请你返回 -1。
示例 1：输入：nums = [5,2,2,4,0,6], k = 4 输出：5
解释：4 次操作后，栈顶元素为 5 的方法之一为：
- 第 1 次操作：删除栈顶元素 5 ，栈变为 [2,2,4,0,6] 。
- 第 2 次操作：删除栈顶元素 2 ，栈变为 [2,4,0,6] 。
- 第 3 次操作：删除栈顶元素 2 ，栈变为 [4,0,6] 。
- 第 4 次操作：将 5 添加回栈顶，栈变为 [5,4,0,6] 。
注意，这不是最后栈顶元素为 5 的唯一方式。但可以证明，4 次操作以后 5 是能得到的最大栈顶元素。
示例 2：输入：nums = [2], k = 1 输出：-1
解释：第 1 次操作中，我们唯一的选择是将栈顶元素弹出栈。
由于 1 次操作后无法得到一个非空的栈，所以我们返回 -1 。
提示：1 <= nums.length <= 105
0 <= nums[i], k <= 109

解题思路

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

func maximumTop(nums []int, k int) int {
	n := len(nums)
	if n == 1 && k%2 == 1 { // 特殊情况：操作1次删除后栈为空
		return -1
	}
	res := 0
	// 2种情况：
	// 1、k-1中的最大值，最后1次选放回最大值（不会选中第k个数）
	// 2、k+1个位置，删除k个数，剩下的就是栈顶
	for i := 1; i <= n; i++ {
		if i <= k+1 && i != k {
			res = max(res, nums[i-1])
		}
	}
	return res
}

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

2207.字符串中最多数目的子字符串(2)¶

题目

给你一个下标从 0开始的字符串text和另一个下标从 0开始且长度为 2的字符串pattern，两者都只包含小写英文字母。
你可以在 text中任意位置插入 一个 字符，这个插入的字符必须是pattern[0]或者pattern[1]。
注意，这个字符可以插入在 text开头或者结尾的位置。
请你返回插入一个字符后，text中最多包含多少个等于 pattern的 子序列。
子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。
示例 1：输入：text = "abdcdbc", pattern = "ac" 输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 "abadcdbc" 。那么 "ac" 作为子序列出现 4 次。
其他得到 4 个 "ac" 子序列的方案还有 "aabdcdbc" 和 "abdacdbc" 。
但是，"abdcadbc" ，"abdccdbc" 和 "abdcdbcc" 这些字符串虽然是可行的插入方案，
但是只出现了 3 次 "ac" 子序列，所以不是最优解。
可以证明插入一个字符后，无法得到超过 4 个 "ac" 子序列。
示例 2：输入：text = "aabb", pattern = "ab" 输出：6
解释：可以得到 6 个 "ab" 子序列的部分方案为 "aaabb" ，"aaabb" 和 "aabbb" 。
提示：1 <= text.length <= 105
pattern.length == 2
text 和pattern都只包含小写英文字母。

解题思路

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

func maximumSubsequenceCount(text string, pattern string) int64 {
	a, b := pattern[0], pattern[1]
	n := len(text)
	if a == b { // 相同情况：count+1的组合
		count := int64(strings.Count(text, string(a)))
		return (count + 1) * count / 2
	}
	var countA, countB int64
	res := int64(0)
	for i := 0; i < n; i++ {
		if text[i] == a {
			countA++
		} else if text[i] == b {
			countB++
			res = res + countA // 子序列数量：加上前面的a
		}
	}
	return res + max(countA, countB) // 最后决定插入a还是b：插入a在最前面，插入b在最后面
}

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

# 2
func maximumSubsequenceCount(text string, pattern string) int64 {
	a, b := pattern[0], pattern[1]
	n := len(text)
	var countA, countB int64
	res := int64(0)
	for i := 0; i < n; i++ {
		if text[i] == b { // 存在相同的情况，先判断b
			countB++
			res = res + countA // 子序列数量：加上前面的a
		}
		if text[i] == a {
			countA++
		}
	}
	return res + max(countA, countB) // 最后决定插入a还是b：插入a在最前面，插入b在最后面
}

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

2208.将数组和减半的最少操作次数(1)¶

题目

给你一个正整数数组nums。每一次操作中，你可以从nums中选择 任意一个数并将它减小到 恰好一半。
（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums数组和 至少减少一半的 最少操作数。
示例 1：输入：nums = [5,19,8,1] 输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
示例 2：输入：nums = [3,8,20] 输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 107

解题思路

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

func halveArray(nums []int) int {
	n := len(nums)
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	sum := float64(0)
	for i := 0; i < n; i++ {
		sum = sum + float64(nums[i])
		heap.Push(&intHeap, []float64{float64(nums[i])})
	}
	target := sum / 2
	res := 0
	for sum > target {
		node := heap.Pop(&intHeap).([]float64)
		v := node[0]
		v = v / 2
		sum = sum - v
		heap.Push(&intHeap, []float64{v})
		res++
	}
	return res
}

type IntHeap [][]float64

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][0] > h[j][0] }
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.([]float64)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

2211.统计道路上的碰撞次数(2)¶

题目

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。
给你一个下标从 0 开始的字符串 directions ，长度为 n 。
directions[i] 可以是 'L'、'R' 或 'S' 分别表示第 i 辆车是向 左 、向 右 或者 停留 在当前位置。每辆车移动时 速度相同 。
碰撞次数可以按下述方式计算：
当两辆移动方向相反的车相撞时，碰撞次数加 2 。
当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。
碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。
返回在这条道路上发生的 碰撞总次数 。
示例 1：输入：directions = "RLRSLL" 输出：5
解释：将会在道路上发生的碰撞列出如下：
- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
因此，将会在道路上发生的碰撞总次数是 5 。
示例 2：输入：directions = "LLRR" 输出：0
解释：不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。
提示：1 <= directions.length <= 105
directions[i] 的值为 'L'、'R' 或 'S'

解题思路

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

func countCollisions(directions string) int {
	s := strings.TrimLeft(directions, "L") // 左边向左不会发生碰撞
	s = strings.TrimRight(s, "R")          // 右边向右不会发生碰撞
	return len(s) - strings.Count(s, "S")  // 剩下的车都会发生碰撞
}

# 2
func countCollisions(directions string) int {
	n := len(directions)
	i, j := 0, n-1
	for i < n && directions[i] == 'L' {
		i++
	}
	for j >= 0 && directions[j] == 'R' {
		j--
	}
	count := 0
	for k := i; k <= j; k++ {
		if directions[k] == 'S' {
			count++
		}
	}
	return j - i + 1 - count
}

2212.射箭比赛中的最大得分(1)¶

题目

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：
Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k区域射中ak 和 bk 支箭。
如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
如果 ak == bk == 0 ，那么无人得到 k 分。
例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。
如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得11 分。
给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中0 到 11 每个计分区域的箭数量。
现在，Bob 想要尽可能 最大化 他所能获得的总分。
返回数组 bobArrows ，该数组表示 Bob 射中0 到 11 每个 计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。
如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。
示例 1：输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0] 输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。
示例 2：输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2] 输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。
提示：1 <= numArrows <= 105
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows

解题思路

No.	思路	时间复杂度	空间复杂度
01	二进制状态-枚举	O(n*2^n)	O(1)

func maximumBobPoints(numArrows int, aliceArrows []int) []int {
	n := len(aliceArrows)
	total := 1 << n // 所有状态
	maxValue := 0
	maxState := 0
	for state := 0; state < total; state++ { // 枚举所有状态
		sum := 0
		score := 0
		for i := 0; i < n; i++ {
			if (state>>i)&1 > 0 {
				sum = sum + aliceArrows[i] + 1 // 箭的数量
				score = score + i              // 得分
			}
		}
		if sum <= numArrows && score > maxValue {
			maxValue = score
			maxState = state
		}
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		if (maxState>>i)&1 > 0 {
			res[i] = aliceArrows[i] + 1
			numArrows = numArrows - res[i]
		}
	}
	res[0] = res[0] + numArrows // 剩下放在任何1个里面即可
	return res
}

2216.美化数组的最少删除数(2)¶

题目

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。
当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目。
示例 1：输入：nums = [1,1,2,3,5] 输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。
可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
示例 2：输入：nums = [1,1,2,2,3,3] 输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。
可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。
提示：1 <= nums.length <= 105
0 <= nums[i] <= 105

解题思路

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

func minDeletion(nums []int) int {
	res := 0
	n := len(nums)
	for i := 0; i < n; {
		j := i + 1
		for j < n && nums[i] == nums[j] { // 找到后面1个不相同的组成1对，然后开始找下一对
			j++
		}
		if j < n {
			res = res + 2
		}
		i = j + 1
	}
	return n - res
}

# 2
func minDeletion(nums []int) int {
	res := 0
	n := len(nums)
	for i := 0; i < n-1; i++ {
		if nums[i] == nums[i+1] {
			res++
		} else {
			i++
		}
	}
	return res + (n-res)%2 // 剩下奇数个要+1
}

2217.找到指定长度的回文数(2)¶

题目

给你一个整数数组queries和一个 正整数intLength，请你返回一个数组answer，
其中answer[i] 是长度为intLength的正回文数 中第queries[i]小的数字，如果不存在这样的回文数，则为 -1。
回文数 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。
示例 1：输入：queries = [1,2,3,4,5,90], intLength = 3 输出：[101,111,121,131,141,999]
解释：长度为 3 的最小回文数依次是：
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
第 90 个长度为 3 的回文数是 999 。
示例 2：输入：queries = [2,4,6], intLength = 4 输出：[1111,1331,1551]
解释：长度为 4 的前 6 个回文数是：
1001, 1111, 1221, 1331, 1441 和 1551 。
提示：1 <= queries.length <= 5 * 104
1 <= queries[i] <= 109
1 <= intLength<= 15

解题思路

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

func kthPalindrome(queries []int, intLength int) []int64 {
	n := (intLength + 1) / 2          // 回文前半部分的长度：12321=>长度5=>前半部分长度3
	start := int(math.Pow10(n-1) - 1) // n长度对应的回文数量下限 ：2=>10^2-1=99
	limit := int(math.Pow10(n) - 1)   // n长度对应的回文数量上限
	res := make([]int64, 0)
	for i := 0; i < len(queries); i++ {
		if start+queries[i] > limit {
			res = append(res, -1)
			continue
		}
		res = append(res, getKthPalindrome(intLength, start+queries[i]))
	}
	return res
}

func getKthPalindrome(intLength, num int) int64 {
	arr := []byte(strconv.Itoa(num))
	if intLength%2 == 0 { // 偶数
		for i := len(arr) - 1; i >= 0; i-- {
			arr = append(arr, arr[i])
		}
	} else {
		for i := len(arr) - 2; i >= 0; i-- {
			arr = append(arr, arr[i])
		}
	}
	res, _ := strconv.ParseInt(string(arr), 10, 64)
	return res
}

# 2
func kthPalindrome(queries []int, intLength int) []int64 {
	n := (intLength + 1) / 2          // 回文前半部分的长度：12321=>长度5=>前半部分长度3
	start := int(math.Pow10(n-1) - 1) // n长度对应的回文数量下限 ：2=>10^2-1=99
	limit := int(math.Pow10(n) - 1)   // n长度对应的回文数量上限
	res := make([]int64, 0)
	for i := 0; i < len(queries); i++ {
		if start+queries[i] > limit {
			res = append(res, -1)
			continue
		}
		res = append(res, getKthPalindrome(intLength, start+queries[i]))
	}
	return res
}

func getKthPalindrome(intLength, num int) int64 {
	temp := num
	if intLength%2 == 1 {
		temp = temp / 10
	}
	res := int64(num)
	for ; temp > 0; temp = temp / 10 {
		res = res*10 + int64(temp%10)
	}
	return res
}

2221.数组的三角和(2)¶

题目

给你一个下标从 0开始的整数数组nums，其中nums[i]是 0到 9之间（两者都包含）的一个数字。
nums的 三角和是执行以下操作以后最后剩下元素的值：
nums初始包含n个元素。如果n == 1，终止操作。否则，创建一个新的下标从0开始的长度为 n - 1的整数数组newNums。
对于满足0 <= i <n - 1的下标i，newNums[i] 赋值为(nums[i] + nums[i+1]) % 10，%表示取余运算。
将newNums替换 数组nums。
从步骤 1 开始重复整个过程。
请你返回nums的三角和。
示例 1：输入：nums = [1,2,3,4,5] 输出：8
解释：上图展示了得到数组三角和的过程。
示例 2：输入：nums = [5] 输出：5
解释：由于 nums 中只有一个元素，数组的三角和为这个元素自己。
提示：1 <= nums.length <= 1000
0 <= nums[i] <= 9

解题思路

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

func triangularSum(nums []int) int {
	for len(nums) > 1 {
		arr := make([]int, len(nums)-1)
		for i := 0; i < len(nums)-1; i++ {
			arr[i] = (nums[i] + nums[i+1]) % 10
		}
		nums = arr
	}
	return nums[0]
}

# 2
func triangularSum(nums []int) int {
	for n := len(nums) - 1; n > 0; n-- {
		for i := 0; i < n; i++ {
			nums[i] = (nums[i] + nums[i+1]) % 10
		}
	}
	return nums[0]
}

2222.选择建筑的方案数(2)¶

题目

给你一个下标从 0开始的二进制字符串s，它表示一条街沿途的建筑类型，其中：
s[i] = '0'表示第i栋建筑是一栋办公楼，
s[i] = '1'表示第i栋建筑是一间餐厅。
作为市政厅的官员，你需要随机选择3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻的两栋不能是同一类型。
比方说，给你s = "001101"，我们不能选择第1，3和5栋建筑，
因为得到的子序列是"011"，有相邻两栋建筑是同一类型，所以 不合题意。
请你返回可以选择 3 栋建筑的 有效方案数。
示例 1：输入：s = "001101" 输出：6
解释：以下下标集合是合法的：
- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"
没有别的合法选择，所以总共有 6 种方法。
示例 2：输入：s = "11100" 输出：0
解释：没有任何符合题意的选择。
提示：3 <= s.length <= 105
s[i]要么是'0'，要么是'1'。

解题思路

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

func numberOfWays(s string) int64 {
	res := int64(0)
	n := len(s)
	count1 := strings.Count(s, "1") // 1的总个数
	count0 := n - count1            // 0的总个数
	count := 0                      // 遍历时候1的个数
	for i := 0; i < n; i++ {        // 枚举以当前字母作为中间元素
		if s[i] == '1' { // 010
			left0 := i - count       // 左边0的个数
			right0 := count0 - left0 // 右边0的个数
			res = res + int64(left0)*int64(right0)
			count++
		} else { // 101
			left1 := count           // 左边1的个数
			right1 := count1 - count // 右边1的个数
			res = res + int64(left1)*int64(right1)
		}
	}
	return res
}

# 2
func numberOfWays(s string) int64 {
	return getCount(s, "101") + getCount(s, "010")
}

func getCount(s string, str string) int64 {
	var a, b, c int64
	for i := 0; i < len(s); i++ {
		if s[i] == str[0] { // 以101为例：计算1的个数
			a++
		}
		if s[i] == str[1] { // 以101为例：计算01的个数
			b = b + a 
		}
		if s[i] == str[2] { // 以101为例：计算101的个数
			c = c + b
		}
	}
	return c
}

2225.找出输掉零场或一场比赛的玩家(2)¶

题目

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 answer ：
answer[0] 是所有 没有 输掉任何比赛的玩家列表。
answer[1] 是所有恰好输掉 一场 比赛的玩家列表。
两个列表中的值都应该按 递增 顺序返回。
注意：只考虑那些参与 至少一场 比赛的玩家。
生成的测试用例保证 不存在 两场比赛结果 相同 。
示例 1：输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。
示例 2：输入：matches = [[2,3],[1,3],[5,4],[6,4]] 输出：[[1,2,5,6],[]]
解释：玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。
提示：1 <= matches.length <= 105
matches[i].length == 2
1 <= winneri, loseri <= 105
winneri != loseri
所有 matches[i] 互不相同

解题思路

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

func findWinners(matches [][]int) [][]int {
	m1, m2 := make(map[int]int), make(map[int]int)
	for i := 0; i < len(matches); i++ {
		a, b := matches[i][0], matches[i][1]
		m1[a]++ // 赢的+1
		m2[b]-- // 输的-1
	}
	arr1, arr2 := make([]int, 0), make([]int, 0)
	for k := range m1 {
		if _, ok := m2[k]; ok == false {
			arr1 = append(arr1, k)
		}
	}
	for k, v := range m2 {
		if v == -1 {
			arr2 = append(arr2, k)
		}
	}
	sort.Ints(arr1)
	sort.Ints(arr2)
	return [][]int{arr1, arr2}
}

# 2
func findWinners(matches [][]int) [][]int {
	m := make(map[int]int)
	for i := 0; i < len(matches); i++ {
		a, b := matches[i][0], matches[i][1]
		if _, ok := m[a]; ok == false {
			m[a] = 0 // 赢的标记为0
		}
		m[b]++ // 输的+1
	}
	arr := [2][]int{}
	for k, v := range m {
		if v < 2 { // 0：全赢， 1：输1次
			arr[v] = append(arr[v], k)
		}
	}
	sort.Ints(arr[0])
	sort.Ints(arr[1])
	return [][]int{arr[0], arr[1]}
}

2226.每个小孩最多能分到多少糖果(3)¶

题目

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。
你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。
每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
示例 1：输入：candies = [5,8,6], k = 3 输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。
现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。
可以证明无法让每个小孩得到超过 5 颗糖果。
示例 2：输入：candies = [2,5], k = 11 输出：0
解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。
因此，最后每个小孩都没有得到糖果，答案是 0 。
提示：1 <= candies.length <= 105
1 <= candies[i] <= 107
1 <= k <= 1012

解题思路

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

func maximumCandies(candies []int, k int64) int {
	sum := int64(0)
	maxValue := 0
	for i := 0; i < len(candies); i++ {
		sum = sum + int64(candies[i])
		maxValue = max(maxValue, candies[i])
	}
	if sum < k {
		return 0
	}
	left := 1
	right := maxValue
	for left <= right {
		mid := left + (right-left)/2
		total := check(candies, mid)
		if total >= k {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left - 1
}

func check(arr []int, target int) int64 {
	res := int64(0)
	for i := 0; i < len(arr); i++ {
		res = res + int64(arr[i]/target)
	}
	return res
}

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

# 2
func maximumCandies(candies []int, k int64) int {
	sum := int64(0)
	maxValue := 0
	for i := 0; i < len(candies); i++ {
		sum = sum + int64(candies[i])
		maxValue = max(maxValue, candies[i])
	}
	if sum < k {
		return 0
	}
	left := 1
	right := maxValue + 1
	for left < right {
		mid := left + (right-left)/2
		total := check(candies, mid)
		if total >= k {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left - 1
}

func check(arr []int, target int) int64 {
	res := int64(0)
	for i := 0; i < len(arr); i++ {
		res = res + int64(arr[i]/target)
	}
	return res
}

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

# 3
func maximumCandies(candies []int, k int64) int {
	sum := int64(0)
	maxValue := 0
	for i := 0; i < len(candies); i++ {
		sum = sum + int64(candies[i])
		maxValue = max(maxValue, candies[i])
	}
	if sum < k {
		return 0
	}
	return sort.Search(maxValue+1, func(target int) bool {
		if target == 0 {
			return false
		}
		res := int64(0)
		for i := 0; i < len(candies); i++ {
			res = res + int64(candies[i]/target)
		}
		return res < k
	}) - 1
}

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

2232.向表达式添加括号后的最小结果(1)¶

题目

给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。
请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。
左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。
返回添加一对括号后形成的表达式expression ，且满足 expression 计算得到 最小 可能值。
如果存在多个答案都能产生相同结果，返回任意一个答案。
生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。
示例 1：输入：expression = "247+38" 输出："2(47+38)"
解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
注意 "2(4)7+38" 不是有效的结果，因为右括号必须添加在 '+' 的右侧。
可以证明 170 是最小可能值。
示例 2：输入：expression = "12+34" 输出："1(2+3)4"
解释：表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。
示例 3：输入：expression = "999+999" 输出："(999+999)"
解释：表达式计算得到 999 + 999 = 1998 。
提示：3 <= expression.length <= 10
expression 仅由数字 '1' 到 '9' 和 '+' 组成
expression 由数字开始和结束
expression 恰好仅含有一个 '+'.
expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围

解题思路

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

func minimizeResult(expression string) string {
	res := ""
	arr := strings.Split(expression, "+")
	left, right := arr[0], arr[1]
	minValue := math.MaxInt32
	for i := 0; i < len(left); i++ {
		for j := 1; j <= len(right); j++ {
			var a, b, c, d int
			if i == 0 { // 左边
				a = 1
			} else {
				a, _ = strconv.Atoi(left[:i])
			}
			b, _ = strconv.Atoi(left[i:])
			c, _ = strconv.Atoi(right[:j])
			d = 1
			if j < len(right) { // 右边
				d, _ = strconv.Atoi(right[j:])
			}
			if a*(b+c)*d < minValue {
				minValue = a * (b + c) * d
				res = fmt.Sprintf("%s(%s+%s)%s", left[:i], left[i:], right[:j], right[j:])
			}
		}
	}
	return res
}

2233.K次增加后的最大乘积(2)¶

题目

给你一个非负整数数组nums和一个整数k。每次操作，你可以选择nums中 任一元素并将它 增加1。
请你返回 至多k次操作后，能得到的nums的最大乘积。由于答案可能很大，请你将答案对109 + 7取余后返回。
示例 1：输入：nums = [0,4], k = 5 输出：20
解释：将第一个数增加 5 次。
得到 nums = [5, 4] ，乘积为 5 * 4 = 20 。
可以证明 20 是能得到的最大乘积，所以我们返回 20 。
存在其他增加 nums 的方法，也能得到最大乘积。
示例 2：输入：nums = [6,3,3,2], k = 2 输出：216
解释：将第二个数增加 1 次，将第四个数增加 1 次。
得到 nums = [6, 4, 3, 3] ，乘积为 6 * 4 * 3 * 3 = 216 。
可以证明 216 是能得到的最大乘积，所以我们返回 216 。
存在其他增加 nums 的方法，也能得到最大乘积。
提示：1 <= nums.length, k <= 105
0 <= nums[i] <= 106

解题思路

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

var mod = 1000000007

func maximumProduct(nums []int, k int) int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < len(nums); i++ {
		heap.Push(&intHeap, nums[i])
	}
	// x y：如果x>y,y+1后的结果较大
	// (x+1)*y = xy+y
	// x*(y+1) = xy+x
	for i := 1; i <= k; i++ {
		node := heap.Pop(&intHeap).(int)
		node++
		heap.Push(&intHeap, node)
	}
	res := 1
	for intHeap.Len() > 0 {
		node := heap.Pop(&intHeap).(int)
		res = res * node % mod
	}
	return res
}

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{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

# 2
var mod = 1000000007

func maximumProduct(nums []int, k int) int {
	res := 1
	sort.Ints(nums)
	n := len(nums)
	nums = append(nums, math.MaxInt32/100)
	for i := 0; i < n; i++ {
		sum := (i + 1) * (nums[i+1] - nums[i])
		if k >= sum {
			k = k - sum
			continue
		}
		b := k / (i + 1) // 加多少
		d := k % (i + 1) // 剩下多少+1
		for j := 0; j <= i; j++ {
			nums[j] = nums[i] + b // 在nums[i]基础上加
			if j < d {
				nums[j]++
			}
		}
		break
	}
	for i := 0; i < n; i++ {
		res = res * nums[i] % mod
	}
	return res
}

2240.买钢笔和铅笔的方案数(1)¶

题目

给你一个整数total，表示你拥有的总钱数。同时给你两个整数cost1 和cost2，分别表示一支钢笔和一支铅笔的价格。
你可以花费你部分或者全部的钱，去买任意数目的两种笔。
请你返回购买钢笔和铅笔的不同方案数目。
示例 1：输入：total = 20, cost1 = 10, cost2 = 5 输出：9
解释：一支钢笔的价格为 10 ，一支铅笔的价格为 5 。
- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。
所以买钢笔和铅笔的总方案数为 5 + 3 + 1 = 9 种。
示例 2：输入：total = 5, cost1 = 10, cost2 = 10 输出：1
解释：钢笔和铅笔的价格都为 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种方案：买 0 支钢笔和 0 支铅笔。
提示：1 <= total, cost1, cost2 <= 106

解题思路

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

func waysToBuyPensPencils(total int, cost1 int, cost2 int) int64 {
	res := int64(0)
	for i := 0; i <= total/cost1; i++ {
		res = res + int64((total-cost1*i)/cost2) + 1 // 可以买0支铅笔，次数+1
	}
	return res
}

2241.设计一个ATM机器(1)¶

题目

一个 ATM 机器，存有5种面值的钞票：20，50，100，200和500美元。初始时，ATM 机是空的。
用户可以用它存或者取任意数目的钱。
取款时，机器会优先取 较大数额的钱。
比方说，你想取$300，并且机器里有2张 $50的钞票，1张$100的钞票和1张$200的钞票，
那么机器会取出$100 和$200的钞票。
但是，如果你想取$600，机器里有3张$200的钞票和1张$500的钞票，那么取款请求会被拒绝，
因为机器会先取出$500的钞票，然后无法取出剩余的$100。注意，因为有$500钞票的存在，机器不能取$200的钞票。
请你实现 ATM 类：
ATM()初始化 ATM 对象。
void deposit(int[] banknotesCount)分别存入$20，$50，$100，$200和$500钞票的数目。
int[] withdraw(int amount)返回一个长度为5的数组，分别表示$20，$50，$100，$200和$500钞票的数目，
并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回[-1]（这种情况下 不取出任何钞票）。
示例 1：输入： ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
输出：[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
解释：ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 $100 ，2 张 $200 和 1 张 $500 的钞票。
atm.withdraw(600);        // 返回 [0,0,1,0,1] 。机器返回 1 张 $100 和 1 张 $500 的钞票。
机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ，1 张 $200 和 1 张 $500 的钞票。
                          // 机器中剩余钞票数量为 [0,1,0,3,1] 。
atm.withdraw(600);        // 返回 [-1] 。机器会尝试取出 $500 的钞票，然后无法得到剩余的 $100 ，所以取款请求会被拒绝。
                          // 由于请求被拒绝，机器中钞票的数量不会发生改变。
atm.withdraw(550);        // 返回 [0,1,0,0,1] ，机器会返回 1 张 $50 的钞票和 1 张 $500 的钞票。
提示：banknotesCount.length == 5
0 <= banknotesCount[i] <= 109
1 <= amount <= 109
总共最多有5000次withdraw 和deposit的调用。
函数 withdraw 和deposit至少各有 一次调用。

解题思路

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

var Array = [5]int{20, 50, 100, 200, 500}

type ATM struct {
	arr [5]int
}

func Constructor() ATM {
	return ATM{arr: [5]int{}}
}

func (this *ATM) Deposit(banknotesCount []int) {
	for i := 0; i < len(banknotesCount); i++ {
		this.arr[i] = this.arr[i] + banknotesCount[i]
	}
}

func (this *ATM) Withdraw(amount int) []int {
	res := make([]int, 5)
	for i := 4; i >= 0; i-- {
		res[i] = min(this.arr[i], amount/Array[i])
		amount = amount - Array[i]*res[i]
	}
	if amount > 0 {
		return []int{-1}
	}
	for i := 0; i < 5; i++ {
		this.arr[i] = this.arr[i] - res[i]
	}
	return res
}

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

2244.完成所有任务需要的最少轮数(1)¶

题目

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。
在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。
返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。
示例 1：输入：tasks = [2,2,3,3,2,4,4,4,4,4] 输出：4
解释：要想完成所有任务，一个可能的计划是：
- 第一轮，完成难度级别为 2 的 3 个任务。 
- 第二轮，完成难度级别为 3 的 2 个任务。 
- 第三轮，完成难度级别为 4 的 3 个任务。 
- 第四轮，完成难度级别为 4 的 2 个任务。 
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。
示例 2：输入：tasks = [2,3,3] 输出：-1
解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。
因此，无法完成所有任务，答案为 -1 。
提示：1 <= tasks.length <= 105
1 <= tasks[i] <= 109

解题思路

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

func minimumRounds(tasks []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(tasks); i++ {
		m[tasks[i]]++
	}
	for _, v := range m {
		if v == 1 { // 1个直接返回
			return -1
		}
		if v%3 == 0 {
			res = res + v/3
		} else {
			res = res + v/3 + 1 // %v=1 拆成2+2；%v=2，拆成3+2
		}
	}
	return res
}

2245.转角路径的乘积中最多能有几个尾随零¶

题目¶

给你一个二维整数数组 grid ，大小为 m x n，其中每个单元格都含一个正整数。
转角路径 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 向水平方向 或者 向竖直方向 移动过弯（如果存在弯），
而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 另一个 方向行进：
如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。
一条路径的 乘积 定义为：路径上所有值的乘积。
请你从 grid 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。
注意：水平 移动是指向左或右移动。 竖直 移动是指向上或下移动。
示例 1：输入：grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]] 输出：3
解释：左侧的图展示了一条有效的转角路径。
其乘积为 15 * 20 * 6 * 1 * 10 = 18000 ，共计 3 个尾随零。
可以证明在这条转角路径的乘积中尾随零数目最多。
中间的图不是一条有效的转角路径，因为它有不止一个弯。
右侧的图也不是一条有效的转角路径，因为它需要重复访问已经访问过的单元格。
示例 2：输入：grid = [[4,3,2],[7,6,1],[8,8,8]] 输出：0
解释：网格如上图所示。
不存在乘积含尾随零的转角路径。
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
1 <= grid[i][j] <= 1000

解题思路¶

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

2249.统计圆内格点数目(1)¶

题目

给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 
表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。
注意：格点 是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。
示例 1：输入：circles = [[2,2,1]] 输出：5
解释：给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。
示例 2：输入：circles = [[2,2,2],[3,4,1]] 输出：16
解释：给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。
提示：1 <= circles.length <= 200
circles[i].length == 3
1 <= xi, yi <= 100
1 <= ri <= min(xi, yi)

解题思路

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

func countLatticePoints(circles [][]int) int {
	res := 0
	for i := 0; i <= 200; i++ {
		for j := 0; j <= 200; j++ {
			for k := 0; k < len(circles); k++ {
				x, y, r := circles[k][0], circles[k][1], circles[k][2]
				if (i-x)*(i-x)+(j-y)*(j-y) <= r*r {
					res++
					break
				}
			}
		}
	}
	return res
}

2250.统计包含每个点的矩形数目(2)¶

题目

给你一个二维整数数组rectangles，其中rectangles[i] = [li, hi]表示第i个矩形长为li高为hi。
给你一个二维整数数组points，其中points[j] = [xj, yj]是坐标为(xj, yj)的一个点。
第i个矩形的 左下角在(0, 0)处，右上角在(li, hi)。
请你返回一个整数数组count，长度为points.length，其中count[j]是 包含 第j个点的矩形数目。
如果0 <= xj <= li 且0 <= yj <= hi，那么我们说第i个矩形包含第j个点。
如果一个点刚好在矩形的 边上，这个点也被视为被矩形包含。
示例 1：输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]输出：[2,1]
解释：第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目为 2 。
包含点 (1, 4) 的矩形数目为 1 。
所以，我们返回 [2, 1] 。
示例 2：输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]] 输出：[1,3]
解释：第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目为 1 。
包含点 (1, 1) 的矩形数目为 3 。
所以，我们返回 [1, 3] 。
提示：1 <= rectangles.length, points.length <= 5 * 104
rectangles[i].length == points[j].length == 2
1 <= li, xj <= 109
1 <= hi, yj <= 100
所有rectangles互不相同。
所有points 互不相同。

解题思路

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

func countRectangles(rectangles [][]int, points [][]int) []int {
	n := len(points)
	res := make([]int, n)
	arr := make([][]int, 101)
	for i := 0; i < len(rectangles); i++ {
		x, y := rectangles[i][0], rectangles[i][1]
		arr[y] = append(arr[y], x)
	}
	for i := 0; i < 101; i++ {
		sort.Ints(arr[i])
	}
	for i := 0; i < n; i++ {
		x, y := points[i][0], points[i][1]
		for j := y; j < 101; j++ {
			total := len(arr[j]) - sort.SearchInts(arr[j], x) // 总和-不满足要求的点
			res[i] = res[i] + total                           // 累加
		}
	}
	return res
}

# 2
func countRectangles(rectangles [][]int, points [][]int) []int {
	n := len(points)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		points[i] = append(points[i], i) // 添加下标
	}
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] > points[j][0] // 横坐标排序
	})
	sort.Slice(rectangles, func(i, j int) bool {
		return rectangles[i][0] > rectangles[j][0] // 横坐标排序
	})
	start := 0
	arr := make([]int, 101)
	for i := 0; i < n; i++ {
		x, y, index := points[i][0], points[i][1], points[i][2]
		for ; start < len(rectangles) && x <= rectangles[start][0]; start++ {
			arr[rectangles[start][1]]++ // 把纵坐标次数+1
		}
		for j := y; j < 101; j++ { // 遍历大于当前纵坐标
			res[index] = res[index] + arr[j] // 累加次数
		}
	}
	return res
}

2256.最小平均差(1)¶

题目

给你一个下标从 0开始长度为 n的整数数组nums。
下标 i处的 平均差指的是 nums中 前i + 1个元素平均值和 后n - i - 1个元素平均值的 绝对差。
两个平均值都需要 向下取整到最近的整数。
请你返回产生 最小平均差的下标。如果有多个下标最小平均差相等，请你返回 最小的一个下标。
注意：两个数的绝对差是两者差的绝对值。
n个元素的平均值是 n个元素之 和除以（整数除法）n。
0个元素的平均值视为0。
示例 1：输入：nums = [2,5,3,9,5,3] 输出：3
解释：- 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。
- 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。
- 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。
- 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。 
- 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。
- 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。
下标 3 处的平均差为最小平均差，所以返回 3 。
示例 2：输入：nums = [0] 输出：0
解释：唯一的下标是 0 ，所以我们返回 0 。
下标 0 处的平均差为：|0 / 1 - 0| = |0 - 0| = 0 。
提示：1 <= nums.length <= 105
0 <= nums[i] <= 105

解题思路

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

func minimumAverageDifference(nums []int) int {
	res := 0
	right := 0
	for _, v := range nums {
		right = right + v
	}
	left := 0
	minValue := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		left = left + nums[i]
		right = right - nums[i]
		var a, b int
		a = left / (i + 1)
		if i != len(nums)-1 {
			b = right / (len(nums) - i - 1)
		}
		if abs(a-b) < minValue { // 更新结果
			minValue = abs(a - b)
			res = i
		}
	}
	return res
}

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

2257.统计网格图中没有被保卫的格子数(2)¶

题目

给你两个整数m和n表示一个下标从0开始的m x n网格图。
同时给你两个二维整数数组guards 和walls，其中guards[i] = [rowi, coli]且walls[j] = [rowj, colj]，
分别表示第 i个警卫和第 j座墙所在的位置。
一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有格子，除非他们被一座墙或者另外一个警卫 挡住了视线。
如果一个格子能被 至少一个警卫看到，那么我们说这个格子被 保卫了。
请你返回空格子中，有多少个格子是 没被保卫的。
示例 1：输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]] 输出：7
解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子，所以我们返回 7 。
示例 2：输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]] 输出：4
解释：上图中，没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子，所以我们返回 4 。
提示：1 <= m, n <= 105
2 <= m * n <= 105
1 <= guards.length, walls.length <= 5 * 104
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= rowi, rowj < m
0 <= coli, colj < n
guards和walls中所有位置 互不相同。

解题思路

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

func countUnguarded(m int, n int, guards [][]int, walls [][]int) int {
	arr := make([][]int, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < len(walls); i++ {
		a, b := walls[i][0], walls[i][1]
		arr[a][b] = 'W'
	}
	for i := 0; i < len(guards); i++ {
		a, b := guards[i][0], guards[i][1]
		arr[a][b] = 'G'
	}
	for i := 0; i < len(guards); i++ {
		a, b := guards[i][0], guards[i][1]
		x, y := a, b-1
		for y >= 0 && arr[x][y] != 'G' && arr[x][y] != 'W' {
			arr[x][y] = 'B'
			y--
		}
		x, y = a-1, b
		for x >= 0 && arr[x][y] != 'G' && arr[x][y] != 'W' {
			arr[x][y] = 'B'
			x--
		}
		x, y = a, b+1
		for y < n && arr[x][y] != 'G' && arr[x][y] != 'W' {
			arr[x][y] = 'B'
			y++
		}
		x, y = a+1, b
		for x < m && arr[x][y] != 'G' && arr[x][y] != 'W' {
			arr[x][y] = 'B'
			x++
		}
	}
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if arr[i][j] == 0 {
				res++
			}
		}
	}
	return res
}

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

func countUnguarded(m int, n int, guards [][]int, walls [][]int) int {
	arr := make([][]int, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < len(walls); i++ {
		a, b := walls[i][0], walls[i][1]
		arr[a][b] = 1
	}
	for i := 0; i < len(guards); i++ {
		a, b := guards[i][0], guards[i][1]
		arr[a][b] = 2
	}
	for i := 0; i < len(guards); i++ {
		a, b := guards[i][0], guards[i][1]
		for k := 0; k < 4; k++ {
			x, y := a+dx[k], b+dy[k]
			for 0 <= x && x < m && 0 <= y && y < n && arr[x][y] != 1 && arr[x][y] != 2 {
				arr[x][y] = 3
				x, y = x+dx[k], y+dy[k]
			}
		}
	}
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if arr[i][j] == 0 {
				res++
			}
		}
	}
	return res
}

2260.必须拿起的最小连续卡牌数(1)¶

题目

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。
返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。
示例 1：输入：cards = [3,4,2,3,4,7] 输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。
示例 2：输入：cards = [1,0,5,3] 输出：-1
解释：无法找出含一对匹配卡牌的一组连续卡牌。
提示：1 <= cards.length <= 105
0 <= cards[i] <= 106

解题思路

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

func minimumCardPickup(cards []int) int {
	n := len(cards)
	res := n + 1
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		if v, ok := m[cards[i]]; ok && i-v+1 < res {
			res = i - v + 1
		}
		m[cards[i]] = i
	}
	if res == n+1 {
		return -1
	}
	return res
}

2261.含最多K个可整除元素的子数组(2)¶

题目

给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。
如果满足下述条件之一，则认为数组 nums1 和 nums2 是 不同 数组：
两数组长度 不同 ，或者
存在 至少 一个下标 i 满足 nums1[i] != nums2[i] 。
子数组 定义为：数组中的连续元素组成的一个 非空 序列。
示例 1：输入：nums = [2,3,3,2,2], k = 2, p = 2 输出：11
解释：位于下标 0、3 和 4 的元素都可以被 p = 2 整除。
共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素：
[2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。
注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。
子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。
示例 2：输入：nums = [1,2,3,4], k = 4, p = 1 输出：10
解释：nums 中的所有元素都可以被 p = 1 整除。
此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。
因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。
提示：1 <= nums.length <= 200
1 <= nums[i], p <= 200
1 <= k <= nums.length

解题思路

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

func countDistinct(nums []int, k int, p int) int {
	m := make(map[[200]int]bool)
	n := len(nums)
	for i := 0; i < n; i++ { // 左边界
		count := 0
		for j := i + 1; j <= n; j++ { // 右边界
			if nums[j-1]%p == 0 {
				count++
			}
			if count <= k {
				temp := [200]int{}
				for k := i; k < j; k++ {
					temp[k-i] = nums[k]
				}
				m[temp] = true
			}
		}
	}
	return len(m)
}

# 2
func countDistinct(nums []int, k int, p int) int {
	m := make(map[[200]int]bool)
	n := len(nums)
	for i := 0; i < n; i++ { // 左边界
		count := 0
		temp := [200]int{}
		for j := i; j < n; j++ { // 右边界
			if nums[j]%p == 0 {
				count++
			}
			temp[j-i] = nums[j]
			if count <= k {
				m[temp] = true
			}
		}
	}
	return len(m)
}

2265.统计值等于子树平均值的节点数(2)¶

题目

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
注意：n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
root 的 子树 由 root 和它的所有后代组成。
示例 1：输入：root = [4,8,5,0,1,null,6] 输出：5
解释：对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
对值为 0 的节点：子树的平均值 0 / 1 = 0 。
对值为 1 的节点：子树的平均值 1 / 1 = 1 。
对值为 6 的节点：子树的平均值 6 / 1 = 6 。
示例 2：输入：root = [1] 输出：1
解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。
提示：树中节点数目在范围 [1, 1000] 内
0 <= Node.val <= 1000

解题思路

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

var res int

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

func dfs(root *TreeNode) (sum, count int) {
	sum, count = root.Val, 1
	if root.Left != nil {
		sL, cL := dfs(root.Left)
		sum = sum + sL
		count = count + cL
	}
	if root.Right != nil {
		sR, cR := dfs(root.Right)
		sum = sum + sR
		count = count + cR
	}
	if sum/count == root.Val {
		res++
	}
	return sum, count
}

# 2
var res int

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

func dfs(root *TreeNode) (sum, count int) {
	if root == nil {
		return 0, 0
	}
	sL, cL := dfs(root.Left)
	sR, cR := dfs(root.Right)
	sum = root.Val + sL + sR
	count = 1 + cL + cR
	if sum/count == root.Val {
		res++
	}
	return sum, count
}

2266.统计打字方案数¶

题目¶

Alice 在给 Bob 用手机打字。数字到字母的 对应如下图所示。
为了 打出一个字母，Alice 需要 按对应字母 i次，i是该字母在这个按键上所处的位置。
比方说，为了按出字母's'，Alice 需要按'7'四次。类似的， Alice 需要按'5'两次得到字母'k'。
注意，数字'0' 和'1'不映射到任何字母，所以Alice 不使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息。
比方说，Alice 发出的信息为"bob"，Bob 将收到字符串"2266622"。
给你一个字符串pressedKeys，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息。
由于答案可能很大，将它对109 + 7取余 后返回。
示例 1：输入：pressedKeys = "22233" 输出：8
解释：Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。
示例 2：输入：pressedKeys = "222222222222222222222222222222222222" 输出：82876089
解释：总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 109 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。
提示：1 <= pressedKeys.length <= 105
pressedKeys 只包含数字'2'到'9'。

解题思路¶

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

2270.分割数组的方案数(1)¶

题目

给你一个下标从 0开始长度为 n的整数数组nums。
如果以下描述为真，那么 nums在下标 i处有一个 合法的分割：
前i + 1个元素的和 大于等于剩下的n - i - 1个元素的和。
下标 i的右边 至少有一个元素，也就是说下标i满足0 <= i < n - 1。
请你返回nums中的合法分割方案数。
示例 1：输入：nums = [10,4,-8,7] 输出：2
解释：总共有 3 种不同的方案可以将 nums 分割成两个非空的部分：
- 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。
因为 10 >= 3 ，所以 i = 0 是一个合法的分割。
- 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。
因为 14 >= -1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。
因为 6 < 7 ，所以 i = 2 不是一个合法的分割。
所以 nums 中总共合法分割方案受为 2 。
示例 2：输入：nums = [2,3,1,0] 输出：2
解释：总共有 2 种 nums 的合法分割：
- 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。
因为 5 >= 1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。
因为 6 >= 0 ，所以 i = 2 是一个合法的分割。
提示：2 <= nums.length <= 105
-105 <= nums[i] <= 105

解题思路

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

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

2271.毯子覆盖的最多白色砖块数(3)¶

题目

给你一个二维整数数组tiles，其中tiles[i] = [li, ri]，表示所有在li <= j <= ri之间的每个瓷砖位置 j都被涂成了白色。
同时给你一个整数carpetLen，表示可以放在任何位置的一块毯子。
请你返回使用这块毯子，最多可以盖住多少块瓷砖。
示例 1：输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10 输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。
示例 2：输入：tiles = [[10,11],[1,1]], carpetLen = 2 输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。
提示：1 <= tiles.length <= 5 * 104
tiles[i].length == 2
1 <= li <= ri <= 109
1 <= carpetLen <= 109
tiles互相 不会重叠。

解题思路

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

func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
	res := 0
	sort.Slice(tiles, func(i, j int) bool {
		return tiles[i][0] < tiles[j][0]
	})
	count := 0
	left := 0
	for right := 0; right < len(tiles); right++ {
		l, r := tiles[right][0], tiles[right][1]
		count = count + r - l + 1
		for tiles[left][1]+carpetLen-1 < r { // 左边瓷砖右边界+毯子 无法覆盖右边瓷砖右边界：left指针右移
			count = count - (tiles[left][1] - tiles[left][0] + 1)
			left++
		}
		leftNum := r - tiles[left][0] - carpetLen + 1 // 未覆盖的数量：左边不在瓷砖内部的数量
		if leftNum < 0 {                              // 毯子够长：毯子左侧有多余
			leftNum = 0
		}
		res = max(res, count-leftNum)
	}
	return res
}

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

# 2
func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
	res := 0
	sort.Slice(tiles, func(i, j int) bool {
		return tiles[i][0] < tiles[j][0]
	})
	count := 0
	right := 0
	n := len(tiles)
	for left := 0; left < n; left++ {
		for right < n && tiles[right][1]-tiles[left][0]+1 < carpetLen { // 左边瓷砖左边界+毯子 能覆盖右边瓷砖右边界：right指针右移
			count = count + (tiles[right][1] - tiles[right][0] + 1)
			right++
		}
		if right < n {
			rightNum := tiles[left][0] + carpetLen - tiles[right][0] // 右边覆盖的数量：右边在瓷砖内部的数量
			if rightNum < 0 {                                        // 毯子不够长，覆盖不到右边
				rightNum = 0
			}
			res = max(res, count+rightNum)
		} else {
			res = max(res, count)
		}
		count = count - (tiles[left][1] - tiles[left][0] + 1)
	}
	return res
}

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

# 3
func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
	res := 0
	sort.Slice(tiles, func(i, j int) bool {
		return tiles[i][0] < tiles[j][0]
	})
	n := len(tiles)
	arr := make([]int, n+1)

	for i := 0; i < n; i++ {
		v := tiles[i][1] - tiles[i][0] + 1
		arr[i+1] = arr[i] + v
	}
	for i := 0; i < n; i++ {
		right := tiles[i][0] + carpetLen - 1       // 右边界
		index := sort.Search(n, func(j int) bool { // 右边界>=right的下标
			return tiles[j][1] >= right
		})
		if index >= n {
			res = max(res, arr[n]-arr[i])
		} else {
			rightNum := right - tiles[index][0] + 1 // 右边覆盖的数量：右边在瓷砖内部的数量
			if rightNum <= 0 {                      // 毯子不够长，覆盖不到右边
				rightNum = 0
			}
			res = max(res, arr[index]-arr[i]+rightNum)
		}
	}
	return res
}

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

2274.不含特殊楼层的最大连续楼层数(2)¶

题目

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。
给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。
另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。
返回不含特殊楼层的 最大 连续楼层数。
示例 1：输入：bottom = 2, top = 9, special = [4,6] 输出：3
解释：下面列出的是不含特殊楼层的连续楼层范围：
- (2, 3) ，楼层数为 2 。
- (5, 5) ，楼层数为 1 。
- (7, 9) ，楼层数为 3 。
因此，返回最大连续楼层数 3 。
示例 2：输入：bottom = 6, top = 8, special = [7,6,8] 输出：0
解释：每层楼都被规划为特殊楼层，所以返回 0 。
提示 1 <= special.length <= 105
1 <= bottom <= special[i] <= top <= 109
special 中的所有值 互不相同

解题思路

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

func maxConsecutive(bottom int, top int, special []int) int {
	res := 0
	sort.Ints(special)
	for i := 0; i < len(special); i++ {
		if i == 0 {
			res = max(res, special[i]-bottom) // 跟bottom比
		} else {
			res = max(res, special[i]-special[i-1]-1)
		}
		if i == len(special)-1 { // top跟最大比
			res = max(res, top-special[i])
		}
	}
	return res
}

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

# 2
func maxConsecutive(bottom int, top int, special []int) int {
	res := 0
	special = append(special, bottom-1, top+1) // 补齐
	sort.Ints(special)
	for i := 0; i < len(special)-1; i++ {
		res = max(res, special[i+1]-special[i]-1)
	}
	return res
}

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

2275.按位与结果大于零的最长组合(2)¶

题目

对数组nums 执行 按位与 相当于对数组nums 中的所有整数执行 按位与 。
例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
同样，对 nums = [7] 而言，按位与等于 7 。
给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 
candidates 中的每个数字在每种组合中只能使用 一次 。
返回按位与结果大于 0 的 最长 组合的长度。
示例 1：输入：candidates = [16,17,71,62,12,24,14] 输出：4
解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合长度是 4 。
可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
注意，符合长度最大的组合可能不止一种。
例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
示例 2：输入：candidates = [8,8] 输出：2
解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ，所以返回 2 。
提示：1 <= candidates.length <= 105
1 <= candidates[i] <= 107

解题思路

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

func largestCombination(candidates []int) int {
	arr := [32]int{}
	for i := 0; i < len(candidates); i++ {
		v := candidates[i]
		j := 0
		for v > 0 {
			if v%2 == 1 {
				arr[j]++
			}
			v = v / 2
			j++
		}
	}
	res := 0
	for i := 0; i < 32; i++ {
		res = max(res, arr[i]) // 计算二进制1出现最多的次数
	}
	return res
}

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

# 2
func largestCombination(candidates []int) int {
	res := 0
	for i := 0; i < 32; i++ {
		count := 0
		for j := 0; j < len(candidates); j++ {
			if (candidates[j]>>i)%2 == 1 {
				count++
			}
		}
		res = max(res, count) // 计算二进制1出现最多的次数
	}
	return res
}

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

2279.装满石头的背包的最大数量(1)¶

题目

现有编号从0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。
第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。
另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
示例 1：输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 输出：3
解释：1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
示例 2：输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 输出：3
解释：8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。
提示：n == capacity.length == rocks.length
1 <= n <= 5 * 104
1 <= capacity[i] <= 109
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 109

解题思路

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

func maximumBags(capacity []int, rocks []int, additionalRocks int) int {
	res := 0
	for i := 0; i < len(capacity); i++ {
		capacity[i] = capacity[i] - rocks[i]
	}
	sort.Ints(capacity)
	for i := 0; i < len(capacity); i++ {
		if capacity[i] <= additionalRocks {
			res++
			additionalRocks = additionalRocks - capacity[i]
		} else {
			break
		}
	}
	return res
}

2280.表示一个折线图的最少线段数(1)¶

题目

给你一个二维整数数组stockPrices ，其中stockPrices[i] = [dayi, pricei]表示股票在dayi的价格为pricei。
折线图是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：
请你返回要表示一个折线图所需要的 最少线段数。
示例 1：输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]] 输出：3
解释：上图为输入对应的图，横坐标表示日期，纵坐标表示价格。
以下 3 个线段可以表示折线图：
- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。
- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。
- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。
可以证明，无法用少于 3 条线段表示这个折线图。
示例 2：输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]] 输出：1
解释：如上图所示，折线图可以用一条线段表示。
提示：1 <= stockPrices.length <= 105
stockPrices[i].length == 2
1 <= dayi, pricei <= 109
所有dayi互不相同。

解题思路

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

func minimumLines(stockPrices [][]int) int {
	sort.Slice(stockPrices, func(i, j int) bool {
		return stockPrices[i][0] < stockPrices[j][0]
	})
	res := 0
	dx, dy := 0, 0
	for i := 1; i < len(stockPrices); i++ {
		x := stockPrices[i][0] - stockPrices[i-1][0]
		y := stockPrices[i][1] - stockPrices[i-1][1]
		if i == 1 {
			dx, dy = x, y
			res++
		} else if dx*y != x*dy { // y/x = dy/dx =>  dx*y == x*dy
			dx, dy = x, y
			res++
		}
	}
	return res
}

2284.最多单词数的发件人(2)¶

题目

给你一个聊天记录，共包含 n条信息。给你两个字符串数组messages 和senders，
其中messages[i]是senders[i]发出的一条信息。
一条 信息是若干用单个空格连接的 单词，信息开头和结尾不会有多余空格。
发件人的 单词计数是这个发件人总共发出的 单词数。注意，一个发件人可能会发出多于一条信息。
请你返回发出单词数 最多的发件人名字。如果有多个发件人发出最多单词数，请你返回 字典序最大的名字。
注意：字典序里，大写字母小于小写字母。"Alice" 和"alice"是不同的名字。
示例 1：输入：messages = ["Hello userTwooo","Hi userThree","Wonderful day Alice","Nice day userThree"], 
senders = ["Alice","userTwo","userThree","Alice"]输出："Alice"
解释：Alice 总共发出了 2 + 3 = 5 个单词。
userTwo 发出了 2 个单词。
userThree 发出了 3 个单词。
由于 Alice 发出单词数最多，所以我们返回 "Alice" 。
示例 2：输入：messages = ["How is leetcode for everyone","Leetcode is useful for practice"],
senders = ["Bob","Charlie"]输出："Charlie"
解释：Bob 总共发出了 5 个单词。
Charlie 总共发出了 5 个单词。
由于最多单词数打平，返回字典序最大的名字，也就是 Charlie 。
提示：n == messages.length == senders.length
1 <= n <= 104
1 <= messages[i].length <= 100
1 <= senders[i].length <= 10
messages[i]包含大写字母、小写字母和' '。
messages[i]中所有单词都由 单个空格隔开。
messages[i]不包含前导和后缀空格。
senders[i]只包含大写英文字母和小写英文字母。

解题思路

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

func largestWordCount(messages []string, senders []string) string {
	res := ""
	maxValue := 0
	m := make(map[string]int)
	for i := 0; i < len(senders); i++ {
		count := len(strings.Fields(messages[i]))
		m[senders[i]] = m[senders[i]] + count
		if m[senders[i]] > maxValue {
			maxValue = m[senders[i]]
			res = senders[i]
		} else if m[senders[i]] == maxValue && senders[i] > res {
			res = senders[i]
		}
	}
	return res
}

# 2
func largestWordCount(messages []string, senders []string) string {
	res := ""
	maxValue := 0
	m := make(map[string]int)
	for i := 0; i < len(senders); i++ {
		count := strings.Count(messages[i], " ") + 1
		m[senders[i]] = m[senders[i]] + count
		if m[senders[i]] > maxValue {
			maxValue = m[senders[i]]
			res = senders[i]
		} else if m[senders[i]] == maxValue && senders[i] > res {
			res = senders[i]
		}
	}
	return res
}

2285.道路的最大总重要性(1)¶

题目

给你一个整数n，表示一个国家里的城市数目。城市编号为0到n - 1。
给你一个二维整数数组roads，其中roads[i] = [ai, bi]表示城市ai和bi之间有一条双向道路。
你需要给每个城市安排一个从 1到 n之间的整数值，且每个值只能被使用 一次。
道路的 重要性定义为这条道路连接的两座城市数值 之和。
请你返回在最优安排下，所有道路重要性 之和 最大为多少。
示例 1：输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：43
解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。
- 道路 (0,1) 重要性为 2 + 4 = 6 。
- 道路 (1,2) 重要性为 4 + 5 = 9 。
- 道路 (2,3) 重要性为 5 + 3 = 8 。
- 道路 (0,2) 重要性为 2 + 5 = 7 。
- 道路 (1,3) 重要性为 4 + 3 = 7 。
- 道路 (2,4) 重要性为 5 + 1 = 6 。
所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。
可以证明，重要性之和不可能超过 43 。
示例 2：输入：n = 5, roads = [[0,3],[2,4],[1,3]] 输出：20
解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。
- 道路 (0,3) 重要性为 4 + 5 = 9 。
- 道路 (2,4) 重要性为 2 + 1 = 3 。
- 道路 (1,3) 重要性为 3 + 5 = 8 。
所有道路重要性之和为 9 + 3 + 8 = 20 。
可以证明，重要性之和不可能超过 20 。
提示：2 <= n <= 5 * 104
1 <= roads.length <= 5 * 104
roads[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
没有重复道路。

解题思路

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

func maximumImportance(n int, roads [][]int) int64 {
	arr := make([]int, n)
	for i := 0; i < len(roads); i++ {
		a, b := roads[i][0], roads[i][1]
		arr[a]++
		arr[b]++
	}
	sort.Ints(arr)
	res := int64(0)
	for i := 1; i <= n; i++ {
		res = res + int64(arr[i-1])*int64(i)
	}
	return res
}

2288.价格减免(2)¶

题目

句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。
如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。
例如 "$100"、"$23" 和 "$6.75" 表示价格，而 "100"、"$" 和 "2$3" 不是。
注意：本题输入中的价格均为整数。
给你一个字符串 sentence 和一个整数 discount 。对于每个表示价格的单词，
都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。
返回表示修改后句子的字符串。
示例 1：输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
输出："there are $0.50 $1.00 and 5$ candies in the shop"
解释：表示价格的单词是 "$1" 和 "$2" 。 
- "$1" 减免 50% 为 "$0.50" ，所以 "$1" 替换为 "$0.50" 。
- "$2" 减免 50% 为 "$1" ，所以 "$1" 替换为 "$1.00" 。
示例 2：输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
解释：任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。
每个单词都替换为 "$0.00"。
提示：1 <= sentence.length <= 105
sentence 由小写英文字母、数字、' ' 和'$' 组成
sentence 不含前导和尾随空格
sentence 的所有单词都用单个空格分隔
所有价格都是 正 整数且不含前导零
所有价格 最多 为 10 位数字
0 <= discount <= 100

解题思路

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

func discountPrices(sentence string, discount int) string {
	arr := strings.Fields(sentence)
	for i := 0; i < len(arr); i++ {
		if arr[i][0] == '$' && len(arr[i]) > 1 &&
			strings.Count(arr[i], "$") == 1 && check(arr[i][1:]) == true {
			v, _ := strconv.Atoi(arr[i][1:])
			vf := float64(v) * float64(100-discount) / 100
			arr[i] = fmt.Sprintf("$%0.2f", vf)
		}
	}
	return strings.Join(arr, " ")
}

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

# 2
func discountPrices(sentence string, discount int) string {
	arr := strings.Fields(sentence)
	for i := 0; i < len(arr); i++ {
		if arr[i][0] == '$' {
			v, err := strconv.Atoi(arr[i][1:])
			if err == nil {
				vf := float64(v) * float64(100-discount) / 100
				arr[i] = fmt.Sprintf("$%0.2f", vf)
			}
		}
	}
	return strings.Join(arr, " ")
}

2294.划分数组使最大差为K(1)¶

题目

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。
在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。
子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。
示例 1：输入：nums = [3,6,1,2,5], k = 2 输出：2
解释：可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。
示例 2：输入：nums = [1,2,3], k = 1输出：2
解释：可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。
示例 3：输入：nums = [2,2,4,5], k = 0 输出：3
解释：可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。
提示：1 <= nums.length <= 105
0 <= nums[i] <= 105
0 <= k <= 105

解题思路

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

func partitionArray(nums []int, k int) int {
	res := 1
	sort.Ints(nums)
	minValue := nums[0]
	for i := 0; i < len(nums); i++ {
		// 贪心：依次从小往大开始，把连续的、满足最大最小差值<=k划分为1组
		// 只需要考虑一组内的最大最小值，无需考虑顺序（划分为1组即可）
		if nums[i]-minValue > k {
			res++
			minValue = nums[i]
		}
	}
	return res
}

2295.替换数组中的元素(1)¶

题目

给你一个下标从 0开始的数组nums，它包含 n个 互不相同的正整数。
请你对这个数组执行 m个操作，在第 i个操作中，你需要将数字operations[i][0] 替换成operations[i][1]。
题目保证在第 i个操作中：
operations[i][0]在nums中存在。
operations[i][1]在nums中不存在。
请你返回执行完所有操作后的数组。
示例 1：输入：nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]] 输出：[3,2,7,1]
解释：我们对 nums 执行以下操作：
- 将数字 1 替换为 3 。nums 变为 [3,2,4,6] 。
- 将数字 4 替换为 7 。nums 变为 [3,2,7,6] 。
- 将数字 6 替换为 1 。nums 变为 [3,2,7,1] 。
返回最终数组 [3,2,7,1] 。
示例 2：输入：nums = [1,2], operations = [[1,3],[2,1],[3,2]] 输出：[2,1]
解释：我们对 nums 执行以下操作：
- 将数字 1 替换为 3 。nums 变为 [3,2] 。
- 将数字 2 替换为 1 。nums 变为 [3,1] 。
- 将数字 3 替换为 2 。nums 变为 [2,1] 。
返回最终数组 [2,1] 。
提示：n == nums.length
m == operations.length
1 <= n, m <= 105
nums中所有数字 互不相同。
operations[i].length == 2
1 <= nums[i], operations[i][0], operations[i][1] <= 106
在执行第i 个操作时，operations[i][0]在nums中存在。
在执行第i个操作时，operations[i][1]在nums中不存在。

解题思路

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

func arrayChange(nums []int, operations [][]int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]] = i
	}
	for i := 0; i < len(operations); i++ {
		a, b := operations[i][0], operations[i][1]
		index := m[a]
		delete(m, a)
		m[b] = index
		nums[index] = b
	}
	return nums
}

# 2
func arrayChange(nums []int, operations [][]int) []int {
	m := make(map[int]int)
	for i := len(operations) - 1; i >= 0; i-- {
		a, b := operations[i][0], operations[i][1]
		if v, ok := m[b]; ok {
			b = v // 在后面出现过，使用最后的结果
		}
		m[a] = b
	}
	for i := 0; i < len(nums); i++ {
		if v, ok := m[nums[i]]; ok {
			nums[i] = v
		}
	}
	return nums
}

2300.咒语和药水的成功对数(2)¶

题目

给你两个正整数数组spells 和potions，长度分别为n 和m，
其中spells[i]表示第i个咒语的能量强度，potions[j]表示第j瓶药水的能量强度。
同时给你一个整数success。一个咒语和药水的能量强度 相乘 如果大于等于success，那么它们视为一对成功的组合。
请你返回一个长度为 n的整数数组pairs，其中pairs[i]是能跟第 i个咒语成功组合的 药水数目。
示例 1：输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7 输出：[4,0,3]
解释：- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。
示例 2：输入：spells = [3,1,2], potions = [8,5,8], success = 16 输出：[2,0,2]
解释：- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。
提示：n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

解题思路

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

func successfulPairs(spells []int, potions []int, success int64) []int {
	n := len(spells)
	res := make([]int, n)
	sort.Ints(potions)
	for i := 0; i < n; i++ {
		index := sort.Search(len(potions), func(j int) bool {
			return int64(potions[j])*int64(spells[i]) >= success
		})
		res[i] = len(potions) - index
	}
	return res
}

# 2
func successfulPairs(spells []int, potions []int, success int64) []int {
	sort.Ints(potions)
	for i := 0; i < len(spells); i++ {
		// xy>= success => y >= success/x => y > floor((success-1)/x)
		spells[i] = len(potions) - sort.SearchInts(potions, int(success-1)/spells[i]+1)
	}
	return spells
}

2201-2300-Hard¶

2209.用地毯覆盖后的最少白色砖块(2)¶

题目

给你一个下标从0开始的 二进制字符串floor，它表示地板上砖块的颜色。
floor[i] = '0'表示地板上第i块砖块的颜色是 黑色。
floor[i] = '1'表示地板上第i块砖块的颜色是 白色。
同时给你numCarpets 和carpetLen。你有numCarpets条黑色的地毯，每一条黑色的地毯长度都为carpetLen块砖块。
请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色砖块的数目 最小。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的 最少数目。
示例 1：输入：floor = "10110101", numCarpets = 2, carpetLen = 2 输出：2
解释：上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。
示例 2：输入：floor = "11111", numCarpets = 2, carpetLen = 3 输出：0
解释：上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。
提示：1 <= carpetLen <= floor.length <= 1000
floor[i] 要么是'0'，要么是'1'。
1 <= numCarpets <= 1000

解题思路

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

func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
	n := numCarpets
	m := len(floor)
	dp := make([][]int, n+1) // dp[i][j]=>表示i条毛毯覆盖前j块砖块时白色砖块的最少数目
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m)
	}
	dp[0][0] = int(floor[0] - '0')
	for j := 1; j < m; j++ {
		dp[0][j] = dp[0][j-1] + int(floor[j]-'0')
	}
	for i := 1; i <= n; i++ {
		for j := carpetLen; j < m; j++ { // 遍历覆盖终点
			// 不覆盖：dp[i][j-1]+int(floor[j]-'0')
			// 覆盖：dp[i-1][j-carpetLen]（其中j-carpetLen是起点）
			dp[i][j] = min(dp[i][j-1]+int(floor[j]-'0'), dp[i-1][j-carpetLen])
		}
	}
	return dp[n][m-1]
}

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

# 2
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
	n := numCarpets
	m := len(floor)
	dp := make([][]int, n+1) // dp[i][j]=>表示i条毛毯覆盖前j块砖块时白色砖块的最少数目
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m)
	}
	dp[0][0] = int(floor[0] - '0')
	for j := 1; j < m; j++ {
		dp[0][j] = dp[0][j-1] + int(floor[j]-'0')
	}
	for i := 1; i <= n; i++ {
		for j := 0; j < m; j++ { // 遍历覆盖终点
			if j < carpetLen {
				dp[i][j] = 0
				continue
			}
			// 不覆盖：dp[i][j-1]+int(floor[j]-'0')
			// 覆盖：dp[i-1][j-carpetLen]（其中j-carpetLen是起点）
			dp[i][j] = min(dp[i][j-1]+int(floor[j]-'0'), dp[i-1][j-carpetLen])
		}
	}
	return dp[n][m-1]
}

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

2213.由单个字符重复的最长子字符串¶

题目¶

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，
一个下标从 0 开始、长度也是 k 的整数 下标 数组queryIndices ，这两个都用来描述 k 个查询。
第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。
返回一个长度为 k 的数组 lengths ，
其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。
示例 1：输入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3] 输出：[3,3,4]
解释：- 第 1 次查询更新后 s = "bbbacc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。
- 第 2 次查询更新后 s = "bbbccc" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。
- 第 3 次查询更新后 s = "bbbbcc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。
因此，返回 [3,3,4] 。
示例 2：输入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1] 输出：[2,3]
解释：- 第 1 次查询更新后 s = "abazz" 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。
- 第 2 次查询更新后 s = "aaazz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。
因此，返回 [2,3] 。
提示：1 <= s.length <= 105
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 105
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	分组背包-动态规划-二维	O(n^3)	O(n^2)

func minimumRounds(tasks []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(tasks); i++ {
		m[tasks[i]]++
	}
	for _, v := range m {
		if v == 1 { // 1个直接返回
			return -1
		}
		if v%3 == 0 {
			res = res + v/3
		} else {
			res = res + v/3 + 1 // %v=1 拆成2+2；%v=2，拆成3+2
		}
	}
	return res
}

2218.从栈中取出K个硬币的最大面值和(2)¶

题目

一张桌子上总共有 n个硬币 栈。每个栈有 正整数个带面值的硬币。
每一次操作中，你可以从任意一个栈的 顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。
给你一个列表piles，其中piles[i]是一个整数数组，分别表示第 i个栈里 从顶到底的硬币面值。
同时给你一个正整数k，请你返回在恰好进行k次操作的前提下，你钱包里硬币面值之和最大为多少。
示例 1：输入：piles = [[1,100,3],[7,8,9]], k = 2 输出：101
解释：上图展示了几种选择 k 个硬币的不同方法。
我们可以得到的最大面值为 101 。
示例 2：输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7 输出：706
解释：如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。
提示：n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000

解题思路

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

func maxValueOfCoins(piles [][]int, k int) int {
	n := len(piles)
	dp := make([][]int, n+1) // 背包问题：dp[i][j]=>表示i个栈取j个硬币的最大值
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		length := len(piles[i-1])
		for j := 1; j <= k; j++ {
			dp[i][j] = dp[i-1][j]
			sum := 0
			for x := 1; x <= min(j, length); x++ { // 枚举第i个栈能取到的长度
				sum = sum + piles[i-1][x-1]                // 第i个栈的前缀和
				dp[i][j] = max(dp[i][j], dp[i-1][j-x]+sum) // x个在第i个栈取+j-x在前i-1个栈取:j减去x + x个前缀和
			}
		}
	}
	return dp[n][k]
}

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 maxValueOfCoins(piles [][]int, k int) int {
	n := len(piles)
	dp := make([]int, k+1) // 背包问题：dp[i]=>表示取i个硬币的最大值
	for i := 1; i <= n; i++ {
		length := len(piles[i-1])
		for j := k; j >= 1; j-- {
			sum := 0
			for x := 1; x <= min(j, length); x++ { // 枚举第i个栈能取到的长度
				sum = sum + piles[i-1][x-1]     // 第i个栈的前缀和
				dp[j] = max(dp[j], dp[j-x]+sum) // x个在第i个栈取+j-x在前i-1个栈取:j减去x + x个前缀和
			}
		}
	}
	return dp[k]
}

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
}

2223.构造字符串的总得分和¶

题目¶

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	分组背包-动态规划-二维	O(n^3)	O(n^2)

2227.加密解密字符串(1)¶

题目

给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。
另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。
请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。
字符串 加密 按下述步骤进行：
对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
在字符串中，用values[i] 替换字符 c 。
字符串 解密 按下述步骤进行：
将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。
如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
在字符串中，用 keys[i] 替换 s 。
实现 Encrypter 类：
Encrypter(char[] keys, String[] values, String[] dictionary) 用 keys、
values 和 dictionary 初始化 Encrypter 类。
String encrypt(String word1) 按上述加密过程完成对 word1 的加密，并返回加密后的字符串。
int decrypt(String word2) 统计并返回可以由 word2 解密得到且出现在 dictionary 中的字符串数目。
示例：输入：["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], 
["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
输出：[null, "eizfeiam", 2]
解释：
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], 
["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // 返回 "eizfeiam"。 
                          // 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2. 
                              // "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。 
                              // 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。 
                              // 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。
提示：1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
所有 keys[i] 和 dictionary[i] 互不相同
1 <= word1.length <= 2000
1 <= word2.length <= 200
所有 word1[i] 都出现在 keys 中
word2.length 是偶数
keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
至多调用 encrypt 和 decrypt 总计 200 次

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希+预处理	O(n^2)	O(n^2)

type Encrypter struct {
	arr [26]string
	m   map[string]int
}

func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
	arr := [26]string{}
	for i := 0; i < len(keys); i++ {
		arr[int(keys[i]-'a')] = values[i]
	}
	e := Encrypter{
		arr: arr,
		m:   map[string]int{},
	}
	// 加密所有值
	for i := 0; i < len(dictionary); i++ {
		e.m[e.Encrypt(dictionary[i])]++
	}
	return e
}

func (this *Encrypter) Encrypt(word1 string) string {
	res := make([]byte, 0)
	for i := 0; i < len(word1); i++ {
		v := this.arr[int(word1[i]-'a')]
		if v == "" {
			return ""
		}
		res = append(res, v...)
	}
	return string(res)
}

func (this *Encrypter) Decrypt(word2 string) int {
	return this.m[word2]
}

2246.相邻字符不同的最长路径(2)¶

题目

给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。
用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，
其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。
另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。
示例 1：输入：parent = [-1,0,0,1,1,2], s = "abacbe" 输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。 
示例 2：输入：parent = [-1,0,0,0], s = "aabc" 输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。
提示：n == parent.length == s.length
1 <= n <= 105
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

解题思路

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

var arr [][]int
var res int

func longestPath(parent []int, s string) int {
	res = 0
	n := len(parent)
	arr = make([][]int, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		arr[p] = append(arr[p], i)
	}
	dfs(0, s)
	return res + 1 // 加上自身
}

func dfs(x int, s string) int {
	result := 0 // 以该节点单边路径最大长度
	for i := 0; i < len(arr[x]); i++ {
		value := dfs(arr[x][i], s) + 1 // 子节点的最长路径
		if s[x] != s[arr[x][i]] {
			res = max(res, result+value) // 更新：子树的最长路径+子树的最长路径
			result = max(result, value)
		}
	}
	return result
}

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

# 2
var arr [][]int
var res int

func longestPath(parent []int, s string) int {
	res = 0
	n := len(parent)
	arr = make([][]int, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		arr[p] = append(arr[p], i)
	}
	dfs(0, s)
	return res
}

func dfs(x int, s string) int {
	var a, b int // 2个节点值 a>b
	for i := 0; i < len(arr[x]); i++ {
		v := dfs(arr[x][i], s)
		if s[x] != s[arr[x][i]] {
			if v > a {
				a, b = v, a
			} else if v > b {
				b = v
			}
		}
	}
	res = max(res, 1+a+b)
	return a + 1
}

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

2251.花期内花的数目¶

题目¶

给你一个下标从 0开始的二维整数数组flowers，其中flowers[i] = [starti, endi]
表示第i朵花的 花期从starti到endi（都 包含）。
同时给你一个下标从 0开始大小为 n的整数数组persons，persons[i]是第i个人来看花的时间。
请你返回一个大小为 n的整数数组answer，其中answer[i]是第i个人到达时在花期内花的数目。
示例 1：输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11] 输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。
示例 2：输入：flowers = [[1,10],[3,3]], persons = [3,3,2] 输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。
提示：1 <= flowers.length <= 5 * 104
flowers[i].length == 2
1 <= starti <= endi <= 109
1 <= persons.length <= 5 * 104
1 <= persons[i] <= 109

解题思路¶

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

2262.字符串的总引力(2)¶

题目

字符串的 引力 定义为：字符串中 不同 字符的数量。
例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。
给你一个字符串 s ，返回 其所有子字符串的总引力 。
子字符串 定义为：字符串中的一个连续字符序列。
示例 1：输入：s = "abbca" 输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。
示例 2：输入：s = "code" 输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。
提示：1 <= s.length <= 105
s 由小写英文字母组成

解题思路

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

func appealSum(s string) int64 {
	res := int64(0)
	n := len(s)
	m := make(map[int]int)
	for i := 0; i < 26; i++ {
		m[i] = -1 // 上一次出现的位置
	}
	sum := 0
	for i := 0; i < n; i++ {
		v := int(s[i] - 'a')
		// 1、新字符没出现：在sum基础上加上(i+1)
		// 2、新字符出现过：在sum基础上加上i-m[v](到上一次出现的距离，只加后一段)
		sum = sum + (i - m[v])
		res = res + int64(sum)
		m[v] = i
	}
	return res
}

# 2
func appealSum(s string) int64 {
	res := int64(0)
	n := len(s)
	dp := make([]int, n+1) // 以长度为i结尾的子字符串总引力
	m := make(map[int]int)
	for i := 0; i < 26; i++ {
		m[i] = -1 // 上一次出现的位置
	}
	for i := 0; i < n; i++ {
		v := int(s[i] - 'a')
		// 1、新字符没出现：在dp[i]基础上加上(i+1)
		// 2、新字符出现过：在dp[i]基础上加上i-m[v](到上一次出现的距离，只加后一段)
		dp[i+1] = dp[i] + (i - m[v])
		m[v] = i
	}
	for i := 1; i <= n; i++ {
		res = res + int64(dp[i])
	}
	return res
}

2276.统计区间中的整数数目¶

题目¶

解题思路¶

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

2290.到达角落需要移除障碍物的最小数目¶

题目¶

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
0 表示一个 空 单元格，
1 表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角(0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。
示例 1：输入：grid = [[0,1,1],[1,1,0],[1,1,0]] 输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。
示例 2：输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] 输出：0
解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 105
2 <= m * n <= 105
grid[i][j] 为 0 或 1
grid[0][0] == grid[m - 1][n - 1] == 0

解题思路¶

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