1401-1500-Easy¶
1403.非递增顺序的最小子序列(2)¶
题目
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，
也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例 1：输入：nums = [4,3,10,9,8] 输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。
但是 [10,9] 的元素之和最大。
示例 2：输入：nums = [4,4,7,6,7] 输出：[7,7,6]
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。
因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。
示例 3：输入：nums = [6] 输出：[6]
提示：
1 <= nums.length <= 500
1 <= nums[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(n) |
| 02 | 排序遍历 | O(nlog(n)) | O(1) |
func minSubsequence(nums []int) []int {
sort.Ints(nums)
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
target := sum / 2
sum = 0
res := make([]int, 0)
for i := len(nums) - 1; i >= 0; i-- {
if sum <= target {
res = append(res, nums[i])
sum = sum + nums[i]
}
}
return res
}
#
func minSubsequence(nums []int) []int {
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
target := sum / 2
sum = 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if sum > target {
return nums[:i+1]
}
}
return nil
}
1408.数组中的字符串匹配(3)¶
题目
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。
请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，
那么字符串 words[i] 就是 words[j] 的一个子字符串。
示例 1：输入：words = ["mass","as","hero","superhero"] 输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。
示例 2：输入：words = ["leetcode","et","code"] 输出：["et","code"]
解释："et" 和 "code" 都是 "leetcode" 的子字符串。
示例 3：输入：words = ["blue","green","bu"] 输出：[]
提示：
1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] 仅包含小写英文字母。
题目数据 保证 每个 words[i] 都是独一无二的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-内置函数 | O(n^3) | O(n) |
| 02 | 遍历-内置函数 | O(n^3) | O(n) |
| 03 | 排序 | O(n^3) | O(n) |
func stringMatching(words []string) []string {
res := make([]string, 0)
m := make(map[string]bool)
for i := 0; i < len(words); i++ {
for j := i + 1; j < len(words); j++ {
if strings.Contains(words[i], words[j]) {
if _, ok := m[words[j]]; !ok {
res = append(res, words[j])
m[words[j]] = true
}
} else if strings.Contains(words[j], words[i]) {
if _, ok := m[words[i]]; !ok {
res = append(res, words[i])
m[words[i]] = true
}
}
}
}
return res
}
#
func stringMatching(words []string) []string {
res := make([]string, 0)
for i := 0; i < len(words); i++ {
for j := 0; j < len(words); j++ {
if i != j && strings.Contains(words[j], words[i]) {
res = append(res, words[i])
break
}
}
}
return res
}
#
func stringMatching(words []string) []string {
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
res := make([]string, 0)
for i := 0; i < len(words); i++ {
for j := i + 1; j < len(words); j++ {
if strings.Contains(words[j], words[i]) {
res = append(res, words[i])
break
}
}
}
return res
}
1413.逐步求和得到正数的最小值(2)¶
题目
给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。
示例 1：输入：nums = [-3,2,-3,4,2] 输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
累加求和
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
示例 2：输入：nums = [1,2] 输出：1
解释：最小的 startValue 需要是正数。
示例 3：输入：nums = [1,-2,-3] 输出：5
提示：
1 <= nums.length <= 100
-100 <= nums[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func minStartValue(nums []int) int {
min := nums[0]
sum := nums[0]
for i := 1; i < len(nums); i++ {
sum = sum + nums[i]
if sum < min {
min = sum
}
}
if min >= 0 {
return 1
}
return 1 - min
}
#
func minStartValue(nums []int) int {
res := 1
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if sum+res < 1 {
res = 1 - sum
}
}
return res
}
1417.重新格式化字符串(2)¶
题目
给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。
请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。
也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。
请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。
示例 1：输入：s = "a0b1c2" 输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。
"a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。
示例 2：输入：s = "leetcode" 输出：""
解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。
示例 3：输入：s = "1229857369" 输出：""
解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。
示例 4：输入：s = "covid2019" 输出："c2o0v1i9d"
示例 5：输入：s = "ab123" 输出："1a2b3"
提示：
1 <= s.length <= 500
s 仅由小写英文字母和/或数字组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
func reformat(s string) string {
arr := make([]byte, 0)
str := make([]byte, 0)
res := ""
for i := 0; i < len(s); i++ {
if s[i] >= '0' && s[i] <= '9' {
arr = append(arr, s[i])
} else {
str = append(str, s[i])
}
}
if abs(len(arr), len(str)) > 1 {
return res
} else {
length := len(arr)
if len(str) < length {
length = len(str)
}
for i := 0; i < length; i++ {
res = res + string(arr[i])
res = res + string(str[i])
}
if length == len(str) && length < len(arr) {
res = res + string(arr[length])
} else if length == len(arr) && length < len(str) {
res = string(str[length]) + res
}
}
return res
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
#
func reformat(s string) string {
res := make([]byte, 0)
m1 := make([]byte, 0)
m2 := make([]byte, 0)
for i := range s {
if s[i] >= '0' && s[i] <= '9' {
m1 = append(m1, s[i])
} else {
m2 = append(m2, s[i])
}
}
if len(m1)-len(m2) == 1 {
for i := 0; i < len(m2); i++ {
res = append(res, m1[i])
res = append(res, m2[i])
}
res = append(res, m1[len(m1)-1])
return string(res)
} else if len(m2)-len(m1) == 1 {
for i := 0; i < len(m1); i++ {
res = append(res, m2[i])
res = append(res, m1[i])
}
res = append(res, m2[len(m2)-1])
return string(res)
} else if len(m2) == len(m1) {
for i := 0; i < len(m1); i++ {
res = append(res, m2[i])
res = append(res, m1[i])
}
return string(res)
} else {
return ""
}
}
1422.分割字符串的最大得分(3)¶
题目
给你一个由若干 0 和 1 组成的字符串 s ，
请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
示例 1：输入：s = "011101" 输出：5
解释：
将字符串 s 划分为两个非空子字符串的可行方案有：
左子字符串 = "0" 且 右子字符串 = "11101"，得分 = 1 + 4 = 5
左子字符串 = "01" 且 右子字符串 = "1101"，得分 = 1 + 3 = 4
左子字符串 = "011" 且 右子字符串 = "101"，得分 = 1 + 2 = 3
左子字符串 = "0111" 且 右子字符串 = "01"，得分 = 1 + 1 = 2
左子字符串 = "01110" 且 右子字符串 = "1"，得分 = 2 + 1 = 3
示例 2：输入：s = "00111" 输出：5
解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5
示例 3：输入：s = "1111" 输出：3
提示：
2 <= s.length <= 500
字符串 s 仅由字符 '0' 和 '1' 组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 暴力法 | O(n^2) | O(1) |
| 03 | 数组辅助 | O(n) | O(n) |
func maxScore(s string) int {
one := 0
for i := 0; i < len(s); i++ {
if s[i] == '1' {
one++
}
}
max := 0
zero := 0
for i := 0; i < len(s)-1; i++ {
if s[i] == '1' {
one--
} else {
zero++
}
if one+zero > max {
max = one + zero
}
}
return max
}
#
func maxScore(s string) int {
max := 0
for i := 0; i < len(s)-1; i++ {
zero := 0
one := 0
for j := 0; j <= i; j++ {
if s[j] == '0' {
zero++
}
}
for j := i + 1; j < len(s); j++ {
if s[j] == '1' {
one++
}
}
if zero+one > max {
max = zero + one
}
}
return max
}
#
func maxScore(s string) int {
max := 0
arr := make([]int, len(s)+1)
for i := 0; i < len(s); i++ {
if s[i] == '1' {
arr[i+1] = arr[i] + 1
} else {
arr[i+1] = arr[i]
}
}
for i := 1; i < len(s); i++ {
zero := i - arr[i]
one := arr[len(s)] - arr[i]
v := zero + one
if v > max {
max = v
}
}
return max
}
1431.拥有最多糖果的孩子(2)¶
题目
给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。
注意，允许有多个孩子同时拥有 最多 的糖果数目。
示例 1：输入：candies = [2,3,5,1,3], extraCandies = 3 输出：[true,true,true,false,true]
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
示例 2：输入：candies = [4,2,1,1,2], extraCandies = 1 输出：[true,false,false,false,false]
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。
示例 3：输入：candies = [12,1,12], extraCandies = 10 输出：[true,false,true]
提示：
2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历比较 | O(n) | O(n) |
| 02 | 暴力法 | O(n^2) | O(n) |
func kidsWithCandies(candies []int, extraCandies int) []bool {
res := make([]bool, len(candies))
max := 0
for i := 0; i < len(candies); i++ {
if candies[i] > max {
max = candies[i]
}
}
for i := 0; i < len(candies); i++ {
if candies[i]+extraCandies >= max {
res[i] = true
}
}
return res
}
#
func kidsWithCandies(candies []int, extraCandies int) []bool {
res := make([]bool, len(candies))
for i := 0; i < len(candies); i++ {
flag := true
for j := 0; j < len(candies); j++ {
if candies[i]+extraCandies < candies[j] {
flag = false
res[i] = false
break
}
}
if flag == true {
res[i] = true
}
}
return res
}
1436.旅行终点站(4)¶
题目
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，
其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。
请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
示例 1：
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo"
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。
本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
示例 2：输入：paths = [["B","C"],["D","B"],["C","A"]] 输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
显然，旅行终点站是 "A" 。
示例 3：输入：paths = [["A","Z"]] 输出："Z"
提示：
1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
所有字符串均由大小写英文字母和空格字符组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
| 02 | 哈希辅助 | O(n) | O(n) |
| 03 | 出入度计算 | O(n) | O(n) |
| 04 | 暴力法 | O(n^2) | O(1) |
func destCity(paths [][]string) string {
m := make(map[string]string)
for i := 0; i < len(paths); i++ {
m[paths[i][0]] = paths[i][1]
}
for _, v := range m {
if _, ok := m[v]; !ok {
return v
}
}
return ""
}
#
func destCity(paths [][]string) string {
m := make(map[string]bool)
for i := 0; i < len(paths); i++ {
m[paths[i][1]] = true
}
for i := 0; i < len(paths); i++ {
m[paths[i][0]] = false
}
for key, value := range m {
if value == true {
return key
}
}
return ""
}
#
func destCity(paths [][]string) string {
m := make(map[string]int)
for i := 0; i < len(paths); i++ {
m[paths[i][1]] -= 1
m[paths[i][0]] += 1
}
for key, value := range m {
if value == -1 {
return key
}
}
return ""
}
#
func destCity(paths [][]string) string {
for i := 0; i < len(paths); i++{
flag := false
for j := 0; j < len(paths); j++{
if j == i {
continue
}
if paths[i][1] == paths[j][0]{
flag = true
break
}
}
if flag == false{
return paths[i][1]
}
}
return ""
}
1441.用栈操作构建数组(2)¶
题目
给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target ：
Push：从 list 中读取一个新元素， 并将其推入数组中。
Pop：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。
题目数据保证答案是唯一的。
示例 1：输入：target = [1,3], n = 3 输出：["Push","Push","Pop","Push"]
解释：
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]
示例 2：输入：target = [1,2,3], n = 3 输出：["Push","Push","Push"]
示例 3：输入：target = [1,2], n = 4 输出：["Push","Push"]
解释：只需要读取前 2 个数字就可以停止。
示例 4：输入：target = [2,3,4], n = 4 输出：["Push","Pop","Push","Push","Push"]
提示：
1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target 是严格递增的
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 双指针 | O(n) | O(n) |
| 02 | 双指针 | O(n) | O(n) |
func buildArray(target []int, n int) []string {
res := make([]string, 0)
j := 0
for i := 1; i <= n; i++ {
if j >= len(target) {
break
}
if target[j] != i {
res = append(res, "Push")
res = append(res, "Pop")
} else {
res = append(res, "Push")
j++
}
}
return res
}
#
func buildArray(target []int, n int) []string {
res := make([]string, 0)
j := 1
for i := 0; i < len(target); i++ {
for ; j < target[i]; j++ {
res = append(res, "Push")
res = append(res, "Pop")
}
res = append(res, "Push")
j++
}
return res
}
1446.连续字符(2)¶
题目
给你一个字符串 s ，字符串的「能量」定义为：只包含一种字符的最长非空子字符串的长度。
请你返回字符串的能量。
示例 1：输入：s = "leetcode" 输出：2
解释：子字符串 "ee" 长度为 2 ，只包含字符 'e' 。
示例 2：输入：s = "abbcccddddeeeeedcba" 输出：5
解释：子字符串 "eeeee" 长度为 5 ，只包含字符 'e' 。
示例 3：输入：s = "triplepillooooow" 输出：5
示例 4：输入：s = "hooraaaaaaaaaaay" 输出：11
示例 5：输入：s = "tourist" 输出：1
提示：
1 <= s.length <= 500
s 只包含小写英文字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 双指针 | O(n) | O(1) |
func maxPower(s string) int {
max := 1
count := 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
count++
} else {
count = 1
}
if count > max {
max = count
}
}
return max
}
#
func maxPower(s string) int {
max := 1
left := 0
right := 1
for right < len(s) {
if s[left] != s[right] {
if right-left > max {
max = right - left
}
left = right
}
right++
}
if right-left > max {
return right - left
}
return max
}
1450.在既定时间做作业的学生人数(1)¶
题目
给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。
已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。
请返回在查询时间 queryTime 时正在做作业的学生人数。
形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。
示例 1：输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4 输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。
示例 2：输入：startTime = [4], endTime = [4], queryTime = 4 输出：1
解释：在查询时间只有一名学生在做作业。
示例 3：输入：startTime = [4], endTime = [4], queryTime = 5 输出：0
示例 4：输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7 输出：0
示例 5：输入：startTime = [9,8,7,6,5,4,3,2,1],
endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5
提示：
startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
func busyStudent(startTime []int, endTime []int, queryTime int) int {
res := 0
for i := 0; i < len(startTime); i++ {
if queryTime >= startTime[i] && queryTime <= endTime[i] {
res++
}
}
return res
}
1455.检查单词是否为句中其他单词的前缀(2)¶
题目
给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。
请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。
如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。
如果 searchWord 不是任何单词的前缀，则返回 -1 。
字符串 S 的 「前缀」是 S 的任何前导连续子字符串。
示例 1：输入：sentence = "i love eating burger", searchWord = "burg" 输出：4
解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。
示例 2：输入：sentence = "this problem is an easy problem", searchWord = "pro" 输出：2
解释："pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，
但是应该返回最小下标 2 。
示例 3：输入：sentence = "i am tired", searchWord = "you" 输出：-1
解释："you" 不是句子中任何单词的前缀。
示例 4：输入：sentence = "i use triple pillow", searchWord = "pill" 输出：4
示例 5：输入：sentence = "hello from the other side", searchWord = "they" 输出：-1
提示：
1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence 由小写英文字母和空格组成。
searchWord 由小写英文字母组成。
前缀就是紧密附着于词根的语素，中间不能插入其它成分，并且它的位置是固定的——-位于词根之前。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
func isPrefixOfWord(sentence string, searchWord string) int {
arr := strings.Split(sentence, " ")
for k, v := range arr {
if strings.HasPrefix(v, searchWord) {
return k + 1
}
}
return -1
}
#
func isPrefixOfWord(sentence string, searchWord string) int {
arr := strings.Fields(sentence)
for k, v := range arr {
if len(v) >= len(searchWord) {
if v[:len(searchWord)] == searchWord {
return k + 1
}
}
}
return -1
}
1460.通过翻转子数组使两个数组相等(3)¶
题目
给你两个长度相同的整数数组 target 和 arr 。
每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。
如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。
示例 1：输入：target = [1,2,3,4], arr = [2,4,1,3] 输出：true
解释：你可以按照如下步骤使 arr 变成 target：
1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]
上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。
示例 2：输入：target = [7], arr = [7] 输出：true
解释：arr 不需要做任何翻转已经与 target 相等。
示例 3：输入：target = [1,12], arr = [12,1] 输出：true
示例 4：输入：target = [3,7,9], arr = [3,7,11] 输出：false
解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。
示例 5：输入：target = [1,1,1,1,1], arr = [1,1,1,1,1] 输出：true
提示：
target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(1) |
| 02 | 数组辅助 | O(n) | O(1) |
| 03 | 哈希辅助 | O(n) | O(1) |
func canBeEqual(target []int, arr []int) bool {
sort.Ints(target)
sort.Ints(arr)
for i := 0; i < len(target); i++ {
if target[i] != arr[i] {
return false
}
}
return true
}
#
func canBeEqual(target []int, arr []int) bool {
temp := make([]int, 1001)
for i := 0; i < len(target); i++ {
temp[target[i]]++
temp[arr[i]]--
}
for i := 0; i < len(temp); i++ {
if temp[i] != 0 {
return false
}
}
return true
}
1464.数组中两元素的最大乘积(3)¶
题目
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。
示例 1：输入：nums = [3,4,5,2] 输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，
(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。
示例 2：输入：nums = [1,5,4,5] 输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。
示例 3：输入：nums = [3,7] 输出：12
提示：
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
| 03 | 暴力法 | O(n^2) | O(1) |
func maxProduct(nums []int) int {
sort.Ints(nums)
return (nums[len(nums)-1] - 1) * (nums[len(nums)-2] - 1)
}
#
func maxProduct(nums []int) int {
max := math.MinInt32
next := math.MinInt32
for i := 0; i < len(nums); i++ {
if nums[i] > max {
next, max = max, nums[i]
} else if nums[i] > next {
next = nums[i]
}
}
return (max - 1) * (next - 1)
}
#
func maxProduct(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if (nums[i]-1)*(nums[j]-1) > res {
res = (nums[i] - 1) * (nums[j] - 1)
}
}
}
return res
}
1470.重新排列数组(2)¶
题目
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：输入：nums = [2,5,1,3,4,7], n = 3 输出：[2,3,5,4,1,7]
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：输入：nums = [1,2,3,4,4,3,2,1], n = 4 输出：[1,4,2,3,3,2,4,1]
示例 3：输入：nums = [1,1,2,2], n = 2 输出：[1,2,1,2]
提示：
1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 数组辅助 | O(n) | O(n) |
| 02 | 前移遍历 | O(n^1) | O(1) |
func shuffle(nums []int, n int) []int {
res := make([]int,0)
for i := 0; i < n; i++{
res = append(res, nums[i], nums[i+n])
}
return res
}
#
func shuffle(nums []int, n int) []int {
for i := n; i < 2*n; i++ {
temp := i
for j := 0; j < 2*n-1-i; j++ {
nums[temp], nums[temp-1] = nums[temp-1], nums[temp]
temp--
}
}
return nums
}
1475.商品折扣后的最终价格(2)¶
题目
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，
其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，
如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
示例 1：输入：prices = [8,4,6,2,3] 输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。
示例 2：输入：prices = [1,2,3,4,5] 输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。
示例 3：输入：prices = [10,1,1,6] 输出：[9,0,1,6]
提示：
1 <= prices.length <= 500
1 <= prices[i] <= 10^3
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历模拟 | O(n^2) | O(1) |
| 02 | 栈 | O(n) | O(n) |
func finalPrices(prices []int) []int {
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
if prices[j] <= prices[i] {
prices[i] = prices[i] - prices[j]
break
}
}
}
return prices
}
#
func finalPrices(prices []int) []int {
stack := make([]int, 0)
for i := 0; i < len(prices); i++ {
for len(stack) > 0 {
index := stack[len(stack)-1]
if prices[i] > prices[index] {
break
}
prices[index] = prices[index] - prices[i]
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return prices
}
1480.一维数组的动态和(2)¶
题目
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
示例 1：输入：nums = [1,2,3,4] 输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：输入：nums = [1,1,1,1,1] 输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：输入：nums = [3,1,2,10,1] 输出：[3,4,6,16,17]
提示：
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 数组辅助 | O(n) | O(n) |
func runningSum(nums []int) []int {
for i := 1; i < len(nums); i++{
nums[i] = nums[i-1]+nums[i]
}
return nums
}
#
func runningSum(nums []int) []int {
res := make([]int, len(nums))
res[0] = nums[0]
for i := 1; i < len(nums); i++ {
res[i] = res[i-1] + nums[i]
}
return res
}
1486.数组异或操作(1)¶
题目
给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
示例 1：输入：n = 5, start = 0 输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
"^" 为按位异或 XOR 运算符。
示例 2：输入：n = 4, start = 3 输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.
示例 3：输入：n = 1, start = 7 输出：7
示例 4：输入：n = 10, start = 5 输出：2
提示：
1 <= n <= 1000
0 <= start <= 1000
n == nums.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
func xorOperation(n int, start int) int {
res := 0
for i := 0; i < n; i++ {
res = res ^ (start + 2*i)
}
return res
}
1491.去掉最低工资和最高工资后的工资平均值(2)¶
题目
给你一个整数数组 salary ，数组里每个数都是 唯一 的，其中 salary[i] 是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。
示例 1：输入：salary = [4000,3000,1000,2000] 输出：2500.00000
解释：最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500
示例 2：输入：salary = [1000,2000,3000] 输出：2000.00000
解释：最低工资和最高工资分别是 1000 和 3000 。
去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000
示例 3：输入：salary = [6000,5000,4000,3000,2000,1000] 输出：3500.00000
示例 4：输入：salary = [8000,9000,2000,3000,6000,1000] 输出：4750.00000
提示：
3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] 是唯一的。
与真实值误差在 10^-5 以内的结果都将视为正确答案。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func average(salary []int) float64 {
sort.Ints(salary)
sum := 0
for i := 1; i < len(salary)-1; i++ {
sum = sum + salary[i]
}
return float64(sum) / float64(len(salary)-2)
}
#
func average(salary []int) float64 {
sum := salary[0]
max := salary[0]
min := salary[0]
for i := 1; i < len(salary); i++ {
sum = sum + salary[i]
if salary[i] > max {
max = salary[i]
}
if salary[i] < min {
min = salary[i]
}
}
return float64(sum-max-min) / float64(len(salary)-2)
}
1496.判断路径是否相交(1)¶
题目
给你一个字符串 path，其中 path[i] 的值可以是 'N'、'S'、'E' 或者 'W'，
分别表示向北、向南、向东、向西移动一个单位。
机器人从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。
如果路径在任何位置上出现相交的情况，也就是走到之前已经走过的位置，请返回 True ；否则，返回 False 。
示例 1：输入：path = "NES" 输出：false
解释：该路径没有在任何位置相交。
示例 2：输入：path = "NESWW" 输出：true
解释：该路径经过原点两次。
提示：
1 <= path.length <= 10^4
path 仅由 {'N', 'S', 'E', 'W} 中的字符组成
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
func isPathCrossing(path string) bool {
m := make(map[string]bool)
m["0,0"] = true
x := 0
y := 0
for i := 0; i < len(path); i++ {
switch path[i] {
case 'N':
y = y + 1
case 'S':
y = y - 1
case 'E':
x = x + 1
case 'W':
x = x - 1
}
if m[fmt.Sprintf("%d,%d", x, y)] {
return true
}
m[fmt.Sprintf("%d,%d", x, y)] = true
}
return false
}
1401-1500-Medium¶
1401.圆和矩形是否有重叠(2)¶
题目
给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2)，
其中(x1, y1) 是矩形左下角的坐标，(x2, y2) 是右上角的坐标。
如果圆和矩形有重叠的部分，请你返回 True ，否则返回 False。
换句话说，请你检测是否 存在 点(xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。
示例 1：输入：radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形有公共点 (1,0)
示例 2：输入：radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true
示例 3：输入：radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
输出：true
示例 4：输入：radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false
提示：1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 几何 | O(1) | O(1) |
| 02 | 几何 | O(1) | O(1) |
func checkOverlap(radius int, x_center int, y_center int, x1 int, y1 int, x2 int, y2 int) bool {
if x1 <= x_center && x_center <= x2 && // 在里面
y1 <= y_center && y_center <= y2 {
return true
} else if x_center > x2 && y1 <= y_center && y_center <= y2 { // 右边
return x_center-x2 <= radius
} else if x_center < x1 && y1 <= y_center && y_center <= y2 { // 左边
return x1-x_center <= radius
} else if y_center < y1 && x1 <= x_center && x_center <= x2 { // 下边
return y1-y_center <= radius
} else if y_center > y2 && x1 <= x_center && x_center <= x2 { // 上边
return y_center-y2 <= radius
}
// 4个顶点判断
minValue := (x1-x_center)*(x1-x_center) + (y1-y_center)*(y1-y_center)
minValue = min(minValue, (x1-x_center)*(x1-x_center)+(y2-y_center)*(y2-y_center))
minValue = min(minValue, (x2-x_center)*(x2-x_center)+(y1-y_center)*(y1-y_center))
minValue = min(minValue, (x2-x_center)*(x2-x_center)+(y2-y_center)*(y2-y_center))
return minValue <= radius*radius
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func checkOverlap(radius int, x_center int, y_center int, x1 int, y1 int, x2 int, y2 int) bool {
minValue := 0
// minValue = (x-x_center)*(x-x_center)+(y-y_center)*(y-y_center)
if x_center < x1 || x_center > x2 {
minValue = minValue + min((x1-x_center)*(x1-x_center), (x2-x_center)*(x2-x_center))
}
if y_center < y1 || y_center > y2 {
minValue = minValue + min((y1-y_center)*(y1-y_center), (y2-y_center)*(y2-y_center))
}
return minValue <= radius*radius
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1404.将二进制表示减到1的步骤数(2)¶
题目
给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
如果当前数字为偶数，则将其除以 2 。
如果当前数字为奇数，则将其加上 1 。
题目保证你总是可以按上述规则将测试用例变为 1 。
示例 1：输入：s = "1101" 输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7 是奇数，加 1 得到 8
Step 4) 8 是偶数，除 2 得到 4
Step 5) 4 是偶数，除 2 得到 2
Step 6) 2 是偶数，除 2 得到 1
示例 2：输入：s = "10" 输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1
示例 3：输入：s = "1" 输出：0
提示：1 <= s.length <= 500
s 由字符 '0' 或 '1' 组成。
s[0] == '1'
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 模拟 | O(n^2) | O(n) |
| 02 | 遍历 | O(n) | O(1) |
func numSteps(s string) int {
res := 0
for s != "1" {
n := len(s)
if s[n-1] == '0' {
s = s[:n-1]
} else {
s = add(s)
}
res++
}
return res
}
func add(s string) string {
arr := []byte(s)
flag := true
for i := len(arr) - 1; i >= 0; i-- {
if arr[i] == '0' {
arr[i] = '1'
flag = false
} else {
arr[i] = '0'
}
if flag == false {
return string(arr)
}
}
return "1" + string(arr)
}
# 2
func numSteps(s string) int {
res := 0
flag := false
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '0' {
if flag == true {
res = res + 2
} else {
res = res + 1 // 没有进位，遇0加1
}
} else {
if flag == true {
res++
} else {
if i != 0 {
res = res + 2
}
flag = true
}
}
}
return res
}
1405.最长快乐字符串(1)¶
题目
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 'a'、b个字母 'b'、c 个字母 'c' 。
s 中只含有 'a'、'b' 、'c' 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例 1：输入：a = 1, b = 1, c = 7 输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。
示例 2：输入：a = 2, b = 2, c = 1 输出："aabbc"
示例 3：输入：a = 7, b = 1, c = 0 输出："aabaa"
解释：这是该测试用例的唯一正确答案。
提示：0 <= a, b, c <= 100
a + b + c > 0
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 贪心 | O(1) | O(1) |
func longestDiverseString(a int, b int, c int) string {
arr := [][2]int{
{0, a},
{1, b},
{2, c},
}
res := make([]byte, 0)
for {
// 按照次数排序
sort.Slice(arr, func(i, j int) bool {
return arr[i][1] < arr[j][1]
})
// 每次放1个，如果最后2个相同，则使用次多的
if len(res) >= 2 &&
res[len(res)-1] == byte(arr[2][0]+'a') &&
res[len(res)-2] == byte(arr[2][0]+'a') {
if arr[1][1] > 0 { // 使用次多的
res = append(res, byte(arr[1][0]+'a'))
arr[1][1]--
} else {
break
}
} else {
if arr[2][1] > 0 { // 使用最多的
res = append(res, byte(arr[2][0]+'a'))
arr[2][1]--
} else {
break
}
}
}
return string(res)
}
1409.查询带键的排列(4)¶
题目
给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。
请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：
一开始，排列 P=[1,2,3,...,m]。
对于当前的 i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），
然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。
注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。
请你以数组形式返回待查数组 queries 的查询结果。
示例 1：输入：queries = [3,1,2,1], m = 5 输出：[2,1,2,1]
解释：待查数组 queries 处理如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。
因此，返回的结果数组为 [2,1,2,1] 。
示例 2：输入：queries = [4,1,2,2], m = 4 输出：[3,1,2,0]
示例 3：输入：queries = [7,5,5,8,3], m = 8 输出：[6,5,0,7,5]
提示：1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 模拟 | O(n^2) | O(n) |
| 02 | 模拟 | O(n^2) | O(n) |
| 03 | 模拟 | O(n^2) | O(n) |
| 04 | 树状数组 | O(nlog(n)) | O(n) |
func processQueries(queries []int, m int) []int {
n := len(queries)
res := make([]int, n)
arr := make([]int, m)
for i := 0; i < m; i++ {
arr[i] = i + 1
}
for i := 0; i < n; i++ {
index := 0
for j := 0; j < m; j++ {
if arr[j] == queries[i] {
index = j
break
}
}
res[i] = index
arr = append(append([]int{arr[index]}, arr[:index]...), arr[index+1:]...)
}
return res
}
# 2
func processQueries(queries []int, m int) []int {
n := len(queries)
res := make([]int, n)
arr := make([]int, m)
for i := 0; i < m; i++ {
arr[i] = i + 1
}
for i := 0; i < n; i++ {
index := 0
for j := 0; j < m; j++ {
if arr[j] == queries[i] {
index = j
// 交换位置
for k := 0; k < index; k++ {
arr[k], arr[index] = arr[index], arr[k]
}
break
}
}
res[i] = index
}
return res
}
# 3
func processQueries(queries []int, m int) []int {
n := len(queries)
res := make([]int, n)
arr := make([]int, m+1) // 存放下标
for i := 1; i <= m; i++ {
arr[i] = i - 1
}
for i := 0; i < n; i++ {
x := queries[i]
index := arr[x]
res[i] = index
for j := 1; j <= m; j++ {
if arr[j] < index { // 下标小于目标值
arr[j]++ // 前面的后移
}
}
arr[x] = 0 // 移到第一位
}
return res
}
# 4
func processQueries(queries []int, m int) []int {
n := len(queries)
res := make([]int, n)
// 使用树状数组
c = make([]int, n+m+1)
length = n + m
arr := make([]int, m+1)
for i := 1; i <= m; i++ {
arr[i] = n + i
upData(n+i, 1) // 数组长度n+m+1，从后面n开始存
}
for i := 0; i < n; i++ {
cur := arr[queries[i]]
upData(cur, -1) // cur位置-1
res[i] = getSum(cur) // cur之前的个数
cur = n - i
arr[queries[i]] = cur // 移到到n-i，每次往前移动1位
upData(cur, 1) // cur位置+1
}
return res
}
var length int
var c []int // 树状数组
func lowBit(x int) int {
return x & (-x)
}
// 单点修改
func upData(i, k int) { // 在i位置加上k
for i <= length {
c[i] = c[i] + k
i = i + lowBit(i) // i = i + 2^k
}
}
// 区间查询
func getSum(i int) int {
res := 0
for i > 0 {
res = res + c[i]
i = i - lowBit(i)
}
return res
}
1410.HTML实体解析器(3)¶
题目
「HTML实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，
并用字符本身替换掉所有这些特殊的字符实体。
HTML 里这些特殊字符和它们对应的字符实体包括：
双引号：字符实体为"，对应的字符是"。
单引号：字符实体为'，对应的字符是'。
与符号：字符实体为&，对应对的字符是&。
大于号：字符实体为>，对应的字符是>。
小于号：字符实体为<，对应的字符是<。
斜线号：字符实体为⁄，对应的字符是/。
给你输入字符串text，请你实现一个 HTML实体解析器，返回解析器解析后的结果。
示例 1：输入：text = "& is an HTML entity but &ambassador; is not."
输出："& is an HTML entity but &ambassador; is not."
解释：解析器把字符实体 & 用 & 替换
示例2：输入：text = "and I quote: "...""
输出："and I quote: \"...\""
示例 3：输入：text = "Stay home! Practice on Leetcode :)"
输出："Stay home! Practice on Leetcode :)"
示例 4：输入：text = "x > y && x < y is always false"
输出："x > y && x < y is always false"
示例 5：输入：text = "leetcode.com⁄problemset⁄all"
输出："leetcode.com/problemset/all"
提示：1 <= text.length <= 10^5
字符串可能包含 256 个ASCII 字符中的任意字符。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 内置函数 | O(n) | O(n) |
| 02 | 内置函数 | O(n) | O(n) |
| 03 | 遍历 | O(n) | O(n) |
func entityParser(text string) string {
text = html.UnescapeString(text)
return strings.ReplaceAll(text, "⁄", "/")
}
# 2
func entityParser(text string) string {
text = strings.ReplaceAll(text, """, "\"")
text = strings.ReplaceAll(text, "'", "'")
text = strings.ReplaceAll(text, ">", ">")
text = strings.ReplaceAll(text, "<", "<")
text = strings.ReplaceAll(text, "⁄", "/")
text = strings.ReplaceAll(text, "&", "&")
return text
}
# 3
func entityParser(text string) string {
res := make([]byte, 0)
temp := make([]byte, 0)
for i := 0; i < len(text); i++ {
if text[i] == '&' {
if len(temp) == 0 {
temp = append(temp, text[i])
} else {
res = append(res, temp...)
temp = make([]byte, 0)
temp = append(temp, text[i])
}
} else if text[i] == ';' {
temp = append(temp, text[i])
switch string(temp) {
case ">":
res = append(res, '>')
case "<":
res = append(res, '<')
case """:
res = append(res, '"')
case "'":
res = append(res, '\'')
case "⁄":
res = append(res, '/')
case "&":
res = append(res, '&')
default:
res = append(res, temp...)
}
temp = make([]byte, 0)
} else if len(temp) == 0 {
res = append(res, text[i])
} else {
temp = append(temp, text[i])
}
}
if len(temp) > 0 {
res = append(res, temp...)
}
return string(res)
}
1414.和为K的最少斐波那契数字数目(2)¶
题目
给你数字 k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2， 其中 n > 2 。
数据保证对于给定的 k，一定能找到可行解。
示例 1：输入：k = 7 输出：2
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。
示例 2：输入：k = 10 输出：2
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
示例 3：输入：k = 19 输出：3
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
提示：1 <= k <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(log(n)) | O(log(n)) |
| 02 | 遍历 | O(log(n)) | O(1) |
func findMinFibonacciNumbers(k int) int {
arr := make([]int, 2)
arr[0] = 1
arr[1] = 1
for arr[len(arr)-2]+arr[len(arr)-1] <= k {
arr = append(arr, arr[len(arr)-2]+arr[len(arr)-1])
}
res := 0
for i := len(arr) - 1; i >= 0; i-- {
for arr[i] <= k {
k = k - arr[i]
res++
}
}
return res
}
# 2
func findMinFibonacciNumbers(k int) int {
res := 0
for {
target := get(k)
k = k - target
res++
if k == 0 {
break
}
}
return res
}
func get(k int) int {
a, b := 1, 1
for {
a, b = b, a+b
if b > k {
return a
} else if b == k {
return b
}
}
}
1415.长度为n的开心字符串中字典序第k小的字符串(2)¶
题目
一个 「开心字符串」定义为：
仅包含小写字母['a', 'b', 'c'].
对所有在1到s.length - 1之间的i，满足s[i] != s[i + 1]（字符串的下标从 1 开始）。
比方说，字符串"abc"，"ac"，"b" 和"abcbabcbcb"都是开心字符串，
但是"aa"，"baa"和"ababbc"都不是开心字符串。
给你两个整数 n和 k，你需要将长度为 n的所有开心字符串按字典序排序。
请你返回排序后的第 k 个开心字符串，如果长度为 n的开心字符串少于 k个，那么请你返回 空字符串。
示例 1：输入：n = 1, k = 3 输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。
示例 2：输入：n = 1, k = 4 输出：""
解释：长度为 1 的开心字符串只有 3 个。
示例 3：输入：n = 3, k = 9 输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac",
"bca", "bcb", "cab", "cac", "cba", "cbc"] 。
第 9 个字符串为 "cab"
示例 4：输入：n = 2, k = 7 输出：""
示例 5：输入：n = 10, k = 100 输出："abacbabacb"
提示：1 <= n <= 10
1 <= k <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(2^n) | O(2^n) |
| 02 | 遍历 | O(n) | O(n) |
var arr []string
func getHappyString(n int, k int) string {
arr = make([]string, 0)
dfs(n, "")
if len(arr) < k {
return ""
}
return arr[k-1]
}
func dfs(n int, str string) {
if len(str) > 1 && str[len(str)-1] == str[len(str)-2] {
return
}
if len(str) == n {
arr = append(arr, str)
return
}
for i := 0; i < 3; i++ {
char := 'a' + i
dfs(n, str+string(char))
}
}
# 2
func getHappyString(n int, k int) string {
per := 1 << (n - 1)
if k > 3*per {
return ""
}
res := make([]byte, n)
next := [][]int{{1, 2}, {0, 2}, {0, 1}} // 3个分支
k = k - 1
var status int
for i := 0; i < n; i++ {
if i == 0 { // 确定第1个分支
status = k / per
} else {
per = per / 2
status = next[status][k/per] // 确定后面的分支
}
k = k % per
res[i] = byte(status + 'a')
}
return string(res)
}
1418.点菜展示表(1)¶
题目
给你一个数组 orders，表示客户在餐厅中完成的订单，确切地说，
orders[i]=[customerNamei,tableNumberi,foodItemi] ，其中 customerNamei 是客户的姓名，
tableNumberi 是客户所在餐桌的桌号，而 foodItemi 是客户点的餐品名称。
请你返回该餐厅的 点菜展示表 。在这张表中，表中第一行为标题，其第一列为餐桌桌号 “Table” ，
后面每一列都是按字母顺序排列的餐品名称。
接下来每一行中的项则表示每张餐桌订购的相应餐品数量，第一列应当填对应的桌号，后面依次填写下单的餐品数量。
注意：客户姓名不是点菜展示表的一部分。此外，表中的数据行应该按餐桌桌号升序排列。
示例 1：
输入：orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],
["David","3","Fried Chicken"],["Carla","5","Water"],
["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
输出：[["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],
["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]]
解释：点菜展示表如下所示：
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3 ,0 ,2 ,1 ,0
5 ,0 ,1 ,0 ,1
10 ,1 ,0 ,0 ,0
对于餐桌 3：David 点了 "Ceviche" 和 "Fried Chicken"，而 Rous 点了 "Ceviche"
而餐桌 5：Carla 点了 "Water" 和 "Ceviche"
餐桌 10：Corina 点了 "Beef Burrito"
示例 2：输入：orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],
["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],
["Brianna","1","Canadian Waffles"]]
输出：[["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]]
解释：对于餐桌 1：Adam 和 Brianna 都点了 "Canadian Waffles"
而餐桌 12：James, Ratesh 和 Amadeus 都点了 "Fried Chicken"
示例 3：
输入：orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
输出：[["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]
提示：
1 <= orders.length <= 5 * 10^4
orders[i].length == 3
1 <= customerNamei.length, foodItemi.length <= 20
customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。
tableNumberi 是 1 到 500 范围内的整数。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(nlog(n)) | O(n) |
func displayTable(orders [][]string) [][]string {
res := make([][]string, 0)
titles := make([]string, 0)
idArr := make([]int, 0)
m := make(map[string]bool)
m2 := make(map[string]map[string]int)
for i := 0; i < len(orders); i++ {
m[orders[i][2]] = true
if m2[orders[i][1]] == nil {
m2[orders[i][1]] = make(map[string]int)
}
m2[orders[i][1]][orders[i][2]]++
}
for k := range m {
titles = append(titles, k)
}
for k := range m2 {
tableID, _ := strconv.Atoi(k)
idArr = append(idArr, tableID)
}
sort.Strings(titles)
sort.Ints(idArr)
res = append(res, append([]string{"Table"}, titles...))
for i := 0; i < len(idArr); i++ {
tableStr := strconv.Itoa(idArr[i])
temp := make([]string, 0)
temp = append(temp, tableStr)
for j := 0; j < len(titles); j++ {
temp = append(temp, strconv.Itoa(m2[tableStr][titles[j]]))
}
res = append(res, temp)
}
return res
}
1419.数青蛙(2)¶
题目
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。
由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
注意：要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。
如果没有输出全部五个字母，那么它就不会发出声音。
如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
示例 1：输入：croakOfFrogs = "croakcroak" 输出：1
解释：一只青蛙 “呱呱” 两次
示例 2：输入：croakOfFrogs = "crcoakroak" 输出：2
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"
示例 3：输入：croakOfFrogs = "croakcrook" 输出：-1
解释：给出的字符串不是 "croak" 的有效组合。
示例 4：输入：croakOfFrogs = "croakcroa" 输出：-1
提示：1 <= croakOfFrogs.length <= 10^5
字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func minNumberOfFrogs(croakOfFrogs string) int {
res := 0
var c, r, o, a, k int
temp := 0
for _, char := range croakOfFrogs {
if char == 'c' {
c++
if temp > 0 {
temp-- // 有空闲的青蛙
} else {
res++ // 没有空闲的青蛙
}
} else if r < c && char == 'r' {
r++
} else if o < r && char == 'o' {
o++
} else if a < o && char == 'a' {
a++
} else if k < a && char == 'k' {
k++
temp++ // 结束有空闲
} else {
return -1
}
}
if temp != res { // 避免出现"croakcroa"的情况
return -1
}
return res
}
# 2
func minNumberOfFrogs(croakOfFrogs string) int {
res := 0
var c, r, o, a, k int
for _, char := range croakOfFrogs {
if char == 'c' {
c++
} else if char == 'r' {
r++
} else if char == 'o' {
o++
} else if char == 'a' {
a++
} else if char == 'k' {
k++
} else {
return -1
}
res = max(res, c)
if c < r || r < o || o < a || a < k {
return -1
}
if k == 1 {
c--
r--
o--
a--
k--
}
}
if c == 0 && r == 0 && o == 0 && a == 0 && k == 0 {
return res
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1423.可获得的最大点数(2)¶
题目
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：输入：cardPoints = [1,2,3,4,5,6,1], k = 3 输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。
最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：输入：cardPoints = [2,2,2], k = 2 输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：输入：cardPoints = [9,7,7,9,7,7,9], k = 7 输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：输入：cardPoints = [1,1000,1], k = 1 输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3 输出：202
提示：1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口 | O(n) | O(1) |
| 02 | 滑动窗口 | O(n) | O(1) |
func maxScore(cardPoints []int, k int) int {
res := 0
left := 0
for i := 0; i < k; i++ {
left = left + cardPoints[i]
}
res = left
right := 0
count := k
for i := len(cardPoints) - 1; i >= len(cardPoints)-k; i-- {
right = right + cardPoints[i]
left = left - cardPoints[count-1]
res = max(res, left+right)
count--
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxScore(cardPoints []int, k int) int {
res := 0
n := len(cardPoints)
window := 0
sum := 0
for i := 0; i < n-k; i++ {
sum = sum + cardPoints[i]
window = window + cardPoints[i]
}
res = window
count := 0
for i := n - k; i < n; i++ {
sum = sum + cardPoints[i]
window = window + cardPoints[i] - cardPoints[count]
res = min(res, window)
count++
}
return sum - res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1424.对角线遍历II(2)¶
题目
给你一个列表 nums ，里面每一个元素都是一个整数列表。
请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
示例 1：输入：nums = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,4,2,7,5,3,8,6,9]
示例 2：输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
示例 3：输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] 输出：[1,4,2,5,3,8,6,9,7,10,11]
示例 4：输入：nums = [[1,2,3,4,5,6]] 输出：[1,2,3,4,5,6]
提示： 1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
nums 中最多有 10^5 个数字。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序 | O((nlog(n))^2) | O(n^2) |
| 02 | 哈希辅助 | O(n^2) | O(n^2) |
func findDiagonalOrder(nums [][]int) []int {
arr := make([][2]int, 0)
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums[i]); j++ {
arr = append(arr, [2]int{i, j})
}
}
sort.Slice(arr, func(i, j int) bool {
a := arr[i][0] + arr[i][1]
b := arr[j][0] + arr[j][1]
if a == b {
return arr[i][1] < arr[j][1]
}
return a < b
})
res := make([]int, 0)
for i := 0; i < len(arr); i++ {
a, b := arr[i][0], arr[i][1]
res = append(res, nums[a][b])
}
return res
}
# 2
func findDiagonalOrder(nums [][]int) []int {
maxValue := 0
m := make(map[int][]int)
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums[i]); j++ {
m[i+j] = append(m[i+j], nums[i][j])
if i+j > maxValue {
maxValue = i + j
}
}
}
res := make([]int, 0)
for i := 0; i <= maxValue; i++ {
for j := len(m[i]) - 1; j >= 0; j-- {
res = append(res, m[i][j])
}
}
return res
}
1432.改变一个整数能得到的最大差值(2)¶
题目
给你一个整数num。你可以对它进行如下步骤恰好 两次：
选择一个数字x (0<= x <= 9).
选择另一个数字y (0<= y <= 9)。数字y可以等于x。
将 num中所有出现 x的数位都用 y替换。
得到的新的整数 不能有前导 0 ，得到的新整数也 不能是 0。
令两次对 num的操作得到的结果分别为a和b。
请你返回a 和b的 最大差值 。
示例 1：输入：num = 555 输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888
示例 2：输入：num = 9 输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8
示例 3：输入：num = 123456 输出：820000
示例 4： 输入：num = 10000 输出：80000
示例 5：输入：num = 9288 输出：8700
提示：1 <= num <= 10^8
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 贪心 | O(log(n)) | O(log(n)) |
| 02 | 暴力法 | O(log(n)) | O(log(n)) |
func maxDiff(num int) int {
maxValue, minValue := num, num
str := strconv.Itoa(num)
for i := 0; i < len(str); i++ {
if str[i] < '9' {
maxValue, _ = strconv.Atoi(strings.ReplaceAll(str, string(str[i]), "9"))
break
}
}
if str[0] > '1' {
minValue, _ = strconv.Atoi(strings.ReplaceAll(str, string(str[0]), "1"))
} else {
for i := 1; i < len(str); i++ {
if str[i] > '1' && str[0] != str[i] {
minValue, _ = strconv.Atoi(strings.ReplaceAll(str, string(str[i]), "0"))
break
}
}
}
return maxValue - minValue
}
# 2
func maxDiff(num int) int {
maxValue, minValue := num, num
str := strconv.Itoa(num)
for x := 0; x < 10; x++ {
for y := 0; y < 10; y++ {
newStr := strings.ReplaceAll(str, string('0'+x), string('0'+y))
if newStr[0] == '0' {
continue
}
value, _ := strconv.Atoi(newStr)
if value > maxValue {
maxValue = value
}
if value < minValue {
minValue = value
}
}
}
return maxValue - minValue
}
1433.检查一个字符串是否可以打破另一个字符串(2)¶
题目
给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，
或者是否存在一个 s2 的排列可以打破 s1 的一个排列。
字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）
都有 x[i] >= y[i]（字典序意义下的顺序）。
示例 1：输入：s1 = "abc", s2 = "xya" 输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
示例 2：输入：s1 = "abe", s2 = "acd" 输出：false
解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，
s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。
然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。
示例 3：输入：s1 = "leetcodee", s2 = "interview" 输出：true
提示： s1.length == n
s2.length == n
1 <= n <= 10^5
所有字符串都只包含小写英文字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(n) |
| 02 | 计数排序 | O(n) | O(n) |
func checkIfCanBreak(s1 string, s2 string) bool {
arr1 := []byte(s1)
sort.Slice(arr1, func(i, j int) bool {
return arr1[i] < arr1[j]
})
arr2 := []byte(s2)
sort.Slice(arr2, func(i, j int) bool {
return arr2[i] < arr2[j]
})
s1 = string(arr1)
s2 = string(arr2)
return compare(s1, s2) || compare(s2, s1)
}
func compare(s1 string, s2 string) bool {
for i := 0; i < len(s1); i++ {
if s1[i] < s2[i] {
return false
}
}
return true
}
# 2
func checkIfCanBreak(s1 string, s2 string) bool {
arr1 := [26]int{}
arr2 := [26]int{}
for i := 0; i < len(s1); i++ {
arr1[int(s1[i]-'a')]++
arr2[int(s2[i]-'a')]++
}
a, b := 0, 0
totalA, totalB := 0, 0
for i := 0; i < 26; i++ {
totalA = totalA + arr1[i]
totalB = totalB + arr2[i]
if totalA >= totalB {
a++
}
if totalB >= totalA {
b++
}
}
return a == 26 || b == 26
}
1437.是否所有1都至少相隔k个元素(2)¶
题目
给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 True ；
否则，返回 False 。
示例 1：输入：nums = [1,0,0,0,1,0,0,1], k = 2 输出：true
解释：每个 1 都至少相隔 2 个元素。
示例 2：输入：nums = [1,0,0,1,0,1], k = 2 输出：false
解释：第二个 1 和第三个 1 之间只隔了 1 个元素。
示例 3：输入：nums = [1,1,1,1,1], k = 0 输出：true
示例 4：输入：nums = [0,1,0,1], k = 1 输出：true
提示：1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i] 的值为 0 或 1
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func kLengthApart(nums []int, k int) bool {
last := -(k + 1) // 兼容第0个元素是1
for i := 0; i < len(nums); i++ {
if nums[i] == 1 {
if i-last <= k {
return false
}
last = i
}
}
return true
}
# 2
func kLengthApart(nums []int, k int) bool {
last := -1
for i := 0; i < len(nums); i++ {
if nums[i] == 1 {
if last != -1 && i-last <= k {
return false
}
last = i
}
}
return true
}
1438.绝对差不超过限制的最长连续子数组(3)¶
题目
给你一个整数数组 nums ，和一个表示限制的整数 limit，
请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：输入：nums = [8,2,4,7], limit = 4 输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
示例 2：输入：nums = [10,1,2,4,7,2], limit = 5 输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3
提示：1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2) | O(1) |
| 02 | 滑动窗口-单调栈 | O(n) | O(n) |
| 03 | 树堆 | O(nlog(n)) | O(n) |
func longestSubarray(nums []int, limit int) int {
res := 0
for i := 0; i < len(nums); i++ {
maxValue, minValue := nums[i], nums[i]
for j := i; j < len(nums); j++ {
maxValue = max(maxValue, nums[j])
minValue = min(minValue, nums[j])
if maxValue-minValue <= limit {
res = max(res, j-i+1)
} else {
break
}
}
if res >= len(nums)-i {
break
}
}
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
}
# 2
func longestSubarray(nums []int, limit int) int {
res := 0
maxStack, minStack := make([]int, 0), make([]int, 0)
var i int
for j := 0; j < len(nums); j++ {
for len(minStack) > 0 && minStack[len(minStack)-1] > nums[j] {
minStack = minStack[:len(minStack)-1]
}
minStack = append(minStack, nums[j])
for len(maxStack) > 0 && maxStack[len(maxStack)-1] < nums[j] {
maxStack = maxStack[:len(maxStack)-1]
}
maxStack = append(maxStack, nums[j])
for maxStack[0]-minStack[0] > limit { // 移除左边
if nums[i] == maxStack[0] {
maxStack = maxStack[1:]
}
if nums[i] == minStack[0] {
minStack = minStack[1:]
}
i++
}
res = max(res, j-i+1)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
import (
"math/rand"
)
func longestSubarray(nums []int, limit int) int {
res := 0
t := &treap{}
var i int
for j := 0; j < len(nums); j++ {
t.insert(nums[j])
for t.max().key-t.min().key > limit {
t.delete(nums[i])
i++
}
res = max(res, j-i+1)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type Node struct {
ch [2]*Node
priority int
key int
cnt int
}
func (n *Node) cmp(b int) int {
switch {
case b < n.key:
return 0
case b > n.key:
return 1
default:
return -1
}
}
func (n *Node) rotate(b int) *Node {
target := n.ch[b^1]
n.ch[b^1] = target.ch[b]
target.ch[b] = n
return target
}
type treap struct {
root *Node
}
func (t *treap) ins(n *Node, key int) *Node {
if n == nil {
return &Node{
ch: [2]*Node{}, // 0左边，1右边
priority: rand.Int(),
key: key,
cnt: 1,
}
}
if b := n.cmp(key); b >= 0 {
n.ch[b] = t.ins(n.ch[b], key)
if n.ch[b].priority > n.priority {
n = n.rotate(b ^ 1)
}
} else {
n.cnt++
}
return n
}
func (t *treap) del(n *Node, key int) *Node {
if n == nil {
return nil
}
if b := n.cmp(key); b >= 0 {
n.ch[b] = t.del(n.ch[b], key)
} else {
if n.cnt > 1 {
n.cnt--
} else {
if n.ch[1] == nil {
return n.ch[0]
}
if n.ch[0] == nil {
return n.ch[1]
}
b = 0
if n.ch[0].priority > n.ch[1].priority {
b = 1
}
n = n.rotate(b)
n.ch[b] = t.del(n.ch[b], key)
}
}
return n
}
func (t *treap) insert(key int) {
t.root = t.ins(t.root, key)
}
func (t *treap) delete(key int) {
t.root = t.del(t.root, key)
}
func (t *treap) min() (min *Node) {
for temp := t.root; temp != nil; temp = temp.ch[0] {
min = temp
}
return min
}
func (t *treap) max() (max *Node) {
for temp := t.root; temp != nil; temp = temp.ch[1] {
max = temp
}
return max
}
1442.形成两个异或相等数组的三元组数目(3)¶
题目
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
示例 1：输入：arr = [2,3,1,6,7] 输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：输入：arr = [1,1,1,1,1] 输出：10
示例 3：输入：arr = [2,3] 输出：0
示例 4：输入：arr = [1,3,5,7,9] 输出：3
示例 5：输入：arr = [7,11,12,9,5,2,7,17,22] 输出：8
提示：
1 <= arr.length <= 300
1 <= arr[i] <= 10^8
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^3) | O(1) |
| 02 | 遍历 | O(n^2) | O(1) |
| 03 | 哈希辅助 | O(n) | O(n) |
func countTriplets(arr []int) int {
res := 0
for i := 1; i < len(arr); i++ {
arr[i] = arr[i] ^ arr[i-1]
}
for i := 0; i < len(arr)-1; i++ {
for j := i + 1; j < len(arr); j++ {
for k := j; k < len(arr); k++ {
var a, b int
if i == 0 {
a = arr[j-1]
} else {
a = arr[j-1] ^ arr[i-1]
}
b = arr[k] ^ arr[j-1]
if a == b {
res++
}
}
}
}
return res
}
#
// a[i]^...a[j-1]^a[j]^...a[k] = 0，则j可以取i+1、i+2、...、..k
func countTriplets(arr []int) int {
res := 0
for i := 0; i < len(arr); i++ {
temp := arr[i]
for k := i + 1; k < len(arr); k++ {
temp = temp ^ arr[k]
if temp == 0 {
res = res + k - i
}
}
}
return res
}
#
func countTriplets(arr []int) int {
res := 0
sumM := make(map[int]int)
countM := make(map[int]int)
countM[0] = 1
temp := 0
for i := 0; i < len(arr); i++ {
temp = temp ^ arr[i]
if countM[temp] > 0 {
// 相同异或结果，分别出现在下标[a,b,c,d]
// 则[a,d]有d-a-1个满足条件的
// sum = (d-a-1)+(d-b-1)+(d-c-1)
// ==> nd - [(a+1) + (b+1) + (c+1)]
// 同理得[a,b], [a,c]
res = res + i*countM[temp] - sumM[temp]
}
countM[temp]++
sumM[temp] = sumM[temp] + (i + 1)
}
return res
}
1443.收集树上所有苹果的最少时间(2)¶
题目
给你一棵有n个节点的无向树，节点编号为0到n-1，它们中有一些节点有苹果。
通过树上的一条边，需要花费 1 秒钟。
你从节点0出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。
无向树的边由edges给出，其中edges[i] = [fromi, toi]，表示有一条边连接from和toi 。
除此以外，还有一个布尔数组hasApple ，其中hasApple[i] = true代表节点i有一个苹果，
否则，节点i没有苹果。
示例 1：输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple = [false,false,true,false,true,true,false] 输出：8
解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 2：输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple = [false,false,true,false,false,true,false] 输出：6
解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 3：输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple = [false,false,false,false,false,false,false] 输出：0
提示：1 <= n <= 10^5
edges.length == n-1
edges[i].length == 2
0 <= fromi, toi <= n-1
fromi< toi
hasApple.length == n
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 深度优先搜索 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
func minTime(n int, edges [][]int, hasApple []bool) int {
arr := make([][]int, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
visited := make([]bool, n)
res, _ := dfs(arr, hasApple, visited, 0)
if res >= 2 {
return res - 2 // 遍历N个点，长度：2N-2
}
return 0
}
func dfs(arr [][]int, hasApple, visited []bool, index int) (int, bool) {
visited[index] = true
res := 0
has := false
if hasApple[index] == true {
has = true
}
for i := 0; i < len(arr[index]); i++ {
next := arr[index][i]
if visited[next] == true {
continue
}
total, isExist := dfs(arr, hasApple, visited, next)
if isExist {
has = true
res = res + total
}
}
if has == true {
return res + 2, true
}
return 0, false
}
# 2
func minTime(n int, edges [][]int, hasApple []bool) int {
ans := 0
m := make([]bool, n)
m[0] = true
for i := 0; i < len(edges); i++ {
from, to := edges[i][0], edges[i][1]
if m[from] {
m[to] = true
} else {
m[from] = true
// 改变数据
// [[0 2] [0 3] [1 2]] => [[0 2] [0 3] [2 1]]
edges[i][0], edges[i][1] = edges[i][1], edges[i][0]
}
}
for i := len(edges) - 1; i >= 0; i-- {
from, to := edges[i][0], edges[i][1]
if hasApple[to] {
hasApple[from] = true
ans += 2
}
}
return ans
}
1447.最简分数(2)¶
题目
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。
分数可以以 任意 顺序返回。
示例 1：输入：n = 2 输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
示例 2：输入：n = 3 输出：["1/2","1/3","2/3"]
示例 3：输入：n = 4 输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
示例 4：输入：n = 1 输出：[]
提示：1 <= n <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2log(n)) | O(n^2) |
| 02 | 哈希辅助 | O(n^3) | O(n^2) |
func simplifiedFractions(n int) []string {
res := make([]string, 0)
for i := 2; i <= n; i++ {
for j := 1; j < i; j++ {
if gcd(i, j) == 1 {
res = append(res, fmt.Sprintf("%d/%d", j, i))
}
}
}
return res
}
func gcd(a, b int) int {
if a%b == 0 {
return b
}
return gcd(b, a%b)
}
# 2
func simplifiedFractions(n int) []string {
res := make([]string, 0)
m := make(map[string]bool)
for i := 2; i <= n; i++ {
for j := 1; j < i; j++ {
str := fmt.Sprintf("%d/%d", j, i)
if _, ok := m[str]; ok{
continue
}
res = append(res, str)
for k := 1; i *k <= n; k++{
m[fmt.Sprintf("%d/%d", j*k, i*k)] = true
}
}
}
return res
}
1448.统计二叉树中好节点的数目(1)¶
题目
给你一棵根为root的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
示例 1：输入：root = [3,1,4,3,null,1,5] 输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。
示例 2：输入：root = [3,3,null,4,2] 输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
示例 3：输入：root = [1] 输出：1
解释：根节点是好节点。
提示：二叉树中节点数目范围是[1, 10^5]。
每个节点权值的范围是[-10^4, 10^4]。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
func goodNodes(root *TreeNode) int {
maxValue := math.MinInt32
return dfs(root, maxValue)
}
func dfs(root *TreeNode, maxValue int) int {
if root == nil {
return 0
}
if root.Val >= maxValue {
return dfs(root.Left, root.Val) + dfs(root.Right, root.Val) + 1
}
return dfs(root.Left, maxValue) + dfs(root.Right, maxValue)
}
1451.重新排列句子中的单词(1)¶
题目
「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :
句子的首字母大写
text 中的每个单词都用单个空格分隔。
请你重新排列 text 中的单词，使所有单词按其长度的升序排列。
如果两个单词的长度相同，则保留其在原句子中的相对顺序。
请同样按上述格式返回新的句子。
示例 1：输入：text = "Leetcode is cool" 输出："Is cool leetcode"
解释：句子中共有 3 个单词，长度为 8 的 "Leetcode" ，长度为 2 的 "is" 以及长度为 4 的 "cool" 。
输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。
示例 2：输入：text = "Keep calm and code on" 输出："On and keep calm code"
解释：输出的排序情况如下：
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母，因为存在长度相同的其他单词，所以它们之间需要保留在原句子中的相对顺序。
"calm" 4 个字母。
"code" 4 个字母。
示例 3：输入：text = "To be or not to be" 输出："To be or to be not"
提示： text 以大写字母开头，然后包含若干小写字母以及单词间的单个空格。
1 <= text.length <= 10^5
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序 | O(nlog(n)) | O(n) |
func arrangeWords(text string) string {
text = strings.ToLower(text)
arr := strings.Fields(text)
sort.SliceStable(arr, func(i, j int) bool {
return len(arr[i]) < len(arr[j])
})
arr[0] = strings.Title(arr[0])
return strings.Join(arr, " ")
}
1452.收藏清单(1)¶
题目
给你一个数组 favoriteCompanies ，
其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
示例 1：输入：favoriteCompanies = [["leetcode","google","facebook"],
["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出：[0,1,4]
解释：favoriteCompanies[2]=["google","facebook"] 是
favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=
["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。
示例 2：输入：favoriteCompanies = [["leetcode","google","facebook"],
["leetcode","amazon"],["facebook","google"]]
输出：[0,1]
解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。
示例 3：输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
输出：[0,1,2,3]
提示：1 <=favoriteCompanies.length <= 100
1 <=favoriteCompanies[i].length <= 500
1 <=favoriteCompanies[i][j].length <= 20
favoriteCompanies[i] 中的所有字符串 各不相同 。
用户收藏的公司清单也 各不相同 ，
也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
所有字符串仅包含小写英文字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 自定义排序 | O(n^3) | O(n^2) |
type Node struct {
index int
str []string
}
func peopleIndexes(favoriteCompanies [][]string) []int {
n := len(favoriteCompanies)
arr := make([]Node, 0)
for i := 0; i < len(favoriteCompanies); i++ {
arr = append(arr, Node{
index: i,
str: favoriteCompanies[i],
})
}
sort.Slice(arr, func(i, j int) bool {
return len(arr[i].str) < len(arr[j].str)
})
res := make([]int, 0)
for i := 0; i < n; i++ {
flag := true
for j := i + 1; j < n; j++ {
if judge(arr[i].str, arr[j].str) == true {
flag = false
break
}
}
if flag == true {
res = append(res, arr[i].index)
}
}
sort.Ints(res)
return res
}
func judge(a, b []string) bool {
m := make(map[string]bool)
for i := 0; i < len(a); i++ {
m[a[i]] = true
}
for i := 0; i < len(b); i++ {
if _, ok := m[b[i]]; ok {
delete(m, b[i])
}
}
return len(m) == 0
}
1456.定长子串中元音的最大数目(2)¶
题目
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：输入：s = "abciiidef", k = 3 输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：输入：s = "aeiou", k = 2 输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：输入：s = "leetcode", k = 3 输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：输入：s = "rhythms", k = 4 输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：输入：s = "tryhard", k = 4 输出：1
提示：1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口 | O(n) | O(1) |
| 02 | 前缀和 | O(n) | O(n) |
func maxVowels(s string, k int) int {
res := 0
total := 0
for i := 0; i < len(s); i++ {
if isVowel(s[i]) == true {
total++
}
if i >= k {
if isVowel(s[i-k]) == true {
total--
}
}
res = max(res, total)
}
return res
}
func isVowel(b byte) bool {
return b == 'a' || b == 'e' ||
b == 'i' || b == 'o' || b == 'u'
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxVowels(s string, k int) int {
res := 0
total := 0
arr := make([]int, len(s)+1)
for i := 0; i < len(s); i++ {
if isVowel(s[i]) == true {
total++
}
arr[i+1] = total
if i >= k-1 {
res = max(res, arr[i+1]-arr[i-k+1])
}
}
return res
}
func isVowel(b byte) bool {
return b == 'a' || b == 'e' ||
b == 'i' || b == 'o' || b == 'u'
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1457.二叉树中的伪回文路径(3)¶
题目
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，
当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中伪回文路径的数目。
示例 1：输入：root = [2,3,1,3,1,null,1] 输出：2
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，
绿色路径 [2,1,1] 和路径 [2,3,1] 。
在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，
绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
示例 2：输入：root = [2,1,1,1,3,null,null,null,null,null,1] 输出：1
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：
绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。
示例 3：输入：root = [9] 输出：1
提示：给定二叉树的节点数目在1到10^5之间。
节点值在1 到9之间。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(1) |
| 02 | 递归 | O(n) | O(1) |
| 03 | 递归 | O(n) | O(1) |
var res int
func pseudoPalindromicPaths(root *TreeNode) int {
res = 0
dfs(root, [10]int{})
return res
}
func dfs(root *TreeNode, arr [10]int) {
arr[root.Val]++
if root.Left == nil && root.Right == nil {
count := 0
for i := 1; i <= 9; i++ {
if arr[i]%2 == 1 {
count++
}
}
if count <= 1 {
res++
}
return
}
if root.Left != nil {
dfs(root.Left, arr)
}
if root.Right != nil {
dfs(root.Right, arr)
}
}
# 2
var res int
func pseudoPalindromicPaths(root *TreeNode) int {
res = 0
dfs(root, make([]int, 10))
return res
}
func dfs(root *TreeNode, arr []int) {
if root == nil {
return
}
arr[root.Val]++
if root.Left == nil && root.Right == nil {
count := 0
for i := 1; i <= 9; i++ {
if arr[i]%2 == 1 {
count++
}
}
if count <= 1 {
res++
}
return
}
tempLeft := make([]int, 10)
copy(tempLeft, arr)
dfs(root.Left, tempLeft)
tempRight := make([]int, 10)
copy(tempRight, arr)
dfs(root.Right, tempRight)
}
# 3
var res int
func pseudoPalindromicPaths(root *TreeNode) int {
res = 0
dfs(root, 0)
return res
}
func dfs(root *TreeNode, value int) {
if root == nil {
return
}
temp := value ^ (1 << root.Val)
if root.Left == nil && root.Right == nil {
if temp == 0 || (temp&(temp-1)) == 0 {
res++
}
return
}
dfs(root.Left, temp)
dfs(root.Right, temp)
}
1461.检查一个字符串是否包含所有长度为K的二进制子串(2)¶
题目
给你一个二进制字符串s和一个整数k。
如果所有长度为 k的二进制字符串都是 s的子串，请返回 True ，否则请返回 False 。
示例 1：输入：s = "00110110", k = 2 输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。
它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
示例 2：输入：s = "00110", k = 2 输出：true
示例 3：输入：s = "0110", k = 1 输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例 4：输入：s = "0110", k = 2 输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
示例 5：输入：s = "0000000001011100", k = 4 输出：false
提示：1 <= s.length <= 5 * 10^5
s 中只含 0 和 1 。
1 <= k <= 20
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(2^n) |
| 02 | 数组辅助 | O(n) | O(2^n) |
func hasAllCodes(s string, k int) bool {
m := make(map[string]bool)
for i := 0; i <= len(s)-k; i++ {
m[s[i:i+k]] = true
}
return len(m) == 1<<k
}
# 2
func hasAllCodes(s string, k int) bool {
length := 1 << k
arr := make([]bool, length)
cur := 0
for i := 0; i < len(s); i++ {
num := int(s[i] - '0')
cur = cur<<1 + num
if i >= k-1 {
cur = cur & (length - 1)
arr[cur] = true
}
}
for i := 0; i < len(arr); i++ {
if arr[i] == false {
return false
}
}
return true
}
1462.课程表IV(2)¶
题目
你总共需要上 n门课，课程编号依次为 0到 n-1。
有的课会有直接的先修课程，比如如果想上课程0 ，你必须先上课程 1 ，那么会以 [1,0]数对的形式给出先修课程数对。
给你课程总数 n和一个直接先修课程数对列表prerequisite 和一个查询对列表queries。
对于每个查询对 queries[i]，请判断queries[i][0]是否是queries[i][1]的先修课程。
请返回一个布尔值列表，列表中每个元素依次分别对应 queries每个查询对的判断结果。
注意：如果课程a是课程b的先修课程且课程b是课程c的先修课程，那么课程a也是课程c的先修课程。
示例 1：输入：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] 输出：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。
示例 2：输入：n = 2, prerequisites = [], queries = [[1,0],[0,1]] 输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。
示例 3：输入：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] 输出：[true,true]
示例 4：输入：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]] 输出：[false,true]
示例 5：输入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输出：[true,false,true,false]
提示：2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
先修课程图中没有环。
先修课程图中没有重复的边。
1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 深度优先搜索 | O(n^2) | O(n) |
| 02 | Floyd | O(n^3) | O(n) |
var arr []map[int]bool
var m map[string]bool
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
res := make([]bool, len(queries))
m = make(map[string]bool)
arr = make([]map[int]bool, numCourses)
for i := 0; i < len(prerequisites); i++ {
a, b := prerequisites[i][0], prerequisites[i][1]
if arr[a] == nil {
arr[a] = make(map[int]bool)
}
arr[a][b] = true // a=>b
}
for i := 0; i < len(queries); i++ {
a, b := queries[i][0], queries[i][1]
res[i] = dfs(a, b) // a=>b
}
return res
}
func dfs(i, target int) bool {
status := fmt.Sprintf("%d,%d", i, target)
if value, ok := m[status]; ok {
return value
}
res := false
if arr[i][target] == true {
res = true
} else {
for k := range arr[i] {
if dfs(k, target) == true {
res = true
break
}
}
}
m[status] = res
return res
}
# 2
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
res := make([]bool, len(queries))
m := make(map[int]map[int]bool)
for i := 0; i < numCourses; i++ {
m[i] = make(map[int]bool)
}
for i := 0; i < len(prerequisites); i++ {
a, b := prerequisites[i][0], prerequisites[i][1]
m[a][b] = true // a=>b
}
for k := 0; k < numCourses; k++ {
for i := 0; i < numCourses; i++ {
for j := 0; j < numCourses; j++ {
// ik + kj =>ij
if m[i][k] == true && m[k][j] == true {
m[i][j] = true
}
}
}
}
for i := 0; i < len(queries); i++ {
a, b := queries[i][0], queries[i][1]
res[i] = m[a][b]
}
return res
}
1465.切割后面积最大的蛋糕(1)¶
题目
矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，
其中 horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离，
类似地， verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，
请你找出 面积最大 的那份蛋糕，并返回其 面积 。
由于答案可能是一个很大的数字，因此需要将结果对 10^9 + 7 取余后返回。
示例 1：输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3] 输出：4
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。
示例 2：输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1] 输出：6
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色和黄色的两份蛋糕面积最大。
示例 3：输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3] 输出：9
提示：2 <= h,w <= 10^9
1 <=horizontalCuts.length <min(h, 10^5)
1 <=verticalCuts.length < min(w, 10^5)
1 <=horizontalCuts[i] < h
1 <=verticalCuts[i] < w
题目数据保证 horizontalCuts 中的所有元素各不相同
题目数据保证 verticalCuts中的所有元素各不相同
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序 | O(nlog(n)) | O(n) |
func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
hArr := append(horizontalCuts, h)
wArr := append(verticalCuts, w)
sort.Ints(hArr)
sort.Ints(wArr)
maxHeight := hArr[0]
maxWeight := wArr[0]
for i := 1; i < len(hArr); i++ {
if hArr[i]-hArr[i-1] > maxHeight {
maxHeight = hArr[i] - hArr[i-1]
}
}
for i := 1; i < len(wArr); i++ {
if wArr[i]-wArr[i-1] > maxWeight {
maxWeight = wArr[i] - wArr[i-1]
}
}
return maxHeight * maxWeight % 1000000007
}
1466.重新规划路线(2)¶
题目
n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。
因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。
去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。
路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
示例 1：输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] 输出：3
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
示例 2：输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 输出：2
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
示例 3：输入：n = 3, connections = [[1,0],[2,0]] 输出：0
提示：2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i][0], connections[i][1] <= n-1
connections[i][0] != connections[i][1]
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 广度优先搜索 | O(n) | O(n) |
| 02 | 深度优先搜索 | O(n) | O(n) |
func minReorder(n int, connections [][]int) int {
m := make(map[int]map[int]int)
for i := 0; i < len(connections); i++ {
a, b := connections[i][0], connections[i][1]
if _, ok := m[a]; ok == false {
m[a] = make(map[int]int)
}
if _, ok := m[b]; ok == false {
m[b] = make(map[int]int)
}
m[a][b] = 1 // a->b
m[b][a] = -1 // b->a
}
res := 0
visited := make(map[int]bool)
visited[0] = true
queue := make([]int, 0)
queue = append(queue, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for k, v := range m[node] {
if visited[k] == true {
continue
}
visited[k] = true
if v == 1 {
res++
}
queue = append(queue, k)
}
}
return res
}
# 2
var res int
var m map[int]map[int]int
func minReorder(n int, connections [][]int) int {
m = make(map[int]map[int]int)
for i := 0; i < len(connections); i++ {
a, b := connections[i][0], connections[i][1]
if _, ok := m[a]; ok == false {
m[a] = make(map[int]int)
}
if _, ok := m[b]; ok == false {
m[b] = make(map[int]int)
}
m[a][b] = 1 // a->b
m[b][a] = -1 // b->a
}
res = 0
visited := make(map[int]bool)
visited[0] = true
dfs(0, visited)
return res
}
func dfs(start int, visited map[int]bool) {
for k, v := range m[start] {
if visited[k] == true {
continue
}
visited[k] = true
if v == 1 {
res++
}
dfs(k, visited)
}
}
1471.数组中的k个最强值(2)¶
题目
给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
|arr[i] - m| > |arr[j]- m|
|arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
中位数 是一个有序整数列表中处于中间位置的值。
形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2) 的元素。
例如 arr =[6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，
数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
例如 arr =[-7, 22, 17, 3]，n = 4：数组排序后得到arr = [-7, 3, 17, 22] ，
数组的中间位置为m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。
示例 1：输入：arr = [1,2,3,4,5], k = 2 输出：[5,1]
解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。
最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。
注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。
示例 2：输入：arr = [1,1,3,5,5], k = 2 输出：[5,5]
解释：中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。
示例 3：输入：arr = [6,7,11,7,6,8], k = 5 输出：[11,8,6,6,7]
解释：中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。
[11,8,6,6,7] 的任何排列都是正确答案。
示例 4：输入：arr = [6,-3,7,2,11], k = 3 输出：[-3,11,2]
示例 5：输入：arr = [-7,22,17,3], k = 2 输出：[22,17]
提示：1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 自定义排序 | O(nlog(n)) | O(1) |
| 02 | 双指针 | O(nlog(n)) | O(n) |
func getStrongest(arr []int, k int) []int {
sort.Ints(arr)
mid := arr[(len(arr)-1)/2]
sort.Slice(arr, func(i, j int) bool {
if abs(arr[i]-mid) == abs(arr[j]-mid) {
return arr[i] > arr[j]
}
return abs(arr[i]-mid) > abs(arr[j]-mid)
})
return arr[:k]
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func getStrongest(arr []int, k int) []int {
sort.Ints(arr)
mid := arr[(len(arr)-1)/2]
res := make([]int, 0)
left, right := 0, len(arr)-1
for k > 0 {
if arr[right]-mid >= mid-arr[left] {
res = append(res, arr[right])
right--
} else {
res = append(res, arr[left])
left++
}
k--
}
return res
}
1472.设计浏览器历史记录(1)¶
题目
你有一个只支持单个标签页的 浏览器，最开始你浏览的网页是homepage，
你可以访问其他的网站url，也可以在浏览历史中后退steps步或前进steps步。
请你实现BrowserHistory 类：
BrowserHistory(string homepage)，用homepage初始化浏览器类。
void visit(string url)从当前页跳转访问 url 对应的页面。
执行此操作会把浏览历史前进的记录全部删除。
string back(int steps)在浏览历史中后退steps步。
如果你只能在浏览历史中后退至多x 步且steps > x，那么你只后退x步。
请返回后退 至多 steps步以后的url。
string forward(int steps)在浏览历史中前进steps步。
如果你只能在浏览历史中前进至多x步且steps > x，那么你只前进 x步。
请返回前进至多steps步以后的 url。
示例：输入：["BrowserHistory","visit","visit","visit","back","back","forward",
"visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],
["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：[null,null,null,null,"facebook.com","google.com","facebook.com",null,
"linkedin.com","google.com","leetcode.com"]
解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com"); // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com"); // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");
// 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);
// 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);
// 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);
// 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");
// 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);
// 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);
// 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);
// 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"
提示：1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage 和url都只包含'.' 或者小写英文字母。
最多调用5000次visit，back和forward函数。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 数组 | O(1) | O(n) |
type BrowserHistory struct {
arr []string
index int
}
func Constructor(homepage string) BrowserHistory {
return BrowserHistory{
arr: []string{homepage},
index: 0,
}
}
func (this *BrowserHistory) Visit(url string) {
length := len(this.arr)
if this.index == length-1 {
this.arr = append(this.arr, url)
} else if this.index < length-1 {
this.arr = this.arr[:this.index+1]
this.arr = append(this.arr, url)
}
this.index++
}
func (this *BrowserHistory) Back(steps int) string {
if steps > this.index {
this.index = 0
return this.arr[0]
}
this.index = this.index - steps
return this.arr[this.index]
}
func (this *BrowserHistory) Forward(steps int) string {
length := len(this.arr)
if this.index == length-1 {
} else if this.index+steps > length-1 {
this.index = length - 1
} else {
this.index = this.index + steps
}
return this.arr[this.index]
}
1476.子矩形查询(2)¶
题目
请你实现一个类SubrectangleQueries，
它的构造函数的参数是一个 rows x cols的矩形（这里用整数矩阵表示），并支持以下两种操作：
1.updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
用newValue更新以(row1,col1)为左上角且以(row2,col2)为右下角的子矩形。
2.getValue(int row, int col)
返回矩形中坐标 (row,col) 的当前值。
示例 1：输入：["SubrectangleQueries","getValue","updateSubrectangle",
"getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
输出：[null,1,null,5,5,null,10,5]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);
// 初始的 (4x3) 矩形如下：
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5
subrectangleQueries.getValue(0, 2); // 返回 5
subrectangleQueries.getValue(3, 1); // 返回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 10 10 10
subrectangleQueries.getValue(3, 1); // 返回 10
subrectangleQueries.getValue(0, 2); // 返回 5
示例 2：输入：["SubrectangleQueries","getValue","updateSubrectangle","getValue",
"getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
输出：[null,1,null,100,100,null,20]
解释：SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // 返回 100
subrectangleQueries.getValue(2, 2); // 返回 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // 返回 20
提示：最多有500次updateSubrectangle 和getValue操作。
1 <= rows, cols <= 100
rows ==rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2) | O(n^2) |
| 02 | 查询更改 | O(n) | O(n^2) |
type SubrectangleQueries struct {
arr [][]int
}
func Constructor(rectangle [][]int) SubrectangleQueries {
return SubrectangleQueries{arr: rectangle}
}
func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int) {
for i := row1; i <= row2; i++ {
for j := col1; j <= col2; j++ {
this.arr[i][j] = newValue
}
}
}
func (this *SubrectangleQueries) GetValue(row int, col int) int {
return this.arr[row][col]
}
# 2
type SubrectangleQueries struct {
arr [][]int
record [][]int // 更改记录
}
func Constructor(rectangle [][]int) SubrectangleQueries {
return SubrectangleQueries{arr: rectangle}
}
func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int) {
this.record = append(this.record, []int{row1, col1, row2, col2, newValue})
}
func (this *SubrectangleQueries) GetValue(row int, col int) int {
for i := len(this.record) - 1; i >= 0; i-- {
row1, col1 := this.record[i][0], this.record[i][1]
row2, col2 := this.record[i][2], this.record[i][3]
newValue := this.record[i][4]
if row1 <= row && row <= row2 &&
col1 <= col && col <= col2 {
return newValue
}
}
return this.arr[row][col]
}
1477.找两个和为目标值且不重叠的子数组(1)¶
题目
给你一个整数数组arr 和一个整数值target。
请你在 arr中找 两个互不重叠的子数组且它们的和都等于target。
可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。
请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1。
示例 1：输入：arr = [3,2,2,4,3], target = 3 输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
示例 2：输入：arr = [7,3,4,7], target = 7 输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），
但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。
示例 3：输入：arr = [4,3,2,6,2,3,4], target = 6 输出：-1
解释：我们只有一个和为 6 的子数组。
示例 4：输入：arr = [5,5,4,4,5], target = 3 输出：-1
解释：我们无法找到和为 3 的子数组。
示例 5：输入：arr = [3,1,1,1,5,1,2,1], target = 3 输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。
提示：1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口+双指针 | O(n) | O(n) |
func minSumOfLengths(arr []int, target int) int {
res := math.MaxInt32
n := len(arr)
sum := 0
left := 0
temp := make([]int, n) // 保存每个位置之前的最小值
for i := 0; i < n; i++ {
temp[i] = math.MaxInt32 // 默认为最大值
}
for right := 0; right < n; right++ {
sum = sum + arr[right]
for sum > target {
sum = sum - arr[left]
left++
}
if right >= 1 {
temp[right] = temp[right-1] // 默认同之前最小值
}
if sum == target { // 找到目标值
temp[right] = min(temp[right], right-left+1) // 更新最小值
if left >= 1 && temp[left-1] != math.MaxInt32 {
res = min(res, temp[left-1]+right-left+1) // 取left之前(即left-1)的最小值，加上当前长度
}
}
}
if res == math.MaxInt32 {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1481.不同整数的最少数目(1)¶
题目
给你一个整数数组 arr 和一个整数 k 。
现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
示例 1：输入：arr = [5,5,4], k = 1 输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：输入：arr = [4,3,1,1,3,3,2], k = 3 输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
提示：1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希排序 | O(nlog(n)) | O(n) |
func findLeastNumOfUniqueInts(arr []int, k int) int {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
m[arr[i]]++
}
temp := make([]int, 0)
for _, v := range m {
temp = append(temp, v)
}
sort.Ints(temp)
res := len(temp)
for i := 0; i < len(temp); i++ {
if k >= temp[i] {
res--
k = k - temp[i]
} else {
break
}
}
return res
}
1482.制作m束花所需的最少天数(1)¶
题目
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：输入：bloomDay = [1,10,3,10,2], m = 3, k = 1 输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3
示例 2：输入：bloomDay = [1,10,3,10,2], m = 3, k = 2 输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。
而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
示例 3：输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。
示例 4：输入：bloomDay = [1000000000,1000000000], m = 1, k = 1 输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束
示例 5：输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2 输出：9
提示：bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 二分查找 | O(nlog(n)) | O(1) |
func minDays(bloomDay []int, m int, k int) int {
if m*k > len(bloomDay) {
return -1
}
minValue, maxValue := bloomDay[0], bloomDay[0]
for i := 1; i < len(bloomDay); i++ {
if bloomDay[i] > maxValue {
maxValue = bloomDay[i]
}
if bloomDay[i] < minValue {
minValue = bloomDay[i]
}
}
left, right := minValue, maxValue
for left < right {
mid := left + (right-left)/2
count := judge(bloomDay, mid, k)
if count >= m {
right = mid
} else {
left = mid + 1
}
}
return left
}
func judge(bloomDay []int, mid int, k int) int {
total := 0
count := 0
for i := 0; i < len(bloomDay); i++ {
if bloomDay[i] <= mid {
total++
} else {
total = 0
}
if total == k {
count++
total = 0
}
}
return count
}
1487.保证文件名唯一(2)¶
题目
给你一个长度为 n 的字符串数组 names 。
你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。
由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，
系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。
返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。
示例 1：
输入：names = ["pes","fifa","gta","pes(2019)"]
输出：["pes","fifa","gta","pes(2019)"]
解释：文件系统将会这样创建文件名：
"pes" --> 之前未分配，仍为 "pes"
"fifa" --> 之前未分配，仍为 "fifa"
"gta" --> 之前未分配，仍为 "gta"
"pes(2019)" --> 之前未分配，仍为 "pes(2019)"
示例 2：
输入：names = ["gta","gta(1)","gta","avalon"]
输出：["gta","gta(1)","gta(2)","avalon"]
解释：文件系统将会这样创建文件名：
"gta" --> 之前未分配，仍为 "gta"
"gta(1)" --> 之前未分配，仍为 "gta(1)"
"gta" --> 文件名被占用，系统为该名称添加后缀 (k)，由于 "gta(1)" 也被占用，所以 k = 2 。
实际创建的文件名为 "gta(2)" 。
"avalon" --> 之前未分配，仍为 "avalon"
示例 3：
输入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释：当创建最后一个文件夹时，最小的正有效 k 为 4 ，文件名变为 "onepiece(4)"。
示例 4：
输入：names = ["wano","wano","wano","wano"]
输出：["wano","wano(1)","wano(2)","wano(3)"]
解释：每次创建文件夹 "wano" 时，只需增加后缀中 k 的值即可。
示例 5：
输入：names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。
提示：
1 <= names.length <= 5 * 10^4
1 <= names[i].length <= 20
names[i] 由小写英文字母、数字和/或圆括号组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助-递归 | O(n) | O(n) |
| 02 | 哈希辅助 | O(n) | O(n) |
func getFolderNames(names []string) []string {
m := make(map[string]int)
for i, name := range names {
if value, ok := m[name]; ok {
names[i] = getName(m, name, value)
m[names[i]] = 1
} else {
m[name] = 1
}
}
return names
}
func getName(m map[string]int, name string, n int) string {
newName := name + fmt.Sprintf("(%d)", n)
if _, ok := m[newName]; ok {
return getName(m, name, n+1)
}
m[name] = n + 1
return newName
}
#
func getFolderNames(names []string) []string {
m := make(map[string]int)
res := make([]string, 0)
for _, name := range names {
if value, ok := m[name]; ok {
for {
newName := name + fmt.Sprintf("(%d)", value)
if _, ok2 := m[newName]; ok2 {
value++
continue
}
res = append(res, newName)
m[newName] = 1
m[name] = value
break
}
} else {
res = append(res, name)
m[name] = 1
}
}
return res
}
1488.避免洪水泛滥¶
题目¶
你的国家有无数个湖泊，所有湖泊一开始都是空的。
当第 n个湖泊下雨的时候，如果第 n个湖泊是空的，那么它就会装满水，否则这个湖泊会发生洪水。
你的目标是避免任意一个湖泊发生洪水。
给你一个整数数组rains，其中：
rains[i] > 0表示第 i天时，第 rains[i]个湖泊会下雨。
rains[i] == 0表示第 i天没有湖泊会下雨，你可以选择 一个湖泊并 抽干这个湖泊的水。
请返回一个数组ans，满足：ans.length == rains.length
如果rains[i] > 0 ，那么ans[i] == -1。
如果rains[i] == 0，ans[i]是你第i天选择抽干的湖泊。
如果有多种可行解，请返回它们中的 任意一个。如果没办法阻止洪水，请返回一个 空的数组。
请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。
但如果你选择抽干一个空的湖泊，那么将无事发生（详情请看示例 4）。
示例 1：输入：rains = [1,2,3,4] 输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。
示例 2：输入：rains = [1,2,0,0,2,1] 输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。
示例 3：输入：rains = [1,2,0,1,2] 输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。
示例 4：输入：rains = [69,0,0,0,69] 输出：[-1,69,1,1,-1]
解释：任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解，
其中 1 <= x,y <= 10^9
示例 5：输入：rains = [10,20,20] 输出：[]
解释：由于湖泊 20 会连续下 2 天的雨，所以没有没有办法阻止洪水。
提示：1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
1492.n的第k个因子(2)¶
题目
给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。
考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。
示例 1：输入：n = 12, k = 3输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。
示例 2：输入：n = 7, k = 2 输出：7
解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。
示例 3：输入：n = 4, k = 4 输出：-1
解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。
示例 4：输入：n = 1, k = 1 输出：1
解释：因子列表包括 [1] ，第 1 个因子为 1 。
示例 5：输入：n = 1000, k = 3 输出：4
解释：因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。
提示：
1 <= k <= n <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n^1/2) | O(1) |
func kthFactor(n int, k int) int {
count := 0
for i := 1; i <= n; i++ {
if n%i == 0 {
count++
if count == k {
return i
}
}
}
return -1
}
#
func kthFactor(n int, k int) int {
count := 0
i := 1
for i = 1; i*i <= n; i++ {
if n%i == 0 {
count++
if count == k {
return i
}
}
}
i--
if i*i == n {
i--
}
for ; i > 0; i-- {
if n%i == 0 {
count++
if count == k {
return n / i
}
}
}
return -1
}
1493.删掉一个元素以后全为 1 的最长子数组(3)¶
题目
给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。
提示 1：输入：nums = [1,1,0,1] 输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。
示例 2：输入：nums = [0,1,1,1,0,1,1,0,1] 输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。
示例 3：输入：nums = [1,1,1] 输出：2
解释：你必须要删除一个元素。
示例 4：输入：nums = [1,1,0,0,1,1,1,0,1] 输出：4
示例 5：输入：nums = [0,0,0] 输出：0
提示：
1 <= nums.length <= 10^5
nums[i] 要么是 0 要么是 1 。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 数组辅助 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(1) |
| 03 | 数组辅助 | O(n) | O(n) |
func longestSubarray(nums []int) int {
n := len(nums)
pre := make([]int, n)
suf := make([]int, n)
pre[0] = nums[0]
for i := 1; i < n; i++ {
if nums[i] == 1 {
pre[i] = pre[i-1] + 1
} else {
pre[i] = 0
}
}
suf[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
if nums[i] == 1 {
suf[i] = suf[i+1] + 1
} else {
suf[i] = 0
}
}
res := 0
for i := 0; i < n; i++ {
var p, s int
if i == 0 {
p = 0
} else {
p = pre[i-1]
}
if i == n-1 {
s = 0
} else {
s = suf[i+1]
}
if p+s > res {
res = p + s
}
}
return res
}
#
func longestSubarray(nums []int) int {
res := 0
p, q := 0, 0 // q=>中间有一个“非1”的和, p=>连续1的和
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
q = p
p = 0
} else {
p++
q++
}
if q > res {
res = q
}
}
if res == len(nums) {
return res - 1
}
return res
}
#
func longestSubarray(nums []int) int {
arr := make([]int, 0)
count := 0
for _, v := range nums {
if v == 0 {
arr = append(arr, count)
count = 0
continue
}
count++
}
arr = append(arr, count)
if len(arr) == 1 {
return arr[0] - 1
}
res := 0
for i := 0; i < len(arr)-1; i++ {
if arr[i]+arr[i+1] > res {
res = arr[i] + arr[i+1]
}
}
return res
}
1497.检查数组对是否可以被k整除(2)¶
题目
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
示例 1：输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5 输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
示例 2：输入：arr = [1,2,3,4,5,6], k = 7 输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
示例 3：输入：arr = [1,2,3,4,5,6], k = 10 输出：false
解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
示例 4：输入：arr = [-10,10], k = 2 输出：true
示例 5：输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3 输出：true
提示：arr.length == n
1 <= n <= 10^5
n 为偶数
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
| 02 | 数组辅助 | O(n) | O(n) |
func canArrange(arr []int, k int) bool {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
value := ((arr[i] % k) + k) % k
m[value]++
}
for key, value := range m {
if key == 0 && value%2 != 0 {
return false
}
target := (k - key) % k // 避免key=0，k-0=k的情况
if m[target] != value {
return false
}
}
return true
}
# 2
func canArrange(arr []int, k int) bool {
temp := make([]int, k)
for i := 0; i < len(arr); i++ {
value := ((arr[i] % k) + k) % k
temp[value]++
}
for i := 1; i < k; i++ {
if temp[i] != temp[k-i] {
return false
}
}
return temp[0]%2 == 0
}
1498.满足条件的子序列数目(2)¶
题目
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
示例 1：输入：nums = [3,5,6,7], target = 9 输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
示例 2：输入：nums = [3,3,6,8], target = 10 输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
示例 3：输入：nums = [2,3,3,4,6,7], target = 12 输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）
示例 4：输入：nums = [5,2,4,1,7,6,8], target = 16 输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127
提示：1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序双指针 | O(nlog(n)) | O(n) |
| 02 | 排序二分查找 | O(nlog(n)) | O(n) |
func numSubseq(nums []int, target int) int {
sort.Ints(nums)
// 计算长度为length满足条件的非空子序列的数目
// 如1、2、3、4，长度为4，1必选，其他3个数可选可不选，组合数：2^3=8
m := make(map[int]int)
m[1] = 1
for i := 2; i <= len(nums); i++ {
m[i] = (m[i-1] * 2) % 1000000007
}
res := 0
left, right := 0, len(nums)-1
for left <= right {
if nums[left]+nums[right] <= target {
length := right - left + 1
res = res + m[length]
left++
} else {
right--
}
}
return res % 1000000007
}
# 2
func numSubseq(nums []int, target int) int {
sort.Ints(nums)
// 计算长度为length满足条件的非空子序列的数目
// 如1、2、3、4，长度为4，1必选，其他3个数可选可不选，组合数：2^3=8
m := make(map[int]int)
m[1] = 1
for i := 2; i <= len(nums); i++ {
m[i] = (m[i-1] * 2) % 1000000007
}
res := 0
for i := 0; i < len(nums); i++ {
left, right := i, len(nums)
for left+1 < right {
mid := left + (right-left)/2
if nums[mid]+nums[i] <= target {
left = mid
} else {
right = mid
}
}
if nums[left]+nums[i] <= target {
length := left - i + 1
res = res + m[length]
}
}
return res % 1000000007
}
1401-1500-Hard¶
1402.做菜顺序(3)¶
题目
一个厨师收集了他n道菜的满意程度satisfaction，这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，
也就是time[i]*satisfaction[i]。
请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
你可以按任意顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。
示例 1：输入：satisfaction = [-1,-8,0,5,-9] 输出：14
解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。
每道菜都需要花费 1 单位时间完成。
示例 2：输入：satisfaction = [4,3,2] 输出：20
解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)
示例 3：输入：satisfaction = [-1,-4,-5] 输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。
示例 4：输入：satisfaction = [-2,5,-1,0,3,-3] 输出：35
提示：n == satisfaction.length
1 <= n <= 500
-10^3 <=satisfaction[i] <= 10^3
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(nlog(n)) | O(1) |
| 02 | 遍历 | O(nlog(n)) | O(1) |
| 03 | 动态规划 | O(nlog(n)) | O(n) |
func maxSatisfaction(satisfaction []int) int {
res := 0
sort.Slice(satisfaction, func(i, j int) bool {
return satisfaction[i] > satisfaction[j]
})
sum := 0
for i := 0; i < len(satisfaction); i++ {
if sum+satisfaction[i] <= 0 {
break
}
sum = sum + satisfaction[i]
res = res + sum // 每多遍历1次，前后相邻的2个数，较大数相对较小数多+1次
}
return res
}
# 2
func maxSatisfaction(satisfaction []int) int {
res := 0
sort.Slice(satisfaction, func(i, j int) bool {
return satisfaction[i] > satisfaction[j]
})
sum := 0
temp := 0
for i := 0; i < len(satisfaction); i++ {
sum = sum + satisfaction[i]
temp = temp + sum // 每多遍历1次，前后相邻的2个数，较大数相对较小数多+1次
if temp > res {
res = temp
}
}
return res
}
# 3
func maxSatisfaction(satisfaction []int) int {
sort.Slice(satisfaction, func(i, j int) bool {
return satisfaction[i] > satisfaction[j]
})
if satisfaction[0] <= 0 {
return 0
}
n := len(satisfaction)
dp := make([]int, n)
dp[0] = satisfaction[0]
sum := satisfaction[0]
for i := 1; i < n; i++ {
sum = sum + satisfaction[i]
dp[i] = max(dp[i-1], dp[i-1]+sum)
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1411.给Nx3网格图涂色的方案数(2)¶
题目
你有一个 n x 3的网格图 grid，你需要用 红，黄，绿三种颜色之一给每一个格子上色，
且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
给你网格图的行数 n。
请你返回给grid涂色的方案数。由于答案可能会非常大，请你返回答案对10^9 + 7取余的结果。
示例 1：输入：n = 1 输出：12
解释：总共有 12 种可行的方法：
示例 2：输入：n = 2 输出：54
示例 3：输入：n = 3 输出：246
示例 4：输入：n = 7 输出：106494
示例 5：输入：n = 5000 输出：30228214
提示：n == grid.length
grid[i].length == 3
1 <= n <= 5000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^3) | O(n^2) |
| 02 | 递推 | O(n) | O(1) |
var mod = 1000000007
func numOfWays(n int) int {
arr := make([]int, 0) // 保存所有满足条件的排列
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
if i != j && j != k {
arr = append(arr, i*100+j*10+k)
}
}
}
}
length := len(arr)
judgeArr := make([][]int, length) // 相邻关系判断：1代表相邻行可以相邻
for i := 0; i < length; i++ {
judgeArr[i] = make([]int, length)
for j := 0; j < length; j++ {
if arr[i]/100 != arr[j]/100 &&
arr[i]/10%10 != arr[j]/10%10 &&
arr[i]%10 != arr[j]%10 {
judgeArr[i][j] = 1
}
}
}
// 上面是预处理
dp := make([][]int, n+1) // dp[i][j]表示：i个x3网格，最后一行是呈现的是j的 方案数
for i := 0; i <= n; i++ {
dp[i] = make([]int, length)
}
for j := 0; j < length; j++ {
dp[1][j] = 1 // 第一行可以使用任何类型
}
for i := 2; i <= n; i++ {
for j := 0; j < length; j++ {
for k := 0; k < length; k++ {
if judgeArr[j][k] == 1 {
dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod
}
}
}
}
res := 0
for j := 0; j < length; j++ {
res = (res + dp[n][j]) % mod
}
return res
}
# 2
var mod = 1000000007
func numOfWays(n int) int {
// 满足要求的组合12种
// 6种互不相同：012, 021, 102, 120, 201, 210
// 6种带有相同：010, 020, 101, 121, 202, 212
a := 6 // 第1行是互不相同的
b := 6 // 第1行带相同的
for i := 2; i <= n; i++ {
x := (2*a + 2*b) % mod // 当前行是互不相同的
y := (2*a + 3*b) % mod // 当前行是带相同的
a = x
b = y
}
return (a + b) % mod
}
1420.生成数组(2)¶
题目
给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。
请你生成一个具有下述属性的数组 arr ：
arr 中有 n 个整数。
1 <= arr[i] <= m 其中 (0 <= i < n) 。
将上面提到的算法应用于 arr ，search_cost 的值等于 k 。
返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。
示例 1：输入：n = 2, m = 3, k = 1 输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
示例 2：输入：n = 5, m = 2, k = 3 输出：0
解释：没有数组可以满足上述条件
示例 3：输入：n = 9, m = 1, k = 1 输出：1
解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]
示例 4：输入：n = 50, m = 100, k = 25 输出：34549172
解释：不要忘了对 1000000007 取余
示例 5：输入：n = 37, m = 17, k = 7 输出：418930126
提示：1 <= n <= 50
1 <= m <= 100
0 <= k <= n
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^4) | O(n^3) |
| 02 | 动态规划 | O(n^3) | O(n^3) |
var mod = 1000000007
func numOfArrays(n int, m int, k int) int {
if k == 0 {
return 0
}
dp := make([][][]int, n+1) // 数组第i位最大值为j，比较次数为k的结果
for i := 0; i <= n; i++ {
dp[i] = make([][]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = make([]int, k+1)
}
}
for i := 1; i <= m; i++ {
dp[1][i][1] = 1
}
for i := 2; i <= n; i++ {
for j := 1; j <= m; j++ {
for a := 1; a <= k; a++ {
for b := 1; b < j; b++ { // 比j小,才可以次数+1
dp[i][j][a] = (dp[i][j][a] + dp[i-1][b][a-1]) % mod
}
dp[i][j][a] = (dp[i][j][a] + dp[i-1][j][a]*j) % mod // 跟j相同，可选择[1,j]共j个数
}
}
}
res := 0
for i := 1; i <= m; i++ {
res = (res + dp[n][i][k]) % mod
}
return res
}
# 2
var mod = 1000000007
func numOfArrays(n int, m int, k int) int {
if k == 0 {
return 0
}
dp := make([][][]int, n+1) // 数组第i位最大值为j，比较次数为k的结果
for i := 0; i <= n; i++ {
dp[i] = make([][]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = make([]int, k+1)
}
}
for i := 1; i <= m; i++ {
dp[1][i][1] = 1
}
for i := 2; i <= n; i++ {
for a := 1; a <= k; a++ {
tempSum := 0
for j := 1; j <= m; j++ {
dp[i][j][a] = (dp[i][j][a] + dp[i-1][j][a]*j) % mod // 跟j相同，可选择[1,j]共j个数
dp[i][j][a] = (dp[i][j][a] + tempSum) % mod // 跟j不同
tempSum = (tempSum + dp[i-1][j][a-1]) % mod
}
}
}
res := 0
for i := 1; i <= m; i++ {
res = (res + dp[n][i][k]) % mod
}
return res
}
1425.带限制的子序列和(4)¶
题目
给你一个整数数组nums和一个整数k，请你返回 非空子序列元素和的最大值，子序列需要满足：
子序列中每两个 相邻的整数nums[i]和nums[j]，
它们在原数组中的下标i和j满足i < j且 j - i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1：输入：nums = [10,2,-10,5,20], k = 2 输出：37
解释：子序列为 [10, 2, 5, 20] 。
示例 2：输入：nums = [-1,-2,-3], k = 1 输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。
示例 3：输入：nums = [10,-2,-10,-5,20], k = 2 输出：23
解释：子序列为 [10, -2, -5, 20] 。
提示：1 <= k <= nums.length <= 10^5
-10^4<= nums[i] <= 10^4
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^2) | O(n) |
| 02 | 动态规划 | O(n) | O(n) |
| 03 | 栈辅助 | O(n) | O(n) |
| 04 | 堆 | O(nlog(n)) | O(n) |
func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
if k > n {
k = n
}
res := nums[0]
dp[0] = nums[0]
maxValue := nums[0]
for i := 1; i < len(nums); i++ {
if i <= k { // 在前k个，dp[i] = maxValue + nums[i]
if maxValue < 0 {
dp[i] = nums[i]
} else {
dp[i] = maxValue + nums[i]
}
maxValue = max(maxValue, dp[i])
} else {
if maxValue == dp[i-1-k] { // 需要重新找maxValue
maxValue = getMaxValue(dp[i-k : i])
}
if maxValue < 0 {
dp[i] = nums[i]
} else {
dp[i] = maxValue + nums[i]
}
maxValue = max(maxValue, dp[i])
}
res = max(res, dp[i])
}
return res
}
func getMaxValue(arr []int) int {
maxValue := arr[0]
for i := 0; i < len(arr); i++ {
if arr[i] > maxValue {
maxValue = arr[i]
}
}
return maxValue
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
if k > n {
k = n
}
dp[0] = nums[0]
maxValue := nums[0]
maxIndex := 0
res := nums[0]
for i := 1; i < len(nums); i++ {
if i <= k { // 在前k个，dp[i] = maxValue + nums[i]
if maxValue < 0 {
dp[i] = nums[i]
} else {
dp[i] = maxValue + nums[i]
}
if dp[i] >= maxValue {
maxValue = dp[i]
maxIndex = i
}
} else {
if i-k > maxIndex {
maxValue = dp[maxIndex+1]
for j := maxIndex + 1; j < i; j++ {
if dp[j] >= maxValue {
maxValue = dp[j]
maxIndex = j
}
}
}
if maxValue < 0 {
dp[i] = nums[i]
} else {
dp[i] = maxValue + nums[i]
}
if dp[i] >= maxValue {
maxValue = dp[i]
maxIndex = i
}
}
if dp[i] > res {
res = dp[i]
}
}
return res
}
# 3
func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
if k > n {
k = n
}
temp := nums[0]
res := nums[0]
stack := make([][2]int, 0)
stack = append(stack, [2]int{0, nums[0]})
for i := 1; i < len(nums); i++ {
if stack[0][0] < i-k {
stack = stack[1:]
}
if stack[0][1] < 0 {
temp = nums[i]
} else {
temp = stack[0][1] + nums[i]
}
for len(stack) > 0 && stack[len(stack)-1][1] < temp {
stack = stack[:len(stack)-1]
}
stack = append(stack, [2]int{i, temp})
if temp > res {
res = temp
}
}
return res
}
# 4
func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
if k > n {
k = n
}
res := nums[0]
temp := nums[0]
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [2]int{0, nums[0]})
for i := 1; i < len(nums); i++ {
for i-intHeap[0][0] > k { // 不满足删除
heap.Pop(&intHeap)
}
if intHeap[0][1] < 0 {
temp = nums[i]
} else {
temp = intHeap[0][1] + nums[i]
}
if temp > res {
res = temp
}
heap.Push(&intHeap, [2]int{i, temp})
}
return res
}
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
}
1434.每个人戴不同帽子的方案数(3)¶
题目
总共有 n个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表hats，其中hats[i]是第 i个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对10^9 + 7取余后的结果。
示例 1：输入：hats = [[3,4],[4,5],[5]] 输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。
示例 2：输入：hats = [[3,5,1],[3,5]] 输出：4
解释：总共有 4 种安排帽子的方法：
(3,5)，(5,3)，(1,3) 和 (1,5)
示例 3：输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 输出：24
解释：每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24 。
示例 4：输入：hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]] 输出：111
提示：n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i]包含一个数字互不相同的整数列表。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^2*2^n) | O(n*2^n) |
| 02 | 动态规划 | O(n^2*2^n) | O(2^n) |
| 03 | 动态规划 | O(n^2*2^n) | O(2^n) |
var mod = 1000000007
func numberWays(hats [][]int) int {
n := len(hats) // n个人
maxValue := 0 // 最大的帽子编号，从1开始
m := make(map[int]map[int]bool) // 帽子对应人的喜欢关系
for i := 0; i < n; i++ {
for j := 0; j < len(hats[i]); j++ {
id := hats[i][j]
maxValue = max(maxValue, id)
if m[id] == nil {
m[id] = make(map[int]bool)
}
m[id][i] = true
}
}
dp := make([][]int, maxValue+1) // dp[i][j] 表示第i个帽子状态为j的方案数
for i := 0; i <= maxValue; i++ {
dp[i] = make([]int, 1<<n)
}
dp[0][0] = 1
target := (1 << n) - 1 // n个1
for i := 1; i <= maxValue; i++ {
for j := 0; j <= target; j++ { // 状态为0~2^n-1
dp[i][j] = dp[i-1][j]
for k := range m[i] { // 对第i个帽子喜欢
if (j>>k)&1 == 1 { // 判断状态j的第k位是否是1
// j ^ (1<<k) ：第k个人没有分配帽子
dp[i][j] = (dp[i][j] + dp[i-1][j^(1<<k)]) % mod
}
}
}
}
return dp[maxValue][target]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var mod = 1000000007
func numberWays(hats [][]int) int {
n := len(hats) // n个人
m := make(map[int]map[int]bool) // 帽子对应人的喜欢关系
for i := 0; i < n; i++ {
for j := 0; j < len(hats[i]); j++ {
id := hats[i][j]
if m[id] == nil {
m[id] = make(map[int]bool)
}
m[id][i] = true
}
}
target := (1 << n) - 1 // n个1
dp := make([]int, target+1) // dp[i][j] 表示第i个帽子状态为j的方案数
dp[0] = 1
for i := 1; i <= 40; i++ {
for j := target; j >= 0; j-- { // 状态为0~2^n-1
for k := range m[i] { // 对第i个帽子喜欢
if (j>>k)&1 == 0 { // 判断状态j的第k位是否是0
// j+1<<k ：第k个人没有分配帽子，然后分配帽子
next := j + 1<<k
dp[next] = (dp[j] + dp[next]) % mod
}
}
}
}
return dp[target]
}
# 3
var mod = 1000000007
func numberWays(hats [][]int) int {
n := len(hats)
target := (1 << n) - 1
dp := make([]int, target+1)
dp[0] = 1
arr := make([][]int, 41)
for i := 0; i < n; i++ {
for j := range hats[i] {
arr[hats[i][j]] = append(arr[hats[i][j]], i)
}
}
for i := 1; i <= 40; i++ {
for j := target - 1; j >= 0; j-- {
for _, k := range arr[i] {
if j&(1<<k) == 0 {
dp[j|(1<<k)] = dp[j|(1<<k)] + dp[j]
}
}
}
}
return dp[target] % mod
}
1439.有序矩阵中的第k个最小数组和¶
题目¶
给你一个 m* n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1：输入：mat = [[1,3,11],[2,4,6]], k = 5输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2：输入：mat = [[1,3,11],[2,4,6]], k = 9输出：17
示例 3：输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7 输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4：输入：mat = [[1,1,10],[2,2,9]], k = 7 输出：12
提示：m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
1449.数位成本和为目标值的最大数字(3)¶
题目
给你一个整数数组cost和一个整数target。请你返回满足如下规则可以得到的最大整数：
给当前结果添加一个数位（i + 1）的成本为cost[i]（cost数组下标从 0 开始）。
总成本必须恰好等于target。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 "0" 。
示例 1：输入：cost = [4,3,2,5,6,7,2,5,5], target = 9 输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。
所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5
示例 2：输入：cost = [7,6,5,5,5,6,8,7,8], target = 12 输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。
示例 3：输入：cost = [2,4,6,2,4,6,4,4,4], target = 5 输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。
示例 4：输入：cost = [6,10,15,40,40,40,40,40,40], target = 47 输出："32211"
提示：cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
| 02 | 动态规划 | O(n) | O(n) |
| 03 | 动态规划 | O(n) | O(n) |
func largestNumber(cost []int, target int) string {
dp, path := make([][]int, 10), make([][]int, 10)
for i := 0; i < 10; i++ {
dp[i], path[i] = make([]int, target+1), make([]int, target+1)
for j := 0; j <= target; j++ {
dp[i][j] = math.MinInt32
}
}
dp[0][0] = 0 // dp[i+1][j] 表示使用前i个数且花费总代价恰好为j时的最大长度
for i := 0; i < len(cost); i++ {
for j := 0; j <= target; j++ {
if j < cost[i] { // 不够
dp[i+1][j] = dp[i][j]
path[i+1][j] = j
} else {
// 不选:dp[i][j]、选:dp[i+1][j-cost[i]]
if dp[i][j] > dp[i+1][j-cost[i]]+1 { // 不选
dp[i+1][j] = dp[i][j]
path[i+1][j] = j
} else { // 选：相等时，也要更新，cost[i]相同取更大i
dp[i+1][j] = dp[i+1][j-cost[i]] + 1
path[i+1][j] = j - cost[i]
}
}
}
}
if dp[9][target] < 0 {
return "0"
}
res := ""
i, j := 9, target
for i > 0 {
if j == path[i][j] {
i--
} else {
res = res + string('0'+i)
j = path[i][j]
}
}
return res
}
# 2
func largestNumber(cost []int, target int) string {
dp := make([]int, target+1)
for i := 0; i <= target; i++ {
dp[i] = math.MinInt32
}
dp[0] = 0 // dp[i]表示花费总代价恰好为i时的最大长度
for i := 0; i < len(cost); i++ {
for j := cost[i]; j <= target; j++ {
dp[j] = max(dp[j], dp[j-cost[i]]+1)
}
}
if dp[target] < 0 {
return "0"
}
res := ""
j := target
for i := 8; i >= 0; i-- {
for c := cost[i]; j >= c && dp[j] == dp[j-c]+1; j = j - c {
res = res + string('1'+i)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
// 有x个物品，求给定费用target的前提下，花光所有费用所能选择的最大物品个数为多少
func largestNumber(cost []int, target int) string {
dp := make([]string, target+1)
for i := 1; i <= target; i++ {
dp[i] = "0"
for j := 8; j >= 0; j-- {
if cost[j] > i || (i-cost[j] != 0 && dp[i-cost[j]] == "0") {
continue
}
a, b := dp[i], dp[i-cost[j]]+fmt.Sprintf("%d", j+1)
if len(a) < len(b) {
dp[i] = b
} else if len(a) == len(b) && a < b {
dp[i] = b
}
}
}
return dp[target]
}
1458.两个子序列的最大点积(2)¶
题目
给你两个数组nums1和nums2。
请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，
但不能改变数字间相对顺序。比方说，[2,3,5]是[1,2,3,4,5]的一个子序列而[1,5,3]不是。
示例 1：输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6] 输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。
示例 2：输入：nums1 = [3,-2], nums2 = [2,-6,7] 输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。
示例 3：输入：nums1 = [-1,-1], nums2 = [1,1] 输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。
提示：1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 100
点积：定义 a= [a1,a2,…,an] 和 b= [b1,b2,…,bn] 的点积为：
这里的 Σ 指示总和符号。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^2) | O(n^2) |
| 02 | 动态规划 | O(n^2) | O(n^2) |
func maxDotProduct(nums1 []int, nums2 []int) int {
n, m := len(nums1), len(nums2)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
value := nums1[i] * nums2[j] // 单独选对应的i,j 乘积
dp[i][j] = value // 至少选一对
if i > 0 {
dp[i][j] = max(dp[i][j], dp[i-1][j])
}
if j > 0 {
dp[i][j] = max(dp[i][j], dp[i][j-1])
}
if i > 0 && j > 0 {
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+value)
}
}
}
return dp[n-1][m-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxDotProduct(nums1 []int, nums2 []int) int {
n, m := len(nums1), len(nums2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = math.MinInt32
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
value := nums1[i-1] * nums2[j-1] // 单独选对应的i,j 乘积
dp[i][j] = max(dp[i][j], value) // 至少选一对
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+value)
dp[i][j] = max(dp[i][j], dp[i-1][j])
dp[i][j] = max(dp[i][j], dp[i][j-1])
}
}
return dp[n][m]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1478.安排邮筒¶
题目¶
给你一个房屋数组houses和一个整数k，其中houses[i]是第 i栋房子在一条街上的位置，现需要在这条街上安排 k个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
答案保证在 32 位有符号整数范围以内。
示例 1：输入：houses = [1,4,8,10,20], k = 3 输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：输入：houses = [2,3,5,12,18], k = 2 输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：输入：houses = [7,4,6,1], k = 1 输出：8
示例 4：输入：houses = [3,6,14,10], k = 4 输出：0
提示：n == houses.length
1 <= n<= 100
1 <= houses[i] <= 10^4
1 <= k <= n
数组houses中的整数互不相同。
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
1483.树节点的第K个祖先(1)¶
题目
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。
树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。
如果不存在这样的祖先节点，返回 -1 。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
示例：输入：["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
输出：[null,1,0,-1]
解释：TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点
提示：1 <= k <=n <= 5*10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 <i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5*10^4 次
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划+倍增法 | O(nlog(n)) | O(nlog(n)) |
type TreeAncestor struct {
dp [][]int
}
func Constructor(n int, parent []int) TreeAncestor {
m := 0
for i := 1; i <= n; i = i * 2 {
m++
}
dp := make([][]int, n) // dp[i][j] => i的第2^j个父节点
for i := 0; i < n; i++ {
dp[i] = make([]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = -1
}
}
for i := 0; i < n; i++ {
dp[i][0] = parent[i]
}
for i := 0; i < n; i++ {
for j := 1; j < m; j++ {
if dp[i][j-1] == -1 { // 没有父节点
continue
}
prev := dp[i][j-1] // 状态转移方程：dp[i][j] = dp[prev][j-1]
dp[i][j] = dp[prev][j-1]
}
}
return TreeAncestor{dp: dp}
}
func (this *TreeAncestor) GetKthAncestor(node int, k int) int {
for i := 0; i < 16; i++ {
if k&(1<<i) > 0 {
node = this.dp[node][i]
}
if node == -1 {
break
}
}
return node
}
1494.并行课程II¶
题目¶
给你一个整数n表示某所大学里课程的数目，编号为1到n，数组dependencies中，
dependencies[i] = [xi, yi] 表示一个先修课的关系，也就是课程xi必须在课程yi之前上。同时你还有一个整数k。
在一个学期中，你 最多可以同时上 k门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
示例 1：输入：n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2 输出：3
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。
示例 2：输入：n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2 输出：4
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。
示例 3：输入：n = 11, dependencies = [], k = 2 输出：6
提示：1 <= n <= 15
1 <= k <= n
0 <=dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= xi, yi<= n
xi != yi
所有先修关系都是不同的，也就是说dependencies[i] != dependencies[j]。
题目输入的图是个有向无环图。
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^2) | O(n^2) |