1901-2000-Easy
1903.字符串中的最大奇数(1)
给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有非空子字符串 中找出 值最大的奇数 ，并以字符串形式返回。
如果不存在奇数，则返回一个空字符串 "" 。
子字符串 是字符串中的一个连续的字符序列。
示例 1：输入：num = "52" 输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。
示例 2：输入：num = "4206" 输出：""
解释：在 "4206" 中不存在奇数。
示例 3：输入：num = "35427" 输出："35427"
解释："35427" 本身就是一个奇数。
提示：1 <= num.length <= 105
num 仅由数字组成且不含前导零
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func largestOddNumber(num string) string {
n := len(num)
for i := n - 1; i >= 0; i-- {
if int(num[i]-'0')%2 == 1 {
return num[:i+1]
}
}
return ""
}
1909.删除一个元素使数组严格递增(3)
给你一个下标从 0开始的整数数组nums，如果恰好删除一个元素后，数组严格递增，那么请你返回true，否则返回false。
如果数组本身已经是严格递增的，请你也返回true。
数组nums是 严格递增的定义为：对于任意下标的1 <= i < nums.length都满足nums[i - 1] < nums[i]。
示例 1：输入：nums = [1,2,10,5,7] 输出：true
解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
[1,2,5,7] 是严格递增的，所以返回 true 。
示例 2：输入：nums = [2,3,1,2] 输出：false
解释：[3,1,2] 是删除下标 0 处元素后得到的结果。
[2,1,2] 是删除下标 1 处元素后得到的结果。
[2,3,2] 是删除下标 2 处元素后得到的结果。
[2,3,1] 是删除下标 3 处元素后得到的结果。
没有任何结果数组是严格递增的，所以返回 false 。
示例 3：输入：nums = [1,1,1] 输出：false
解释：删除任意元素后的结果都是 [1,1] 。
[1,1] 不是严格递增的，所以返回 false 。
示例 4：输入：nums = [1,2,3] 输出：true
解释：[1,2,3] 已经是严格递增的，所以返回 true 。
提示：2 <= nums.length <= 1000
1 <= nums[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
暴力法 |
O(n^2) |
O(n) |
| 03 |
动态规划 |
O(n^2) |
O(n) |
func canBeIncreasing(nums []int) bool {
for i := 0; i < len(nums)-1; i++ {
if nums[i] >= nums[i+1] {
return judge(nums, i) == true || judge(nums, i+1) == true
}
}
return true
}
func judge(nums []int, index int) bool {
arr := append([]int{}, nums[:index]...)
arr = append(arr, nums[index+1:]...)
for i := 0; i < len(arr)-1; i++ {
if arr[i] >= arr[i+1] {
return false
}
}
return true
}
# 2
func canBeIncreasing(nums []int) bool {
for i := 0; i < len(nums); i++ {
if judge(nums, i) == true {
return true
}
}
return false
}
func judge(nums []int, index int) bool {
arr := append([]int{}, nums[:index]...)
arr = append(arr, nums[index+1:]...)
for i := 0; i < len(arr)-1; i++ {
if arr[i] >= arr[i+1] {
return false
}
}
return true
}
# 3
func canBeIncreasing(nums []int) bool {
n := len(nums)
dp := make([]int, n)
res := 1
for i := 0; i < n; i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[j]+1, dp[i])
}
}
res = max(res, dp[i])
}
return res == n || res == n-1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1913.两个数对之间的最大乘积差(2)
两个数对(a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。
例如，(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。
给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，
使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。
返回以这种方式取得的乘积差中的 最大值 。
示例 1：输入：nums = [5,6,2,7,4] 输出：34
解释：可以选出下标为 1 和 3 的元素构成第一个数对 (6, 7) 以及下标 2 和 4 构成第二个数对 (2, 4)
乘积差是 (6 * 7) - (2 * 4) = 34
示例 2：输入：nums = [4,2,5,9,7,4,8] 输出：64
解释：可以选出下标为 3 和 6 的元素构成第一个数对 (9, 8) 以及下标 1 和 5 构成第二个数对 (2, 4)
乘积差是 (9 * 8) - (2 * 4) = 64
提示：4 <= nums.length <= 104
1 <= nums[i] <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func maxProductDifference(nums []int) int {
sort.Ints(nums)
n := len(nums)
return nums[n-1]*nums[n-2] - nums[0]*nums[1]
}
# 2
func maxProductDifference(nums []int) int {
n := len(nums)
minA, minB := min(nums[0], nums[1]), max(nums[0], nums[1])
maxA, maxB := max(nums[0], nums[1]), min(nums[0], nums[1])
for i := 2; i < n; i++ {
if nums[i] > maxA {
maxA, maxB = nums[i], maxA
} else if nums[i] > maxB {
maxB = nums[i]
}
if nums[i] < minA {
minA, minB = nums[i], minA
} else if nums[i] < minB {
minB = nums[i]
}
}
return maxA*maxB - minA*minB
}
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
}
1920.基于排列构建数组(2)
给你一个 从 0 开始的排列 nums（下标也从 0 开始）。
请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。
返回构建好的数组 ans 。
从 0 开始的排列 nums 是一个由 0 到nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。
示例 1：输入：nums = [0,2,1,5,3,4] 输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
= [0,1,2,4,5,3]
示例 2：输入：nums = [5,0,1,2,3,4] 输出：[4,5,0,1,2,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
= [4,5,0,1,2,3]
提示：1 <= nums.length <= 1000
0 <= nums[i] < nums.length
nums 中的元素 互不相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历-原地构造 |
O(n) |
O(1) |
func buildArray(nums []int) []int {
n := len(nums)
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = nums[nums[i]]
}
return res
}
# 2
func buildArray(nums []int) []int {
n := len(nums)
for i := 0; i < n; i++ {
nums[i] = nums[i] + 1000*(nums[nums[i]]%1000)
}
for i := 0; i < n; i++ {
nums[i] = nums[i] / 1000
}
return nums
}
1925.统计平方和三元组的数目(3)
一个 平方和三元组(a,b,c)指的是满足 a2 + b2 = c2的 整数三元组a，b和c。
给你一个整数n，请你返回满足1 <= a, b, c <= n的 平方和三元组 的数目。
示例 1：输入：n = 5 输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。
示例 2：输入：n = 10 输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。
提示：1 <= n <= 250
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^3) |
O(1) |
| 02 |
哈希辅助 |
O(n^2) |
O(n) |
| 03 |
内置函数 |
O(n^2) |
O(1) |
func countTriples(n int) int {
res := 0
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
for k := 1; k <= n; k++ {
if i*i+j*j == k*k {
res++
}
}
}
}
return res
}
# 2
func countTriples(n int) int {
res := 0
m := make(map[int]bool)
for i := 1; i <= n; i++ {
m[i*i] = true
}
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if m[i*i+j*j] == true {
res++
}
}
}
return res
}
# 3
func countTriples(n int) int {
res := 0
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
k := int(math.Sqrt(float64(i*i + j*j)))
if k*k == i*i+j*j && k <= n {
res++
}
}
}
return res
}
1929.数组串联(3)
给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，
数组下标 从 0 开始计数 ，对于所有0 <= i < n 的 i ，满足下述所有要求：
ans[i] == nums[i]
ans[i + n] == nums[i]
具体而言，ans 由两个 nums 数组 串联 形成。
返回数组 ans 。
示例 1：输入：nums = [1,2,1] 输出：[1,2,1,1,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]
示例 2：输入：nums = [1,3,2,1] 输出：[1,3,2,1,1,3,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]
提示：n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
| 03 |
内置语法 |
O(n) |
O(n) |
func getConcatenation(nums []int) []int {
n := len(nums)
res := make([]int, 2*n)
for i := 0; i < n; i++ {
res[i] = nums[i]
res[i+n] = nums[i]
}
return res
}
# 2
func getConcatenation(nums []int) []int {
n := len(nums)
for i := 0; i < n; i++ {
nums = append(nums, nums[i])
}
return nums
}
# 3
func getConcatenation(nums []int) []int {
return append(nums, nums...)
}
1935.可以输入的最大单词数(2)
键盘出现了一些故障，有些字母键无法正常工作。而键盘上所有其他键都能够正常工作。
给你一个由若干单词组成的字符串 text ，单词间由单个空格组成（不含前导和尾随空格）；
另有一个字符串 brokenLetters ，由所有已损坏的不同字母键组成，返回你可以使用此键盘完全输入的 text 中单词的数目。
示例 1：输入：text = "hello world", brokenLetters = "ad" 输出：1
解释：无法输入 "world" ，因为字母键 'd' 已损坏。
示例 2：输入：text = "leet code", brokenLetters = "lt" 输出：1
解释：无法输入 "leet" ，因为字母键 'l' 和 't' 已损坏。
示例 3：输入：text = "leet code", brokenLetters = "e" 输出：0
解释：无法输入任何单词，因为字母键 'e' 已损坏。
提示：1 <= text.length <= 104
0 <= brokenLetters.length <= 26
text 由若干用单个空格分隔的单词组成，且不含任何前导和尾随空格
每个单词仅由小写英文字母组成
brokenLetters 由 互不相同 的小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func canBeTypedWords(text string, brokenLetters string) int {
res := 0
arr := strings.Split(text, " ")
for i := 0; i < len(arr); i++ {
if strings.ContainsAny(arr[i], brokenLetters) == false {
res++
}
}
return res
}
# 2
func canBeTypedWords(text string, brokenLetters string) int {
res := 0
m := make(map[byte]bool)
for i := 0; i < len(brokenLetters); i++ {
m[brokenLetters[i]] = true
}
arr := strings.Split(text, " ")
for i := 0; i < len(arr); i++ {
flag := true
for j := 0; j < len(arr[i]); j++ {
if m[arr[i][j]] == true {
flag = false
break
}
}
if flag == true {
res++
}
}
return res
}
1941.检查是否所有字符出现次数相同(2)
给你一个字符串s，如果 s是一个 好字符串，请你返回 true，否则请返回 false。
如果 s中出现过的所有 字符的出现次数 相同，那么我们称字符串 s是 好字符串。
示例 1：输入：s = "abacbc" 输出：true
解释：s 中出现过的字符为 'a'，'b' 和 'c' 。s 中所有字符均出现 2 次。
示例 2：输入：s = "aaabb" 输出：false
解释：s 中出现过的字符为 'a' 和 'b' 。
'a' 出现了 3 次，'b' 出现了 2 次，两者出现次数不同。
提示：1 <= s.length <= 1000
s只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func areOccurrencesEqual(s string) bool {
m := make(map[byte]int)
for i := 0; i < len(s); i++ {
m[s[i]]++
}
count := 0
for _, v := range m {
if count == 0 {
count = v
} else {
if count != v {
return false
}
}
}
return true
}
# 2
func areOccurrencesEqual(s string) bool {
m := make(map[byte]int)
for i := 0; i < len(s); i++ {
m[s[i]]++
}
count := len(s)/len(m)
for _, v := range m {
if v != count{
return false
}
}
return true
}
1945.字符串转化后的各位数字之和(2)
给你一个由小写字母组成的字符串 s ，以及一个整数 k 。
首先，用字母在字母表中的位置替换该字母，将 s 转化 为一个整数（也就是，'a' 用 1 替换，'b' 用 2 替换，... 'z' 用 26 替换）。
接着，将整数 转换 为其 各位数字之和 。共重复 转换 操作 k 次 。
例如，如果 s = "zbax" 且 k = 2 ，那么执行下述步骤后得到的结果是整数 8 ：
转化："zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
转换 #1：262124➝ 2 + 6 + 2 + 1 + 2 + 4➝ 17
转换 #2：17 ➝ 1 + 7 ➝ 8
返回执行上述操作后得到的结果整数。
示例 1：输入：s = "iiii", k = 1 输出：36
解释：操作如下：- 转化："iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- 转换 #1：9999 ➝ 9 + 9 + 9 + 9 ➝ 36
因此，结果整数为 36 。
示例 2：输入：s = "leetcode", k = 2 输出：6
解释：操作如下：- 转化："leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- 转换 #1：12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- 转换 #2：33 ➝ 3 + 3 ➝ 6
因此，结果整数为 6 。
提示：1 <= s.length <= 100
1 <= k <= 10
s 由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟 |
O(n) |
O(n) |
| 02 |
模拟 |
O(n) |
O(1) |
func getLucky(s string, k int) int {
arr := make([]int, 0)
for i := 0; i < len(s); i++ {
value := int(s[i]-'a') + 1
if value < 10 {
arr = append(arr, value)
} else {
arr = append(arr, value/10)
arr = append(arr, value%10)
}
}
for i := 1; i <= k; i++ {
arr = trans(arr)
}
res := 0
for i := 0; i < len(arr); i++ {
res = 10*res + arr[i]
}
return res
}
func trans(arr []int) []int {
sum := 0
for i := 0; i < len(arr); i++ {
sum = sum + arr[i]
}
res := make([]int, 0)
for sum > 0 {
res = append([]int{sum % 10}, res...)
sum = sum / 10
}
return res
}
# 2
func getLucky(s string, k int) int {
sum := 0
for i := 0; i < len(s); i++ {
value := int(s[i]-'a') + 1
sum = sum + (value/10 + value%10)
}
res := sum
for i := 1; i <= k-1; i++ {
sum = res
res = 0
for sum > 0 {
res = res + sum%10
sum = sum / 10
}
}
return res
}
1952.三除数(3)
给你一个整数 n 。如果 n 恰好有三个正除数 ，返回 true ；否则，返回 false 。
如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个 除数 。
示例 1：输入：n = 2 输出：false
解释：2 只有两个除数：1 和 2 。
示例 2：输入：n = 4 输出：true
解释：4 有三个除数：1、2 和 4 。
提示：1 <= n <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n^(1/2)) |
O(1) |
| 03 |
遍历 |
O(n^(1/2)) |
O(1) |
func isThree(n int) bool {
count := 0
for i := 1; i <= n; i++ {
if n%i == 0 {
count++
}
}
return count == 3
}
# 2
func isThree(n int) bool {
count := 0
for i := 1; i*i <= n; i++ {
if n%i == 0 {
if i*i == n {
count++
} else {
count = count + 2
}
}
}
return count == 3
}
# 3
func isThree(n int) bool {
target := int(math.Sqrt(float64(n)))
return target*target == n && isPrime(target) == true
}
func isPrime(n int) bool {
for i := 2; i*i <= n; i++ {
if n%i == 0 {
return false
}
}
return n >= 2
}
1957.删除字符使字符串变好(2)
一个字符串如果没有 三个连续相同字符，那么它就是一个 好字符串。
给你一个字符串s，请你从 s删除最少的字符，使它变成一个 好字符串 。
请你返回删除后的字符串。题目数据保证答案总是 唯一的 。
示例 1：输入：s = "leeetcode" 输出："leetcode"
解释：从第一组 'e' 里面删除一个 'e' ，得到 "leetcode" 。
没有连续三个相同字符，所以返回 "leetcode" 。
示例 2：输入：s = "aaabaaaa" 输出："aabaa"
解释：从第一组 'a' 里面删除一个 'a' ，得到 "aabaaaa" 。
从第二组 'a' 里面删除两个 'a' ，得到 "aabaa" 。
没有连续三个相同字符，所以返回 "aabaa" 。
示例 3：输入：s = "aab" 输出："aab"
解释：没有连续三个相同字符，所以返回 "aab" 。
提示：1 <= s.length <= 105
s只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func makeFancyString(s string) string {
for i := 'a'; i <= 'z'; i++ {
for strings.Contains(s, strings.Repeat(string(i), 3)) == true {
s = strings.ReplaceAll(s, strings.Repeat(string(i), 3), strings.Repeat(string(i), 2))
}
}
return s
}
# 2
func makeFancyString(s string) string {
res := make([]byte, 0)
for i := 0; i < len(s); i++ {
if len(res) >= 2 && res[len(res)-1] == s[i] && res[len(res)-2] == s[i] {
continue
}
res = append(res, s[i])
}
return string(res)
}
1961.检查字符串是否为数组前缀(1)
给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的 前缀字符串 。
字符串 s 要成为 words 的 前缀字符串 ，需要满足：s 可以由 words 中的前 k（k 为 正数 ）个字符串按顺序相连得到，
且 k 不超过 words.length 。
如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。
示例 1：输入：s = "iloveleetcode", words = ["i","love","leetcode","apples"] 输出：true
解释：s 可以由 "i"、"love" 和 "leetcode" 相连得到。
示例 2：输入：s = "iloveleetcode", words = ["apples","i","love","leetcode"] 输出：false
解释： 数组的前缀相连无法得到 s 。
提示：1 <= words.length <= 100
1 <= words[i].length <= 20
1 <= s.length <= 1000
words[i] 和 s 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func isPrefixString(s string, words []string) bool {
temp := ""
for i := 0; i < len(words); i++ {
temp = temp + words[i]
if temp == s {
return true
}
}
return false
}
1967.作为子字符串出现在单词中的字符串数目(1)
给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：patterns = ["a","abc","bc","d"], word = "abc" 输出：3
解释：- "a" 是 "abc" 的子字符串。
- "abc" 是 "abc" 的子字符串。
- "bc" 是 "abc" 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。
示例 2：输入：patterns = ["a","b","c"], word = "aaaaabbbbb" 输出：2
解释：- "a" 是 "aaaaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbbb" 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。
示例 3：输入：patterns = ["a","a","a"], word = "ab" 输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。
提示：1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
func numOfStrings(patterns []string, word string) int {
res := 0
for i := 0; i < len(patterns); i++ {
if strings.Contains(word, patterns[i]) == true {
res++
}
}
return res
}
1974.使用特殊打字机键入单词的最少时间(2)
有一个特殊打字机，它由一个 圆盘 和一个 指针组成， 圆盘上标有小写英文字母'a' 到'z'。
只有当指针指向某个字母时，它才能被键入。指针 初始时指向字符 'a'。
每一秒钟，你可以执行以下操作之一：
将指针 顺时针或者 逆时针移动一个字符。
键入指针 当前指向的字符。
给你一个字符串word，请你返回键入word所表示单词的 最少秒数。
示例 1：输入：word = "abc" 输出：5
解释：单词按如下操作键入：
- 花 1 秒键入字符 'a' in 1 ，因为指针初始指向 'a' ，故不需移动指针。
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 1 秒将指针顺时针移到 'c' 。
- 花 1 秒键入字符 'c' 。
示例 2：输入：word = "bza" 输出：7
解释：单词按如下操作键入：
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 2 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 1 秒将指针顺时针移到 'a' 。
- 花 1 秒键入字符 'a' 。
示例 3：输入：word = "zjpc" 输出：34
解释：单词按如下操作键入：
- 花 1 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 10 秒将指针顺时针移到 'j' 。
- 花 1 秒键入字符 'j' 。
- 花 6 秒将指针顺时针移到 'p' 。
- 花 1 秒键入字符 'p' 。
- 花 13 秒将指针逆时针移到 'c' 。
- 花 1 秒键入字符 'c' 。
提示：1 <= word.length <= 100
word只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func minTimeToType(word string) int {
res := 0
cur := 0
for i := 0; i < len(word); i++ {
target := int(word[i] - 'a')
left := (cur - target + 26) % 26
right := (target - cur + 26) % 26
res = res + 1 + min(left, right)
cur = target
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minTimeToType(word string) int {
res := 0
cur := 0
for i := 0; i < len(word); i++ {
target := abs(int(word[i]-'a') - cur)
res = res + 1 + min(target, 26-target)
cur = int(word[i]-'a')
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
1979.找出数组的最大公约数(2)
给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。
两个数的最大公约数 是能够被两个数整除的最大正整数。
示例 1：输入：nums = [2,5,6,9,10] 输出：2
解释：nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
示例 2：输入：nums = [7,5,6,8,3] 输出：1
解释：nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1
示例 3：输入：nums = [3,3] 输出：3
解释：nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3
提示：2 <= nums.length <= 1000
1 <= nums[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func findGCD(nums []int) int {
sort.Ints(nums)
a, b := nums[0], nums[len(nums)-1]
return gcd(a, b)
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
# 2
func findGCD(nums []int) int {
a, b := nums[0], nums[0]
for i := 0; i < len(nums); i++ {
if nums[i] > a {
a = nums[i]
}
if nums[i] < b {
b = nums[i]
}
}
return gcd(a, b)
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
1984.学生分数的最小差值(1)
给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
示例 1：输入：nums = [90], k = 1 输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0
示例 2：输入：nums = [9,4,1,7], k = 2 输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2
提示：1 <= k <= nums.length <= 1000
0 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(1) |
func minimumDifference(nums []int, k int) int {
sort.Ints(nums)
res := math.MaxInt32
for i := 0; i <= len(nums)-k; i++ {
left := nums[i]
right := nums[i+k-1]
res = min(res, right-left)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1991.找到数组的中间位置(1)
给你一个下标从 0开始的整数数组nums，请你找到 最左边的中间位置middleIndex（也就是所有可能中间位置下标最小的一个）。
中间位置middleIndex是满足nums[0] + nums[1] + ... + nums[middleIndex-1] ==
nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1]的数组下标。
如果middleIndex == 0，左边部分的和定义为 0。类似的，如果middleIndex == nums.length - 1，右边部分的和定义为0。
请你返回满足上述条件 最左边的middleIndex，如果不存在这样的中间位置，请你返回-1。
示例 1：输入：nums = [2,3,-1,8,4] 输出：3
解释：下标 3 之前的数字和为：2 + 3 + -1 = 4
下标 3 之后的数字和为：4 = 4
示例 2：输入：nums = [1,-1,4] 输出：2
解释：下标 2 之前的数字和为：1 + -1 = 0
下标 2 之后的数字和为：0
示例 3：输入：nums = [2,5]输出：-1
解释：不存在符合要求的 middleIndex 。
示例 4：输入：nums = [1] 输出：0
解释：下标 0 之前的数字和为：0
下标 0 之后的数字和为：0
提示：1 <= nums.length <= 100
-1000 <= nums[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func findMiddleIndex(nums []int) int {
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
count := 0
for i := 0; i < len(nums); i++ {
if 2*count == sum-nums[i] {
return i
}
count = count + nums[i]
}
return -1
}
1995.统计特殊四元组(1)
给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
nums[a] + nums[b] + nums[c] == nums[d] ，且 a < b < c < d
示例 1：输入：nums = [1,2,3,6] 输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。
示例 2：输入：nums = [3,3,6,4,5] 输出：0
解释：[3,3,6,4,5] 中不存在满足要求的四元组。
示例 3：输入：nums = [1,1,1,3,5] 输出：4
解释：满足要求的 4 个四元组如下：
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5
提示：4 <= nums.length <= 50
1 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^4) |
O(1) |
func countQuadruplets(nums []int) int {
res := 0
n := len(nums)
for i := 0; i < n-3; i++ {
for j := i + 1; j < n-2; j++ {
for k := j + 1; k < n-1; k++ {
for l := k + 1; l < n; l++ {
if nums[i]+nums[j]+nums[k] == nums[l] {
res++
}
}
}
}
}
return res
}
2000.反转单词前缀(1)
给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，
反转 word 中从下标 0 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。
例如，如果 word = "abcdefd" 且 ch = "d" ，那么你应该 反转 从下标 0 开始、直到下标 3 结束（含下标 3 ）。
结果字符串将会是 "dcbaefd" 。
返回 结果字符串 。
示例 1：输入：word = "abcdefd", ch = "d" 输出："dcbaefd"
解释："d" 第一次出现在下标 3 。
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "dcbaefd" 。
示例 2：输入：word = "xyxzxe", ch = "z" 输出："zxyxxe"
解释："z" 第一次也是唯一一次出现是在下标 3 。
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。
示例 3：输入：word = "abcd", ch = "z" 输出："abcd"
解释："z" 不存在于 word 中。
无需执行反转操作，结果字符串是 "abcd" 。
提示：1 <= word.length <= 250
word 由小写英文字母组成
ch 是一个小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
func reversePrefix(word string, ch byte) string {
index := strings.Index(word, string(ch))
arr := []byte(word)
reverse(arr[:index+1])
return string(arr)
}
func reverse(arr []byte) []byte {
start := 0
end := len(arr) - 1
for start < end {
arr[start], arr[end] = arr[end], arr[start]
start++
end--
}
return arr
}
1901-2000-Medium
1901.找出顶峰元素II(3)
一个 2D 网格中的 顶峰元素 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。
找出 任意一个 顶峰元素 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
示例 1:输入: mat = [[1,4],[3,2]] 输出: [0,1]
解释:3和4都是顶峰元素，所以[1,0]和[0,1]都是可接受的答案。
示例 2:输入: mat = [[10,20,15],[21,30,14],[7,16,32]] 输出: [1,1]
解释:30和32都是顶峰元素，所以[1,1]和[2,2]都是可接受的答案。
提示：m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 105
任意两个相邻元素均不相等.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
贪心 |
O(n) |
O(1) |
| 03 |
二分查找 |
O(nlog(n)) |
O(1) |
func findPeakGrid(mat [][]int) []int {
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
if (1 <= i && mat[i][j] < mat[i-1][j]) ||
(i < len(mat)-1 && mat[i][j] < mat[i+1][j]) ||
(1 <= j && mat[i][j] < mat[i][j-1]) ||
(j < len(mat[i])-1 && mat[i][j] < mat[i][j+1]) {
continue
}
return []int{i, j}
}
}
return nil
}
# 2
func findPeakGrid(mat [][]int) []int {
n, m := len(mat), len(mat[0])
x, y := 0, 0
for {
if x < n-1 && mat[x][y] < mat[x+1][y] {
x++
} else if 1 <= x && mat[x][y] < mat[x-1][y] {
x--
} else if y < m-1 && mat[x][y] < mat[x][y+1] {
y++
} else if 1 <= y && mat[x][y] < mat[x][y-1] {
y--
} else {
return []int{x, y}
}
}
return nil
}
# 3
func findPeakGrid(mat [][]int) []int {
n := len(mat)
left, right := 0, n-1
for left <= right {
mid := left + (right-left)/2
midValue, index := getMax(mat[mid])
a, b := -1, -1
if mid >= 1 {
a, _ = getMax(mat[mid-1])
}
if mid <= n-2 {
b, _ = getMax(mat[mid+1])
}
res, _ := getMax([]int{a, b, midValue})
if res == midValue {
return []int{mid, index}
} else if res == a {
right = mid - 1
} else {
left = mid + 1
}
}
return nil
}
func getMax(arr []int) (int, int) {
res := arr[0]
index := 0
for i := 0; i < len(arr); i++ {
if arr[i] > res {
index = i
res = arr[i]
}
}
return res, index
}
1904.你完成的完整对局数(1)
一款新的在线电子游戏在近期发布，在该电子游戏中，以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。
这意味着，在 HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23 的整数表示。
游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00，最晚的时间是 23:59 。
给你两个字符串 startTime 和 finishTime ，均符合 "HH:MM" 格式，分别表示你 进入 和 退出 游戏的确切时间，
请计算在整个游戏会话期间，你完成的 完整对局的对局数 。
例如，如果 startTime = "05:20" 且 finishTime = "05:59" ，这意味着你仅仅完成从 05:30 到 05:45 这一个完整对局。
而你没有完成从 05:15 到 05:30 的完整对局，因为你是在对局开始后进入的游戏；
同时，你也没有完成从 05:45 到 06:00 的完整对局，因为你是在对局结束前退出的游戏。
如果 finishTime 早于 startTime ，这表示你玩了个通宵（也就是从 startTime 到午夜，再从午夜到 finishTime）。
假设你是从startTime 进入游戏，并在finishTime 退出游戏，请计算并返回你完成的 完整对局的对局数 。
示例 1：输入：startTime = "12:01", finishTime = "12:44" 输出：1
解释：你完成了从 12:15 到 12:30 的一个完整对局。
你没有完成从 12:00 到 12:15 的完整对局，因为你是在对局开始后的 12:01 进入的游戏。
你没有完成从 12:30 到 12:45 的完整对局，因为你是在对局结束前的 12:44 退出的游戏。
示例 2：输入：startTime = "20:00", finishTime = "06:00" 输出：40
解释：你完成了从 20:00 到 00:00 的 16 个完整的对局，以及从 00:00 到 06:00 的 24 个完整的对局。
16 + 24 = 40
示例 3：输入：startTime = "00:00", finishTime = "23:59" 输出：95
解释：除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。
提示：startTime 和 finishTime 的格式为 HH:MM
00 <= HH <= 23
00 <= MM <= 59
startTime 和 finishTime 不相等
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(1) |
O(1) |
func numberOfRounds(startTime string, finishTime string) int {
a, _ := strconv.Atoi(startTime[:2])
b, _ := strconv.Atoi(startTime[3:])
c, _ := strconv.Atoi(finishTime[:2])
d, _ := strconv.Atoi(finishTime[3:])
t1 := 60*a + b
t2 := 60*c + d
if t2 < t1 {
t2 = t2 + 1440
}
start := int(math.Ceil(float64(t1) / float64(15)))
finish := int(math.Floor(float64(t2) / float64(15)))
if finish - start >= 0{
return finish-start
}
return 0
}
1905.统计子岛屿(2)
给你两个m x n的二进制矩阵grid1 和grid2，它们只包含0（表示水域）和 1（表示陆地）。
一个 岛屿是由 四个方向（水平或者竖直）上相邻的1组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2的一个岛屿，被 grid1的一个岛屿完全 包含，
也就是说 grid2中该岛屿的每一个格子都被 grid1中同一个岛屿完全包含，那么我们称 grid2中的这个岛屿为 子岛屿。
请你返回 grid2中 子岛屿的 数目。
示例 1：输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]],
grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
示例 2：输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]],
grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出：2
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。
提示：m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] 和grid2[i][j]都要么是0要么是1。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(1) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n) |
func countSubIslands(grid1 [][]int, grid2 [][]int) int {
res := 0
for i := 0; i < len(grid2); i++ {
for j := 0; j < len(grid2[i]); j++ {
if grid2[i][j] == 1 {
if dfs(grid1, grid2, i, j) == true {
res++
}
}
}
}
return res
}
func dfs(grid1, grid2 [][]int, i, j int) bool {
if i < 0 || j < 0 || i >= len(grid2) || j >= len(grid2[0]) || grid2[i][j] == 0 {
return true
}
if grid1[i][j] == 0 {
return false
}
grid1[i][j], grid2[i][j] = 0, 0
res1 := dfs(grid1, grid2, i+1, j)
res2 := dfs(grid1, grid2, i-1, j)
res3 := dfs(grid1, grid2, i, j+1)
res4 := dfs(grid1, grid2, i, j-1)
if res1 == false || res2 == false || res3 == false || res4 == false {
return false
}
return true
}
# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
func countSubIslands(grid1 [][]int, grid2 [][]int) int {
res := 0
for i := 0; i < len(grid2); i++ {
for j := 0; j < len(grid2[i]); j++ {
if grid2[i][j] == 1 {
if bfs(grid1, grid2, i, j) == true {
res++
}
}
}
}
return res
}
func bfs(grid1, grid2 [][]int, i, j int) bool {
queue := make([][2]int, 0)
queue = append(queue, [2]int{i, j})
flag := true
if grid1[i][j] == 0 {
flag = false
}
grid1[i][j] = 0
grid2[i][j] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for i := 0; i < 4; i++ {
x := node[0] + dx[i]
y := node[1] + dy[i]
if 0 <= x && x < len(grid2) &&
0 <= y && y < len(grid2[0]) &&
grid2[x][y] == 1 {
queue = append(queue, [2]int{x, y})
if grid1[x][y] == 0 {
flag = false
}
grid1[x][y] = 0
grid2[x][y] = 0
}
}
}
return flag
}
1906.查询差绝对值的最小值(2)
一个数组 a的 差绝对值的最小值定义为：0 <= i < j < a.length且 a[i] != a[j]的 |a[i] - a[j]| 的 最小值。
如果 a中所有元素都 相同，那么差绝对值的最小值为 -1。
比方说，数组[5,2,3,7,2]差绝对值的最小值是|2 - 3| = 1。注意答案不为 0，因为a[i] 和a[j]必须不相等。
给你一个整数数组nums和查询数组queries，其中queries[i] = [li, ri]。
对于每个查询i，计算子数组nums[li...ri]中 差绝对值的最小值 ，
子数组nums[li...ri] 包含 nums数组（下标从 0开始）中下标在 li 和ri 之间的所有元素（包含li 和ri 在内）。
请你返回ans数组，其中 ans[i]是第 i个查询的答案。
子数组是一个数组中连续的一段元素。
|x|的值定义为：
如果x >= 0，那么值为x。
如果x < 0，那么值为-x。
示例 1：输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]] 输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。
示例 2：输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
- queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
- queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
- queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。
提示：2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2* 104
0 <= li < ri < nums.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(n) |
| 02 |
树状数组 |
O(nlog(n)) |
O(n) |
func minDifference(nums []int, queries [][]int) []int {
n := len(nums)
arr := make([][101]int, n+1)
for i := 1; i <= n; i++ {
arr[i] = arr[i-1]
arr[i][nums[i-1]]++
}
res := make([]int, len(queries))
for i := 0; i < len(queries); i++ {
res[i] = -1
left, right := queries[i][0], queries[i][1]
prev, minValue := 0, math.MaxInt32
for j := 1; j <= 100; j++ {
if arr[right+1][j] != arr[left][j] {
if prev != 0 {
if j-prev < minValue {
minValue = j - prev
}
}
prev = j
}
}
if minValue != math.MaxInt32 {
res[i] = minValue
}
}
return res
}
# 2
func minDifference(nums []int, queries [][]int) []int {
n := len(nums)
length = n
c = make([][]int, 101)
for i := 0; i < 101; i++ {
c[i] = make([]int, n+1)
}
for i := 1; i <= n; i++ {
upData(nums[i-1], i, 1)
}
res := make([]int, len(queries))
for i := 0; i < len(queries); i++ {
res[i] = -1
left, right := queries[i][0], queries[i][1]
prev, minValue := 0, math.MaxInt32
for j := 1; j <= 100; j++ {
count := getSum(j, right+1) - getSum(j, left)
if count > 0 {
if prev != 0 {
if j-prev < minValue {
minValue = j - prev
}
}
prev = j
}
}
if minValue != math.MaxInt32 {
res[i] = minValue
}
}
return res
}
var length int
var c [][]int
func lowBit(x int) int {
return x & (-x)
}
func upData(index, i, k int) {
for i <= length {
c[index][i] = c[index][i] + k
i = i + lowBit(i)
}
}
func getSum(index, i int) int {
res := 0
for i > 0 {
res = res + c[index][i]
i = i - lowBit(i)
}
return res
}
1910.删除一个字符串中所有出现的给定子字符串(2)
给你两个字符串s和part，请你对s反复执行以下操作直到 所有子字符串part都被删除：
找到 s中 最左边的子字符串 part，并将它从 s中删除。
请你返回从 s中删除所有 part子字符串以后得到的剩余字符串。
一个 子字符串是一个字符串中连续的字符序列。
示例 1：输入：s = "daabcbaabcbc", part = "abc" 输出："dab"
解释：以下操作按顺序执行：
- s = "daabcbaabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。
- s = "dabaabcbc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。
- s = "dababc" ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。
此时 s 中不再含有子字符串 "abc" 。
示例 2：输入：s = "axxxxyyyyb", part = "xy" 输出："ab"
解释：以下操作按顺序执行：
- s = "axxxxyyyyb" ，删除下标从 4 开始的 "xy" ，得到 s = "axxxyyyb" 。
- s = "axxxyyyb" ，删除下标从 3 开始的 "xy" ，得到 s = "axxyyb" 。
- s = "axxyyb" ，删除下标从 2 开始的 "xy" ，得到 s = "axyb" 。
- s = "axyb" ，删除下标从 1 开始的 "xy" ，得到 s = "ab" 。
此时 s 中不再含有子字符串 "xy" 。
提示：1 <= s.length <= 1000
1 <= part.length <= 1000
s和part只包小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n^2) |
O(n) |
| 02 |
内置函数 |
O(n^2) |
O(n) |
func removeOccurrences(s string, part string) string {
for strings.Contains(s, part) {
s = strings.Replace(s, part, "", 1)
}
return s
}
# 2
func removeOccurrences(s string, part string) string {
for {
index := strings.Index(s, part)
if index < 0 {
return s
}
s = s[:index] + s[index+len(part):]
}
return s
}
1911.最大子序列交替和(3)
一个下标从 0开始的数组的 交替和定义为 偶数下标处元素之 和减去 奇数下标处元素之 和。
比方说，数组[4,2,5,3]的交替和为(4 + 5) - (2 + 3) = 4。
给你一个数组nums，请你返回nums中任意子序列的最大交替和（子序列的下标 重新从 0 开始编号）。
一个数组的 子序列是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。
比方说，[2,7,4]是[4,2,3,7,2,1,4]的一个子序列（加粗元素），但是[2,4,2] 不是。
示例 1：输入：nums = [4,2,5,3] 输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。
示例 2：输入：nums = [5,6,7,8] 输出：8
解释：最优子序列为 [8] ，交替和为 8 。
示例 3：输入：nums = [6,2,1,2,4,5] 输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
贪心法 |
O(n) |
O(n) |
func maxAlternatingSum(nums []int) int64 {
n := len(nums)
odd, even := 0, nums[0]
for i := 1; i < n; i++ {
odd, even = max(even-nums[i], odd), max(odd+nums[i], even)
}
return int64(even)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxAlternatingSum(nums []int) int64 {
n := len(nums)
dp := make([][2]int, n)
dp[0][0] = int(nums[0])
dp[0][1] = 0
for i := 1; i < n; i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i])
dp[i][1] = max(dp[i-1][1], dp[i][0]-nums[i])
}
return int64(max(dp[n-1][0], dp[n-1][1]))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func maxAlternatingSum(nums []int) int64 {
nums = append([]int{0}, nums...)
res := 0
for i := 1; i < len(nums); i++ {
if nums[i] > nums[i-1] {
res = res + nums[i] - nums[i-1]
}
}
return int64(res)
}
1914.循环轮转矩阵(1)
给你一个大小为 m x n 的整数矩阵 grid，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。
矩阵由若干层组成，如下图所示，每种颜色代表一层：
矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。
在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其逆时针 方向的相邻元素。轮转示例如下：
返回执行 k 次循环轮转操作后的矩阵。
示例 1：输入：grid = [[40,10],[30,20]], k = 1 输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。
示例 2：输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。
提示：m == grid.length
n == grid[i].length
2 <= m, n <= 50
m 和 n 都是 偶数
1 <= grid[i][j] <= 5000
1 <= k <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n) |
func rotateGrid(grid [][]int, k int) [][]int {
n, m := len(grid), len(grid[0])
count := min(n/2, m/2)
for level := 0; level < count; level++ {
arr := make([][3]int, 0)
for i := level; i < n-1-level; i++ {
arr = append(arr, [3]int{i, level, grid[i][level]})
}
for j := level; j < m-1-level; j++ {
arr = append(arr, [3]int{n - 1 - level, j, grid[n-1-level][j]})
}
for i := n - 1 - level; i > level; i-- {
arr = append(arr, [3]int{i, m - 1 - level, grid[i][m-1-level]})
}
for j := m - 1 - level; j > level; j-- {
arr = append(arr, [3]int{level, j, grid[level][j]})
}
total := len(arr)
step := k % total
for i := 0; i < total; i++ {
index := (i + total - step) % total
a, b, c := arr[i][0], arr[i][1], arr[index][2]
grid[a][b] = c
}
}
return grid
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1915.最美子字符串的数目(1)
如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。
例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。
请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：word = "aba" 输出：4
解释：4 个最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"
示例 2：输入：word = "aabb" 输出：9
解释：9 个最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"
示例 3：输入：word = "he" 输出：2
解释：2 个最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"
提示：1 <= word.length <= 105
word 由从 'a' 到 'j' 的小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+位运算 |
O(n) |
O(1) |
func wonderfulSubstrings(word string) int64 {
res := 0
m := make(map[int]int)
m[0] = 1
cur := 0
for i := 0; i < len(word); i++ {
value := int(word[i] - 'a')
cur = cur ^ (1 << value)
res = res + m[cur]
for i := 0; i < 10; i++ {
count := m[cur^(1<<i)]
res = res + count
}
m[cur]++
}
return int64(res)
}
1921.消灭怪物的最大数量(1)
你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。
给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
怪物以 恒定 的速度走向城市。
给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
怪物从 第 0 分钟 时开始移动。你有一把武器，并可以 选择 在每一分钟的开始时使用，包括第 0 分钟。
但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市，你就输掉了这场游戏。
如果某个怪物 恰 在某一分钟开始时到达城市，这会被视为 输掉游戏，在你可以使用武器之前，游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 n 。
示例 1：输入：dist = [1,3,4], speed = [1,1,1] 输出：3
解释：第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你没有消灭任何怪物。
第 2 分钟开始时，怪物的距离是 [X,1,2]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,1]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。
示例 2：输入：dist = [1,1,2,3], speed = [1,1,1,1] 输出：1
解释：第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,1,2]，你输掉了游戏。
你只能消灭 1 个怪物。
示例 3：输入：dist = [3,2,4], speed = [5,3,2] 输出：1
解释：第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。
你只能消灭 1 个怪物。
提示：n == dist.length == speed.length
1 <= n <= 105
1 <= dist[i], speed[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(n) |
func eliminateMaximum(dist []int, speed []int) int {
res := 0
temp := make([]float64, len(dist))
for i := 0; i < len(dist); i++ {
temp[i] = float64(dist[i]) / float64(speed[i])
}
sort.Slice(temp, func(i, j int) bool {
return temp[i] < temp[j]
})
for i := 0; i < len(dist); i++ {
if float64(i) < temp[i] {
res++
} else {
break
}
}
return res
}
1922.统计好数字的数目(2)
我们称一个数字字符串是 好数字 当它满足（下标从 0开始）偶数 下标处的数字为 偶数且 奇数下标处的数字为 质数（2，3，5或7）。
比方说，"2582"是好数字，因为偶数下标处的数字（2和8）是偶数且奇数下标处的数字（5 和2）为质数。
但"3245"不是 好数字，因为3在偶数下标处但不是偶数。
给你一个整数n，请你返回长度为n且为好数字的数字字符串总数。由于答案可能会很大，请你将它对109 + 7取余后返回。
一个 数字字符串是每一位都由0到 9组成的字符串，且可能包含前导 0 。
示例 1：输入：n = 1 输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
示例 2：输入：n = 4 输出：400
示例 3：输入：n = 50 输出：564908303
提示：1 <= n <= 1015
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
快速幂 |
O(log(n)) |
O(1) |
| 02 |
快速幂 |
O(log(n)) |
O(1) |
var mod = int64(1000000007)
func countGoodNumbers(n int64) int {
res := mypow(20, n/2)
if n%2 == 1 {
res = res * 5 % mod
}
return int(res)
}
func mypow(a int64, n int64) int64 {
var res = int64(1)
for n > 0 {
if n%2 == 1 {
res = res * a % mod
}
a = a * a % mod
n = n / 2
}
return res
}
# 2
var mod = int64(1000000007)
func countGoodNumbers(n int64) int {
return int(mypow(5, (n+1)/2) * mypow(4, n/2) % mod)
}
func mypow(a int64, n int64) int64 {
var res = int64(1)
for n > 0 {
if n%2 == 1 {
res = res * a % mod
}
a = a * a % mod
n = n / 2
}
return res
}
1926.迷宫中离入口最近的出口(1)
给你一个m x n的迷宫矩阵maze（下标从 0 开始），矩阵中有空格子（用'.'表示）和墙（用'+'表示）。
同时给你迷宫的入口entrance，用entrance = [entrancerow, entrancecol]表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。
你的目标是找到离entrance最近的出口。出口的含义是maze边界上的空格子。entrance格子不算出口。
请你返回从 entrance到最近出口的最短路径的 步数，如果不存在这样的路径，请你返回 -1。
示例 1：输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] 输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。
示例 2：输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] 输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。
示例 3：输入：maze = [[".","+"]], entrance = [0,0] 输出：-1
解释：这个迷宫中没有出口。
提示：maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] 要么是'.'，要么是'+'。
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance一定是空格子。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n^2) |
O(n) |
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
func nearestExit(maze [][]byte, entrance []int) int {
n, m := len(maze), len(maze[0])
queue := make([][2]int, 0)
visited := make(map[[2]int]bool)
queue = append(queue, [2]int{entrance[0], entrance[1]})
visited[[2]int{entrance[0], entrance[1]}] = true
count := 0
for len(queue) > 0 {
count++
length := len(queue)
for i := 0; i < length; i++ {
a, b := queue[i][0], queue[i][1]
for j := 0; j < 4; j++ {
x := a + dx[j]
y := b + dy[j]
if 0 <= x && x < n && 0 <= y && y < m &&
maze[x][y] != '+' && visited[[2]int{x, y}] == false {
if (x == 0 || x == n-1 || y == 0 || y == m-1) && maze[x][y] == '.' {
return count
}
queue = append(queue, [2]int{x, y})
visited[[2]int{x, y}] = true
}
}
}
queue = queue[length:]
}
return -1
}
1927.求和游戏(1)
Alice 和 Bob 玩一个游戏，两人轮流行动，Alice 先手。
给你一个 偶数长度的字符串num，每一个字符为数字字符或者'?'。
每一次操作中，如果 num中至少有一个 '?'，那么玩家可以执行以下操作：
选择一个下标 i满足num[i] == '?'。
将num[i]用'0'到'9'之间的一个数字字符替代。
当 num中没有 '?' 时，游戏结束。
Bob 获胜的条件是 num中前一半数字的和 等于后一半数字的和。
Alice 获胜的条件是前一半的和与后一半的和 不相等。
比方说，游戏结束时num = "243801"，那么Bob 获胜，因为2+4+3 = 8+0+1。
如果游戏结束时num = "243803"，那么 Alice 获胜，因为2+4+3 != 8+0+3。
在 Alice 和 Bob 都采取 最优策略的前提下，如果 Alice 获胜，请返回 true，如果 Bob 获胜，请返回 false。
示例 1：输入：num = "5023" 输出：false
解释：num 中没有 '?' ，没法进行任何操作。
前一半的和等于后一半的和：5 + 0 = 2 + 3 。
示例 2：输入：num = "25??" 输出：true
解释：Alice 可以将两个 '?' 中的一个替换为 '9' ，Bob 无论如何都无法使前一半的和等于后一半的和。
示例 3：输入：num = "?3295???" 输出：false
解释：Bob 总是能赢。一种可能的结果是：
- Alice 将第一个 '?' 用 '9' 替换。num = "93295???" 。
- Bob 将后面一半中的一个 '?' 替换为 '9' 。num = "932959??" 。
- Alice 将后面一半中的一个 '?' 替换为 '2' 。num = "9329592?" 。
- Bob 将后面一半中最后一个 '?' 替换为 '7' 。num = "93295927" 。
Bob 获胜，因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。
提示：2 <= num.length <= 105
num.length是 偶数。
num只包含数字字符和'?'。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(1) |
func sumGame(num string) bool {
n := len(num)
leftSum, rightSum := 0, 0
leftCount, rightCount := 0, 0
for i := 0; i < n; i++ {
if i < n/2 {
if num[i] == '?' {
leftCount++
} else {
leftSum = leftSum + int(num[i]-'0')
}
} else {
if num[i] == '?' {
rightCount++
} else {
rightSum = rightSum + int(num[i]-'0')
}
}
}
if (leftCount+rightCount)%2 == 1 {
return true
}
if leftSum-rightSum != (rightCount-leftCount)*9/2 {
return true
}
return false
}
1930.长度为3的不同回文子序列(3)
给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。
即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。
回文 是正着读和反着读一样的字符串。
子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。
例如，"ace" 是 "abcde" 的一个子序列。
示例 1：输入：s = "aabca"输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)
示例 2：输入：s = "adc"输出：0
解释："adc" 不存在长度为 3 的回文子序列。
示例 3：输入：s = "bbcbaba" 输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)
提示：3 <= s.length <= 105
s 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
| 03 |
遍历+位运算 |
O(n) |
O(n) |
func countPalindromicSubsequence(s string) int {
n := len(s)
arr := [26][]int{}
for i := 0; i < n; i++ {
index := int(s[i] - 'a')
arr[index] = append(arr[index], i)
}
m := make(map[string]bool)
for i := 0; i < 26; i++ {
if len(arr[i]) <= 1 {
continue
}
left, right := arr[i][0], arr[i][len(arr[i])-1]
for j := 0; j < 26; j++ {
if len(arr[j]) == 0 {
continue
}
if i == j && len(arr[i]) > 2 {
m[fmt.Sprintf("%d,%d,%d", i, i, i)] = true
continue
}
flag := false
for k := 0; k < len(arr[j]); k++ {
if left < arr[j][k] && arr[j][k] < right {
flag = true
break
}
}
if flag == true {
m[fmt.Sprintf("%d,%d,%d", i, j, i)] = true
}
}
}
return len(m)
}
# 2
func countPalindromicSubsequence(s string) int {
n := len(s)
res := 0
for i := 0; i < 26; i++ {
left, right := 0, n-1
for left < n && s[left] != byte(i+'a') {
left++
}
for right >= 0 && s[right] != byte(i+'a') {
right--
}
if left+2 > right {
continue
}
m := make(map[byte]int)
for k := left + 1; k < right; k++ {
m[s[k]] = 1
}
res = res + len(m)
}
return res
}
# 3
func countPalindromicSubsequence(s string) int {
n := len(s)
res := 0
pre, suf := make([]int, n+1), make([]int, n+1)
arr := make([]int, 26)
for i := 0; i < n; i++ {
pre[i+1] = pre[i] | (1 << int(s[i]-'a'))
}
for i := n - 1; i >= 0; i-- {
suf[i] = suf[i+1] | (1 << int(s[i]-'a'))
}
for i := 1; i < n-1; i++ {
index := int(s[i] - 'a')
arr[index] = arr[index] | (pre[i] & suf[i+1])
}
for i := 0; i < 26; i++ {
res = res + bits.OnesCount(uint(arr[i]))
}
return res
}
1936.新增的最少台阶数(1)
给你一个 严格递增 的整数数组 rungs ，用于表示梯子上每一台阶的 高度 。
当前你正站在高度为 0 的地板上，并打算爬到最后一个台阶。
另给你一个整数 dist 。每次移动中，你可以到达下一个距离你当前位置（地板或台阶）不超过dist高度的台阶。
当然，你也可以在任何正 整数 高度处插入尚不存在的新台阶。
返回爬到最后一阶时必须添加到梯子上的 最少台阶数。
示例 1：输入：rungs = [1,3,5,10], dist = 2 输出：2
解释：现在无法到达最后一阶。
在高度为 7 和 8 的位置增设新的台阶，以爬上梯子。
梯子在高度为 [1,3,5,7,8,10] 的位置上有台阶。
示例 2：输入：rungs = [3,6,8,10], dist = 3 输出：0
解释：这个梯子无需增设新台阶也可以爬上去。
示例 3：输入：rungs = [3,4,6,7], dist = 2 输出：1
解释：现在无法从地板到达梯子的第一阶。
在高度为 1 的位置增设新的台阶，以爬上梯子。
梯子在高度为 [1,3,4,6,7] 的位置上有台阶。
示例 4：输入：rungs = [5], dist = 10 输出：0
解释：这个梯子无需增设新台阶也可以爬上去。
提示：1 <= rungs.length <= 105
1 <= rungs[i] <= 109
1 <= dist <= 109
rungs 严格递增
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func addRungs(rungs []int, dist int) int {
res := 0
cur := 0
for i := 0; i < len(rungs); i++{
res = res + (rungs[i]-cur-1)/dist
cur = rungs[i]
}
return res
}
1937.扣分后的最大得分(3)
给你一个m x n的整数矩阵points（下标从 0开始）。一开始你的得分为 0，你想最大化从矩阵中得到的分数。
你的得分方式为：每一行中选取一个格子，选中坐标为(r, c)的格子会给你的总得分 增加points[r][c]。
然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。
对于相邻行r 和r + 1（其中0 <= r < m - 1），选中坐标为(r, c1) 和(r + 1, c2)的格子，
你的总得分减少abs(c1 - c2)。
请你返回你能得到的 最大得分。
abs(x)定义为：如果x >= 0，那么值为x。如果x <0，那么值为 -x。
示例 1：输入：points = [[1,2,3],[1,5,1],[3,1,1]] 输出：9
解释：蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。
示例 2：输入：points = [[1,5],[2,3],[4,2]] 输出：11
解释：蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
你的总得分增加 5 + 3 + 4 = 12 。
但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
你的最终得分为 12 - 1 = 11 。
提示：m == points.length
n == points[r].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= points[r][c] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
动态规划+前缀和 |
O(n^2) |
O(n) |
func maxPoints(points [][]int) int64 {
n, m := len(points), len(points[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
for j := 0; j < m; j++ {
dp[0][j] = points[0][j]
}
for i := 1; i < n; i++ {
maxValue := math.MinInt32
for j := 0; j < m; j++ {
maxValue = max(maxValue, dp[i-1][j]+j)
dp[i][j] = max(dp[i][j], maxValue+points[i][j]-j)
}
maxValue = math.MinInt32
for j := m - 1; j >= 0; j-- {
maxValue = max(maxValue, dp[i-1][j]-j)
dp[i][j] = max(dp[i][j], maxValue+points[i][j]+j)
}
}
res := 0
for j := 0; j < m; j++ {
res = max(res, dp[n-1][j])
}
return int64(res)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxPoints(points [][]int) int64 {
n, m := len(points), len(points[0])
dp := make([]int, m)
for i := 0; i < n; i++ {
temp := make([]int, m)
maxValue := math.MinInt32
for j := 0; j < m; j++ {
maxValue = max(maxValue, dp[j]+j)
temp[j] = max(temp[j], maxValue+points[i][j]-j)
}
maxValue = math.MinInt32
for j := m - 1; j >= 0; j-- {
maxValue = max(maxValue, dp[j]-j)
temp[j] = max(temp[j], maxValue+points[i][j]+j)
}
copy(dp, temp)
}
res := 0
for j := 0; j < m; j++ {
res = max(res, dp[j])
}
return int64(res)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func maxPoints(points [][]int) int64 {
n, m := len(points), len(points[0])
dp := make([]int, m)
for i := 0; i < n; i++ {
temp := make([]int, m)
leftArr := make([]int, m)
rightArr := make([]int, m)
leftArr[0] = dp[0]
rightArr[m-1] = dp[m-1] - (m - 1)
for j := 1; j < m; j++ {
leftArr[j] = max(leftArr[j-1], dp[j]+j)
}
for j := m - 2; j >= 0; j-- {
rightArr[j] = max(rightArr[j+1], dp[j]-j)
}
for j := 0; j < m; j++ {
temp[j] = points[i][j] + max(leftArr[j]-j, rightArr[j]+j)
}
copy(dp, temp)
}
res := 0
for j := 0; j < m; j++ {
res = max(res, dp[j])
}
return int64(res)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1942.最小未被占据椅子的编号(2)
有 n个朋友在举办一个派对，这些朋友从 0到 n - 1编号。派对里有 无数张椅子，编号为 0到 infinity。
当一个朋友到达派对时，他会占据编号最小且未被占据的椅子。
比方说，当一个朋友到达时，如果椅子0，1和5被占据了，那么他会占据2号椅子。
当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。
给你一个下标从 0开始的二维整数数组times，其中times[i] = [arrivali, leavingi]
表示第 i个朋友到达和离开的时刻，同时给你一个整数 targetFriend。所有到达时间 互不相同。
请你返回编号为 targetFriend的朋友占据的 椅子编号。
示例 1：输入：times = [[1,4],[2,3],[4,6]], targetFriend = 1 输出：1
解释：- 朋友 0 时刻 1 到达，占据椅子 0 。
- 朋友 1 时刻 2 到达，占据椅子 1 。
- 朋友 1 时刻 3 离开，椅子 1 变成未占据。
- 朋友 0 时刻 4 离开，椅子 0 变成未占据。
- 朋友 2 时刻 4 到达，占据椅子 0 。
朋友 1 占据椅子 1 ，所以返回 1 。
示例 2：输入：times = [[3,10],[1,5],[2,6]], targetFriend = 0 输出：2
解释：- 朋友 1 时刻 1 到达，占据椅子 0 。
- 朋友 2 时刻 2 到达，占据椅子 1 。
- 朋友 0 时刻 3 到达，占据椅子 2 。
- 朋友 1 时刻 5 离开，椅子 0 变成未占据。
- 朋友 2 时刻 6 离开，椅子 1 变成未占据。
- 朋友 0 时刻 10 离开，椅子 2 变成未占据。
朋友 0 占据椅子 2 ，所以返回 2 。
提示：n == times.length
2 <= n <= 104
times[i].length == 2
1 <= arrivali < leavingi <= 105
0 <= targetFriend <= n - 1
每个arrivali时刻互不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双堆 |
O(nlog(n)) |
O(n) |
| 02 |
堆 |
O(nlog(n)) |
O(n) |
type Node struct {
Index int
ArriveTime int
LeaveTime int
}
func smallestChair(times [][]int, targetFriend int) int {
n := len(times)
arr := make([]Node, 0)
waitHeap := make(WaitHeap, 0)
heap.Init(&waitHeap)
runHeap := make(RunHeap, 0)
heap.Init(&runHeap)
for i := 0; i < n; i++ {
heap.Push(&waitHeap, i)
arr = append(arr, Node{
Index: i,
ArriveTime: times[i][0],
LeaveTime: times[i][1],
})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].ArriveTime < arr[j].ArriveTime
})
cur := 0
for i := 0; i < n; i++ {
cur = arr[i].ArriveTime
for runHeap.Len() > 0 && runHeap[0].EndTime <= cur {
node := heap.Pop(&runHeap).(RunNode)
heap.Push(&waitHeap, node.Id)
}
node := heap.Pop(&waitHeap).(int)
heap.Push(&runHeap, RunNode{
Id: node,
EndTime: arr[i].LeaveTime,
})
if arr[i].Index == targetFriend {
return node
}
}
return -1
}
type WaitHeap []int
func (h WaitHeap) Len() int {
return len(h)
}
func (h WaitHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h WaitHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *WaitHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *WaitHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
type RunNode struct {
Id int
EndTime int
}
type RunHeap []RunNode
func (h RunHeap) Len() int {
return len(h)
}
func (h RunHeap) Less(i, j int) bool {
return h[i].EndTime < h[j].EndTime
}
func (h RunHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *RunHeap) Push(x interface{}) {
*h = append(*h, x.(RunNode))
}
func (h *RunHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
# 2
func smallestChair(times [][]int, targetFriend int) int {
n := len(times)
waitHeap := make(WaitHeap, 0)
heap.Init(&waitHeap)
arriveArr := make([][2]int, 0)
leaveArr := make([][2]int, 0)
for i := 0; i < n; i++ {
heap.Push(&waitHeap, i)
arriveArr = append(arriveArr, [2]int{i, times[i][0]})
leaveArr = append(leaveArr, [2]int{i, times[i][1]})
}
sort.Slice(arriveArr, func(i, j int) bool {
return arriveArr[i][1] < arriveArr[j][1]
})
sort.Slice(leaveArr, func(i, j int) bool {
return leaveArr[i][1] < leaveArr[j][1]
})
j := 0
m := make(map[int]int)
for i := 0; i < n; i++ {
for j < n && leaveArr[j][1] <= arriveArr[i][1] {
heap.Push(&waitHeap, m[leaveArr[j][0]])
j++
}
target := heap.Pop(&waitHeap).(int)
m[arriveArr[i][0]] = target
if arriveArr[i][0] == targetFriend {
return target
}
}
return -1
}
type WaitHeap []int
func (h WaitHeap) Len() int {
return len(h)
}
func (h WaitHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h WaitHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *WaitHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *WaitHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1943.描述绘画结果(3)
给你一个细长的画，用数轴表示。这幅画由若干有重叠的线段表示，每个线段有 独一无二的颜色。
给你二维整数数组segments，
其中segments[i] = [starti, endi, colori]表示线段为半开区间[starti, endi) 且颜色为colori。
线段间重叠部分的颜色会被 混合。如果有两种或者更多颜色混合时，它们会形成一种新的颜色，用一个 集合表示这个混合颜色。
比方说，如果颜色2，4和6被混合，那么结果颜色为{2,4,6}。
为了简化题目，你不需要输出整个集合，只需要用集合中所有元素的 和来表示颜色集合。
你想要用 最少数目不重叠 半开区间来 表示这幅混合颜色的画。这些线段可以用二维数组painting表示，
其中 painting[j] = [leftj, rightj, mixj]表示一个半开区间[leftj, rightj)的颜色 和为mixj。
比方说，这幅画由segments = [[1,4,5],[1,7,7]]组成，那么它可以表示为painting = [[1,4,12],[4,7,7]]，因为：
[1,4)由颜色{5,7}组成（和为12），分别来自第一个线段和第二个线段。
[4,7)由颜色 {7}组成，来自第二个线段。
请你返回二维数组painting，它表示最终绘画的结果（没有被涂色的部分不出现在结果中）。
你可以按 任意顺序 返回最终数组的结果。
半开区间[a, b)是数轴上点a 和点b之间的部分，包含 点a且 不包含点b。
示例 1：输入：segments = [[1,4,5],[4,7,7],[1,7,9]] 输出：[[1,4,14],[4,7,16]]
解释：绘画借故偶可以表示为：
- [1,4) 颜色为 {5,9} （和为 14），分别来自第一和第二个线段。
- [4,7) 颜色为 {7,9} （和为 16），分别来自第二和第三个线段。
示例 2：输入：segments = [[1,7,9],[6,8,15],[8,10,7]] 输出：[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
解释：绘画结果可以以表示为：
- [1,6) 颜色为 9 ，来自第一个线段。
- [6,7) 颜色为 {9,15} （和为 24），来自第一和第二个线段。
- [7,8) 颜色为 15 ，来自第二个线段。
- [8,10) 颜色为 7 ，来自第三个线段。
示例 3：输入：segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]] 输出：[[1,4,12],[4,7,12]]
解释：绘画结果可以表示为：
- [1,4) 颜色为 {5,7} （和为 12），分别来自第一和第二个线段。
- [4,7) 颜色为 {1,11} （和为 12），分别来自第三和第四个线段。
注意，只返回一个单独的线段 [1,7) 是不正确的，因为混合颜色的集合不相同。
提示：1 <= segments.length <= 2 * 104
segments[i].length == 3
1 <= starti < endi <= 105
1 <= colori <= 109
每种颜色colori互不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双差分数组 |
O(n) |
O(n) |
| 02 |
差分数组+前缀和 |
O(nlog(n)) |
O(n) |
| 03 |
差分数组+哈希 |
O(n) |
O(n) |
func splitPainting(segments [][]int) [][]int64 {
res := make([][]int64, 0)
arr1 := make([]int64, 100005)
arr2 := make([]int64, 100005)
n := len(segments)
for i := 0; i < n; i++ {
start := segments[i][0]
end := segments[i][1]
count := segments[i][2]
arr1[start], arr2[start] = arr1[start]+int64(count), arr1[start]+1
arr1[end], arr2[end] = arr1[end]-int64(count), arr1[end]-1
}
prevIndex := -1
var prev1, prev2 int64
var sum1, sum2 int64
for i := 1; i < 100005; i++ {
sum1 = sum1 + arr1[i]
sum2 = sum2 + arr2[i]
if sum1 > 0 {
if prevIndex == -1 {
prevIndex = i
prev1, prev2 = sum1, sum2
} else if prev1 != sum1 {
res = append(res, []int64{int64(prevIndex), int64(i), prev1})
prevIndex = i
prev1, prev2 = sum1, sum2
} else {
if prev2 != sum2 {
res = append(res, []int64{int64(prevIndex), int64(i), prev1})
prevIndex = i
prev1, prev2 = sum1, sum2
}
}
} else if sum1 == 0 {
if prevIndex > 0 {
res = append(res, []int64{int64(prevIndex), int64(i), prev1})
prevIndex = -1
prev1, prev2 = sum1, sum2
}
}
}
return res
}
# 2
func splitPainting(segments [][]int) [][]int64 {
res := make([][]int64, 0)
m := make(map[int]int)
for i := 0; i < len(segments); i++ {
start := segments[i][0]
end := segments[i][1]
count := segments[i][2]
m[start] = m[start] + count
m[end] = m[end] - count
}
arr := make([][2]int, 0)
for k, v := range m {
arr = append(arr, [2]int{k, v})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] < arr[j][0]
})
n := len(arr)
for i := 1; i < n; i++ {
arr[i][1] = arr[i][1] + arr[i-1][1]
}
for i := 0; i < n-1; i++ {
if arr[i][1] > 0 {
res = append(res, []int64{
int64(arr[i][0]),
int64(arr[i+1][0]),
int64(arr[i][1]),
})
}
}
return res
}
# 3
func splitPainting(segments [][]int) [][]int64 {
res := make([][]int64, 0)
arr := make([]int64, 100005)
m := make([]bool, 100005)
n := len(segments)
for i := 0; i < n; i++ {
start := segments[i][0]
end := segments[i][1]
count := segments[i][2]
arr[start] = arr[start] + int64(count)
arr[end] = arr[end] - int64(count)
m[start] = true
m[end] = true
}
var sum int64
var prev int64
for i := 1; i < 100005; i++ {
if m[i] == true {
if sum > 0 {
res = append(res, []int64{prev, int64(i), sum})
}
sum = sum + arr[i]
prev = int64(i)
}
}
return res
}
1946.子字符串突变后可能得到的最大整数(2)
给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0 开始 的整数数组 change ，
该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。
你可以选择 突变 num 的任一子字符串。
突变 子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。
请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。
子字符串 是字符串中的一个连续序列。
示例 1：输入：num = "132", change = [9,8,5,0,3,6,4,2,6,8] 输出："832"
解释：替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
因此 "132" 变为 "832" 。
"832" 是可以构造的最大整数，所以返回它的字符串表示。
示例 2：输入：num = "021", change = [9,4,3,5,7,2,1,9,0,6] 输出："934"
解释：替换子字符串 "021"：
- 0 映射为 change[0] = 9 。
- 2 映射为 change[2] = 3 。
- 1 映射为 change[1] = 4 。
因此，"021" 变为 "934" 。
"934" 是可以构造的最大整数，所以返回它的字符串表示。
示例 3：输入：num = "5", change = [1,4,7,5,3,2,5,6,9,4] 输出："5"
解释："5" 已经是可以构造的最大整数，所以返回它的字符串表示。
提示：1 <= num.length <= 105
num 仅由数字 0-9 组成
change.length == 10
0 <= change[d] <= 9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
| 02 |
贪心 |
O(n) |
O(n) |
func maximumNumber(num string, change []int) string {
res := []byte(num)
flag := false
for i := 0; i < len(num); i++ {
value := int(num[i] - '0')
if value < change[value] {
flag = true
res[i] = byte(change[value] + '0')
} else if value == change[value] {
res[i] = byte(change[value] + '0')
} else {
if flag == true {
break
}
}
}
return string(res)
}
# 2
func maximumNumber(num string, change []int) string {
res := []byte(num)
for i := 0; i < len(num); i++ {
if getValue(num[i]) < change[getValue(num[i])] {
for i < len(num) && change[getValue(num[i])] >= getValue(num[i]) {
res[i] = byte(change[getValue(num[i])] + '0')
i++
}
break
}
}
return string(res)
}
func getValue(c byte) int {
return int(c - '0')
}
1947.最大兼容性评分和(4)
有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。
这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。
学生的答案用一个二维整数数组 students 表示，
其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。
导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，
包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。
每个学生都会被分配给 一名 导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。
例如，学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。
请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。
给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。
示例 1：输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] 输出：8
解释：按下述方式分配学生和导师：
- 学生 0 分配给导师 2 ，兼容性评分为 3 。
- 学生 1 分配给导师 0 ，兼容性评分为 2 。
- 学生 2 分配给导师 1 ，兼容性评分为 3 。
最大兼容性评分和为 3 + 2 + 3 = 8 。
示例 2：输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]] 输出：0
解释：任意学生与导师配对的兼容性评分都是 0 。
提示：m == students.length == mentors.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k] 为 0 或 1
mentors[j][k] 为 0 或 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^n) |
O(n^2) |
| 02 |
全排列 |
O(n*n!) |
O(n^2) |
| 03 |
动态规划-状态压缩 |
O(n*2^n) |
O(2^n) |
| 04 |
回溯 |
O(n^n) |
O(n^2) |
var arr [][]int
var res int
func maxCompatibilitySum(students [][]int, mentors [][]int) int {
n := len(students)
arr = make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = calculate(students[i], mentors[j])
}
}
res = 0
for i := 0; i < n; i++ {
visited1, visited2 := make([]int, n), make([]int, n)
visited1[0], visited2[i] = 1, 1
dfs(n, visited1, visited2, arr[0][i])
}
return res
}
func dfs(n int, visited1, visited2 []int, sum int) {
if sum > res {
res = sum
}
index := -1
for i := 0; i < n; i++ {
if visited1[i] == 0 {
index = i
break
}
}
if index == -1 {
return
}
for i := 0; i < n; i++ {
if visited2[i] == 1 {
continue
}
temp1 := make([]int, n)
temp2 := make([]int, n)
copy(temp1, visited1)
copy(temp2, visited2)
temp1[index] = 1
temp2[i] = 1
dfs(n, temp1, temp2, sum+arr[index][i])
}
}
func calculate(a, b []int) int {
res := 0
for i := 0; i < len(a); i++ {
if a[i] == b[i] {
res++
}
}
return res
}
# 2
func maxCompatibilitySum(students [][]int, mentors [][]int) int {
n := len(students)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = calculate(students[i], mentors[j])
}
}
temp := make([]int, n)
for i := 0; i < n; i++ {
temp[i] = i
}
res := 0
for {
if temp == nil {
break
}
sum := 0
for i := 0; i < n; i++ {
sum = sum + arr[i][temp[i]]
}
if sum > res {
res = sum
}
temp = nextPermutation(temp)
}
return res
}
func nextPermutation(nums []int) []int {
n := len(nums)
left := n - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left == -1 {
return nil
}
right := n - 1
for right >= 0 && nums[right] <= nums[left] {
right--
}
nums[left], nums[right] = nums[right], nums[left]
count := 0
for i := left + 1; i <= (left+1+n-1)/2; i++ {
nums[i], nums[n-1-count] = nums[n-1-count], nums[i]
count++
}
return nums
}
func calculate(a, b []int) int {
res := 0
for i := 0; i < len(a); i++ {
if a[i] == b[i] {
res++
}
}
return res
}
# 3
func maxCompatibilitySum(students [][]int, mentors [][]int) int {
n := len(students)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = calculate(students[i], mentors[j])
}
}
target := 1 << n
dp := make([]int, target)
for i := 1; i < target; i++ {
count := bits.OnesCount(uint(i))
for j := 0; j < n; j++ {
if i&(1<<j) != 0 {
prev := i ^ (1 << j)
dp[i] = max(dp[i], dp[prev]+arr[count-1][j])
}
}
}
return dp[target-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func calculate(a, b []int) int {
res := 0
for i := 0; i < len(a); i++ {
if a[i] == b[i] {
res++
}
}
return res
}
# 4
var arr [][]int
var res int
func maxCompatibilitySum(students [][]int, mentors [][]int) int {
n := len(students)
arr = make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = calculate(students[i], mentors[j])
}
}
res = 0
for i := 0; i < n; i++ {
visited1, visited2 := make([]int, n), make([]int, n)
visited1[0], visited2[i] = 1, 1
dfs(n, visited1, visited2, arr[0][i])
}
return res
}
func dfs(n int, visited1, visited2 []int, sum int) {
if sum > res {
res = sum
}
index := -1
for i := 0; i < n; i++ {
if visited1[i] == 0 {
index = i
break
}
}
if index == -1 {
return
}
for i := 0; i < n; i++ {
if visited2[i] == 1 {
continue
}
visited1[index] = 1
visited2[i] = 1
dfs(n, visited1, visited2, sum+arr[index][i])
visited1[index] = 0
visited2[i] = 0
}
}
func calculate(a, b []int) int {
res := 0
for i := 0; i < len(a); i++ {
if a[i] == b[i] {
res++
}
}
return res
}
1953.你可以工作的最大周数(1)
给你n 个项目，编号从 0 到 n - 1 。
同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。
你可以按下面两个规则参与项目中的工作：每周，你将会完成 某一个 项目中的 恰好一个阶段任务。你每周都 必须 工作。
在 连续的 两周中，你 不能 参与并完成同一个项目中的两个阶段任务。
一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将停止工作 。
注意，由于这些条件的限制，你可能无法完成所有阶段任务。
返回在不违反上面规则的情况下你最多能工作多少周。
示例 1：输入：milestones = [1,2,3] 输出：6
解释：一种可能的情形是：- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。
示例 2：输入：milestones = [5,2,1] 输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。
提示：n == milestones.length
1 <= n <= 105
1 <= milestones[i] <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func numberOfWeeks(milestones []int) int64 {
var maxCount int64
var sum int64
for i := 0; i < len(milestones); i++ {
if int64(milestones[i]) > maxCount {
maxCount = int64(milestones[i])
}
sum = sum + int64(milestones[i])
}
if maxCount > (sum+1)/2 {
return (sum-maxCount)*2 + 1
}
return sum
}
1954.收集足够苹果的最小花园周长(3)
给你一个用无限二维网格表示的花园，每一个整数坐标处都有一棵苹果树。整数坐标(i, j)处的苹果树有 |i| + |j|个苹果。
你将会买下正中心坐标是 (0, 0)的一块 正方形土地，且每条边都与两条坐标轴之一平行。
给你一个整数neededApples，请你返回土地的最小周长，使得至少有neededApples个苹果在土地里面或者边缘上。
|x|的值定义为：
如果x >= 0，那么值为x
如果x <0，那么值为-x
示例 1：输入：neededApples = 1 输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。
示例 2：输入：neededApples = 13 输出：16
示例 3：输入：neededApples = 1000000000 输出：5040
提示：1 <= neededApples <= 1015
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^(1/2)) |
O(1) |
| 02 |
遍历 |
O(n^(1/3)) |
O(1) |
| 03 |
二分查找 |
O(log(n)) |
O(1) |
func minimumPerimeter(neededApples int64) int64 {
var total int64
var i int64
var sum int64
for i = 0; ; i = i + 2 {
sum = 3 * i * i
total = total + sum
if neededApples <= total {
return int64(i) * 4
}
}
return 0
}
# 2
func minimumPerimeter(neededApples int64) int64 {
var i int64
for i = 1; ; i = i + 1 {
total := 2 * i * (i + 1) * (2*i + 1)
if neededApples <= total {
return i * 8
}
}
return 0
}
# 3
func minimumPerimeter(neededApples int64) int64 {
var res, left, right int64
left = 1
right = 100000
for left <= right {
mid := left + (right-left)/2
total := 2 * mid * (mid + 1) * (2*mid + 1)
if total >= neededApples {
res = mid
right = mid - 1
} else {
left = mid + 1
}
}
return res * 8
}
1958.检查操作是否合法(1)
给你一个下标从0开始的8 x 8 网格board，其中board[r][c]表示游戏棋盘上的格子(r, c)。
棋盘上空格用'.'表示，白色格子用'W'表示，黑色格子用'B'表示。
游戏中每次操作步骤为：选择一个空格子，将它变成你正在执行的颜色（要么白色，要么黑色）。
但是，合法 操作必须满足：涂色后这个格子是 好线段的一个端点（好线段可以是水平的，竖直的或者是对角线）。
好线段指的是一个包含 三个或者更多格子（包含端点格子）的线段，线段两个端点格子为 同一种颜色，
且中间剩余格子的颜色都为 另一种颜色（线段上不能有任何空格子）。你可以在下图找到好线段的例子：
给你两个整数rMove 和cMove以及一个字符color，表示你正在执行操作的颜色（白或者黑），
如果将格子(rMove, cMove)变成颜色color后，是一个合法操作，那么返回true，如果不是合法操作返回false。
示例 1：输入：board = [[".",".",".","B",".",".",".","."],
[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],
[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],
[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],
[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
输出：true
解释：'.'，'W' 和 'B' 分别用颜色蓝色，白色和黑色表示。格子 (rMove, cMove) 用 'X' 标记。
以选中格子为端点的两个好线段在上图中用红色矩形标注出来了。
示例 2：输入：board = [[".",".",".",".",".",".",".","."],
[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],
[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],
[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],
[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
输出：false
解释：虽然选中格子涂色后，棋盘上产生了好线段，但选中格子是作为中间格子，没有产生以选中格子为端点的好线段。
提示：board.length == board[r].length == 8
0 <= rMove, cMove < 8
board[rMove][cMove] == '.'
color要么是'B' 要么是'W'。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
枚举 |
O(1) |
O(1) |
var dx = []int{1, 1, 0, -1, -1, -1, 0, 1}
var dy = []int{0, 1, 1, 1, 0, -1, -1, -1}
func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
for i := 0; i < 8; i++ {
if judge(board, rMove, cMove, color, dx[i], dy[i]) == true {
return true
}
}
return false
}
func judge(board [][]byte, rMove int, cMove int, color byte, dirX, dirY int) bool {
x, y := rMove+dirX, cMove+dirY
count := 1
for 0 <= x && x < 8 && 0 <= y && y < 8 {
if board[x][y] == '.' {
return false
}
if count == 1 {
if board[x][y] == color {
return false
}
} else {
if board[x][y] == color {
return true
}
}
count++
x = x + dirX
y = y + dirY
}
return false
}
1959.K次调整数组大小浪费的最小总空间(1)
你正在设计一个动态数组。给你一个下标从 0开始的整数数组nums，其中nums[i]是i时刻数组中的元素数目。
除此以外，你还有一个整数 k，表示你可以 调整数组大小的 最多次数（每次都可以调整成 任意大小）。
t时刻数组的大小sizet必须大于等于nums[t]，因为数组需要有足够的空间容纳所有元素。
t时刻 浪费的空间为sizet - nums[t]，总浪费空间为满足0 <= t < nums.length的每一个时刻t浪费的空间之和。
在调整数组大小不超过 k次的前提下，请你返回 最小总浪费空间。
注意：数组最开始时可以为任意大小，且不计入调整大小的操作次数。
示例 1：输入：nums = [10,20], k = 0 输出：10
解释：size = [20,20].
我们可以让数组初始大小为 20 。
总浪费空间为 (20 - 10) + (20 - 20) = 10 。
示例 2：输入：nums = [10,20,30], k = 1 输出：10
解释：size = [20,20,30].
我们可以让数组初始大小为 20 ，然后时刻 2 调整大小为 30 。
总浪费空间为 (20 - 10) + (20 - 20) + (30 - 30) = 10 。
示例 3：输入：nums = [10,20,15,30,20], k = 2 输出：15
解释：size = [10,20,20,30,30].
我们可以让数组初始大小为 10 ，时刻 1 调整大小为 20 ，时刻 3 调整大小为 30 。
总浪费空间为 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15 。
提示：1 <= nums.length <= 200
1 <= nums[i] <= 106
0 <= k <= nums.length - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^3) |
O(n^2) |
func minSpaceWastedKResizing(nums []int, k int) int {
n := len(nums)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
}
for i := 0; i < n; i++ {
maxValue, sum := math.MinInt32, 0
for j := i; j < n; j++ {
if nums[j] > maxValue {
maxValue = nums[j]
}
sum = sum + nums[j]
arr[i][j] = maxValue*(j-i+1) - sum
}
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, k+2)
for j := 0; j < k+2; j++ {
dp[i][j] = math.MaxInt32 / 10
}
}
for i := 0; i < n; i++ {
for j := 1; j <= k+1; j++ {
for l := 0; l <= i; l++ {
if l == 0 {
dp[i][j] = arr[0][i]
} else {
dp[i][j] = min(dp[i][j], dp[l-1][j-1]+arr[l][i])
}
}
}
}
return dp[n-1][k+1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1962.移除石子使总数最小(1)
给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。
另给你一个整数 k ，请你执行下述操作 恰好 k 次：
选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。
注意：你可以对 同一堆 石子多次执行此操作。
返回执行 k 次操作后，剩下石子的 最小 总数。
floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。
示例 1：输入：piles = [5,4,9], k = 2 输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
剩下石子的总数为 12 。
示例 2：输入：piles = [4,3,6,7], k = 3 输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
剩下石子的总数为 12 。
提示：1 <= piles.length <= 105
1 <= piles[i] <= 104
1 <= k <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
堆 |
O(nlog(n)) |
O(n) |
func minStoneSum(piles []int, k int) int {
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
for i := 0; i < len(piles); i++ {
heap.Push(&intHeap, piles[i])
}
for i := 1; i <= k; i++ {
node := heap.Pop(&intHeap).(int)
value := node - node/2
heap.Push(&intHeap, value)
}
res := 0
for i := 0; i < len(piles); i++ {
res = res + intHeap[i]
}
return res
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1963.使字符串平衡的最小交换次数(3)
给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。
只有能满足下述所有条件的字符串才能称为 平衡字符串 ：
字符串是一个空字符串，或者
字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。
返回使 s 变成 平衡字符串 所需要的 最小 交换次数。
示例 1：输入：s = "][][" 输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。
示例 2：输入：s = "]]][[[" 输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][[]" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。
示例 3：输入：s = "[]" 输出：0
解释：这个字符串已经是平衡字符串。
提示：n == s.length
2 <= n <= 106
n 为偶数
s[i] 为'[' 或 ']'
开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
| 03 |
遍历 |
O(n) |
O(n) |
func minSwaps(s string) int {
res := 0
left, right := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '[' {
left++
} else {
right++
}
if right > left {
res++
right--
left++
}
}
return res
}
# 2
func minSwaps(s string) int {
count := 0
minValue := 0
for i := 0; i < len(s); i++ {
if s[i] == '[' {
count++
} else {
count--
minValue = min(minValue, count)
}
}
return (abs(minValue) + 1) / 2
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 3
func minSwaps(s string) int {
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] == '[' {
stack = append(stack, '[')
} else {
if len(stack) > 0 && stack[len(stack)-1] == '[' {
stack = stack[:len(stack)-1]
}
}
}
return len(stack)/2 + len(stack)%2
}
1968.构造元素不等于两相邻元素平均值的数组(2)
给你一个 下标从 0 开始 的数组 nums ，数组由若干 互不相同的 整数组成。
你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都 不等于 其两侧相邻元素的 平均值 。
更公式化的说法是，重新排列的数组应当满足这一属性：
对于范围1 <= i < nums.length - 1 中的每个 i ，(nums[i-1] + nums[i+1]) / 2 不等于 nums[i] 均成立 。
返回满足题意的任一重排结果。
示例 1：输入：nums = [1,2,3,4,5] 输出：[1,2,4,5,3]
解释：i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5
示例 2：输入：nums = [6,2,0,9,7] 输出：[9,7,6,2,0]
解释：i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3
提示：3 <= nums.length <= 105
0 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(n) |
func rearrangeArray(nums []int) []int {
n := len(nums)
res := make([]int, n)
sort.Ints(nums)
index := 0
for i := 0; i < n; i++ {
res[index] = nums[i]
index = index + 2
if index >= n {
index = 1
}
}
return res
}
# 2
func rearrangeArray(nums []int) []int {
n := len(nums)
res := make([]int, 0)
sort.Ints(nums)
m := (n + 1) / 2
for i := 0; i < m; i++ {
res = append(res, nums[i])
if i+m < n {
res = append(res, nums[i+m])
}
}
return res
}
1969.数组元素的最小非零乘积(1)
给你一个正整数p。你有一个下标从 1开始的数组nums，这个数组包含范围[1, 2p - 1]内所有整数的二进制形式（两端都 包含）。
你可以进行以下操作 任意次：
从 nums中选择两个元素x和y 。
选择 x中的一位与 y对应位置的位交换。对应位置指的是两个整数 相同位置的二进制位。
比方说，如果x = 1101且y = 0011，交换右边数起第 2位后，我们得到x = 1111 和y = 0001。
请你算出进行以上操作 任意次以后，nums能得到的 最小非零乘积。将乘积对109 + 7取余 后返回。
注意：答案应为取余 之前的最小值。
示例 1：输入：p = 1 输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。
示例 2：输入：p = 2 输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。
示例 3：输入：p = 3 输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中，我们交换第二个和第五个元素最左边的数位。
- 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
- 第二次操作中，我们交换第三个和第四个元素中间的数位。
- 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。
提示：1 <= p <= 60
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
快速幂 |
O(log(n)) |
O(1) |
var mod = 1000000007
func minNonZeroProduct(p int) int {
a := (1<<p - 1) % mod
b := (1<<p - 2) % mod
c := 1<<(p-1) - 1
return a * mypow(b, c) % mod
}
func mypow(a int, n int) int {
res := 1
for n > 0 {
if n%2 == 1 {
res = res * a % mod
}
a = a * a % mod
n = n / 2
}
return res
}
1971.寻找图中是否存在路径(3)
有一个具有 n个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。
图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。
每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。
给你数组 edges 和整数 n、start和end，如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false 。
示例 1：输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2 输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2
示例 2：输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5 输出：false
解释：不存在由顶点 0 到顶点 5 的路径.
提示: 1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= start, end <= n - 1
不存在双向边
不存在指向顶点自身的边
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n) |
| 03 |
并查集 |
O(nlog(n)) |
O(n) |
var m map[int][]int
var visited map[int]bool
func validPath(n int, edges [][]int, source int, destination int) bool {
m = make(map[int][]int)
visited = make(map[int]bool)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
m[a] = append(m[a], b)
m[b] = append(m[b], a)
}
return dfs(source, destination)
}
func dfs(source int, destination int) bool {
visited[source] = true
if source == destination {
return true
}
for i := 0; i < len(m[source]); i++ {
next := m[source][i]
if visited[next] == false && dfs(next, destination) {
return true
}
}
return false
}
# 2
func validPath(n int, edges [][]int, source int, destination int) bool {
m := make(map[int][]int)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
m[a] = append(m[a], b)
m[b] = append(m[b], a)
}
queue := make([]int, 0)
queue = append(queue, source)
visited := make(map[int]bool)
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
if cur == destination {
return true
}
for i := 0; i < len(m[cur]); i++ {
next := m[cur][i]
if visited[next] == false {
queue = append(queue, next)
visited[next] = true
}
}
}
return false
}
# 3
func validPath(n int, edges [][]int, source int, destination int) bool {
fa = Init(n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
union(a, b)
}
return query(source, destination)
}
var fa []int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func find(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
func union(i, j int) {
fa[find(i)] = find(j)
}
func query(i, j int) bool {
return find(i) == find(j)
}
1975.最大方阵和(1)
给你一个n x n的整数方阵matrix。你可以执行以下操作任意次：
选择matrix中相邻两个元素，并将它们都 乘以-1。
如果两个元素有 公共边，那么它们就是 相邻的。
你的目的是 最大化方阵元素的和。请你在执行以上操作之后，返回方阵的最大和。
示例 1：输入：matrix = [[1,-1],[-1,1]] 输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。
示例2：输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] 输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。
提示：n == matrix.length == matrix[i].length
2 <= n <= 250
-105 <= matrix[i][j] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n^2) |
O(1) |
func maxMatrixSum(matrix [][]int) int64 {
res := int64(0)
minValue := math.MaxInt32
count := 0
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
res = res + int64(abs(matrix[i][j]))
minValue = min(minValue, abs(matrix[i][j]))
if matrix[i][j] <= 0 {
count++
}
}
}
if count%2 == 0 {
return res
}
return res - 2*int64(minValue)
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1976.到达目的地的方案数(4)
你在一个城市里，城市由 n个路口组成，路口编号为0到n - 1，某些路口之间有 双向道路。
输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
给你一个整数n和二维整数数组roads，
其中roads[i] = [ui, vi, timei]表示在路口ui和vi之间有一条需要花费timei时间才能通过的道路。
你想知道花费 最少时间从路口0出发到达路口n - 1的方案数。
请返回花费 最少时间到达目的地的 路径数目。由于答案可能很大，将结果对109 + 7取余后返回。
示例 1：输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出：4
解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为：
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
示例 2：输入：n = 2, roads = [[1,0,10]] 输出：1
解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。
提示：1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 109
ui != vi
任意两个路口之间至多有一条路。
从任意路口出发，你能够到达其他任意路口。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
Dijkstra+动态规划 |
O(n^2) |
O(n^2) |
| 02 |
Floyd+递归 |
O(n^3) |
O(n^2) |
| 03 |
Floyd+动态规划 |
O(n^3) |
O(n^2) |
| 04 |
Dijkstra+堆+动态规划 |
O(nlog(n)) |
O(n^2) |
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
maxValue := int(1e11)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
}
dis := make([]int, n)
for i := 0; i < n; i++ {
dis[i] = maxValue
}
dis[0] = 0
visited := make([]bool, n)
for i := 0; i < n; i++ {
target := -1
for j := 0; j < n; j++ {
if visited[j] == false && (target == -1 || dis[j] < dis[target]) {
target = j
}
}
visited[target] = true
for j := 0; j < n; j++ {
dis[j] = min(dis[j], dis[target]+arr[target][j])
}
}
edge := make([]int, n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if dis[i]+arr[i][j] == dis[j] {
edge[j]++
}
}
}
dp := make([]int, n)
dp[0] = 1
queue := make([]int, 0)
queue = append(queue, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for j := 0; j < n; j++ {
if dis[node]+arr[node][j] == dis[j] {
dp[j] = (dp[j] + dp[node]) % mod
edge[j]--
if edge[j] == 0 {
queue = append(queue, j)
}
}
}
}
return dp[n-1] % mod
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
var mod = 1000000007
var dp []int
func countPaths(n int, roads [][]int) int {
maxValue := int(1e12)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
arr[i][i] = 0
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
}
arr = Floyd(arr)
path := make([][]int, n)
dp = make([]int, n)
for i := 0; i < n; i++ {
path[i] = make([]int, 0)
dp[i] = -1
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
if arr[0][b]-arr[0][a] == c {
path[a] = append(path[a], b)
} else if arr[0][a]-arr[0][b] == c {
path[b] = append(path[b], a)
}
}
return dfs(path, 0)
}
func dfs(path [][]int, index int) int {
if index == len(path)-1 {
return 1
}
if dp[index] != -1 {
return dp[index]
}
dp[index] = 0
for i := 0; i < len(path[index]); i++ {
next := path[index][i]
dp[index] = (dp[index] + dfs(path, next)) % mod
}
return dp[index]
}
func Floyd(arr [][]int) [][]int {
n := len(arr)
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if arr[i][k]+arr[k][j] < arr[i][j] {
arr[i][j] = arr[i][k] + arr[k][j]
}
}
}
}
return arr
}
# 3
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
if n <= 2 {
return 1
}
maxValue := int(1e12)
arr := make([][]int, n)
dp := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
arr[i][i] = 0
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
dp[a][b] = 1
dp[b][a] = 1
}
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
if arr[i][k] == maxValue {
continue
}
for j := 0; j < n; j++ {
if arr[j][k] == maxValue || arr[i][k]+arr[k][j] > arr[i][j] {
continue
}
if arr[i][k]+arr[k][j] < arr[i][j] {
dp[i][j] = (dp[i][k] * dp[k][j]) % mod
arr[i][j] = arr[i][k] + arr[k][j]
} else if arr[i][k]+arr[k][j] == arr[i][j] {
dp[i][j] = (dp[i][j] + dp[i][k]*dp[k][j]) % mod
}
}
}
}
return dp[0][n-1]
}
# 4
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
mathValue := int(1e12)
arr := make([][][2]int, n)
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a] = append(arr[a], [2]int{b, c})
arr[b] = append(arr[b], [2]int{a, c})
}
dp := make([]int, n)
dis := make([]int, n)
for i := 0; i < n; i++ {
dis[i] = mathValue
}
dis[0] = 0
dp[0] = 1
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [2]int{0, 0})
for intHeap.Len() > 0 {
node := heap.Pop(&intHeap).([2]int)
a, d := node[0], node[1]
if dis[a] < d {
continue
}
for i := 0; i < len(arr[a]); i++ {
b, c := arr[a][i][0], arr[a][i][1]
if dis[a]+c < dis[b] {
dis[b] = dis[a] + c
dp[b] = dp[a]
heap.Push(&intHeap, [2]int{b, dis[b]})
} else if dis[a]+c == dis[b] {
dp[b] = (dp[b] + dp[a]) % mod
}
}
}
return dp[n-1] % mod
}
type IntHeap [][2]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][1] < h[j][1]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1980.找出不同的二进制字符串(2)
给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。
请你找出并返回一个长度为n且没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。
示例 1：输入：nums = ["01","10"] 输出："11"
解释："11" 没有出现在 nums 中。"00" 也是正确答案。
示例 2：输入：nums = ["00","01"] 输出："11"
解释："11" 没有出现在 nums 中。"10" 也是正确答案。
示例 3：输入：nums = ["111","011","001"] 输出："101"
解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。
提示：n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] 为 '0' 或 '1'
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(2^n) |
O(n) |
| 02 |
贪心 |
O(n) |
O(1) |
func findDifferentBinaryString(nums []string) string {
n := len(nums)
m := make(map[string]bool)
for i := 0; i < len(nums); i++{
m[strings.Repeat("0",16-n)+nums[i]] = true
}
for i := 0; i < (1 << n); i++{
if m[fmt.Sprintf("%016b", i)] ==false{
res := fmt.Sprintf("%016b", i)
return res[16-n:]
}
}
return ""
}
# 2
func findDifferentBinaryString(nums []string) string {
n := len(nums)
res := ""
for i := 0; i < n; i++ {
if nums[i][i] == '0' {
res = res + "1"
} else {
res = res + "0"
}
}
return res
}
1981.最小化目标值与所选元素的差(4)
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数，你的目标是最小化所有选中元素之和与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。
示例 1：输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13 输出：0
解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7
所选元素的和是 13 ，等于目标值，所以绝对差是 0 。
示例 2：输入：mat = [[1],[2],[3]], target = 100 输出：94
解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3
所选元素的和是 6 ，绝对差是 94 。
示例 3：输入：mat = [[1,2,9,8,7]], target = 6 输出：1
解释：最优的选择方案是选出第一行的 7 。
绝对差是 1 。
提示：m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^3) |
O(n^2) |
| 02 |
动态规划 |
O(n^3) |
O(n) |
| 03 |
动态规划 |
O(n^3) |
O(n) |
| 04 |
动态规划 |
O(n^3) |
O(n^2) |
func minimizeTheDifference(mat [][]int, target int) int {
n := len(mat)
m := len(mat[0])
maxSum := 0
dp := make([][]bool, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]bool, 5000)
}
dp[0][0] = true
for i := 0; i < n; i++ {
maxValue := 0
for j := 0; j < m; j++ {
maxValue = max(maxValue, mat[i][j])
for k := mat[i][j]; k <= maxSum+mat[i][j]; k++ {
if dp[i][k-mat[i][j]] == true {
dp[i+1][k] = true
}
}
}
maxSum = maxSum + maxValue
}
res := math.MaxInt32
for j := 0; j <= maxSum; j++ {
if dp[n][j] == true {
res = min(res, abs(j-target))
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func minimizeTheDifference(mat [][]int, target int) int {
n := len(mat)
m := len(mat[0])
maxSum := 0
dp := []int{1}
for i := 0; i < n; i++ {
maxValue := 0
for j := 0; j < m; j++ {
maxValue = max(maxValue, mat[i][j])
}
temp := make([]int, maxSum+maxValue+1)
for j := 0; j < m; j++ {
for k := mat[i][j]; k <= maxSum+mat[i][j]; k++ {
temp[k] = temp[k] | dp[k-mat[i][j]]
}
}
dp = temp
maxSum = maxSum + maxValue
}
res := math.MaxInt32
for j := 0; j <= maxSum; j++ {
if dp[j] > 0 {
res = min(res, abs(j-target))
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 3
func minimizeTheDifference(mat [][]int, target int) int {
n := len(mat)
m := len(mat[0])
dp := make([]bool, target)
dp[0] = true
maxValue := math.MaxInt32
for i := 0; i < n; i++ {
temp := make([]bool, target)
tempMaxValue := math.MaxInt32
for j := 0; j < m; j++ {
for k := 0; k < target; k++ {
if dp[k] == true {
if k+mat[i][j] >= target {
tempMaxValue = min(tempMaxValue, k+mat[i][j])
} else {
temp[k+mat[i][j]] = true
}
}
}
if maxValue != math.MaxInt32 {
tempMaxValue = min(tempMaxValue, maxValue+mat[i][j])
}
}
dp = temp
maxValue = tempMaxValue
}
res := abs(maxValue - target)
for i := target - 1; i >= 0; i-- {
if dp[i] == true {
res = min(res, target-i)
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 4
func minimizeTheDifference(mat [][]int, target int) int {
n := len(mat)
m := len(mat[0])
maxValue := 5000
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, maxValue)
}
for j := 0; j < m; j++ {
dp[0][mat[0][j]] = 1
}
for i := 1; i < n; i++ {
for j := 0; j < m; j++ {
for k := mat[i][j]; k < maxValue; k++ {
dp[i][k] = dp[i][k] | dp[i-1][k-mat[i][j]]
}
}
}
res := math.MaxInt32
for j := 0; j < maxValue; j++ {
if dp[n-1][j] == 1 {
res = min(res, abs(j-target))
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
1985.找出数组中的第K大整数(1)
给你一个字符串数组 nums 和一个整数 k 。nums 中的每个字符串都表示一个不含前导零的整数。
返回 nums 中表示第 k 大整数的字符串。
注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 ["1","2","2"]，
那么 "2" 是最大的整数，"2" 是第二大的整数，"1" 是第三大的整数。
示例 1：输入：nums = ["3","6","7","10"], k = 4 输出："3"
解释：nums 中的数字按非递减顺序排列为 ["3","6","7","10"]
其中第 4 大整数是 "3"
示例 2：输入：nums = ["2","21","12","1"], k = 3 输出："2"
解释：nums 中的数字按非递减顺序排列为 ["1","2","12","21"]
其中第 3 大整数是 "2"
示例 3：输入：nums = ["0","0"], k = 2 输出："0"
解释：nums 中的数字按非递减顺序排列为 ["0","0"]
其中第 2 大整数是 "0"
提示：1 <= k <= nums.length <= 104
1 <= nums[i].length <= 100
nums[i] 仅由数字组成
nums[i] 不含任何前导零
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(1) |
func kthLargestNumber(nums []string, k int) string {
sort.Slice(nums, func(i, j int) bool {
if len(nums[i]) == len(nums[j]) {
return nums[i] > nums[j]
}
return len(nums[i]) > len(nums[j])
})
return nums[k-1]
}
1986.完成任务的最少工作时间段(5)
你被安排了 n个任务。任务需要花费的时间用长度为 n的整数数组tasks表示，第 i个任务需要花费tasks[i]小时完成。
一个 工作时间段中，你可以 至多连续工作sessionTime个小时，然后休息一会儿。
你需要按照如下条件完成给定任务：
如果你在某一个时间段开始一个任务，你需要在 同一个时间段完成它。
完成一个任务后，你可以 立马开始一个新的任务。
你可以按 任意顺序完成任务。
给你tasks 和sessionTime，请你按照上述要求，返回完成所有任务所需要的最少数目的工作时间段。
测试数据保证sessionTime 大于等于tasks[i]中的最大值。
示例 1：输入：tasks = [1,2,3], sessionTime = 3 输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。
示例 2：输入：tasks = [3,1,3,1,1], sessionTime = 8 输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。
示例 3：输入：tasks = [1,2,3,4,5], sessionTime = 15 输出：1
解释：你可以在一个工作时间段以内完成所有任务。
提示：n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划+状态压缩 |
O(3^n) |
O(2^n) |
| 02 |
动态规划+状态压缩 |
O(3^n) |
O(2^n) |
| 03 |
动态规划+状态压缩 |
O(3^n) |
O(2^n) |
| 04 |
回溯 |
O(2^n) |
O(n) |
| 05 |
二分查找+回溯 |
O(nlog(n)) |
O(n) |
func minSessions(tasks []int, sessionTime int) int {
n := len(tasks)
total := 1 << n
dp := make([]int, total)
for i := 0; i < total; i++ {
dp[i] = n
}
dp[0] = 0
sum := make([]int, total)
for i := 0; i < n; i++ {
count := 1 << i
for j := 0; j < count; j++ {
sum[count|j] = sum[j] + tasks[i]
}
}
for i := 0; i < total; i++ {
for j := i; j > 0; j = (j - 1) & i {
if sum[j] <= sessionTime {
dp[i] = min(dp[i], dp[i^j]+1)
}
}
}
return dp[total-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minSessions(tasks []int, sessionTime int) int {
n := len(tasks)
total := 1 << n
dp := make([]int, total)
for i := 0; i < total; i++ {
dp[i] = n
}
dp[0] = 0
valid := make([]bool, total)
for i := 1; i < total; i++ {
sum := 0
for j := 0; j < n; j++ {
if i&(1<<j) > 0 {
sum = sum + tasks[j]
}
}
if sum <= sessionTime {
valid[i] = true
}
}
for i := 1; i < total; i++ {
for j := i; j > 0; j = (j - 1) & i {
if valid[j] == true {
dp[i] = min(dp[i], dp[i^j]+1)
}
}
}
return dp[total-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func minSessions(tasks []int, sessionTime int) int {
n := len(tasks)
total := 1 << n
dp := make([]int, total)
for i := 0; i < total; i++ {
dp[i] = n
}
dp[0] = 0
sum := make([]int, total)
for i := 0; i < n; i++ {
count := 1 << i
for j := 0; j < count; j++ {
sum[count|j] = sum[j] + tasks[i]
}
}
for i := 0; i < total; i++ {
for j := 1; j <= i; j++ {
if i|j == i && sum[j] <= sessionTime {
dp[i] = min(dp[i], dp[i^j]+1)
}
}
}
return dp[total-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
var res int
func minSessions(tasks []int, sessionTime int) int {
res = len(tasks)
dfs(tasks, sessionTime, 0, 0, make([]int, len(tasks)))
return res
}
func dfs(tasks []int, sessionTime int, index, count int, arr []int) {
if count >= res {
return
}
if index == len(tasks) {
res = count
return
}
flag := false
for i := 0; i < len(tasks); i++ {
if arr[i] == 0 && flag == true {
break
}
if arr[i]+tasks[index] > sessionTime {
continue
}
if arr[i] == 0 {
flag = true
}
arr[i] = arr[i] + tasks[index]
if flag == true {
dfs(tasks, sessionTime, index+1, count+1, arr)
} else {
dfs(tasks, sessionTime, index+1, count, arr)
}
arr[i] = arr[i] - tasks[index]
}
}
# 5
func minSessions(tasks []int, sessionTime int) int {
sort.Slice(tasks, func(i, j int) bool {
return tasks[i] > tasks[j]
})
left, right := 1, len(tasks)
for left < right {
mid := left + (right-left)/2
arr := make([]int, mid)
if dfs(tasks, sessionTime, 0, mid, arr) == true {
right = mid
} else {
left = mid + 1
}
}
return left
}
func dfs(tasks []int, sessionTime int, index, count int, arr []int) bool {
if index == len(tasks) {
return true
}
flag := false
for i := 0; i < count; i++ {
if arr[i] == 0 && flag == true {
break
}
if arr[i]+tasks[index] > sessionTime {
continue
}
if arr[i] == 0 {
flag = true
}
arr[i] = arr[i] + tasks[index]
if dfs(tasks, sessionTime, index+1, count, arr) == true {
return true
}
arr[i] = arr[i] - tasks[index]
}
return false
}
1992.找到所有的农场组(2)
给你一个下标从 0开始，大小为m x n的二进制矩阵land，其中 0表示一单位的森林土地，1表示一单位的农场土地。
为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅包含农场土地。
且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 不会与另一个农场组的任何一块土地在四个方向上相邻。
land可以用坐标系统表示，其中 land左上角坐标为(0, 0)，右下角坐标为(m-1, n-1)。
请你找到所有 农场组最左上角和最右下角的坐标。
一个左上角坐标为(r1, c1)且右下角坐标为(r2, c2)的 农场组 用长度为 4 的数组[r1, c1, r2, c2]表示。
请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land中的一个 农场组。
如果没有任何农场组，请你返回一个空数组。可以以 任意顺序返回所有农场组。
示例 1：输入：land = [[1,0,0],[0,1,1],[0,1,1]] 输出：[[0,0,0,0],[1,1,2,2]]
解释：第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。
第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。
示例 2：输入：land = [[1,1],[1,1]] 输出：[[0,0,1,1]]
解释：第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。
示例 3：输入：land = [[0]] 输出：[]
解释：没有任何农场组。
提示：m == land.length
n == land[i].length
1 <= m, n <= 300
land只包含0和1。
农场组都是 矩形的形状。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(n^2) |
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var res [][]int
var a, b, c, d int
func findFarmland(land [][]int) [][]int {
res = make([][]int, 0)
n, m := len(land), len(land[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if land[i][j] == 1 {
a, b, c, d = i, j, i, j
land[i][j] = 2
dfs(land, i, j)
res = append(res, []int{a, b, c, d})
}
}
}
return res
}
func dfs(land [][]int, i, j int) {
a, b = min(a, i), min(b, j)
c, d = max(c, i), max(d, j)
for k := 0; k < 4; k++ {
x, y := i+dx[k], j+dy[k]
if 0 <= x && x < len(land) && 0 <= y && y < len(land[0]) && land[x][y] == 1 {
land[x][y] = 2
dfs(land, x, y)
}
}
}
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 findFarmland(land [][]int) [][]int {
res := make([][]int, 0)
n, m := len(land), len(land[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if land[i][j] == 0 {
continue
}
if (0 < i && land[i-1][j] == 1) ||
(0 < j && land[i][j-1] == 1) {
continue
}
var a, b, c, d int
a, b = i, j
for c = i; c+1 < n && land[c+1][j] == 1; c++ {
}
for d = j; d+1 < m && land[i][d+1] == 1; d++ {
}
res = append(res, []int{a, b, c, d})
}
}
return res
}
1993.树上的操作(2)
给你一棵n个节点的树，编号从0到n - 1，以父节点数组parent的形式给出，其中parent[i]是第i个节点的父节点。
树的根节点为 0号节点，所以parent[0] = -1，因为它没有父节点。
你想要设计一个数据结构实现树里面对节点的加锁，解锁和升级操作。
数据结构需要支持如下函数：
Lock：指定用户给指定节点 上锁，上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下，才能进行上锁操作。
Unlock：指定用户给指定节点 解锁，只有当指定节点当前正被指定用户锁住时，才能执行该解锁操作。
Upgrade：指定用户给指定节点上锁，并且将该节点的所有子孙节点解锁。只有如下 3 个条件 全部 满足时才能执行升级操作：
指定节点当前状态为未上锁。
指定节点至少有一个上锁状态的子孙节点（可以是 任意用户上锁的）。
指定节点没有任何上锁的祖先节点。
请你实现LockingTree类：
LockingTree(int[] parent)用父节点数组初始化数据结构。
lock(int num, int user) 如果id 为user的用户可以给节点num上锁，那么返回true，否则返回false。
如果可以执行此操作，节点num会被 id 为 user的用户 上锁。
unlock(int num, int user)如果 id 为 user的用户可以给节点 num解锁，那么返回true，否则返回 false。
如果可以执行此操作，节点 num变为 未上锁状态。
upgrade(int num, int user)如果 id 为 user的用户可以给节点 num升级，那么返回true，否则返回 false。
如果可以执行此操作，节点 num会被升级 。
示例 1：输入：["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"]
[[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]]
输出：[null, true, false, true, true, true, false]
解释：LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);
lockingTree.lock(2, 2); // 返回 true ，因为节点 2 未上锁。
// 节点 2 被用户 2 上锁。
lockingTree.unlock(2, 3); // 返回 false ，因为用户 3 无法解锁被用户 2 上锁的节点。
lockingTree.unlock(2, 2); // 返回 true ，因为节点 2 之前被用户 2 上锁。
// 节点 2 现在变为未上锁状态。
lockingTree.lock(4, 5); // 返回 true ，因为节点 4 未上锁。
// 节点 4 被用户 5 上锁。
lockingTree.upgrade(0, 1); // 返回 true ，因为节点 0 未上锁且至少有一个被上锁的子孙节点（节点 4）。
// 节点 0 被用户 1 上锁，节点 4 变为未上锁。
lockingTree.lock(0, 1); // 返回 false ，因为节点 0 已经被上锁了。
提示：n == parent.length
2 <= n <= 2000
对于i != 0，满足0 <= parent[i] <= n - 1
parent[0] == -1
0 <= num <= n - 1
1 <= user <= 104
parent表示一棵合法的树。
lock，unlock和upgrade的调用总共不超过2000次。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n) |
O(n) |
| 02 |
深度优先搜索 |
O(n) |
O(n) |
type LockingTree struct {
m map[int]int
parent map[int]int
next map[int][]int
}
func Constructor(parent []int) LockingTree {
temp := make(map[int]int)
next := make(map[int][]int)
for i := 0; i < len(parent); i++ {
temp[i] = parent[i]
next[parent[i]] = append(next[parent[i]], i)
}
return LockingTree{m: make(map[int]int), parent: temp, next: next}
}
func (this *LockingTree) Lock(num int, user int) bool {
if _, ok := this.m[num]; ok {
return false
}
this.m[num] = user
return true
}
func (this *LockingTree) Unlock(num int, user int) bool {
if v, ok := this.m[num]; ok == false || v != user {
return false
}
delete(this.m, num)
return true
}
func (this *LockingTree) Upgrade(num int, user int) bool {
if _, ok := this.m[num]; ok == true {
return false
}
queue := make([]int, 0)
queue = append(queue, this.next[num]...)
flag := false
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node < len(this.parent) {
queue = append(queue, this.next[node]...)
if _, ok := this.m[node]; ok {
flag = true
break
}
}
}
if flag == false {
return false
}
flag = false
p := this.parent[num]
for p != -1 {
if _, ok := this.m[p]; ok {
flag = true
}
p = this.parent[p]
}
if flag == true {
return false
}
this.m[num] = user
queue = make([]int, 0)
queue = append(queue, this.next[num]...)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node < len(this.parent) {
queue = append(queue, this.next[node]...)
delete(this.m, node)
}
}
return true
}
# 2
type LockingTree struct {
m map[int]int
parent map[int]int
next map[int][]int
}
func Constructor(parent []int) LockingTree {
temp := make(map[int]int)
next := make(map[int][]int)
for i := 0; i < len(parent); i++ {
temp[i] = parent[i]
next[parent[i]] = append(next[parent[i]], i)
}
return LockingTree{m: make(map[int]int), parent: temp, next: next}
}
func (this *LockingTree) Lock(num int, user int) bool {
if _, ok := this.m[num]; ok {
return false
}
this.m[num] = user
return true
}
func (this *LockingTree) Unlock(num int, user int) bool {
if v, ok := this.m[num]; ok == false || v != user {
return false
}
delete(this.m, num)
return true
}
func (this *LockingTree) Upgrade(num int, user int) bool {
v := num
for {
if v >= 0 {
if _, ok := this.m[v]; ok {
return false
}
v = this.parent[v]
} else {
break
}
}
if this.hasLock(num) == false {
return false
}
this.m[num] = user
this.dfsUnLock(num)
return true
}
func (this *LockingTree) hasLock(num int) bool {
for i := 0; i < len(this.next[num]); i++ {
v := this.next[num][i]
if _, ok := this.m[v]; ok {
return true
}
if this.hasLock(v) {
return true
}
}
return false
}
func (this *LockingTree) dfsUnLock(num int) {
for i := 0; i < len(this.next[num]); i++ {
v := this.next[num][i]
delete(this.m, v)
this.dfsUnLock(v)
}
}
1996.游戏中弱角色的数量(2)
你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。
给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。
更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
返回 弱角色 的数量。
示例 1：输入：properties = [[5,5],[6,3],[3,6]] 输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。
示例 2：输入：properties = [[2,2],[3,3]] 输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
示例 3：输入：properties = [[1,5],[10,4],[4,3]] 输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
提示：2 <= properties.length <= 105
properties[i].length == 2
1 <= attacki, defensei <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+遍历 |
O(nlog(n)) |
O(1) |
| 02 |
排序+栈 |
O(nlog(n)) |
O(n) |
func numberOfWeakCharacters(properties [][]int) int {
sort.Slice(properties, func(i, j int) bool {
if properties[i][0] == properties[j][0] {
return properties[i][1] < properties[j][1]
}
return properties[i][0] > properties[j][0]
})
res := 0
maxValue := 0
for i := 0; i < len(properties); i++ {
if properties[i][1] < maxValue {
res++
} else {
maxValue = properties[i][1]
}
}
return res
}
# 2
func numberOfWeakCharacters(properties [][]int) int {
sort.Slice(properties, func(i, j int) bool {
if properties[i][0] == properties[j][0] {
return properties[i][1] < properties[j][1]
}
return properties[i][0] > properties[j][0]
})
res := 0
stack := make([]int, 0)
for i := 0; i < len(properties); i++ {
for len(stack) > 0 && properties[stack[len(stack)-1]][1] <= properties[i][1] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
res++
}
stack = append(stack, i)
}
return res
}
1997.访问完所有房间的第一天(3)
你需要访问n 个房间，房间从 0 到 n - 1 编号。
同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
最开始的第 0 天，你访问0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。
在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：
假设某一天，你访问i 号房间。
如果算上本次访问，访问i 号房间的次数为 奇数 ，
那么 第二天 需要访问nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
如果算上本次访问，访问i 号房间的次数为 偶数 ，那么 第二天 需要访问(i + 1) mod n 号房间。
请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。
示例 1：输入：nextVisit = [0,0] 输出：2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
下一天你需要访问房间的编号是 nextVisit[0] = 0
- 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
- 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。
示例 2：输入：nextVisit = [0,0,2] 输出：6
解释：你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
第 6 天是你访问完所有房间的第一天。
示例 3：输入：nextVisit = [0,1,2,0] 输出：6
解释：你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
第 6 天是你访问完所有房间的第一天。
提示：n == nextVisit.length
2 <= n <= 105
0 <= nextVisit[i] <= i
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
动态规划 |
O(n) |
O(n) |
var mod = 1000000007
func firstDayBeenInAllRooms(nextVisit []int) int {
n := len(nextVisit)
dp := make([]int, n)
dp[0] = 1
for i := 1; i < n; i++ {
a := dp[i-1] + 1
b := dp[i-1] - dp[nextVisit[i-1]] + 1
dp[i] = (a + b + mod) % mod
}
return (dp[n-1] - 1 + mod) % mod
}
# 2
var mod = 1000000007
func firstDayBeenInAllRooms(nextVisit []int) int {
n := len(nextVisit)
dp := make([]int, n)
dp[0] = 1
for i := 0; i < n-1; i++ {
a := (dp[i] - dp[nextVisit[i]] + mod) % mod
dp[i+1] = (dp[i] + a + 2) % mod
}
return (dp[n-1] - 1 + mod) % mod
}
# 3
var mod = 1000000007
func firstDayBeenInAllRooms(nextVisit []int) int {
n := len(nextVisit)
dp := make([]int, n)
dp[0] = 0
for i := 1; i < n; i++ {
dp[i] = (2*dp[i-1] - dp[nextVisit[i-1]] + 2 + mod) % mod
}
return dp[n-1]
}
1901-2000-Hard
1912.设计电影租借系统
题目
你有一个电影租借公司和 n个电影商店。
你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。
同时系统还能生成一份当前被借出电影的报告。
所有电影用二维整数数组entries表示，其中entries[i] = [shopi, moviei, pricei]
表示商店 shopi有一份电影moviei的拷贝，租借价格为pricei。
每个商店有至多一份编号为moviei的电影拷贝。
系统需要支持以下操作：
Search：找到拥有指定电影且 未借出的商店中最便宜的 5 个。
商店需要按照价格升序排序，如果价格相同，则shopi较小的商店排在前面。
如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出。
Drop：在指定商店返还 之前已借出的指定电影。
Report：返回 最便宜的 5 部已借出电影（可能有重复的电影 ID），将结果用二维列表res返回，
其中 res[j] = [shopj, moviej]表示第j便宜的已借出电影是从商店shopj借出的电影moviej。
res中的电影需要按 价格升序排序；如果价格相同，则shopj 较小的排在前面；
如果仍然相同，则 moviej 较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。
如果当前没有借出电影，则返回一个空的列表。
请你实现MovieRentingSystem类：
MovieRentingSystem(int n, int[][] entries)将MovieRentingSystem对象用n个商店和entries表示的电影列表初始化。
List<Integer> search(int movie) 如上所述，返回 未借出指定 movie的商店列表。
void rent(int shop, int movie)从指定商店 shop借出指定电影movie。
void drop(int shop, int movie)在指定商店 shop返还之前借出的电影movie。
List<List<Integer>> report() 如上所述，返回最便宜的 已借出电影列表。
注意：测试数据保证rent操作中指定商店拥有 未借出 的指定电影，且drop操作指定的商店 之前已借出指定电影。
示例 1：输入：["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1],
[0, 1], [1, 2], [], [1, 2], [2]]
输出：[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]
解释：MovieRentingSystem movieRentingSystem =
new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1); // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。
商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report(); // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2); // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。
提示：1 <= n <= 3 * 105
1 <= entries.length <= 105
0 <= shopi < n
1 <= moviei, pricei <= 104
每个商店 至多有一份电影moviei的拷贝。
search，rent，drop 和report的调用总共不超过105次。
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n) |
O(n) |
1928.规定时间内到达终点的最小花费(3)
一个国家有 n个城市，城市编号为0到n - 1，题目保证 所有城市都由双向道路 连接在一起。
道路由二维整数数组edges表示，其中edges[i] = [xi, yi, timei]表示城市xi 和yi之间有一条双向道路，
耗费时间为timei分钟。
两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
每次经过一个城市时，你需要付通行费。通行费用一个长度为 n且下标从 0开始的整数数组passingFees表示，
其中passingFees[j]是你经过城市 j需要支付的费用。
一开始，你在城市0，你想要在 maxTime分钟以内（包含 maxTime分钟）到达城市n - 1。
旅行的 费用 为你经过的所有城市 通行费之和（包括起点和终点城市的通行费）。
给你maxTime，edges和passingFees，请你返回完成旅行的最小费用，
如果无法在maxTime分钟以内完成旅行，请你返回-1。
示例 1：输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],
passingFees = [5,1,2,20,20,3] 输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。
示例 2：输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],
passingFees = [5,1,2,20,20,3] 输出：48
解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。
你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。
示例 3：输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],
passingFees = [5,1,2,20,20,3] 输出：-1
解释：无法在 25 分钟以内从城市 0 到达城市 5 。
提示：1 <= maxTime <= 1000
n == passingFees.length
2 <= n <= 1000
n - 1 <= edges.length <= 1000
0 <= xi, yi <= n - 1
1 <= timei <= 1000
1 <= passingFees[j] <= 1000
图中两个节点之间可能有多条路径。
图中不含有自环。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划-二维 |
O(n^2) |
O(n^2) |
| 02 |
动态规划-二维 |
O(n^3) |
O(n^2) |
| 03 |
堆 |
O(nlog(n)) |
O(n) |
func minCost(maxTime int, edges [][]int, passingFees []int) int {
maxValue := math.MaxInt32 / 10
n := len(passingFees)
dp := make([][]int, maxTime+1)
for i := 0; i <= maxTime; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
dp[i][j] = maxValue
}
}
dp[0][0] = passingFees[0]
for i := 1; i <= maxTime; i++ {
for j := 0; j < len(edges); j++ {
a, b, c := edges[j][0], edges[j][1], edges[j][2]
if c <= i {
dp[i][a] = min(dp[i][a], dp[i-c][b]+passingFees[a])
dp[i][b] = min(dp[i][b], dp[i-c][a]+passingFees[b])
}
}
}
res := maxValue
for i := 1; i <= maxTime; i++ {
res = min(res, dp[i][n-1])
}
if res == maxValue {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minCost(maxTime int, edges [][]int, passingFees []int) int {
maxValue := math.MaxInt32 / 10
n := len(passingFees)
dp := make([][]int, maxTime+1)
for i := 0; i <= maxTime; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
dp[i][j] = maxValue
}
}
arr := make([][][2]int, n)
for i := 0; i < len(edges); i++ {
a, b, c := edges[i][0], edges[i][1], edges[i][2]
arr[a] = append(arr[a], [2]int{b, c})
arr[b] = append(arr[b], [2]int{a, c})
}
dp[0][0] = passingFees[0]
for i := 1; i <= maxTime; i++ {
for j := 0; j < n; j++ {
for k := 0; k < len(arr[j]); k++ {
a := j
b, c := arr[j][k][0], arr[j][k][1]
if c <= i {
dp[i][a] = min(dp[i][a], dp[i-c][b]+passingFees[a])
dp[i][b] = min(dp[i][b], dp[i-c][a]+passingFees[b])
}
}
}
}
res := maxValue
for i := 1; i <= maxTime; i++ {
res = min(res, dp[i][n-1])
}
if res == maxValue {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func minCost(maxTime int, edges [][]int, passingFees []int) int {
n := len(passingFees)
arr := make([][][2]int, n)
for i := 0; i < len(edges); i++ {
a, b, c := edges[i][0], edges[i][1], edges[i][2]
arr[a] = append(arr[a], [2]int{b, c})
arr[b] = append(arr[b], [2]int{a, c})
}
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [3]int{passingFees[0], maxTime, 0})
m := make(map[int]int)
m[0] = maxTime
for intHeap.Len() > 0 {
node := heap.Pop(&intHeap).([3]int)
value, leftTime, index := node[0], node[1], node[2]
if index == n-1 {
return value
}
for i := 0; i < len(arr[index]); i++ {
a, b := arr[index][i][0], arr[index][i][1]
if b > leftTime {
continue
}
if v, ok := m[a]; ok == false || leftTime-b > v {
m[a] = leftTime - b
heap.Push(&intHeap, [3]int{value + passingFees[a], leftTime - b, a})
}
}
}
return -1
}
type IntHeap [][3]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][0] < h[j][0]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.([3]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1931.用三种不同颜色为网格涂色
题目
给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。
请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。
涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。
因为答案可能非常大， 返回 对 109 + 7 取余 的结果。
示例 1：输入：m = 1, n = 1 输出：3
解释：如上图所示，存在三种可能的涂色方案。
示例 2：输入：m = 1, n = 2 输出：6
解释：如上图所示，存在六种可能的涂色方案。
示例 3：输入：m = 5, n = 5 输出：580986
提示：1 <= m <= 5
1 <= n <= 1000
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n) |
O(n) |
1944.队列中可以看到的人数(2)
有n个人排成一个队列，从左到右编号为0到n - 1。
给你以一个整数数组heights，每个整数 互不相同，heights[i]表示第i个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮。
更正式的，第i个人能看到第j个人的条件是i < j且
min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])。
请你返回一个长度为 n的数组answer，其中answer[i]是第i个人在他右侧队列中能看到的人数。
示例 1：输入：heights = [10,6,8,5,11,9] 输出：[3,1,2,1,1,0]
解释：第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。
示例 2：输入：heights = [5,1,2,3,10] 输出：[4,1,1,1,0]
提示：n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
heights中所有数 互不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n) |
O(n) |
| 02 |
单调栈 |
O(n) |
O(n) |
func canSeePersonsCount(heights []int) []int {
n := len(heights)
res := make([]int, n)
stack := make([]int, 0)
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 {
res[i]++
if heights[i] > heights[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
} else {
break
}
}
stack = append(stack, i)
}
return res
}
# 2
func canSeePersonsCount(heights []int) []int {
n := len(heights)
res := make([]int, n)
stack := make([]int, 0)
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 && heights[i] > heights[stack[len(stack)-1]] {
res[i]++
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
res[i]++
}
stack = append(stack, i)
}
return res
}
1955.统计特殊子序列的数目(2)
特殊序列 是由正整数个 0，紧接着正整数个 1，最后 正整数个 2组成的序列。
比方说，[0,1,2] 和[0,0,1,1,1,2]是特殊序列。
相反，[2,1,0]，[1]和[0,1,2,0]就不是特殊序列。
给你一个数组nums（仅包含整数0，1和2），请你返回 不同特殊子序列的数目。
由于答案可能很大，请你将它对109 + 7 取余 后返回。
一个数组的 子序列是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。
如果两个子序列的 下标集合不同，那么这两个子序列是 不同的。
示例 1：输入：nums = [0,1,2,2] 输出：3
解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。
示例 2：输入：nums = [2,2,0,0] 输出：0
解释：数组 [2,2,0,0] 中没有特殊子序列。
示例 3：输入：nums = [0,1,2,0,1,2] 输出：7
解释：特殊子序列包括：
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
提示：1 <= nums.length <= 105
0 <= nums[i] <= 2
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n) |
O(1) |
var mod = 1000000007
func countSpecialSubsequences(nums []int) int {
n := len(nums)
a, b, c := 0, 0, 0
for i := 0; i < n; i++ {
if nums[i] == 0 {
a = (a*2 + 1) % mod
} else if nums[i] == 1 {
b = (b*2 + a) % mod
} else if nums[i] == 2 {
c = (c*2 + b) % mod
}
}
return c
}
# 2
var mod = 1000000007
func countSpecialSubsequences(nums []int) int {
n := len(nums)
dp := make([]int, 3)
for i := 0; i < n; i++ {
if nums[i] == 0 {
dp[0] = (dp[0]*2 + 1) % mod
} else if nums[i] == 1 {
dp[1] = (dp[1]*2 + dp[0]) % mod
} else if nums[i] == 2 {
dp[2] = (dp[2]*2 + dp[1]) % mod
}
}
return dp[2]
}
1964.找出到每个位置为止最长的有效障碍赛跑路线(2)
你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，
其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，
请你找出obstacles 能构成的最长障碍路线的长度：
你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
在这条路线中，必须包含第 i 个障碍。
你必须按障碍在obstacles中的 出现顺序 布置这些障碍。
除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。
示例 1：输入：obstacles = [1,2,3,2] 输出：[1,2,3,3]
解释：每个位置的最长有效障碍路线是：
- i = 0: [1], [1] 长度为 1
- i = 1: [1,2], [1,2] 长度为 2
- i = 2: [1,2,3], [1,2,3] 长度为 3
- i = 3: [1,2,3,2], [1,2,2] 长度为 3
示例 2：输入：obstacles = [2,2,1] 输出：[1,2,1]
解释：每个位置的最长有效障碍路线是：
- i = 0: [2], [2] 长度为 1
- i = 1: [2,2], [2,2] 长度为 2
- i = 2: [2,2,1], [1] 长度为 1
示例 3：输入：obstacles = [3,1,5,6,4,2] 输出：[1,1,2,3,2,2]
解释：每个位置的最长有效障碍路线是：
- i = 0: [3], [3] 长度为 1
- i = 1: [3,1], [1] 长度为 1
- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2
提示：n == obstacles.length
1 <= n <= 105
1 <= obstacles[i] <= 107
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划+二分查找 |
O(nlog(n)) |
O(n) |
| 02 |
动态规划+二分查找 |
O(nlog(n)) |
O(n) |
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
n := len(obstacles)
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = 1
}
dp := make([]int, 0)
dp = append(dp, obstacles[0])
for i := 1; i < n; i++ {
if dp[len(dp)-1] <= obstacles[i] {
dp = append(dp, obstacles[i])
res[i] = len(dp)
} else {
left, right := 0, len(dp)-1
index := 0
for left <= right {
mid := left + (right-left)/2
if dp[mid] <= obstacles[i] {
left = mid + 1
} else {
index = mid
right = mid - 1
}
}
dp[index] = obstacles[i]
res[i] = index + 1
}
}
return res
}
# 2
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
n := len(obstacles)
res := make([]int, n)
dp := make([]int, 0)
for i := 0; i < n; i++ {
index := sort.SearchInts(dp, obstacles[i]+1)
if index < len(dp) {
dp[index] = obstacles[i]
} else {
dp = append(dp, obstacles[i])
}
res[i] = index + 1
}
return res
}
1970.你能穿过矩阵的最后一天
题目
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划+二分查找 |
O(nlog(n)) |
O(n) |
```
## 1987.不同的好子序列数目
### 题目
### 解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
| :----- | :------------------ | :----------- | :----------- |
| 01 | 动态规划+二分查找 | O(nlog(n)) | O(n) |
```go