2101-2200-Easy
2108.找出数组中的第一个回文字符串(1)
给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 "" 。
回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。
示例 1：输入：words = ["abc","car","ada","racecar","cool"] 输出："ada"
解释：第一个回文字符串是 "ada" 。
注意，"racecar" 也是回文字符串，但它不是第一个。
示例 2：输入：words = ["notapalindrome","racecar"] 输出："racecar"
解释：第一个也是唯一一个回文字符串是 "racecar" 。
示例 3：输入：words = ["def","ghi"] 输出：""
解释：不存在回文字符串，所以返回一个空字符串。
提示：1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func firstPalindrome(words []string) string {
for i := 0; i < len(words); i++ {
if isPalindrome(words[i]) == true {
return words[i]
}
}
return ""
}
func isPalindrome(a string) bool {
i, j := 0, len(a)-1
for i < j {
if a[i] != a[j] {
return false
}
i++
j--
}
return true
}
2103.环和杆(2)
总计有 n 个环，环的颜色可以是红、绿、蓝中的一种。这些环分布穿在 10 根编号为 0 到 9 的杆上。
给你一个长度为 2n 的字符串 rings ，表示这 n 个环在杆上的分布。rings 中每两个字符形成一个 颜色位置对 ，用于描述每个环：
第 i 对中的 第一个 字符表示第 i 个环的 颜色（'R'、'G'、'B'）。
第 i 对中的 第二个 字符表示第 i 个环的 位置，也就是位于哪根杆上（'0' 到 '9'）。
例如，"R3G2B1" 表示：共有 n == 3 个环，红色的环在编号为 3 的杆上，绿色的环在编号为 2 的杆上，蓝色的环在编号为 1 的杆上。
找出所有集齐 全部三种颜色 环的杆，并返回这种杆的数量。
示例 1：输入：rings = "B0B6G0R6R0R6G9" 输出：1
解释：- 编号 0 的杆上有 3 个环，集齐全部颜色：红、绿、蓝。
- 编号 6 的杆上有 3 个环，但只有红、蓝两种颜色。
- 编号 9 的杆上只有 1 个绿色环。
因此，集齐全部三种颜色环的杆的数目为 1 。
示例 2：输入：rings = "B0R0G0R9R0B0G0" 输出：1
解释：- 编号 0 的杆上有 6 个环，集齐全部颜色：红、绿、蓝。
- 编号 9 的杆上只有 1 个红色环。
因此，集齐全部三种颜色环的杆的数目为 1 。
示例 3：输入：rings = "G4"输出：0
解释：只给了一个环，因此，不存在集齐全部三种颜色环的杆。
提示：rings.length == 2 * n
1 <= n <= 100
如 i 是 偶数 ，则rings[i] 的值可以取 'R'、'G' 或 'B'（下标从 0 开始计数）
如 i 是 奇数 ，则rings[i] 的值可以取 '0' 到 '9' 中的一个数字（下标从 0 开始计数）
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历+位运算 |
O(n) |
O(1) |
| 02 |
遍历+哈希 |
O(n) |
O(1) |
func countPoints(rings string) int {
m := map[byte]int{
'R': 1,
'G': 2,
'B': 4,
}
arr := make([]int, 10)
for i := 0; i < len(rings); i = i + 2 {
v := int(rings[i+1] - '0')
arr[v] = arr[v] | m[rings[i]]
}
res := 0
for i := 0; i < len(arr); i++ {
if arr[i] == 7 {
res++
}
}
return res
}
# 2
func countPoints(rings string) int {
m := make(map[byte]map[byte]bool)
for i := 0; i < 10; i++ {
m[byte(i+'0')] = make(map[byte]bool)
}
for i := 0; i < len(rings); i = i + 2 {
m[rings[i+1]][rings[i]] = true
}
res := 0
for _, v := range m {
if len(v) == 3 {
res++
}
}
return res
}
2114.句子中的最多单词数(2)
一个 句子由一些 单词以及它们之间的单个空格组成，句子的开头和结尾不会有多余空格。
给你一个字符串数组sentences，其中sentences[i]表示单个 句子。
请你返回单个句子里 单词的最多数目。
示例 1：输入：sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
输出：6
解释：- 第一个句子 "alice and bob love leetcode" 总共有 5 个单词。
- 第二个句子 "i think so too" 总共有 4 个单词。
- 第三个句子 "this is great thanks very much" 总共有 6 个单词。
所以，单个句子中有最多单词数的是第三个句子，总共有 6 个单词。
示例 2：输入：sentences = ["please wait", "continue to fight", "continue to win"]输出：3
解释：可能有多个句子有相同单词数。
这个例子中，第二个句子和第三个句子（加粗斜体）有相同数目的单词数。
提示：1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i]只包含小写英文字母和' '。
sentences[i]的开头和结尾都没有空格。
sentences[i]中所有单词由单个空格隔开。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
func mostWordsFound(sentences []string) int {
res := 0
for i := 0; i < len(sentences); i++ {
arr := strings.Fields(sentences[i])
if len(arr) > res {
res = len(arr)
}
}
return res
}
# 2
func mostWordsFound(sentences []string) int {
res := 0
for i := 0; i < len(sentences); i++ {
count := strings.Count(sentences[i], " ") + 1
if count > res {
res = count
}
}
return res
}
2119.反转两次的数字(1)
反转 一个整数意味着倒置它的所有位。
例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零 。
给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。
如果 reversed2 等于 num ，返回 true ；否则，返回 false 。
示例 1：输入：num = 526 输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。
示例 2：输入：num = 1800 输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。
示例 3：输入：num = 0 输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。
提示：0 <= num <= 106
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(1) |
O(1) |
func isSameAfterReversals(num int) bool {
return num == 0 || num%10 != 0
}
2124.检查是否所有A都在B之前(2)
给你一个 仅 由字符 'a' 和 'b' 组成的字符串 s 。
如果字符串中 每个 'a' 都出现在 每个 'b' 之前，返回 true ；否则，返回 false 。
示例 1：输入：s = "aaabbb" 输出：true
解释：'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。
示例 2：输入：s = "abab" 输出：false
解释：存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false 。
示例 3：输入：s = "bbb" 输出：true
解释：不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。
提示：1 <= s.length <= 100
s[i] 为 'a' 或 'b'
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(n) |
| 02 |
内置函数 |
O(n) |
O(1) |
func checkString(s string) bool {
arr := []byte(s)
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
return string(arr) == s
}
# 2
func checkString(s string) bool {
return strings.Contains(s, "ba") == false
}
2129.将标题首字母大写(1)
给你一个字符串title，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写：
如果单词的长度为1或者2，所有字母变成小写。
否则，将单词首字母大写，剩余字母变成小写。
请你返回 大写后的title。
示例 1：输入：title = "capiTalIze tHe titLe" 输出："Capitalize The Title"
解释：由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。
示例 2：输入：title = "First leTTeR of EACH Word" 出："First Letter of Each Word"
解释：单词 "of" 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。
示例 3：输入：title = "i lOve leetcode" 出："i Love Leetcode"
解释：单词 "i" 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。
提示：1 <= title.length <= 100
title由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
每个单词由大写和小写英文字母组成，且都是 非空的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
func capitalizeTitle(title string) string {
arr := strings.Fields(title)
for i := 0; i < len(arr); i++ {
arr[i] = strings.ToLower(arr[i])
if len(arr[i]) > 2 {
arr[i] = strings.Title(arr[i])
}
}
return strings.Join(arr, " ")
}
2133.检查是否每一行每一列都包含全部整数(1)
对一个大小为 n x n 的矩阵而言，如果其每一行和每一列都包含从 1 到 n 的 全部 整数（含 1 和 n），则认为该矩阵是一个 有效 矩阵。
给你一个大小为 n x n 的整数矩阵 matrix ，请你判断矩阵是否为一个有效矩阵：如果是，返回 true ；否则，返回 false 。
示例 1：输入：matrix = [[1,2,3],[3,1,2],[2,3,1]] 输出：true
解释：在此例中，n = 3 ，每一行和每一列都包含数字 1、2、3 。
因此，返回 true 。
示例 2：输入：matrix = [[1,1,1],[1,2,3],[1,2,3]] 输出：false
解释：在此例中，n = 3 ，但第一行和第一列不包含数字 2 和 3 。
因此，返回 false 。
提示：n == matrix.length == matrix[i].length
1 <= n <= 100
1 <= matrix[i][j] <= n
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
func checkValid(matrix [][]int) bool {
n, m := len(matrix), len(matrix[0])
for i := 0; i < n; i++ {
visited := make(map[int]bool)
for j := 0; j < m; j++ {
if visited[matrix[i][j]] == true {
return false
}
visited[matrix[i][j]] = true
}
}
for j := 0; j < m; j++ {
visited := make(map[int]bool)
for i := 0; i < n; i++ {
if visited[matrix[i][j]] == true {
return false
}
visited[matrix[i][j]] = true
}
}
return true
}
2138.将字符串拆分为若干长度为k的组(1)
字符串 s 可以按下述步骤划分为若干长度为 k 的组：
第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。
注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。
给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，
按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。
示例 1：输入：s = "abcdefghi", k = 3, fill = "x" 输出：["abc","def","ghi"]
解释：前 3 个字符是 "abc" ，形成第一组。
接下来 3 个字符是 "def" ，形成第二组。
最后 3 个字符是 "ghi" ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 "abc"、"def" 和 "ghi" 。
示例 2：输入：s = "abcdefghij", k = 3, fill = "x" 出：["abc","def","ghi","jxx"]
解释：与前一个例子类似，形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组，字符串中仅剩下字符 'j' 可以用。为了补全这一组，使用填充字符 'x' 两次。
因此，形成 4 组，分别是 "abc"、"def"、"ghi" 和 "jxx" 。
提示：1 <= s.length <= 100
s 仅由小写英文字母组成
1 <= k <= 100
fill 是一个小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func divideString(s string, k int, fill byte) []string {
n := len(s)
res := make([]string, 0)
for i := 0; i < n; i = i + k {
if i+k <= n {
res = append(res, s[i:i+k])
} else {
res = append(res, s[i:]+strings.Repeat(string(fill), k-(n-i)))
}
}
return res
}
2144.打折购买糖果的最小开销(1)
一家商店正在打折销售糖果。每购买 两个糖果，商店会 免费送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值。
比方说，总共有 4个糖果，价格分别为1，2，3和4，一位顾客买了价格为2 和3的糖果，那么他可以免费获得价格为 1的糖果，
但不能获得价格为4的糖果。
给你一个下标从 0开始的整数数组cost，其中cost[i]表示第i个糖果的价格，请你返回获得 所有糖果的 最小总开销。
示例 1：输入：cost = [1,2,3] 输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2：输入：cost = [6,5,7,9,2,2] 输出：23
解释：最小总开销购买糖果方案为：
- 购买价格为 9 和 7 的糖果
- 免费获得价格为 6 的糖果
- 购买价格为 5 和 2 的糖果
- 免费获得价格为 2 的最后一个糖果
因此，最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3：输入：cost = [5,5] 输出：10
解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。
提示：1 <= cost.length <= 100
1 <= cost[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
func minimumCost(cost []int) int {
sort.Slice(cost, func(i, j int) bool {
return cost[i] > cost[j]
})
res := 0
for i := 0; i < len(cost); i++ {
if i%3 != 2 {
res = res + cost[i]
}
}
return res
}
2148.元素计数(2)
给你一个整数数组 nums ，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。
示例 1：输入：nums = [11,7,2,15] 输出：2
解释：元素 7 ：严格较小元素是元素 2 ，严格较大元素是元素 11 。
元素 11 ：严格较小元素是元素 7 ，严格较大元素是元素 15 。
总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
示例 2：输入：nums = [-3,3,3,90] 输出：2
解释：元素 3 ：严格较小元素是元素 -3 ，严格较大元素是元素 90 。
由于有两个元素的值为 3 ，总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
提示：1 <= nums.length <= 100
-105 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func countElements(nums []int) int {
sort.Ints(nums)
minValue, maxValue := nums[0], nums[len(nums)-1]
res := 0
for i := 0; i < len(nums); i++ {
if nums[i] != minValue && nums[i] != maxValue {
res++
}
}
return res
}
# 2
func countElements(nums []int) int {
minValue, maxValue := nums[0], nums[0]
minCount, maxCount := 1, 1
for i := 1; i < len(nums); i++ {
if nums[i] > maxValue {
maxValue = nums[i]
maxCount = 1
} else if nums[i] == maxValue {
maxCount++
}
if nums[i] < minValue {
minValue = nums[i]
minCount = 1
} else if nums[i] == minValue {
minCount++
}
}
if maxValue == minValue {
return 0
}
return len(nums) - maxCount - minCount
}
2154.将找到的值乘以2(2)
给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。
接下来，你需要按下述步骤操作：
如果在 nums 中找到 original ，将 original乘以 2 ，得到新 original（即，令 original = 2 * original）。
否则，停止这一过程。
只要能在数组中找到新 original ，就对新 original 继续 重复 这一过程。
返回 original 的 最终 值。
示例 1：输入：nums = [5,3,6,1,12], original = 3 输出：24
解释： - 3 能在 nums 中找到。3 * 2 = 6 。
- 6 能在 nums 中找到。6 * 2 = 12 。
- 12 能在 nums 中找到。12 * 2 = 24 。
- 24 不能在 nums 中找到。因此，返回 24 。
示例 2：输入：nums = [2,7,9], original = 4 输出：4
解释：- 4 不能在 nums 中找到。因此，返回 4 。
提示：1 <= nums.length <= 1000
1 <= nums[i], original <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希 |
O(n) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
func findFinalValue(nums []int, original int) int {
m := make(map[int]bool)
for i := 0; i < len(nums); i++ {
m[nums[i]] = true
}
for m[original] == true {
original = original * 2
}
return original
}
# 2
func findFinalValue(nums []int, original int) int {
sort.Ints(nums)
for i := 0; i < len(nums); i++ {
if nums[i] == original {
original = original * 2
}
}
return original
}
2160.拆分数位后四位数字的最小和(1)
给你一个四位正整数num。请你使用 num中的 数位 ，将num拆成两个新的整数new1和new2。
new1 和new2中可以有前导 0，且num中 所有数位都必须使用。
比方说，给你num = 2932，你拥有的数位包括：两个2，一个9和一个3。
一些可能的[new1, new2]数对为[22, 93]，[23, 92]，[223, 9] 和[2, 329]。
请你返回可以得到的new1和 new2的 最小和。
示例 1：输入：num = 2932 输出：52
解释：可行的 [new1, new2] 数对为 [29, 23] ，[223, 9] 等等。
最小和为数对 [29, 23] 的和：29 + 23 = 52 。
示例 2：输入：num = 4009 输出：13
解释：可行的 [new1, new2] 数对为 [0, 49] ，[490, 0] 等等。
最小和为数对 [4, 9] 的和：4 + 9 = 13 。
提示：1000 <= num <= 9999
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(1) |
O(1) |
func minimumSum(num int) int {
arr := make([]int, 0)
for num > 0 {
arr = append(arr, num%10)
num = num / 10
}
sort.Ints(arr)
return 10*(arr[0]+arr[1]) + arr[2] + arr[3]
}
2164.对奇偶下标分别排序(1)
给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：
按 非递增 顺序排列 nums 奇数下标 上的所有值。
举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。
按 非递减 顺序排列 nums 偶数下标 上的所有值。
举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。
返回重排 nums 的值之后形成的数组。
示例 1：输入：nums = [4,1,2,3] 输出：[2,3,4,1]
解释：首先，按非递增顺序重排奇数下标（1 和 3）的值。
所以，nums 从 [4,1,2,3] 变为 [4,3,2,1] 。
然后，按非递减顺序重排偶数下标（0 和 2）的值。
所以，nums 从 [4,1,2,3] 变为 [2,3,4,1] 。
因此，重排之后形成的数组是 [2,3,4,1] 。
示例 2：输入：nums = [2,1] 输出：[2,1]
解释：由于只有一个奇数下标和一个偶数下标，所以不会发生重排。
形成的结果数组是 [2,1] ，和初始数组一样。
提示：1 <= nums.length <= 100
1 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(nlog(n)) |
O(n) |
func sortEvenOdd(nums []int) []int {
even, odd := make([]int, 0), make([]int, 0)
for i := 0; i < len(nums); i++ {
if i%2 == 0 {
even = append(even, nums[i])
} else {
odd = append(odd, nums[i])
}
}
sort.Ints(even)
sort.Slice(odd, func(i, j int) bool {
return odd[i] > odd[j]
})
for i := 0; i < len(even); i++ {
nums[2*i] = even[i]
}
for i := 0; i < len(odd); i++ {
nums[2*i+1] = odd[i]
}
return nums
}
2169.得到0的操作数(2)
给你两个 非负 整数 num1 和 num2 。
每一步 操作中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。
例如，num1 = 5 且 num2 = 4 ，应该用num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。
然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。
返回使 num1 = 0 或 num2 = 0 的 操作数 。
示例 1：输入：num1 = 2, num2 = 3 输出：3
解释：- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。
示例 2：输入：num1 = 10, num2 = 10 输出：1
解释：- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。
提示：0 <= num1, num2 <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学-辗转相除 |
O(log(n)) |
O(1) |
| 02 |
模拟 |
O(n) |
O(1) |
func countOperations(num1 int, num2 int) int {
res := 0
for num1 > 0 {
res = res + num2/num1
num1, num2 = num2%num1, num1
}
return res
}
# 2
func countOperations(num1 int, num2 int) int {
res := 0
for num1 > 0 && num2 > 0 {
if num1 >= num2 {
num1 = num1 - num2
} else {
num2 = num2 - num1
}
res++
}
return res
}
2176.统计数组中相等且可以被整除的数对(1)
给你一个下标从 0开始长度为 n的整数数组nums和一个整数k，
请你返回满足0 <= i < j < n，nums[i] == nums[j] 且(i * j)能被k整除的数对(i, j)的数目。
示例 1：输入：nums = [3,1,2,2,2,1,3], k = 2 输出：4
解释：总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。
示例 2：输入：nums = [1,2,3,4], k = 1 输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。
提示：1 <= nums.length <= 100
1 <= nums[i], k <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
func countPairs(nums []int, k int) int {
res := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] == nums[j] && i*j%k == 0 {
res++
}
}
}
return res
}
2180.统计各位数字之和为偶数的整数个数(2)
给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。
正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
示例 1：输入：num = 4 输出：2
解释：只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。
示例 2：输入：num = 30 输出：14
解释：只有 14 个整数满足小于等于 30 且各位数字之和为偶数，分别是：
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。
提示：1 <= num <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(1) |
| 02 |
数学 |
O(log(n)) |
O(1) |
func countEven(num int) int {
res := 0
for i := 2; i <= num; i++ {
sum := 0
temp := i
for temp > 0 {
sum = sum + temp%10
temp = temp / 10
}
if sum%2 == 0 {
res++
}
}
return res
}
# 2
func countEven(num int) int {
a := num / 10 * 5
b := 0
for temp := num / 10; temp > 0; temp = temp / 10 {
b = b + temp%10
}
if b%2 == 0 {
return a + (num%10+2)/2 - 1
}
return a + (num%10+1)/2 - 1
}
2185.统计包含给定前缀的字符串(2)
给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
示例 1：输入：words = ["pay","attention","practice","attend"], pref = "at" 输出：2
解释：以 "at" 作为前缀的字符串有两个，分别是："attention" 和 "attend" 。
示例 2：输入：words = ["leetcode","win","loops","success"], pref = "code" 输出：0
解释：不存在以 "code" 作为前缀的字符串。
提示：1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] 和 pref 由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func prefixCount(words []string, pref string) int {
res := 0
for i := 0; i < len(words); i++ {
if strings.HasPrefix(words[i], pref) {
res++
}
}
return res
}
# 2
func prefixCount(words []string, pref string) int {
res := 0
for i := 0; i < len(words); i++ {
if len(words[i]) >= len(pref) && words[i][:len(pref)] == pref {
res++
}
}
return res
}
2190.数组中紧跟key之后出现最频繁的数字(2)
给你一个下标从 0开始的整数数组nums，同时给你一个整数key，它在nums出现过。
统计在 nums数组中紧跟着 key后面出现的不同整数target的出现次数。换言之，target的出现次数为满足以下条件的 i的数目：
0 <= i <= n - 2
nums[i] == key且
nums[i + 1] == target。
请你返回出现 最多次数的target。测试数据保证出现次数最多的 target是唯一的。
示例 1：输入：nums = [1,100,200,1,100], key = 1 输出：100
解释：对于 target = 100 ，在下标 1 和 4 处出现过 2 次，且都紧跟着 key 。
没有其他整数在 key 后面紧跟着出现，所以我们返回 100 。
示例 2：输入：nums = [2,2,2,2,3], key = 2 输出：2
解释：对于 target = 2 ，在下标 1 ，2 和 3 处出现过 3 次，且都紧跟着 key 。
对于 target = 3 ，在下标 4 出出现过 1 次，且紧跟着 key 。
target = 2 是紧跟着 key 之后出现次数最多的数字，所以我们返回 2 。
提示：2 <= nums.length <= 1000
1 <= nums[i] <= 1000
测试数据保证答案是唯一的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希 |
O(n) |
O(n) |
| 02 |
哈希 |
O(n) |
O(n) |
func mostFrequent(nums []int, key int) int {
m := make(map[int]int)
for i := 0; i < len(nums)-1; i++ {
if nums[i] == key {
m[nums[i+1]]++
}
}
res, count := 0, 0
for k, v := range m {
if v > count {
count = v
res = k
}
}
return res
}
# 2
func mostFrequent(nums []int, key int) int {
m := make(map[int]int)
res, count := 0, 0
for i := 0; i < len(nums)-1; i++ {
if nums[i] == key {
m[nums[i+1]]++
if m[nums[i+1]] > count {
count = m[nums[i+1]]
res = nums[i+1]
}
}
}
return res
}
2191.将杂乱无章的数字排序(1)
给你一个下标从 0开始的整数数组mapping，它表示一个十进制数的映射规则，
mapping[i] = j表示这个规则下将数位i映射为数位 j。
一个整数 映射后的值为将原数字每一个数位 i（0 <= i <= 9）映射为mapping[i]。
另外给你一个整数数组nums，请你将数组nums中每个数按照它们映射后对应数字非递减顺序排序后返回。
注意：如果两个数字映射后对应的数字大小相同，则将它们按照输入中的 相对顺序排序。
nums中的元素只有在排序的时候需要按照映射后的值进行比较，返回的值应该是输入的元素本身。
示例 1：输入：mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38] 输出：[338,38,991]
解释：将数字 991 按照如下规则映射：
1. mapping[9] = 6 ，所有数位 9 都会变成 6 。
2. mapping[1] = 9 ，所有数位 1 都会变成 8 。
所以，991 映射的值为 669 。
338 映射为 007 ，去掉前导 0 后得到 7 。
38 映射为 07 ，去掉前导 0 后得到 7 。
由于 338 和 38 映射后的值相同，所以它们的前后顺序保留原数组中的相对位置关系，338 在 38 的前面。
所以，排序后的数组为 [338,38,991] 。
示例 2：输入：mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123] 输出：[123,456,789]
解释：789 映射为 789 ，456 映射为 456 ，123 映射为 123 。所以排序后数组为 [123,456,789] 。
提示：mapping.length == 10
0 <= mapping[i] <= 9
mapping[i]的值 互不相同。
1 <= nums.length <= 3 * 104
0 <= nums[i] < 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(1) |
func sortJumbled(mapping []int, nums []int) []int {
sort.SliceStable(nums, func(i, j int) bool {
return transfer(mapping, nums[i]) < transfer(mapping, nums[j])
})
return nums
}
func transfer(mapping []int, num int) int {
res := 0
if num == 0 {
return mapping[0]
}
v := 1
for ; num > 0; num = num / 10 {
res = res + mapping[num%10]*v
v = v * 10
}
return res
}
2194.Excel表中某个范围内的单元格(1)
Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：
<col> 即单元格的列号 c 。用英文字母表中的 字母 标识。
例如，第 1 列用 'A' 表示，第 2 列用 'B' 表示，第 3 列用 'C' 表示，以此类推。
<row> 即单元格的行号 r 。第 r 行就用 整数 r 标识。
给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，
其中 <col1> 表示 c1 列，<row1> 表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。
找出所有满足r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。
单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。
示例 1：输入：s = "K1:L2" 输出：["K1","K2","L1","L2"]
解释：上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。
示例 2：输入：s = "A1:F1" 输出：["A1","B1","C1","D1","E1","F1"]
解释：上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。
提示：s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s 由大写英文字母、数字、和 ':' 组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
func cellsInRange(s string) []string {
res := make([]string, 0)
for i := s[0]; i <= s[3]; i++ {
for j := s[1]; j <= s[4]; j++ {
res = append(res, string(i)+string(j))
}
}
return res
}
2200.找出数组中的所有K近邻下标(2)
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。
K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。
以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
示例 1：输入：nums = [3,4,9,1,3,9,5], key = 9, k = 1 输出：[1,2,3,4,5,6]
解释：因此，nums[2] == key 且 nums[5] == key 。
- 对下标 0 ，|0 - 2| > k 且 |0 - 5| > k ，所以不存在 j 使得 |0 - j| <= k 且 nums[j] == key 。
所以 0 不是一个 K 近邻下标。
- 对下标 1 ，|1 - 2| <= k 且 nums[2] == key ，所以 1 是一个 K 近邻下标。
- 对下标 2 ，|2 - 2| <= k 且 nums[2] == key ，所以 2 是一个 K 近邻下标。
- 对下标 3 ，|3 - 2| <= k 且 nums[2] == key ，所以 3 是一个 K 近邻下标。
- 对下标 4 ，|4 - 5| <= k 且 nums[5] == key ，所以 4 是一个 K 近邻下标。
- 对下标 5 ，|5 - 5| <= k 且 nums[5] == key ，所以 5 是一个 K 近邻下标。
- 对下标 6 ，|6 - 5| <= k 且 nums[5] == key ，所以 6 是一个 K 近邻下标。
因此，按递增顺序返回 [1,2,3,4,5,6] 。
示例 2：输入：nums = [2,2,2,2,2], key = 2, k = 2 输出：[0,1,2,3,4]
解释：对 nums 的所有下标 i ，总存在某个下标 j 使得 |i - j| <= k 且 nums[j] == key ，所以每个下标都是一个 K 近邻下标。
因此，返回 [0,1,2,3,4] 。
提示：1 <= nums.length <= 1000
1 <= nums[i] <= 1000
key 是数组 nums 中的一个整数
1 <= k <= nums.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func findKDistantIndices(nums []int, key int, k int) []int {
n := len(nums)
res := make([]int, 0)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if nums[j] == key && abs(i-j) <= k {
res = append(res, i)
break
}
}
}
return res
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func findKDistantIndices(nums []int, key int, k int) []int {
n := len(nums)
res := make([]int, 0)
right := 0
for j := 0; j < n; j++ {
if nums[j] == key {
left := max(right, j-k)
right = min(n-1, j+k) + 1
for i := left; i < right; i++ {
res = append(res, i)
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2101-2200-Medium
2101.引爆最多的炸弹(2)
给你一个炸弹列表。一个炸弹的 爆炸范围定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0开始的二维整数数组bombs表示，其中bombs[i] = [xi, yi, ri]。
xi 和yi表示第 i个炸弹的 X 和 Y 坐标，ri表示爆炸范围的 半径。
你需要选择引爆 一个炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，
这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组bombs，请你返回在引爆一个炸弹的前提下，最多能引爆的炸弹数目。
示例 1：输入：bombs = [[2,1,3],[6,1,4]] 输出：2
解释：上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。
示例 2：输入：bombs = [[1,1,5],[10,10,5]] 输出：1
解释：引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。
示例 3：输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]] 输出：5
解释：最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。
提示：1 <= bombs.length<= 100
bombs[i].length == 3
1 <= xi, yi, ri <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n^3) |
O(n^2) |
| 02 |
深度优先搜索 |
O(n^3) |
O(n^2) |
func maximumDetonation(bombs [][]int) int {
n := len(bombs)
arr := make([][]int, n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i != j && judge(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1], bombs[i][2]) == true {
arr[i] = append(arr[i], j)
}
}
}
res := 0
for i := 0; i < n; i++ {
count := 1
visited := make([]bool, n)
queue := make([]int, 0)
queue = append(queue, i)
visited[i] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for j := 0; j < len(arr[node]); j++ {
next := arr[node][j]
if visited[next] == false {
count++
queue = append(queue, next)
visited[next] = true
}
}
}
if count > res {
res = count
}
}
return res
}
func judge(a, b, c, d, r int) bool {
return r*r >= (a-c)*(a-c)+(b-d)*(b-d)
}
# 2
var arr [][]int
var count int
func maximumDetonation(bombs [][]int) int {
n := len(bombs)
arr = make([][]int, n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i != j && judge(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1], bombs[i][2]) == true {
arr[i] = append(arr[i], j)
}
}
}
res := 0
for i := 0; i < n; i++ {
count = 0
dfs(i, make([]bool, n))
if count > res {
res = count
}
}
return res
}
func dfs(start int, visited []bool) {
visited[start] = true
count++
for i := 0; i < len(arr[start]); i++ {
next := arr[start][i]
if visited[next] == false {
dfs(next, visited)
}
}
}
func judge(a, b, c, d, r int) bool {
return r*r >= (a-c)*(a-c)+(b-d)*(b-d)
}
2104.子数组范围和(2)
给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1：输入：nums = [1,2,3]输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
示例 2：输入：nums = [1,3,3]输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[3]，范围 = 3 - 3 = 0
[3]，范围 = 3 - 3 = 0
[1,3]，范围 = 3 - 1 = 2
[3,3]，范围 = 3 - 3 = 0
[1,3,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
示例 3：输入：nums = [4,-2,-3,4,1]输出：59
解释：nums 中所有子数组范围的和是 59
提示：1 <= nums.length <= 1000
-109 <= nums[i] <= 109
进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
单调栈 |
O(n) |
O(n) |
func subArrayRanges(nums []int) int64 {
res := int64(0)
for i := 0; i < len(nums); i++ {
minValue, maxValue := nums[i], nums[i]
for j := i + 1; j < len(nums); j++ {
if nums[j] > maxValue {
maxValue = nums[j]
}
if nums[j] < minValue {
minValue = nums[j]
}
res = res + int64(maxValue-minValue)
}
}
return res
}
# 2
func subArrayRanges(nums []int) int64 {
return int64(sumSubarrayMaxs(nums)) - int64(sumSubarrayMins(nums))
}
func sumSubarrayMins(arr []int) int {
res := 0
stack := make([]int, 0)
stack = append(stack, -1)
total := 0
for i := 0; i < len(arr); i++ {
for len(stack) > 1 && arr[i] < arr[stack[len(stack)-1]] {
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
total = total - arr[prev]*(prev-stack[len(stack)-1])
}
stack = append(stack, i)
total = total + arr[i]*(i-stack[len(stack)-2])
res = res + total
}
return res
}
func sumSubarrayMaxs(arr []int) int {
res := 0
stack := make([]int, 0)
stack = append(stack, -1)
total := 0
for i := 0; i < len(arr); i++ {
for len(stack) > 1 && arr[i] > arr[stack[len(stack)-1]] {
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
total = total - arr[prev]*(prev-stack[len(stack)-1])
}
stack = append(stack, i)
total = total + arr[i]*(i-stack[len(stack)-2])
res = res + total
}
return res
}
2105.给植物浇水II(2)
Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。
其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。
他们 同时 给植物浇水。
如果没有足够的水 完全 浇灌下一株植物，他 / 她会立即重新灌满浇水罐。
不管植物需要多少水，浇水所耗费的时间都是一样的。
不能 提前重新灌满水罐。
每株植物都可以由 Alice 或者 Bob 来浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水。
如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。
其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和capacityB 分别表示 Alice 和 Bob 水罐的容量。
返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例 1：输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5 输出：1
解释：- 最初，Alice 和 Bob 的水罐中各有 5 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
示例 2：输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4 输出：2
解释：- 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。
- 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。
示例 3：输入：plants = [5], capacityA = 10, capacityB = 8 输出：0
解释：- 只有一株植物
- Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。
示例 4：输入：plants = [1,2,4,4,5], capacityA = 6, capacityB = 5 输出：2
解释：- 最初，Alice 的水罐中有 6 单元水，Bob 的水罐中有 5 单元水。
- Alice 给植物 0 浇水，Bob 给植物 4 浇水。
- Alice 和 Bob 现在分别剩下 5 单元和 0 单元水。
- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 3 ，所以他先重新装满水，再浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 1 单元水。
- 由于 Alice 的水更多，所以由她给植物 2 浇水。然而，她水罐里的水不够给植物 2 ，所以她先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 1 + 0 = 2 。
示例 5：输入：plants = [2,2,5,2,2], capacityA = 5, capacityB = 5 输出：1
解释：Alice 和 Bob 都会到达中间的植物，并且此时他俩剩下的水量相同，所以 Alice 会给这株植物浇水。
由于她到达时只剩下 1 单元水，所以需要重新灌满水罐。
这是唯一一次需要重新灌满水罐的情况。所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 1 。
提示：n == plants.length
1 <= n <= 105
1 <= plants[i] <= 106
max(plants[i]) <= capacityA, capacityB <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟 |
O(n) |
O(1) |
func minimumRefill(plants []int, capacityA int, capacityB int) int {
res := 0
i, j := 0, len(plants)-1
a, b := capacityA, capacityB
for i <= j {
if i == j {
if a >= b && a < plants[i] {
res++
}
if a < b && b < plants[i] {
res++
}
return res
}
if a < plants[i] {
res++
a = capacityA - plants[i]
} else {
a = a - plants[i]
}
i++
if b < plants[j] {
res++
b = capacityB - plants[j]
} else {
b = b - plants[j]
}
j--
}
return res
}
2109.向字符串添加空格(1)
给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。
例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，
这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。
请你添加空格，并返回修改后的字符串。
示例 1：输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] 输出："Leetcode Helps Me Learn"
解释：下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。
示例 2：输入：s = "icodeinpython", spaces = [1,5,7,9] 输出："i code in py thon"
解释：下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。
示例 3：输入：s = "spacing", spaces = [0,1,2,3,4,5,6] 输出：" s p a c i n g"
解释：字符串的第一个字符前可以添加空格。
提示：1 <= s.length <= 3 * 105
s 仅由大小写英文字母组成
1 <= spaces.length <= 3 * 105
0 <= spaces[i] <= s.length - 1
spaces 中的所有值 严格递增
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func addSpaces(s string, spaces []int) string {
res := make([]byte, 0)
if len(spaces) == 0 {
return s
}
j := 0
for i := 0; i < len(s); i++ {
if j < len(spaces) && i == spaces[j] {
res = append(res, ' ')
j++
}
res = append(res, s[i])
}
return string(res)
}
2110.股票平滑下跌阶段的数目(1)
给你一个整数数组prices，表示一支股票的历史每日股价，其中prices[i]是这支股票第i天的价格。
一个 平滑下降的阶段定义为：对于连续一天或者多天，每日股价都比 前一日股价恰好少 1，这个阶段第一天的股价没有限制。
请你返回 平滑下降阶段的数目。
示例 1：输入：prices = [3,2,1,4] 输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。
示例 2：输入：prices = [8,6,7,7] 输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。
示例 3：输入：prices = [1] 输出：1
解释：总共有 1 个平滑下降阶段：[1]
提示：1 <= prices.length <= 105
1 <= prices[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func getDescentPeriods(prices []int) int64 {
res := int64(1)
if len(prices) == 1 {
return 1
}
count := int64(1)
for i := 1; i < len(prices); i++ {
if prices[i-1]-prices[i] == 1 {
count++
} else {
count = int64(1)
}
res = res + count
}
return res
}
2115.从给定原材料中找到所有可以做出的菜(1)
你有 n道不同菜的信息。给你一个字符串数组recipes和一个二维字符串数组ingredients。
第i道菜的名字为recipes[i]，如果你有它所有的原材料ingredients[i]，
那么你可以做出这道菜。一道菜的原材料可能是另一道菜，也就是说ingredients[i]可能包含recipes中另一个字符串。
同时给你一个字符串数组supplies，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
请你返回你可以做出的所有菜。你可以以 任意顺序返回它们。
注意两道菜在它们的原材料中可能互相包含。
示例 1：输入：recipes = ["bread"], ingredients = [["yeast","flour"]],
supplies = ["yeast","flour","corn"]输出：["bread"]
解释：我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
示例 2：输入：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]],
supplies = ["yeast","flour","meat"] 输出：["bread","sandwich"]
解释：我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
示例 3：输入：recipes = ["bread","sandwich","burger"],
ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]],
supplies = ["yeast","flour","meat"] 输出：["bread","sandwich","burger"]
解释：我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
我们可以做出 "burger" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。
示例 4：输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"] 输出：[]
解释：我们没法做出任何菜，因为我们只有原材料 "yeast" 。
提示：n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j]和supplies[k]只包含小写英文字母。
所有recipes 和supplies中的值互不相同。
ingredients[i]中的字符串互不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
拓扑排序 |
O(n) |
O(n) |
func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
res := make([]string, 0)
arr := make(map[string][]string)
inDegree := make(map[string]int)
for i := 0; i < len(recipes); i++ {
a := recipes[i]
for j := 0; j < len(ingredients[i]); j++ {
b := ingredients[i][j]
arr[b] = append(arr[b], a)
inDegree[a]++
}
}
for len(supplies) > 0 {
b := supplies[0]
supplies = supplies[1:]
for i := 0; i < len(arr[b]); i++ {
a := arr[b][i]
inDegree[a]--
if inDegree[a] == 0 {
res = append(res, a)
supplies = append(supplies, a)
}
}
}
return res
}
2116.判断一个括号字符串是否有效(1)
一个括号字符串是只由'(' 和')'组成的非空字符串。如果一个字符串满足下面 任意一个条件，那么它就是有效的：
字符串为().
它可以表示为 AB（A与B连接），其中A 和B都是有效括号字符串。
它可以表示为(A)，其中A是一个有效括号字符串。
给你一个括号字符串s和一个字符串locked，两者长度都为n。locked是一个二进制字符串，只包含'0'和'1'。对于locked中每一个下标i ：
如果locked[i]是'1'，你 不能改变s[i]。
如果locked[i]是'0'，你可以将s[i]变为'('或者')'。
如果你可以将 s变为有效括号字符串，请你返回true，否则返回false。
示例 1：输入：s = "))()))", locked = "010100" 输出：true
解释：locked[1] == '1' 和 locked[3] == '1' ，所以我们无法改变 s[1] 或者 s[3] 。
我们可以将 s[0] 和 s[4] 变为 '(' ，不改变 s[2] 和 s[5] ，使 s 变为有效字符串。
示例 2：输入：s = "()()", locked = "0000" 输出：true
解释：我们不需要做任何改变，因为 s 已经是有效字符串了。
示例 3：输入：s = ")", locked = "0" 输出：false
解释：locked 允许改变 s[0] 。
但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。
提示：n == s.length == locked.length
1 <= n <= 105
s[i]要么是'('要么是')'。
locked[i] 要么是'0'要么是'1' 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func canBeValid(s string, locked string) bool {
if len(s)%2 == 1 {
return false
}
var arr []byte
for i := 0; i < len(locked); i++ {
if locked[i] == '1' {
arr = append(arr, s[i])
} else {
arr = append(arr, '*')
}
}
return checkValidString(string(arr))
}
func checkValidString(s string) bool {
left, right := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == ')' {
right++
} else {
left++
}
if right > left {
return false
}
}
left, right = 0, 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
if left > right {
return false
}
}
return true
}
2120.执行所有后缀指令(1)
现有一个 n x n 大小的网格，左上角单元格坐标 (0, 0) ，右下角单元格坐标 (n - 1, n - 1) 。
给你整数 n 和一个整数数组 startPos ，
其中 startPos = [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。
另给你一个长度为 m 、下标从 0 开始的字符串 s ，其中 s[i] 是对机器人的第 i 条指令：
'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。
机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满足下述条件之一时，机器人将会停止：
下一条指令将会导致机器人移动到网格外。
没有指令可以执行。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是机器人从第 i条指令 开始，可以执行的 指令数目 。
示例 1：输入：n = 3, startPos = [0,1], s = "RRDDLU" 输出：[1,5,4,3,1,0]
解释：机器人从 startPos 出发，并从第 i 条指令开始执行：
- 0: "RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
- 1: "RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 2: "DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 3: "DLU" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 4: "LU" 在移动到网格外之前，只能执行一条 "L" 指令。
- 5: "U" 如果向上移动，将会移动到网格外。
示例 2：输入：n = 2, startPos = [1,1], s = "LURD" 输出：[4,1,0,0]
解释：- 0: "LURD"
- 1: "URD"
- 2: "RD"
- 3: "D"
示例 3：输入：n = 1, startPos = [0,0], s = "LRUD" 输出：[0,0,0,0]
解释：无论机器人从哪条指令开始执行，都会移动到网格外。
提示：m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= startrow, startcol < n
s 由 'L'、'R'、'U' 和 'D' 组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟 |
O(n^2) |
O(n) |
func executeInstructions(n int, startPos []int, s string) []int {
res := make([]int, 0)
for i := 0; i < len(s); i++ {
count := 0
a, b := startPos[0], startPos[1]
for j := i; j < len(s); j++ {
switch s[j] {
case 'L':
b--
case 'R':
b++
case 'U':
a--
case 'D':
a++
}
if 0 <= a && a < n && 0 <= b && b < n {
count++
} else {
break
}
}
res = append(res, count)
}
return res
}
2121.相同元素的间隔之和(2)
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。
返回一个长度为 n 的数组intervals ，
其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与 arr[i] 的值相同）的 间隔之和 。
注意：|x| 是 x 的绝对值。
示例 1：输入：arr = [2,1,3,1,2,3,3] 输出：[4,2,7,2,4,4,5]
解释：- 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4
- 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2
- 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7
- 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2
- 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4
- 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4
- 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5
示例 2：输入：arr = [10,5,10,10] 输出：[5,0,3,4]
解释：
- 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5
- 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0
- 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3
- 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4
提示：n == arr.length
1 <= n <= 105
1 <= arr[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
分组+前缀和 |
O(n) |
O(n) |
| 02 |
分组+遍历 |
O(n) |
O(n) |
func getDistances(arr []int) []int64 {
n := len(arr)
res := make([]int64, n)
m := make(map[int][]int)
for i := 0; i < n; i++ {
m[arr[i]] = append(m[arr[i]], i)
}
for _, v := range m {
arr := getSumAbsoluteDifferences(v)
for i := 0; i < len(v); i++ {
res[v[i]] = int64(arr[i])
}
}
return res
}
func getSumAbsoluteDifferences(nums []int) []int {
n := len(nums)
res := make([]int, 0)
arr := make([]int, 0)
sum := 0
for i := 0; i < n; i++ {
sum = sum + nums[i]
arr = append(arr, sum)
}
res = append(res, sum-n*nums[0])
for i := 1; i < n; i++ {
left := nums[i]*i - arr[i-1]
right := (sum - arr[i]) - nums[i]*(n-1-i)
res = append(res, left+right)
}
return res
}
# 2
func getDistances(arr []int) []int64 {
n := len(arr)
res := make([]int64, n)
m := make(map[int][]int)
for i := 0; i < n; i++ {
m[arr[i]] = append(m[arr[i]], i)
}
for _, v := range m {
arr := getSumAbsoluteDifferences(v)
for i := 0; i < len(v); i++ {
res[v[i]] = int64(arr[i])
}
}
return res
}
func getSumAbsoluteDifferences(nums []int) []int {
n := len(nums)
res := make([]int, 0)
right := 0
left := 0
for i := 1; i < n; i++ {
right = right + (nums[i] - nums[0])
}
res = append(res, right)
for i := 1; i < n; i++ {
diff := nums[i] - nums[i-1]
left = left + diff*i
right = right - diff*(n-i)
res = append(res, left+right)
}
return res
}
2125.银行中的激光束数量(2)
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，
表示银行的平面图，这是一个大小为 m x n 的二维矩阵。
bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。
对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：
两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
满足r1 < i < r2的 所有行i，都没有安全设备 。
激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。
返回银行中激光束的总数量。
示例 1：输入：bank = ["011001","000000","010100","001000"] 输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
* bank[0][1] -- bank[2][1]
* bank[0][1] -- bank[2][3]
* bank[0][2] -- bank[2][1]
* bank[0][2] -- bank[2][3]
* bank[0][5] -- bank[2][1]
* bank[0][5] -- bank[2][3]
* bank[2][1] -- bank[3][2]
* bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。
示例 2：输入：bank = ["000","111","000"] 输出：0
解释：不存在两个位于不同行的设备
提示：m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] 为 '0' 或 '1'
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n^2) |
O(1) |
func numberOfBeams(bank []string) int {
res := 0
prev := 0
n, m := len(bank), len(bank[0])
for i := 0; i < n; i++ {
cur := 0
for j := 0; j < m; j++ {
if bank[i][j] == '1' {
cur++
}
}
if cur == 0 {
continue
}
res = res + cur*prev
prev = cur
}
return res
}
# 2
func numberOfBeams(bank []string) int {
res := 0
prev := 0
for i := 0; i < len(bank); i++ {
cur := strings.Count(bank[i], "1")
if cur > 0 {
res = res + cur*prev
prev = cur
}
}
return res
}
2126.摧毁小行星(1)
给你一个整数mass，它表示一颗行星的初始质量。再给你一个整数数组asteroids，其中asteroids[i]是第i颗小行星的质量。
你可以按 任意顺序重新安排小行星的顺序，然后让行星跟它们发生碰撞。
如果行星碰撞时的质量 大于等于小行星的质量，那么小行星被 摧毁，并且行星会 获得这颗小行星的质量。否则，行星将被摧毁。
如果所有小行星 都能被摧毁，请返回 true，否则返回 false。
示例 1：输入：mass = 10, asteroids = [3,9,19,5,21] 输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。
示例 2：输入：mass = 5, asteroids = [4,9,23,4] 输出：false
解释：行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。
提示：1 <= mass <= 105
1 <= asteroids.length <= 105
1 <= asteroids[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
func asteroidsDestroyed(mass int, asteroids []int) bool {
sort.Ints(asteroids)
temp := int64(mass)
for i := 0; i < len(asteroids); i++ {
if int64(asteroids[i]) < temp {
return false
}
temp = temp + int64(asteroids[i])
}
return true
}
2130.链表最大孪生和(2)
在一个大小为n且 n为偶数 的链表中，对于0 <= i <= (n / 2) - 1的 i，
第i个节点（下标从 0开始）的孪生节点为第(n-1-i)个节点 。
比方说，n = 4那么节点0是节点 3的孪生节点，节点 1是节点 2的孪生节点。这是长度为 n = 4的链表中所有的孪生节点。
孪生和定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点head，请你返回链表的 最大孪生和。
示例1：输入：head = [5,4,2,1] 输出：6
解释：节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。
示例 2：输入：head = [4,2,2,3] 出：7
解释：链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。
示例 3：输入：head = [1,100000] 出：100001
解释：链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。
提示：链表的节点数目是[2, 105]中的偶数。
1 <= Node.val <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(n) |
| 02 |
快慢指针+反转链表 |
O(n) |
O(1) |
func pairSum(head *ListNode) int {
arr := make([]int, 0)
for head != nil {
arr = append(arr, head.Val)
head = head.Next
}
res := 0
for i := 0; i < len(arr)/2; i++ {
res = max(res, arr[i]+arr[len(arr)-1-i])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func pairSum(head *ListNode) int {
res := 0
slow, fast := head, head.Next
for fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
slow = reverseList(slow.Next)
fast = head
for slow != nil {
res = max(res, fast.Val+slow.Val)
fast = fast.Next
slow = slow.Next
}
return res
}
func reverseList(head *ListNode) *ListNode {
var result *ListNode
var temp *ListNode
for head != nil {
temp = head.Next
head.Next = result
result = head
head = temp
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2131.连接两字母单词得到的最长回文串(1)
给你一个字符串数组words。words中每个元素都是一个包含 两个小写英文字母的单词。
请你从 words中选择一些元素并按 任意顺序连接它们，并得到一个 尽可能长的回文串。每个元素 至多只能使用一次。
请你返回你能得到的最长回文串的 长度。如果没办法得到任何一个回文串，请你返回 0。
回文串指的是从前往后和从后往前读一样的字符串。
示例 1：输入：words = ["lc","cl","gg"] 输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
示例 2：输入：words = ["ab","ty","yt","lc","cl","ab"] 输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
示例 3：输入：words = ["cc","ll","xx"]
输出：2 解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
提示：1 <= words.length <= 105
words[i].length == 2
words[i]仅包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
func longestPalindrome(words []string) int {
res := 0
m := make(map[string]int)
for i := 0; i < len(words); i++ {
m[words[i]]++
}
mid := false
for k, v := range m {
str := string(k[1]) + string(k[0])
if k == str {
if v%2 == 1 {
mid = true
}
res = res + 2*(v/2*2)
} else {
res = res + 2*min(v, m[str])
}
}
if mid == true {
res = res + 2
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2134.最少交换次数来组合所有的1II(2)
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
示例 1：输入：nums = [0,1,0,1,1,0,0] 输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。
示例 2：输入：nums = [0,1,1,1,0,0,1,1,0] 输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。
示例 3：输入：nums = [1,1,0,0,1] 输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。
提示：1 <= nums.length <= 105
nums[i] 为 0 或者 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
滑动窗口 |
O(n) |
O(1) |
| 02 |
滑动窗口 |
O(n) |
O(n) |
func minSwaps(nums []int) int {
n := len(nums)
count := 0
for i := 0; i < n; i++ {
if nums[i] == 1 {
count++
}
}
res := 0
for i := 0; i < count; i++ {
if nums[i] == 0 {
res++
}
}
temp := res
for i := 0; i < n-1; i++ {
if nums[i] == 0 {
temp--
}
if nums[(i+count)%n] == 0 {
temp++
}
res = min(res, temp)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minSwaps(nums []int) int {
n := len(nums)
count := 0
for i := 0; i < n; i++ {
if nums[i] == 1 {
count++
}
}
res := n
nums = append(nums, nums...)
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + (1 - nums[i])
if i >= count {
sum = sum - (1 - nums[i-count])
res = min(res, sum)
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2135.统计追加字母可以获得的单词数(2)
给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。
对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作，
得到的结果与当前targetWords 字符串相等。
转换操作 如下面两步所述：
追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
例如，如果字符串为 "abc" ，那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾，但 'a' 就不行。
如果追加的是 'd' ，那么结果字符串为 "abcd" 。
重排 新字符串中的字母，可以按 任意 顺序重新排布字母。
例如，"abcd" 可以重排为 "acbd"、"bacd"、"cbda"，以此类推。注意，它也可以重排为 "abcd" 自身。
找出 targetWords 中有多少字符串能够由startWords 中的 任一 字符串执行上述转换操作获得。
返回 targetWords 中这类 字符串的数目 。
注意：你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。
startWords 中的字符串在这一过程中 不 发生实际变更。
示例 1：输入：startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] 输出：2
解释：
- 为了形成 targetWords[0] = "tack" ，可以选用 startWords[1] = "act" ，追加字母 'k' ，并重排 "actk" 为 "tack" 。
- startWords 中不存在可以用于获得 targetWords[1] = "act" 的字符串。
注意 "act" 确实存在于 startWords ，但是 必须 在重排前给这个字符串追加一个字母。
- 为了形成 targetWords[2] = "acti" ，可以选用 startWords[1] = "act" ，追加字母 'i' ，并重排 "acti" 为 "acti" 自身。
示例 2：输入：startWords = ["ab","a"], targetWords = ["abc","abcd"] 输出：1
解释：- 为了形成 targetWords[0] = "abc" ，可以选用 startWords[0] = "ab" ，追加字母 'c' ，并重排为 "abc" 。
- startWords 中不存在可以用于获得 targetWords[1] = "abcd" 的字符串。
提示：1 <= startWords.length, targetWords.length <= 5 * 104
1 <= startWords[i].length, targetWords[j].length <= 26
startWords 和 targetWords 中的每个字符串都仅由小写英文字母组成
在 startWords 或 targetWords 的任一字符串中，每个字母至多出现一次
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
枚举 |
O(n) |
O(n) |
| 02 |
枚举 |
O(n) |
O(n) |
func wordCount(startWords []string, targetWords []string) int {
m := make(map[int]bool)
for i := 0; i < len(startWords); i++ {
status := getStatus(startWords[i])
for j := 0; j < 26; j++ {
if (status>>j)&1 == 0 {
m[status|(1<<j)] = true
}
}
}
res := 0
for i := 0; i < len(targetWords); i++ {
if m[getStatus(targetWords[i])] == true {
res++
}
}
return res
}
func getStatus(str string) int {
status := 0
for i := 0; i < len(str); i++ {
v := int(str[i] - 'a')
status = status | (1 << v)
}
return status
}
# 2
func wordCount(startWords []string, targetWords []string) int {
m := make(map[int]bool)
for i := 0; i < len(startWords); i++ {
status := getStatus(startWords[i])
m[status] = true
}
res := 0
for i := 0; i < len(targetWords); i++ {
status := getStatus(targetWords[i])
for j := 0; j < len(targetWords[i]); j++ {
v := int(targetWords[i][j] - 'a')
if m[status^(1<<v)] == true {
res++
break
}
}
}
return res
}
func getStatus(str string) int {
status := 0
for i := 0; i < len(str); i++ {
v := int(str[i] - 'a')
status = status | (1 << v)
}
return status
}
2139.得到目标值的最少行动次数(1)
你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
在一次行动中，你可以做下述两种操作之一：
递增，将当前整数的值加 1（即， x = x + 1）。
加倍，使当前整数的值翻倍（即，x = 2 * x）。
在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。
示例 1：输入：target = 5, maxDoubles = 0 输出：4
解释：一直递增 1 直到得到 target 。
示例 2：输入：target = 19, maxDoubles = 2 输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。
示例 3：输入：target = 10, maxDoubles = 4 输出：4
解释：最初，x = 1 。
递增 1 次，x = 2 。
加倍 1 次，x = 4 。
递增 1 次，x = 5 。
加倍 1 次，x = 10 。
提示：1 <= target <= 109
0 <= maxDoubles <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(log(n)) |
O(1) |
func minMoves(target int, maxDoubles int) int {
res := 0
for maxDoubles > 0 && target != 1 {
res++
if target%2 == 1 {
target--
} else {
maxDoubles--
target = target / 2
}
}
res = res + (target - 1)
return res
}
2140.解决智力问题(2)
给你一个下标从 0开始的二维整数数组questions，其中questions[i] = [pointsi, brainpoweri]。
这个数组表示一场考试里的一系列题目，你需要 按顺序（也就是从问题 0开始依次解决），针对每个问题选择 解决或者 跳过操作。
解决问题 i将让你 获得pointsi的分数，但是你将 无法解决接下来的brainpoweri个问题
（即只能跳过接下来的 brainpoweri个问题）。如果你跳过问题i，你可以对下一个问题决定使用哪种操作。
比方说，给你questions = [[3, 2], [4, 3], [4, 4], [2, 5]]：
如果问题0被解决了， 那么你可以获得3分，但你不能解决问题1 和2。
如果你跳过问题0，且解决问题1，你将获得 4 分但是不能解决问题2 和3。
请你返回这场考试里你能获得的 最高分数。
示例 1：输入：questions = [[3,2],[4,3],[4,4],[2,5]] 输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
示例 2：输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] 输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
提示：1 <= questions.length <= 105
questions[i].length == 2
1 <= pointsi, brainpoweri <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
func mostPoints(questions [][]int) int64 {
n := len(questions)
dp := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
next := min(n, i+questions[i][1]+1)
dp[i] = max(dp[i+1], dp[next]+questions[i][0])
}
return int64(dp[0])
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func mostPoints(questions [][]int) int64 {
n := len(questions)
dp := make([]int, n+1)
for i := 0; i < n; i++ {
next := min(n, i+questions[i][1]+1)
dp[i+1] = max(dp[i+1], dp[i])
dp[next] = max(dp[next], dp[i]+questions[i][0])
}
return int64(dp[n])
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2145.统计隐藏数组数目(1)
给你一个下标从 0开始且长度为 n的整数数组differences，它表示一个长度为n + 1的隐藏数组相邻元素之间的差值。
更正式的表述为：我们将隐藏数组记作hidden，那么differences[i] = hidden[i + 1] - hidden[i]。
同时给你两个整数lower 和upper，它们表示隐藏数组中所有数字的值都在 闭区间[lower, upper]之间。
比方说，differences = [1, -3, 4]，lower = 1，upper = 6，
那么隐藏数组是一个长度为 4且所有值都在1和6（包含两者）之间的数组。
[3, 4, 1, 5] 和[4, 5, 2, 6]都是符合要求的隐藏数组。
[5, 6, 3, 7]不符合要求，因为它包含大于 6的元素。
[1, 2, 3, 4]不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0。
示例 1：输入：differences = [1,-3,4], lower = 1, upper = 6 输出：2
解释：符合要求的隐藏数组为：
- [3, 4, 1, 5]
- [4, 5, 2, 6]
所以返回 2 。
示例 2：输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5 输出：4
解释：符合要求的隐藏数组为：
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
所以返回 4 。
示例 3：输入：differences = [4,-7,2], lower = 3, upper = 6 输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。
提示：n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func numberOfArrays(differences []int, lower int, upper int) int {
sum := 0
maxValue, minValue := 0, 0
for i := 0; i < len(differences); i++ {
sum = sum + differences[i]
maxValue = max(maxValue, sum)
minValue = min(minValue, sum)
}
return max(0, upper-lower+1-(maxValue-minValue))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2146.价格范围内最高排名的K样物品(2)
给你一个下标从 0开始的二维整数数组grid，它的大小为m x n，表示一个商店中物品的分布图。数组中的整数含义为：
0表示无法穿越的一堵墙。
1表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费1步。
同时给你一个整数数组pricing 和start，其中pricing = [low, high] 且start = [row, col]，
表示你开始位置为(row, col)，同时你只对物品价格在闭区间[low, high]之内的物品感兴趣。同时给你一个整数k。
你想知道给定范围 内且 排名最高的 k件物品的 位置。排名按照优先级从高到低的以下规则制定：
距离：定义为从start到一件物品的最短路径需要的步数（较近距离的排名更高）。
价格：较低价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小行坐标的有更高优先级。
列坐标：较小列坐标的有更高优先级。
请你返回给定价格内排名最高的 k件物品的坐标，将它们按照排名排序后返回。
如果给定价格内少于 k件物品，那么请将它们的坐标全部返回。
示例 1：输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出：[[0,1],[1,1],[2,1]]
解释：起点为 (0,0) 。
价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。
这些物品的排名为：
- (0,1) 距离为 1
- (1,1) 距离为 2
- (2,1) 距离为 3
- (2,2) 距离为 4
所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。
示例 2：输入：grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
输出：[[2,1],[1,2]]
解释：起点为 (2,3) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。
这些物品的排名为：
- (2,1) 距离为 2 ，价格为 2
- (1,2) 距离为 2 ，价格为 3
- (1,1) 距离为 3
- (0,1) 距离为 4
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。
示例 3：输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]
解释：起点为 (0,0) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为：
- (2,1) 距离为 5
- (2,0) 距离为 6
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] <= 105
pricing.length == 2
2 <= low <= high <= 105
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n^2*log(n)) |
O(n^2) |
| 02 |
广度优先搜索 |
O(n^2*log(n)) |
O(n^2) |
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
n, m := len(grid), len(grid[0])
arr := make([][]int, 0)
queue := make([][]int, 0)
queue = append(queue, []int{start[0], start[1], 0})
if pricing[0] <= grid[start[0]][start[1]] && grid[start[0]][start[1]] <= pricing[1] {
arr = append(arr, []int{0, grid[start[0]][start[1]], start[0], start[1]})
}
grid[start[0]][start[1]] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
x, y, dis := node[0], node[1], node[2]
for i := 0; i < 4; i++ {
newX := x + dx[i]
newY := y + dy[i]
if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] > 0 {
if pricing[0] <= grid[newX][newY] && grid[newX][newY] <= pricing[1] {
arr = append(arr, []int{dis + 1, grid[newX][newY], newX, newY})
}
queue = append(queue, []int{newX, newY, dis + 1})
grid[newX][newY] = 0
}
}
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][0] == arr[j][0] {
if arr[i][1] == arr[j][1] {
if arr[i][2] == arr[j][2] {
return arr[i][3] < arr[j][3]
}
return arr[i][2] < arr[j][2]
}
return arr[i][1] < arr[j][1]
}
return arr[i][0] < arr[j][0]
})
res := make([][]int, 0)
for i := 0; i < k && i < len(arr); i++ {
res = append(res, []int{arr[i][2], arr[i][3]})
}
return res
}
# 2
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
n, m := len(grid), len(grid[0])
arr := make([][]int, 0)
queue := make([][]int, 0)
queue = append(queue, []int{start[0], start[1], 0})
grid[start[0]][start[1]] = -grid[start[0]][start[1]]
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
x, y, dis := node[0], node[1], node[2]
if pricing[0] <= -grid[x][y] && -grid[x][y] <= pricing[1] {
arr = append(arr, []int{dis, -grid[x][y], x, y})
}
for i := 0; i < 4; i++ {
newX := x + dx[i]
newY := y + dy[i]
if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] > 0 {
queue = append(queue, []int{newX, newY, dis + 1})
grid[newX][newY] = -grid[newX][newY]
}
}
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][0] == arr[j][0] {
if arr[i][1] == arr[j][1] {
if arr[i][2] == arr[j][2] {
return arr[i][3] < arr[j][3]
}
return arr[i][2] < arr[j][2]
}
return arr[i][1] < arr[j][1]
}
return arr[i][0] < arr[j][0]
})
res := make([][]int, 0)
for i := 0; i < k && i < len(arr); i++ {
res = append(res, []int{arr[i][2], arr[i][3]})
}
return res
}
2149.按符号重排数组(1)
给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。
你需要 重排 nums 中的元素，使修改后的数组满足下述条件：
任意连续 的两个整数 符号相反
对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。
重排元素满足上述条件后，返回修改后的数组。
示例 1：输入：nums = [3,1,-2,-5,2,-4] 输出：[3,-2,1,-5,2,-4]
解释：nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。
示例 2：输入：nums = [-1,1] 输出：[1,-1]
解释：1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。
提示：2 <= nums.length <= 2 * 105
nums.length 是 偶数
1 <= |nums[i]| <= 105
nums 由 相等 数量的正整数和负整数组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func rearrangeArray(nums []int) []int {
res := make([]int, len(nums))
i, j := 0, 1
for k := 0; k < len(nums); k++ {
if nums[k] > 0 {
res[i] = nums[k]
i = i + 2
} else {
res[j] = nums[k]
j = j + 2
}
}
return res
}
2150.找出数组中的所有孤独数字(2)
给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ，
且没有 相邻 数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。
返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。
示例 1：输入：nums = [10,6,5,8] 输出：[10,8]
解释：- 10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。
- 8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。
- 5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。
因此，nums 中的孤独数字是 [10, 8] 。
注意，也可以返回 [8, 10] 。
示例 2：输入：nums = [1,3,5,3] 输出：[1,5]
解释：- 1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。
- 5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。
- 3 不是一个孤独数字，因为它出现两次。
因此，nums 中的孤独数字是 [1, 5] 。
注意，也可以返回 [5, 1] 。
提示：1 <= nums.length <= 105
0 <= nums[i] <= 106
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(n) |
func findLonely(nums []int) []int {
res := make([]int, 0)
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for k, v := range m {
if v == 1 && m[k-1] == 0 && m[k+1] == 0 {
res = append(res, k)
}
}
return res
}
# 2
func findLonely(nums []int) []int {
res := make([]int, 0)
nums = append(nums, math.MinInt32)
nums = append(nums, math.MaxInt32)
sort.Ints(nums)
for i := 1; i < len(nums)-1; i++ {
if nums[i]-nums[i-1] > 1 && nums[i+1]-nums[i] > 1 {
res = append(res, nums[i])
}
}
return res
}
2155.分组得分最高的所有下标(2)
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。
nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），
而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1：输入：nums = [0,0,1,0] 输出：[2,4]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意，答案 [4,2] 也被视为正确答案。
示例 2：输入：nums = [0,0,0] 输出：[3]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
只有下标 3 可以得到最高的分组得分 3 。
示例 3：输入：nums = [1,1] 输出：[0]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。
- 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。
- 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。
只有下标 0 可以得到最高的分组得分 2 。
提示：n == nums.length
1 <= n <= 105
nums[i] 为 0 或 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func maxScoreIndices(nums []int) []int {
res := []int{0}
sum := 0
maxValue := 0
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
sum++
} else {
sum--
}
if sum > maxValue {
maxValue = sum
res = []int{i + 1}
} else if sum == maxValue {
res = append(res, i+1)
}
}
return res
}
# 2
func maxScoreIndices(nums []int) []int {
res := []int{0}
left, right := 0, 0
for i := 0; i < len(nums); i++ {
if nums[i] == 1 {
right++
}
}
maxValue := left + right
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
left++
} else {
right--
}
if left+right > maxValue {
maxValue = left + right
res = []int{i + 1}
} else if left+right == maxValue {
res = append(res, i+1)
}
}
return res
}
2156.查找给定哈希值的子串(1)
给定整数 p和 m，一个长度为 k且下标从 0开始的字符串s的哈希值按照如下函数计算：
hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
其中val(s[i])表示s[i]在字母表中的下标，从val('a') = 1 到val('z') = 26。
给你一个字符串s和整数power，modulo，k和hashValue。
请你返回 s中 第一个 长度为 k的 子串sub，满足hash(sub, power, modulo) == hashValue。
测试数据保证一定 存在至少一个这样的子串。
子串 定义为一个字符串中连续非空字符组成的序列。
示例 1：输入：s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0 输出："ee"
解释："ee" 的哈希值为 hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。
"ee" 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 "ee" 。
示例 2：输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32 输出："fbx"
解释："fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。
注意，"bxz" 的哈希值也为 32 ，但是它在字符串中比 "fbx" 更晚出现。
提示：1 <= k <= s.length <= 2 * 104
1 <= power, modulo <= 109
0 <= hashValue < modulo
s只包含小写英文字母。
测试数据保证一定 存在满足条件的子串。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
func subStrHash(s string, power int, modulo int, k int, hashValue int) string {
n := len(s)
p := 1
sum := 0
for i := n - 1; i >= n-k; i-- {
p = p * power % modulo
a := int(s[i]-'a') + 1
sum = (a + sum*power) % modulo
}
res := s[n-k:]
for i := n - k - 1; i >= 0; i-- {
a := int(s[i]-'a') + 1 + sum*power
b := (int(s[i+k]-'a') + 1) * p % modulo
sum = (a - b + modulo) % modulo
if sum == hashValue {
res = s[i : i+k]
}
}
return res
}
2161.根据给定数字划分数组(3)
给你一个下标从 0开始的整数数组nums和一个整数pivot。请你将nums重新排列，使得以下条件均成立：
所有小于pivot的元素都出现在所有大于pivot的元素之前。
所有等于pivot的元素都出现在小于和大于 pivot的元素 中间。
小于 pivot的元素之间和大于 pivot的元素之间的 相对顺序不发生改变。
更正式的，考虑每一对pi，pj，pi是初始时位置 i元素的新位置，pj是初始时位置j元素的新位置。
对于小于pivot的元素，如果i < j且nums[i] < pivot 和nums[j] < pivot都成立，那么pi < pj也成立。
类似的，对于大于pivot的元素，如果i < j 且nums[i] > pivot 和nums[j] > pivot都成立，那么pi < pj。
请你返回重新排列 nums数组后的结果数组。
示例 1：输入：nums = [9,12,5,10,14,3,10], pivot = 10 输出：[9,5,3,10,10,12,14]
解释：元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，
它们在结果数组中的相对顺序需要保留。
示例 2：输入：nums = [-3,4,3,2], pivot = 2 输出：[-3,2,4,3]
解释：元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。
提示：1 <= nums.length <= 105
-106 <= nums[i] <= 106
pivot等于nums中的一个元素。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针+反转 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
| 03 |
遍历 |
O(n) |
O(n) |
func pivotArray(nums []int, pivot int) []int {
n := len(nums)
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = pivot
}
left, right := 0, n-1
for i := 0; i < n; i++ {
if nums[i] < pivot {
res[left] = nums[i]
left++
} else if nums[i] > pivot {
res[right] = nums[i]
right--
}
}
reverse(res[right+1:])
return res
}
func reverse(arr []int) {
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
}
# 2
func pivotArray(nums []int, pivot int) []int {
n := len(nums)
res := make([]int, 0)
for i := 0; i < n; i++ {
if nums[i] < pivot {
res = append(res, nums[i])
}
}
for i := 0; i < n; i++ {
if nums[i] == pivot {
res = append(res, nums[i])
}
}
for i := 0; i < n; i++ {
if nums[i] > pivot {
res = append(res, nums[i])
}
}
return res
}
# 3
func pivotArray(nums []int, pivot int) []int {
n := len(nums)
a, b, c := make([]int, 0), make([]int, 0), make([]int, 0)
for i := 0; i < n; i++ {
if nums[i] < pivot {
a = append(a, nums[i])
} else if nums[i] == pivot {
b = append(b, nums[i])
} else {
c = append(c, nums[i])
}
}
return append(a, append(b, c...)...)
}
2162.设置时间的最少代价(2)
常见的微波炉可以设置加热时间，且加热时间满足以下条件：
至少为 1秒钟。
至多为99分99秒。
你可以 最多输入4 个数字来设置加热时间。如果你输入的位数不足 4 位，微波炉会自动加 前缀0来补足 4 位。
微波炉会将设置好的四位数中，前两位当作分钟数，后两位当作秒数。它们所表示的总时间就是加热时间。比方说：
你输入9 5 4（三个数字），被自动补足为0954，并表示9分54秒。
你输入0 0 0 8（四个数字），表示0分8秒。
你输入8 0 9 0，表示80分90秒。
你输入8 1 3 0，表示81分30秒。
给你整数startAt，moveCost，pushCost和targetSeconds。
一开始，你的手指在数字startAt处。将手指移到任何其他数字，需要花费moveCost的单位代价。
每输入你手指所在位置的数字一次，需要花费pushCost的单位代价。
要设置targetSeconds秒的加热时间，可能会有多种设置方法。你想要知道这些方法中，总代价最小为多少。
请你能返回设置targetSeconds秒钟加热时间需要花费的最少代价。
请记住，虽然微波炉的秒数最多可以设置到 99秒，但一分钟等于60秒。
示例 1：输入：startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600 输出：6
解释：以下为设置加热时间的所有方法。
- 1 0 0 0 ，表示 10 分 0 秒。
手指一开始就在数字 1 处，输入 1 （代价为 1），移到 0 处（代价为 2），
输入 0（代价为 1），输入 0（代价为 1），输入 0（代价为 1）。
总代价为：1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。
- 0 9 6 0，表示 9 分 60 秒。它也表示 600 秒。
手指移到 0 处（代价为 2），输入 0 （代价为 1），移到 9 处（代价为 2），
输入 9（代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
总代价为：2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12 。
- 9 6 0，微波炉自动补全为 0960 ，表示 9 分 60 秒。
手指移到 9 处（代价为 2），输入 9 （代价为 1），移到 6 处（代价为 2），
输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
总代价为：2 + 1 + 2 + 1 + 2 + 1 = 9 。
示例 2：输入：startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76 输出：6
解释：最优方案为输入两个数字 7 6，表示 76 秒。
手指移到 7 处（代价为 1），输入 7 （代价为 2），移到 6 处（代价为 1），输入 6（代价为 2）。
总代价为：1 + 2 + 1 + 2 = 6
其他可行方案为 0076 ，076 ，0116 和 116 ，但是它们的代价都比 6 大。
提示：0 <= startAt <= 9
1 <= moveCost, pushCost <= 105
1 <= targetSeconds <= 6039
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
枚举 |
O(1) |
O(1) |
func minCostSetTime(startAt int, moveCost int, pushCost int, targetSeconds int) int {
m, s := targetSeconds/60, targetSeconds%60
a := cost(startAt, moveCost, pushCost, m, s)
b := cost(startAt, moveCost, pushCost, m-1, s+60)
return min(a, b)
}
func cost(startAt int, moveCost int, pushCost int, m, s int) int {
res := 0
if m < 0 || m > 99 || s < 0 || s > 99 {
return math.MaxInt32
}
arr := []int{m / 10, m % 10, s / 10, s % 10}
i := 0
for i < 4 && arr[i] == 0 {
i++
}
for j := i; j < 4; j++ {
if startAt != arr[j] {
startAt = arr[j]
res = res + moveCost
}
res = res + pushCost
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2165.重排数字的最小值(1)
给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。
返回不含前导零且值最小的重排数字。
注意，重排各位数字后，num 的符号不会改变。
示例 1：输入：num = 310 输出：103
解释：310 中各位数字的可行排列有：013、031、103、130、301、310 。
不含任何前导零且值最小的重排数字是 103 。
示例 2：输入：num = -7605 输出：-7650
解释：-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。
不含任何前导零且值最小的重排数字是 -7650 。
提示：-1015 <= num <= 1015
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(n) |
func smallestNumber(num int64) int64 {
arr := []byte(strconv.FormatInt(num, 10))
flag := int64(1)
if num <= 0 {
flag = -1
arr = arr[1:]
}
if flag == 1 {
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
i := 0
for arr[i] == '0' {
i++
}
arr[0], arr[i] = arr[i], arr[0]
} else {
sort.Slice(arr, func(i, j int) bool {
return arr[i] > arr[j]
})
}
res, _ := strconv.ParseInt(string(arr), 10, 64)
return flag * res
}
2166.设计位集(2)
位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。
Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
boolean all() 检查Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
boolean one() 检查Bitset 中 是否至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
int count() 返回 Bitset 中值为 1 的位的 总数 。
String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。
示例：输入["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
输出[null, null, null, null, false, null, null, true, null, 2, "01010"]
解释 Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3); // 将 idx = 3 处的值更新为 1 ，此时 bitset = "00010" 。
bs.fix(1); // 将 idx = 1 处的值更新为 1 ，此时 bitset = "01010" 。
bs.flip(); // 翻转每一位上的值，此时 bitset = "10101" 。
bs.all(); // 返回 False ，bitset 中的值不全为 1 。
bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = "00101" 。
bs.flip(); // 翻转每一位上的值，此时 bitset = "11010" 。
bs.one(); // 返回 True ，至少存在一位的值为 1 。
bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = "01010" 。
bs.count(); // 返回 2 ，当前有 2 位的值为 1 。
bs.toString(); // 返回 "01010" ，即 bitset 的当前组成情况。
提示：1 <= size <= 105
0 <= idx <= size - 1
至多调用fix、unfix、flip、all、one、count 和 toString 方法 总共 105 次
至少调用 all、one、count 或 toString 方法一次
至多调用toString 方法 5 次
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(n) |
O(n) |
| 02 |
数组 |
O(n) |
O(n) |
type Bitset struct {
arr []int
count int
flipCount int
}
func Constructor(size int) Bitset {
return Bitset{
arr: make([]int, size),
count: 0,
flipCount: 0,
}
}
func (this *Bitset) Fix(idx int) {
if (this.flipCount%2 == 0 && this.arr[idx] == 0) ||
(this.flipCount%2 == 1 && this.arr[idx] == 1) {
this.count++
this.arr[idx] = 1 - this.arr[idx]
}
}
func (this *Bitset) Unfix(idx int) {
if (this.flipCount%2 == 0 && this.arr[idx] == 1) ||
(this.flipCount%2 == 1 && this.arr[idx] == 0) {
this.count--
this.arr[idx] = 1 - this.arr[idx]
}
}
func (this *Bitset) Flip() {
this.flipCount++
this.count = len(this.arr) - this.count
}
func (this *Bitset) All() bool {
return len(this.arr) == this.count
}
func (this *Bitset) One() bool {
return this.count > 0
}
func (this *Bitset) Count() int {
return this.count
}
func (this *Bitset) ToString() string {
temp := make([]byte, len(this.arr))
for i := 0; i < len(this.arr); i++ {
v := this.arr[i]
if this.flipCount%2 == 1 {
v = 1 - v
}
temp[i] = byte('0' + v)
}
return string(temp)
}
# 2
type Bitset struct {
arr []byte
count int
flipCount int
}
func Constructor(size int) Bitset {
arr := bytes.Repeat([]byte{'0'}, size)
return Bitset{
arr: arr,
count: 0,
flipCount: 0,
}
}
func (this *Bitset) Fix(idx int) {
if (this.flipCount%2 == 0 && this.arr[idx] == '0') ||
(this.flipCount%2 == 1 && this.arr[idx] == '1') {
this.count++
this.arr[idx] = '0' + ('1' - this.arr[idx])
}
}
func (this *Bitset) Unfix(idx int) {
if (this.flipCount%2 == 0 && this.arr[idx] == '1') ||
(this.flipCount%2 == 1 && this.arr[idx] == '0') {
this.count--
this.arr[idx] = '0' + ('1' - this.arr[idx])
}
}
func (this *Bitset) Flip() {
this.flipCount++
this.count = len(this.arr) - this.count
}
func (this *Bitset) All() bool {
return len(this.arr) == this.count
}
func (this *Bitset) One() bool {
return this.count > 0
}
func (this *Bitset) Count() int {
return this.count
}
func (this *Bitset) ToString() string {
if this.flipCount%2 == 1 {
temp := make([]byte, len(this.arr))
for i := 0; i < len(this.arr); i++ {
temp[i] = '0' + ('1' - this.arr[i])
}
return string(temp)
}
return string(this.arr)
}
2170.使数组变成交替数组的最少操作数(2)
给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。
如果满足下述条件，则数组 nums 是一个 交替数组 ：
nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。
在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
返回使数组变成交替数组的 最少操作数 。
示例 1：输入：nums = [3,1,3,2,4,3] 输出：3
解释：使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。
示例 2：输入：nums = [1,2,2,2,2] 输出：2
解释：使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希 |
O(n) |
O(n) |
| 02 |
哈希+排序 |
O(nlog(n)) |
O(n) |
func minimumOperations(nums []int) int {
m := [2]map[int]int{}
for i := 0; i < 2; i++ {
m[i] = make(map[int]int)
}
for i := 0; i < len(nums); i++ {
if i%2 == 0 {
m[0][nums[i]]++
} else {
m[1][nums[i]]++
}
}
a := getMaxValue(m[0])
b := getMaxValue(m[1])
if a[0] == b[0] {
return len(nums) - max(a[1]+b[3], a[3]+b[1])
}
return len(nums) - a[1] - b[1]
}
func getMaxValue(m map[int]int) []int {
firstValue, firstIndex := 0, 0
secondValue, secondIndex := 0, 0
for k, v := range m {
if v > firstValue {
secondIndex, secondValue = firstIndex, firstValue
firstIndex, firstValue = k, v
} else if v > secondValue {
secondIndex, secondValue = k, v
}
}
return []int{firstIndex, firstValue, secondIndex, secondValue}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func minimumOperations(nums []int) int {
m := [2]map[int]int{}
for i := 0; i < 2; i++ {
m[i] = make(map[int]int)
}
for i := 0; i < len(nums); i++ {
if i%2 == 0 {
m[0][nums[i]]++
} else {
m[1][nums[i]]++
}
}
a := make([][2]int, 0)
b := make([][2]int, 0)
for i := 0; i < 2; i++ {
temp := make([][2]int, 2)
for k, v := range m[i] {
temp = append(temp, [2]int{k, v})
}
sort.Slice(temp, func(i, j int) bool {
return temp[i][1] > temp[j][1]
})
if i%2 == 0 {
a = temp[:2]
} else {
b = temp[:2]
}
}
if a[0][0] == b[0][0] {
return len(nums) - max(a[0][1]+b[1][1], a[1][1]+b[0][1])
}
return len(nums) - a[0][1] - b[0][1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2171.拿出最少数目的魔法豆(1)
给你一个 正整数数组beans，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的 非空 袋子中（即 至少还有 一颗魔法豆的袋子）魔法豆的数目相等。
一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。
请你返回你需要拿出魔法豆的 最少数目。
示例 1：输入：beans = [4,1,6,5] 输出：4
解释：- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。
示例 2：输入：beans = [2,10,3,2] 输出：7
解释：- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。
提示：1 <= beans.length <= 105
1 <= beans[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
func minimumRemoval(beans []int) int64 {
n := len(beans)
sum := int64(0)
for i := 0; i < n; i++ {
sum = sum + int64(beans[i])
}
res := sum
sort.Ints(beans)
for i := 0; i < n; i++ {
res = min(res, sum-int64(beans[i])*int64(n-i))
}
return res
}
func min(a, b int64) int64 {
if a > b {
return b
}
return a
}
2177.找到和为给定整数的三个连续整数(1)
给你一个整数num，请你返回三个连续的整数，它们的和为num。如果num无法被表示成三个连续整数的和，请你返回一个 空数组。
示例 1：输入：num = 33 输出：[10,11,12]
解释：33 可以表示为 10 + 11 + 12 = 33 。
10, 11, 12 是 3 个连续整数，所以返回 [10, 11, 12] 。
示例 2：输入：num = 4 输出：[]
解释：没有办法将 4 表示成 3 个连续整数的和。
提示：0 <= num <= 1015
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(1) |
O(1) |
func sumOfThree(num int64) []int64 {
if num%3 == 0 {
target := num / 3
return []int64{target - 1, target, target + 1}
}
return nil
}
2178.拆分成最多数目的正偶数之和(1)
给你一个整数finalSum。请你将它拆分成若干个互不相同 的正偶数之和，且拆分出来的正偶数数目最多。
比方说，给你finalSum = 12，那么这些拆分是符合要求 的（互不相同的正偶数且和为finalSum）：
(2 + 10)，(2 + 4 + 6)和(4 + 8)。
它们中，(2 + 4 + 6)包含最多数目的整数。注意finalSum不能拆分成(2 + 2 + 4 + 4)，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成 最多 数目的正偶数数组。
如果没有办法将finalSum进行拆分，请你返回一个空数组。你可以按 任意顺序返回这些整数。
示例 1：输入：finalSum = 12 输出：[2,4,6]
解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。
示例 2：输入：finalSum = 7 输出：[]
解释：没有办法将 finalSum 进行拆分。
所以返回空数组。
示例 3：输入：finalSum = 28 输出：[6,8,2,12]
解释：以下是一些符合要求的拆分：(2 + 26)，(6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。
提示：1 <= finalSum <= 1010
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n^(1/2)) |
O(n^(1/2)) |
func maximumEvenSplit(finalSum int64) []int64 {
if finalSum%2 == 1 {
return nil
}
res := make([]int64, 0)
for i := int64(2); i <= finalSum; i = i + 2 {
res = append(res, i)
finalSum = finalSum - i
}
res[len(res)-1] = res[len(res)-1] + finalSum
return res
}
2181.合并零之间的节点(2)
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。
然后将所有 0 移除，修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
示例 1：输入：head = [0,3,1,0,4,5,2,0] 输出：[4,11]
解释：上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：3 + 1 = 4
- 标记为红色的节点之和：4 + 5 + 2 = 11
示例 2：输入：head = [0,1,0,3,0,2,2,0] 输出：[1,3,4]
解释：上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：1 = 1
- 标记为红色的节点之和：3 = 3
- 标记为黄色的节点之和：2 + 2 = 4
提示：列表中的节点数目在范围 [3, 2 * 105] 内
0 <= Node.val <= 1000
不 存在连续两个Node.val == 0 的节点
链表的 开端 和 末尾 节点都满足 Node.val == 0
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
func mergeNodes(head *ListNode) *ListNode {
temp := make([]int, 0)
for head != nil {
temp = append(temp, head.Val)
head = head.Next
}
sum := 0
arr := make([]int, 0)
for i := 1; i < len(temp); i++ {
if temp[i] == 0 && sum != 0 {
arr = append(arr, sum)
sum = 0
} else {
sum = sum + temp[i]
}
}
res := &ListNode{}
t := res
for i := 0; i < len(arr); i++ {
t.Next = &ListNode{
Val: arr[i],
Next: nil,
}
t = t.Next
}
return res.Next
}
# 2
func mergeNodes(head *ListNode) *ListNode {
res := &ListNode{}
t := res
sum := 0
for cur := head.Next; cur != nil; cur = cur.Next {
if cur.Val == 0 {
node := &ListNode{
Val: sum,
}
t.Next = node
t = t.Next
sum = 0
} else {
sum = sum + cur.Val
}
}
return res.Next
}
2182.构造限制重复的字符串(1)
给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，
使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，
则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。
示例 1：输入：s = "cczazcc", repeatLimit = 3 输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。
示例 2：输入：s = "aababab", repeatLimit = 2 输出："bbabaa"
解释：使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。
字母 'a' 连续出现至多 2 次。
字母 'b' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。
提示：1 <= repeatLimit <= s.length <= 105
s 由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
func repeatLimitedString(s string, repeatLimit int) string {
arr := make([]int, 26)
for i := 0; i < len(s); i++ {
arr[int(s[i]-'a')]++
}
res := make([]byte, 0)
for i := 25; i >= 0; i-- {
prev := i - 1
for {
count := min(repeatLimit, arr[i])
arr[i] = arr[i] - count
res = append(res, bytes.Repeat([]byte{byte('a' + i)}, count)...)
if arr[i] == 0 {
break
}
for prev >= 0 && arr[prev] == 0 {
prev--
}
if prev < 0 {
break
}
arr[prev]--
res = append(res, byte('a'+prev))
}
}
return string(res)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2186.使两字符串互为字母异位词的最少步骤数(1)
给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。
返回使 s 和 t 互为 字母异位词 所需的最少步骤数。
字母异位词 指字母相同但是顺序不同（或者相同）的字符串。
示例 1：输入：s = "leetcode", t = "coats" 输出：7
解释：- 执行 2 步操作，将 "as" 追加到 s = "leetcode" 中，得到 s = "leetcodeas" 。
- 执行 5 步操作，将 "leede" 追加到 t = "coats" 中，得到 t = "coatsleede" 。
"leetcodeas" 和 "coatsleede" 互为字母异位词。
总共用去 2 + 5 = 7 步。
可以证明，无法用少于 7 步操作使这两个字符串互为字母异位词。
示例 2：输入：s = "night", t = "thing" 输出：0
解释：给出的字符串已经互为字母异位词。因此，不需要任何进一步操作。
提示：1 <= s.length, t.length <= 2 * 105
s 和 t 由小写英文字符组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func minSteps(s string, t string) int {
arr := make([]int, 26)
for i := 0; i < len(s); i++ {
arr[int(s[i]-'a')]++
}
for i := 0; i < len(t); i++ {
arr[int(t[i]-'a')]--
}
res := 0
for i := 0; i < 26; i++ {
res = res + abs(arr[i])
}
return res
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
2187.完成旅途的最少时间(2)
给你一个数组time，其中time[i]表示第 i辆公交车完成 一趟旅途所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始下一趟旅途。
每辆公交车 独立运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数totalTrips，表示所有公交车总共需要完成的旅途数目。请你返回完成 至少totalTrips趟旅途需要花费的 最少时间。
示例 1：输入：time = [1,2,3], totalTrips = 5 输出：3
解释：- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2：输入：time = [2], totalTrips = 1 输出：2
解释：只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。
提示：1 <= time.length <= 105
1 <= time[i], totalTrips <= 107
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(nlog(n)) |
O(1) |
| 02 |
二分查找 |
O(nlog(n)) |
O(1) |
func minimumTime(time []int, totalTrips int) int64 {
n := len(time)
maxValue := 0
for i := 0; i < n; i++ {
maxValue = max(maxValue, time[i])
}
left := int64(1)
right := int64(totalTrips) * int64(maxValue)
for left < right {
mid := left + (right-left)/2
if check(time, mid) >= totalTrips {
right = mid
} else {
left = mid + 1
}
}
return left
}
func check(arr []int, per int64) int {
count := 0
for i := 0; i < len(arr); i++ {
count = count + int(per/int64(arr[i]))
}
return count
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func minimumTime(time []int, totalTrips int) int64 {
n := len(time)
maxValue := 0
for i := 0; i < n; i++ {
maxValue = max(maxValue, time[i])
}
right := totalTrips * maxValue
return int64(sort.Search(right, func(per int) bool {
count := 0
for i := 0; i < len(time); i++ {
count = count + int(per/time[i])
}
return count >= totalTrips
}))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2192.有向无环图中一个节点的所有祖先(1)
给你一个正整数n，它表示一个 有向无环图中节点的数目，节点编号为0到n - 1（包括两者）。
给你一个二维整数数组edges，其中edges[i] = [fromi, toi]表示图中一条从fromi到toi的单向边。
请你返回一个数组answer，其中answer[i]是第i个节点的所有祖先，这些祖先节点升序排序。
如果 u通过一系列边，能够到达 v，那么我们称节点 u是节点 v的 祖先节点。
示例 1：输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释：上图为输入所对应的图。
- 节点 0 ，1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ，1 和 3 。
- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。
示例 2：输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。
提示：1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
拓扑排序 |
O(n^2log(n)) |
O(n^2) |
func getAncestors(n int, edges [][]int) [][]int {
m := make([]map[int]bool, n)
for i := 0; i < n; i++ {
m[i] = make(map[int]bool)
}
arr := make([][]int, n)
inDegree := make([]int, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], b)
inDegree[b]++
}
queue := make([]int, 0)
for i := 0; i < n; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for i := 0; i < len(arr[cur]); i++ {
next := arr[cur][i]
m[next][cur] = true
for k := range m[cur] {
m[next][k] = true
}
inDegree[next]--
if inDegree[next] == 0 {
queue = append(queue, next)
}
}
}
res := make([][]int, n)
for i := 0; i < n; i++ {
for k, _ := range m[i] {
res[i] = append(res[i], k)
}
sort.Ints(res[i])
}
return res
}
2195.向数组中追加K个整数
题目
给你一个整数数组 nums 和一个整数 k 。
请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
示例 1：输入：nums = [1,4,25,10,25], k = 2 输出：5
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
示例 2：输入：nums = [5,6], k = 6 输出：25
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。
提示：1 <= nums.length <= 105
1 <= nums[i], k <= 109
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+哈希 |
O(nlog(n)) |
O(n) |
func minimalKSum(nums []int, k int) int64 {
sum := int64(0)
sort.Ints(nums)
m := make(map[int]bool)
for i := 0; i < len(nums); i++ {
if m[nums[i]] == false && nums[i] <= k {
sum = sum + int64(nums[i])
k++
}
m[nums[i]] = true
}
return int64((k+1)*k/2) - sum
}
2196.根据描述创建二叉树(1)
给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti]
表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
测试用例会保证可以构造出 有效 的二叉树。
示例 1：输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] 输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。
示例 2：输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]] 输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。
结果二叉树如上图所示。
提示：1 <= descriptions.length <= 104
descriptions[i].length == 3
1 <= parenti, childi <= 105
0 <= isLefti <= 1
descriptions 所描述的二叉树是一棵有效二叉树
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希 |
O(n) |
O(n) |
func createBinaryTree(descriptions [][]int) *TreeNode {
m := make(map[int]*TreeNode)
visited := make(map[int]bool)
for i := 0; i < len(descriptions); i++ {
a, b, c := descriptions[i][0], descriptions[i][1], descriptions[i][2]
if m[a] == nil {
m[a] = &TreeNode{Val: a}
}
if m[b] == nil {
m[b] = &TreeNode{Val: b}
}
if c == 1 {
m[a].Left = m[b]
} else {
m[a].Right = m[b]
}
visited[b] = true
}
for k := range m {
if visited[k] == false {
return m[k]
}
}
return nil
}
2101-2200-Hard
2106.摘水果(2)
在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。
给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。
fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。
在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。
你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
返回你可以摘到水果的 最大总数 。
示例 1：输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4 输出：9
解释：最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果
示例 2：输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4 输出：14
解释：可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果
示例 3：输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2 输出：0
解释：最多可以移动 k = 2 步，无法到达任一有水果的地方
提示：1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）
1 <= amounti <= 104
0 <= k <= 2 * 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+二分查找 |
O(nlog(n)) |
O(n) |
| 02 |
滑动窗口 |
O(n) |
O(1) |
func maxTotalFruits(fruits [][]int, startPos int, k int) int {
res := 0
n := len(fruits)
sum := make([]int, n+1)
position := make([]int, n)
for i := 0; i < n; i++ {
position[i] = fruits[i][0]
sum[i+1] = sum[i] + fruits[i][1]
}
for i := 0; i <= k/2; i++ {
j := k - 2*i
res = max(res, getValue(position, sum, startPos-i, startPos+j))
res = max(res, getValue(position, sum, startPos-j, startPos+i))
}
return res
}
func getValue(arr []int, sum []int, left, right int) int {
l := sort.Search(len(arr), func(i int) bool {
return arr[i] >= left
})
r := sort.Search(len(arr), func(i int) bool {
return arr[i] > right
})
return sum[r] - sum[l]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxTotalFruits(fruits [][]int, startPos int, k int) int {
res := 0
sum := 0
i := 0
for j := 0; j < len(fruits); j++ {
for i <= j && (min(abs(startPos-fruits[i][0]), abs(startPos-fruits[j][0]))+
fruits[j][0]-fruits[i][0]) > k {
sum = sum - fruits[i][1]
i++
}
sum = sum + fruits[j][1]
res = max(res, sum)
}
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
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2111.使数组K递增的最少操作次数(2)
给你一个下标从 0开始包含 n个正整数的数组arr，和一个正整数k。
如果对于每个满足k <= i <= n-1的下标i，都有arr[i-k] <= arr[i]，那么我们称arr是 K递增 的。
比方说，arr = [4, 1, 5, 2, 6, 2]对于k = 2是 K 递增的，因为：
arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
但是，相同的数组arr对于k = 1不是 K 递增的（因为arr[0] > arr[1]），
对于k = 3也不是 K 递增的（因为arr[0] > arr[3]）。
每一次 操作中，你可以选择一个下标i 并将arr[i] 改成任意正整数。
请你返回对于给定的 k，使数组变成 K 递增的 最少操作次数。
示例 1：输入：arr = [5,4,3,2,1], k = 1 输出：4
解释：对于 k = 1 ，数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。
示例 2：输入：arr = [4,1,5,2,6,2], k = 2 输出：0
解释：这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的，我们不需要进行任何操作。
示例 3：输入：arr = [4,1,5,2,6,2], k = 3 输出：2
解释：下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。
提示：1 <= arr.length <= 105
1 <= arr[i], k <= arr.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划+二分查找 |
O(nlog(n)) |
O(n) |
| 02 |
动态规划+二分查找 |
O(nlog(n)) |
O(n) |
func kIncreasing(arr []int, k int) int {
res := 0
for i := 1; i <= k; i++ {
num := make([]int, 0)
num = append(num, arr[i-1])
for j := i - 1; j < len(arr)-k; j = j + k {
num = append(num, arr[j+k])
}
count := lengthOfLIS(num)
res = res + len(num) - count
}
return res
}
func lengthOfLIS(nums []int) int {
if len(nums) < 2 {
return len(nums)
}
arr := make([]int, 0)
arr = append(arr, nums[0])
for i := 1; i < len(nums); i++ {
index := upperBound(arr, nums[i])
if index == len(arr) {
arr = append(arr, nums[i])
} else {
arr[index] = nums[i]
}
}
return len(arr)
}
func upperBound(arr []int, target int) int {
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid] == target {
left = mid + 1
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
# 2
func kIncreasing(arr []int, k int) int {
res := 0
for i := 0; i < k; i++ {
dp := make([]int, 0)
count := 0
for j := i; j < len(arr); j = j + k {
count++
index := upperBound(dp, arr[j])
if index == len(dp) {
dp = append(dp, arr[j])
} else {
dp[index] = arr[j]
}
}
res = res + count - len(dp)
}
return res
}
func upperBound(arr []int, target int) int {
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid] == target {
left = mid + 1
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
2122.还原原数组(2)
Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。
她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
不幸地是，Alice 丢失了全部三个数组。
但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。
如果出现答案不唯一的情况，返回 任一 有效数组。
注意：生成的测试用例保证存在 至少一个 有效数组 arr 。
示例 1：输入：nums = [2,10,6,4,8,12] 输出：[3,7,11]
解释：如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。
示例 2：输入：nums = [1,1,3,3] 输出：[2,2]
解释：如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。
示例 3：输入：nums = [5,435] 输出：[220]
解释：唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。
提示：2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 109
生成的测试用例保证存在 至少一个 有效数组 arr
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
枚举+双指针 |
O(n^2) |
O(n) |
| 02 |
枚举+哈希 |
O(n^2) |
O(n) |
func recoverArray(nums []int) []int {
n := len(nums)
sort.Ints(nums)
for i := 1; i < n; i++ {
if nums[i] == nums[0] || (nums[i]-nums[0])%2 == 1 || nums[i] == nums[i-1] {
continue
}
visited := make([]bool, n)
visited[0], visited[i] = true, true
res := make([]int, 0)
k := (nums[i] - nums[0]) / 2
res = append(res, nums[0]+k)
left := 1
right := i
for j := 2; j <= n/2; j++ {
for visited[left] == true {
left++
}
for right < n && (visited[right] == true || nums[right]-nums[left] != 2*k) {
right++
}
if right == n {
break
}
res = append(res, nums[left]+k)
visited[left], visited[right] = true, true
}
if len(res) == n/2 {
return res
}
}
return nil
}
# 2
func recoverArray(nums []int) []int {
n := len(nums)
sort.Ints(nums)
for i := 1; i < n; i++ {
if nums[i] == nums[0] || (nums[i]-nums[0])%2 == 1 || nums[i] == nums[i-1] {
continue
}
m := make(map[int]int)
for i := 0; i < n; i++ {
m[nums[i]]++
}
res := make([]int, 0)
k := (nums[i] - nums[0]) / 2
for j := 0; j < n; j++ {
if m[nums[j]] == 0 {
continue
}
if m[nums[j]+2*k] == 0 {
break
}
m[nums[j]]--
m[nums[j]+2*k]--
res = append(res, nums[j]+k)
}
if len(res) == n/2 {
return res
}
}
return nil
}
2132.用邮票贴满网格图
题目
给你一个m x n的二进制矩阵grid，每个格子要么为0（空）要么为1（被占据）。
给你邮票的尺寸为stampHeight x stampWidth。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：
覆盖所有 空格子。
不覆盖任何 被占据的格子。
我们可以放入任意数目的邮票。
邮票可以相互有 重叠部分。
邮票不允许 旋转。
邮票必须完全在矩阵 内。
如果在满足上述要求的前提下，可以放入邮票，请返回true，否则返回false。
示例 1：输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。
示例 2：输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 输出：false
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。
提示：m == grid.length
n == grid[r].length
1 <= m, n <= 105
1 <= m * n <= 2 * 105
grid[r][c] 要么是0，要么是1 。
1 <= stampHeight, stampWidth <= 105
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
枚举+双指针 |
O(n^2) |
O(n) |
```
## 2136.全部开花的最早一天(1)
- 题目
你有 n 枚花的种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。
给你两个下标从 0 开始的整数数组 plantTime 和 growTime ，每个数组的长度都是 n ：
plantTime[i] 是 播种 第 i 枚种子所需的 完整天数 。每天，你只能为播种某一枚种子而劳作。
无须 连续几天都在种同一枚种子，但是种子播种必须在你工作的天数达到 plantTime[i] 之后才算完成。
growTime[i] 是第 i 枚种子完全种下后生长所需的 完整天数 。在它生长的最后一天 之后 ，将会开花并且永远 绽放 。
从第 0 开始，你可以按 任意 顺序播种种子。
返回所有种子都开花的 最早 一天是第几天。
示例 1：输入：plantTime = [1,4,3], growTime = [2,3,1] 输出：9
解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。
一种最优方案是：
第 0 天，播种第 0 枚种子，种子生长 2 整天。并在第 3 天开花。
第 1、2、3、4 天，播种第 1 枚种子。种子生长 3 整天，并在第 8 天开花。
第 5、6、7 天，播种第 2 枚种子。种子生长 1 整天，并在第 9 天开花。
因此，在第 9 天，所有种子都开花。
示例 2：输入：plantTime = [1,2,3,2], growTime = [2,1,2,1] 输出：9
解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。
一种最优方案是：
第 1 天，播种第 0 枚种子，种子生长 2 整天。并在第 4 天开花。
第 0、3 天，播种第 1 枚种子。种子生长 1 整天，并在第 5 天开花。
第 2、4、5 天，播种第 2 枚种子。种子生长 2 整天，并在第 8 天开花。
第 6、7 天，播种第 3 枚种子。种子生长 1 整天，并在第 9 天开花。
因此，在第 9 天，所有种子都开花。
示例 3：输入：plantTime = [1], growTime = [1] 输出：2
解释：第 0 天，播种第 0 枚种子。种子需要生长 1 整天，然后在第 2 天开花。
因此，在第 2 天，所有种子都开花。
提示：n == plantTime.length == growTime.length
1 <= n <= 105
1 <= plantTime[i], growTime[i] <= 104
- 解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
| :----- | :----- | :----------- | :----------- |
| 01 | 排序 | O(nlog(n)) | O(n) |
```go
func earliestFullBloom(plantTime []int, growTime []int) int {
n := len(plantTime)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = []int{plantTime[i], growTime[i]}
}
sort.Slice(arr, func(i, j int) bool { // 按生长日期降序排序
return arr[i][1] > arr[j][1]
})
res := 0
sum := 0
// 播种的总时间不变（串行），生长时间尽可能小（并行）
for i := 0; i < len(arr); i++ {
sum = sum + arr[i][0]
if sum+arr[i][1] > res {
res = sum + arr[i][1]
}
}
return res
}
2141.同时运行N台电脑的最长时间(4)
你有n台电脑。给你整数n和一个下标从 0开始的整数数组batteries，其中第i个电池可以让一台电脑 运行batteries[i]分钟。
你想使用这些电池让全部n台电脑 同时运行。
一开始，你可以给每台电脑连接 至多一个电池。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，
你可以进行这个操作 任意次。
新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。
注意，你不能给电池充电。
请你返回你可以让 n台电脑同时运行的 最长分钟数。
示例 1：输入：n = 2, batteries = [3,3,3] 输出：4
解释：一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。
示例 2：输入：n = 2, batteries = [1,1,1,1] 输出：2
解释：一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。
提示：1 <= n <= batteries.length <= 105
1 <= batteries[i] <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(nlog(n)) |
O(1) |
| 02 |
二分查找-内置函数 |
O(nlog(n)) |
O(1) |
| 03 |
贪心 |
O(nlog(n)) |
O(1) |
| 04 |
二分查找 |
O(nlog(n)) |
O(1) |
func maxRunTime(n int, batteries []int) int64 {
sum := 0
for i := 0; i < len(batteries); i++ {
sum = sum + batteries[i]
}
left, right := 1, sum/n
res := 0
for left <= right {
mid := left + (right-left)/2
total := 0
for j := 0; j < len(batteries); j++ {
total = total + min(batteries[j], mid)
}
if total >= n*mid {
res = mid
left = mid + 1
} else {
right = mid - 1
}
}
return int64(res)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func maxRunTime(n int, batteries []int) int64 {
sum := 0
for i := 0; i < len(batteries); i++ {
sum = sum + batteries[i]
}
return int64(sort.Search(sum/n, func(target int) bool {
target++
total := 0
for i := 0; i < len(batteries); i++ {
total = total + min(batteries[i], target)
}
return target*n > total
}))
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func maxRunTime(n int, batteries []int) int64 {
sort.Slice(batteries, func(i, j int) bool {
return batteries[i] > batteries[j]
})
sum := 0
for i := 0; i < len(batteries); i++ {
sum = sum + batteries[i]
}
for i := 0; i < len(batteries); i++ {
if batteries[i] <= sum/n {
return int64(sum / n)
}
sum = sum - batteries[i]
n--
}
return 0
}
# 4
func maxRunTime(n int, batteries []int) int64 {
sum := 0
for i := 0; i < len(batteries); i++ {
sum = sum + batteries[i]
}
left, right := 1, sum/n
for left <= right {
mid := left + (right-left)/2
total := 0
for j := 0; j < len(batteries); j++ {
total = total + min(batteries[j], mid)
}
if total >= n*mid {
left = mid + 1
} else {
right = mid - 1
}
}
return int64(right)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2147.分隔长廊的方案数(1)
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0开始，长度为 n的字符串corridor，
它包含字母'S' 和'P'，其中每个'S'表示一个座位，每个'P'表示一株植物。
在下标 0的左边和下标 n - 1的右边 已经分别各放了一个屏风。你还需要额外放置一些屏风。
每一个位置i - 1 和i之间（1 <= i <= n - 1），至多能放一个屏风。
请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位，而每一段内植物的数目没有要求。
可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 不同 方案。
请你返回划分走廊的方案数。由于答案可能很大，请你返回它对109 + 7取余的结果。如果没有任何方案，请返回0。
示例 1：输入：corridor = "SSPPSPS" 输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个座位。
示例 2：输入：corridor = "PPSPSP" 输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。
示例 3：输入：corridor = "S" 输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。
提示：n == corridor.length
1 <= n <= 105
corridor[i]要么是'S'，要么是'P' 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
var mod = 1000000007
func numberOfWays(corridor string) int {
res := 1
prev := -1
count := 0
for i := 0; i < len(corridor); i++ {
if corridor[i] == 'S' {
count++
if count >= 3 && count%2 == 1 {
res = res * (i - prev) % mod
}
prev = i
}
}
if count < 2 || count%2 == 1 {
return 0
}
return res
}
2157.字符串分组
题目
给你一个下标从0开始的字符串数组words。每个字符串都只包含 小写英文字母。words中任意一个子串中，每个字母都至多只出现一次。
如果通过以下操作之一，我们可以从 s1的字母集合得到 s2的字母集合，那么我们称这两个字符串为 关联的：
往s1的字母集合中添加一个字母。
从s1的字母集合中删去一个字母。
将 s1中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组words可以分为一个或者多个无交集的 组。一个字符串与一个组如果满足以下 任一条件，它就属于这个组：
它与组内 至少一个其他字符串关联。
它是这个组中 唯一的字符串。
注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2的数组ans：
ans[0]是words分组后的总组数。
ans[1]是字符串数目最多的组所包含的字符串数目。
示例 1：输入：words = ["a","b","ab","cde"] 输出：[2,3]
解释：- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。
所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。
所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以，words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。
示例 2：输入：words = ["a","ab","abc"] 输出：[1,3]
解释：- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。
提示：1 <= words.length <= 2 * 104
1 <= words[i].length <= 26
words[i]只包含小写英文字母。
words[i] 中每个字母最多只出现一次。
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
```
## 2167.移除所有载有违禁货物车厢所需的最少时间(3)
- 题目
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，
而 s[i] = '1' 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：
从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。
示例 1：输入：s = "1100101" 输出：5
解释：一种从序列中移除所有载有违禁货物的车厢的方法是：
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(n) |
| 02 |
前缀和 |
O(n) |
O(1) |
| 03 |
遍历 |
O(n) |
O(1) |
func minimumTime(s string) int {
n := len(s)
res := n
pre := make([]int, n+1)
for i := 0; i < n; i++ {
pre[i+1] = pre[i] + int(s[i]-'0')
}
a := 0
for j := 0; j < n; j++ {
a = min(a, j-2*pre[j])
b := 2*pre[j+1] - j
res = min(res, a+b+n-1)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minimumTime(s string) int {
n := len(s)
res := n
a := 0
sum := 0
for j := 0; j < n; j++ {
a = min(a, j-2*sum)
sum = sum + int(s[j]-'0')
b := 2*sum - j
res = min(res, a+b+n-1)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func minimumTime(s string) int {
n := len(s)
res := n
count := 0
for i := 0; i < n; i++ {
if s[i] == '1' {
count = min(count+2, i+1)
}
res = min(res, count+n-1-i)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2183.统计可以被K整除的下标对数目(2)
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：
0 <= i < j <= n - 1 且 nums[i] * nums[j] 能被 k 整除。
示例 1：输入：nums = [1,2,3,4,5], k = 2 输出：7
解释：共有 7 对下标的对应积可以被 2 整除：
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。
示例 2：输入：nums = [1,2,3,4], k = 5 输出：0
解释：不存在对应积可以被 5 整除的下标对。
提示：1 <= nums.length <= 105
1 <= nums[i], k <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学-最大公约数 |
O(nlog(n)) |
O(log(n)) |
| 02 |
数学-最大公约数 |
O(nlog(n)) |
O(log(n)) |
func countPairs(nums []int, k int) int64 {
res := int64(0)
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[gcd(k, nums[i])]++
}
for k1, v1 := range m {
for k2, v2 := range m {
if k1*k2%k == 0 {
res = res + int64(v1)*int64(v2)
}
}
}
for i := 0; i < len(nums); i++ {
if nums[i]*nums[i]%k == 0 {
res--
}
}
return res / 2
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
# 2
func countPairs(nums []int, k int) int64 {
res := int64(0)
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[gcd(k, nums[i])]++
}
for k1, v1 := range m {
for k2, v2 := range m {
if k1*k2%k == 0 {
if k1 < k2 {
res = res + int64(v1)*int64(v2)
} else if k1 == k2 {
res = res + int64(v1)*int64(v1-1)/2
}
}
}
}
return res
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
2188.完成比赛的最少时间(1)
给你一个下标从 0开始的二维整数数组tires，其中tires[i] = [fi, ri]表示第i种轮胎如果连续使用，
第x圈需要耗时fi * ri(x-1)秒。
比方说，如果fi = 3且ri = 2，且一直使用这种类型的同一条轮胎，
那么该轮胎完成第1圈赛道耗时 3秒，完成第 2圈耗时3 * 2 = 6秒，完成第 3圈耗时3 * 22 = 12秒，依次类推。
同时给你一个整数changeTime和一个整数numLaps。
比赛总共包含numLaps圈，你可以选择 任意一种轮胎开始比赛。每一种轮胎都有 无数条。
每一圈后，你可以选择耗费 changeTime秒 换成任意一种轮胎（也可以换成当前种类的新轮胎）。
请你返回完成比赛需要耗费的 最少时间。
示例 1：输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4 输出：21
解释：第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。
示例 2：输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5 输出：25
解释：第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。
提示：1 <= tires.length <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
minArr := make([]int, 20)
for i := 0; i < 20; i++ {
minArr[i] = math.MaxInt32 / 10
}
for i := 0; i < len(tires); i++ {
f, r := tires[i][0], tires[i][1]
first := f + changeTime
sum := first
for j := 1; f <= first; j++ {
minArr[j] = min(minArr[j], sum)
f = f * r
sum = sum + f
}
}
dp := make([]int, numLaps+1)
for i := 0; i <= numLaps; i++ {
dp[i] = math.MaxInt32 / 10
}
dp[0] = 0
for i := 1; i <= numLaps; i++ {
for j := 1; j <= 19 && j <= i; j++ {
dp[i] = min(dp[i], dp[i-j]+minArr[j])
}
}
return dp[numLaps] - changeTime
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2197.替换数组中的非互质数(1)
给你一个整数数组 nums 。请你对数组执行下述操作：
从 nums 中找出 任意 两个 相邻 的 非互质 数。
如果不存在这样的数，终止 这一过程。
否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
示例 1 ：输入：nums = [6,4,3,2,7,6,2] 输出：[12,7,6]
解释：- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。
示例 2 ：输入：nums = [2,2,1,1,3,3,3] 输出：[2,1,1,3]
解释：- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [2,1,1,3] 。
注意，存在其他方法可以获得相同的最终数组。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈 |
O(nlog(n)) |
O(n) |
func replaceNonCoprimes(nums []int) []int {
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
v := nums[i]
for len(res) > 0 {
if gcd(v, res[len(res)-1]) > 1 {
v = lcm(v, res[len(res)-1])
res = res[:len(res)-1]
} else {
break
}
}
res = append(res, v)
}
return res
}
func lcm(x, y int) int {
return x * y / gcd(x, y)
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}