1501-1600-Easy
1502.判断能否形成等差数列(2)
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：输入：arr = [3,5,1] 输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：输入：arr = [1,2,4] 输出：false
解释：无法通过重新排序得到等差数列。
提示：
2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(1) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func canMakeArithmeticProgression(arr []int) bool {
sort.Ints(arr)
diff := arr[1] - arr[0]
for i := 2; i < len(arr); i++ {
if arr[i]-arr[i-1] != diff {
return false
}
}
return true
}
#
func canMakeArithmeticProgression(arr []int) bool {
min, max := arr[0], arr[0]
m := make(map[int]bool)
for i := 0; i < len(arr); i++ {
if arr[i] <= min {
min = arr[i]
}
if arr[i] >= max {
max = arr[i]
}
m[arr[i]] = true
}
diff := (max - min) / (len(arr) - 1)
for i := 0; i < len(m); i++ {
value := min + diff*i
if _, ok := m[value]; !ok {
return false
}
}
return true
}
1507.转变日期格式(1)
给你一个字符串 date ，它的格式为 Day Month Year ，其中：
Day 是集合 {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"} 中的一个元素。
Month 是集合 {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul",
"Aug", "Sep", "Oct", "Nov", "Dec"} 中的一个元素。
Year 的范围在 [1900, 2100] 之间。
请你将字符串转变为 YYYY-MM-DD 的格式，其中：
YYYY 表示 4 位的年份。
MM 表示 2 位的月份。
DD 表示 2 位的天数。
示例 1：输入：date = "20th Oct 2052" 输出："2052-10-20"
示例 2：输入：date = "6th Jun 1933" 输出："1933-06-06"
示例 3：输入：date = "26th May 1960" 输出："1960-05-26"
提示： 给定日期保证是合法的，所以不需要处理异常输入。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-内置函数 |
O(n) |
O(n) |
func reformatDate(date string) string {
month := []string{"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}
arr := strings.Split(date, " ")
res := arr[2] + "-"
for i := 1; i < len(month); i++ {
if month[i] == arr[1] {
res = res + fmt.Sprintf("%02d", i) + "-"
}
}
if len(arr[0]) == 3 {
res = res + "0" + arr[0][:1]
} else {
res = res + arr[0][:2]
}
return res
}
1512.好数对的数目(3)
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：输入：nums = [1,2,3,1,1,3] 输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：输入：nums = [1,1,1,1] 输出：6
解释：数组中的每组数字都是好数对
示例 3：输入：nums = [1,2,3] 输出：0
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(1) |
| 03 |
哈希辅助 |
O(n) |
O(1) |
func numIdenticalPairs(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] == nums[j] {
res++
}
}
}
return res
}
#
func numIdenticalPairs(nums []int) int {
res := 0
arr := make([]int, 101)
for i := 0; i < len(nums); i++ {
res = res + arr[nums[i]]
arr[nums[i]]++
}
return res
}
#
func numIdenticalPairs(nums []int) int {
res := 0
m := make(map[int]int, 101)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for _, v := range m {
if v > 0 {
res = res + v*(v-1)/2
}
}
return res
}
1518.换酒问题(2)
小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
请你计算 最多 能喝到多少瓶酒。
示例 1：输入：numBottles = 9, numExchange = 3 输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
示例 2：输入：numBottles = 15, numExchange = 4 输出：19
解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
示例 3：输入：numBottles = 5, numExchange = 5 输出：6
示例 4：输入：numBottles = 2, numExchange = 3 输出：2
提示：
1 <= numBottles <= 100
2 <= numExchange <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
计算 |
O(1) |
O(1) |
func numWaterBottles(numBottles int, numExchange int) int {
res := numBottles
for numBottles > 0 {
times := numBottles / numExchange
res = res + times
numBottles = numBottles%numExchange + times
if numBottles < numExchange {
break
}
}
return res
}
#
func numWaterBottles(numBottles int, numExchange int) int {
return numBottles + (numBottles-1)/(numExchange-1)
}
1523.在区间范围内统计奇数数目(2)
给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
示例 1：输入：low = 3, high = 7 输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：输入：low = 8, high = 10输出：1
解释：8 到 10 之间奇数数字为 [9] 。
提示：0 <= low <= high <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(1) |
O(1) |
| 02 |
数学 |
O(1) |
O(1) |
func countOdds(low int, high int) int {
if low%2 == 1 {
low = low - 1
}
if high%2 == 1 {
high = high + 1
}
return (high - low) / 2
}
#
func countOdds(low int, high int) int {
if low%2 == 0 && high%2 == 0 {
return (high - low) / 2
}
return (high-low)/2 + 1
}
1528.重新排列字符串(1)
给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3] 输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。
示例 2：输入：s = "abc", indices = [0,1,2] 输出："abc"
解释：重新排列后，每个字符都还留在原来的位置上。
示例 3：输入：s = "aiohn", indices = [3,1,4,2,0] 输出："nihao"
示例 4：输入：s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]输出："arigatou"
示例 5：输入：s = "art", indices = [1,0,2] 输出："rat"
提示：
s.length == indices.length == n
1 <= n <= 100
s 仅包含小写英文字母。
0 <= indices[i] < n
indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func restoreString(s string, indices []int) string {
arr := []byte(s)
res := make([]byte, len(s))
for i := 0; i < len(indices); i++ {
res[indices[i]] = arr[i]
}
return string(res)
}
1534.统计好三元组(2)
给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
其中 |x| 表示 x 的绝对值。
返回 好三元组的数量 。
示例 1：输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3 输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。
示例 2：输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1 输出：0
解释：不存在满足所有条件的三元组。
提示：
3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^3) |
O(1) |
| 02 |
遍历 |
O(n^3) |
O(1) |
func countGoodTriplets(arr []int, a int, b int, c int) int {
res := 0
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
for k := j + 1; k < len(arr); k++ {
if abs(arr[i], arr[j]) <= a &&
abs(arr[j], arr[k]) <= b &&
abs(arr[i], arr[k]) <= c {
res++
}
}
}
}
return res
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
#
func countGoodTriplets(arr []int, a int, b int, c int) int {
res := 0
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if abs(arr[i], arr[j]) > a {
continue
}
for k := j + 1; k < len(arr); k++ {
if abs(arr[j], arr[k]) <= b &&
abs(arr[i], arr[k]) <= c {
res++
}
}
}
}
return res
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
1539.第k个缺失的正整数(3)
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
示例 1：输入：arr = [2,3,4,7,11], k = 5 输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
示例 2：输入：arr = [1,2,3,4], k = 2 输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
提示：1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
| 03 |
二分查找 |
O(log(n)) |
O(1) |
func findKthPositive(arr []int, k int) int {
start := 1
i := 0
for {
if i < len(arr) && arr[i] == start {
i++
} else {
k--
if k == 0 {
return start
}
}
start++
}
}
# 2
func findKthPositive(arr []int, k int) int {
for i := 0; i < len(arr); i++ {
if arr[i]-(i+1) >= k {
return k + i
}
}
return k + len(arr)
}
# 3
func findKthPositive(arr []int, k int) int {
left := 0
right := len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid]-(mid+1) >= k {
right = mid
} else {
left = mid + 1
}
}
return k + left
}
1544.整理字符串(1)
给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：
0 <= i <= s.length - 2
s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
示例 1：输入：s = "leEeetcode" 输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。
示例 2：输入：s = "abBAcC" 输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
示例 3：输入：s = "s"输出："s"
提示： 1 <= s.length <= 100
s 只包含小写和大写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈辅助 |
O(n) |
O(n) |
func makeGood(s string) string {
if len(s) <= 1 {
return s
}
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
stack = append(stack, s[i])
if len(stack) > 1 {
length := len(stack)
if stack[length-1]-'A'+'a' == stack[length-2] ||
stack[length-1]-'a'+'A' == stack[length-2] {
stack = stack[:length-2]
}
}
}
return string(stack)
}
1550.存在连续三个奇数的数组(2)
给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：
如果存在，请返回 true ；否则，返回 false 。
示例 1：输入：arr = [2,6,4,1] 输出：false
解释：不存在连续三个元素都是奇数的情况。
示例 2：输入：arr = [1,2,34,3,4,5,7,23,12] 输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。
提示： 1 <= arr.length <= 1000
1 <= arr[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func threeConsecutiveOdds(arr []int) bool {
for i := 0; i < len(arr)-2; i++ {
if arr[i]%2 == 1 && arr[i+1]%2 == 1 && arr[i+2]%2 == 1 {
return true
}
}
return false
}
# 2
func threeConsecutiveOdds(arr []int) bool {
count := 0
for i := 0; i < len(arr); i++ {
if arr[i]%2 == 1 {
count++
} else {
count = 0
}
if count == 3 {
return true
}
}
return false
}
1556.千位分隔数(1)
给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。
示例 1：输入：n = 987 输出："987"
示例 2：输入：n = 1234 输出："1.234"
示例 3：输入：n = 123456789 输出："123.456.789"
示例 4：输入：n = 0 输出："0"
提示： 0 <= n < 2^31
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func thousandSeparator(n int) string {
res := ""
if n == 0 {
return "0"
}
count := 0
for n != 0 {
count++
value := n % 10
if count%3 == 1 {
res = strconv.Itoa(value) + "." + res
} else {
res = strconv.Itoa(value) + res
}
n = n / 10
}
return strings.Trim(res, ".")
}
1560.圆形赛道上经过次数最多的扇区(2)
给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。
现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。
其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。
举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。
请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。
注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。
示例 1：输入：n = 4, rounds = [1,3,1,2] 输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）--> 4 --> 1（阶段 2 结束）--> 2
（阶段 3 结束，即本场马拉松结束）其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。
扇区 3 和 4 都只经过了一次。
示例 2：输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2] 出：[2]
示例 3：输入：n = 7, rounds = [1,3,5,7] 出：[1,2,3,4,5,6,7]
提示：
2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] ，其中 0 <= i < m
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组模拟 |
O(n^2) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func mostVisited(n int, rounds []int) []int {
arr := make([]int, n+1)
res := make([]int, 0)
max := 0
arr[rounds[0]]++
for i := 0; i < len(rounds)-1; i++ {
start := rounds[i]
end := rounds[i+1]
if start < end {
for j := start + 1; j <= end; j++ {
arr[j]++
}
} else {
for j := start + 1; j <= n; j++ {
arr[j]++
}
for j := 1; j <= end; j++ {
arr[j]++
}
}
}
for i := 1; i < len(arr); i++ {
if arr[i] > max {
max = arr[i]
res = make([]int, 0)
res = append(res, i)
} else if arr[i] == max {
res = append(res, i)
}
}
return res
}
# 2
func mostVisited(n int, rounds []int) []int {
res := make([]int, 0)
start := rounds[0]
end := rounds[len(rounds)-1]
if start <= end {
for i := start; i <= end; i++ {
res = append(res, i)
}
} else {
for i := 1; i <= end; i++ {
res = append(res, i)
}
for i := start; i <= n; i++ {
res = append(res, i)
}
}
return res
}
1566.重复至少K次且长度为M的模式(2)
给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。
示例 1：输入：arr = [1,2,4,4,4,4], m = 1, k = 3 输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。
示例 2：输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2 输出：true
解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。
示例 3：输入：arr = [1,2,1,2,1,3], m = 2, k = 3 输出：false
解释：模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。
示例 4：输入：arr = [1,2,3,1,2], m = 2, k = 2 输出：false
解释：模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。
示例 5：输入：arr = [2,2,2,2], m = 2, k = 3 输出：false
解释：长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。
提示： 2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n^2) |
O(1) |
func containsPattern(arr []int, m int, k int) bool {
for i := 0; i < len(arr)-m; i++ {
count := 0
j := i
for j+m <= len(arr) {
flag := true
for l := 0; l < m; l++ {
if arr[i+l] != arr[j+l] {
flag = false
break
}
}
if flag == true {
count++
j = j + m
} else {
break
}
}
if count >= k {
return true
}
}
return false
}
# 2
func containsPattern(arr []int, m int, k int) bool {
n := len(arr)
if n < m*k {
return false
}
i, j := 0, 0
for i = 0; i <= n-m*k; i++ {
for j = i + m; j < i+m*k; j++ {
if arr[j] != arr[j-m] {
break
}
}
if j == i+m*k {
return true
}
}
return false
}
1572.矩阵对角线元素的和(2)
给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
示例 1：输入：mat = [[1,2,3],
[4,5,6],
[7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。
示例 2：输入：mat = [[1,1,1,1],
[1,1,1,1],
[1,1,1,1],
[1,1,1,1]]
输出：8
示例 3：输入：mat = [[5]] 输出：5
提示：
n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func diagonalSum(mat [][]int) int {
res := 0
for i := 0; i < len(mat); i++ {
a, b := i, len(mat)-1-i
if a == b {
res = res + mat[a][b]
} else {
res = res + mat[a][a]
res = res + mat[a][b]
}
}
return res
}
# 2
func diagonalSum(mat [][]int) int {
res := 0
for i := 0; i < len(mat); i++ {
a, b := i, len(mat)-1-i
res = res + mat[a][a]
res = res + mat[a][b]
}
if len(mat)%2 == 1 {
res = res - mat[len(mat)/2][len(mat)/2]
}
return res
}
1576.替换所有的问号(1)
给你一个仅包含小写英文字母和 '?' 字符的字符串 s，
请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
注意：你 不能 修改非 '?' 字符。
题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
在完成所有转换（可能无需转换）后返回最终的字符串。
如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：输入：s = "?zs" 输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。
只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2：输入：s = "ubv?w"输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。
因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
示例 3：输入：s = "j?qg??b" 输出："jaqgacb"
示例 4：输入：s = "??yw?ipkj?" 输出："acywaipkja"
提示：1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func modifyString(s string) string {
res := []byte(s)
for i := 0; i < len(s); i++ {
if s[i] == '?' {
for j := byte('a'); j <= 'z'; j++ {
if (i == 0 || res[i-1] != j) && (i == len(s)-1 || s[i+1] != j) {
res[i] = j
break
}
}
}
}
return string(res)
}
1582.二进制矩阵中的特殊位置(2)
给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，
请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0
（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。
示例 1：输入：mat = [[1,0,0],
[0,0,1],
[1,0,0]]
输出：1
解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：输入：mat = [[1,0,0],
[0,1,0],
[0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：输入：mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
输出：2
示例 4：输入：mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
输出：3
提示：
rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] 是 0 或 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^3) |
O(1) |
| 02 |
数组辅助 |
O(n^2) |
O(n) |
func numSpecial(mat [][]int) int {
res := 0
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
if mat[i][j] == 1 && judge(mat, i, j) == true {
res++
}
}
}
return res
}
func judge(mat [][]int, i, j int) bool {
for a := 0; a < len(mat[i]); a++ {
if mat[i][a] == 1 && a != j {
return false
}
}
for a := 0; a < len(mat); a++ {
if mat[a][j] == 1 && a != i {
return false
}
}
return true
}
# 2
func numSpecial(mat [][]int) int {
res := 0
rows, cols := make([]int, len(mat)), make([]int, len(mat[0]))
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
rows[i] = rows[i] + mat[i][j]
cols[j] = cols[j] + mat[i][j]
}
}
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[i]); j++ {
if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
res++
}
}
}
return res
}
1588.所有奇数长度子数组的和(3)
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1：输入：arr = [1,4,2,5,3] 输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2：输入：arr = [1,2] 输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
示例 3：输入：arr = [10,11,12] 输出：66
提示：
1 <= arr.length <= 100
1 <= arr[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n^2) |
O(n) |
| 02 |
暴力法 |
O(n^3) |
O(1) |
| 03 |
数学 |
O(n) |
O(1) |
func sumOddLengthSubarrays(arr []int) int {
sum := make([]int, len(arr)+1)
sum[0] = 0
for i := 1; i <= len(arr); i++ {
sum[i] = sum[i-1] + arr[i-1]
}
res := 0
for i := 1; i <= len(arr); i = i + 2 {
for j := 0; j < len(arr); j++ {
k := j + i
if k <= len(arr) {
total := sum[k] - sum[j]
res = res + total
}
}
}
return res
}
# 2
func sumOddLengthSubarrays(arr []int) int {
res := 0
for i := 1; i <= len(arr); i = i + 2 {
for j := 0; j < len(arr); j++ {
k := j + i
for start := j; start < k && k <= len(arr); start++ {
res = res + arr[start]
}
}
}
return res
}
# 3
# https:
func sumOddLengthSubarrays(arr []int) int {
res := 0
n := len(arr)
for i := 0; i < n; i++ {
left := i + 1
right := n - i
leftEven := (left + 1) / 2
rightEven := (right + 1) / 2
leftOdd := left / 2
rightOdd := right / 2
res = res + arr[i]*(leftEven*rightEven+leftOdd*rightOdd)
}
return res
}
1592.重新排列单词间的空格(1)
给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，
并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。
如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，
这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
示例 1：输入：text = " this is a sentence " 输出："this is a sentence"
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：
9 / (4-1) = 3 个。
示例 2：输入：text = " practice makes perfect" 输出："practice makes perfect "
解释：总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格加上 1 个多余的空格。
多余的空格需要放在字符串的末尾。
示例 3：输入：text = "hello world" 输出："hello world"
示例 4：输入：text = " walks udp package into bar a"
输出："walks udp package into bar a "
示例 5：输入：text = "a" 输出："a"
提示： 1 <= text.length <= 100
text 由小写英文字母和 ' ' 组成
text 中至少包含一个单词
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
func reorderSpaces(text string) string {
count := strings.Count(text, " ")
arr := strings.Fields(text)
if len(arr) == 1 {
return arr[0] + strings.Repeat(" ", count)
}
value := count / (len(arr) - 1)
left := count % (len(arr) - 1)
res := strings.Join(arr, strings.Repeat(" ", value))
res = res + strings.Repeat(" ", left)
return res
}
1598.文件夹操作日志搜集器(1)
每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。
下面给出对变更操作的说明：
"../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
"./" ：继续停留在当前文件夹。
"x/" ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。
给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。
文件系统启动时位于主文件夹，然后执行 logs 中的操作。
执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。
示例 1：输入：logs = ["d1/","d2/","../","d21/","./"] 输出：2
解释：执行 "../" 操作变更文件夹 2 次，即可回到主文件夹
示例 2：输入：logs = ["d1/","d2/","./","d3/","../","d31/"] 输出：3
示例 3：输入：logs = ["d1/","../","../","../"] 输出：0
提示： 1 <= logs.length <= 103
2 <= logs[i].length <= 10
logs[i] 包含小写英文字母，数字，'.' 和 '/'
logs[i] 符合语句中描述的格式
文件夹名称由小写英文字母和数字组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈 |
O(n) |
O(n) |
func minOperations(logs []string) int {
stack := make([]string, 0)
for i := 0; i < len(logs); i++ {
if logs[i] == "../" {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else if logs[i] != "./" {
stack = append(stack, logs[i])
}
}
return len(stack)
}
1501-1600-Medium
1503.所有蚂蚁掉下来前的最后一刻(2)
有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。
其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。
假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。
两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。
示例 1：输入：n = 4, left = [4,3], right = [0,1] 输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。
（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。
示例 2：输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7] 输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。
示例 3：输入：n = 7, left = [0,1,2,3,4,5,6,7], right = [] 输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
示例 4：输入：n = 9, left = [5], right = [4] 输出：5
解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。
示例 5：输入：n = 6, left = [6], right = [0] 输出：6
提示：
1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
func getLastMoment(n int, left []int, right []int) int {
max := 0
for i := 0; i < len(left); i++ {
if left[i] > max {
max = left[i]
}
}
for i := 0; i < len(right); i++ {
if n-right[i] > max {
max = n - right[i]
}
}
return max
}
# 2
func getLastMoment(n int, left []int, right []int) int {
sort.Ints(left)
sort.Ints(right)
if len(left) == 0 {
return n - right[0]
}
if len(right) == 0 {
return left[len(left)-1]
}
if n-right[0] > left[len(left)-1] {
return n - right[0]
}
return left[len(left)-1]
}
1504.统计全1子矩形(2)
给你一个只包含 0 和 1 的rows * columns矩阵mat，请你返回有多少个子矩形的元素全部都是 1 。
示例 1：输入：mat = [[1,0,1],
[1,1,0],
[1,1,0]]
输出：13
解释：有 6个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13。
示例 2：输入：mat = [[0,1,1,0],
[0,1,1,1],
[1,1,1,0]]
输出：24
解释：有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
示例 3：输入：mat = [[1,1,1,1,1,1]] 输出：21
示例 4：输入：mat = [[1,0,1],[0,1,0],[1,0,1]] 输出：5
提示：1 <= rows<= 150
1 <= columns<= 150
0 <= mat[i][j] <= 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n^3) |
O(1) |
| 02 |
前缀和 |
O(n^3) |
O(n^2) |
func numSubmat(mat [][]int) int {
res := 0
n, m := len(mat), len(mat[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if j > 0 && mat[i][j] == 1 {
mat[i][j] = mat[i][j-1] + 1
}
target := mat[i][j]
for k := i; k >= 0; k-- {
if target > mat[k][j] {
target = mat[k][j]
}
res = res + target
}
}
}
return res
}
# 2
func numSubmat(mat [][]int) int {
res := 0
n, m := len(mat), len(mat[0])
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if j == 0 {
arr[i][j] = mat[i][j]
} else if j > 0 && mat[i][j] == 1 {
arr[i][j] = arr[i][j-1] + 1
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
target := arr[i][j]
for k := i; k >= 0; k-- {
if target > arr[k][j] {
target = arr[k][j]
}
res = res + target
}
}
}
return res
}
1508.子数组和排序后的区间和(1)
给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，
得到一个新的包含 n * (n + 1) / 2 个数字的数组。
请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：输入：nums = [1,2,3,4], n = 4, left = 1, right = 5 输出：13
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。
将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。
下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。
示例 2：输入：nums = [1,2,3,4], n = 4, left = 3, right = 4 输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。
下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。
示例 3：输入：nums = [1,2,3,4], n = 4, left = 1, right = 10 输出：50
提示：
1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2log(n)) |
O(n^2) |
func rangeSum(nums []int, n int, left int, right int) int {
arr := make([]int, 0)
for i := 0; i < len(nums); i++ {
sum := 0
for j := i; j < len(nums); j++ {
sum = sum + nums[j]
arr = append(arr, sum)
}
}
sort.Ints(arr)
res := 0
for i := left - 1; i <= right-1; i++ {
res = (res + arr[i]) % 1000000007
}
return res
}
1509.三次操作后最大值与最小值的最小差(2)
给你一个数组 nums ，每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。
请你返回三次操作后， nums 中最大值与最小值的差的最小值。
示例 1：输入：nums = [5,3,2,4] 输出：0
解释：将数组 [5,3,2,4] 变成 [2,2,2,2].
最大值与最小值的差为 2-2 = 0 。
示例 2：输入：nums = [1,5,0,10,14] 输出：1
解释：将数组 [1,5,0,10,14] 变成 [1,1,0,1,1] 。
最大值与最小值的差为 1-0 = 1 。
示例 3：输入：nums = [6,6,0,1,1,4,6] 输出：2
示例 4：输入：nums = [1,5,6,14,15] 输出：1
提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
func minDifference(nums []int) int {
if len(nums) < 5 {
return 0
}
sort.Ints(nums)
res := math.MaxInt32
for i := 0; i <= 3; i++ {
res = min(res, nums[len(nums)-1-(3-i)]-nums[i])
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
#
func minDifference(nums []int) int {
if len(nums) < 5 {
return 0
}
sort.Ints(nums)
res := math.MaxInt32
res = min(res, nums[len(nums)-1]-nums[3])
res = min(res, nums[len(nums)-2]-nums[2])
res = min(res, nums[len(nums)-3]-nums[1])
res = min(res, nums[len(nums)-4]-nums[0])
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
1513.仅含1的子串数(2)
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：输入：s = "0110111" 输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
示例 2：输入：s = "101" 输出：2
解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：输入：s = "111111" 输出：21
解释：每个子字符串都仅由 '1' 组成
示例 4：输入：s = "000" 输出：0
提示：
s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func numSub(s string) int {
res := 0
count := 0
for i := 0; i < len(s); i++ {
if s[i] == '1' {
count++
} else {
res = (res + (count+1)*count/2) % 1000000007
count = 0
}
}
if count > 0 {
res = (res + (count+1)*count/2) % 1000000007
}
return res
}
#
func numSub(s string) int {
res := 0
count := 0
for i := 0; i < len(s); i++ {
if s[i] == '1' {
count++
} else {
count = 0
}
res = (res + count) % 1000000007
}
return res
}
1514.概率最大的路径(2)
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，
其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，
就会被视作正确答案。
示例 1：
输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
示例 2：
输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000
示例 3：输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径
提示：2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
Dijkstra-堆 |
O(nlog(n)) |
O(n) |
| 02 |
Dijkstra |
O(n^2) |
O(n) |
func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
arr := make([][]Node, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], Node{index: b, Value: succProb[i]})
arr[b] = append(arr[b], Node{index: a, Value: succProb[i]})
}
visited := make([]bool, n)
maxValue := make([]float64, n)
nodeHeap := make(NodeHeap, 0)
heap.Init(&nodeHeap)
heap.Push(&nodeHeap, Node{
Value: 1,
index: start,
})
for nodeHeap.Len() > 0 {
node := heap.Pop(&nodeHeap).(Node)
visited[node.index] = true
if node.index == end {
return node.Value
}
for i := 0; i < len(arr[node.index]); i++ {
next := arr[node.index][i]
if visited[next.index] == true || node.Value*next.Value < maxValue[next.index] {
continue
}
maxValue[next.index] = node.Value * next.Value
heap.Push(&nodeHeap, Node{
Value: maxValue[next.index],
index: next.index,
})
}
}
return 0
}
type Node struct {
Value float64
index int
}
type NodeHeap []Node
func (h NodeHeap) Len() int {
return len(h)
}
func (h NodeHeap) Less(i, j int) bool {
return h[i].Value > h[j].Value
}
func (h NodeHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *NodeHeap) Push(x interface{}) {
*h = append(*h, x.(Node))
}
func (h *NodeHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
# 2
func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
arr := make([][]Node, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], Node{index: b, Value: succProb[i]})
arr[b] = append(arr[b], Node{index: a, Value: succProb[i]})
}
maxValue := make([]float64, n)
maxValue[start] = 1.0
queue := make([]Node, 0)
queue = append(queue, Node{
Value: 1.0,
index: start,
})
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if maxValue[node.index] > node.Value {
continue
}
for i := 0; i < len(arr[node.index]); i++ {
next := arr[node.index][i]
if maxValue[node.index]*next.Value <= maxValue[next.index] {
continue
}
maxValue[next.index] = maxValue[node.index] * next.Value
queue = append(queue, Node{
Value: maxValue[next.index],
index: next.index,
})
}
}
return maxValue[end]
}
type Node struct {
Value float64
index int
}
1519.子树中标签相同的节点数(2)
给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，
且恰好有 n - 1 条 edges 。
树的根节点为节点 0 ，树上的每一个节点都有一个标签，
也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）
边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。
返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。
树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。
示例 1：输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
输出：[2,1,1,1,1,1,1]
解释：节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因此答案为 2 。
注意树中的每个节点都是这棵子树的一部分。
节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，
但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。
示例 2：输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb" 输出：[4,2,1,1]
解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
节点 3 的子树中只有节点 3 ，所以答案为 1 。
节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。
节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。
示例 3：输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab" 输出：[3,2,1,1,1]
示例 4：输入：n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
输出：[1,2,1,1,2,1]
示例 5：输入：n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
输出：[6,5,4,1,3,2,1]
提示：1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai,bi < n
ai !=bi
labels.length == n
labels 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n) |
| 02 |
深度优先搜索 |
O(n^2) |
O(n) |
var arr [][]int
var res []int
func countSubTrees(n int, edges [][]int, labels string) []int {
res = make([]int, n)
arr = make([][]int, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
dfs(labels, 0, 0)
return res
}
func dfs(s string, cur int, prev int) [26]int {
count := [26]int{}
for i := 0; i < len(arr[cur]); i++ {
next := arr[cur][i]
if next == prev {
continue
}
res := dfs(s, next, cur)
for j := 0; j < len(res); j++ {
count[j] = count[j] + res[j]
}
}
value := int(s[cur] - 'a')
count[value]++
res[cur] = count[value]
return count
}
# 2
var arr [][]int
var res []int
var m map[int]int
func countSubTrees(n int, edges [][]int, labels string) []int {
res = make([]int, n)
arr = make([][]int, n)
m = make(map[int]int)
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)
}
dfs(labels, 0, 0)
for i := 0; i < n; i++ {
value := int(labels[i] - 'a')
res[i] = m[i*26+value]
}
return res
}
func dfs(s string, cur int, prev int) {
m[cur*26+int(s[cur]-'a')]++
for i := 0; i < len(arr[cur]); i++ {
next := arr[cur][i]
if next == prev {
continue
}
dfs(s, next, cur)
for j := 0; j < 26; j++ {
m[cur*26+j] = m[cur*26+j] + m[next*26+j]
}
}
}
1524.和为奇数的子数组数目(2)
给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
示例 1：输入：arr = [1,3,5] 输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：输入：arr = [2,4,6] 输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
示例 3：输入：arr = [1,2,3,4,5,6,7] 输出：16
示例 4：输入：arr = [100,100,99,99] 输出：4
示例 5：输入：arr = [7] 输出：1
提示：1 <= arr.length <= 10^5
1 <= arr[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n) |
O(n) |
func numOfSubarrays(arr []int) int {
odd, even := 0, 1
res := 0
total := 0
for i := 0; i < len(arr); i++ {
total = total + arr[i]
if total%2 == 0 {
res = res + odd
even = even + 1
} else {
res = res + even
odd = odd + 1
}
}
return res % 1000000007
}
# 2
func numOfSubarrays(arr []int) int {
res := 0
dp := make([][2]int, len(arr))
if arr[0]%2 == 1 {
dp[0][0] = 1
res++
} else {
dp[0][1] = 1
}
for i := 1; i < len(arr); i++ {
if arr[i]%2 == 1 {
dp[i][0] = dp[i-1][1] + 1
dp[i][1] = dp[i-1][0]
} else {
dp[i][0] = dp[i-1][0]
dp[i][1] = dp[i-1][1] + 1
}
res = res + dp[i][0]
}
return res % 1000000007
}
1525.字符串的好分割数目(2)
给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：
将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
请你返回 s 中好分割的数目。
示例 1：输入：s = "aacaba" 输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
示例 2：输入：s = "abcd"输出：1 解释：好分割为将字符串分割成 ("ab", "cd") 。
示例 3：输入：s = "aaaaa"输出：4 解释：所有分割都是好分割。
示例 4：输入：s = "acbadbaada"输出：2
提示：s 只包含小写英文字母。 1 <= s.length <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(1) |
func numSplits(s string) int {
left := make(map[byte]int)
right := make(map[byte]int)
for i := 0; i < len(s); i++{
left[s[i]]++
}
res := 0
for i := 0; i < len(s); i++{
left[s[i]]--
right[s[i]]++
if left[s[i]] == 0{
delete(left,s[i])
}
if len(left) == len(right){
res++
}
}
return res
}
#
func numSplits(s string) int {
left := [256]int{}
right := [256]int{}
leftCount := 0
rightCount := 0
for i := 0; i < len(s); i++ {
left[s[i]]++
if left[s[i]] == 1 {
leftCount++
}
}
res := 0
for i := 0; i < len(s); i++ {
left[s[i]]--
right[s[i]]++
if left[s[i]] == 0 {
leftCount--
}
if right[s[i]] == 1 {
rightCount++
}
if leftCount == rightCount {
res++
}
}
return res
}
1529.灯泡开关IV(2)
房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，
等于 0 意味着第 i 个灯是关着的。
有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：
选择当前配置下的任意一个灯泡（下标为 i ）
翻转下标从 i 到 n-1 的每个灯泡
翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。
返回达成 target 描述的状态所需的 最少 翻转次数。
示例 1：输入：target = "10111" 输出：3 解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态
示例 2：输入：target = "101" 输出：3 解释："000" -> "111" -> "100" -> "101".
示例 3：输入：target = "00000" 输出：0
示例 4：输入：target = "001011101" 输出：5
提示：
1 <= target.length <= 10^5
target[i] == '0' 或者 target[i] == '1'
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func minFlips(target string) int {
res := 0
prev := uint8('0')
for i := 0; i < len(target); i++ {
if prev != target[i] {
res++
prev = target[i]
}
}
return res
}
# 2
func minFlips(target string) int {
res := 0
target = "0" + target
for i := 1; i < len(target); i++ {
if target[i] != target[i-1] {
res++
}
}
return res
}
1530.好叶子节点对的数量(2)
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 1：输入：root = [1,2,3,null,4], distance = 3 输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：输入：root = [1,2,3,4,5,6,7], distance = 3 输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。
但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3 输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：输入：root = [100], distance = 1 输出：0
示例 5：输入：root = [1,1,1], distance = 2 输出：1
提示：tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^2) |
O(n) |
| 02 |
递归 |
O(n^2) |
O(n) |
func countPairs(root *TreeNode, distance int) int {
_, res := dfs(root, distance)
return res
}
func dfs(root *TreeNode, distance int) (arr []int, count int) {
arr = make([]int, distance+2)
if root == nil {
return arr, 0
}
if root.Left == nil && root.Right == nil {
arr[1] = 1
return arr, 0
}
leftArr, rightArr := make([]int, distance+1), make([]int, distance+1)
leftCount, rightCount := 0, 0
if root.Left != nil {
leftArr, leftCount = dfs(root.Left, distance)
}
if root.Right != nil {
rightArr, rightCount = dfs(root.Right, distance)
}
for i := 1; i <= distance; i++ {
arr[i+1] = leftArr[i] + rightArr[i]
}
count = 0
for i := 0; i <= distance; i++ {
for j := 0; j <= distance-i; j++ {
count = count + leftArr[i]*rightArr[j]
}
}
return arr, count + leftCount + rightCount
}
# 2
var res int
func countPairs(root *TreeNode, distance int) int {
res = 0
dfs(root, distance)
return res
}
func dfs(root *TreeNode, distance int) (arr []int) {
arr = make([]int, distance+2)
if root == nil {
return arr
}
if root.Left == nil && root.Right == nil {
arr[1] = 1
return arr
}
leftArr, rightArr := make([]int, distance+1), make([]int, distance+1)
if root.Left != nil {
leftArr = dfs(root.Left, distance)
}
if root.Right != nil {
rightArr = dfs(root.Right, distance)
}
for i := 1; i <= distance; i++ {
arr[i+1] = leftArr[i] + rightArr[i]
}
for i := 0; i <= distance; i++ {
for j := 0; j <= distance-i; j++ {
res = res + leftArr[i]*rightArr[j]
}
}
return arr
}
1535.找出数组游戏的赢家(1)
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。
比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，
较小的整数移至数组的末尾。
当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
示例 1：输入：arr = [2,1,3,5,4,6,7], k = 2 输出：5
解释：一起看一下本场游戏每回合的情况：
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。
示例 2：输入：arr = [3,2,1], k = 10 输出：3
解释：3 将会在前 10 个回合中连续获胜。
示例 3：输入：arr = [1,9,8,2,3,7,6,4,5], k = 7 输出：9
示例 4：输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000 输出：99
提示：2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr 所含的整数 各不相同 。
1 <= k <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func getWinner(arr []int, k int) int {
res := arr[0]
count := 0
for i := 1; i < len(arr); i++ {
if arr[i] > res {
res = arr[i]
count = 1
} else {
count++
}
if count == k {
break
}
}
return res
}
1536.排布二进制网格的最少交换次数(1)
给你一个nx n的二进制网格grid，每一次操作中，你可以选择网格的相邻两行进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0。
请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1。
主对角线指的是从(1, 1)到(n, n)的这些格子。
示例 1：输入：grid = [[0,0,1],[1,1,0],[1,0,0]] 输出：3
示例 2：输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] 输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。
示例 3：输入：grid = [[1,0,0],[1,1,0],[1,1,1]] 输出：0
提示：n == grid.length
n == grid[i].length
1 <= n<= 200
grid[i][j]要么是0要么是1。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历+排序 |
O(n^2) |
O(n) |
func minSwaps(grid [][]int) int {
n := len(grid)
arr := make([]int, n)
for i := 0; i < n; i++ {
count := 0
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 0 {
count++
} else {
break
}
}
arr[i] = count
}
res := 0
for i := 0; i < n-1; i++ {
if arr[i] >= n-1-i {
continue
}
j := i
for ; j < n; j++ {
if arr[j] >= n-1-i {
break
}
}
if j == n {
return -1
}
for ; j > i; j-- {
arr[j], arr[j-1] = arr[j-1], arr[j]
res++
}
}
return res
}
1540.K次操作转变字符串(2)
给你两个字符串 s 和 t ，你的目标是在 k 次操作以内把字符串 s 转变成 t 。
在第 i 次操作时（1 <= i <= k），你可以选择进行如下操作：
选择字符串 s 中满足 1 <= j <= s.length 且之前未被选过的任意下标 j （下标从 1 开始），
并将此位置的字符切换 i 次。
不进行任何操作。
切换 1 次字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 'z' 切换后会变成 'a'）。
请记住任意一个下标 j 最多只能被操作 1 次。
如果在不超过 k 次操作内可以把字符串 s 转变成 t ，那么请你返回 true ，否则请你返回 false 。
示例 1：输入：s = "input", t = "ouput", k = 9 输出：true
解释：第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u' 。
示例 2：输入：s = "abc", t = "bcd", k = 10 输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，
但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。
示例 3：输入：s = "aab", t = "bbb", k = 27 输出：true
解释：第 1 次操作时，我们将第一个 'a' 切换 1 次得到 'b' 。
在第 27 次操作时，我们将第二个字母 'a' 切换 27 次得到 'b' 。
提示：1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s 和 t 只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(1) |
func canConvertString(s string, t string, k int) bool {
if len(s) != len(t) {
return false
}
m := make(map[int]int)
maxValue := 0
for i := 0; i < len(s); i++ {
if s[i] != t[i] {
count := (int(t[i]) - int(s[i]) + 26) % 26
maxValue = 26*m[count] + count
if maxValue > k {
return false
}
m[count]++
}
}
return true
}
# 2
func canConvertString(s string, t string, k int) bool {
if len(s) != len(t) {
return false
}
next := [26]int{}
for i := 0; i < 26; i++ {
next[i] = i
}
for i := 0; i < len(s); i++ {
if s[i] != t[i] {
count := (int(t[i]) - int(s[i]) + 26) % 26
if next[count] > k {
return false
}
next[count] = next[count] + 26
}
}
return true
}
1541.平衡括号字符串的最少插入次数(2)
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
任何左括号 '(' 必须对应两个连续的右括号 '))' 。
左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：输入：s = "(()))" 输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。
我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：输入：s = "())" 输出：0
解释：字符串已经平衡了。
示例 3：输入：s = "))())(" 输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：输入：s = "((((((" 输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：输入：s = ")))))))" 输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5
s 只包含 '(' 和 ')' 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
栈辅助 |
O(n) |
O(n) |
func minInsertions(s string) int {
res := 0
left := 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
left++
} else if s[i] == ')' {
if i+1 < len(s) && s[i+1] == ')' {
i++
} else {
res++
}
if left > 0 {
left--
} else {
res++
}
}
}
res = res + left*2
return res
}
# 2
func minInsertions(s string) int {
res := 0
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, '(')
} else if s[i] == ')' {
if i+1 < len(s) && s[i+1] == ')' {
if len(stack) == 0 {
res++
} else {
stack = stack[:len(stack)-1]
}
i++
} else {
if len(stack) == 0 {
res = res + 2
} else {
res++
stack = stack[:len(stack)-1]
}
}
}
}
res = res + len(stack)*2
return res
}
1545.找出第N个二进制字符串中的第K位(2)
给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：
S1 = "0"
当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，
而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）
例如，符合上述描述的序列的前 4 个字符串依次是：
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
示例 1：输入：n = 3, k = 1 输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。
示例 2：输入：n = 4, k = 11 输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。
示例 3：输入：n = 1, k = 1 输出："0"
示例 4：输入：n = 2, k = 3 输出："1"
提示：
1 <= n <= 20
1 <= k <= 2n - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
暴力 |
O(2^n) |
O(2^n) |
| 03 |
遍历 |
O(n) |
O(1) |
func findKthBit(n int, k int) byte {
if n == 1 {
return '0'
}
mid := 1 << (n - 1)
if k == mid {
return '1'
} else if k < mid {
return findKthBit(n-1, k)
}
return change(findKthBit(n-1, (1<<n)-k))
}
func change(char byte) byte {
if char == '0' {
return '1'
}
return '0'
}
# 2
func findKthBit(n int, k int) byte {
arr := generate(n)
return arr[k-1]
}
func generate(n int) []byte {
arr := make([][]byte, n)
arr[0] = []byte{'0'}
for i := 1; i < n; i++ {
arr[i] = append(arr[i], arr[i-1]...)
arr[i] = append(arr[i], '1')
arr[i] = append(arr[i], reverse(invert(arr[i-1]))...)
}
return arr[n-1]
}
func reverse(arr []byte) []byte {
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
return arr
}
func invert(arr []byte) []byte {
for i := 0; i < len(arr); i++ {
arr[i] = '1' - arr[i] + '0'
}
return arr
}
# 3
func findKthBit(n int, k int) byte {
if n == 1 {
return '0'
}
flag := false
mid := 1 << (n - 1)
for k > 1 {
if k == mid {
if flag == true {
return '0'
}
return '1'
} else if k > mid {
if flag == true {
flag = false
} else {
flag = true
}
k = (mid << 1) - k
}
mid = mid >> 1
}
if flag == true {
return '1'
}
return '0'
}
1546.和为目标值的最大数目不重叠非空子数组数目(2)
给你一个数组 nums 和一个整数 target 。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
示例 1：输入：nums = [1,1,1,1,1], target = 2 输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
示例 2：输入：nums = [-1,3,5,1,4,2,-9], target = 6 输出：2
解释：总共有 3 个子数组和为 6 。([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3：输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10 输出：3
示例 4：输入：nums = [0,0,0], target = 0 输出：3
提示： 1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和-哈希辅助 |
O(n) |
O(n) |
| 02 |
前缀和-哈希辅助 |
O(n) |
O(n) |
func maxNonOverlapping(nums []int, target int) int {
res := 0
m := make(map[int]int)
m[0] = -1
sum := 0
prev := -1
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if index, ok := m[sum-target]; ok && index >= prev {
res++
prev = i
}
m[sum] = i
}
return res
}
# 2
func maxNonOverlapping(nums []int, target int) int {
res := 0
m := make(map[int]int)
m[0] = -1
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if _, ok := m[sum-target]; ok {
m = make(map[int]int)
sum = 0
res++
}
m[sum] = i
}
return res
}
1551.使数组中所有元素相等的最小操作数(3)
存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。
一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、
arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。
最终的目标是使数组中的所有元素都 相等 。
题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。
给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。
示例 1：输入：n = 3 输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]
示例 2：输入：n = 6 输出：9
提示： 1 <= n <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
| 02 |
数学 |
O(1) |
O(1) |
| 03 |
数学 |
O(1) |
O(1) |
func minOperations(n int) int {
res := 0
for i := 1; i < n; i = i + 2 {
res = res + n - i
}
return res
}
# 2
func minOperations(n int) int {
res := 0
if n == 1 {
return res
}
if n%2 == 1 {
value := n / 2
res = value * (value + 1)
} else {
value := n / 2
res = value * value
}
return res
}
# 3
func minOperations(n int) int {
return n*n/4
}
1552.两球之间的磁力(2)
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力
。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，
使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
示例 1：输入：position = [1,2,3,4,7], m = 3 输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。
我们没办法让最小磁力大于 3 。
示例 2：输入：position = [5,4,3,2,1,1000000000], m = 2 输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
提示：n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(nlog(n)) |
O(1) |
| 02 |
二分查找 |
O(nlog(n)) |
O(1) |
func maxDistance(position []int, m int) int {
sort.Ints(position)
n := len(position)
maxValue := position[n-1] - position[0]
minValue := position[n-1]
for i := 1; i < n; i++ {
if minValue > position[i]-position[i-1] {
minValue = position[i] - position[i-1]
}
}
if m == 2 {
return maxValue
}
left, right := minValue, maxValue
for left <= right {
mid := left + (right-left)/2
if check(position, mid, m) {
left = mid + 1
} else {
right = mid - 1
}
}
return left - 1
}
func check(arr []int, value int, m int) bool {
count := 1
target := arr[0] + value
for i := 0; i < len(arr); i++ {
if arr[i] >= target {
count++
target = arr[i] + value
}
}
return count >= m
}
# 2
func maxDistance(position []int, m int) int {
sort.Ints(position)
n := len(position)
maxValue := (position[n-1] - position[0]) / (m - 1)
minValue := 1
left, right := minValue, maxValue
res := 1
for left <= right {
mid := left + (right-left)/2
if check(position, mid, m) {
res = mid
left = mid + 1
} else {
right = mid - 1
}
}
return res
}
func check(arr []int, value int, m int) bool {
count := 1
prev := 0
for i := 1; i < len(arr); i++ {
if arr[i]-arr[prev] >= value {
count++
prev = i
}
}
return count >= m
}
1557.可以到达所有点的最少点数目(2)
给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，
其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。
找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
你可以以任意顺序返回这些节点编号。
示例 1：输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] 输出：[0,3]
解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。
从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。
示例 2：输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] 输出：[0,2,3]
解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，
这些点都能到达节点 1 和 4 。
提示：
2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
所有点对 (fromi, toi) 互不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
入度统计 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func findSmallestSetOfVertices(n int, edges [][]int) []int {
res := make([]int, 0)
inEdges := make([]int, n)
for i := 0; i < len(edges); i++ {
b := edges[i][1]
inEdges[b]++
}
for i := 0; i < len(inEdges); i++ {
if inEdges[i] == 0 {
res = append(res, i)
}
}
return res
}
# 2
func findSmallestSetOfVertices(n int, edges [][]int) []int {
res := make([]int, 0)
m := make(map[int]bool)
for i := 0; i < n; i++ {
m[i] = true
}
for i := 0; i < len(edges); i++ {
b := edges[i][1]
delete(m, b)
}
for k := range m {
res = append(res, k)
}
return res
}
1558.得到目标数组的最少函数调用次数(2)
给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。
请你返回将 arr 变成 nums 的最少函数调用次数。
答案保证在 32 位有符号整数以内。
示例 1：输入：nums = [1,5] 输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。
示例 2：输入：nums = [2,2] 输出：3
解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
总操作次数为： 2 + 1 = 3 。
示例 3：输入：nums = [4,2,5] 输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] ->
[4,2,4] -> [4,2,5] （nums 数组）。
示例 4：输入：nums = [3,2,2,4] 输出：7
示例 5：输入：nums = [2,4,8,16] 输出：8
提示：1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟 |
O(n) |
O(1) |
| 02 |
数学 |
O(n) |
O(1) |
func minOperations(nums []int) int {
res := 0
for judge(nums) != true {
res++
res = res + div(nums)
}
return res - 1
}
func judge(arr []int) bool {
for i := 0; i < len(arr); i++ {
if arr[i] != 0 {
return false
}
}
return true
}
func div(arr []int) int {
res := 0
for i := 0; i < len(arr); i++ {
if arr[i] == 0 {
continue
}
if arr[i]%2 == 1 {
res++
}
arr[i] = arr[i] / 2
}
return res
}
# 2
func minOperations(nums []int) int {
res := 0
maxValue := 0
for i := 0; i < len(nums); i++ {
count := 0
n := nums[i]
for n != 0 {
if n%2 == 0 {
n = n / 2
count++
} else {
n = n - 1
res = res + 1
}
}
maxValue = max(maxValue, count)
}
return res + maxValue
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1561.你可以获得的最大硬币数目(3)
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
Alice 将会取走硬币数量最多的那一堆。
你将会取走硬币数量第二多的那一堆。
Bob 将会取走最后一堆。
重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
示例 1：输入：piles = [2,4,1,2,7,8] 输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：输入：piles = [2,4,5] 输出：4
示例 3：输入：piles = [9,8,7,6,5,1,2,3,4] 输出：18
提示：
3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
| 03 |
排序 |
O(nlog(n)) |
O(1) |
func maxCoins(piles []int) int {
res := 0
sort.Ints(piles)
count := len(piles) / 3
for i := 0; i < count; i++ {
index := len(piles) - 1 - i*2 - 1
res = res + piles[index]
}
return res
}
# 2
func maxCoins(piles []int) int {
res := 0
sort.Slice(piles, func(i, j int) bool {
return piles[i] > piles[j]
})
for i := 0; i < len(piles)/3; i++ {
res = res + piles[i*2+1]
}
return res
}
# 3
func maxCoins(piles []int) int {
res := 0
sort.Ints(piles)
left := 0
right := len(piles)-1
for left < right{
left++
right--
res = res + piles[right]
right--
}
return res
}
1562.查找大小为M的最新分组(2)
给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。
有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），
二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。
一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。
示例 1：输入：arr = [3,5,1,2,4], m = 1 输出：4
解释：步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："00101"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："11101"，由 1 构成的组：["111", "1"]
步骤 5："11111"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。
示例 2：输入：arr = [3,1,5,4,2], m = 2 输出：-1
解释：步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："10100"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："10111"，由 1 构成的组：["1", "111"]
步骤 5："11111"，由 1 构成的组：["11111"]
不管是哪一步骤都无法形成长度为 2 的一组 1 。
示例 3：输入：arr = [1], m = 1 输出：1
示例 4：输入：arr = [2,1], m = 2 输出：2
提示：n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
arr 中的所有整数 互不相同
1 <= m <= arr.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
数组辅助 |
O(n) |
O(n) |
func findLatestStep(arr []int, m int) int {
res := -1
temp := make([]int, len(arr)+2)
M := make(map[int]bool)
for i := 0; i < len(arr); i++ {
index := arr[i]
temp[index] = 1
left := temp[index-1]
right := temp[index+1]
total := 1 + left + right
temp[index] = total
temp[index-left] = total
temp[index+right] = total
for k := range M {
if index-left <= k && k < index {
delete(M, k)
}
if index < k && k <= index+right {
delete(M, k)
}
}
if total == m {
M[index] = true
}
if len(M) > 0 {
res = i + 1
}
}
return res
}
# 2
func findLatestStep(arr []int, m int) int {
if len(arr) == m {
return len(arr)
}
res := -1
temp := make([]int, len(arr)+2)
for i := 0; i < len(arr); i++ {
index := arr[i]
total := 1 + temp[index-1] + temp[index+1]
if temp[index-1] == m || temp[index+1] == m {
res = i
}
temp[index-temp[index-1]] = total
temp[index+temp[index+1]] = total
}
return res
}
1567.乘积为正数的最长子数组长度(2)
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1：输入：nums = [1,-2,-3,4] 输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：输入：nums = [0,1,-2,-3,-4] 输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：输入：nums = [-1,-2,-3,0,1] 输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
示例 4：输入：nums = [-1,2] 输出：1
示例 5：输入：nums = [1,2,3,5,-6,4,0,10] 输出：4
提示：1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历+贪心 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
func getMaxLen(nums []int) int {
arr := make([][]int, 0)
temp := make([]int, 0)
res := 0
total := 1
for i := 0; i < len(nums); i++ {
if nums[i] > 0 {
total = total * 1
} else if nums[i] < 0 {
total = total * -1
} else {
total = 0
}
if total > 0 {
temp = append(temp, 1)
} else if nums[i] == 0 {
if len(temp) > 0 {
arr = append(arr, temp)
temp = make([]int, 0)
}
total = 1
} else if total < 0 {
temp = append(temp, -1)
}
}
if len(temp) > 0 {
arr = append(arr, temp)
}
for i := 0; i < len(arr); i++ {
tempArr := arr[i]
left, right := 0, len(tempArr)-1
for 0 <= right && tempArr[right] != 1 {
right--
}
res = max(res, right-left+1)
left, right = 0, len(tempArr)-1
for left < len(tempArr) && tempArr[left] != -1 {
left++
}
for 0 <= right && tempArr[right] != -1 {
right--
}
res = max(res, right-left)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func getMaxLen(nums []int) int {
dp := make([][2]int, len(nums)+1)
res := 0
for i := 1; i <= len(nums); i++ {
if nums[i-1] == 0 {
dp[i][0] = 0
dp[i][1] = 0
} else if nums[i-1] > 0 {
dp[i][0] = dp[i-1][0] + 1
if dp[i-1][1] != 0 {
dp[i][1] = dp[i-1][1] + 1
} else {
dp[i][1] = 0
}
} else {
if dp[i-1][1] != 0 {
dp[i][0] = dp[i-1][1] + 1
} else {
dp[i][0] = 0
}
dp[i][1] = dp[i-1][0] + 1
}
res = max(res, dp[i][0])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1568.使陆地分离的最少天数(1)
给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。
岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
示例 1：输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] 输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。
示例 2：输入：grid = [[1,1]] 输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。
示例 3：输入：grid = [[1,0,1,0]] 输出：0
示例 4：输入：grid = [[1,1,0,1,1],
[1,1,1,1,1],
[1,1,0,1,1],
[1,1,0,1,1]]
输出：1
示例 5：输入：grid = [[1,1,0,1,1],
[1,1,1,1,1],
[1,1,0,1,1],
[1,1,1,1,1]]
输出：2
提示：1 <= grid.length, grid[i].length <= 30
grid[i][j] 为 0 或 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^4) |
O(n^2) |
func minDays(grid [][]int) int {
temp := copyArr(grid)
nums := numIslands(temp)
if nums >= 2 {
return 0
}
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == 0 {
continue
}
temp = copyArr(grid)
temp[i][j] = 0
if numIslands(temp) == 2 {
return 1
}
}
}
return 2
}
func numIslands(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == 1 {
dfs(grid, i, j)
res++
}
}
}
return res
}
func dfs(grid [][]int, i, j int) {
if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) ||
grid[i][j] == 0 {
return
}
grid[i][j] = 0
dfs(grid, i+1, j)
dfs(grid, i-1, j)
dfs(grid, i, j+1)
dfs(grid, i, j-1)
}
func copyArr(grid [][]int) [][]int {
temp := make([][]int, len(grid))
for i := 0; i < len(grid); i++ {
temp[i] = make([]int, len(grid[i]))
for j := 0; j < len(grid[i]); j++ {
temp[i][j] = grid[i][j]
}
}
return temp
}
1573.分割字符串的方案数(2)
给你一个二进制串 s （一个只包含 0 和 1 的字符串），
我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。
请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。
由于答案可能很大，请将它对 10^9 + 7 取余后返回。
示例 1：输入：s = "10101" 输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"
示例 2：输入：s = "1001" 输出：0
示例 3：输入：s = "0000" 输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"
示例 4：输入：s = "100100010100110" 输出：12
提示：
s[i] == '0' 或者 s[i] == '1'
3 <= s.length <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(n) |
func numWays(s string) int {
total := 0
for i := 0; i < len(s); i++ {
if s[i] == '1' {
total++
}
}
if total%3 != 0 {
return 0
}
if total == 0 {
return ((len(s) - 2) * (len(s) - 1) / 2) % 1000000007
}
single := total / 3
first, second := single*1, single*2
var start, left, right int
for i := 0; i < len(s); i++ {
if s[i] == '1' {
start++
} else {
continue
}
if start == first {
left = i + 1
} else if start == first+1 {
left = i - left
}
if start == second {
right = i + 1
} else if start == second+1 {
right = i - right
}
}
return (left + 1) * (right + 1) % 1000000007
}
1574.删除最短的子数组使剩余数组有序(1)
给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1：输入：arr = [1,2,3,10,4,2,3,5] 输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。
示例 2：输入：arr = [5,4,3,2,1] 输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，
要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。
示例 3：输入：arr = [1,2,3] 输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。
示例 4：输入：arr = [1] 输出：0
提示：
1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func findLengthOfShortestSubarray(arr []int) int {
if len(arr) < 2 {
return 0
}
flag := true
left := 0
for i := 1; i < len(arr); i++ {
if arr[i-1] > arr[i] {
flag = false
break
} else {
left = i
}
}
if flag == true {
return 0
}
right := len(arr) - 1
for i := len(arr) - 1; i >= 1; i-- {
if arr[i-1] <= arr[i] {
right = i - 1
} else {
break
}
}
leftC, rightC := 0, 0
for i := left; i >= 0 && arr[i] > arr[right]; i-- {
leftC++
}
for i := right; i < len(arr) && arr[i] < arr[left]; i++ {
rightC++
}
res := 0
res = max(res, (left+1)+(len(arr)-right)-leftC)
res = max(res, (left+1)+(len(arr)-right)-rightC)
return len(arr) - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1577.数的平方等于两数乘积的方法数(1)
给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
类型 1：三元组 (i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k]
其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
类型 2：三元组 (i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k]
其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length
示例 1：输入：nums1 = [7,4], nums2 = [5,2,8,9] 输出：1
解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)
示例 2：输入：nums1 = [1,1], nums2 = [1,1,1] 输出：9
解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2),
nums1[i]^2 = nums2[j] * nums2[k]
类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]
示例 3：输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7] 输出：2
解释：有两个符合题目要求的三元组
类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]
示例 4：输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18] 输出：0
解释：不存在符合题目要求的三元组
提示：1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
func numTriplets(nums1 []int, nums2 []int) int {
res := 0
res = res + getCount(nums1, nums2)
res = res + getCount(nums2, nums1)
return res
}
func getCount(nums1 []int, nums2 []int) int {
res := 0
m := make(map[int]int)
for i := 0; i < len(nums1); i++ {
m[nums1[i]*nums1[i]]++
}
for i := 0; i < len(nums2); i++ {
for j := i + 1; j < len(nums2); j++ {
res = res + m[nums2[i]*nums2[j]]
}
}
return res
}
1578.避免重复字母的最小删除成本(2)
给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。
返回使字符串任意相邻两个字母不相同的最小删除成本。
请注意，删除一个字符后，删除其他字符的成本不会改变。
示例 1：输入：s = "abaac", cost = [1,2,3,4,5] 输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
示例 2：输入：s = "abc", cost = [1,2,3] 输出：0
解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。
示例 3：输入：s = "aabaa", cost = [1,2,3,4,1] 输出：2
解释：删除第一个和最后一个字母，得到字符串 ("aba") 。
提示： s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s 中只含有小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历交换 |
O(n) |
O(1) |
func minCost(s string, cost []int) int {
res := 0
cur := 0
for i := 0; i < len(s)-1; i++ {
if s[cur] == s[i+1] {
res = res + min(cost[cur], cost[i+1])
if cost[cur] < cost[i+1] {
cur = i + 1
}
} else {
cur = i + 1
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minCost(s string, cost []int) int {
res := 0
for i := 0; i < len(s)-1; i++ {
if s[i] == s[i+1] {
res = res + min(cost[i], cost[i+1])
if cost[i] > cost[i+1] {
cost[i], cost[i+1] = cost[i+1], cost[i]
}
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1583.统计不开心的朋友(1)
给你一份 n 位朋友的亲近程度列表，其中 n 总是 偶数 。
对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。
换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。
每个列表中的朋友均以 0 到 n-1 之间的整数表示。
所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [xi, yi] 表示 xi 与 yi 配对，
且 yi 与 xi 配对。
但是，这样的配对情况可能会是其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，
如果同时满足下述两个条件，x 就会不开心：
x 与 u 的亲近程度胜过 x 与 y，且
u 与 x 的亲近程度胜过 u 与 v
返回 不开心的朋友的数目 。
示例 1：输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]],
pairs = [[0, 1], [2, 3]] 输出：2
解释：朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。
示例 2：输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]] 输出：0
解释：朋友 0 和 1 都开心。
示例 3：输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]],
pairs = [[1, 3], [0, 2]] 输出：4
提示：2 <= n <= 500
n 是偶数
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n - 1
每位朋友都 恰好 被包含在一对中
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(n^2) |
func unhappyFriends(n int, preferences [][]int, pairs [][]int) int {
arr := make(map[int]map[int]int)
for i := 0; i < n; i++ {
arr[i] = make(map[int]int)
}
for i := 0; i < len(preferences); i++ {
total := n
for j := 0; j < len(preferences[i]); j++ {
arr[i][preferences[i][j]] = total
total = total - 1
}
}
m := make(map[int]bool)
for i := 0; i < len(pairs); i++ {
x, y := pairs[i][0], pairs[i][1]
x1, y1 := pairs[i][1], pairs[i][0]
for j := 0; j < len(pairs); j++ {
if i == j {
continue
}
u, v := pairs[j][0], pairs[j][1]
u1, v1 := pairs[j][1], pairs[j][0]
if arr[x][u] > arr[x][y] && arr[u][x] > arr[u][v] {
m[x] = true
}
if arr[x1][u] > arr[x1][y1] && arr[u][x1] > arr[u][v] {
m[x1] = true
}
if arr[x][u1] > arr[x][y] && arr[u1][x] > arr[u1][v1] {
m[x] = true
}
if arr[x1][u1] > arr[x1][y1] && arr[u1][x1] > arr[u1][v1] {
m[x1] = true
}
}
}
return len(m)
}
1584.连接所有点的最小费用(3)
给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。
示例 1：输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20
解释：我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：输入：points = [[3,12],[-2,5],[-4,1]] 输出：18
示例 3：输入：points = [[0,0],[1,1],[1,0],[-1,1]] 输出：4
示例 4：输入：points = [[-1000000,-1000000],[1000000,1000000]] 输出：4000000
示例 5：输入：points = [[0,0]] 输出：0
提示：1 <= points.length <= 1000
-106<= xi, yi <= 106
所有点(xi, yi)两两不同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
Kruskal-排序+并查集 |
O(n^2log(n)) |
O(n^2) |
| 02 |
Prime |
O(n^2) |
O(n^2) |
| 03 |
Prime+堆优化 |
O(nlog(n)) |
O(n^2) |
func minCostConnectPoints(points [][]int) int {
n := len(points)
arr := make([][3]int, 0)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
arr = append(arr, [3]int{i, j, dis(points[i], points[j])})
}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][2] < arr[j][2]
})
return Kruskal(n, arr)
}
func Kruskal(n int, arr [][3]int) int {
res := 0
fa = Init(n)
count := 0
for i := 0; i < len(arr); i++ {
a, b, c := arr[i][0], arr[i][1], arr[i][2]
if query(a, b) == false {
union(a, b)
res = res + c
count++
if count == n-1 {
break
}
}
}
return res
}
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)
}
func dis(a, b []int) int {
return abs(a[0]-b[0]) + abs(a[1]-b[1])
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func minCostConnectPoints(points [][]int) int {
n := len(points)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
c := dis(points[i], points[j])
arr[i][j] = c
arr[j][i] = c
}
}
return Prime(arr)
}
func Prime(arr [][]int) int {
res := 0
n := len(arr)
visited := make([]bool, n)
target := 0
visited[target] = true
dis := make([]int, n)
for i := 0; i < n; i++ {
dis[i] = arr[target][i]
}
for i := 1; i < n; i++ {
var index int
minValue := math.MaxInt32
for j := 0; j < n; j++ {
if visited[j] == false && dis[j] < minValue {
minValue = dis[j]
index = j
}
}
visited[index] = true
res = res + minValue
for j := 0; j < n; j++ {
if visited[j] == false && dis[j] > arr[index][j] {
dis[j] = arr[index][j]
}
}
}
return res
}
func dis(a, b []int) int {
return abs(a[0]-b[0]) + abs(a[1]-b[1])
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 3
func minCostConnectPoints(points [][]int) int {
n := len(points)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
c := dis(points[i], points[j])
arr[i][j] = c
arr[j][i] = c
}
}
return Prime(arr)
}
func Prime(arr [][]int) int {
res := 0
n := len(arr)
visited := make([]bool, n)
target := 0
dis := make([]int, n)
for i := 0; i < n; i++ {
dis[i] = math.MaxInt32
}
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [2]int{0, target})
for intHeap.Len() > 0 {
node := heap.Pop(&intHeap).([2]int)
minValue, index := node[0], node[1]
if visited[index] == true {
continue
}
visited[index] = true
res = res + minValue
for j := 0; j < len(arr[index]); j++ {
if visited[j] == false && dis[j] > arr[index][j] {
dis[j] = arr[index][j]
heap.Push(&intHeap, [2]int{arr[index][j], j})
}
}
}
return res
}
type IntHeap [][2]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][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
}
func dis(a, b []int) int {
return abs(a[0]-b[0]) + abs(a[1]-b[1])
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
1589.所有排列中的最大和(1)
有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。
第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，
starti 和 endi 数组索引都是 从 0 开始 的。
你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
示例 1：输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]] 输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。
示例 2：输入：nums = [1,2,3,4,5,6], requests = [[0,1]] 输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。
示例 3：输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]] 输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。
提示：n == nums.length
1 <= n <= 105
0 <= nums[i] <= 105
1 <= requests.length <= 105
requests[i].length == 2
0 <= starti <= endi < n
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
差分+排序 |
O(nlog(n)) |
O(n) |
func maxSumRangeQuery(nums []int, requests [][]int) int {
d := make([]int, len(nums)+1)
arr := make([]int, len(nums))
for i := 0; i < len(requests); i++ {
start := requests[i][0]
end := requests[i][1]
d[start]++
d[end+1]--
}
arr[0] = d[0]
for i := 1; i < len(nums); i++ {
arr[i] = d[i] + arr[i-1]
}
sort.Ints(arr)
sort.Ints(nums)
res := 0
for i := len(arr) - 1; i >= 0; i-- {
res = (res + arr[i]*nums[i]) % 1000000007
}
return res
}
1590.使数组和能被P整除(2)
给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。
不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
示例 1：输入：nums = [3,1,4,2], p = 6 输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
示例 2：输入：nums = [6,3,5,2], p = 9 输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
示例 3：输入：nums = [1,2,3], p = 3 输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
示例 4：输入：nums = [1,2,3], p = 7 输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
示例 5：输入：nums = [1000000000,1000000000,1000000000], p = 3 输出：0
提示： 1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func minSubarray(nums []int, p int) int {
n := len(nums)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = (arr[i] + nums[i]) % p
}
if arr[n] == 0 {
return 0
}
targetValue := arr[n]
res := n
m := make(map[int]int)
m[0] = -1
for i := 0; i < n; i++ {
target := (arr[i+1] - targetValue + p) % p
if value, ok := m[target]; ok {
if res > i-value {
res = i - value
}
}
m[arr[i+1]] = i
}
if res == n {
return -1
}
return res
}
# 2
func minSubarray(nums []int, p int) int {
n := len(nums)
targetValue := 0
for i := 0; i < n; i++ {
targetValue = (targetValue + nums[i]) % p
}
if targetValue == 0 {
return 0
}
res := n
m := make(map[int]int)
m[0] = -1
total := 0
for i := 0; i < n; i++ {
total = (total + nums[i] + p) % p
target := (total - targetValue + p) % p
if value, ok := m[target]; ok {
if res > i-value {
res = i - value
}
}
m[total] = i
}
if res == n {
return -1
}
return res
}
1593.拆分字符串使唯一子字符串的数目最大(1)
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。
但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "ababccc" 输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。
像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，
因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2：输入：s = "aba" 输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。
示例 3：输入：s = "aa" 输出：1
解释：无法进一步拆分字符串。
提示：1 <= s.length <= 16
s 仅包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n*2^n) |
O(n) |
var res int
func maxUniqueSplit(s string) int {
res = 1
dfs(s, make(map[string]bool), make([]string, 0))
return res
}
func dfs(s string, m map[string]bool, arr []string) {
if len(s) == 0 {
if len(arr) > res {
res = len(arr)
}
return
}
for i := 0; i < len(s); i++ {
newStr := s[:i+1]
if m[newStr] == false {
m[newStr] = true
dfs(s[i+1:], m, append(arr, newStr))
m[newStr] = false
}
}
}
1594.矩阵的最大非负积(2)
给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，
每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，
找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。
注意，取余是在得到最大积之后执行的。
示例 1：输入：grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
示例 2：输入：grid = [[1,-2,1],
[1,-2,1],
[3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：输入：grid = [[1, 3],
[0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)
示例 4：输入：grid = [[ 1, 4,4,0],
[-2, 0,0,1],
[ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)
提示：1 <= rows, cols <= 15
-4 <= grid[i][j] <= 4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
递归 |
O(n^2) |
O(n) |
func maxProductPath(grid [][]int) int {
n := len(grid)
if n == 0 {
return 0
}
m := len(grid[0])
dp := make([][][2]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][2]int, m)
}
dp[0][0][0] = grid[0][0]
dp[0][0][1] = grid[0][0]
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if i == 0 && j != 0 {
dp[i][j][0] = min(dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])
dp[i][j][1] = max(dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])
} else if i != 0 && j == 0 {
dp[i][j][0] = min(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j])
dp[i][j][1] = max(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j])
} else if i != 0 && j != 0 {
if grid[i][j] > 0 {
dp[i][j][0] = min(min(dp[i-1][j][0], dp[i][j-1][0]), min(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
dp[i][j][1] = max(max(dp[i-1][j][0], dp[i][j-1][0]), max(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
} else {
dp[i][j][0] = max(max(dp[i-1][j][0], dp[i][j-1][0]), max(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
dp[i][j][1] = min(min(dp[i-1][j][0], dp[i][j-1][0]), min(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
}
}
}
}
a, b := dp[n-1][m-1][0], dp[n-1][m-1][1]
if a == 0 || b == 0 {
return max(0, max(a, b))
}
if a > 0 && b > 0 {
return max(a, b) % 1000000007
}
if b > 0 {
return b % 1000000007
}
if a > 0 {
return a % 1000000007
}
return -1
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var res int
func maxProductPath(grid [][]int) int {
if len(grid) == 0 {
return 0
}
res = -1
dfs(grid, 0, 0, 1)
if res < 0 {
return -1
}
return res % 1000000007
}
func dfs(grid [][]int, i, j int, value int) {
value = value * grid[i][j]
if grid[i][j] == 0 {
if value > res {
res = value
}
return
}
if i == len(grid)-1 && j == len(grid[0])-1 {
if value > res {
res = value
}
}
if i < len(grid)-1 {
dfs(grid, i+1, j, value)
}
if j < len(grid[0])-1 {
dfs(grid, i, j+1, value)
}
}
1599.经营摩天轮的最大利润(2)
你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。
你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。
摩天轮每次轮转都恰好转动 1 / 4 周。
给你一个长度为 n 的数组 customers ，
customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。
这也意味着你必须在新游客到来前轮转 i 次。
每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，
他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。
如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。
注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。
示例 1：输入：customers = [8,3], boardingCost = 5, runningCost = 6 输出：3
解释：座舱上标注的数字是该座舱的当前游客数。
1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。
2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。
3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。
轮转 3 次得到最大利润，最大利润为 $37 。
示例 2：输入：customers = [10,9,6], boardingCost = 6, runningCost = 4 输出：7
解释：1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。
2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。
当前利润为 8 * $6 - 2 * $4 = $40 。
3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。
4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。
5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。
6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。
7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。
轮转 7 次得到最大利润，最大利润为$122 。
示例 3：输入：customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92 输出：-1
解释：1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。
2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 is 7 * $1 - 2 * $92 = -$177 。
3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。
4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 12 * $1 - 4 * $92 = -$356 。
5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。
利润永不为正，所以返回 -1 。
示例 4：输入：customers = [10,10,6,4,7], boardingCost = 3, runningCost = 8 输出：9
解释：1. 10 位游客抵达，4 位登舱，6 位等待，摩天轮轮转。当前利润为 4 * $3 - 1 * $8 = $4 。
2. 10 位游客抵达，4 位登舱，12 位等待，摩天轮轮转。当前利润为 8 * $3 - 2 * $8 = $8 。
3. 6 位游客抵达，4 位登舱，14 位等待，摩天轮轮转。当前利润为 12 * $3 - 3 * $8 = $12 。
4. 4 位游客抵达，4 位登舱，14 位等待，摩天轮轮转。当前利润为 16 * $3 - 4 * $8 = $16 。
5. 7 位游客抵达，4 位登舱，17 位等待，摩天轮轮转。当前利润为 20 * $3 - 5 * $8 = $20 。
6. 4 位登舱，13 位等待，摩天轮轮转。当前利润为 24 * $3 - 6 * $8 = $24 。
7. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 28 * $3 - 7 * $8 = $28 。
8. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 32 * $3 - 8 * $8 = $32 。
9. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 36 * $3 - 9 * $8 = $36 。
10. 1 位登舱，0 位等待，摩天轮轮转。当前利润为 37 * $3 - 10 * $8 = $31 。
轮转 9 次得到最大利润，最大利润为 $36 。
提示：n == customers.length
1 <= n <= 105
0 <= customers[i] <= 50
1 <= boardingCost, runningCost <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
转数组模拟 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
n := len(customers)
arr := make([]int, 0)
total := 0
for i := 0; i < len(customers)-1; i++ {
total = total + customers[i]
if total > 4 {
arr = append(arr, 4)
total = total - 4
customers[i+1] = customers[i+1] + total
total = 0
} else {
arr = append(arr, total)
total = 0
}
}
if customers[n-1] > 0 {
for customers[n-1] > 4 {
arr = append(arr, 4)
customers[n-1] = customers[n-1] - 4
}
arr = append(arr, customers[n-1])
}
maxValue := 0
res := -1
total = 0
for i := 0; i < len(arr); i++ {
total = total + arr[i]
profit := total*boardingCost - (i+1)*runningCost
if profit > 0 {
if profit > maxValue {
maxValue = profit
res = i + 1
}
}
}
return res
}
# 2
func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
maxValue := 0
res := -1
total := 0
i := 0
profit := 0
for total > 0 || i < len(customers) {
if i < len(customers) {
total = total + customers[i]
}
count := min(total, 4)
total = total - count
profit = profit + count*boardingCost - runningCost
if profit > maxValue {
maxValue = profit
res = i + 1
}
i++
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1600.皇位继承顺序(2)
一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。
我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
如果 x 是国王，那么返回 null
否则，返回 Successor(x 的父亲, curOrder)
否则，返回 x 不在 curOrder 中最年长的孩子
比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。
一开始， curOrder 为 ["king"].
调用 Successor(king, curOrder) ，返回 Alice ，
所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
调用 Successor(Alice, curOrder) ，返回 Jack ，
所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
调用 Successor(Jack, curOrder) ，返回 Bob ，
所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
调用 Successor(Bob, curOrder) ，返回 null 。
最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。
通过以上的函数，我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance 类：
ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。
国王的名字作为构造函数的参数传入。
void birth(string parentName,
string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，
也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。
示例：输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth",
"getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"],
["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"],
[null], ["bob"], [null]]
输出：[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob",
"alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha",
"catherine"]]
解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex",
"asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex >
asha > catherine
t.getInheritanceOrder();
// 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]
提示：
1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName，parentName， childName 和 name 仅包含小写英文字母。
所有的参数 childName 和 kingName 互不相同。
所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
最多调用 105 次birth 和 death 。
最多调用 10 次 getInheritanceOrder 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前序遍历 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
type Node struct {
Name string
Child []*Node
}
type ThroneInheritance struct {
isDead map[string]bool
m map[string]*Node
king *Node
}
func Constructor(kingName string) ThroneInheritance {
node := &Node{
Name: kingName,
Child: make([]*Node, 0),
}
res := ThroneInheritance{
king: node,
m: map[string]*Node{},
isDead: map[string]bool{},
}
res.m[kingName] = node
return res
}
func (this *ThroneInheritance) Birth(parentName string, childName string) {
node := this.m[parentName]
child := &Node{
Name: childName,
Child: make([]*Node, 0),
}
this.m[childName] = child
node.Child = append(node.Child, child)
}
func (this *ThroneInheritance) Death(name string) {
this.isDead[name] = true
}
func (this *ThroneInheritance) GetInheritanceOrder() []string {
res := make([]string, 0)
root := this.king
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if this.isDead[node.Name] == false {
res = append(res, node.Name)
}
if len(node.Child) > 0 {
for i := len(node.Child) - 1; i >= 0; i-- {
stack = append(stack, node.Child[i])
}
}
}
return res
}
# 2
type ThroneInheritance struct {
isDead map[string]bool
children map[string][]string
king string
}
func Constructor(kingName string) ThroneInheritance {
return ThroneInheritance{
isDead: make(map[string]bool),
children: make(map[string][]string),
king: kingName,
}
}
func (this *ThroneInheritance) Birth(parentName string, childName string) {
this.children[parentName] = append(this.children[parentName], childName)
}
func (this *ThroneInheritance) Death(name string) {
this.isDead[name] = true
}
func (this *ThroneInheritance) GetInheritanceOrder() []string {
return dfs(this, this.king)
}
func dfs(this *ThroneInheritance, name string) []string {
res := make([]string, 0)
if this.isDead[name] == false {
res = append(res, name)
}
for _, child := range this.children[name] {
res = append(res, dfs(this, child)...)
}
return res
}
1501-1600-Hard
1510.石子游戏IV(1)
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：输入：n = 1 输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：输入：n = 2 输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：输入：n = 4 输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：输入：n = 7 输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，
Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，
Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：输入：n = 17 输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示： 1 <= n <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^(3/2)) |
O(n) |
func winnerSquareGame(n int) bool {
dp := make([]bool, n+1)
count := 1
for i := 1; i <= n; i++ {
if count*count == i {
dp[i] = true
count++
continue
}
for j := 1; j*j < i; j++ {
if dp[i-j*j] == false {
dp[i] = true
break
}
}
}
return dp[n]
}
1526.形成目标数组的子数组最少增加次数(1)
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，
且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：输入：target = [1,2,3,2,1] 输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
示例 2：输入：target = [3,1,1,2] 输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：输入：target = [3,1,5,4,2] 输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：输入：target = [1,1,1,1] 输出：1
提示：
1 <= target.length <= 10^5
1 <= target[i] <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func minNumberOperations(target []int) int {
res := target[0]
for i := 1; i < len(target); i++ {
res = res + max(target[i]-target[i-1], 0)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1537.最大得分(1)
你有两个 有序且数组内元素互不相同的数组nums1 和nums2。
一条合法路径定义如下：
选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1和 nums2中都存在的值，
那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
示例 1：输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] 输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10]。
示例 2：输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100] 输出：109
解释：最大得分由路径 [1,3,5,100] 得到。
示例 3：输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10] 输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。
示例 4：输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12] 输出：61
提示：1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 和nums2都是严格递增的数组。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func maxSum(nums1 []int, nums2 []int) int {
n := len(nums1)
m := len(nums2)
a, b := 0, 0
i, j := 0, 0
for i < n || j < m {
if i < n && j < m {
if nums1[i] < nums2[j] {
a = a + nums1[i]
i++
} else if nums1[i] > nums2[j] {
b = b + nums2[j]
j++
} else {
temp := max(a, b) + nums1[i]
a = temp
b = temp
i++
j++
}
} else if i < n {
a = a + nums1[i]
i++
} else if j < m {
b = b + nums2[j]
j++
}
}
return max(a, b) % 1000000007
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1542.找出最长的超赞子字符串(1)
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：
该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：输入：s = "3242415" 输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
示例 2：输入：s = "12345678" 输出：1
示例 3：输入：s = "213123" 输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
示例 4：输入：s = "00" 输出：2
提示：1 <= s.length <= 10^5
s 仅由数字组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+位运算 |
O(n) |
O(1) |
func longestAwesome(s string) int {
res := 0
n := len(s)
m := make(map[int]int)
m[0] = -1
cur := 0
for i := 0; i < n; i++ {
value := int(s[i] - '0')
cur = cur ^ (1 << value)
if index, ok := m[cur]; ok {
res = max(res, i-index)
} else {
m[cur] = i
}
for j := 0; j < 10; j++ {
if index, ok := m[cur^(1<<j)]; ok {
res = max(res, i-index)
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1547.切棍子的最小成本(3)
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。
对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。
请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：输入：n = 7, cuts = [1,3,4,5] 输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。
第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，
最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：输入：n = 9, cuts = [5,6,1,4,2] 输出：22
解释：如果按给定的顺序切割，则总成本为 25 。
总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。
提示：2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^3) |
O(n^2) |
| 02 |
动态规划 |
O(n^3) |
O(n^2) |
| 03 |
动态规划-递归 |
O(n^3) |
O(n^2) |
func minCost(n int, cuts []int) int {
m := len(cuts)
cuts = append(cuts, 0, n)
sort.Ints(cuts)
dp := make([][]int, m+2)
for i := 0; i < m+2; i++ {
dp[i] = make([]int, m+2)
}
for i := m; i >= 1; i-- {
for j := i; j <= m; j++ {
dp[i][j] = math.MaxInt32
for k := i; k <= j; k++ {
dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
}
dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
}
}
return dp[1][m]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minCost(n int, cuts []int) int {
m := len(cuts)
cuts = append(cuts, 0, n)
sort.Ints(cuts)
dp := make([][]int, m+2)
for i := 0; i < m+2; i++ {
dp[i] = make([]int, m+2)
}
for length := 2; length <= m+1; length++ {
for i := 1; i <= m; i++ {
j := i + length - 2
if j > m {
break
}
dp[i][j] = math.MaxInt32
for k := i; k <= j; k++ {
dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
}
dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
}
}
return dp[1][m]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
var dp [][]int
func minCost(n int, cuts []int) int {
m := len(cuts)
cuts = append(cuts, 0, n)
sort.Ints(cuts)
dp = make([][]int, m+2)
for i := 0; i < m+2; i++ {
dp[i] = make([]int, m+2)
}
return dfs(cuts, 1, m)
}
func dfs(cuts []int, i, j int) int {
if dp[i][j] != 0 {
return dp[i][j]
}
if i > j {
return 0
}
if i == j {
return cuts[j+1] - cuts[i-1]
}
dp[i][j] = math.MaxInt32
for k := i; k <= j; k++ {
dp[i][j] = min(dp[i][j], dfs(cuts, i, k-1)+dfs(cuts, k+1, j))
}
dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
return dp[i][j]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1553.吃掉N个橘子的最少天数(2)
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：输入：n = 10 输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。
示例 2：输入：n = 6 输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。
示例 3：输入：n = 1 输出：1
示例 4：输入：n = 56 输出：6
提示： 1 <= n <= 2*10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划-递归 |
O(log(n)) |
O(log(n)) |
| 02 |
广度优先搜索 |
O(log(n)) |
O(log(n)) |
var dp map[int]int
func minDays(n int) int {
dp = make(map[int]int)
dp[0] = 0
dp[1] = 1
return dfs(n)
}
func dfs(n int) int {
if value, ok := dp[n]; ok {
return value
}
dp[n] = min(dfs(n/2)+n%2+1, dfs(n/3)+n%3+1)
return dp[n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minDays(n int) int {
m := make(map[int]bool)
queue := make([]int, 0)
queue = append(queue, n)
res := 0
for len(queue) > 0 {
length := len(queue)
for i := 0; i < length; i++ {
day := queue[i]
if day == 0 {
return res
}
if day%3 == 0 && m[day/3] == false {
queue = append(queue, day/3)
m[day/3] = true
}
if day%2 == 0 && m[day/2] == false {
queue = append(queue, day/2)
m[day/2] = true
}
if m[day-1] == false {
queue = append(queue, day-1)
m[day-1] = true
}
}
res++
queue = queue[length:]
}
return res
}
1559.二维网格图中探测环(1)
给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，
你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，
因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
示例 1：
输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：
示例 2：
输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：
示例 3：输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]] 输出：false
提示： m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n^2) |
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var visited map[[2]int]bool
func containsCycle(grid [][]byte) bool {
n, m := len(grid), len(grid[0])
visited = make(map[[2]int]bool)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if visited[[2]int{i, j}] == true {
continue
}
start := grid[i][j]
if dfs(grid, start, i, j, -1, -1) == true {
return true
}
}
}
return false
}
func dfs(grid [][]byte, start byte, x, y int, pX, pY int) bool {
visited[[2]int{x, y}] = true
for i := 0; i < 4; i++ {
newX := x + dx[i]
newY := y + dy[i]
if newX < 0 || newX >= len(grid) || newY < 0 || newY >= len(grid[0]) ||
(newX == pX && newY == pY) {
continue
}
if start == grid[newX][newY] {
if visited[[2]int{newX, newY}] == true {
return true
}
result := dfs(grid, start, newX, newY, x, y)
if result == true {
return true
}
}
}
return false
}
1563.石子游戏V(2)
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；
Bob 负责计算每一行的值，即此行中所有石子的值的总和。
Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。
如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1：输入：stoneValue = [6,2,3,4,5,5] 输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。
左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。
游戏结束，因为这行只剩下一块石头了。
示例 2：输入：stoneValue = [7,7,7,7,7,7,7] 输出：28
示例 3：输入：stoneValue = [4] 输出：0
提示：
1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划+前缀和 |
O(n^3) |
O(n^2) |
| 02 |
递归+前缀和 |
O(n^3) |
O(n^2) |
func stoneGameV(stoneValue []int) int {
n := len(stoneValue)
sum := make([]int, n+1)
sum[0] = stoneValue[0]
for i := 1; i < n; i++ {
sum[i] = sum[i-1] + stoneValue[i]
}
dp := make([][]int, n+1)
for i := 0; i < n; i++ {
dp[i] = make([]int, n+1)
}
for length := 2; length <= n; length++ {
for i := 0; i+length-1 < n; i++ {
j := i + length - 1
for k := i; k <= j; k++ {
if i > k || k+1 > j {
continue
}
left := dp[i][k]
right := dp[k+1][j]
leftSum := sum[k]
if i > 0 {
leftSum = sum[k] - sum[i-1]
}
rightSum := sum[j] - sum[k]
if leftSum == rightSum {
dp[i][j] = max(dp[i][j], max(left, right)+leftSum)
} else if leftSum > rightSum {
dp[i][j] = max(dp[i][j], right+rightSum)
} else if leftSum < rightSum {
dp[i][j] = max(dp[i][j], left+leftSum)
}
}
}
}
return dp[0][n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var dp [][]int
var sum []int
func stoneGameV(stoneValue []int) int {
n := len(stoneValue)
sum = make([]int, n+1)
sum[0] = 0
for i := 0; i < n; i++ {
sum[i+1] = sum[i] + stoneValue[i]
}
dp = make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, n+1)
for j := 0; j <= n; j++ {
dp[i][j] = -1
}
}
return dfs(1, n)
}
func dfs(left, right int) int {
if dp[left][right] != -1 {
return dp[left][right]
}
if left == right {
dp[left][right] = 0
} else {
value := 0
for i := left; i < right; i++ {
leftSum := sum[i] - sum[left-1]
rightSum := sum[right] - sum[i]
if leftSum < rightSum {
value = max(value, leftSum+dfs(left, i))
} else if leftSum > rightSum {
value = max(value, rightSum+dfs(i+1, right))
} else {
value = max(value, max(dfs(left, i), dfs(i+1, right))+leftSum)
}
}
dp[left][right] = value
}
return dp[left][right]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1579.保证图可完全遍历(1)
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：
类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。
给你一个数组 edges ，其中 edges[i] = [typei, ui, vi]表示节点 ui 和 vi 之间存在类型为 typei 的双向边。
请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。
如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
示例 1：输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] 输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。
再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。
示例 2：输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] 输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。
示例 3：输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] 输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。
提示：1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
所有元组 (typei, ui, vi) 互不相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
并查集 |
O(nlog(n)) |
O(n) |
func maxNumEdgesToRemove(n int, edges [][]int) int {
res := len(edges)
alice, bob := &UnionFind{}, &UnionFind{}
alice.Init(n)
bob.Init(n)
for i := 0; i < len(edges); i++ {
a, b, c := edges[i][0], edges[i][1]-1, edges[i][2]-1
if a == 3 && (alice.query(b, c) == false || bob.query(b, c) == false) {
alice.union(b, c)
bob.union(b, c)
res--
}
}
for i := 0; i < len(edges); i++ {
a, b, c := edges[i][0], edges[i][1]-1, edges[i][2]-1
if a == 1 && alice.query(b, c) == false {
alice.union(b, c)
res--
}
if a == 2 && bob.query(b, c) == false {
bob.union(b, c)
res--
}
}
if alice.count > 1 || bob.count > 1 {
return -1
}
return res
}
type UnionFind struct {
fa []int
count int
}
func (u *UnionFind) Init(n int) {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
u.count = n
u.fa = arr
}
func (u UnionFind) find(x int) int {
if u.fa[x] == x {
return x
}
u.fa[x] = u.find(u.fa[x])
return u.fa[x]
}
func (u *UnionFind) union(i, j int) {
x, y := u.find(i), u.find(j)
if x != y {
u.fa[x] = y
u.count--
}
}
func (u UnionFind) query(i, j int) bool {
return u.find(i) == u.find(j)
}
1585.检查字符串是否可以通过排序子字符串得到另一个字符串(1)
给你两个字符串s 和t，请你通过若干次以下操作将字符串s转化成字符串t：
选择 s中一个 非空子字符串并将它包含的字符就地 升序排序。
比方说，对下划线所示的子字符串进行操作可以由"14234"得到"12344"。
如果可以将字符串 s变成 t，返回 true。否则，返回 false。
一个 子字符串定义为一个字符串中连续的若干字符。
示例 1：输入：s = "84532", t = "34852" 输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"
示例 2：输入：s = "34521", t = "23415" 输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"
示例 3：输入：s = "12345", t = "12435" 输出：false
示例 4：输入：s = "1", t = "2" 输出：false
提示：s.length == t.length
1 <= s.length <= 105
s 和t都只包含数字字符，即'0'到'9' 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
func isTransformable(s string, t string) bool {
n := len(s)
arr := [10][]int{}
for i := 0; i < n; i++ {
arr[int(s[i]-'0')] = append(arr[int(s[i]-'0')], i)
}
for i := 0; i < n; i++ {
index := int(t[i] - '0')
if len(arr[index]) == 0 {
return false
}
for j := 0; j < index; j++ {
if len(arr[j]) > 0 && arr[j][0] < arr[index][0] {
return false
}
}
arr[index] = arr[index][1:]
}
return true
}