1301-1400-Easy
1304.和为零的N个唯一整数(2)
给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。
示例 1：输入：n = 5 输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。
示例 2：输入：n = 3 输出：[-1,0,1]
示例 3：输入：n = 1 输出：[0]
提示：
1 <= n <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
1负N正 |
O(n) |
O(n) |
| 02 |
半正半负 |
O(n) |
O(n) |
func sumZero(n int) []int {
res := make([]int, n)
sum := 0
for i := 0; i < n-1; i++ {
res[i] = i + 1
sum = sum + i + 1
}
res[n-1] = -sum
return res
}
#
func sumZero(n int) []int {
res := make([]int, 0)
if n%2 == 1 {
res = append(res, 0)
}
for i := 1; i <= n/2; i++ {
res = append(res, i)
res = append(res, -i)
}
return res
}
1309.解码字母到整数映射(3)
给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
字符（'a' - 'i'）分别用（'1' - '9'）表示。
字符（'j' - 'z'）分别用（'10#' - '26#'）表示。
返回映射之后形成的新字符串。
题目数据保证映射始终唯一。
示例 1：输入：s = "10#11#12" 输出："jkab"
解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
示例 2：输入：s = "1326#" 输出："acz"
示例 3：输入：s = "25#" 输出："y"
示例 4：输入：s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
输出："abcdefghijklmnopqrstuvwxyz"
提示：
1 <= s.length <= 1000
s[i] 只包含数字（'0'-'9'）和 '#' 字符。
s 是映射始终存在的有效字符串。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
反向遍历 |
O(n) |
O(n) |
| 02 |
正向遍历 |
O(n) |
O(n) |
| 03 |
内置函数 |
O(n) |
O(n) |
func freqAlphabets(s string) string {
res := ""
for i := len(s) - 1; i >= 0; {
if s[i] == '#' {
value, _ := strconv.Atoi(string(s[i-2 : i]))
res = string('a'+value-1) + res
i = i - 3
} else {
value, _ := strconv.Atoi(string(s[i]))
res = string('a'+value-1) + res
i = i - 1
}
}
return res
}
#
func freqAlphabets(s string) string {
res := ""
for i := 0; i < len(s); {
if i+2 < len(s) && s[i+2] == '#' {
value, _ := strconv.Atoi(string(s[i : i+2]))
res = res + string('a'+value-1)
i = i + 3
} else {
value, _ := strconv.Atoi(string(s[i]))
res = res + string('a'+value-1)
i = i + 1
}
}
return res
}
#
func freqAlphabets(s string) string {
m := make(map[string]string)
for i := 10; i <= 26; i++ {
m[strconv.Itoa(i)+"#"] = string('j' + i - 10)
}
m2 := make(map[string]string)
for i := 1; i <= 9; i++ {
m2[strconv.Itoa(i)] = string('a' + i - 1)
}
for k, v := range m {
s = strings.ReplaceAll(s, k, v)
}
for k, v := range m2 {
s = strings.ReplaceAll(s, k, v)
}
return s
}
1313.解压缩编码列表(1)
给你一个以行程长度编码压缩的整数列表 nums 。
考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），
每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。
请你返回解压后的列表。
示例：输入：nums = [1,2,3,4] 输出：[2,4,4,4]
解释：第一对 [1,2] 代表着 2 的出现频次为 1，所以生成数组 [2]。
第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。
最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
示例 2：输入：nums = [1,1,2,3] 输出：[1,3,3]
提示：
2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
func decompressRLElist(nums []int) []int {
res := make([]int, 0)
for i := 0; i < len(nums); i = i + 2 {
for j := 0; j < nums[i]; j++ {
res = append(res, nums[i+1])
}
}
return res
}
1317.将整数转换为两个无零整数的和(2)
「无零整数」是十进制表示中 不含任何 0 的正整数。
给你一个整数 n，请你返回一个 由两个整数组成的列表 [A, B]，满足：
A 和 B 都是无零整数
A + B = n
题目数据保证至少有一个有效的解决方案。
如果存在多个有效解决方案，你可以返回其中任意一个。
示例 1：输入：n = 2 输出：[1,1]
解释：A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。
示例 2：输入：n = 11 输出：[2,9]
示例 3：输入：n = 10000 输出：[1,9999]
示例 4：输入：n = 69 输出：[1,68]
示例 5：输入：n = 1010 输出：[11,999]
提示：2 <= n <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(1) |
| 02 |
遍历 |
O(nlog(n)) |
O(1) |
func getNoZeroIntegers(n int) []int {
for i := 1; i < n; i++ {
if strings.ContainsAny(strconv.Itoa(i), "0") ||
strings.ContainsAny(strconv.Itoa(n-i), "0") {
continue
}
return []int{i, n - i}
}
return nil
}
#
func getNoZeroIntegers(n int) []int {
for i := 1; i < n; i++ {
if contains(i) || contains(n-i) {
continue
}
return []int{i, n - i}
}
return nil
}
func contains(num int) bool {
for num > 0 {
if num%10 == 0 {
return false
}
num = num / 10
}
return true
}
1323.6和9组成的最大数字(3)
给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1：输入：num = 9669 输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。
示例 2：输入：num = 9996 输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。
示例 3：输入：num = 9999 输出：9999
解释：无需改变就已经是最大的数字了。
提示：
1 <= num <= 10^4
num 每一位上的数字都是 6 或者 9 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-转字符串 |
O(log(n)) |
O(log(n)) |
| 02 |
遍历-转数组 |
O(log(n)) |
O(log(n)) |
| 03 |
内置函数 |
O(log(n)) |
O(log(n)) |
func maximum69Number(num int) int {
arr := []byte(strconv.Itoa(num))
for i := 0; i < len(arr); i++ {
if arr[i] == '6' {
arr[i] = '9'
break
}
}
res, _ := strconv.Atoi(string(arr))
return res
}
#
func maximum69Number(num int) int {
arr := make([]int, 0)
for num > 0 {
arr = append(arr, num%10)
num = num / 10
}
res := 0
flag := true
for i := len(arr) - 1; i >= 0; i-- {
if arr[i] == 6 && flag == true {
res = res*10 + 9
flag = false
} else {
res = res*10 + arr[i]
}
}
return res
}
#
func maximum69Number(num int) int {
str := strconv.Itoa(num)
str = strings.Replace(str, "6", "9", 1)
res, _ := strconv.Atoi(string(str))
return res
}
1331.数组序号转换(2)
给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下：
序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。
示例 1：输入：arr = [40,10,20,30] 输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。
示例 2：输入：arr = [100,100,100] 输出：[1,1,1]
解释：所有元素有相同的序号。
示例 3：输入：arr = [37,12,28,9,100,56,80,5,12] 输出：[5,3,4,2,8,6,7,1,3]
提示：
0 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-哈希辅助 |
O(nlog(n)) |
O(n) |
| 02 |
数组辅助 |
O(n) |
O(10^9) |
func arrayRankTransform(arr []int) []int {
temp := make([]int, len(arr))
copy(temp, arr)
sort.Ints(temp)
m := make(map[int]int)
count := 1
for i := 0; i < len(temp); i++ {
if m[temp[i]] > 0 {
continue
}
m[temp[i]] = count
count++
}
res := make([]int, len(arr))
for i := 0; i < len(arr); i++ {
res[i] = m[arr[i]]
}
return res
}
#
func arrayRankTransform(arr []int) []int {
if len(arr) == 0 {
return arr
}
min := math.MaxInt32
max := math.MinInt32
for i := 0; i < len(arr); i++ {
if arr[i] <= min {
min = arr[i]
}
if arr[i] >= max {
max = arr[i]
}
}
length := max - min + 1
temp := make([]int, length)
for i := 0; i < length; i++ {
temp[i] = math.MinInt32
}
for i := 0; i < len(arr); i++ {
temp[arr[i]-min] = -1
}
count := 0
for i := 0; i < length; i++ {
if temp[i] == -1 {
temp[i] = count
count++
}
}
for i := 0; i < len(arr); i++ {
arr[i] = temp[arr[i]-min] + 1
}
return arr
}
1332.删除回文子序列(2)
给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，
那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
示例 1：输入：s = "ababa" 输出：1
解释：字符串本身就是回文序列，只需要删除一次。
示例 2：输入：s = "abb" 输出：2
解释："abb" -> "bb" -> "". 先删除回文子序列 "a"，然后再删除 "bb"。
示例 3：输入：s = "baabb" 输出：2
解释："baabb" -> "b" -> "". 先删除回文子序列 "baab"，然后再删除 "b"。
示例 4：输入：s = "" 输出：0
提示：
0 <= s.length <= 1000
s 仅包含字母 'a' 和 'b'
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
反转 |
O(n) |
O(n) |
func removePalindromeSub(s string) int {
if len(s) == 0 {
return 0
}
for i, j := 0, len(s)-1; i < j; {
if s[i] != s[j] {
return 2
}
i++
j--
}
return 1
}
#
func removePalindromeSub(s string) int {
if len(s) == 0 {
return 0
}
temp := ""
for i := len(s) - 1; i >= 0; i-- {
temp = temp + string(s[i])
}
if temp == s {
return 1
}
return 2
}
1337.方阵中战斗力最弱的K行(2)
给你一个大小为 m * n 的方阵 mat，方阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回方阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，
那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
示例 1：输入：mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
示例 2：输入：mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
输出：[0,2]
解释：
每行中的军人数目：
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
从最弱到最强对这些行排序后得到 [0,2,3,1]
提示：
m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] 不是 0 就是 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
加权排序 |
O(n^2) |
O(n) |
| 02 |
自定义排序 |
O(n^2) |
O(n) |
func kWeakestRows(mat [][]int, k int) []int {
arr := make([]int, 0)
for i := 0; i < len(mat); i++ {
sum := 0
for j := 0; j < len(mat[i]); j++ {
if mat[i][j] == 1 {
sum++
}
}
arr = append(arr, sum*100+i)
}
sort.Ints(arr)
for i := 0; i < k; i++ {
arr[i] = arr[i] % 100
}
return arr[:k]
}
#
func kWeakestRows(mat [][]int, k int) []int {
arr := make([][]int, 0)
for i := 0; i < len(mat); i++ {
sum := 0
for j := 0; j < len(mat[i]); j++ {
if mat[i][j] == 1 {
sum++
}
}
arr = append(arr, []int{sum, i})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][0] == arr[j][0] {
return arr[i][1] < arr[j][1]
}
return arr[i][0] < arr[j][0]
})
res := make([]int, 0)
for i := 0; i < k; i++ {
res = append(res, arr[i][1])
}
return res
}
1342.将数字变成0的操作次数(3)
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。
如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
示例 1：输入：num = 14 输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。
示例 2：输入：num = 8 输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。
示例 3：输入：num = 123 输出：12
提示： 0 <= num <= 10^6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历模拟 |
O(log(n)) |
O(1) |
| 02 |
递归 |
O(log(n)) |
O(log(n)) |
| 02 |
递归 |
O(log(n)) |
O(log(n)) |
func numberOfSteps(num int) int {
res := 0
for num > 0 {
if num%2 == 1 {
num = num - 1
} else {
num = num / 2
}
res++
}
return res
}
#
var res int
func numberOfSteps(num int) int {
res = 0
dfs(num)
return res
}
func dfs(num int) {
if num != 0 {
res++
if num%2 == 1 {
dfs(num - 1)
} else {
dfs(num / 2)
}
}
}
#
func numberOfSteps(num int) int {
if num == 0 {
return 0
} else if num%2 == 1 {
return 1 + numberOfSteps(num-1)
}
return 1 + numberOfSteps(num/2)
}
1346.检查整数及其两倍数是否存在(3)
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
示例 1：输入：arr = [10,2,5,3] 输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。
示例 2：输入：arr = [7,1,14,11] 输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。
示例 3：输入：arr = [3,1,7,11] 输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。
提示：
2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
| 03 |
排序+二分查找 |
O(nlog(n)) |
O(1) |
func checkIfExist(arr []int) bool {
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if arr[i]*2 == arr[j] || arr[j]*2 == arr[i] {
return true
}
}
}
return false
}
#
func checkIfExist(arr []int) bool {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
if m[arr[i]*2] > 0 || (i%2 == 0 && m[arr[i]/2] > 0) {
return true
}
m[arr[i]] = 1
}
return false
}
#
func checkIfExist(arr []int) bool {
var target int
sort.Ints(arr)
for i := 0; i < len(arr); i++ {
left := i + 1
right := len(arr) - 1
if arr[i] >= 0 {
target = 2 * arr[i]
} else {
if arr[i]%2 == -1 {
continue
}
target = arr[i] / 2
}
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return true
} else if arr[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
}
return false
}
1351.统计有序矩阵中的负数(4)
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
请你统计并返回 grid 中 负数 的数目。
示例 1：输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 输出：8
解释：矩阵中共有 8 个负数。
示例 2：输入：grid = [[3,2],[1,0]] 输出：0
示例 3：输入：grid = [[1,-1],[-1,-1]] 输出：3
示例 4：输入：grid = [[-1]] 输出：1
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
二分查找 |
O(nlog(n)) |
O(1) |
| 03 |
遍历 |
O(n^2) |
O(1) |
| 04 |
右上角 |
O(n) |
O(1) |
func countNegatives(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] < 0 {
res++
}
}
}
return res
}
#
func countNegatives(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
res = res + (len(grid[i]) - search(grid[i]))
}
return res
}
func search(arr []int) int {
left := 0
right := len(arr) - 1
for left <= right {
mid := left + (right-left)/2
if arr[mid] >= 0 {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
#
func countNegatives(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
for j := len(grid[i]) - 1; j >= -1; j-- {
if j == -1 {
res = res + len(grid[i])
break
}
if grid[i][j] >= 0 {
count := len(grid[i]) - 1 - j
res = res + count
break
}
}
}
return res
}
#
func countNegatives(grid [][]int) int {
res := 0
i := 0
j := len(grid[0])-1
for i < len(grid) && j >= 0 {
if grid[i][j] >=0{
res = res + len(grid[0])-j-1
i++
}else {
j--
}
}
if j < 0{
res = res + (len(grid)-i)*len(grid[0])
}
return res
}
1356.根据数字二进制下1的数目排序(3)
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
示例 1：输入：arr = [0,1,2,3,4,5,6,7,8] 输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
示例 2：输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
示例 3：输入：arr = [10000,10000] 输出：[10000,10000]
示例 4：输入：arr = [2,3,5,7,11,13,17,19] 输出：[2,3,5,17,7,11,13,19]
示例 5：输入：arr = [10,100,1000,10000] 输出：[10,100,10000,1000]
提示：
1 <= arr.length <= 500
0 <= arr[i] <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(log(n)^2*n) |
O(1) |
| 02 |
排序+分组 |
O(nlog(n)) |
O(n) |
| 03 |
内置函数 |
O(log(n)^2*n) |
O(1) |
func sortByBits(arr []int) []int {
sort.Slice(arr, func(i, j int) bool {
if countBit(arr[i]) == countBit(arr[j]) {
return arr[i] < arr[j]
}
return countBit(arr[i]) < countBit(arr[j])
})
return arr
}
func countBit(num int) int {
res := 0
for num > 0 {
if num%2 == 1 {
res++
}
num = num / 2
}
return res
}
#
func sortByBits(arr []int) []int {
sort.Ints(arr)
m := make(map[int][]int, 0)
for i := 0; i < len(arr); i++ {
num := countBit(arr[i])
m[num] = append(m[num], arr[i])
}
res := make([]int, 0)
for i := 0; i < 32; i++ {
for _, value := range m[i] {
res = append(res, value)
}
}
return res
}
func countBit(num int) int {
res := 0
for num > 0 {
if num%2 == 1 {
res++
}
num = num / 2
}
return res
}
#
func sortByBits(arr []int) []int {
sort.Slice(arr, func(i, j int) bool {
if bits.OnesCount32(uint32(arr[i])) == bits.OnesCount32(uint32(arr[j])) {
return arr[i] < arr[j]
}
return bits.OnesCount32(uint32(arr[i])) < bits.OnesCount32(uint32(arr[j]))
})
return arr
}
1360.日期之间隔几天(2)
请你编写一个程序来计算两个日期之间隔了多少天。
日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。
示例 1：输入：date1 = "2019-06-29", date2 = "2019-06-30" 输出：1
示例 2：输入：date1 = "2020-01-15", date2 = "2019-12-31" 输出：15
提示：
给定的日期是 1971 年到 2100 年之间的有效日期。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(1) |
O(1) |
| 02 |
内置函数 |
O(1) |
O(1) |
func daysBetweenDates(date1 string, date2 string) int {
v1 := totalDay(date1)
v2 := totalDay(date2)
if v1 > v2 {
return v1 - v2
}
return v2 - v1
}
var monthDate = []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
func totalDay(date string) int {
var year, month, day int
arr := strings.Split(date, "-")
year, _ = strconv.Atoi(arr[0])
month, _ = strconv.Atoi(arr[1])
day, _ = strconv.Atoi(arr[2])
total := 0
for i := 1971; i < year; i++ {
total = total + 365
if isLeap(i) {
total = total + 1
}
}
for i := 0; i < month-1; i++ {
total = total + monthDate[i]
if i == 1 && isLeap(year) {
total = total + 1
}
}
total = total + day
return total
}
func isLeap(year int) bool {
return year%400 == 0 || (year%4 == 0 && year%100 != 0)
}
#
func daysBetweenDates(date1 string, date2 string) int {
t1, _ := time.Parse("2006-01-02", date1)
t2, _ := time.Parse("2006-01-02", date2)
value := int(t1.Sub(t2).Hours() / 24)
if value > 0 {
return value
}
return -value
}
1365.有多少小于当前数字的数字(3)
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例 1：输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3]
解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
示例 2：输入：nums = [6,5,4,8] 输出：[2,1,0,3]
示例 3：输入：nums = [7,7,7,7] 输出：[0,0,0,0]
提示：
2 <= nums.length <= 500
0 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
暴力法 |
O(n^2) |
O(n) |
| 03 |
排序 |
O(nlog(n)) |
O(n) |
func smallerNumbersThanCurrent(nums []int) []int {
arr := make([]int, 101)
res := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
arr[nums[i]]++
}
for i := 1; i < len(arr); i++ {
arr[i] = arr[i] + arr[i-1]
}
for i := 0; i < len(nums); i++ {
if nums[i] != 0 {
res[i] = arr[nums[i]-1]
}
}
return res
}
#
func smallerNumbersThanCurrent(nums []int) []int {
res := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
if nums[i] > nums[j] {
res[i]++
}
}
}
return res
}
#
func smallerNumbersThanCurrent(nums []int) []int {
temp := make([]int, len(nums))
copy(temp, nums)
sort.Ints(temp)
m := make(map[int]int)
count := 0
m[temp[0]] = count
for i := 1; i < len(temp); i++ {
count++
if temp[i-1] != temp[i] {
m[temp[i]] = count
} else {
m[temp[i]] = m[temp[i-1]]
}
}
res := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
res[i] = m[nums[i]]
}
return res
}
1370.上升下降字符串(2)
给你一个字符串 s ，请你根据下面的算法重新构造字符串：
从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
示例 1：输入：s = "aaaabbbbcccc" 输出："abccbaabccba"
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"
示例 2：输入：s = "rat" 输出："art"
解释：单词 "rat" 在上述算法重排序以后变成 "art"
示例 3：输入：s = "leetcode" 输出："cdelotee"
示例 4：输入：s = "ggggggg" 输出："ggggggg"
示例 5：输入：s = "spo" 输出："ops"
提示：
1 <= s.length <= 500
s 只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func sortString(s string) string {
arr := make([]int, 26)
for i := 0; i < len(s); i++ {
arr[s[i]-'a']++
}
res := ""
for len(res) < len(s) {
for i := 0; i < 26; i++ {
if arr[i] > 0 {
res = res + string(i+'a')
arr[i]--
}
}
for i := 25; i >= 0; i-- {
if arr[i] > 0 {
res = res + string(i+'a')
arr[i]--
}
}
}
return res
}
#
func sortString(s string) string {
m := make(map[int]int, 26)
for i := 0; i < len(s); i++ {
m[int(s[i]-'a')]++
}
res := ""
for len(res) < len(s) {
for i := 0; i < 26; i++ {
if m[i] > 0 {
res = res + string(i+'a')
m[i]--
}
}
for i := 25; i >= 0; i-- {
if m[i] > 0 {
res = res + string(i+'a')
m[i]--
}
}
}
return res
}
1374.生成每种字符都是奇数个的字符串(2)
给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。
返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。
示例 1：输入：n = 4 输出："pppz"
解释："pppz" 是一个满足题目要求的字符串，因为 'p' 出现 3 次，且 'z' 出现 1 次。
当然，还有很多其他字符串也满足题目要求，比如："ohhh" 和 "love"。
示例 2：输入：n = 2 输出："xy"
解释："xy" 是一个满足题目要求的字符串，因为 'x' 和 'y' 各出现 1 次。
当然，还有很多其他字符串也满足题目要求，比如："ag" 和 "ur"。
示例 3：输入：n = 7 输出："holasss"
提示：1 <= n <= 500
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
奇1偶2 |
O(n) |
O(n) |
| 02 |
奇1偶2 |
O(n) |
O(n) |
func generateTheString(n int) string {
if n % 2 == 0 {
return strings.Repeat("a", n-1)+"b"
}
return strings.Repeat("a", n)
}
#
func generateTheString(n int) string {
res := ""
if n%2 == 0 {
res = "a"
for i := 0; i < n-1; i++ {
res = res + "b"
}
} else {
for i := 0; i < n; i++ {
res = res + "a"
}
}
return res
}
1379.找出克隆二叉树中的相同节点
题目
给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
其中，克隆树 cloned 是原始树 original 的一个 副本 。
请找出在树 cloned 中，与 target 相同 的节点，
并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
示例 1:输入: tree = [7,4,3,null,null,6,19], target = 3 输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。
答案是树 cloned 中的黄颜色的节点（其他示例类似）。
示例 2:输入: tree = [7], target = 7 输出: 7
示例 3:输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 输出: 4
提示：树中节点的数量范围为 [1, 104] 。
同一棵树中，没有值相同的节点。
target 节点是树 original 中的一个节点，并且不会是 null 。
进阶：如果树中允许出现值相同的节点，将如何解答？
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
奇1偶2 |
O(n) |
O(n) |
1380.矩阵中的幸运数(2)
给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
幸运数是指矩阵中满足同时下列两个条件的元素：
在同一行的所有元素中最小
在同一列的所有元素中最大
示例 1：输入：matrix = [[3,7,8],[9,11,13],[15,16,17]] 输出：[15]
解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
示例 2：输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] 输出：[12]
解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
示例 3：输入：matrix = [[7,8],[1,2]] 输出：[7]
提示：
m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5
矩阵中的所有元素都是不同的
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n) |
| 02 |
遍历 |
O(n^2) |
O(n) |
func luckyNumbers(matrix [][]int) []int {
res := make([]int, 0)
for i := 0; i < len(matrix); i++ {
min := matrix[i][0]
minIndex := 0
for j := 1; j < len(matrix[i]); j++ {
if min > matrix[i][j] {
min = matrix[i][j]
minIndex = j
}
}
flag := true
for j := 0; j < len(matrix); j++ {
if matrix[j][minIndex] > min {
flag = false
break
}
}
if flag == true {
res = append(res, min)
}
}
return res
}
#
func luckyNumbers(matrix [][]int) []int {
res := make([]int, 0)
minArr := make([]int, 0)
maxArr := make([]int, 0)
for i := 0; i < len(matrix); i++ {
min := matrix[i][0]
for j := 1; j < len(matrix[i]); j++ {
if min > matrix[i][j] {
min = matrix[i][j]
}
}
minArr = append(minArr, min)
}
for i := 0; i < len(matrix[0]); i++ {
max := matrix[0][i]
for j := 1; j < len(matrix); j++ {
if max < matrix[j][i] {
max = matrix[j][i]
}
}
maxArr = append(maxArr, max)
}
for i := 0; i < len(minArr); i++ {
for j := 0; j < len(maxArr); j++ {
if minArr[i] == maxArr[j] {
res = append(res, minArr[i])
}
}
}
return res
}
1385.两个数组间的距离值(2)
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此描述的元素数目：
对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
示例 1：输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 输出：2
解释：
对于 arr1[0]=4 我们有：
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
对于 arr1[1]=5 我们有：
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
示例 2：输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3 输出：2
示例 3：输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6 输出：1
提示：
1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
二分查找 |
O(nlog(n)) |
O(1) |
func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
res := 0
for i := 0; i < len(arr1); i++ {
flag := true
for j := 0; j < len(arr2); j++ {
if abs(arr1[i], arr2[j]) <= d {
flag = false
}
}
if flag == true {
res++
}
}
return res
}
#
func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
res := 0
sort.Ints(arr2)
for i := 0; i < len(arr1); i++ {
if search(arr1[i], arr2, d) {
res++
}
}
return res
}
func search(target int, arr []int, d int) bool {
left := 0
right := len(arr) - 1
for left <= right {
mid := left + (right-left)/2
if arr[mid] < target {
if target-arr[mid] <= d {
return false
}
left = mid + 1
} else {
if arr[mid]-target <= d {
return false
}
right = mid - 1
}
}
return true
}
1389.按既定顺序创建目标数组(3)
给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：
目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，
在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。
请你返回目标数组。
题目保证数字插入位置总是存在。
示例 1：输入：nums = [0,1,2,3,4], index = [0,1,2,2,1] 输出：[0,4,1,3,2]
解释：
nums index target
0 0 [0]
1 1 [0,1]
2 2 [0,1,2]
3 2 [0,1,3,2]
4 1 [0,4,1,3,2]
示例 2：输入：nums = [1,2,3,4,0], index = [0,1,2,3,0] 输出：[0,1,2,3,4]
解释：
nums index target
1 0 [1]
2 1 [1,2]
3 2 [1,2,3]
4 3 [1,2,3,4]
0 0 [0,1,2,3,4]
示例 3：输入：nums = [1], index = [0] 输出：[1]
提示：
1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历模拟 |
O(n^2) |
O(n) |
| 02 |
遍历-切片操作 |
O(n^2) |
O(n) |
| 03 |
遍历-定位 |
O(n^2) |
O(n) |
func createTargetArray(nums []int, index []int) []int {
res := make([]int, len(nums))
for i := 0; i < len(index); i++ {
for j := len(res) - 1; j > index[i]; j-- {
res[j] = res[j-1]
}
res[index[i]] = nums[i]
}
return res
}
#
func createTargetArray(nums []int, index []int) []int {
res := make([]int, len(nums))
for i := 0; i < len(index); i++ {
copy(res[index[i]+1:], res[index[i]:])
res[index[i]] = nums[i]
}
return res
}
#
func createTargetArray(nums []int, index []int) []int {
res := make([]int, len(nums))
for i := 0; i < len(index); i++ {
for j := 0; j < i; j++ {
if index[j] >= index[i] {
index[j]++
}
}
}
for i := 0; i < len(index); i++ {
res[index[i]] = nums[i]
}
return res
}
1394.找出数组中的幸运数(2)
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
给你一个整数数组 arr，请你从中找出并返回一个幸运数。
如果数组中存在多个幸运数，只需返回 最大 的那个。
如果数组中不含幸运数，则返回 -1 。
示例 1：输入：arr = [2,2,3,4] 输出：2
解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
示例 2：输入：arr = [1,2,2,3,3,3] 输出：3
解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
示例 3：输入：arr = [2,2,2,3,3] 输出：-1
解释：数组中不存在幸运数。
示例 4：输入：arr = [5] 输出：-1
示例 5：输入：arr = [7,7,7,7,7,7,7] 输出：7
提示：
1 <= arr.length <= 500
1 <= arr[i] <= 500
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
数组辅助 |
O(n) |
O(1) |
func findLucky(arr []int) int {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
m[arr[i]]++
}
max := -1
for i := range m {
if i == m[i] && max < i {
max = i
}
}
return max
}
#
func findLucky(arr []int) int {
res := make([]int, 501)
for i := 0; i < len(arr); i++ {
res[arr[i]]++
}
for i := 500; i >= 1; i-- {
if res[i] == i {
return i
}
}
return -1
}
1399.统计最大组的数目(2)
给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），
然后把数位和相等的数字放到同一个组中。
请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
示例 1：输入：n = 13 输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
示例 2：输入：n = 2 输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。
示例 3：输入：n = 15 输出：6
示例 4：输入：n = 24 输出：5
提示：1 <= n <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(nlog(n)) |
O(1) |
| 02 |
数组辅助 |
O(nlog(n)) |
O(1) |
func countLargestGroup(n int) int {
if n < 10 {
return n
}
m := make(map[int]int,50)
max := 0
for i := 1; i <= n; i++ {
value := sum(i)
m[value]++
if m[value] > max {
max = m[value]
}
}
res := 0
for i := range m {
if m[i] == max {
res++
}
}
return res
}
func sum(n int) int {
res := 0
for n > 0 {
res = res + n%10
n = n / 10
}
return res
}
#
func countLargestGroup(n int) int {
if n < 10 {
return n
}
arr := make([]int, 50)
max := 0
for i := 1; i <= n; i++ {
value := sum(i)
arr[value]++
if arr[value] > max {
max = arr[value]
}
}
res := 0
for i := range arr {
if arr[i] == max {
res++
}
}
return res
}
func sum(n int) int {
res := 0
for n > 0 {
res = res + n%10
n = n / 10
}
return res
}
1301-1400-Medium
1302.层数最深叶子节点的和(2)
给你一棵二叉树，请你返回层数最深的叶子节点的和。
示例：输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8] 输出：15
提示：树中节点数目在 1 到 10^4 之间。
每个节点的值在 1 到 100 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
var maxLevel, sum int
func deepestLeavesSum(root *TreeNode) int {
maxLevel, sum = 0, 0
dfs(root, 0)
return sum
}
func dfs(root *TreeNode, level int) {
if root != nil {
if level > maxLevel {
maxLevel = level
sum = root.Val
} else if level == maxLevel {
sum = sum + root.Val
}
dfs(root.Left, level+1)
dfs(root.Right, level+1)
}
}
# 2
func deepestLeavesSum(root *TreeNode) int {
if root == nil {
return 0
}
res := 0
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
length := len(queue)
res = 0
for i := 0; i < length; i++ {
res = res + queue[i].Val
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
}
queue = queue[length:]
}
return res
}
1305.两棵二叉搜索树中的所有元素(3)
给你 root1 和 root2 这两棵二叉搜索树。
请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
示例 1：输入：root1 = [2,1,4], root2 = [1,0,3] 输出：[0,1,1,2,3,4]
示例 2：输入：root1 = [0,-10,10], root2 = [5,1,7,0,2] 输出：[-10,0,0,1,2,5,7,10]
示例 3：输入：root1 = [], root2 = [5,1,7,0,2] 输出：[0,1,2,5,7]
示例 4：输入：root1 = [0,-10,10], root2 = [] 输出：[-10,0,10]
示例 5：输入：root1 = [1,null,8], root2 = [8,1] 输出：[1,1,8,8]
提示：每棵树最多有 5000 个节点。
每个节点的值在 [-10^5, 10^5] 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(nlog(n)) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
| 03 |
迭代 |
O(n) |
O(n) |
var res []int
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
res = make([]int, 0)
dfs(root1)
dfs(root2)
sort.Ints(res)
return res
}
func dfs(root *TreeNode) {
if root == nil {
return
}
res = append(res, root.Val)
dfs(root.Left)
dfs(root.Right)
}
# 2
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
res := make([]int, 0)
arr1, arr2 := make([]int, 0), make([]int, 0)
dfs(root1, &arr1)
dfs(root2, &arr2)
i, j := 0, 0
for i < len(arr1) || j < len(arr2) {
if i < len(arr1) && (j == len(arr2) || arr1[i] < arr2[j]) {
res = append(res, arr1[i])
i++
} else {
res = append(res, arr2[j])
j++
}
}
return res
}
func dfs(root *TreeNode, arr *[]int) {
if root == nil {
return
}
dfs(root.Left, arr)
*arr = append(*arr, root.Val)
dfs(root.Right, arr)
}
# 3
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
res := make([]int, 0)
arr1 := inorderTraversal(root1)
arr2 := inorderTraversal(root2)
i, j := 0, 0
for i < len(arr1) || j < len(arr2) {
if i < len(arr1) && (j == len(arr2) || arr1[i] < arr2[j]) {
res = append(res, arr1[i])
i++
} else {
res = append(res, arr2[j])
j++
}
}
return res
}
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := make([]*TreeNode, 0)
res := make([]int, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
last := len(stack) - 1
res = append(res, stack[last].Val)
root = stack[last].Right
stack = stack[:last]
}
return res
}
1306.跳跃游戏III(2)
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。
当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
示例 1：输入：arr = [4,2,3,0,3,1,2], start = 5 输出：true
解释：到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
示例 2：输入：arr = [4,2,3,0,3,1,2], start = 0 输出：true
解释：到达值为 0 的下标 3 有以下可能方案：
下标 0 -> 下标 4 -> 下标 1 -> 下标 3
示例 3：输入：arr = [3,0,2,1,2], start = 2 输出：false
解释：无法到达值为 0 的下标 1 处。
提示：
1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n) |
O(n) |
| 02 |
深度优先搜索 |
O(n) |
O(n) |
func canReach(arr []int, start int) bool {
m := make(map[int]bool)
queue := make([]int, 0)
queue = append(queue, start)
for len(queue) > 0 {
length := len(queue)
for j := 0; j < length; j++ {
i := queue[j]
if m[i] == false {
m[i] = true
if i+arr[i] < len(arr) {
if arr[i+arr[i]] == 0 {
return true
}
queue = append(queue, i+arr[i])
}
if i-arr[i] >= 0 {
if arr[i-arr[i]] == 0 {
return true
}
queue = append(queue, i-arr[i])
}
}
}
queue = queue[length:]
}
return false
}
# 2
var m map[int]bool
func canReach(arr []int, start int) bool {
m = make(map[int]bool)
return dfs(arr, start)
}
func dfs(arr []int, i int) bool {
if i < 0 || i > len(arr)-1 || m[i] == true {
return false
}
m[i] = true
return arr[i] == 0 || dfs(arr, i+arr[i]) || dfs(arr, i-arr[i])
}
1310.子数组异或查询(1)
有一个正整数数组arr，现给你一个对应的查询数组queries，其中queries[i] = [Li,Ri]。
对于每个查询i，请你计算从Li到Ri的XOR值
（即arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询queries所有结果的数组。
示例 1：输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 输出：[2,7,14,8]
解释：数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
示例 2：输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 输出：[8,0,4,4]
提示：1 <= arr.length <= 3 *10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀异或和 |
O(n) |
O(n) |
func xorQueries(arr []int, queries [][]int) []int {
temp := make([]int, len(arr)+1)
for i := 0; i < len(arr); i++ {
temp[i+1] = temp[i] ^ arr[i]
}
res := make([]int, 0)
for i := 0; i < len(queries); i++ {
a, b := queries[i][0], queries[i][1]+1
res = append(res, temp[a]^temp[b])
}
return res
}
1311.获取你好友已观看的视频(1)
有n 个人，每个人都有一个 0到n-1的唯一id。
给你数组 watchedVideos 和friends，
其中watchedVideos[i] 和friends[i]分别表示id = i的人观看过的视频列表和他的好友列表。
Level1的视频包含所有你好友观看过的视频，level2的视频包含所有你好友的好友观看过的视频，以此类推。
一般的，Level 为 k的视频包含所有从你出发，最短距离为k的好友观看过的视频。
给定你的id 和一个level值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。
如果有频率相同的视频，请将它们按字母顺序从小到大排列。
示例 1：输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]],
friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出：["B","C"]
解释：你的 id 为 0（绿色），你的朋友包括（黄色）：
id 为 1 -> watchedVideos = ["C"]
id 为 2 -> watchedVideos = ["B","C"]
你朋友观看过视频的频率为：
B -> 1
C -> 2
示例 2：输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]],
friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出：["D"]
解释：你的 id 为 0（绿色），你朋友的朋友只有一个人，他的 id 为 3（黄色）。
提示：
n == watchedVideos.length ==friends.length
2 <= n<= 100
1 <=watchedVideos[i].length <= 100
1 <=watchedVideos[i][j].length <= 8
0 <= friends[i].length < n
0 <= friends[i][j]< n
0 <= id < n
1 <= level < n
如果friends[i] 包含j，那么friends[j] 包含i
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n^2) |
O(n^2) |
func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, level int) []string {
m := make(map[string]int)
visited := make(map[int]bool)
visited[id] = true
queue := make([]int, 0)
queue = append(queue, id)
for len(queue) > 0 {
level--
length := len(queue)
for i := 0; i < length; i++ {
node := queue[i]
for j := 0; j < len(friends[node]); j++ {
ID := friends[node][j]
if visited[ID] == false {
visited[ID] = true
queue = append(queue, ID)
if level == 0 {
for _, v := range watchedVideos[ID] {
m[v]++
}
}
}
}
}
if level == 0 {
break
}
queue = queue[length:]
}
res := make([]string, 0)
for k := range m {
res = append(res, k)
}
sort.Slice(res, func(i, j int) bool {
if m[res[i]] == m[res[j]] {
return res[i] < res[j]
}
return m[res[i]] < m[res[j]]
})
return res
}
1314.矩阵区域和(2)
给你一个m * n的矩阵mat和一个整数K ，请你返回一个矩阵answer，
其中每个answer[i][j]是所有满足下述条件的元素mat[r][c] 的和：
i - K <= r <= i + K, j - K <= c <= j + K
(r, c)在矩阵内。
示例 1：输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：m ==mat.length
n ==mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二维前缀和 |
O(n^2) |
O(n^2) |
| 02 |
二维前缀和 |
O(n^2) |
O(n^2) |
func matrixBlockSum(mat [][]int, K int) [][]int {
n, m := len(mat), len(mat[0])
arr := make([][]int, n+1)
for i := 0; i < n+1; i++ {
arr[i] = make([]int, m+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + mat[i-1][j-1]
}
}
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, m)
for j := 0; j < m; j++ {
a1, a2 := getIndex(n, m, i+K+1, j+K+1)
b1, b2 := getIndex(n, m, i-K, j+K+1)
c1, c2 := getIndex(n, m, i+K+1, j-K)
d1, d2 := getIndex(n, m, i-K, j-K)
res[i][j] = arr[a1][a2] - arr[b1][b2] - arr[c1][c2] + arr[d1][d2]
}
}
return res
}
func getIndex(a, b, x, y int) (int, int) {
x = max(min(a, x), 0)
y = max(min(b, y), 0)
return x, y
}
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 matrixBlockSum(mat [][]int, K int) [][]int {
n, m := len(mat), len(mat[0])
arr := make([][]int, n+1)
for i := 0; i < n+1; i++ {
arr[i] = make([]int, m+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + mat[i-1][j-1]
}
}
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, m)
for j := 0; j < m; j++ {
left, right := max(0, j-K), min(m, j+K+1)
up, down := max(0, i-K), min(n, i+K+1)
res[i][j] = arr[down][right] - arr[down][left] - arr[up][right] + arr[up][left]
}
}
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
}
1315.祖父节点值为偶数的节点和(3)
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回0 。
示例：输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出：18
解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
提示：树中节点的数目在1 到10^4之间。
每个节点的值在1 到100 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
递归 |
O(n) |
O(log(n)) |
| 03 |
迭代 |
O(n) |
O(n) |
func sumEvenGrandparent(root *TreeNode) int {
res := 0
if root == nil {
return res
}
if root.Val%2 == 0 {
if root.Left != nil && root.Left.Left != nil {
res = res + root.Left.Left.Val
}
if root.Left != nil && root.Left.Right != nil {
res = res + root.Left.Right.Val
}
if root.Right != nil && root.Right.Left != nil {
res = res + root.Right.Left.Val
}
if root.Right != nil && root.Right.Right != nil {
res = res + root.Right.Right.Val
}
}
res = res + sumEvenGrandparent(root.Left)
res = res + sumEvenGrandparent(root.Right)
return res
}
# 2
var res int
func sumEvenGrandparent(root *TreeNode) int {
res = 0
if root == nil {
return res
}
dfs(root, false, false)
return res
}
func dfs(root *TreeNode, grandfather, father bool) {
if root == nil {
return
}
if grandfather == true {
res = res + root.Val
}
flag := true
if root.Val%2 == 1 {
flag = false
}
dfs(root.Left, father, flag)
dfs(root.Right, father, flag)
}
# 3
func sumEvenGrandparent(root *TreeNode) int {
res := 0
if root == nil {
return res
}
quque := make([]*TreeNode, 0)
quque = append(quque, root)
for len(quque) > 0 {
length := len(quque)
for i := 0; i < length; i++ {
node := quque[i]
if node.Val%2 == 0 {
if node.Left != nil && node.Left.Left != nil {
res = res + node.Left.Left.Val
}
if node.Left != nil && node.Left.Right != nil {
res = res + node.Left.Right.Val
}
if node.Right != nil && node.Right.Left != nil {
res = res + node.Right.Left.Val
}
if node.Right != nil && node.Right.Right != nil {
res = res + node.Right.Right.Val
}
}
if node.Left != nil {
quque = append(quque, node.Left)
}
if node.Right != nil {
quque = append(quque, node.Right)
}
}
quque = quque[length:]
}
return res
}
1318.或运算的最小翻转次数(2)
给你三个正整数a、b 和 c。
你可以对 a 和 b的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c成立的最小翻转次数。
「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。
示例 1：输入：a = 2, b = 6, c = 5 输出：3
解释：翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c
示例 2：输入：a = 4, b = 2, c = 7 输出：1
示例 3：输入：a = 1, b = 2, c = 3 输出：0
提示：1 <= a <= 10^9
1 <= b<= 10^9
1 <= c<= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
位运算 |
O(1) |
O(1) |
| 02 |
位运算 |
O(1) |
O(1) |
func minFlips(a int, b int, c int) int {
res := 0
for i := 0; i < 31; i++ {
A := (a >> i) & 1
B := (b >> i) & 1
C := (c >> i) & 1
if C == 0 {
res = res + A + B
} else {
if A+B == 0 {
res = res + 1
}
}
}
return res
}
# 2
func minFlips(a int, b int, c int) int {
res := 0
for i := 0; i < 31; i++ {
A := a & 1
B := b & 1
C := c & 1
if C == 0 {
res = res + A + B
} else {
if A+B == 0 {
res = res + 1
}
}
a, b, c = a>>1, b>>1, c>>1
}
return res
}
1319.连通网络的操作次数(2)
用以太网线缆将n台计算机连接成一个网络，计算机的编号从0到n-1。
线缆用connections表示，其中connections[i] = [a, b]连接了计算机a和b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线connections，你可以拔开任意两台直连计算机之间的线缆，
并用它连接一对未直连的计算机。
请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回-1 。
示例 1：输入：n = 4, connections = [[0,1],[0,2],[1,2]] 输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] 输出：2
示例 3：输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] 输出：-1
解释：线缆数量不足。
示例 4：输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]] 输出：0
提示：1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1]< n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
并查集 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
func makeConnected(n int, connections [][]int) int {
if len(connections) < n-1 {
return -1
}
res := n - 1
fa := make([]int, n)
for i := 0; i < n; i++ {
fa[i] = i
}
for i := 0; i < len(connections); i++ {
a, b := connections[i][0], connections[i][1]
if find(fa, a) != find(fa, b) {
union(fa, a, b)
res--
}
}
return res
}
func union(fa []int, a, b int) {
fa[find(fa, a)] = find(fa, b)
}
func find(fa []int, a int) int {
for fa[a] != a {
fa[a] = fa[fa[a]]
a = fa[a]
}
return a
}
# 2
var m map[int][]int
var visited []bool
func makeConnected(n int, connections [][]int) int {
if len(connections) < n-1 {
return -1
}
m = make(map[int][]int)
visited = make([]bool, n)
for i := 0; i < len(connections); i++ {
a, b := connections[i][0], connections[i][1]
m[a] = append(m[a], b)
m[b] = append(m[b], a)
}
res := 0
for i := 0; i < n; i++ {
if visited[i] == false {
dfs(i)
res++
}
}
return res - 1
}
func dfs(i int) {
if visited[i] == true {
return
}
visited[i] = true
for j := 0; j < len(m[i]); j++ {
dfs(m[i][j])
}
}
1324.竖直打印单词(2)
给你一个字符串s。请你按照单词在 s 中的出现顺序将它们全部竖直返回。
单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。
每个单词只能放在一列上，每一列中也只能有一个单词。
示例 1：输入：s = "HOW ARE YOU" 输出：["HAY","ORO","WEU"]
解释：每个单词都应该竖直打印。
"HAY"
"ORO"
"WEU"
示例 2：输入：s = "TO BE OR NOT TO BE" 输出：["TBONTB","OEROOE"," T"]
解释：题目允许使用空格补位，但不允许输出末尾出现空格。
"TBONTB"
"OEROOE"
" T"
示例 3：输入：s = "CONTEST IS COMING" 输出：["CIC","OSO","N M","T I","E N","S G","T"]
提示：1 <= s.length <= 200
s仅含大写英文字母。
题目数据保证两个单词之间只有一个空格。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(n) |
func printVertically(s string) []string {
arr := strings.Split(s, " ")
n := len(arr)
maxLength := 0
for i := 0; i < n; i++ {
if len(arr[i]) > maxLength {
maxLength = len(arr[i])
}
}
temp := make([][]byte, maxLength)
for i := 0; i < maxLength; i++ {
temp[i] = make([]byte, n)
for j := 0; j < n; j++ {
temp[i][j] = ' '
}
}
for i := 0; i < n; i++ {
for j := 0; j < len(arr[i]); j++ {
temp[j][i] = arr[i][j]
}
}
res := make([]string, 0)
for i := 0; i < len(temp); i++ {
res = append(res, strings.TrimRight(string(temp[i]), " "))
}
return res
}
# 2
func printVertically(s string) []string {
arr := strings.Split(s, " ")
n := len(arr)
maxLength := 0
for i := 0; i < n; i++ {
if len(arr[i]) > maxLength {
maxLength = len(arr[i])
}
}
res := make([]string, 0)
for i := 0; i < maxLength; i++ {
temp := make([]byte, 0)
for j := 0; j < len(arr); j++ {
if len(res) < len(arr[j]) {
temp = append(temp, arr[j][i])
} else {
temp = append(temp, ' ')
}
}
res = append(res, strings.TrimRight(string(temp), " "))
}
return res
}
1325.删除给定值的叶子节点(1)
给你一棵以root为根的二叉树和一个整数target，请你删除所有值为target 的叶子节点 。
注意，一旦删除值为target的叶子节点，它的父节点就可能变成叶子节点；
如果新叶子节点的值恰好也是target ，那么这个节点也应该被删除。
也就是说，你需要重复此过程直到不能继续删除。
示例 1：输入：root = [1,2,3,2,null,2,4], target = 2 输出：[1,null,3,null,4]
解释：上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），
它们会被删除，得到中间的图。
有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。
示例 2：输入：root = [1,3,3,3,2], target = 3 输出：[1,3,null,null,2]
示例 3：输入：root = [1,2,null,2,null,2], target = 2 输出：[1]
解释：每一步都删除一个绿色的叶子节点（值为 2）。
示例 4：输入：root = [1,1,1], target = 1 输出：[]
示例 5：输入：root = [1,2,3], target = 1 输出：[1,2,3]
提示：1 <= target<= 1000
每一棵树最多有 3000 个节点。
每一个节点值的范围是[1, 1000]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
if root == nil {
return root
}
root.Left = removeLeafNodes(root.Left, target)
root.Right = removeLeafNodes(root.Right, target)
if root.Left == nil && root.Right == nil && root.Val == target {
return nil
}
return root
}
1328.破坏回文串(1)
给你一个回文字符串palindrome ，请你将其中一个 字符用任意小写英文字母替换，
使得结果字符串的字典序最小，且不是回文串。
请你返回结果字符串。如果无法做到，则返回一个空串。
示例 1：输入：palindrome = "abccba" 输出："aaccba"
示例 2：输入：palindrome = "a" 输出：""
提示：1 <= palindrome.length <= 1000
palindrome只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func breakPalindrome(palindrome string) string {
if len(palindrome) < 2 {
return ""
}
for i := 0; i < len(palindrome)/2; i++ {
if palindrome[i] != 'a' {
return palindrome[:i] + "a" + palindrome[i+1:]
}
}
return palindrome[:len(palindrome)-1] + "b"
}
1329.将矩阵按对角线排序(2)
给你一个m * n的整数矩阵mat，请你将同一条对角线上的元素（从左上到右下）按升序排序后，
返回排好序的矩阵。
示例 1：输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] 输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
提示：m ==mat.length
n ==mat[i].length
1 <= m, n<= 100
1 <= mat[i][j] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(n^2log(n)) |
O(n^2) |
| 02 |
遍历 |
O(n^3) |
O(1) |
func diagonalSort(mat [][]int) [][]int {
m := make(map[int][]int)
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
m[i-j] = append(m[i-j], mat[i][j])
}
}
for _, v := range m {
sort.Ints(v)
}
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
mat[i][j] = m[i-j][0]
m[i-j] = m[i-j][1:]
}
}
return mat
}
# 2
func diagonalSort(mat [][]int) [][]int {
m, n := len(mat), len(mat[0])
for k := 0; k < min(m, n); k++ {
for i := 0; i < m-1; i++ {
for j := 0; j < n-1; j++ {
if mat[i][j] > mat[i+1][j+1] {
mat[i][j], mat[i+1][j+1] = mat[i+1][j+1], mat[i][j]
}
}
}
}
return mat
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1333.餐厅过滤器(1)
给你一个餐馆信息数组 restaurants，其中 restaurants[i] =
[idi, ratingi, veganFriendlyi, pricei, distancei]。
你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，
如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。
此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，
它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 id 从高到低排序。
简单起见， veganFriendlyi 和 veganFriendly 为 true 时取值为 1，为 false 时，取值为 0 。
示例 1：输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],
[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
输出：[3,1,5]
解释： 这些餐馆为：
餐馆 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
餐馆 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
餐馆 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
餐馆 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
餐馆 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]
在按照 veganFriendly = 1, maxPrice = 50 和 maxDistance = 10 进行过滤后，
我们得到了餐馆 3, 餐馆 1 和 餐馆 5（按评分从高到低排序）。
示例 2：输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],
[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
输出：[4,3,2,1,5]
解释：餐馆与示例 1 相同，但在 veganFriendly = 0 的过滤条件下，应该考虑所有餐馆。
示例 3：输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],
[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
输出：[4,5]
提示：1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= idi, ratingi, pricei, distancei <= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendlyi 和 veganFriendly 的值为 0 或 1 。
所有 idi 各不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(n) |
func filterRestaurants(restaurants [][]int, veganFriendly int, maxPrice int, maxDistance int) []int {
res := make([]int, 0)
arr := make([][2]int, 0)
for i := 0; i < len(restaurants); i++ {
if restaurants[i][3] > maxPrice || restaurants[i][4] > maxDistance {
continue
}
if veganFriendly == 1 {
if restaurants[i][2] == 0 {
continue
}
}
arr = append(arr, [2]int{restaurants[i][0], restaurants[i][1]})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] > arr[j][0]
}
return arr[i][1] > arr[j][1]
})
for i := 0; i < len(arr); i++ {
res = append(res, arr[i][0])
}
return res
}
1334.阈值距离内邻居最少的城市
题目
有 n个城市，按从 0 到 n-1编号。
给你一个边数组edges，其中 edges[i] = [fromi, toi, weighti]代表fromi和toi两个城市之间的双向加权边，
距离阈值是一个整数distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为distanceThreshold的城市。
如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
示例 2：输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 2 以内只有 1 个邻居城市。
提示：2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti,distanceThreshold <= 10^4
所有 (fromi, toi)都是不同的。
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
floyd |
O(n^3) |
O(n^2) |
func findTheCity(n int, edges [][]int, distanceThreshold int) int {
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = math.MaxInt32
}
arr[i][i] = 0
}
for i := 0; i < len(edges); i++ {
a, b, c := edges[i][0], edges[i][1], edges[i][2]
arr[a][b], arr[b][a] = c, c
}
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if arr[i][k] != math.MaxInt32 && arr[k][j] != math.MaxInt32 &&
arr[i][j] >= arr[i][k]+arr[k][j] {
arr[i][j] = arr[i][k] + arr[k][j]
}
}
}
}
res := -1
minCount := math.MaxInt32
for i := 0; i < n; i++ {
count := 0
for j := 0; j < n; j++ {
if arr[i][j] <= distanceThreshold && i != j {
count++
}
}
if count <= minCount {
minCount = count
res = i
}
}
return res
}
1338.数组大小减半(2)
给你一个整数数组arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回至少能删除数组中的一半整数的整数集合的最小大小。
示例 1：输入：arr = [3,3,3,3,5,5,5,2,2,7] 输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：输入：arr = [7,7,7,7,7,7] 输出：1
解释：我们只能选择集合 {7}，结果数组为空。
示例 3：输入：arr = [1,9] 输出：1
示例 4：输入：arr = [1000,1000,3,7] 输出：1
示例 5：输入：arr = [1,2,3,4,5,6,7,8,9,10] 输出：5
提示：1 <= arr.length <= 10^5
arr.length为偶数
1 <= arr[i] <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(n) |
func minSetSize(arr []int) int {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
m[arr[i]]++
}
temp := make([][2]int, 0)
for k, v := range m {
temp = append(temp, [2]int{k, v})
}
sort.Slice(temp, func(i, j int) bool {
return temp[i][1] > temp[j][1]
})
res := 0
total := 0
for i := 0; i < len(temp); i++ {
total = total + temp[i][1]
res++
if total*2 >= len(arr) {
return res
}
}
return res
}
# 2
func minSetSize(arr []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 := 0
total := 0
for i := len(temp) - 1; i >= 0; i-- {
total = total + temp[i]
res++
if total*2 >= len(arr) {
return res
}
}
return res
}
1339.分裂二叉树的最大乘积(2)
给你一棵二叉树，它的根为root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
示例 1：输入：root = [1,2,3,4,5,6] 输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）
示例 2：输入：root = [1,null,2,3,4,null,null,5,6] 输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）
示例 3：输入：root = [2,3,9,10,7,8,6,5,4,11,1] 输出：1025
示例 4：输入：root = [1,1] 输出：1
提示：每棵树最多有50000个节点，且至少有2个节点。
每个节点的值在[1, 10000]之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双递归 |
O(n) |
O(log(n)) |
| 02 |
双递归 |
O(n) |
O(log(n)) |
var sum int
var res int
func maxProduct(root *TreeNode) int {
sum = 0
res = 0
dfsSum(root)
dfs(root)
return res % 1000000007
}
func dfsSum(root *TreeNode) {
if root == nil {
return
}
sum = sum + root.Val
dfsSum(root.Left)
dfsSum(root.Right)
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
res = max(res, left*(sum-left))
res = max(res, right*(sum-right))
return left + right + root.Val
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var sum int
var target int
func maxProduct(root *TreeNode) int {
sum = 0
target = 0
dfsSum(root)
dfs(root)
return target * (sum - target) % 1000000007
}
func dfsSum(root *TreeNode) {
if root == nil {
return
}
sum = sum + root.Val
dfsSum(root.Left)
dfsSum(root.Right)
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
total := left + right + root.Val
if abs(sum-2*total) < abs(sum-2*target) {
target = total
}
return total
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
1343.大小为K且平均值大于等于阈值的子数组数目(2)
给你一个整数数组arr和两个整数 k和 threshold。
请你返回长度为 k且平均值大于等于threshold的子数组数目。
示例 1：输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。
其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
示例 2：输入：arr = [1,1,1,1,1], k = 1, threshold = 0 输出：5
示例 3：输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
示例 4：输入：arr = [7,7,7,7,7,7,7], k = 7, threshold = 7 输出：1
示例 5：输入：arr = [4,4,4,4], k = 4, threshold = 1 输出：1
提示：1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
func numOfSubarrays(arr []int, k int, threshold int) int {
n := len(arr)
temp := make([]int, n+1)
for i := 1; i <= n; i++ {
temp[i] = temp[i-1] + arr[i-1]
}
res := 0
target := k * threshold
for i := k; i <= n; i++ {
if temp[i]-temp[i-k] >= target {
res++
}
}
return res
}
# 2
func numOfSubarrays(arr []int, k int, threshold int) int {
n := len(arr)
sum := 0
for i := 0; i < k; i++ {
sum = sum + arr[i]
}
res := 0
target := k * threshold
if sum >= target {
res++
}
for i := k; i < n; i++ {
sum = sum + arr[i] - arr[i-k]
if sum >= target {
res++
}
}
return res
}
1344.时钟指针的夹角(1)
给你两个数hour和minutes。请你返回在时钟上，由给定时间的时针和分针组成的较小角的角度（60 单位制）。
示例 1：输入：hour = 12, minutes = 30 输出：165
示例 2：输入：hour = 3, minutes = 30 输出；75
示例 3：输入：hour = 3, minutes = 15 输出：7.5
示例 4：输入：hour = 4, minutes = 50 输出：155
示例 5：输入：hour = 12, minutes = 0 输出：0
提示：1 <= hour <= 12
0 <= minutes <= 59
与标准答案误差在10^-5以内的结果都被视为正确结果。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(1) |
O(1) |
func angleClock(hour int, minutes int) float64 {
m := float64(minutes) * 6
h := float64(hour)*30 + float64(minutes)*0.5
res := math.Abs(m - h)
if res > 180 {
return 360 - res
}
return res
}
1347.制造字母异位词的最小步骤数(3)
给你两个长度相等的字符串s 和 t。每一个步骤中，你可以选择将t中的 任一字符 替换为 另一个字符。
返回使t成为s的字母异位词的最小步骤数。
字母异位词 指字母相同，但排列不同（也可能相同）的字符串。
示例 1：输出：s = "bab", t = "aba" 输出：1
提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。
示例 2：输出：s = "leetcode", t = "practice" 输出：5
提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。
示例 3：输出：s = "anagram", t = "mangaar" 输出：0
提示："anagram" 和 "mangaar" 本身就是一组字母异位词。
示例 4：输出：s = "xxyyzz", t = "xxyyzz" 输出：0
示例 5：输出：s = "friend", t = "family" 输出：4
提示：1 <= s.length <= 50000
s.length == t.length
s 和 t只包含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
| 03 |
哈希辅助 |
O(n) |
O(n) |
func minSteps(s string, t string) int {
res := 0
m := make(map[uint8]int)
for i := 0; i < len(s); i++ {
m[s[i]]++
}
for i := 0; i < len(t); i++ {
if _, ok := m[t[i]]; ok {
m[t[i]]--
} else {
m[t[i]] = -1
}
}
for _, v := range m {
if v > 0 {
res = res + v
}
}
return res
}
# 2
func minSteps(s string, t string) int {
res := 0
m := make(map[uint8]int)
for i := 0; i < len(s); i++ {
m[s[i]]++
m[t[i]]--
}
for _, v := range m {
if v > 0 {
res = res + v
}
}
return res
}
# 3
func minSteps(s string, t string) int {
res := 0
a := make(map[int]int)
b := make(map[int]int)
for i := 0; i < len(s); i++ {
a[int(s[i]-'a')]++
b[int(t[i]-'a')]++
}
for i := 0; i < 26; i++ {
if a[i] < b[i] {
res = res + b[i] - a[i]
}
}
return res
}
1348.推文计数(1)
请你实现一个能够支持以下两种方法的推文计数类TweetCounts：
1. recordTweet(string tweetName, int time)
记录推文发布情况：用户tweetName在time（以 秒为单位）时刻发布了一条推文。
2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)
返回从开始时间startTime（以 秒 为单位）到结束时间endTime（以 秒 为单位）内，
每 分minute，时hour 或者 日day（取决于freq）内指定用户tweetName发布的推文总数。
freq的值始终为 分minute，时 hour或者日 day之一，表示获取指定用户tweetName发布推文次数的时间间隔。
第一个时间间隔始终从 startTime 开始，因此时间间隔为
[startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>,
[startTime + delta*2, startTime + delta*3>, ... ,
[startTime + delta*i,min(startTime + delta*(i+1), endTime + 1)>，
其中 i 和 delta（取决于 freq）都是非负整数。
示例：输入：["TweetCounts","recordTweet","recordTweet","recordTweet",
"getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet",
"getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],
["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]
输出：[null,null,null,null,[2],[2,1],null,[4]]
解释：
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);
//"tweet3"发布推文的时间分别是0,10和60 。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59);
//返回[2]。统计频率是每分钟（60 秒），因此只有一个有效时间间隔 [0,60>->2条推文。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60);
//返回[2,1]。统计频率是每分钟（60 秒），因此有两个有效时间间隔1)[0,60>->2条推文，和2)[60,61>->1条推文。
tweetCounts.recordTweet("tweet3", 120);
// "tweet3"发布推文的时间分别是 0, 10, 60 和 120 。
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);
//返回[4]。统计频率是每小时（3600 秒），因此只有一个有效时间间隔 [0,211>->4条推文。
提示：同时考虑recordTweet和getTweetCountsPerFrequency，最多有 10000 次操作。
0 <= time, startTime, endTime <=10^9
0 <= endTime - startTime <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
type TweetCounts struct {
m map[string][]int
}
func Constructor() TweetCounts {
return TweetCounts{m: make(map[string][]int)}
}
func (this *TweetCounts) RecordTweet(tweetName string, time int) {
this.m[tweetName] = append(this.m[tweetName], time)
}
func (this *TweetCounts) GetTweetCountsPerFrequency(freq string, tweetName string, startTime int, endTime int) []int {
per := 0
if freq == "minute" {
per = 60
} else if freq == "hour" {
per = 60 * 60
} else if freq == "day" {
per = 60 * 60 * 24
}
n := (endTime-startTime)/per + 1
res := make([]int, n)
for i := 0; i < len(this.m[tweetName]); i++ {
t := this.m[tweetName][i]
if startTime <= t && t <= endTime {
index := (t - startTime) / per
res[index]++
}
}
return res
}
1352.最后K个数的乘积(2)
请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
1.add(int num)
将数字num添加到当前数字列表的最后面。
2. getProduct(int k)
返回当前数字列表中，最后k个数字的乘积。
你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
示例：输入：
["ProductOfNumbers","add","add","add","add","add",
"getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
输出： [null,null,null,null,null,null,20,40,0,null,32]
解释：ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3); // [3]
productOfNumbers.add(0); // [3,0]
productOfNumbers.add(2); // [3,0,2]
productOfNumbers.add(5); // [3,0,2,5]
productOfNumbers.add(4); // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
提示：add 和 getProduct两种操作加起来总共不会超过40000次。
0 <= num<=100
1 <= k <= 40000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
前缀积 |
O(1) |
O(n) |
type ProductOfNumbers struct {
arr []int
}
func Constructor() ProductOfNumbers {
return ProductOfNumbers{arr: make([]int, 0)}
}
func (this *ProductOfNumbers) Add(num int) {
this.arr = append(this.arr, num)
}
func (this *ProductOfNumbers) GetProduct(k int) int {
res := 1
n := len(this.arr)
for i := n - 1; i >= n-k && i >= 0; i-- {
res = res * this.arr[i]
}
return res
}
# 2
type ProductOfNumbers struct {
arr []int
}
func Constructor() ProductOfNumbers {
return ProductOfNumbers{arr: []int{1}}
}
func (this *ProductOfNumbers) Add(num int) {
if num == 0 {
this.arr = []int{1}
return
}
num = num * this.arr[len(this.arr)-1]
this.arr = append(this.arr, num)
}
func (this *ProductOfNumbers) GetProduct(k int) int {
if k > len(this.arr)-1 {
return 0
}
return this.arr[len(this.arr)-1] / this.arr[len(this.arr)-1-k]
}
1353.最多可以参加的会议数目
题目
给你一个数组events，其中events[i] = [startDayi, endDayi]，
表示会议i开始于startDayi，结束于endDayi。
你可以在满足startDayi<= d <= endDayi中的任意一天d参加会议i。注意，一天只能参加一个会议。
请你返回你可以参加的最大会议数目。
示例 1：输入：events = [[1,2],[2,3],[3,4]] 输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2：输入：events= [[1,2],[2,3],[3,4],[1,2]] 输出：4
示例 3：输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]] 输出：4
示例 4：输入：events = [[1,100000]] 输出：1
示例 5：输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]] 输出：7
提示：1 <= events.length <= 10^5
events[i].length == 2
1 <= events[i][0] <= events[i][1] <= 10^5
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^(1/2)) |
O(1) |
1357.每隔n个顾客打折(1)
超市里正在举行打折活动，每隔n个顾客会得到 discount的折扣。
超市里有一些商品，第i种商品为products[i]且每件单品的价格为prices[i]。
结账系统会统计顾客的数目，每隔n个顾客结账时，该顾客的账单都会打折，
折扣为discount（也就是如果原本账单为x，
那么实际金额会变成x - (discount * x) / 100），然后系统会重新开始计数。
顾客会购买一些商品，product[i]是顾客购买的第i种商品，amount[i]是对应的购买该种商品的数目。
请你实现Cashier类：
Cashier(int n, int discount, int[] products, int[] prices)初始化实例对象，
参数分别为打折频率n，折扣大小 discount，超市里的商品列表 products和它们的价格 prices。
doublegetBill(int[] product, int[] amount)返回账单的实际金额（如果有打折，请返回打折后的结果）。
返回结果与标准答案误差在10^-5以内都视为正确结果。
示例 1：输入
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],
[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],
[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
输出 [null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
解释Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]); // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]); // 返回 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]); // 返回 800.0 ，账单原本为 1600.0 ，但由于该顾客是第三位顾客，他将得到 50% 的折扣，所以实际金额为 1600 - 1600 * (50 / 100) = 800 。
cashier.getBill([4],[10]); // 返回 4000.0
cashier.getBill([7,3],[10,10]); // 返回 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ，账单原本为 14700.0 ，但由于系统计数再次达到三，该顾客将得到 50% 的折扣，实际金额为 7350.0 。
cashier.getBill([2,3,5],[5,3,2]); // 返回 2500.0
提示：1 <= n <= 10^4
0 <= discount <= 100
1 <= products.length <= 200
1 <= products[i] <= 200
products列表中不会有重复的元素。
prices.length == products.length
1 <= prices[i] <= 1000
1 <= product.length <= products.length
product[i]在products出现过。
amount.length == product.length
1 <= amount[i] <= 1000
最多有1000 次对getBill函数的调用。
返回结果与标准答案误差在10^-5以内都视为正确结果。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
type Cashier struct {
n int
discount int
count int
m map[int]int
}
func Constructor(n int, discount int, products []int, prices []int) Cashier {
res := Cashier{
n: n,
discount: discount,
count: 0,
m: make(map[int]int),
}
for i := 0; i < len(products); i++ {
res.m[products[i]] = prices[i]
}
return res
}
func (this *Cashier) GetBill(product []int, amount []int) float64 {
var res int
for i := 0; i < len(product); i++ {
res = res + amount[i]*this.m[product[i]]
}
this.count++
if this.count%this.n == 0 {
this.count = 0
return float64(res*(100-this.discount)) / 100.0
}
return float64(res)
}
1358.包含所有三种字符的子字符串数目(4)
给你一个字符串 s，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都至少出现过一次的子字符串数目。
示例 1：输入：s = "abcabc" 输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为
"abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
示例 2：输入：s = "aaacb" 输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
示例 3：输入：s = "abc" 输出：1
提示：3 <= s.length <= 5 x 10^4
s只包含字符 a，b 和 c 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+二分查找 |
O(nlog(n)) |
O(n) |
| 02 |
双指针 |
O(n) |
O(1) |
| 03 |
双指针 |
O(n) |
O(1) |
| 04 |
map |
O(n) |
O(1) |
func numberOfSubstrings(s string) int {
res := 0
n := len(s)
arr := make([][3]int, n+1)
for i := 0; i < n; i++ {
for j := 0; j < 3; j++ {
arr[i+1][j] = arr[i][j]
}
value := int(s[i] - 'a')
arr[i+1][value]++
}
for i := 0; i < n; i++ {
left := i + 1
right := n
index := -1
for left <= right {
mid := left + (right-left)/2
if arr[mid][0] > arr[i][0] &&
arr[mid][1] > arr[i][1] &&
arr[mid][2] > arr[i][2] {
right = mid - 1
index = mid
} else {
left = mid + 1
}
}
if index != -1 {
res = res + n - index + 1
}
}
return res
}
# 2
func numberOfSubstrings(s string) int {
res := 0
n := len(s)
arr := [3]int{}
left := 0
right := -1
var value int
for left = 0; left < n; left++ {
for right < n && (arr[0] == 0 || arr[1] == 0 || arr[2] == 0) {
right++
if right == n {
break
}
value = int(s[right] - 'a')
arr[value]++
}
res = res + n - right
value = int(s[left] - 'a')
arr[value]--
}
return res
}
# 3
func numberOfSubstrings(s string) int {
res := 0
n := len(s)
arr := [3]int{}
var value int
i := 0
for j := 0; j < n; j++ {
value = int(s[j] - 'a')
arr[value]++
for arr[0] > 0 && arr[1] > 0 && arr[2] > 0 {
res = res + n - j
value = int(s[i] - 'a')
arr[value]--
i++
}
}
return res
}
# 4
func numberOfSubstrings(s string) int {
res := 0
n := len(s)
m := make(map[int]int)
count := 0
var value int
i := 0
for j := 0; j < n; j++ {
value = int(s[j] - 'a')
if m[value] == 0 {
count++
}
m[value]++
for count == 3 {
res = res + n - j
value = int(s[i] - 'a')
m[value]--
i++
if m[value] == 0 {
count--
}
}
}
return res
}
1361.验证二叉树(2)
二叉树上有 n个节点，按从0到 n - 1编号，其中节点i的两个子节点分别是leftChild[i]和rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗有效的二叉树时，返回true；否则返回 false。
如果节点i没有左子节点，那么leftChild[i]就等于-1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
示例 1：输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] 输出：true
示例 2：输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] 输出：false
示例 3：输入：n = 2, leftChild = [1,0], rightChild = [-1,-1] 输出：false
示例 4：输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1] 输出：false
提示：1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild[i], rightChild[i] <= n - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
层序遍历 |
O(n) |
O(n) |
| 02 |
并查集 |
O(nlog(n)) |
O(n) |
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
arr := make([]int, n)
for i := 0; i < n; i++ {
if leftChild[i] != -1 {
arr[leftChild[i]]++
}
if rightChild[i] != -1 {
arr[rightChild[i]]++
}
}
root := -1
for i := 0; i < n; i++ {
if arr[i] == 0 {
root = i
break
}
}
if root == -1 {
return false
}
visited := make(map[int]bool)
visited[root] = true
queue := make([]int, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
a, b := leftChild[node], rightChild[node]
if a != -1 {
if visited[a] == true {
return false
}
visited[a] = true
queue = append(queue, a)
}
if b != -1 {
if visited[b] == true {
return false
}
visited[b] = true
queue = append(queue, b)
}
}
return len(visited) == n
}
# 2
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
fa = Init(n)
for i := 0; i < n; i++ {
a, b := leftChild[i], rightChild[i]
if a != -1 {
if find(a) != a || query(i, a) == true {
return false
}
union(a, i)
}
if b != -1 {
if find(b) != b || query(i, b) == true {
return false
}
union(b, i)
}
}
return getCount() == 1
}
var fa []int
var count int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
count = n
return arr
}
func find(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
func union(i, j int) {
x, y := find(i), find(j)
if x != y {
fa[x] = y
count--
}
}
func query(i, j int) bool {
return find(i) == find(j)
}
func getCount() int {
return count
}
1362.最接近的因数(2)
给你一个整数num，请你找出同时满足下面全部要求的两个整数：
两数乘积等于 num + 1或num + 2
以绝对差进行度量，两数大小最接近
你可以按任意顺序返回这两个整数。
示例 1：输入：num = 8 输出：[3,3]
解释：对于 num + 1 = 9，最接近的两个因数是 3 & 3；对于 num + 2 = 10,
最接近的两个因数是 2 & 5，因此返回 3 & 3 。
示例 2：输入：num = 123 输出：[5,25]
示例 3：输入：num = 999 输出：[40,25]
提示：1 <= num <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^(1/2)) |
O(1) |
| 02 |
遍历 |
O(n^(1/2)) |
O(1) |
func closestDivisors(num int) []int {
res := []int{1, num + 1}
for i := num + 1; i <= num+2; i++ {
temp := divide(i)
if abs(temp[0]-temp[1]) < abs(res[0]-res[1]) {
res = temp
}
}
return res
}
func divide(n int) []int {
for i := int(math.Sqrt(float64(n))); i >= 0; i-- {
if n%i == 0 {
return []int{i, n / i}
}
}
return nil
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func closestDivisors(num int) []int {
res := []int{1, num + 1}
for i := int(math.Sqrt(float64(num + 2))); i >= 0; i-- {
if (num+1)%i == 0 {
return []int{i, (num + 1) / i}
}
if (num+2)%i == 0 {
return []int{i, (num + 2) / i}
}
}
return res
}
1366.通过投票对团队排名(1)
现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，
每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
排名规则如下：
参赛团队的排名次序依照其所获「排位第一」的票的多少决定。
如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
请你返回能表示按排名系统 排序后 的所有团队排名的字符串。
示例 1：输入：votes = ["ABC","ACB","ABC","ACB","ACB"] 输出："ACB"
解释：A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
B 队获得两票「排位第二」，三票「排位第三」。
C 队获得三票「排位第二」，两票「排位第三」。
由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。
示例 2：输入：votes = ["WXYZ","XYZW"] 输出："XWYZ"
解释：X 队在并列僵局打破后成为排名第一的团队。
X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W 没有获得「排位第二」。
示例 3：输入：votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
输出："ZMNAGUEDSJYLBOPHRQICWFXTVK"
解释：只有一个投票者，所以排名完全按照他的意愿。
示例 4：输入：votes = ["BCA","CAB","CBA","ABC","ACB","BAC"] 输出："ABC"
解释： A 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
B 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
C 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
完全并列，所以我们需要按照字母升序排名。
示例 5：输入：votes = ["M","M","M","M"] 输出："M"
解释：只有 M 队参赛，所以它排名第一。
提示：1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length
votes[i][j] 是英文 大写 字母
votes[i] 中的所有字母都是唯一的
votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中，其中 1 <= j < votes.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(n^2log(n)) |
O(n^2) |
type Node struct {
rank []int
teamName byte
}
func rankTeams(votes []string) string {
m := make(map[byte][]int, 0)
for i := 0; i < len(votes[0]); i++ {
team := votes[0][i]
m[team] = make([]int, len(votes[0]))
}
for _, vote := range votes {
for i := 0; i < len(vote); i++ {
m[vote[i]][i]++
}
}
arr := make([]Node, 0)
for k, v := range m {
arr = append(arr, Node{
rank: v,
teamName: k,
})
}
sort.Slice(arr, func(i, j int) bool {
for k := 0; k < len(arr[i].rank); k++ {
if arr[i].rank[k] != arr[j].rank[k] {
return arr[i].rank[k] > arr[j].rank[k]
}
}
return arr[i].teamName < arr[j].teamName
})
res := ""
for i := 0; i < len(arr); i++ {
res = res + string(arr[i].teamName)
}
return res
}
1367.二叉树中的列表(2)
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，
那么请你返回 True ，否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
示例 1：
输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。
示例 2：
输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
示例 3：
输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。
提示：
二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^2) |
O(log(n)) |
| 02 |
迭代+递归 |
O(n^2) |
O(n) |
func isSubPath(head *ListNode, root *TreeNode) bool {
if root == nil {
return false
}
return dfs(head, root) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}
func dfs(head *ListNode, root *TreeNode) bool {
if head == nil {
return true
}
if root == nil || root.Val != head.Val {
return false
}
return dfs(head.Next, root.Left) || dfs(head.Next, root.Right)
}
# 2
func isSubPath(head *ListNode, root *TreeNode) bool {
if root == nil {
return false
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node.Val == head.Val {
if dfs(head, node) == true {
return true
}
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return false
}
func dfs(head *ListNode, root *TreeNode) bool {
if head == nil {
return true
}
if root == nil || root.Val != head.Val {
return false
}
return dfs(head.Next, root.Left) || dfs(head.Next, root.Right)
}
1371.每个元音包含偶数次的最长子字符串(2)
给你一个字符串s，请你返回满足以下条件的最长子字符串的长度：
每个元音字母，即'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：输入：s = "eleetminicoworoep" 输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o各 2 个，以及 0 个 a，u 。
示例 2：输入：s = "leetcodeisgreat" 输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3： 输入：s = "bcbcbc" 输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
提示：1 <= s.length <= 5 x 10^5
s只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助+位运算 |
O(n) |
O(1) |
| 02 |
哈希辅助 |
O(n) |
O(1) |
func findTheLongestSubstring(s string) int {
res := 0
m := make(map[int]int)
m[0] = -1
status := 0
for i := 0; i < len(s); i++ {
switch s[i] {
case 'a':
status = status ^ 0b00001
case 'e':
status = status ^ 0b00010
case 'i':
status = status ^ 0b00100
case 'o':
status = status ^ 0b01000
case 'u':
status = status ^ 0b10000
}
if v, ok := m[status]; ok {
res = max(res, i-v)
} else {
m[status] = i
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func findTheLongestSubstring(s string) int {
res := 0
m := make(map[[5]int]int)
status := [5]int{}
m[status] = -1
for i := 0; i < len(s); i++ {
switch s[i] {
case 'a':
status[0] = 1 - status[0]
case 'e':
status[1] = 1 - status[1]
case 'i':
status[2] = 1 - status[2]
case 'o':
status[3] = 1 - status[3]
case 'u':
status[4] = 1 - status[4]
}
if v, ok := m[status]; ok {
res = max(res, i-v)
} else {
m[status] = i
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1372.二叉树中的最长交错路径(1)
给你一棵以root为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径的长度。
示例 1：输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1] 输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
示例 2：输入：root = [1,1,1,null,1,null,null,1,1,null,1] 输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
示例 3：输入：root = [1] 输出：0
提示：每棵树最多有50000个节点。
每个节点的值在[1, 100] 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(1) |
var res int
func longestZigZag(root *TreeNode) int {
res = 0
dfs(root, 0, 0)
return res
}
func dfs(root *TreeNode, left, right int) {
if root != nil {
res = max(res, left)
res = max(res, right)
dfs(root.Left, right+1, 0)
dfs(root.Right, 0, left+1)
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1375.灯泡开关III(2)
房间中有 n 枚灯泡，编号从 1 到 n，自左向右排成一排。最初，所有的灯都是关着的。
在 k 时刻（ k 的取值范围是 0 到 n - 1），我们打开 light[k] 这个灯。
灯的颜色要想 变成蓝色 就必须同时满足下面两个条件：
灯处于打开状态。
排在它之前（左侧）的所有灯也都处于打开状态。
请返回能够让 所有开着的 灯都 变成蓝色 的时刻 数目 。
示例 1：输入：light = [2,1,3,5,4] 输出：3
解释：所有开着的灯都变蓝的时刻分别是 1，2 和 4 。
示例 2：输入：light = [3,2,4,1,5] 输出：2
解释：所有开着的灯都变蓝的时刻分别是 3 和 4（index-0）。
示例 3：输入：light = [4,1,2,3] 输出：1
解释：所有开着的灯都变蓝的时刻是 3（index-0）。
第 4 个灯在时刻 3 变蓝。
示例 4：输入：light = [2,1,4,3,6,5] 输出：3
示例 5：输入：light = [1,2,3,4,5,6] 输出：6
提示：
n == light.length
1 <= n <= 5 * 10^4
light 是 [1, 2, ..., n] 的一个排列。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func numTimesAllBlue(light []int) int {
res := 0
sum := 0
for i := 0; i < len(light); i++ {
sum = sum + light[i]
if (i+1)*(i+2)/2 == sum {
res++
}
}
return res
}
# 2
func numTimesAllBlue(light []int) int {
res := 0
maxValue := 0
for i := 0; i < len(light); i++ {
maxValue = max(maxValue, light[i])
if maxValue == i+1 {
res++
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1376.通知所有员工所需的时间(3)
公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。
公司的总负责人通过 headID 进行标识。
在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。
对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。
公司总负责人想要向公司所有员工通告一条紧急消息。
他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。
第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，
他的所有直属下属都可以开始传播这一消息）。
返回通知所有员工这一紧急消息所需要的 分钟数 。
示例 1：输入：n = 1, headID = 0, manager = [-1], informTime = [0] 输出：0
解释：公司总负责人是该公司的唯一一名员工。
示例 2：输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出：1
解释：id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。
上图显示了公司员工的树结构。
示例 3：输入：n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
输出：21
解释：总负责人 id = 6。他将在 1 分钟内通知 id = 5 的员工。
id = 5 的员工将在 2 分钟内通知 id = 4 的员工。
id = 4 的员工将在 3 分钟内通知 id = 3 的员工。
id = 3 的员工将在 4 分钟内通知 id = 2 的员工。
id = 2 的员工将在 5 分钟内通知 id = 1 的员工。
id = 1 的员工将在 6 分钟内通知 id = 0 的员工。
所需时间 = 1 + 2 + 3 + 4 + 5 + 6 = 21 。
示例 4：输入：n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6],
informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0] 输出：3
解释：第一分钟总负责人通知员工 1 和 2 。
第二分钟他们将会通知员工 3, 4, 5 和 6 。
第三分钟他们将会通知剩下的员工。
示例 5：输入：n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914] 输出：1076
提示：
1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
如果员工 i 没有下属，informTime[i] == 0 。
题目 保证 所有员工都可以收到通知。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
| 03 |
广度优先搜索 |
O(n) |
O(n) |
var res int
var m map[int][]int
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
m = make(map[int][]int)
for i := 0; i < len(manager); i++ {
if _, ok := m[manager[i]]; ok {
m[manager[i]] = append(m[manager[i]], i)
} else {
m[manager[i]] = []int{i}
}
}
res = 0
dfs(headID, 0, informTime)
return res
}
func dfs(headID int, cost int, informTime []int) {
arr, ok := m[headID]
if !ok {
if cost > res {
res = cost
}
return
}
cost = cost + informTime[headID]
for i := 0; i < len(arr); i++ {
dfs(arr[i], cost, informTime)
}
}
# 2
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
res := 0
for i := 0; i < len(manager); i++ {
if informTime[i] == 0 {
count := 0
index := i
for index != -1 {
count = count + informTime[index]
index = manager[index]
}
res = max(res, count)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
res := 0
m := make(map[int][]int)
for i := 0; i < len(manager); i++ {
if _, ok := m[manager[i]]; ok {
m[manager[i]] = append(m[manager[i]], i)
} else {
m[manager[i]] = []int{i}
}
}
queue := make([]int, 0)
queue = append(queue, headID)
costM := make(map[int]int)
costM[headID] = 0
for len(queue) > 0 {
id := queue[0]
queue = queue[1:]
res = max(res, costM[id])
for i := 0; i < len(m[id]); i++ {
costM[m[id][i]] = informTime[id] + costM[id]
queue = append(queue, m[id][i])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1381.设计一个支持增量操作的栈(2)
请你设计一个支持下述操作的栈。
实现自定义栈类 CustomStack ：
CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，
栈在增长到 maxSize 之后则不支持 push 操作。
void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。
如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
示例：输入：
["CustomStack","push","push","pop","push","push","push",
"increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：CustomStack customStack = new CustomStack(3); // 栈是空的 []
customStack.push(1); // 栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.pop(); // 返回 2 --> 返回栈顶值 2，栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.push(3); // 栈变为 [1, 2, 3]
customStack.push(4);
// 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
customStack.increment(5, 100); // 栈变为 [101, 102, 103]
customStack.increment(2, 100); // 栈变为 [201, 202, 103]
customStack.pop();
// 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
customStack.pop(); // 返回 202 --> 返回栈顶值 202，栈变为 [201]
customStack.pop(); // 返回 201 --> 返回栈顶值 201，栈变为 []
customStack.pop(); // 返回 -1 --> 栈为空，返回 -1
提示：1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
每种方法 increment，push 以及 pop 分别最多调用 1000 次
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈实现 |
O(n) |
O(n) |
| 02 |
数组 |
O(1) |
O(n) |
type CustomStack struct {
stack []int
size int
}
func Constructor(maxSize int) CustomStack {
return CustomStack{
stack: make([]int, 0),
size: maxSize,
}
}
func (this *CustomStack) Push(x int) {
if len(this.stack) < this.size {
this.stack = append(this.stack, x)
}
}
func (this *CustomStack) Pop() int {
if len(this.stack) > 0 {
res := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
return res
}
return -1
}
func (this *CustomStack) Increment(k int, val int) {
if k > len(this.stack) {
k = len(this.stack)
}
for i := 0; i < k; i++ {
this.stack[i] = this.stack[i] + val
}
}
# 2
type CustomStack struct {
stack []int
add []int
top int
}
func Constructor(maxSize int) CustomStack {
return CustomStack{
stack: make([]int, maxSize),
add: make([]int, maxSize),
top: -1,
}
}
func (this *CustomStack) Push(x int) {
if this.top != len(this.stack)-1 {
this.top++
this.stack[this.top] = x
}
}
func (this *CustomStack) Pop() int {
if this.top == -1 {
return -1
}
res := this.stack[this.top] + this.add[this.top]
if this.top != 0 {
this.add[this.top-1] = this.add[this.top-1] + this.add[this.top]
}
this.add[this.top] = 0
this.top--
return res
}
func (this *CustomStack) Increment(k int, val int) {
index := int(math.Min(float64(k-1), float64(this.top)))
if index >= 0{
this.add[index] = this.add[index] + val
}
}
1382.将二叉搜索树变平衡(1)
给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的 。
如果有多种构造方法，请你返回任意一种。
示例：输入：root = [1,null,2,null,3,null,4,null,null] 输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
提示：树节点的数目在1到10^4之间。
树节点的值互不相同，且在1到10^5 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var arr []int
func balanceBST(root *TreeNode) *TreeNode {
arr = make([]int, 0)
dfs(root)
return build(0, len(arr)-1)
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
arr = append(arr, root.Val)
dfs(root.Right)
}
}
func build(left, right int) *TreeNode {
if left > right {
return nil
}
mid := left + (right-left)/2
return &TreeNode{
Val: arr[mid],
Left: build(left, mid-1),
Right: build(mid+1, right),
}
}
1386.安排电影院座位(2)
如上图所示，电影院的观影厅中有 n行座位，行编号从 1到 n，
且每一行内总共有 10 个座位，列编号从 1 到 10 。
给你数组reservedSeats，包含所有已经被预约了的座位。
比如说，researvedSeats[i]=[3,8]，它表示第3行第8个座位被预约了。
请你返回最多能安排多少个 4 人家庭。4 人家庭要占据同一行内连续的 4 个座位。
隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，
但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。
示例 1：输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]] 输出：4
解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。
蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。
示例 2：输入：n = 2, reservedSeats = [[2,1],[1,8],[2,6]] 输出：2
示例 3：输入：n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]] 输出：4
提示：1 <= n <= 10^9
1 <=reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1<=reservedSeats[i][0] <= n
1 <=reservedSeats[i][1] <= 10
所有reservedSeats[i] 都是互不相同的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
位运算 |
O(n) |
O(n) |
func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
m := make(map[int]map[int]bool)
for i := 0; i < len(reservedSeats); i++ {
a, b := reservedSeats[i][0], reservedSeats[i][1]
if b == 1 || b == 10 {
continue
}
if m[a] == nil {
m[a] = make(map[int]bool)
}
m[a][b] = true
}
res := 0
for _, v := range m {
flag := false
if v[2] == false && v[3] == false && v[4] == false && v[5] == false {
res++
flag = true
}
if v[6] == false && v[7] == false && v[8] == false && v[9] == false {
res++
flag = true
}
if flag == false &&
v[4] == false && v[5] == false && v[6] == false && v[7] == false {
res++
}
}
res = res + 2*(n-len(m))
return res
}
# 2
func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
m := make(map[int]int)
for i := 0; i < len(reservedSeats); i++ {
a, b := reservedSeats[i][0], reservedSeats[i][1]
if b == 1 || b == 10 {
continue
}
m[a] = m[a] | (1 << (b - 2))
}
left := 0b11110000
middle := 0b11000011
right := 0b00001111
res := (n - len(m)) * 2
for _, v := range m {
if v|left == left || v|middle == middle || v|right == right {
res++
}
}
return res
}
1387.将整数按权重排序(2)
我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：
如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1
（3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。
给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，
如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。
示例 1：输入：lo = 12, hi = 15, k = 2 输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
示例 2：输入：lo = 1, hi = 1, k = 1 输出：1
示例 3：输入：lo = 7, hi = 11, k = 4 输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。
示例 4：输入：lo = 10, hi = 20, k = 5 输出：13
示例 5：输入：lo = 1, hi = 1000, k = 777 输出：570
提示：1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(n) |
| 02 |
自定义排序+递归 |
O(nlog(n)) |
O(n) |
var m map[int]int
func getKth(lo int, hi int, k int) int {
m = make(map[int]int)
arr := make([][2]int, 0)
for i := lo; i <= hi; i++ {
arr = append(arr, [2]int{i, getCount(i)})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] < arr[j][0]
}
return arr[i][1] < arr[j][1]
})
return arr[k-1][0]
}
func getCount(i int) int {
res := 0
temp := i
for temp != 1 {
if temp%2 == 1 {
temp = temp*3 + 1
} else {
temp = temp / 2
}
res++
if value, ok := m[temp]; ok {
res = res + value
break
}
}
m[i] = res
return res
}
# 2
func getKth(lo int, hi int, k int) int {
arr := make([][2]int, 0)
for i := lo; i <= hi; i++ {
arr = append(arr, [2]int{i, getCount(i)})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] < arr[j][0]
}
return arr[i][1] < arr[j][1]
})
return arr[k-1][0]
}
func getCount(i int) int {
if i == 1 {
return 0
}
if i%2 == 1 {
return getCount(i*3+1) + 1
}
return getCount(i/2) + 1
}
1390.四因数(1)
给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。
如果数组中不存在满足题意的整数，则返回 0 。
示例：输入：nums = [21,4,7]输出：32
解释：21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。
提示：1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(1) |
func sumFourDivisors(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
sum := 0
count := 0
for j := 1; j*j <= nums[i]; j++ {
if nums[i]%j == 0 {
count++
sum = sum + j
if j*j != nums[i] {
count++
sum = sum + nums[i]/j
}
}
}
if count == 4 {
res = res + sum
}
}
return res
}
1391.检查网格中是否存在有效路径(2)
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、
一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：输入：grid = [[2,4,3],[6,5,2]] 输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。
示例 2：输入：grid = [[1,2,1],[1,2,1]] 输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。
示例 3：输入：grid = [[1,1,2]] 输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。
示例 4：输入：grid = [[1,1,1,1,1,1,3]] 输出：true
示例 5：输入：grid = [[2],[2],[2],[2],[2],[2],[6]] 输出：true
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n^2) |
| 02 |
并查集 |
O(n^2log(n)) |
O(n^2) |
func hasValidPath(grid [][]int) bool {
n, m := len(grid), len(grid[0])
arr := make([][]bool, 3*n)
for i := 0; i < 3*n; i++ {
arr[i] = make([]bool, 3*m)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
x, y := 3*i, 3*j
arr[x+1][y+1] = true
switch grid[i][j] {
case 1:
arr[x+1][y], arr[x+1][y+2] = true, true
case 2:
arr[x][y+1], arr[x+2][y+1] = true, true
case 3:
arr[x+1][y], arr[x+2][y+1] = true, true
case 4:
arr[x+1][y+2], arr[x+2][y+1] = true, true
case 5:
arr[x+1][y], arr[x][y+1] = true, true
case 6:
arr[x][y+1], arr[x+1][y+2] = true, true
}
}
}
return dfs(arr, 1, 1, 3*n-2, 3*m-2)
}
func dfs(arr [][]bool, i, j int, x, y int) bool {
if i == x && j == y {
return true
}
if i < 0 || i >= len(arr) || j < 0 || j >= len(arr[0]) || arr[i][j] == false {
return false
}
arr[i][j] = false
return dfs(arr, i-1, j, x, y) || dfs(arr, i+1, j, x, y) ||
dfs(arr, i, j-1, x, y) || dfs(arr, i, j+1, x, y)
}
# 2
func hasValidPath(grid [][]int) bool {
n, m := len(grid), len(grid[0])
fa = Init(n * m)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
index := i*m + j
if grid[i][j] == 1 || grid[i][j] == 3 || grid[i][j] == 5 {
if j > 0 && (grid[i][j-1] == 1 || grid[i][j-1] == 4 || grid[i][j-1] == 6) {
union(index, index-1)
}
}
if grid[i][j] == 2 || grid[i][j] == 5 || grid[i][j] == 6 {
if i > 0 && (grid[i-1][j] == 2 || grid[i-1][j] == 3 || grid[i-1][j] == 4) {
union(index, index-m)
}
}
}
}
return query(0, n*m-1)
}
var fa []int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func find(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
func union(i, j int) {
fa[find(i)] = find(j)
}
func query(i, j int) bool {
return find(i) == find(j)
}
1395.统计作战单位数(2)
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，
他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k]
或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例 1：输入：rating = [2,5,3,4,1] 输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
示例 2：输入：rating = [2,1,3] 输出：0
解释：根据题目条件，我们无法组建作战单位。
示例 3：输入：rating = [1,2,3,4] 输出：4
提示：n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^3) |
O(1) |
| 02 |
遍历统计 |
O(n^2) |
O(1) |
func numTeams(rating []int) int {
res := 0
n := len(rating)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if (rating[i] < rating[j] && rating[j] < rating[k]) ||
(rating[i] > rating[j] && rating[j] > rating[k]) {
res++
}
}
}
}
return res
}
# 2
func numTeams(rating []int) int {
res := 0
n := len(rating)
for i := 0; i < n; i++ {
leftMax, leftMin := 0, 0
rightMax, rightMin := 0, 0
for j := 0; j < i; j++ {
if rating[j] > rating[i] {
leftMax++
}
if rating[j] < rating[i] {
leftMin++
}
}
for j := i + 1; j < len(rating); j++ {
if rating[j] > rating[i] {
rightMin++
}
if rating[j] < rating[i] {
rightMax++
}
}
res = res + leftMin*rightMin + leftMax*rightMax
}
return res
}
1396.设计地铁系统(1)
请你实现一个类UndergroundSystem，它支持以下 3 种方法：
1.checkIn(int id, string stationName, int t)
编号为id的乘客在 t时刻进入地铁站stationName。
一个乘客在同一时间只能在一个地铁站进入或者离开。
2.checkOut(int id, string stationName, int t)
编号为id的乘客在 t时刻离开地铁站 stationName。
3.getAverageTime(string startStation, string endStation)
返回从地铁站startStation到地铁站endStation的平均花费时间。
平均时间计算的行程包括当前为止所有从startStation直接到达endStation的行程。
调用getAverageTime时，询问的路线至少包含一趟行程。
你可以假设所有对checkIn和checkOut的调用都是符合逻辑的。
也就是说，如果一个顾客在 t1时刻到达某个地铁站，那么他离开的时间t2一定满足t2 > t1。所有的事件都按时间顺序给出。
示例：输入：["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut",
"checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],
[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],
[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]
输出： [null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]
解释：
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");
// 返回 14.0。从 "Paradise"（时刻 8）到 "Cambridge"(时刻 22)的行程只有一趟
undergroundSystem.getAverageTime("Leyton", "Waterloo");
// 返回 11.0。总共有 2 躺从 "Leyton" 到 "Waterloo" 的行程，
编号为 id=45 的乘客出发于 time=3 到达于 time=15，编号为 id=27 的乘客于 time=10 出发于 time=20 到达。
所以平均时间为 ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 12.0
提示：总共最多有20000次操作。
1 <= id, t <= 10^6
所有的字符串包含大写字母，小写字母和数字。
1 <=stationName.length <= 10
与标准答案误差在10^-5以内的结果都视为正确结果。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双map |
O(1) |
O(n) |
type Node struct {
startName string
startTime int
}
type SumInfo struct {
count int
total int
}
type UndergroundSystem struct {
record map[int]Node
sum map[string]SumInfo
}
func Constructor() UndergroundSystem {
return UndergroundSystem{
record: make(map[int]Node),
sum: make(map[string]SumInfo),
}
}
func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
this.record[id] = Node{
startName: stationName,
startTime: t,
}
}
func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
key := this.record[id].startName + "=>" + stationName
node := this.sum[key]
node.count++
node.total = node.total + t - this.record[id].startTime
this.sum[key] = node
}
func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
key := startStation + "=>" + endStation
return float64(this.sum[key].total) / float64(this.sum[key].count)
}
1400.构造K个回文字符串(1)
给你一个字符串 s和一个整数 k。请你用 s字符串中 所有字符构造 k个非空 回文串。
如果你可以用s中所有字符构造k个回文字符串，那么请你返回 True，否则返回False。
示例 1：输入：s = "annabelle", k = 2 输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"
示例 2：输入：s = "leetcode", k = 3 输出：false
解释：无法用 s 中所有字符构造 3 个回文串。
示例 3：输入：s = "true", k = 4 输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。
示例 4：输入：s = "yzyzyzyzyzyzyzy", k = 2 输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。
示例 5：输入：s = "cr", k = 7 输出：false
解释：我们没有足够的字符去构造 7 个回文串。
提示：1 <= s.length <= 10^5
s中所有字符都是小写英文字母。
1 <= k <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func canConstruct(s string, k int) bool {
if k > len(s) {
return false
}
arr := [26]int{}
for i := 0; i < len(s); i++ {
arr[s[i]-'a']++
}
res := 0
for i := 0; i < len(arr); i++ {
if arr[i]%2 == 1 {
res++
}
}
return res <= k
}
1301-1400-Hard
1301.最大得分的路径数目(1)
给你一个正方形字符数组board，你从数组最右下方的字符'S'出发。
你的目标是到达数组最左上角的字符'E' ，数组剩余的部分为数字字符1, 2, ..., 9或者障碍 'X'。
在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为：路径上所有数字的和。
请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回[0, 0] 。
示例 1：输入：board = ["E23","2X2","12S"] 输出：[7,1]
示例 2：输入：board = ["E12","1X1","21S"] 输出：[4,2]
示例 3：输入：board = ["E11","XXX","11S"] 输出：[0,0]
提示：2 <= board.length == board[i].length <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
var mod = 1000000007
var dx = []int{1, 0, 1}
var dy = []int{0, 1, 1}
func pathsWithMaxScore(board []string) []int {
n := len(board)
dp := make([][][2]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][2]int, n)
}
dp[n-1][n-1][1] = 1
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if board[i][j] == 'X' {
continue
}
var value int
if board[i][j] == 'E' || board[i][j] == 'S' {
value = 0
} else {
value = int(board[i][j] - '0')
}
for k := 0; k < 3; k++ {
x := i + dx[k]
y := j + dy[k]
if x < n && y < n && dp[x][y][1] > 0 {
sum := dp[x][y][0] + value
if sum > dp[i][j][0] {
dp[i][j][0] = sum
dp[i][j][1] = dp[x][y][1]
} else if sum == dp[i][j][0] {
dp[i][j][1] = (dp[i][j][1] + dp[x][y][1]) % mod
}
}
}
}
}
return []int{dp[0][0][0], dp[0][0][1] % mod}
}
1312.让字符串成为回文串的最少插入次数(4)
给你一个字符串s，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让s成为回文串的最少操作次数。
「回文串」是正读和反读都相同的字符串。
示例 1：输入：s = "zzazz" 输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：输入：s = "mbadm" 输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：输入：s = "leetcode" 输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：输入：s = "g" 输出：0
示例 5：输入：s = "no" 输出：1
提示：1 <= s.length <= 500
s中所有字符都是小写字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n^2) |
| 03 |
动态规划 |
O(n^2) |
O(n^2) |
| 04 |
动态规划 |
O(n^2) |
O(n^2) |
func minInsertions(s string) int {
n := len(s)
t := reverse(s)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, n+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == t[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return n - dp[n][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func reverse(str string) string {
arr := []byte(str)
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
return string(arr)
}
# 2
func minInsertions(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
for k := 2; k <= n; k++ {
for i := 0; i <= n-k; i++ {
j := i + k - 1
dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
if s[i] == s[j] {
dp[i][j] = min(dp[i][j], dp[i+1][j-1])
}
}
}
return dp[0][n-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func minInsertions(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
if s[i] == s[j] {
dp[i][j] = min(dp[i][j], dp[i+1][j-1])
}
}
}
return dp[0][n-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
func minInsertions(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = 1
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return n - dp[0][n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1326.灌溉花园的最少水龙头数目(3)
在 x 轴上有一个一维的花园。花园长度为n，从点0开始，到点n结束。
花园里总共有n + 1 个水龙头，分别位于[0, 1, ..., n] 。
给你一个整数n和一个长度为n + 1 的整数数组ranges，其中ranges[i] （下标从 0 开始）表示：
如果打开点i处的水龙头，可以灌溉的区域为[i - ranges[i], i + ranges[i]]。
请你返回可以灌溉整个花园的最少水龙头数目。如果花园始终存在无法灌溉到的地方，请你返回-1。
示例 1：输入：n = 5, ranges = [3,4,1,1,0,0] 输出：1
解释：点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。
示例 2：输入：n = 3, ranges = [0,0,0,0] 输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。
示例 3：输入：n = 7, ranges = [1,2,1,0,2,1,0,1] 输出：3
示例 4：输入：n = 8, ranges = [4,0,0,0,0,0,0,0,4] 输出：2
示例 5：输入：n = 8, ranges = [4,0,0,0,4,0,0,0,4] 输出：1
提示：1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
贪心 |
O(n) |
O(n) |
| 03 |
贪心 |
O(n^2) |
O(n) |
func minTaps(n int, ranges []int) int {
arr := make([][2]int, n+1)
for i := 0; i <= n; i++ {
l := max(0, i-ranges[i])
r := min(n, i+ranges[i])
arr = append(arr, [2]int{l, r})
}
dp := make([]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = math.MaxInt32 / 10
}
dp[0] = 0
for i := 1; i <= n; i++ {
for j := 0; j < len(arr); j++ {
a, b := arr[j][0], arr[j][1]
if a < i && i <= b && dp[a]+1 < dp[i] {
dp[i] = dp[a] + 1
}
}
}
if dp[n] == math.MaxInt32/10 {
return -1
}
return dp[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minTaps(n int, ranges []int) int {
arr := make([]int, n+1)
for i := 0; i <= n; i++ {
l := max(0, i-ranges[i])
r := min(n, i+ranges[i])
arr[l] = max(arr[l], r)
}
last := 0
prev := 0
res := 0
for i := 0; i < len(arr); i++ {
if arr[i] > last {
last = arr[i]
}
if i == last && last < n {
return -1
}
if i == prev && i < n {
res++
prev = last
}
}
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
}
# 3
func minTaps(n int, ranges []int) int {
arr := make([]int, n+1)
for i := 0; i <= n; i++ {
l := max(0, i-ranges[i])
r := min(n, i+ranges[i])
for j := l; j < r; j++ {
arr[j] = max(arr[j], r)
}
}
res := 0
cur := 0
for cur < n {
if arr[cur] == 0 {
return -1
}
cur = arr[cur]
res++
}
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
}
1340.跳跃游戏V(2)
给你一个整数数组arr 和一个整数d 。每一步你可以从下标i跳到：
i + x，其中i + x < arr.length且0 < x <= d。
i - x，其中i - x >= 0且0 < x <= d。
除此以外，你从下标i 跳到下标 j需要满足：arr[i] > arr[j]且 arr[i] > arr[k]，
其中下标k是所有 i到 j之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你 最多可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。
示例 1：输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2 输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。
你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2：输入：arr = [3,3,3,3,3], d = 3 输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3：输入：arr = [7,6,5,4,3,2,1], d = 1 输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
示例 4：输入：arr = [7,1,7,1,7,1], d = 2 输出：2
示例 5：输入：arr = [66], d = 1 输出：1
提示：1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
var dp []int
func maxJumps(arr []int, d int) int {
n := len(arr)
dp = make([]int, n)
for i := 0; i < n; i++ {
dp[i] = -1
}
for i := 0; i < n; i++ {
dfs(arr, d, i)
}
res := 1
for i := 0; i < n; i++ {
res = max(res, dp[i])
}
return res
}
func dfs(arr []int, d int, index int) {
if dp[index] != -1 {
return
}
dp[index] = 1
for i := index - 1; i >= 0 && index-i <= d && arr[index] > arr[i]; i-- {
dfs(arr, d, i)
dp[index] = max(dp[index], dp[i]+1)
}
for i := index + 1; i < len(arr) && i-index <= d && arr[index] > arr[i]; i++ {
dfs(arr, d, i)
dp[index] = max(dp[index], dp[i]+1)
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
type Node struct {
index int
value int
}
func maxJumps(arr []int, d int) int {
n := len(arr)
dp := make([]int, n)
temp := make([]Node, 0)
for i := 0; i < n; i++ {
temp = append(temp, Node{index: i, value: arr[i]})
}
sort.Slice(temp, func(i, j int) bool {
if temp[i].value == temp[j].value {
return temp[i].index < temp[j].index
}
return temp[i].value < temp[j].value
})
res := 1
for i := 0; i < n; i++ {
index := temp[i].index
dp[index] = 1
for j := index - 1; j >= 0 && index-j <= d && arr[index] > arr[j]; j-- {
if dp[j] != 0 {
dp[index] = max(dp[index], dp[j]+1)
}
}
for j := index + 1; j < len(arr) && j-index <= d && arr[index] > arr[j]; j++ {
if dp[j] != 0 {
dp[index] = max(dp[index], dp[j]+1)
}
}
res = max(res, dp[index])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1354.多次求和构造目标数组(1)
给你一个整数数组target 。一开始，你有一个数组A ，它的所有元素均为 1 ，你可以执行以下操作：
令x为你数组里所有元素的和
选择满足0 <= i < target.size的任意下标i，并让A数组里下标为i处的值为x。
你可以重复该过程任意次。如果能从A开始构造出目标数组target，请你返回 True ，否则返回 False 。
示例 1：输入：target = [9,3,5] 输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5， 选择下标 2
[1, 3, 5], 和为 9， 选择下标 0
[9, 3, 5] 完成
示例 2：输入：target = [1,1,1,2] 输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。
示例 3：输入：target = [8,5] 输出：true
提示：N == target.length
1 <= target.length<= 5 * 10^4
1 <= target[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
堆 |
O(nlog(n)) |
O(n) |
func isPossible(target []int) bool {
sum := 0
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
for i := 0; i < len(target); i++ {
sum = sum + target[i]
heap.Push(&intHeap, target[i])
}
for {
curMax := heap.Pop(&intHeap).(int)
if curMax == 1 {
break
}
otherSum := sum - curMax
if curMax <= otherSum || otherSum == 0 {
return false
}
temp := curMax % otherSum
heap.Push(&intHeap, temp)
sum = sum - curMax + temp
}
return true
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1359.有效的快递序列数目(1)
给你n笔订单，每笔订单都需要快递服务。
请你统计所有有效的 收件/配送 序列的数目，
确保第 i 个物品的配送服务delivery(i) 总是在其收件服务pickup(i) 之后。
由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。
示例 1：输入：n = 1 输出：1
解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。
示例 2：输入：n = 2 输出：6
解释：所有可能的序列包括：
(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，
(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。
示例 3：输入：n = 3 输出：90
提示：1 <= n <= 500
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
var mod = 1000000007
func countOrders(n int) int {
if n == 1 {
return 1
}
res := 1
for i := 2; i <= n; i++ {
res = res * (i*2 - 1) * i % mod
}
return res
}
1363.形成三的最大倍数(1)
给你一个整数数组digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，
请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
如果无法得到答案，请返回一个空字符串。
示例 1：输入：digits = [8,1,9] 输出："981"
示例 2：输入：digits = [8,6,7,1,0] 输出："8760"
示例 3：输入：digits = [1] 输出：""
示例 4：输入：digits = [0,0,0,0,0,0] 输出："0"
提示：1 <= digits.length <= 10^4
0 <= digits[i] <= 9
返回的结果不应包含不必要的前导零。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func largestMultipleOfThree(digits []int) string {
arr, arr3 := [10]int{}, [3]int{}
var sum, index, count int
for i := 0; i < len(digits); i++ {
arr[digits[i]]++
arr3[digits[i]%3]++
sum = sum + digits[i]
}
if sum%3 == 1 {
if arr3[1] >= 1 {
index = 1
count = 1
} else {
index = 2
count = 2
}
} else if sum%3 == 2 {
if arr3[2] >= 1 {
index = 2
count = 1
} else {
index = 1
count = 2
}
}
res := make([]byte, 0)
for i := 0; i <= 9; i++ {
for j := 0; j < arr[i]; j++ {
if count > 0 && i%3 == index {
count--
} else {
res = append(res, byte('0'+i))
}
}
}
sort.Slice(res, func(i, j int) bool {
return res[i] > res[j]
})
if len(res) > 0 && res[0] == '0' {
return "0"
}
return string(res)
}
1368.使网格图至少有一条有效路径的最小代价(3)
给你一个 m x n 的网格图grid。grid中每个格子都有一个数字，对应着从该格子出发下一步走的方向。grid[i][j]中的数字可能为以下几种情况：
1，下一步往右走，也就是你会从 grid[i][j]走到 grid[i][j + 1]
2，下一步往左走，也就是你会从 grid[i][j]走到 grid[i][j - 1]
3，下一步往下走，也就是你会从 grid[i][j]走到 grid[i + 1][j]
4，下一步往上走，也就是你会从 grid[i][j]走到 grid[i - 1][j]
注意网格图中可能会有无效数字，因为它们可能指向grid以外的区域。
一开始，你会从最左上角的格子(0,0)出发。我们定义一条有效路径为从格子(0,0)出发，
每一步都顺着数字对应方向走，最终在最右下角的格子(m - 1, n - 1)结束的路径。有效路径不需要是最短路径。
你可以花费cost = 1的代价修改一个格子中的数字，但每个格子中的数字只能修改一次。
请你返回让网格图至少有一条有效路径的最小代价。
示例 1：输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] 输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.
示例 2：输入：grid = [[1,1,3],[3,2,2],[1,1,4]] 输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
示例 3：输入：grid = [[1,2],[4,3]] 输出：1
示例 4：输入：grid = [[2,2,2],[2,2,2]] 输出：3
示例 5：输入：grid = [[4]] 输出：0
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
Dijkstra |
O(n^2log(n)) |
O(n^2) |
| 02 |
广度优先搜索-双端队列 |
O(n^2) |
O(n^2) |
| 03 |
广度优先搜索 |
O(n^2) |
O(n^2) |
var dx = []int{0, 0, 1, -1}
var dy = []int{1, -1, 0, 0}
func minCost(grid [][]int) int {
n, m := len(grid), len(grid[0])
total := n * m
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
for j := 0; j < m; j++ {
arr[i][j] = total
}
}
arr[0][0] = 0
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, []int{0, 0, 0})
visited := make(map[[2]int]bool)
for intHeap.Len() > 0 {
node := heap.Pop(&intHeap).([]int)
v, a, b := node[0], node[1], node[2]
if visited[[2]int{a, b}] == true {
continue
}
visited[[2]int{a, b}] = true
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m {
dis := v
if i+1 != grid[a][b] {
dis++
}
if dis < arr[x][y] {
arr[x][y] = dis
heap.Push(&intHeap, []int{dis, x, y})
}
}
}
}
return arr[n-1][m-1]
}
type IntHeap [][]int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([]int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
# 2
var dx = []int{0, 0, 1, -1}
var dy = []int{1, -1, 0, 0}
func minCost(grid [][]int) int {
n, m := len(grid), len(grid[0])
total := n * m
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
for j := 0; j < m; j++ {
arr[i][j] = total
}
}
arr[0][0] = 0
visited := make(map[[2]int]bool)
deque := make([][]int, 0)
deque = append(deque, []int{0, 0})
for len(deque) > 0 {
node := deque[0]
deque = deque[1:]
a, b := node[0], node[1]
if visited[[2]int{a, b}] == true {
continue
}
visited[[2]int{a, b}] = true
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m {
dis := arr[a][b]
if i+1 != grid[a][b] {
dis = dis + 1
}
if dis < arr[x][y] {
arr[x][y] = dis
if i+1 == grid[a][b] {
deque = append([][]int{{x, y}}, deque...)
} else {
deque = append(deque, []int{x, y})
}
}
}
}
}
return arr[n-1][m-1]
}
# 3
var dx = []int{0, 0, 1, -1}
var dy = []int{1, -1, 0, 0}
func minCost(grid [][]int) int {
n, m := len(grid), len(grid[0])
total := n * m
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
for j := 0; j < m; j++ {
arr[i][j] = total
}
}
arr[0][0] = 0
queue := make([][]int, 0)
queue = append(queue, []int{0, 0})
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
a, b := node[0], node[1]
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m {
dis := arr[a][b]
if i+1 != grid[a][b] {
dis = dis + 1
}
if dis < arr[x][y] {
arr[x][y] = dis
queue = append(queue, []int{x, y})
}
}
}
}
return arr[n-1][m-1]
}
1373.二叉搜索子树的最大键值和(1)
给你一棵以root为根的二叉树，请你返回 任意二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
任意节点的左子树中的键值都小于此节点的键值。
任意节点的右子树中的键值都 大于此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。
示例 1：输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6] 输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。
示例 2：输入：root = [4,3,null,1,2] 输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。
示例 3：输入：root = [-4,-2,-5] 输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。
示例 4：输入：root = [2,1,3] 输出：6
示例 5：输入：root = [5,4,8,3,null,6,3] 输出：7
提示：每棵树有 1 到 40000个节点。
每个节点的键值在[-4 * 10^4, 4 * 10^4] 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
var res int
func maxSumBST(root *TreeNode) int {
res = 0
dfs(root)
return res
}
func dfs(root *TreeNode) (bool, int, int, int) {
if root == nil {
return true, 0, math.MaxInt32, math.MinInt32
}
leftOk, leftValue, leftMin, leftMax := dfs(root.Left)
rightOk, rightValue, rightMin, rightMax := dfs(root.Right)
if leftOk == false || rightOk == false || root.Val <= leftMax || root.Val >= rightMin {
return false, 0, 0, 0
}
sum := root.Val + leftValue + rightValue
res = max(res, sum)
return true, sum, min(root.Val, leftMin), max(root.Val, rightMax)
}
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
}
1377.T秒后青蛙的位置(2)
给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：
在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
青蛙无法跳回已经访问过的顶点。
如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 描述，其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边
返回青蛙在 t 秒后位于目标顶点 target 上的概率。
示例 1：输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出：0.16666666666666666
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 1 秒 有 1/3 的概率跳到顶点 2 ，
然后第 2 秒 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。
示例 2：输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 输出：0.3333333333333333
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。
示例 3：输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
输出：0.16666666666666666
提示：1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t<= 50
1 <= target<= n
与准确值误差在 10^-5 之内的结果将被判定为正确。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n) |
O(n) |
| 02 |
广度优先搜索 |
O(n) |
O(n) |
var arr [][]int
var res []float64
func frogPosition(n int, edges [][]int, t int, target int) float64 {
arr = make([][]int, n+1)
res = make([]float64, n+1)
res[1] = 1
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+1)
visited[1] = true
dfs(1, t, visited)
return res[target]
}
func dfs(start int, t int, visited []bool) {
if t <= 0 {
return
}
count := 0
for i := 0; i < len(arr[start]); i++ {
next := arr[start][i]
if visited[next] == false {
count++
}
}
if count == 0 {
return
}
per := res[start] / float64(count)
for i := 0; i < len(arr[start]); i++ {
next := arr[start][i]
if visited[next] == false {
visited[next] = true
res[start] = res[start] - per
res[next] = res[next] + per
dfs(next, t-1, visited)
visited[next] = false
}
}
}
# 2
func frogPosition(n int, edges [][]int, t int, target int) float64 {
arr := make([][]int, n+1)
res := make([]float64, n+1)
res[1] = 1
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+1)
queue := make([]int, 0)
queue = append(queue, 1)
count := 0
for len(queue) > 0 {
length := len(queue)
if count == t {
break
}
for i := 0; i < length; i++ {
start := queue[i]
visited[start] = true
count := 0
for j := 0; j < len(arr[start]); j++ {
next := arr[start][j]
if visited[next] == false {
count++
}
}
if count == 0 {
continue
}
per := res[start] / float64(count)
for j := 0; j < len(arr[start]); j++ {
next := arr[start][j]
if visited[next] == false {
res[start] = res[start] - per
res[next] = res[next] + per
queue = append(queue, next)
}
}
}
queue = queue[length:]
count++
}
return res[target]
}
1383.最大的团队表现值(1)
公司有编号为 1到 n的 n个工程师，给你两个数组 speed和 efficiency，
其中 speed[i]和 efficiency[i]分别代表第 i位工程师的速度和效率。
请你返回由最多k个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。
团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
示例 1：输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 输出：60
解释：我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。
他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
示例 2：输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3 输出：68
解释：此示例与第一个示例相同，除了 k = 3 。
我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。
表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
示例 3：输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4 输出：72
提示：1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
堆 |
O(nlog(n)) |
O(n) |
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
arr := make([]Node, 0)
for i := 0; i < len(speed); i++ {
arr = append(arr, Node{
speed: speed[i],
efficiency: efficiency[i],
})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i].efficiency == arr[j].efficiency {
return arr[i].speed > arr[j].speed
}
return arr[i].efficiency > arr[j].efficiency
})
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
res := 0
sum := 0
for i := 0; i < len(arr); i++ {
s := arr[i].speed
e := arr[i].efficiency
sum = sum + s
heap.Push(&intHeap, s)
if intHeap.Len() > k {
value := heap.Pop(&intHeap).(int)
sum = sum - value
}
res = max(res, sum*e)
}
return res % 1000000007
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type Node struct {
speed int
efficiency int
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1388.3n块披萨(2)
给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
你挑选 任意一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices表示。
请你返回你可以获得的披萨大小总和的最大值。
示例 1：输入：slices = [1,2,3,4,5,6] 输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。
然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。
示例 2：输入：slices = [8,9,8,6,1,1] 输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。
示例 3：输入：slices = [4,1,2,5,8,3,1,9,7] 输出：21
示例 4：输入：slices = [3,1,2] 输出：3
提示：1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
堆 |
O(nlog(n)) |
O(n) |
func maxSizeSlices(slices []int) int {
a := calculate(slices[1:])
b := calculate(slices[:len(slices)-1])
return max(a, b)
}
func calculate(slices []int) int {
n := len(slices)
target := (n + 1) / 3
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, target+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= target; j++ {
var a, b int
if 2 <= i {
a = dp[i-2][j-1]
}
a = a + slices[i-1]
b = dp[i-1][j]
dp[i][j] = max(a, b)
}
}
return dp[n][target]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var m map[int][2]int
func maxSizeSlices(slices []int) int {
n := len(slices)
target := n / 3
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
m = make(map[int][2]int)
for i := 0; i < n; i++ {
left := (i - 1 + n) % n
right := (i + 1) % n
m[i] = [2]int{left, right}
heap.Push(&intHeap, [2]int{slices[i], i})
}
res := 0
visited := make([]bool, n)
for i := 0; i < target; {
top := heap.Pop(&intHeap).([2]int)
value, index := top[0], top[1]
if visited[index] == true {
continue
}
i++
left, right := m[index][0], m[index][1]
visited[left], visited[right] = true, true
res = res + value
slices[index] = slices[left] + slices[right] - value
heap.Push(&intHeap, [2]int{slices[index], index})
reconnect(left)
reconnect(right)
}
return res
}
func reconnect(index int) {
left, right := m[index][0], m[index][1]
m[right] = [2]int{left, m[right][1]}
m[left] = [2]int{m[left][0], right}
}
type IntHeap [][2]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][0] > h[j][0]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}