1601-1700-Easy

1603.设计停车系统(2)

  • 题目
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类:
    ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,
    三个参数分别对应每种停车位的数目。
    bool addCar(int carType) 检车是否有 carType 对应的停车位。 
    carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。
    一辆车只能停在  carType 对应尺寸的停车位中。
    如果没有空车位,请返回 false ,否则将该车停入车位并返回 true 。
示例 1:输入:["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
输出:[null, true, true, false, false]
解释:ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ,因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ,因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ,因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ,因为没有空的大车位,唯一一个大车位已经被占据了
提示: 0 <= big, medium, small <= 1000
    carType 取值为 1, 2 或 3
    最多会调用 addCar 函数 1000 次
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组 O(1) O(1)
02 数组 O(1) O(1)
type ParkingSystem struct {
    arr   [3]int
    total [3]int
}

func Constructor(big int, medium int, small int) ParkingSystem {
    return ParkingSystem{
        arr:   [3]int{big, medium, small},
        total: [3]int{0, 0, 0},
    }
}

func (this *ParkingSystem) AddCar(carType int) bool {
    index := carType - 1
    if this.total[index] < this.arr[index] {
        this.total[index]++
        return true
    }
    return false
}

# 2
type ParkingSystem struct {
    arr [3]int
}

func Constructor(big int, medium int, small int) ParkingSystem {
    return ParkingSystem{
        arr: [3]int{big, medium, small},
    }
}

func (this *ParkingSystem) AddCar(carType int) bool {
    if this.arr[carType-1] > 0 {
        this.arr[carType-1]--
        return true
    }
    return false
}

1608.特殊数组的特征值(3)

  • 题目
给你一个非负整数数组 nums 。
如果存在一个数 x ,使得 nums 中恰好有 x 个元素 大于或者等于 x ,
那么就称 nums 是一个 特殊数组 ,而 x 是该数组的 特征值 。
注意: x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ,请返回它的特征值 x 。
否则,返回 -1 。可以证明的是,如果 nums 是特殊数组,那么其特征值 x 是 唯一的 。
示例 1:输入:nums = [3,5] 输出:2
解释:有 2 个元素(3 和 5)大于或等于 2 。
示例 2:输入:nums = [0,0] 输出:-1
解释:没有满足题目要求的特殊数组,故而也不存在特征值 x 。
如果 x = 0,应该有 0 个元素 >= x,但实际有 2 个。
如果 x = 1,应该有 1 个元素 >= x,但实际有 0 个。
如果 x = 2,应该有 2 个元素 >= x,但实际有 0 个。
x 不能取更大的值,因为 nums 中只有两个元素。
示例 3:输入:nums = [0,4,3,0,4] 输出:3
解释:有 3 个元素大于或等于 3 。
示例 4:输入:nums = [3,6,7,7,0] 输出:-1
提示:1 <= nums.length <= 100
    0 <= nums[i] <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 计数排序 O(n) O(n)
02 暴力法 O(n^2) O(1)
03 排序 O(nlog(n)) O(1)
func specialArray(nums []int) int {
    arr := make([]int, 1001)
    for i := 0; i < len(nums); i++ {
        arr[nums[i]]++
    }
    for i := len(arr) - 2; i >= 0; i-- {
        arr[i] = arr[i] + arr[i+1]
    }
    for i := 0; i <= len(nums); i++ {
        if arr[i] == i {
            return i
        }
    }
    return -1
}

# 2
func specialArray(nums []int) int {
    for i := 0; i <= len(nums); i++ {
        count := 0
        for j := 0; j < len(nums); j++ {
            if nums[j] >= i {
                count++
            }
        }
        if count == i {
            return i
        }
    }
    return -1
}

# 3
func specialArray(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    if nums[0] >= n {
        return n
    }
    for i := 1; i < n; i++ {
        target := n - i
        if nums[i] >= target && target > nums[i-1] {
            return target
        }
    }
    return -1
}

1614.括号的最大嵌套深度(2)

  • 题目
如果字符串满足一下条件之一,则可以称之为 有效括号字符串(valid parentheses string,可以简写为 VPS):
    字符串是一个空字符串 "",或者是一个不为 "(" 或 ")" 的单字符。
    字符串可以写为 AB(A 与 B 字符串连接),其中 A 和 B 都是 有效括号字符串 。
    字符串可以写为 (A),其中 A 是一个 有效括号字符串 。
类似地,可以定义任何有效括号字符串 S 的 嵌套深度 depth(S):
    depth("") = 0
    depth(A + B) = max(depth(A), depth(B)),其中 A 和 B 都是 有效括号字符串
    depth("(" + A + ")") = 1 + depth(A),其中 A 是一个 有效括号字符串
例如:""、"()()"、"()(()())" 都是 有效括号字符串(嵌套深度分别为 0、1、2),
而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s,返回该字符串的 s 嵌套深度 。
示例 1:输入:s = "(1+(2*3)+((8)/4))+1" 输出:3
解释:数字 8 在嵌套的 3 层括号中。
示例 2:输入:s = "(1)+((2))+(((3)))" 输出:3
示例 3:输入:s = "1+(2*3)/(2-1)" 输出:1
示例 4:输入:s = "1" 输出:0
提示: 1 <= s.length <= 100
    s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
    题目数据保证括号表达式 s 是 有效的括号表达式
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 栈辅助 O(n) O(n)
func maxDepth(s string) int {
    res := 0
    count := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            count++
        } else if s[i] == ')' {
            if count > res {
                res = count
            }
            count--
        }
    }
    return res
}

# 2
func maxDepth(s string) int {
    res := 0
    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, s[i])
        } else if s[i] == ')' {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > res {
            res = len(stack)
        }
    }
    return res
}

1619.删除某些元素后的数组均值(2)

  • 题目
给你一个整数数组arr,请你删除最小5%的数字和最大 5%的数字后,剩余数字的平均值。
与 标准答案误差在10-5的结果都被视为正确结果。
示例 1:输入:arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3] 输出:2.00000
解释:删除数组中最大和最小的元素后,所有元素都等于 2,所以平均值为 2 。
示例 2:输入:arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0] 输出:4.00000
示例 3:输入:arr =[6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,
3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
输出:4.77778
示例 4:输入:arr =[9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,
7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
输出:5.27778
示例 5:输入:arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,
9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,
7,2,10,7,7,8,2,0,1,1]
输出:5.29167
提示:20 <= arr.length <= 1000
arr.length是20的倍数
0 <= arr[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(n)
02 排序遍历 O(nlog(n)) O(1)
func trimMean(arr []int) float64 {
    temp := make([]float64, 0)
    for i := 0; i < len(arr); i++ {
        temp = append(temp, float64(arr[i]))
    }
    sort.Float64s(temp)
    var sum float64
    count := int(float64(len(arr)) * 0.05)
    for i := count; i < len(temp)-count; i++ {
        sum = sum + temp[i]
    }
    return sum / float64(len(arr)-2*count)
}

# 2
func trimMean(arr []int) float64 {
    n := len(arr)
    count := n / 20
    sort.Ints(arr)
    sum := 0
    for i := count; i < n-count; i++ {
        sum += arr[i]
    }
    return float64(sum) / float64(n-2*count)
}

1624.两个相同字符之间的最长子字符串(2)

  • 题目
给你一个字符串 s,请你返回 两个相同字符之间的最长子字符串的长度 ,计算长度时不含这两个字符。
如果不存在这样的子字符串,返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1:输入:s = "aa" 输出:0
解释:最优的子字符串是两个 'a' 之间的空子字符串。
示例 2:输入:s = "abca" 输出:2
解释:最优的子字符串是 "bc" 。
示例 3:输入:s = "cbzxy" 输出:-1
解释:s 中不存在出现出现两次的字符,所以返回 -1 。
示例 4:输入:s = "cabbac" 输出:4
解释:最优的子字符串是 "abba" ,其他的非最优解包括 "bb" 和 "" 。
提示:1 <= s.length <= 300  s 只含小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(1)
02 暴力法 O(n^2) O(1)
func maxLengthBetweenEqualCharacters(s string) int {
    m := make(map[byte]int)
    res := -1
    for i := 0; i < len(s); i++ {
        if value, ok := m[s[i]]; ok {
            res = max(res, i-value-1)
        } else {
            m[s[i]] = i
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maxLengthBetweenEqualCharacters(s string) int {
    res := -1
    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s); j++ {
            if s[i] == s[j] {
                res = max(res, j-i-1)
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1629.按键持续时间最长的键(1)

  • 题目
LeetCode 设计了一款新式键盘,正在测试其可用性。测试人员将会点击一系列键(总计 n 个),每次一个。
给你一个长度为 n 的字符串 keysPressed ,其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。
releaseTimes 是一个升序排列的列表,其中 releaseTimes[i] 表示松开第 i 个键的时间。
字符串和数组的 下标都从 0 开始 。
第 0 个键在时间为 0 时被按下,接下来每个键都 恰好 在前一个键松开时被按下。
测试人员想要找出按键 持续时间最长 的键。
第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ,
第 0 次按键的持续时间为 releaseTimes[0] 。
注意,测试期间,同一个键可以在不同时刻被多次按下,而每次的持续时间都可能不同。
请返回按键 持续时间最长 的键,如果有多个这样的键,则返回 按字母顺序排列最大 的那个键。
示例 1:输入:releaseTimes = [9,29,49,50], keysPressed = "cbcd" 输出:"c"
解释:按键顺序和持续时间如下:
按下 'c' ,持续时间 9(时间 0 按下,时间 9 松开)
按下 'b' ,持续时间 29 - 9 = 20(松开上一个键的时间 9 按下,时间 29 松开)
按下 'c' ,持续时间 49 - 29 = 20(松开上一个键的时间 29 按下,时间 49 松开)
按下 'd' ,持续时间 50 - 49 = 1(松开上一个键的时间 49 按下,时间 50 松开)
按键持续时间最长的键是 'b' 和 'c'(第二次按下时),持续时间都是 20
'c' 按字母顺序排列比 'b' 大,所以答案是 'c'
示例 2:输入:releaseTimes = [12,23,36,46,62], keysPressed = "spuda" 输出:"a"
解释:按键顺序和持续时间如下:
按下 's' ,持续时间 12
按下 'p' ,持续时间 23 - 12 = 11
按下 'u' ,持续时间 36 - 23 = 13
按下 'd' ,持续时间 46 - 36 = 10
按下 'a' ,持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ,持续时间 16
提示: releaseTimes.length == n
    keysPressed.length == n
    2 <= n <= 1000
    0 <= releaseTimes[i] <= 109
    releaseTimes[i] < releaseTimes[i+1]
    keysPressed 仅由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func slowestKey(releaseTimes []int, keysPressed string) byte {
    res := 0
    maxValue := releaseTimes[0]
    for i := 1; i < len(releaseTimes); i++ {
        if releaseTimes[i]-releaseTimes[i-1] > maxValue {
            maxValue = releaseTimes[i] - releaseTimes[i-1]
            res = i
        } else if releaseTimes[i]-releaseTimes[i-1] == maxValue &&
            keysPressed[i] > keysPressed[res] {
            res = i
        }
    }
    return keysPressed[res]
}

1636.按照频率将数组升序排序(1)

  • 题目
给你一个整数数组 nums ,请你将数组按照每个值的频率 升序 排序。
如果有多个值的频率相同,请你按照数值本身将它们 降序 排序。 
请你返回排序后的数组。
示例 1:输入:nums = [1,1,2,2,2,3] 输出:[3,1,1,2,2,2]
解释:'3' 频率为 1,'1' 频率为 2,'2' 频率为 3 。
示例 2:输入:nums = [2,3,1,3,2] 输出:[1,3,3,2,2]
解释:'2' 和 '3' 频率都为 2 ,所以它们之间按照数值本身降序排序。
示例 3:输入:nums = [-1,1,-6,4,5,-6,1,4,1] 输出:[5,-1,4,4,-6,-6,1,1,1]
提示:1 <= nums.length <= 100
    -100 <= nums[i] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 自定义排序 O(nlog(n)) O(n)
func frequencySort(nums []int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    arr := make([][2]int, 0)
    for k, v := range m {
        arr = append(arr, [2]int{k, v})
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][1] == arr[j][1] {
            return arr[i][0] > arr[j][0]
        }
        return arr[i][1] < arr[j][1]
    })
    res := make([]int, 0)
    for i := 0; i < len(arr); i++ {
        for j := 0; j < arr[i][1]; j++ {
            res = append(res, arr[i][0])
        }
    }
    return res
}

1640.能否连接形成数组(2)

  • 题目
给你一个整数数组 arr ,数组中的每个整数 互不相同 。
另有一个由整数数组构成的数组 pieces,其中的整数也 互不相同 。
请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是,不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ,返回 true ;否则,返回 false 。
示例 1:输入:arr = [85], pieces = [[85]]输出:true
示例 2:输入:arr = [15,88], pieces = [[88],[15]] 输出:true
解释:依次连接 [15] 和 [88]
示例 3:输入:arr = [49,18,16], pieces = [[16,18,49]] 输出:false
解释:即便数字相符,也不能重新排列 pieces[0]
示例 4:输入:arr = [91,4,64,78], pieces = [[78],[4,64],[91]] 输出:true
解释:依次连接 [91]、[4,64] 和 [78]
示例 5:输入:arr = [1,3,5,7], pieces = [[2,4,6,8]] 输出:false
提示:1 <= pieces.length <= arr.length <= 100
    sum(pieces[i].length) == arr.length
    1 <= pieces[i].length <= arr.length
    1 <= arr[i], pieces[i][j] <= 100
    arr 中的整数 互不相同
    pieces 中的整数 互不相同(也就是说,如果将 pieces 扁平化成一维数组,数组中的所有整数互不相同)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历标记 O(n^2) O(1)
02 哈希辅助 O(n) O(n)
func canFormArray(arr []int, pieces [][]int) bool {
    for i := 0; i < len(pieces); i++ {
        value := pieces[i]
        length := len(value)
        flag := false
        for j := 0; j < len(arr); j++ {
            if arr[j] == value[0] {
                flag = true
                for k := j; k < j+length && k < len(arr); k++ {
                    if arr[k] != value[k-j] {
                        return false
                    } else {
                        arr[k] = 0
                    }
                }
                break
            }
        }
        if flag == false {
            return false
        }
    }
    for i := 0; i < len(arr); i++ {
        if arr[i] != 0 {
            return false
        }
    }
    return true
}

# 2
func canFormArray(arr []int, pieces [][]int) bool {
    m := make(map[int]int)
    for i := 0; i < len(arr); i++ {
        m[arr[i]] = i
    }
    for i := 0; i < len(pieces); i++ {
        if _, ok := m[pieces[i][0]]; !ok {
            return false
        }
        for k := 0; k < len(pieces[i])-1; k++ {
            if m[pieces[i][k+1]]-m[pieces[i][k]] != 1 {
                return false
            }
        }
    }
    return true
}

1646.获取生成数组中的最大值(1)

  • 题目
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums :
nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时,nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时,nums[2 * i + 1] = nums[i] + nums[i + 1]
返回生成数组 nums 中的 最大 值。
示例 1:输入:n = 7 输出:3
解释:根据规则:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此,nums = [0,1,1,2,1,3,2,3],最大值 3
示例 2:输入:n = 2 输出:1
解释:根据规则,nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
示例 3:输入:n = 3 输出:2
解释:根据规则,nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
提示:0 <= n <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func getMaximumGenerated(n int) int {
    arr := make([]int, n+3)
    arr[0] = 0
    arr[1] = 1
    res := 0
    for i := 0; i <= n; i++ {
        if i%2 == 0 {
            arr[i] = arr[i/2]
        } else {
            arr[i] = arr[i/2] + arr[(i+1)/2]
        }
        if arr[i] > res {
            res = arr[i]
        }
    }
    return res
}

1652.拆炸弹(1)

  • 题目
你有一个炸弹需要拆除,时间紧迫!你的情报员会给你一个长度为n的循环数组code以及一个密钥k。
为了获得正确的密码,你需要替换掉每一个数字。所有数字会同时被替换。
如果k > 0,将第i个数字用 接下来k个数字之和替换。
如果k < 0,将第i个数字用 之前k个数字之和替换。
如果k == 0,将第i个数字用0替换。
由于code是循环的,code[n-1]下一个元素是code[0],且code[0]前一个元素是code[n-1]。
给你 循环数组code和整数密钥k,请你返回解密后的结果来拆除炸弹!
示例 1:输入:code = [5,7,1,4], k = 3 输出:[12,10,16,13]
解释:每个数字都被接下来 3 个数字之和替换。
解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。
示例 2:输入:code = [1,2,3,4], k = 0 输出:[0,0,0,0]
解释:当 k 为 0 时,所有数字都被 0 替换。
示例 3:输入:code = [2,4,9,3], k = -2 输出:[12,5,6,13]
解释:解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。
如果 k 是负数,那么和为 之前 的数字。
提示:n == code.length
1 <= n<= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func decrypt(code []int, k int) []int {
    n := len(code)
    res := make([]int, n)
    if k == 0 {
        return res
    }
    for i := 0; i < n; i++ {
        sum := 0
        for j := 1; j <= abs(k); j++ {
            if k > 0 {
                sum = sum + code[(i+j+n)%n]
            } else {
                sum = sum + code[(i-j+n)%n]
            }
        }
        res[i] = sum
    }
    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

1656.设计有序流(1)

  • 题目
有 n 个 (id, value) 对,其中 id 是 1 到 n 之间的一个整数,value 是一个字符串。
不存在 id 相同的两个(id, value) 对。
设计一个流,以 任意 顺序获取 n个(id, value)对,并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类:
OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后:
如果流存储有 id = ptr 的 (id, value) 对,则找出从 id = ptr 开始的 最长 id 连续递增序列 ,
并 按顺序 返回与这些 id 关联的值的列表。然后,将 ptr 更新为最后那个 id + 1。
否则,返回一个空列表。
示例:输入["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
解释: OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc"),返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa"),返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb"),返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee"),返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd"),返回 ["ddddd", "eeeee"]
提示:1 <= n <= 1000
1 <= id <= n
value.length == 5
value 仅由小写字母组成
每次调用 insert 都会使用一个唯一的 id
恰好调用 n 次 insert
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组 O(n) O(n)
type OrderedStream struct {
    arr []string
    ptr int
}

func Constructor(n int) OrderedStream {
    return OrderedStream{
        arr: make([]string, n+1),
        ptr: 1,
    }
}

func (this *OrderedStream) Insert(id int, value string) []string {
    res := make([]string, 0)
    this.arr[id] = value
    if this.ptr < id-1 {
        return res
    }
    for i := this.ptr; i < len(this.arr); i++ {
        if this.arr[i] == "" {
            break
        }
        res = append(res, this.arr[i])
        this.ptr++
    }
    return res
}

1662.检查两个字符串数组是否相等(2)

  • 题目
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同,返回 true ;否则,返回 false 。
数组表示的字符串是由数组中的所有元素 按顺序 连接形成的字符串。
示例 1:输入:word1 = ["ab", "c"], word2 = ["a", "bc"] 输出:true
解释:word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同,返回 true
示例 2:输入:word1 = ["a", "cb"], word2 = ["ab", "c"] 输出:false
示例 3:输入:word1  = ["abc", "d", "defg"], word2 = ["abcddefg"] 输出:true
提示:1 <= word1.length, word2.length <= 103
1 <= word1[i].length, word2[i].length <= 103
1 <= sum(word1[i].length), sum(word2[i].length) <= 103
word1[i] 和 word2[i] 由小写字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(n)
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
    return strings.Join(word1,"") == strings.Join(word2,"")
}

# 2
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
    str1 := ""
    str2 := ""
    for i := 0; i < len(word1); i++ {
        str1 = str1 + word1[i]
    }
    for i := 0; i < len(word2); i++ {
        str2 = str2 + word2[i]
    }
    return str1 == str2
}

1668.最大重复子字符串(1)

  • 题目
给你一个字符串sequence,如果字符串 word连续重复k次形成的字符串是sequence的一个子字符串,
那么单词word 的 重复值为 k 。单词 word的 最大重复值是单词word在sequence中最大的重复值。
如果word不是sequence的子串,那么重复值k为 0 。
给你一个字符串 sequence和 word,请你返回 最大重复值k 。
示例 1:输入:sequence = "ababc", word = "ab" 输出:2
解释:"abab" 是 "ababc" 的子字符串。
示例 2:输入:sequence = "ababc", word = "ba" 输出:1
解释:"ba" 是 "ababc" 的子字符串,但 "baba" 不是 "ababc" 的子字符串。
示例 3:输入:sequence = "ababc", word = "ac" 输出:0
解释:"ac" 不是 "ababc" 的子字符串。
提示:1 <= sequence.length <= 100
1 <= word.length <= 100
sequence 和word都只包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
func maxRepeating(sequence string, word string) int {
    res := 0
    for i := 1; ; i++ {
        if strings.Contains(sequence, strings.Repeat(word, i)) == false {
            break
        } else {
            res = i
        }
    }
    return res
}

1672.最富有客户的资产总量(1)

  • 题目
给你一个 m x n 的整数网格 accounts ,其中 accounts[i][j] 是第 i位客户在第 j 家银行托管的资产数量。
返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
示例 1:输入:accounts = [[1,2,3],[3,2,1]] 输出:6
解释:第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的,资产总量都是 6 ,所以返回 6 。
示例 2:输入:accounts = [[1,5],[7,3],[3,5]] 输出:10
解释:第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的,资产总量是 10
示例 3:输入:accounts = [[2,8,7],[7,1,3],[1,9,5]] 输出:17
提示:m ==accounts.length
n ==accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
func maximumWealth(accounts [][]int) int {
    res := 0
    for i := 0; i < len(accounts); i++ {
        sum := 0
        for j := 0; j < len(accounts[i]); j++ {
            sum = sum + accounts[i][j]
        }
        if sum > res {
            res = sum
        }
    }
    return res
}

1678.设计Goal解析器(2)

  • 题目
请你设计一个可以解释字符串 command 的 Goal 解析器 。
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。
Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ,"(al)" 解释为字符串 "al" 。
然后,按原顺序将经解释得到的字符串连接成一个字符串。
给你字符串 command ,返回 Goal 解析器 对 command 的解释结果。
示例 1:输入:command = "G()(al)" 输出:"Goal"
解释:Goal 解析器解释命令的步骤如下所示:
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"
示例 2:输入:command = "G()()()()(al)" 输出:"Gooooal"
示例 3:输入:command = "(al)G(al)()()G" 输出:"alGalooG"
提示:1 <= command.length <= 100
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(n)
func interpret(command string) string {
    command = strings.ReplaceAll(command, "(al)", "al")
    command = strings.ReplaceAll(command, "()", "o")
    return command
}

# 2
func interpret(command string) string {
    res := ""
    for i := 0; i < len(command); {
        if command[i] == 'G' {
            res = res + "G"
            i = i + 1
        } else if command[i] == '(' {
            if command[i+1] == ')' {
                res = res + "o"
                i = i + 2
            } else {
                res = res + "al"
                i = i + 4
            }
        }
    }
    return res
}

1684.统计一致字符串的数目(1)

  • 题目
给你一个由不同字符组成的字符串allowed和一个字符串数组words。
如果一个字符串的每一个字符都在 allowed中,就称这个字符串是 一致字符串。
请你返回words数组中一致字符串的数目。
示例 1:输入:allowed = "ab", words = ["ad","bd","aaab","baa","badab"] 输出:2
解释:字符串 "aaab" 和 "baa" 都是一致字符串,因为它们只包含字符 'a' 和 'b' 。
示例 2:输入:allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"] 输出:7
解释:所有字符串都是一致的。
示例 3:输入:allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"] 输出:4
解释:字符串 "cc","acd","ac" 和 "d" 是一致字符串。
提示:1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
allowed中的字符 互不相同。
words[i] 和allowed只包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n)
func countConsistentStrings(allowed string, words []string) int {
    res := 0
    m := make(map[byte]bool)
    for i := 0; i < len(allowed); i++ {
        m[allowed[i]] = true
    }

    for _, word := range words {
        flag := true
        for i := 0; i < len(word); i++ {
            if _, ok := m[word[i]]; !ok {
                flag = false
                break
            }
        }
        if flag == true {
            res++
        }
    }
    return res
}

1688.比赛中的配对次数(2)

  • 题目
给你一个整数 n ,表示比赛中的队伍数。比赛遵循一种独特的赛制:
如果当前队伍数是 偶数 ,那么每支队伍都会与另一支队伍配对。
总共进行 n / 2 场比赛,且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ,那么将会随机轮空并晋级一支队伍,其余的队伍配对。
总共进行 (n - 1) / 2 场比赛,且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数,直到决出获胜队伍为止。
示例 1:输入:n = 7 输出:6
解释:比赛详情:
- 第 1 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。
- 第 2 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。
- 第 3 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6
示例 2:输入:n = 14 输出:13
解释:比赛详情:
- 第 1 轮:队伍数 = 14 ,配对次数 = 7 ,7 支队伍晋级。
- 第 2 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。 
- 第 3 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。
- 第 4 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13
提示:1 <= n <= 200
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(log(n)) O(1)
02 数学 O(1) O(1)
func numberOfMatches(n int) int {
    res := 0
    for n > 1 {
        res = res + n/2
        n = n/2 + n%2
    }
    return res
}

# 2
func numberOfMatches(n int) int {
    // 共有n个队伍,一个冠军,需要淘汰n-1个 队伍。
    // 每一场比赛淘汰一个队伍,因此进行了n-1场比赛。
    return n - 1
}

1694.重新格式化电话号码(1)

  • 题目
给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。
请你按下述方式重新格式化电话号码。
首先,删除 所有的空格和破折号。
其次,将数组从左到右 每 3 个一组 分块,直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块:
2 个数字:单个含 2 个数字的块。
3 个数字:单个含 3 个数字的块。
4 个数字:两个分别含 2 个数字的块。
最后用破折号将这些块连接起来。
注意,重新格式化过程中 不应该 生成仅含 1 个数字的块,并且 最多 生成两个含 2 个数字的块。
返回格式化后的电话号码。
示例 1:输入:number = "1-23-45 6" 输出:"123-456"
解释:数字是 "123456"
步骤 1:共有超过 4 个数字,所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2:剩下 3 个数字,将它们放入单个含 3 个数字的块。第 2 个块是 "456" 。
连接这些块后得到 "123-456" 。
示例 2:输入:number = "123 4-567" 输出:"123-45-67"
解释:数字是 "1234567".
步骤 1:共有超过 4 个数字,所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2:剩下 4 个数字,所以将它们分成两个含 2 个数字的块。这 2 块分别是 "45" 和 "67" 。
连接这些块后得到 "123-45-67" 。
示例 3:输入:number = "123 4-5678" 输出:"123-456-78"
解释:数字是 "12345678" 。
步骤 1:第 1 个块 "123" 。
步骤 2:第 2 个块 "456" 。
步骤 3:剩下 2 个数字,将它们放入单个含 2 个数字的块。第 3 个块是 "78" 。
连接这些块后得到 "123-456-78" 。
示例 4:输入:number = "12" 输出:"12"
示例 5:输入:number = "--17-5 229 35-39475 " 输出:"175-229-353-94-75"
提示:2 <= number.length <= 100
number 由数字和字符 '-' 及 ' ' 组成。
number 中至少含 2 个数字。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
func reformatNumber(number string) string {
    str := strings.ReplaceAll(number, "-", "")
    str = strings.ReplaceAll(str, " ", "")
    res := ""
    for len(str) > 4 {
        res = res + str[:3] + "-"
        str = str[3:]
    }
    if len(str) == 4 {
        res = res + str[:2] + "-" + str[2:]
    } else {
        res = res + str
    }
    return res
}

1700.无法吃午餐的学生数量(1)

  • 题目
学校的自助午餐提供圆形和方形的三明治,分别用数字0和1表示。
所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里,每一轮:
如果队列最前面的学生喜欢栈顶的三明治,那么会拿走它并离开队列。
否则,这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组students 和sandwiches,
其中sandwiches[i]是栈里面第i个三明治的类型(i = 0是栈的顶部),
students[j]是初始队列里第j名学生对三明治的喜好(j = 0是队列的最开始位置)。
请你返回无法吃午餐的学生数量。
示例 1:输入:students = [1,1,0,0], sandwiches = [0,1,0,1] 输出:0 
解释:- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [0,1,1],
三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1,0],三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1],三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [],三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。
示例 2:输入:students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] 输出:3
提示:1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i]要么是0,要么是1。
students[i]要么是0,要么是1。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func countStudents(students []int, sandwiches []int) int {
    a, b := 0, 0
    for i := 0; i < len(students); i++ {
        if students[i] == 0 {
            a++
        } else {
            b++
        }
    }
    for i := 0; i < len(sandwiches); i++ {
        if sandwiches[i] == 0 && a > 0 {
            a--
        } else if sandwiches[i] == 1 && b > 0 {
            b--
        } else {
            break
        }
    }
    return a + b
}

1601-1700-Medium

1604.警告一小时内使用相同员工卡大于等于三次的人(2)

  • 题目
力扣公司的员工都使用员工卡来开办公室的门。
每当一个员工使用一次他的员工卡,安保系统会记录下员工的名字和使用时间。
如果一个员工在一小时时间内使用员工卡的次数大于等于三次,这个系统会自动发布一个 警告 。
给你字符串数组 keyName 和 keyTime ,
其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。
使用时间的格式是 24小时制 ,形如 "HH:MM" ,比方说 "23:51" 和 "09:49" 。
请你返回去重后的收到系统警告的员工名字,将它们按 字典序升序 排序后返回。
请注意 "10:00" - "11:00" 视为一个小时时间范围内,
而 "23:51" - "00:10" 不被视为一小时内,因为系统记录的是某一天内的使用情况。
示例 1:输入:keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], 
keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出:["daniel"]
解释:"daniel" 在一小时内使用了 3 次员工卡("10:00","10:40","11:00")。
示例 2:输入:keyName = ["alice","alice","alice","bob","bob","bob","bob"], 
keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出:["bob"]
解释:"bob" 在一小时内使用了 3 次员工卡("21:00","21:20","21:30")。
示例 3:输入:keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
输出:[]
示例 4:输入:keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], 
keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
输出:["clare","leslie"]
提示:1 <= keyName.length, keyTime.length <= 105
    keyName.length == keyTime.length
    keyTime 格式为 "HH:MM" 。
    保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
    1 <= keyName[i].length <= 10
    keyName[i] 只包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希+排序+遍历 O(nlog(n)) O(n)
02 哈希+排序+滑动窗口 O(nlog(n)) O(n)
func alertNames(keyName []string, keyTime []string) []string {
    m := make(map[string][]int)
    for i := 0; i < len(keyName); i++ {
        m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
    }
    res := make([]string, 0)
    for k, v := range m {
        sort.Ints(v)
        first := v[0]
        second := v[0]
        count := 1
        for i := 1; i < len(v); i++ {
            if v[i] > first && v[i]-first <= 60 {
                second = v[i]
                count++
            } else {
                first = second
                second = v[i]
                count = 2
            }
            if count >= 3 {
                res = append(res, k)
                break
            }
        }
    }
    sort.Strings(res)
    return res
}

func strToInt(str string) int {
    arr := strings.Split(str, ":")
    hour, _ := strconv.Atoi(arr[0])
    minute, _ := strconv.Atoi(arr[1])
    return hour*60 + minute
}

# 2
func alertNames(keyName []string, keyTime []string) []string {
    m := make(map[string][]int)
    for i := 0; i < len(keyName); i++ {
        m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
    }
    res := make([]string, 0)
    for k, v := range m {
        sort.Ints(v)
        for i := 0; i < len(v)-2; i++ {
            if v[i+2]-v[i] <= 60 {
                res = append(res, k)
                break
            }
        }
    }
    sort.Strings(res)
    return res
}

func strToInt(str string) int {
    arr := strings.Split(str, ":")
    hour, _ := strconv.Atoi(arr[0])
    minute, _ := strconv.Atoi(arr[1])
    return hour*60 + minute
}

1605.给定行和列的和求可行矩阵(1)

  • 题目
给你两个非负整数数组 rowSum 和 colSum ,其中 rowSum[i] 是二维矩阵中第 i 行元素的和, 
colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素,但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵,
且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵,题目保证存在 至少一个 可行矩阵。
示例 1:输入:rowSum = [3,8], colSum = [4,7] 输出:[[3,0],
      [1,7]]
解释:第 0 行:3 + 0 = 0 == rowSum[0]
第 1 行:1 + 7 = 8 == rowSum[1]
第 0 列:3 + 1 = 4 == colSum[0]
第 1 列:0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求,且所有矩阵元素都是非负的。
另一个可行的矩阵为:[[1,2],
                  [3,5]]
示例 2:输入:rowSum = [5,7,10], colSum = [8,6,8] 
输出:[[0,5,0],
      [6,1,0],
      [2,0,8]]
示例 3:输入:rowSum = [14,9], colSum = [6,9,8]
输出:[[0,9,5],
      [6,0,3]]
示例 4:输入:rowSum = [1,0], colSum = [1]
输出:[[1],
      [0]]
示例 5:输入:rowSum = [0], colSum = [0]
输出:[[0]]
提示:1 <= rowSum.length, colSum.length <= 500
    0 <= rowSum[i], colSum[i] <= 108
    sum(rows) == sum(columns)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n^2) O(n^2)
func restoreMatrix(rowSum []int, colSum []int) [][]int {
    n := len(rowSum)
    m := len(colSum)
    res := make([][]int, n)
    for i := 0; i < n; i++ {
        res[i] = make([]int, m)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            value := min(rowSum[i], colSum[j])
            res[i][j] = value
            rowSum[i] = rowSum[i] - value
            colSum[j] = colSum[j] - value
        }
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1609.奇偶树(1)

  • 题目
如果一棵二叉树满足下述几个条件,则可以称为 奇偶树 :
    二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。
    偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增
    奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减
给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false 。
示例 1:输入:root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出:true
解释:每一层的节点值分别是:
0 层:[1]
1 层:[10,4]
2 层:[3,7,9]
3 层:[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增,而 1 层和 3 层上的节点值都是偶数且严格递减,
因此这是一棵奇偶树。
示例 2:输入:root = [5,4,2,3,3,7] 输出:false
解释:每一层的节点值分别是:
0 层:[5]
1 层:[4,2]
2 层:[3,3,7]
2 层上的节点值不满足严格递增的条件,所以这不是一棵奇偶树。
示例 3:输入:root = [5,9,1,3,5,7] 输出:false
解释:1 层上的节点值应为偶数。
示例 4:输入:root = [1]输出:true
示例 5:输入:root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17] 输出:true
提示:树中节点数在范围 [1, 105] 内
    1 <= Node.val <= 106
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 层序遍历 O(n) O(n)
func isEvenOddTree(root *TreeNode) bool {
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    level := 1
    for len(queue) > 0 {
        length := len(queue)
        temp := make([]int, 0)
        for i := 0; i < length; i++ {
            temp = append(temp, queue[i].Val)
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left)
            }
            if queue[i].Right != nil {
                queue = append(queue, queue[i].Right)
            }
        }
        if level%2 == 0 {
            for j := 0; j < len(temp)/2; j++ {
                temp[j], temp[len(temp)-1-j] = temp[len(temp)-1-j], temp[j]
            }
        }
        for i := 0; i < len(temp); i++ {
            if i < len(temp)-1 && temp[i] >= temp[i+1] {
                return false
            }
            if temp[i]%2 != level%2 {
                return false
            }
        }
        queue = queue[length:]
        level++
    }
    return true
}

1615.最大网络秩(1)

  • 题目
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。
每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为:与这两座城市 直接 相连的道路总数。
如果存在一条道路直接连接这两座城市,则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads,返回整个基础设施网络的 最大网络秩 。
示例 1:输入:n = 4, roads = [[0,1],[0,3],[1,2],[1,3]] 输出:4
解释:城市 0 和 1 的网络秩是 4,因为共有 4 条道路与城市 0 或 1 相连。
位于 0 和 1 之间的道路只计算一次。
示例 2:输入:n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] 输出:5
解释:共有 5 条道路与城市 1 或 2 相连。
示例 3:输入:n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] 输出:5
解释:2 和 5 的网络秩为 5,注意并非所有的城市都需要连接起来。
提示:2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= ai, bi<= n-1
ai!=bi
每对城市之间 最多只有一条道路相连
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n)
func maximalNetworkRank(n int, roads [][]int) int {
    arr := make([]int, n)
    m := make(map[int]int)
    for i := 0; i < len(roads); i++ {
        a, b := roads[i][0], roads[i][1]
        arr[a]++
        arr[b]++
        m[a*100+b]++
        m[b*100+a]++
    }
    res := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            value := arr[i] + arr[j] - m[i*100+j]
            if value > res {
                res = value
            }
        }
    }
    return res
}

1616.分割两个字符串得到回文串(2)

  • 题目
给你两个字符串 a 和 b ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。
由 a 可以得到两个字符串: aprefix 和 asuffix ,满足 a = aprefix + asuffix ,
同理,由 b 可以得到两个字符串 bprefix 和 bsuffix ,满足 b = bprefix + bsuffix 。
请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时, ssuffix 或者 sprefix 可以为空。
比方说, s = "abc" 那么 "" + "abc" , "a" + "bc" , "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ,那么请返回 true,否则返回 false 。
请注意, x + y 表示连接字符串 x 和 y 。
示例 1:输入:a = "x", b = "y" 输出:true
解释:如果 a 或者 b 是回文串,那么答案一定为 true ,因为你可以如下分割:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
那么 aprefix + bsuffix = "" + "y" = "y" 是回文串。
示例 2:输入:a = "ulacfd", b = "jizalu" 输出:true
解释:在下标为 3 处分割:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
那么 aprefix + bsuffix = "ula" + "alu" = "ulaalu" 是回文串。
提示:1 <= a.length, b.length <= 105
    a.length == b.length
    a 和 b 都只包含小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 双指针 O(n) O(1)
func checkPalindromeFormation(a string, b string) bool {
    if judge(a, b) == true || judge(b, a) == true {
        return true
    }
    return false
}

// 判断prefixA+suffixB是否是回文
func judge(a, b string) bool {
    left, right := 0, len(a)-1
    for left < right {
        if a[left] == b[right] {
            left++
            right--
        } else {
            break
        }
    }
    var i, j int
    // 2种判断
    // A1+A2+A3
    // B1+B2+B3
    // 1.reverse(A1)=B3,判断B2是否回文
    i, j = left, right
    for i < j {
        if b[i] == b[j] {
            i++
            j--
        } else {
            break
        }
    }
    if i >= j {
        return true
    }
    // 2.reverse(A1)=B3,判断A2是否回文
    i, j = left, right
    for i < j {
        if a[i] == a[j] {
            i++
            j--
        } else {
            break
        }
    }
    if i >= j {
        return true
    }
    return false
}

# 2
func checkPalindromeFormation(a string, b string) bool {
    start := len(a)/2 - 1 // 中间靠左坐标
    c := check(a, a, start)
    if check(a, b, c) == -1 || check(b, a, c) == -1 {
        return true
    }
    c = check(b, b, start)
    if check(a, b, c) == -1 || check(b, a, c) == -1 {
        return true
    }
    return false
}

// 从start往左边走,从n-1-start往右边走
func check(a, b string, start int) int {
    left := start
    right := len(a) - 1 - start
    for left >= 0 {
        if a[left] != b[right] {
            break
        }
        left--
        right++
    }
    return left
}

1620.网络信号最好的坐标(1)

  • 题目
给你一个数组 towers和一个整数 radius,数组中包含一些网络信号塔,
其中towers[i] = [xi, yi, qi]表示第i个网络信号塔的坐标是(xi, yi)且信号强度参数为qi。
所有坐标都是在 X-Y 坐标系内的整数坐标。两个坐标之间的距离用 欧几里得距离计算。
整数radius表示一个塔 能到达的 最远距离。
如果一个坐标跟塔的距离在 radius以内,那么该塔的信号可以到达该坐标。
在这个范围以外信号会很微弱,所以 radius以外的距离该塔是 不能到达的。
如果第 i个塔能到达 (x, y),那么该塔在此处的信号为⌊qi / (1 + d)⌋,其中d是塔跟此坐标的距离。
一个坐标的 网络信号是所有 能到达该坐标的塔的信号强度之和。
请你返回 网络信号最大的整数坐标点。如果有多个坐标网络信号一样大,请你返回字典序最小的一个坐标。
注意:坐标(x1, y1)字典序比另一个坐标(x2, y2)小:要么x1 < x2,要么x1 == x2 且y1 < y2。
⌊val⌋表示小于等于val的最大整数(向下取整函数)。
示例 1:输入:towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2 输出:[2,1]
解释:坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ,在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ,在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ,在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
示例 2:输入:towers = [[23,11,21]], radius = 9 输出:[23,11]
示例 3:输入:towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2 输出:[1,2]
示例 4:输入:towers = [[2,1,9],[0,1,9]], radius = 2 输出:[0,1]
解释:坐标 (0, 1) 和坐标 (2, 1) 都是强度最大的位置,但是 (0, 1) 字典序更小。
提示:1 <= towers.length <= 50
towers[i].length == 3
0 <= xi, yi, qi <= 50
1 <= radius <= 50
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n) O(1)
func bestCoordinate(towers [][]int, radius int) []int {
    res := []int{0, 0}
    maxValue := 0
    for i := 0; i <= 50; i++ {
        for j := 0; j <= 50; j++ {
            sum := 0
            for k := 0; k < len(towers); k++ {
                a, b, c := towers[k][0], towers[k][1], towers[k][2]
                d := (a-i)*(a-i) + (b-j)*(b-j)
                if d <= radius*radius {
                    value := float64(c) / (1 + math.Sqrt(float64(d)))
                    sum = sum + int(math.Floor(value))
                }
            }
            if sum > maxValue {
                maxValue = sum
                res = []int{i, j}
            }
        }
    }
    return res
}

1621.大小为K的不重叠线段的数目(2)

  • 题目
给你一维空间的n个点,其中第i个点(编号从0 到n-1)位于x = i处,
请你找到恰好k个不重叠线段且每个线段至少覆盖两个点的方案数。
线段的两个端点必须都是整数坐标。
这k个线段不需要全部覆盖全部n个点,且它们的端点可以重合。
请你返回 k个不重叠线段的方案数。由于答案可能很大,请将结果对109 + 7取余 后返回。
示例 1:输入:n = 4, k = 2 输出:5
解释:如图所示,两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)},{(0,1),(1,3)},{(0,1),(2,3)},
{(1,2),(2,3)},{(0,1),(1,2)} 。
示例 2:输入:n = 3, k = 1 输出:3
解释:总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。
示例 3:输入:n = 30, k = 7 输出:796297179
解释:画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。
示例 4:输入:n = 5, k = 3 输出:7
示例 5:输入:n = 3, k = 2 输出:1
提示:2 <= n <= 1000
1 <= k <= n-1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 数学-组合 O(n) O(1)
var mod = 1000000007

func numberOfSets(n int, k int) int {
    dp := make([][][2]int, n)
    // dp[i][j][0] =>0到i的点,构造成j条线段的方案数, 第j条线段的右端点没有使用i
    // dp[i][j][1] =>0到i的点,构造成j条线段的方案数, 第j条线段的右端点使用i
    for i := 0; i < n; i++ {
        dp[i] = make([][2]int, n)
    }
    dp[0][0][0] = 1
    for i := 1; i < n; i++ {
        for j := 0; j <= k; j++ {
            dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % mod // 没有使用i
            dp[i][j][1] = dp[i-1][j][1]                         // 使用i:扩展右侧
            if j > 0 {
                dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0] + dp[i-1][j-1][1]) % mod // 使用i:新开一个
            }
        }
    }
    return (dp[n-1][k][0] + dp[n-1][k][1]) % mod
}

# 2

# 2
var mod = 1000000007

func numberOfSets(n int, k int) int {
    // 共享k-1个点+n个点 => n+k-1个点
    // 共 n+k−1 个数中选择 2k 个
    return C(n+k-1, 2*k)
}

func C(n, m int) int {
    a := multiMod(n, n-m+1)
    b := multiMod(m, 1)
    return a * powMod(b, mod-2) % mod
}

func multiMod(n, m int) int {
    res := 1
    for i := m; i <= n; i++ {
        res = (res * i) % mod
    }
    return res
}

func powMod(a, b int) int {
    res := 1
    for b > 0 {
        if b%2 == 1 {
            res = (res * a) % mod
        }
        a = a * a % mod
        b = b / 2
    }
    return res
}

1625.执行操作后字典序最小的字符串(2)

  • 题目
给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。
你可以在 s 上按任意顺序多次执行下面两个操作之一:
累加:将 a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。
例如,s = "3456" 且 a = 5,则执行此操作后 s 变成 "3951"。
轮转:将 s 向右轮转 b 位。例如,s = "3456" 且 b = 1,则执行此操作后 s 变成 "6345"。
请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。
如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:
在 a 和 b 出现不同的第一个位置上,字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。
例如,"0158” 字典序比 "0190" 小,因为不同的第一个位置是在第三个字符,显然 '5' 出现在 '9' 之前。
示例 1:输入:s = "5525", a = 9, b = 2 输出:"2050"
解释:执行操作如下:
初态:"5525"
轮转:"2555"
累加:"2454"
累加:"2353"
轮转:"5323"
累加:"5222"
累加:"5121"
轮转:"2151"
累加:"2050"
无法获得字典序小于 "2050" 的字符串。
示例 2:输入:s = "74", a = 5, b = 1 输出:"24"
解释:执行操作如下:
初态:"74"
轮转:"47"
累加:"42"
轮转:"24"
无法获得字典序小于 "24" 的字符串。
示例 3:输入:s = "0011", a = 4, b = 2 输出:"0011"
解释:无法获得字典序小于 "0011" 的字符串。
示例 4:输入:s = "43987654", a = 7, b = 3 输出:"00553311"
提示:2 <= s.length <= 100
s.length 是偶数
s 仅由数字 0 到 9 组成
1 <= a <= 9
1 <= b <= s.length - 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n)
02 广度优先搜索 O(n^2) O(n)
var m map[string]bool
var res string

func findLexSmallestString(s string, a int, b int) string {
    res = s
    m = make(map[string]bool)
    dfs(s, a, b)
    return res
}

func dfs(s string, a, b int) {
    if m[s] == true {
        return
    }
    m[s] = true
    if s < res {
        res = s
    }
    dfs(add(s, a), a, b)
    dfs(s[b:]+s[:b], a, b)
}

func add(s string, a int) string {
    res := []byte(s)
    for i := 1; i < len(s); i = i + 2 {
        res[i] = byte('0' + (int(s[i]-'0')+a)%10)
    }
    return string(res)
}

# 2
func findLexSmallestString(s string, a int, b int) string {
    res := s
    m := make(map[string]bool)
    queue := make([]string, 0)
    queue = append(queue, s)
    for len(queue) > 0 {
        str := queue[0]
        queue = queue[1:]
        if m[str] == true {
            continue
        }
        m[str] = true
        if str < res {
            res = str
        }
        queue = append(queue, str[b:]+str[:b])
        queue = append(queue, add(str, a))
    }
    return res
}

func add(s string, a int) string {
    res := []byte(s)
    for i := 1; i < len(s); i = i + 2 {
        res[i] = byte('0' + (int(s[i]-'0')+a)%10)
    }
    return string(res)
}

1626.无矛盾的最佳球队(1)

  • 题目
假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。
球队的得分是球队中所有球员的分数 总和 。
然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。
如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员,则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages,其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。
请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
示例 1:输入:scores = [1,3,5,10,15], ages = [1,2,3,4,5] 输出:34
解释:你可以选中所有球员。
示例 2:输入:scores = [4,5,6,5], ages = [2,1,2,1] 输出:16
解释:最佳的选择是后 3 名球员。注意,你可以选中多个同龄球员。
示例 3:输入:scores = [1,2,3,5], ages = [8,9,10,1] 输出:6
解释:最佳的选择是前 3 名球员。
提示: 1 <= scores.length, ages.length <= 1000
    scores.length == ages.length
    1 <= scores[i] <= 10^6
    1 <= ages[i] <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
func bestTeamScore(scores []int, ages []int) int {
    arr := make([][2]int, 0)
    for i := 0; i < len(ages); i++ {
        arr = append(arr, [2]int{ages[i], scores[i]})
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] == arr[j][0] {
            return arr[i][1] < arr[j][1]
        }
        return arr[i][0] < arr[j][0]
    })
    dp := make([]int, len(arr))
    res := 0
    for i := 0; i < len(arr); i++ {
        dp[i] = arr[i][1]
        for j := 0; j < i; j++ {
            if arr[j][1] <= arr[i][1] {
                dp[i] = max(dp[i], dp[j]+arr[i][1])
            }
        }
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1630.等差子数组(1)

  • 题目
如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是 等差数列 。
更正式地,数列 s 是等差数列,只需要满足:对于每个有效的 i , s[i+1] - s[i] == s[1] - s[0] 都成立。
例如,下面这些都是 等差数列 :
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
下面的数列 不是等差数列 :
1, 1, 2, 5, 7
给你一个由 n 个整数组成的数组 nums,和两个由 m 个整数组成的数组 l 和 r,后两个数组表示 m 组范围查询,
其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , 
nums[r[i]] 可以 重新排列 形成 等差数列 ,answer[i] 的值就是 true;否则answer[i] 的值就是 false 。
示例 1:输入:nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5] 输出:[true,false,true]
解释:第 0 个查询,对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询,对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询,对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。
示例 2:输入:nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], 
l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
输出:[false,true,false,false,true,true]
提示:n == nums.length
    m == l.length
    m == r.length
    2 <= n <= 500
    1 <= m <= 500
    0 <= l[i] < r[i] < n
    -105 <= nums[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(n^2*log(n)) O(n)
func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
    res := make([]bool, 0)
    for i := 0; i < len(l); i++ {
        flag := true
        arr := make([]int, 0)
        arr = append(arr, nums[l[i]:r[i]+1]...)
        sort.Ints(arr)
        for j := 2; j < len(arr); j++ {
            if arr[j]-arr[j-1] != arr[1]-arr[0] {
                flag = false
                break
            }
        }
        res = append(res, flag)
    }
    return res
}

1631.最小体力消耗路径(4)

  • 题目
你准备参加一场远足活动。给你一个二维rows x columns的地图heights,
其中heights[row][col]表示格子(row, col)的高度。
一开始你在最左上角的格子(0, 0),且你希望去最右下角的格子(rows-1, columns-1)(注意下标从 0 开始编号)。
你每次可以往 上,下,左,右四个方向之一移动,你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值是路径上相邻格子之间 高度差绝对值的 最大值决定的。
请你返回从左上角走到右下角的最小体力消耗值。
示例 1:输入:heights = [[1,2,2],[3,8,2],[5,3,5]] 输出:2
解释:路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优,因为另一条路径差值最大值为 3 。
示例 2:输入:heights = [[1,2,3],[3,8,4],[5,3,5]] 输出:1
解释:路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ,比路径 [1,3,5,3,5] 更优。
示例 3:输入:heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出:0
解释:上图所示路径不需要消耗任何体力。
提示:rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找+广度优先搜索 O(n^2log(n)) O(n^2)
02 并查集 O(n^2log(n)) O(n^2)
03 Dijkstra O(n^2log(n)) O(n^2)
04 二分查找+广度优先搜索+内置函数 O(n^2log(n)) O(n^2)
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func minimumEffortPath(heights [][]int) int {
    n, m := len(heights), len(heights[0])
    left, right := 0, 1000000
    res := 0
    for left <= right {
        mid := left + (right-left)/2 // 二分枚举最大值
        queue := make([][2]int, 0)
        queue = append(queue, [2]int{0, 0})
        visited := make([][]bool, n)
        for i := 0; i < n; i++ {
            visited[i] = make([]bool, m)
        }
        for len(queue) > 0 {
            a, b := queue[0][0], queue[0][1]
            queue = queue[1:]
            for i := 0; i < 4; i++ {
                x, y := a+dx[i], b+dy[i]
                if 0 <= x && x < n && 0 <= y && y < m &&
                    visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= mid {
                    queue = append(queue, [2]int{x, y})
                    visited[x][y] = true
                }
            }
        }
        if visited[n-1][m-1] == true { // 缩小范围
            res = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return res
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

# 2
func minimumEffortPath(heights [][]int) int {
    n, m := len(heights), len(heights[0])
    arr := make([][3]int, 0) // 相邻格子可以连一条边,高度差绝对值最为边的权值
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            index := i*m + j // 转化为一维坐标
            if i > 0 {
                value := abs(heights[i][j] - heights[i-1][j])      // 上到下
                arr = append(arr, [3]int{index - m, index, value}) // 之前坐标,当前坐标,绝对值
            }
            if j > 0 {
                value := abs(heights[i][j] - heights[i][j-1])      // 左到右
                arr = append(arr, [3]int{index - 1, index, value}) // 之前坐标,当前坐标,绝对值
            }
        }
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][2] < arr[j][2]
    })
    fa = Init(n * m)
    for i := 0; i < len(arr); i++ { // 从小到大枚举高度差绝对值
        a, b, c := arr[i][0], arr[i][1], arr[i][2]
        union(a, b)
        if query(0, n*m-1) == true {
            return c
        }
    }
    return 0
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

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)
}

# 3
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func minimumEffortPath(heights [][]int) int {
    n, m := len(heights), len(heights[0])
    arr := make([][]int, n) //  高度差绝对值的最大值
    for i := 0; i < n; i++ {
        arr[i] = make([]int, m)
        for j := 0; j < m; j++ {
            arr[i][j] = math.MaxInt32 // 初始化为最大值
        }
    }
    arr[0][0] = 0
    intHeap := make(IntHeap, 0)
    heap.Init(&intHeap)
    heap.Push(&intHeap, [3]int{0, 0, 0})
    for {
        node := heap.Pop(&intHeap).([3]int)
        a, b, c := node[0], node[1], node[2]
        if a == n-1 && b == m-1 { // 返回结果
            return c
        }
        if arr[a][b] < c { // 大于 高度差绝对值的最大值,跳过
            continue
        }
        for i := 0; i < 4; i++ {
            x, y := a+dx[i], b+dy[i]
            if 0 <= x && x < n && 0 <= y && y < m {
                diff := max(c, abs(heights[x][y]-heights[a][b])) // 更新:去 高度差绝对值的最大值 的较大值
                if diff < arr[x][y] {                            // 更新:加入堆,点会重复,通过更新arr[x][y]来过滤
                    arr[x][y] = diff
                    heap.Push(&intHeap, [3]int{x, y, diff})
                }
            }
        }
    }
    return 0
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type IntHeap [][3]int

func (h IntHeap) Len() int {
    return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
    return h[i][2] < h[j][2]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.([3]int))
}

func (h *IntHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

# 4
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func minimumEffortPath(heights [][]int) int {
    n, m := len(heights), len(heights[0])
    return sort.Search(1000000, func(target int) bool {
        queue := make([][2]int, 0)
        queue = append(queue, [2]int{0, 0})
        visited := make([][]bool, n)
        for i := 0; i < n; i++ {
            visited[i] = make([]bool, m)
        }
        for len(queue) > 0 {
            a, b := queue[0][0], queue[0][1]
            queue = queue[1:]
            if a == n-1 && b == m-1 {
                return true
            }
            for i := 0; i < 4; i++ {
                x, y := a+dx[i], b+dy[i]
                if 0 <= x && x < n && 0 <= y && y < m &&
                    visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= target {
                    queue = append(queue, [2]int{x, y})
                    visited[x][y] = true
                }
            }
        }
        return false
    })
    return 0
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

1637.两点之间不包含任何点的最宽垂直面积(1)

  • 题目
给你 n 个二维平面上的点 points ,其中 points[i] = [xi, yi] ,
请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
垂直面积 的定义是固定宽度,而 y 轴上无限延伸的一块区域(也就是高度为无穷大)。
最宽垂直面积 为宽度最大的一个垂直面积。
请注意,垂直区域 边上 的点 不在 区域内。
示例 1:输入:points = [[8,7],[9,9],[7,4],[9,7]] 输出:1
解释:红色区域和蓝色区域都是最优区域。
示例 2:输入:points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] 输出:3
提示: n == points.length
    2 <= n <= 105
    points[i].length == 2
    0 <= xi, yi <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
func maxWidthOfVerticalArea(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
        return points[i][0] < points[j][0]
    })
    res := 0
    for i := 1; i < len(points); i++ {
        res = max(res, points[i][0]-points[i-1][0])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1638.统计只差一个字符的子串数目(3)

  • 题目
给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换 一个不同字符 以后,
是 t 串的子串。换言之,请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。
比方说, "computer" 和 "computation" 加粗部分只有一个字符不同: 
'e'/'a' ,所以这一对子字符串会给答案加 1 。
请你返回满足上述条件的不同子字符串对数目。
一个 子字符串 是一个字符串中连续的字符。
示例 1:输入:s = "aba", t = "baba" 输出:6
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 2:输入:s = "ab", t = "bb" 输出:3
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 3:输入:s = "a", t = "a" 输出:0
示例 4:输入:s = "abe", t = "bbc" 输出:10
提示:1 <= s.length, t.length <= 100
    s 和 t 都只包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^3) O(1)
02 暴力法 O(n^4) O(n)
03 动态规划 O(n^2) O(n^2)
func countSubstrings(s string, t string) int {
    res := 0
    for i := 0; i < len(s); i++ {
        for j := 0; j < len(t); j++ {
            diff := 0
            for k := 0; i+k < len(s) && j+k < len(t); k++ {
                if s[i+k] != t[j+k] {
                    diff++
                }
                if diff > 1 {
                    break
                }
                if diff == 1 {
                    res++
                }
            }
        }
    }
    return res
}

# 2
func countSubstrings(s string, t string) int {
    res := 0
    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            length := j - i
            newStr := s[i:j]
            for k := 0; k <= len(t)-length; k++ {
                b := t[k : k+length]
                if compare(newStr, b) {
                    res++
                }
            }
        }
    }
    return res
}

func compare(a, b string) bool {
    count := 0
    for i := 0; i < len(a); i++ {
        if a[i] != b[i] {
            count++
        }
        if count >= 2 {
            return false
        }
    }
    if count == 0 {
        return false
    }
    return true
}

# 3
func countSubstrings(s, t string) int {
    res := 0
    m, n := len(s), len(t)
    // dp以s[i]和t[j]结尾的所有子串对中,满足恰好只有一个字符不同的字符串对的数目
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    // 以s[i]和t[j]为结尾的子串,最多有多少个连续相同的字符
    same := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        same[i] = make([]int, n+1)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if s[i] == t[j] {
                dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j]
                same[i+1][j+1] = same[i][j] + 1
            } else {
                dp[i+1][j+1] = same[i][j] + 1
            }
            res = res + dp[i+1][j+1]
        }
    }
    return res
}

1641.统计字典序元音字符串的数目(3)

  • 题目
给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足:对于所有有效的 i,
s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1:输入:n = 1 输出:5
解释:仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
示例 2:输入:n = 2 输出:15
解释:仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意,"ea" 不是符合题意的字符串,因为 'e' 在字母表中的位置比 'a' 靠后
示例 3:输入:n = 33 输出:66045
提示:1 <= n <= 50
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 动态规划 O(n) O(1)
03 数学 O(1) O(1)
func countVowelStrings(n int) int {
    dp := make([][5]int, n+1)
    dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 1, 1, 1, 1, 1
    for i := 1; i <= n; i++ {
        for j := 0; j < 5; j++ {
            for k := 0; k <= j; k++ {
                dp[i][j] = dp[i][j] + dp[i-1][k]
            }
        }
    }
    res := 0
    for i := 0; i < 5; i++ {
        res = res + dp[n-1][i]
    }
    return res
}

# 2
func countVowelStrings(n int) int {
    dp := make([]int, 5)
    dp[0] = 1
    for i := 0; i < n; i++ {
        for j := 1; j < 5; j++ {
            dp[j] = dp[j] + dp[j-1]
        }
    }
    res := 0
    for i := 0; i < 5; i++ {
        res = res + dp[i]
    }
    return res
}

# 3
// 将n个小球放到m个盒子里,盒子可以空:C(n+m-1, m-1) m=5 => C(n+4,4)
// 在n+4中选择4个整数(4*3*2)
func countVowelStrings(n int) int {
    return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24
}

1642.可以到达的最远建筑(2)

  • 题目
给你一个整数数组 heights ,表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程,不断向后面的建筑物移动,期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1(下标 从 0 开始 )时:
如果当前建筑物的高度 大于或等于 下一建筑物的高度,则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度,您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块,返回你可以到达的最远建筑物的下标(下标 从 0 开始 )。
示例 1:输入:heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 输出:4
解释:从建筑物 0 出发,你可以按此方案完成旅程:
- 不使用砖块或梯子到达建筑物 1 ,因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子,因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ,因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子,因为 6 < 9
无法越过建筑物 4 ,因为没有更多砖块或梯子。
示例 2:输入:heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 输出:7
示例 3:输入:heights = [14,3,19,3], bricks = 17, ladders = 0 输出:3
提示:1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
02 二分查找 O(nlog(n)^2) O(n)
func furthestBuilding(heights []int, bricks int, ladders int) int {
    if len(heights) <= 1 {
        return 0
    }
    intHeap := &IntHeap{}
    heap.Init(intHeap)
    need := 0
    for i := 1; i < len(heights); i++ {
        need = heights[i] - heights[i-1]
        if need <= 0 {
            continue
        }
        heap.Push(intHeap, need)
        if intHeap.Len() > ladders {
            need = heap.Pop(intHeap).(int)
            if need > bricks {
                return i - 1
            }
            bricks = bricks - need
        }
    }
    return len(heights) - 1
}

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

# 2
func furthestBuilding(heights []int, bricks int, ladders int) int {
    left, right := 0, len(heights)
    res := 0
    for left <= right {
        mid := left + (right-left)/2
        if check(heights[0:mid], bricks, ladders) {
            left = mid + 1
            res = mid
        } else {
            right = mid - 1
        }
    }
    return res - 1
}

func check(heights []int, bricks int, ladders int) bool {
    arr := make([]int, 0)
    for i := 1; i < len(heights); i++ {
        need := heights[i] - heights[i-1]
        if need > 0 {
            arr = append(arr, need)
        }
    }
    sort.Ints(arr)
    i := 0
    for ; i < len(arr); i++ {
        if bricks-arr[i] >= 0 {
            bricks = bricks - arr[i]
            continue
        }
        if ladders > 0 {
            ladders--
            continue
        }
        break
    }
    return i == len(arr)
}

1647.字符频次唯一的最小删除次数(1)

  • 题目
如果字符串 s 中 不存在 两个不同字符 频次 相同的情况,就称 s 是 优质字符串 。
给你一个字符串 s,返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。
例如,在字符串 "aab" 中,'a' 的频次是 2,而 'b' 的频次是 1 。
示例 1:输入:s = "aab" 输出:0
解释:s 已经是优质字符串。
示例 2:输入:s = "aaabbbcc" 输出:2
解释:可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ,得到优质字符串 "aaabbc" 。
示例 3:输入:s = "ceabaacb" 输出:2
解释:可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意,只需要关注结果字符串中仍然存在的字符。(即,频次为 0 的字符会忽略不计。)
提示:1 <= s.length <= 10^5  s 仅含小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+贪心 O(n) O(1)
func minDeletions(s string) int {
    m := make(map[int]int)
    for i := 0; i < len(s); i++ {
        m[int(s[i])]++
    }
    arr := make([]int, 0)
    for _, v := range m {
        arr = append(arr, v)
    }
    sort.Ints(arr)
    M := make(map[int]bool)
    res := 0
    for i := len(arr) - 1; i >= 0; i-- {
        if M[arr[i]] == false {
            M[arr[i]] = true
            continue
        }
        j := arr[i]
        for j >= 0 {
            if M[j] == false {
                M[j] = true
                res = res + arr[i] - j
                break
            }
            j--
        }
        if j == -1 {
            res = res + arr[i]
        }
    }
    return res
}

1648.销售价值减少的颜色球(2)

  • 题目
你有一些球的库存inventory,里面包含着不同颜色的球。一个顾客想要任意颜色 总数为orders的球。
这位顾客有一种特殊的方式衡量球的价值:每个球的价值是目前剩下的同色球的数目。
比方说还剩下6个黄球,那么顾客买第一个黄球的时候该黄球的价值为6。
这笔交易以后,只剩下5个黄球了,所以下一个黄球的价值为5(也就是球的价值随着顾客购买同色球是递减的)
给你整数数组inventory,其中inventory[i]表示第i种颜色球一开始的数目。
同时给你整数orders,表示顾客总共想买的球数目。你可以按照 任意顺序卖球。
请你返回卖了 orders个球以后 最大总价值之和。
由于答案可能会很大,请你返回答案对 109+ 7取余数的结果。
示例 1:输入:inventory = [2,5], orders = 4 输出:14
解释:卖 1 个第一种颜色的球(价值为 2 ),卖 3 个第二种颜色的球(价值为 5 + 4 + 3)。
最大总和为 2 + 5 + 4 + 3 = 14 。
示例 2:输入:inventory = [3,5], orders = 6 输出:19
解释:卖 2 个第一种颜色的球(价值为 3 + 2),卖 4 个第二种颜色的球(价值为 5 + 4 + 3 + 2)。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。
示例 3:输入:inventory = [2,8,4,10,6], orders = 20 输出:110
示例 4:输入:inventory = [1000000000], orders = 1000000000 输出:21
解释:卖 1000000000 次第一种颜色的球,总价值为 500000000500000000 。 
500000000500000000 对 109 + 7 取余为 21 。
提示:1 <= inventory.length <= 105
1 <= inventory[i] <= 109
1 <= orders <= min(sum(inventory[i]), 109)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(nlog(n)) O(n)
02 二分查找 O(nlog(n)) O(1)
func maxProfit(inventory []int, orders int) int {
    inventory = append(inventory, 0) // 避免第一个数特判
    sort.Ints(inventory)
    n := len(inventory)
    res := 0
    // 每次把当前数减到前一个数
    for i := n - 1; i >= 1; i-- {
        if orders <= 0 {
            break
        }
        total := (n - i) * (inventory[i] - inventory[i-1])
        if total <= orders { // 够用
            sum := (inventory[i-1] + 1 + inventory[i]) * (inventory[i] - inventory[i-1]) / 2 * (n - i)
            res = (res + sum) % 1000000007
            orders = orders - total
        } else { // 不够用
            a, b := orders/(n-i), orders%(n-i)
            start := inventory[i] - a + 1
            sum := (start+inventory[i])*a/2*(n-i) + b*(start-1)
            res = (res + sum) % 1000000007
            orders = 0
        }
    }
    return res
}

# 2
func maxProfit(inventory []int, orders int) int {
    left, right := 0, math.MaxInt32
    target := 0
    for left <= right {
        target = left + (right-left)/2
        sum := 0
        count := 0
        for i := 0; i < len(inventory); i++ {
            if inventory[i] >= target {
                count++
                sum = sum + (inventory[i] - target)
            }
        }
        if sum > orders { // 过小
            left = target + 1
        } else if sum+count <= orders { // 过小
            right = target - 1
        } else {
            break
        }
    }
    res := 0
    temp := 0
    for i := 0; i < len(inventory); i++ {
        if inventory[i] > target {
            res = (res + getCount(target+1, inventory[i])) % 1000000007
            temp = temp + inventory[i] - target
        }
    }
    return (res + (orders-temp)*target) % 1000000007
}

func getCount(a, b int) int {
    return (a + b) * (b - a + 1) / 2
}

1653.使字符串平衡的最少删除次数(4)

  • 题目
给你一个字符串s,它仅包含字符'a' 和'b'。
你可以删除s中任意数目的字符,使得s 平衡。
我们称s平衡的当不存在下标对(i,j)满足i < j 且s[i] = 'b'同时s[j]= 'a'。
请你返回使 s平衡的 最少删除次数。
示例 1:输入:s = "aababbab" 输出:2
解释:你可以选择以下任意一种方案:
下标从 0 开始,删除第 2 和第 6 个字符("aababbab" -> "aaabbb"),
下标从 0 开始,删除第 3 和第 6 个字符("aababbab" -> "aabbbb")。
示例 2:输入:s = "bbaaaaabb" 输出:2
解释:唯一的最优解是删除最前面两个字符。
提示:1 <= s.length <= 105
s[i]要么是'a' 要么是'b'。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和+后缀和 O(n) O(n)
02 O(n) O(n)
03 遍历 O(n) O(1)
04 动态规划 O(n) O(n)
func minimumDeletions(s string) int {
    n := len(s)
    dpA := make([]int, n)
    dpB := make([]int, n)
    if s[0] == 'a' {
        dpA[0] = 1
    }
    for i := 1; i < n; i++ {
        if s[i] == 'a' {
            dpA[i] = dpA[i-1] + 1
        } else {
            dpA[i] = dpA[i-1]
        }
    }
    if s[n-1] == 'b' {
        dpB[n-1] = 1
    }
    for i := n - 2; i >= 0; i-- {
        if s[i] == 'b' {
            dpB[i] = dpB[i+1] + 1
        } else {
            dpB[i] = dpB[i+1]
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dpA[i]+dpB[i])
    }
    return n - res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func minimumDeletions(s string) int {
    res := 0
    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == 'b' {
            stack = append(stack, 'b')
        } else {
            // 遇到'ba'则删掉,并次数+1
            if len(stack) > 0 {
                res++
                stack = stack[:len(stack)-1]
            }
        }
    }
    return res
}

# 3
func minimumDeletions(s string) int {
    aCount := 0
    for i := 0; i < len(s); i++ {
        if s[i] == 'a' {
            aCount = aCount + 1
        }
    }
    res := aCount
    bCount := 0
    for i := 0; i < len(s); i++ {
        if s[i] == 'a' {
            aCount--
        } else {
            bCount++
        }
        // 要删除:前面b的个数+后面a的个数
        res = min(res, aCount+bCount)
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 4
func minimumDeletions(s string) int {
    n := len(s)
    dp := make([][2]int, n+1)
    // dp[n][0]以a结尾需要删除的次数
    // dp[n][1]以b结尾需要删除的次数
    for i := 0; i < n; i++ {
        if s[i] == 'a' {
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1] + 1
        } else {
            dp[i+1][0] = dp[i][0] + 1
            dp[i+1][1] = min(dp[i][0], dp[i][1])
        }
    }
    return min(dp[n][0], dp[n][1])
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1654.到家的最少跳跃次数(2)

  • 题目
有一只跳蚤的家在数轴上的位置x处。请你帮助它从位置0出发,到达它的家。
跳蚤跳跃的规则如下:
它可以 往前 跳恰好 a个位置(即往右跳)。
它可以 往后跳恰好 b个位置(即往左跳)。
它不能 连续 往后跳 2 次。
它不能跳到任何forbidden数组中的位置。
跳蚤可以往前跳 超过它的家的位置,但是它 不能跳到负整数的位置。
给你一个整数数组forbidden,其中forbidden[i]是跳蚤不能跳到的位置,同时给你整数a,b和x,
请你返回跳蚤到家的最少跳跃次数。
如果没有恰好到达 x的可行方案,请你返回 -1 。
示例 1:输入:forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 输出:3
解释:往前跳 3 次(0 -> 3 -> 6 -> 9),跳蚤就到家了。
示例 2:输入:forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11 输出:-1
示例 3:输入:forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7 输出:2
解释:往前跳一次(0 -> 16),然后往回跳一次(16 -> 7),跳蚤就到家了。
提示:1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden中所有位置互不相同。
位置x不在 forbidden中。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n) O(n)
02 深度优先搜索 O(n) O(n)
func minimumJumps(forbidden []int, a int, b int, x int) int {
    m := make([]bool, 6001)
    for i := 0; i < len(forbidden); i++ {
        m[forbidden[i]] = true
    }
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{0, 0})
    res := -1
    for len(queue) > 0 {
        length := len(queue)
        res++
        for i := 0; i < length; i++ {
            index, dir := queue[i][0], queue[i][1]
            if index == x {
                return res
            }
            if dir == 0 && index-b > 0 && m[index-b] == false { // 向后跳-b
                m[index-b] = true
                queue = append(queue, [2]int{index - b, 1})
            }
            if index+a < len(m) && m[index+a] == false { // 向前跳+a
                m[index+a] = true
                queue = append(queue, [2]int{index + a, 0})
            }
        }
        queue = queue[length:]
    }
    return -1
}

# 2
var m []bool

func minimumJumps(forbidden []int, a int, b int, x int) int {
    m = make([]bool, 6001)
    for i := 0; i < len(forbidden); i++ {
        m[forbidden[i]] = true
    }
    return dfs(0, 0, a, b, x)
}

func dfs(index int, dir int, a int, b int, x int) int {
    if index == x {
        return 0
    }
    res := -1
    if index+a < len(m) && m[index+a] == false { // 向前跳+a
        m[index+a] = true
        res = dfs(index+a, 0, a, b, x)
        if res != -1 {
            return res + 1
        }
    }
    if dir == 0 && index-b > 0 && m[index-b] == false { // 向后跳-b
        res = dfs(index-b, 1, a, b, x)
        if res != -1 {
            return res + 1
        }
    }
    return res
}

1657.确定两个字符串是否接近(1)

  • 题目
如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 :
操作 1:交换任意两个 现有 字符。
例如,abcde -> aecdb
操作 2:将一个 现有 字符的每次出现转换为另一个 现有 字符,并对另一个字符执行相同的操作。
例如,aacabb -> bbcbaa(所有 a 转化为 b ,而所有的 b 转换为 a )
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串,word1 和 word2 。如果 word1 和 word2 接近 ,就返回 true ;否则,返回 false 。
示例 1:输入:word1 = "abc", word2 = "bca" 输出:true
解释:2 次操作从 word1 获得 word2 。
执行操作 1:"abc" -> "acb"
执行操作 1:"acb" -> "bca"
示例 2:输入:word1 = "a", word2 = "aa" 输出:false
解释:不管执行多少次操作,都无法从 word1 得到 word2 ,反之亦然。
示例 3:输入:word1 = "cabbba", word2 = "abbccc" 输出:true
解释:3 次操作从 word1 获得 word2 。
执行操作 1:"cabbba" -> "caabbb"
执行操作 2:"caabbb" -> "baaccc"
执行操作 2:"baaccc" -> "abbccc"
示例 4:输入:word1 = "cabbba", word2 = "aabbss" 输出:false
解释:不管执行多少次操作,都无法从 word1 得到 word2 ,反之亦然。
提示:1 <= word1.length, word2.length <= 105
word1 和 word2 仅包含小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(n) O(1)
func closeStrings(word1 string, word2 string) bool {
    if len(word1) != len(word2) {
        return false
    }
    arr1 := make([]int, 26)
    arr2 := make([]int, 26)
    m1 := make(map[uint8]bool)
    m2 := make(map[uint8]bool)
    for i := 0; i < len(word1); i++ {
        arr1[word1[i]-'a']++
        arr2[word2[i]-'a']++
        m1[word1[i]-'a'] = true
        m2[word2[i]-'a'] = true
    }
    for key := range m1 {
        if m2[key] != true {
            return false
        }
    }
    sort.Ints(arr1)
    sort.Ints(arr2)
    for i := 0; i < 26; i++ {
        if arr1[i] != arr2[i] {
            return false
        }
    }
    return true
}

1658.将x减到0的最小操作数(2)

  • 题目
给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,
然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x恰好 减到0 ,返回 最小操作数 ;否则,返回 -1 。
示例 1:输入:nums = [1,1,4,2,3], x = 5 输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。
示例 2:输入:nums = [5,6,7,8,9], x = 4 输出:-1
示例 3:输入:nums = [3,2,20,1,1,3], x = 10 输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。
提示:1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前后缀和 O(n) O(n)
02 滑动窗口 O(n) O(1)
func minOperations(nums []int, x int) int {
    n := len(nums)
    res := n + 1
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + nums[i]
    }
    if sum < x {
        return -1
    }
    if sum == x {
        return n
    }
    left := make([]int, n)
    right := make([]int, n)
    mLeft := make(map[int]int)
    mRight := make(map[int]int)
    left[0] = nums[0]
    mLeft[nums[0]] = 0
    right[n-1] = nums[n-1]
    mRight[nums[n-1]] = n - 1
    if left[0] == x || right[n-1] == x {
        return 1
    }
    for i := 1; i < n; i++ {
        left[i] = left[i-1] + nums[i]
        mLeft[left[i]] = i
        if left[i] == x {
            res = min(res, i+1)
        }
    }
    for i := n - 2; i >= 0; i-- {
        right[i] = right[i+1] + nums[i]
        mRight[right[i]] = i
        if right[i] == x {
            res = min(res, n-i)
        }
    }
    for i := 1; i < n; i++ {
        left := left[i]
        if index, ok := mRight[x-left]; ok && i < index {
            target := n - (index - i - 1)
            res = min(res, target)
        }
    }
    if res == n+1 {
        return -1
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 2
func minOperations(nums []int, x int) int {
    n := len(nums)
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + nums[i]
    }
    target := sum - x
    left := 0
    right := 0
    res := -1
    cur := 0
    // 和为sum-x的最长连续子数组
    for left < n {
        if right < n {
            cur = cur + nums[right]
            right++
        }
        for cur > target && left < n {
            cur = cur - nums[left]
            left++
        }
        if cur == target {
            res = max(res, right-left)
        }
        if right == n {
            left++
        }
    }
    if res == -1 {
        return -1
    }
    return n - res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1663.具有给定数值的最小字符串(2)

  • 题目
小写字符 的 数值 是它在字母表中的位置(从 1 开始),因此 a 的数值为 1 ,b 的数值为 2 ,
c 的数值为 3 ,以此类推。
字符串由若干小写字符组成,字符串的数值 为各字符的数值之和。
例如,字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意,如果字符串 x 在字典排序中位于 y 之前,就认为 x 字典序比 y 小,有以下两种情况:
x 是 y 的一个前缀;
如果 i 是x[i] != y[i] 的第一个位置,且 x[i]在字母表中的位置比y[i]靠前。
示例 1:输入:n = 3, k = 27 输出:"aay"
解释:字符串的数值为 1 + 1 + 25 = 27,它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2:输入:n = 5, k = 73 输出:"aaszz"
提示:1 <= n <= 105
n <= k <= 26 * n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(n)
02 遍历 O(n) O(n)
func getSmallestString(n int, k int) string {
    res := ""
    k = k - n
    a := k / 25
    b := k % 25
    right := a
    var left, middle int
    if b == 0 {
        left = n - right
        middle = 0
    } else {
        left = n - right - 1
        middle = b
    }
    res = res + strings.Repeat("a", left)
    if middle > 0 {
        res = res + string('a'+middle)
    }
    res = res + strings.Repeat("z", right)
    return res
}

# 2
func getSmallestString(n int, k int) string {
    arr := make([]byte, n)
    k = k - n
    for i := n - 1; i >= 0; i-- {
        if k > 25 {
            arr[i] = 'z'
            k = k - 25
        } else {
            arr[i] = byte('a' + k)
            k = 0
        }
    }
    return string(arr)
}

1664.生成平衡数组的方案数(2)

  • 题目
给你一个整数数组nums。你需要选择 恰好一个下标(下标从 0开始)并删除对应的元素。
请注意剩下元素的下标可能会因为删除操作而发生改变。
比方说,如果nums = [6,1,7,4,1],那么:
选择删除下标 1 ,剩下的数组为nums = [6,7,4,1]。
选择删除下标2,剩下的数组为nums = [6,1,4,1]。
选择删除下标4,剩下的数组为nums = [6,1,7,4]。
如果一个数组满足奇数下标元素的和与偶数下标元素的和相等,该数组就是一个 平衡数组 。
请你返回删除操作后,剩下的数组nums是平衡数组 的方案数。
示例 1:输入:nums = [2,1,6,4] 输出:1
解释:删除下标 0 :[1,6,4] -> 偶数元素下标为:1 + 4 = 5 。奇数元素下标为:6 。不平衡。
删除下标 1 :[2,6,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:6 。平衡。
删除下标 2 :[2,1,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:1 。不平衡。
删除下标 3 :[2,1,6] -> 偶数元素下标为:2 + 6 = 8 。奇数元素下标为:1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。
示例 2:输入:nums = [1,1,1] 输出:3
解释:你可以删除任意元素,剩余数组都是平衡数组。
示例 3:输入:nums = [1,2,3] 输出:0
解释:不管删除哪个元素,剩下数组都不是平衡数组。
提示:1 <= nums.length <= 105
1 <= nums[i] <= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 前缀和 O(n) O(n)
func waysToMakeFair(nums []int) int {
    res := 0
    a := 0
    b := 0
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            a = a + nums[i]
        } else {
            b = b + nums[i]
        }
    }
    x, y := 0, 0
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            a = a - nums[i]
        } else {
            b = b - nums[i]
        }
        even := x + b
        odd := y + a
        if even == odd {
            res++
        }
        if i%2 == 0 {
            x = x + nums[i]
        } else {
            y = y + nums[i]
        }
    }
    return res
}

# 2
func waysToMakeFair(nums []int) int {
    n := len(nums)
    dp := make([]int, n+1)
    for i := 0; i < n; i++ {
        if i%2 == 0 {
            dp[i+1] = dp[i] + nums[i]
        } else {
            dp[i+1] = dp[i] - nums[i]
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        // dp[i]表示索引i左边部分奇偶元素差值,
        // dp[n] - dp[i+1]表示索引i右边部分奇偶元素差值
        if dp[i] == dp[n]-dp[i+1] {
            res++
        }
    }
    return res
}

1669.合并两个链表(2)

  • 题目
给你两个链表list1 和list2,它们包含的元素分别为n 个和m 个。
请你将list1中第a个节点到第b个节点删除,并将list2接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果:
请你返回结果链表的头指针。
示例 1:输入:list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出:[0,1,2,1000000,1000001,1000002,5]
解释:我们删除 list1 中第三和第四个节点,并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2:输入:list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出:[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释:上图中蓝色的边和节点为答案链表。
提示:3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    res := &ListNode{}
    temp := res
    for i := 0; i < a; i++{
        temp.Next = list1
        temp = temp.Next
        list1 = list1.Next
    }
    for list2 != nil{
        temp.Next = list2
        temp = temp.Next
        list2 = list2.Next
    }
    for i := a; i <= b; i++{
        list1 = list1.Next
    }
    for list1 != nil{
        temp.Next = list1
        temp = temp.Next
        list1 = list1.Next
    }
    return  res.Next
}

# 2
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    cur := list1
    for i := 0; i < a-1; i++ {
        cur = cur.Next
    }
    temp := cur.Next
    for i := 0; i < (b - a + 1); i++ {
        temp = temp.Next
    }
    cur.Next = list2
    for cur.Next != nil {
        cur = cur.Next
    }
    cur.Next = temp
    return list1
}

1670.设计前中后队列(1)

  • 题目
请你设计一个队列,支持在前,中,后三个位置的 push和 pop操作。
请你完成FrontMiddleBack类:
FrontMiddleBack()初始化队列。
void pushFront(int val) 将val添加到队列的 最前面。
void pushMiddle(int val) 将val添加到队列的 正中间。
void pushBack(int val)将val添加到队里的 最后面。
int popFront()将 最前面 的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1。
int popMiddle() 将 正中间的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1。
int popBack() 将 最后面 的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1。
请注意当有两个中间位置的时候,选择靠前面的位置进行操作。比方说:
将 6添加到[1, 2, 3, 4, 5]的中间位置,结果数组为[1, 2, 6, 3, 4, 5]。
从[1, 2, 3, 4, 5, 6]的中间位置弹出元素,返回3,数组变为[1, 2, 4, 5, 6]。
示例 1:输入:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", 
"pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出:[null, null, null, null, null, 1, 3, 4, 2, -1]
解释:FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] (队列为空)
提示:1 <= val <= 109
最多调用1000次pushFront,pushMiddle,pushBack,popFront,popMiddle和popBack 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组 O(n^2) O(n)
type FrontMiddleBackQueue struct {
    arr []int
}

func Constructor() FrontMiddleBackQueue {
    return FrontMiddleBackQueue{}
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
    this.arr = append([]int{val}, this.arr...)
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
    mid := len(this.arr) / 2
    this.arr = append(this.arr[:mid], append([]int{val}, this.arr[mid:]...)...)
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
    this.arr = append(this.arr, val)
}

func (this *FrontMiddleBackQueue) PopFront() int {
    var res int
    if len(this.arr) == 0 {
        return -1
    }
    res = this.arr[0]
    this.arr = this.arr[1:]
    return res
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
    var res, mid int
    if len(this.arr) == 0 {
        return -1
    }
    if len(this.arr)%2 == 1 {
        mid = len(this.arr) / 2
    } else {
        mid = len(this.arr)/2 - 1
    }
    res = this.arr[mid]
    this.arr = append(this.arr[:mid], this.arr[mid+1:]...)
    return res
}

func (this *FrontMiddleBackQueue) PopBack() int {
    var res int
    if len(this.arr) == 0 {
        return -1
    }
    res = this.arr[len(this.arr)-1]
    this.arr = this.arr[:len(this.arr)-1]
    return res
}

1673.找出最具竞争力的子序列(1)

  • 题目
给你一个整数数组 nums 和一个正整数 k ,返回长度为 k 且最具 竞争力 的 nums 子序列。
数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。
在子序列a 和子序列b 第一个不相同的位置上,如果a中的数字小于 b 中对应的数字,
那么我们称子序列 a 比子序列 b(相同长度下)更具 竞争力 。 
例如,[1,3,4] 比 [1,3,5] 更具竞争力,在第一个不相同的位置,也就是最后一个位置上,4 小于 5 。
示例 1:输入:nums = [3,5,2,6], k = 2 输出:[2,6]
解释:在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中,
[2,6] 最具竞争力。
示例 2:输入:nums = [2,4,3,3,5,4,9,6], k = 4 输出:[2,3,3,4]
提示:1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单调栈 O(n) O(n)
func mostCompetitive(nums []int, k int) []int {
    stack := make([]int, 0)
    k = len(nums) - k
    for i := 0; i < len(nums); i++ {
        value := nums[i]
        // 栈顶元素打大于后面的元素,摘除栈顶元素(因为前面的更大,需要删除了才能变的最小)
        for len(stack) > 0 && stack[len(stack)-1] > value && k > 0 {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, value)
    }
    stack = stack[:len(stack)-k]
    return stack
}

1674.使数组互补的最少操作次数(1)

  • 题目
给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。
每一次操作,你可以将 nums 中的任何整数替换为1到limit 之间的另一个整数。
如果对于所有下标 i(下标从 0 开始),nums[i] + nums[n - 1 - i]都等于同一个数,
则数组 nums 是 互补的 。
例如,数组 [1,2,3,4] 是互补的,因为对于所有下标i ,nums[i] + nums[n - 1 - i] = 5 。
返回使数组 互补 的 最少操作次数。
示例 1:输入:nums = [1,2,4,3], limit = 4 输出:1
解释:经过 1 次操作,你可以将数组 nums 变成 [1,2,2,3](加粗元素是变更的数字):
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ,nums[i] + nums[n-1-i] = 4 ,所以 nums 是互补的。
示例 2:输入:nums = [1,2,2,1], limit = 2 输出:2
解释:经过 2 次操作,你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ,因为 3 > limit 。
示例 3:输入:nums = [1,2,1,2], limit = 2 输出:0
解释:nums 已经是互补的。
提示:n == nums.length
2 <= n<=105
1 <= nums[i]<= limit <=105
n 是偶数。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 差分数组 O(n) O(n)
func minMoves(nums []int, limit int) int {
    n := len(nums)
    arr := make([]int, 2*limit+2)
    for i := 0; i < n/2; i++ {
        a, b := nums[i], nums[n-1-i]
        // 1、首先[2,2*limit]都加2=>操作2次
        arr[2] = arr[2] + 2
        arr[2*limit+1] = arr[2*limit+1] - 2
        // 2、将[1+min(a,b),limit+max(a,b)] 减1=>操作1次
        arr[1+min(a, b)] = arr[1+min(a, b)] - 1
        arr[limit+max(a, b)+1] = arr[limit+max(a, b)+1] + 1
        // 3、将[a+b]减1,目标值=>操作0次
        arr[a+b] = arr[a+b] - 1
        arr[a+b+1] = arr[a+b+1] + 1
    }
    res := n
    sum := 0
    for i := 2; i <= 2*limit; i++ {
        sum = sum + arr[i]
        if res > sum {
            res = sum
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

1679.K和数对的最大数目(3)

  • 题目
给你一个整数数组 nums 和一个整数 k 。
每一步操作中,你需要从数组中选出和为 k 的两个整数,并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1:输入:nums = [1,2,3,4], k = 5 输出:2
解释:开始时 nums = [1,2,3,4]:
- 移出 1 和 4 ,之后 nums = [2,3]
- 移出 2 和 3 ,之后 nums = []
不再有和为 5 的数对,因此最多执行 2 次操作。
示例 2:输入:nums = [3,1,3,4,3], k = 6 输出:1
解释:开始时 nums = [3,1,3,4,3]:
- 移出前两个 3 ,之后nums = [1,4,3]
不再有和为 6 的数对,因此最多执行 1 次操作。
提示:1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希 O(n) O(n)
02 排序 O(nlog(n)) O(1)
03 哈希 O(n) O(n)
func maxOperations(nums []int, k int) int {
    res := 0
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        if m[k-nums[i]] > 0 {
            res++
            m[k-nums[i]]--
        } else {
            m[nums[i]]++
        }
    }
    return res
}

# 2
func maxOperations(nums []int, k int) int {
    sort.Ints(nums)
    res := 0
    left := 0
    right := len(nums) - 1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == k {
            res++
            left++
            right--
        } else if sum > k {
            right--
        } else {
            left++
        }
    }
    return res
}

# 3
func maxOperations(nums []int, k int) int {
    res := 0
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    for key := range m {
        res = res + min(m[key], m[k-key])
    }
    return res / 2
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1680.连接连续二进制数字(2)

  • 题目
给你一个整数n,请你将1到 n的二进制表示连接起来,
并返回连接结果对应的 十进制数字对 109+ 7取余的结果。
示例 1:输入:n = 1 输出:1
解释:二进制的 "1" 对应着十进制的 1 。
示例 2:输入:n = 3 输出:27
解释:二进制下,1,2 和 3 分别对应 "1" ,"10" 和 "11" 。
将它们依次连接,我们得到 "11011" ,对应着十进制的 27 。
示例 3:输入:n = 12 输出:505379714
解释:连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后,结果为 505379714 。
提示:1 <= n <= 10^5
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
package main

import "math/bits"

func main() {

}

func concatenatedBinary(n int) int {
    res := 0
    for i := 1; i <= n; i++ {
        length := bits.Len(uint(i))
        res = (res<<length + i) % 1000000007
    }
    return res
}

# 2
func concatenatedBinary(n int) int {
    res := 0
    length := 0
    for i := 1; i <= n; i++ {
        if i&(i-1) == 0 {
            length++
        }
        res = (res<<length + i) % 1000000007
    }
    return res
}

1685.有序数组中差绝对值之和(2)

  • 题目
给你一个 非递减有序整数数组nums。
请你建立并返回一个整数数组result,它跟nums长度相同,
且result[i]等于nums[i]与数组中所有其他元素差的绝对值之和。
换句话说,result[i]等于sum(|nums[i]-nums[j]|) ,
其中0 <= j < nums.length 且j != i(下标从 0 开始)。
示例 1:输入:nums = [2,3,5] 输出:[4,3,5]
解释:假设数组下标从 0 开始,那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
示例 2:输入:nums = [1,4,6,8,10] 输出:[24,15,13,15,21]
提示:2 <= nums.length <= 105
1 <= nums[i] <= nums[i + 1] <= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 前缀和 O(n) O(n)
func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    res := make([]int, 0)
    right := 0 // 右边和
    left := 0  // 左边和
    for i := 1; i < n; i++ {
        right = right + (nums[i] - nums[0])
    }
    res = append(res, right)
    for i := 1; i < n; i++ {
        diff := nums[i] - nums[i-1]
        left = left + diff*i
        right = right - diff*(n-i)
        res = append(res, left+right)
    }
    return res
}

# 2
func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    res := make([]int, 0)
    arr := make([]int, 0)
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + nums[i]
        arr = append(arr, sum)
    }
    res = append(res, sum-n*nums[0])
    for i := 1; i < n; i++ {
        left := nums[i]*i - arr[i-1]              // 左边和
        right := (sum - arr[i]) - nums[i]*(n-1-i) // 右边和
        res = append(res, left+right)
    }
    return res
}

1686.石子游戏VI(1)

  • 题目
Alice 和Bob 轮流玩一个游戏,Alice 先手。
一堆石子里总共有n个石子,轮到某个玩家时,他可以移出一个石子并得到这个石子的价值。
Alice 和 Bob 对石子价值有不一样的的评判标准。双方都知道对方的评判标准。
给你两个长度为 n的整数数组aliceValues 和bobValues。
aliceValues[i] 和bobValues[i]分别表示 Alice 和 Bob 认为第i个石子的价值。
所有石子都被取完后,得分较高的人为胜者。
如果两个玩家得分相同,那么为平局。两位玩家都会采用 最优策略进行游戏。
请你推断游戏的结果,用如下的方式表示:
如果 Alice 赢,返回1。
如果 Bob 赢,返回-1。
如果游戏平局,返回0。
示例 1:输入:aliceValues = [1,3], bobValues = [2,1] 输出:1
解释:如果 Alice 拿石子 1 (下标从 0开始),那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ,得到 2 分。
Alice 获胜。
示例 2:输入:aliceValues = [1,2], bobValues = [3,1] 输出:0
解释:Alice 拿石子 0 , Bob 拿石子 1 ,他们得分都为 1 分。
打平。
示例 3:输入:aliceValues = [2,4,3], bobValues = [1,6,7] 输出:-1
解释:不管 Alice 怎么操作,Bob 都可以得到比 Alice 更高的得分。
比方说,Alice 拿石子 1 ,Bob 拿石子 2 , Alice 拿石子 0 ,Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。
提示:n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(nlog(n)) O(n)
func stoneGameVI(aliceValues []int, bobValues []int) int {
    arr := make([][2]int, len(aliceValues))
    for i := 0; i < len(arr); i++ {
        arr[i] = [2]int{i, aliceValues[i] + bobValues[i]}
    }
    // 贪心策略:将两组石头的价值相加,每次取价值最大的那一组
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][1] > arr[j][1]
    })
    a, b := 0, 0
    for i := 0; i < len(arr); i++ {
        if i%2 == 0 {
            a = a + aliceValues[arr[i][0]]
        } else {
            b = b + bobValues[arr[i][0]]
        }
    }
    if a == b {
        return 0
    } else if a > b {
        return 1
    }
    return -1
}

1689.十-二进制数的最少数目(1)

  • 题目
如果一个十进制数字不含任何前导零,且每一位上的数字不是 0 就是 1 ,那么该数字就是一个 十-二进制数 。
例如,101 和 1100 都是 十-二进制数,而 112 和 3001 不是。
给你一个表示十进制整数的字符串 n ,返回和为 n 的 十-二进制数 的最少数目。
示例 1:输入:n = "32" 输出:3
解释:10 + 11 + 11 = 32
示例 2:输入:n = "82734" 输出:8
示例 3:输入:n = "27346209830709182346" 输出:9
提示:1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func minPartitions(n string) int {
    res := 0
    for i := 0; i < len(n); i++ {
        value := int(n[i] - '0')
        if value > res {
            res = value
        }
    }
    return res
}

1690.石子游戏VII(4)

  • 题目
石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,
并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时,得分较高者获胜。
鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。
爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,
如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值 。
示例 1:输入:stones = [5,3,1,4,2] 输出:6
解释:
- 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4] 。
- 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4] 。
- 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4] 。
- 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4] 。
- 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2:输入:stones = [7,90,5,1,100,10,10,2] 输出:122
提示:n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 递归 O(n^2) O(n^2)
03 动态规划 O(n^2) O(n^2)
04 动态规划 O(n^2) O(n)
func stoneGameVII(stones []int) int {
    n := len(stones)
    arr := make([]int, n+1)
    for i := 0; i < n; i++ {
        arr[i+1] = arr[i] + stones[i]
    }
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    for j := 2; j <= n; j++ {
        for i := 0; i+j <= n; i++ {
            left := arr[i+j] - arr[i+1] - dp[i+1][i+j-1] // 左边得分-得分
            right := arr[i+j-1] - arr[i] - dp[i][i+j-2]  // 右边得分-得分
            dp[i][i+j-1] = max(left, right)
        }
    }
    return dp[0][n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
var dp [][]int
var arr []int

func stoneGameVII(stones []int) int {
    n := len(stones)
    arr = make([]int, n+1)
    for i := 0; i < n; i++ {
        arr[i+1] = arr[i] + stones[i]
    }
    dp = make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            dp[i][j] = -1
        }
    }
    dfs(0, n-1)
    return dp[0][n-1]
}

func dfs(i, j int) int {
    if dp[i][j] != -1 {
        return dp[i][j]
    }
    left := arr[j+1] - arr[i+1] - dfs(i+1, j)
    right := arr[j] - arr[i] - dfs(i, j-1)
    dp[i][j] = max(left, right)
    return dp[i][j]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func stoneGameVII(stones []int) int {
    n := len(stones)
    arr := make([]int, n+1)
    for i := 0; i < n; i++ {
        arr[i+1] = arr[i] + stones[i]
    }
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            left := arr[j+1] - arr[i+1] - dp[i+1][j] // 左边得分-得分
            right := arr[j] - arr[i] - dp[i][j-1]    // 右边得分-得分
            dp[i][j] = max(left, right)
        }
    }
    return dp[0][n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 4
func stoneGameVII(stones []int) int {
    n := len(stones)
    arr := make([]int, n+1)
    for i := 0; i < n; i++ {
        arr[i+1] = arr[i] + stones[i]
    }
    dp := make([]int, n)
    for i := n - 2; i >= 0; i-- {
        sum := stones[i]
        for j := i + 1; j < n; j++ {
            sum = sum + stones[j]
            left := sum - stones[i] - dp[j]    // 左边得分-得分
            right := sum - stones[j] - dp[j-1] // 右边得分-得分
            dp[j] = max(left, right)
        }
    }
    return dp[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1695.删除子数组的最大得分(1)

  • 题目
给你一个正整数数组 nums ,请你从中删除一个含有 若干不同元素 的子数组。
删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列,即如果它等于 a[l],a[l+1],...,a[r] ,那么它就是a 的一个子数组。
示例 1:输入:nums = [4,2,4,5,6] 输出:17
解释:最优子数组是 [2,4,5,6]
示例 2:输入:nums = [5,2,1,2,5,2,1,2,5] 输出:8
解释:最优子数组是 [5,2,1] 或 [1,2,5]
提示:1 <= nums.length <= 105
1 <= nums[i] <= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 滑动窗口 O(n) O(n)
func maximumUniqueSubarray(nums []int) int {
    res := 0
    sum := 0
    m := make(map[int]int)
    left := 0
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
        sum = sum + nums[i]
        for m[nums[i]] > 1 {
            m[nums[left]]--
            sum = sum - nums[left]
            left++
        }
        if sum > res {
            res = sum
        }
    }
    return res
}

1696.跳跃游戏VI(4)

  • 题目
给你一个下标从 0 开始的整数数组 nums和一个整数 k。
一开始你在下标0处。每一步,你最多可以往前跳k步,但你不能跳出数组的边界。
也就是说,你可以从下标i跳到[i + 1, min(n - 1, i + k)]包含 两个端点的任意位置。
你的目标是到达数组最后一个位置(下标为 n - 1),你的 得分为经过的所有数字之和。
请你返回你能得到的 最大得分。
示例 1:输入:nums = [1,-1,-2,4,-7,3], k = 2 输出:7
解释:你可以选择子序列 [1,-1,4,3] (上面加粗的数字),和为 7 。
示例 2:输入:nums = [10,-5,-2,4,0,3], k = 3 输出:17
解释:你可以选择子序列 [10,4,3] (上面加粗数字),和为 17 。
示例 3:输入:nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出:0
提示:1 <= nums.length, k <= 105
-104<= nums[i]<= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 动态规划 O(n) O(n)
03 栈辅助 O(n) O(n)
04 O(nlog(n)) O(n)
func maxResult(nums []int, k int) int {
    n := len(nums)
    dp := make([]int, n)
    if k > n {
        k = n
    }
    dp[0] = nums[0]
    maxValue := nums[0]
    for i := 1; i < len(nums); i++ {
        if i <= k { // 在前k个,dp[i] = maxValue + nums[i]
            dp[i] = maxValue + nums[i]
            maxValue = max(maxValue, dp[i])
        } else {
            if maxValue == dp[i-1-k] { // 需要重新找maxValue
                maxValue = getMaxValue(dp[i-k : i])
            }
            dp[i] = maxValue + nums[i]
            maxValue = max(maxValue, dp[i])
        }
    }
    return dp[n-1]
}

func getMaxValue(arr []int) int {
    maxValue := arr[0]
    for i := 0; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
        }
    }
    return maxValue
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maxResult(nums []int, k int) int {
    n := len(nums)
    dp := make([]int, n)
    if k > n {
        k = n
    }
    dp[0] = nums[0]
    maxValue := nums[0]
    maxIndex := 0
    for i := 1; i < len(nums); i++ {
        if i <= k { // 在前k个,dp[i] = maxValue + nums[i]
            dp[i] = maxValue + nums[i]
            if dp[i] >= maxValue {
                maxValue = dp[i]
                maxIndex = i
            }
        } else {
            if i-k > maxIndex {
                maxValue = dp[maxIndex+1]
                for j := maxIndex + 1; j < i; j++ {
                    if dp[j] >= maxValue {
                        maxValue = dp[j]
                        maxIndex = j
                    }
                }
            }
            dp[i] = maxValue + nums[i]
            if dp[i] >= maxValue {
                maxValue = dp[i]
                maxIndex = i
            }
        }
    }
    return dp[n-1]
}

# 3
func maxResult(nums []int, k int) int {
    n := len(nums)
    if k > n {
        k = n
    }
    res := nums[0]
    stack := make([][2]int, 0)
    stack = append(stack, [2]int{0, nums[0]})
    for i := 1; i < len(nums); i++ {
        if stack[0][0] < i-k {
            stack = stack[1:]
        }
        res = stack[0][1] + nums[i]
        for len(stack) > 0 && stack[len(stack)-1][1] < res {
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, [2]int{i, res})
    }
    return res
}

# 4
func maxResult(nums []int, k int) int {
    n := len(nums)
    if k > n {
        k = n
    }
    res := nums[0]
    intHeap := make(IntHeap, 0)
    heap.Init(&intHeap)
    heap.Push(&intHeap, [2]int{0, nums[0]})
    for i := 1; i < len(nums); i++ {
        for i-intHeap[0][0] > k { // 不满足删除
            heap.Pop(&intHeap)
        }
        res = intHeap[0][1] + nums[i]
        heap.Push(&intHeap, [2]int{i, res})
    }
    return res
}

type IntHeap [][2]int

func (h IntHeap) Len() int {
    return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
    return h[i][1] > h[j][1]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.([2]int))
}

func (h *IntHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

1601-1700-Hard

1606.找到处理最多请求的服务器(2)

  • 题目
你有 k个服务器,编号为 0到 k-1,它们可以同时处理多个请求组。
每个服务器有无穷的计算能力但是 不能同时处理超过一个请求。请求分配到服务器的规则如下:
第i(序号从 0 开始)个请求到达。
如果所有服务器都已被占据,那么该请求被舍弃(完全不处理)。
如果第(i % k)个服务器空闲,那么对应服务器会处理该请求。
否则,将请求安排给下一个空闲的服务器(服务器构成一个环,必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器)。
比方说,如果第 i个服务器在忙,那么会查看第 (i+1)个服务器,第 (i+2)个服务器等等。
给你一个 严格递增的正整数数组arrival,表示第i个任务的到达时间,和另一个数组load,
其中load[i]表示第i个请求的工作量(也就是服务器完成它所需要的时间)。
你的任务是找到 最繁忙的服务器。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。
请你返回包含所有最繁忙服务器序号的列表,你可以以任意顺序返回这个列表。
示例 1:输入:k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]  输出:[1] 
解释:所有服务器一开始都是空闲的。
前 3 个请求分别由前 3 台服务器依次处理。
请求 3 进来的时候,服务器 0 被占据,所以它呗安排到下一台空闲的服务器,也就是服务器 1 。
请求 4 进来的时候,由于所有服务器都被占据,该请求被舍弃。
服务器 0 和 2 分别都处理了一个请求,服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。
示例 2:输入:k = 3, arrival = [1,2,3,4], load = [1,2,1,2] 输出:[0]
解释:前 3 个请求分别被前 3 个服务器处理。
请求 3 进来,由于服务器 0 空闲,它被服务器 0 处理。
服务器 0 处理了两个请求,服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。
示例 3:输入:k = 3, arrival = [1,2,3], load = [10,12,11] 输出:[0,1,2]
解释:每个服务器分别处理了一个请求,所以它们都是最忙的服务器。
示例 4:输入:k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2] 输出:[1]
示例 5:输入:k = 1, arrival = [1], load = [1] 输出:[0]
提示:1 <= k <= 105
1 <= arrival.length, load.length <= 105
arrival.length == load.length
1 <= arrival[i], load[i] <= 109
arrival保证 严格递增。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双堆 O(nlog(n)) O(n)
02 堆+二分查找 O(nlog(n)) O(n)
func busiestServers(k int, arrival []int, load []int) []int {
    n := len(arrival)
    res := make([]int, 0)
    freeHeap := &mixHeap{isBig: false} // 小根堆:下标小的优先处理
    busyHeap := &mixHeap{isBig: false} // 小根堆: 空闲时间小,早结束
    for i := 0; i < k; i++ {
        freeHeap.push([]int{i})
    }
    arr := make([]int, k)
    for i := 0; i < n; i++ {
        start := arrival[i]
        // busy堆执行完出队列
        for busyHeap.Len() > 0 && busyHeap.Top()[0] <= start {
            id := busyHeap.pop()[1]
            // i+((id-i)%k+k)%k 表示下一个循环的编号
            freeHeap.push([]int{i + ((id-i)%k+k)%k}) // 入free堆:注意时间处理,负数取模后要取正
        }
        // 选择一个执行,如果为空舍弃:条件2
        if freeHeap.Len() > 0 {
            id := freeHeap.pop()[0] % k
            busyHeap.push([]int{start + load[i], id}) // 结束时间+id
            arr[id]++
        }
    }
    var maxValue int
    for i := 0; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
            res = []int{i}
        } else if arr[i] == maxValue {
            res = append(res, i)
        }
    }
    return res
}

type mixHeap struct {
    arr   [][]int
    isBig bool
}

func (m *mixHeap) Len() int {
    return len(m.arr)
}

func (m *mixHeap) Swap(i, j int) {
    m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}

func (m *mixHeap) Less(i, j int) bool {
    if m.isBig {
        return m.arr[i][0] > m.arr[j][0] // 大根堆
    }
    return m.arr[i][0] < m.arr[j][0] // 小根堆
}

func (m *mixHeap) Push(x interface{}) {
    m.arr = append(m.arr, x.([]int))
}

func (m *mixHeap) Pop() interface{} {
    value := (m.arr)[len(m.arr)-1]
    m.arr = (m.arr)[:len(m.arr)-1]
    return value
}

func (m *mixHeap) push(x []int) {
    heap.Push(m, x)
}

func (m *mixHeap) pop() []int {
    return heap.Pop(m).([]int)
}

func (m *mixHeap) Top() []int {
    if m.Len() > 0 {
        return m.arr[0]
    }
    return nil
}

# 2
func busiestServers(k int, arrival []int, load []int) []int {
    n := len(arrival)
    res := make([]int, 0)
    arr := make([]int, k)
    free := make([]int, k)
    for i := 0; i < k; i++ {
        free[i] = i
    }
    busyHeap := make(IntHeap, 0)
    heap.Init(&busyHeap)
    for i := 0; i < n; i++ {
        start := arrival[i]
        // busy堆执行完出队列
        for busyHeap.Len() > 0 && busyHeap[0][0] <= start {
            // free插入该下标:插入有序数组后有序
            id := busyHeap[0][1]
            index := sort.SearchInts(free, id)
            free = append(free[:index], append([]int{id}, free[index:]...)...)
            heap.Pop(&busyHeap)
        }
        if len(free) == 0 {
            continue
        }
        id := sort.SearchInts(free, i%k)
        if id == len(free) {
            id = 0
        }
        arr[free[id]]++
        heap.Push(&busyHeap, []int{start + load[i], free[id]})
        free = append(free[:id], free[id+1:]...) // 删除该下标
    }
    var maxValue int
    for i := 0; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
            res = []int{i}
        } else if arr[i] == maxValue {
            res = append(res, i)
        }
    }
    return res
}

type IntHeap [][]int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([]int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

1611.使整数变为0的最少操作次数(3)

  • 题目
给你一个整数 n,你需要重复执行多次下述操作将其转换为 0 :
翻转 n 的二进制表示中最右侧位(第 0 位)。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0,则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1:输入:n = 0 输出:0
示例 2:输入:n = 3 输出:2
解释:3 的二进制表示为 "11"
"11" -> "01" ,执行的是第 2 种操作,因为第 0 位为 1 。
"01" -> "00" ,执行的是第 1 种操作。
示例 3:输入:n = 6 输出:4
解释:6 的二进制表示为 "110".
"110" -> "010" ,执行的是第 2 种操作,因为第 1 位为 1 ,第 0 到 0 位为 0 。
"010" -> "011" ,执行的是第 1 种操作。
"011" -> "001" ,执行的是第 2 种操作,因为第 0 位为 1 。
"001" -> "000" ,执行的是第 1 种操作。
示例 4:输入:n = 9 输出:14
示例 5:输入:n = 333 输出:393
提示:0 <= n <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(log(n)) O(1)
02 格雷码 O(log(n)) O(1)
03 遍历 O(log(n)) O(1)
func minimumOneBitOperations(n int) int {
    // 依次将高位的1翻转为0
    // 操作2:00..110000..00 => 00..010000..00
    // 操作2+操作1:00..010000..00 => 00..011000..00
    // 操作2:00..011000..00 => 00..001000..00
    res := 0
    if n == 0 {
        return 0
    }
    for i := 0; (1 << i) <= n; i++ {
        if (1<<i)&n > 0 { // 第i位>0
            total := 1<<(1+i) - 1 // 把(1+i)位数变为100..00的次数
            res = total - res     // 交替加减
        }
    }
    return res
}

# 2
func minimumOneBitOperations(n int) int {
    // 在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同
    // 则称这种编码为格雷码(Gray Code)
    res := 0
    for n > 0 {
        res = res ^ n
        n = n / 2
    }
    return res
}

# 3
func minimumOneBitOperations(n int) int {
    // 依次将高位的1翻转为0
    // 操作2:00..110000..00 => 00..010000..00
    // 操作2+操作1:00..010000..00 => 00..011000..00
    // 操作2:00..011000..00 => 00..001000..00
    res := 0
    if n == 0 {
        return 0
    }
    length := bits.Len(uint(n))
    flag := 1
    for i := 0; (1 << i) <= n; i++ {
        if (1<<(length-1-i))&n > 0 { // 第length-1-i位>0{
            total := 1<<(length-i) - 1
            res = res + total*flag
            flag = -1 * flag
        }
    }
    return res
}

1649.通过指令创建有序数组(2)

  • 题目
给你一个整数数组instructions,你需要根据instructions中的元素创建一个有序数组。
一开始你有一个空的数组nums,你需要从左到右遍历instructions中的元素,将它们依次插入nums数组中。
每一次插入操作的代价是以下两者的 较小值:
nums中 严格小于instructions[i]的数字数目。
nums中 严格大于instructions[i]的数字数目。
比方说,如果要将3 插入到nums = [1,2,3,5],
那么插入操作的代价为min(2, 1) (元素1和2小于3,元素5大于3),插入后nums 变成[1,2,3,3,5]。
请你返回将instructions中所有元素依次插入nums后的 总最小代价。由于答案会很大,请将它对109 + 7取余后返回。
示例 1:输入:instructions = [1,5,6,2] 输出:1
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 5 ,代价为 min(1, 0) = 0 ,现在 nums = [1,5] 。
插入 6 ,代价为 min(2, 0) = 0 ,现在 nums = [1,5,6] 。
插入 2 ,代价为 min(1, 2) = 1 ,现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。
示例 2:输入:instructions = [1,2,3,6,5,4] 输出:3
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 2 ,代价为 min(1, 0) = 0 ,现在 nums = [1,2] 。
插入 3 ,代价为 min(2, 0) = 0 ,现在 nums = [1,2,3] 。
插入 6 ,代价为 min(3, 0) = 0 ,现在 nums = [1,2,3,6] 。
插入 5 ,代价为 min(3, 1) = 1 ,现在 nums = [1,2,3,5,6] 。
插入 4 ,代价为 min(3, 2) = 2 ,现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。
示例 3:输入:instructions = [1,3,3,3,2,4,2,1,2] 输出:4
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3,3] 。
插入 2 ,代价为 min(1, 3) = 1 ,现在 nums = [1,2,3,3,3] 。
插入 4 ,代价为 min(5, 0) = 0 ,现在 nums = [1,2,3,3,3,4] 。
插入 2 ,代价为 min(1, 4) = 1 ,现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ,代价为 min(0, 6) = 0 ,现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ,代价为 min(2, 4) = 2 ,现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。
提示:1 <= instructions.length <= 105
1 <= instructions[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 树状数组 O(nlog(n)) O(n)
02 线段树 O(nlog(n)) O(n)
var mod = 1000000007

func createSortedArray(instructions []int) int {
    res := 0
    c = make([]int, 100002)
    length = 100001
    for i := 0; i < len(instructions); i++ {
        value := instructions[i]
        upData(value, 1) // 次数+1
        left := getSum(value - 1)
        right := getSum(100000) - getSum(value)
        res = (res + min(left, right)) % mod
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

var length int
var c []int // 树状数组

func lowBit(x int) int {
    return x & (-x)
}

// 单点修改
func upData(i, k int) { // 在i位置加上k
    for i <= length {
        c[i] = c[i] + k
        i = i + lowBit(i) // i = i + 2^k
    }
}

// 区间查询
func getSum(i int) int {
    res := 0
    for i > 0 {
        res = res + c[i]
        i = i - lowBit(i)
    }
    return res
}

# 2
var mod = 1000000007

func createSortedArray(instructions []int) int {
    res := 0
    n := 100001
    arr = make([]int, n*4+1)
    for i := 0; i < len(instructions); i++ {
        x := instructions[i]
        left := query(0, 1, n, 1, x-1)  // 查询1~x-1
        right := query(0, 1, n, x+1, n) // 查询 x+1~n
        res = (res + min(left, right)) % mod
        update(0, 1, n, x) // 添加x
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

var arr []int // 线段树

func update(id int, left, right, x int) {
    if left > x || right < x {
        return
    }
    arr[id]++
    if left == right {
        return
    }
    mid := left + (right-left)/2
    update(2*id+1, left, mid, x)    // 左节点
    update(2*id+2, mid+1, right, x) // 右节点
}

func query(id int, left, right, queryLeft, queryRight int) int {
    if left > queryRight || right < queryLeft {
        return 0
    }
    if queryLeft <= left && right <= queryRight {
        return arr[id]
    }
    mid := left + (right-left)/2
    return query(id*2+1, left, mid, queryLeft, queryRight) +
        query(id*2+2, mid+1, right, queryLeft, queryRight)
}

1655.分配重复整数

题目

给你一个长度为n的整数数组nums,这个数组中至多有50个不同的值。
同时你有 m个顾客的订单 quantity,其中,整数quantity[i]是第i位顾客订单的数目。
请你判断是否能将 nums中的整数分配给这些顾客,且满足:
第i位顾客 恰好有quantity[i]个整数。
第i位顾客拿到的整数都是 相同的。
每位顾客都满足上述两个要求。
如果你可以分配 nums中的整数满足上面的要求,那么请返回true,否则返回 false。
示例 1:输入:nums = [1,2,3,4], quantity = [2] 输出:false
解释:第 0 位顾客没办法得到两个相同的整数。
示例 2:输入:nums = [1,2,3,3], quantity = [2] 输出:true
解释:第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3:输入:nums = [1,1,2,2], quantity = [2,2] 输出:true
解释:第 0 位顾客得到 [1,1] ,第 1 位顾客得到 [2,2] 。
示例 4:输入:nums = [1,1,2,3], quantity = [2,2] 输出:false
解释:尽管第 0 位顾客可以得到 [1,1] ,第 1 位顾客没法得到 2 个一样的整数。
示例 5:输入:nums = [1,1,1,1,1], quantity = [2,3] 输出:true
解释:第 0 位顾客得到 [1,1] ,第 1 位顾客得到 [1,1,1] 。
提示:n == nums.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
nums中至多有50个不同的数字。

解题思路

No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)


1665.完成所有任务的最少初始能量(1)

  • 题目
给你一个任务数组tasks ,其中tasks[i] = [actuali, minimumi]:
actuali是完成第 i个任务 需要耗费的实际能量。
minimumi是开始第 i个任务前需要达到的最低能量。
比方说,如果任务为[10, 12]且你当前的能量为11,那么你不能开始这个任务。
如果你当前的能量为13,你可以完成这个任务,且完成它后剩余能量为 3。
你可以按照 任意顺序完成任务。
请你返回完成所有任务的 最少初始能量。
示例 1:输入:tasks = [[1,2],[2,4],[4,8]] 输出:8
解释:一开始有 8 能量,我们按照如下顺序完成任务:
    - 完成第 3 个任务,剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务,剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务,剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余,但是如果一开始只有 7 能量是不能完成所有任务的,因为我们无法开始第 3 个任务。
示例 2:输入:tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]] 输出:32
解释:一开始有 32 能量,我们按照如下顺序完成任务:
    - 完成第 1 个任务,剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务,剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务,剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务,剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务,剩余能量为 9 - 8 = 1 。
示例 3:输入:tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]] 输出:27
解释:一开始有 27 能量,我们按照如下顺序完成任务:
    - 完成第 5 个任务,剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务,剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务,剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务,剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务,剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务,剩余能量为 12 - 6 = 6 。
提示:1 <= tasks.length <= 105
1 <= actuali<= minimumi<= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)
func minimumEffort(tasks [][]int) int {
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i][1]-tasks[i][0] > tasks[j][1]-tasks[j][0]
    })
    total := 0
    res := 0
    for i := 0; i < len(tasks); i++ {
        res = max(res, total+tasks[i][1])
        total = total + tasks[i][0]
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1671.得到山形数组的最少删除次数(1)

  • 题目
我们定义arr是 山形数组当且仅当它满足:
arr.length >= 3
存在某个下标i(从 0 开始)满足0 < i < arr.length - 1且:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给你整数数组nums,请你返回将 nums变成 山形状数组的最少删除次数。
示例 1:输入:nums = [1,3,1] 输出:0
解释:数组本身就是山形数组,所以我们不需要删除任何元素。
示例 2:输入:nums = [2,1,1,5,6,2,3,1]输出:3
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。
示例 3:输入:nums = [4,3,2,1,1,2,3,1]输出:4
提示:输入:nums = [1,2,3,4,4,3,2,1]输出:1
提示:3 <= nums.length <= 1000
1 <= nums[i] <= 109
题目保证nums 删除一些元素后一定能得到山形数组。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
func minimumMountainRemovals(nums []int) int {
    n := len(nums)
    res := 0
    left := make([]int, n)
    right := make([]int, n)
    for i := 0; i < n; i++ {
        left[i] = 0
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                left[i] = max(left[j]+1, left[i])
            }
        }
    }
    for i := n - 1; i >= 0; i-- {
        right[i] = 0
        for j := n - 1; j > i; j-- {
            if nums[j] < nums[i] {
                right[i] = max(right[j]+1, right[i])
            }
        }
    }
    for i := 1; i < n-1; i++ {
        res = max(res, left[i]+right[i]+1)
    }
    return n - res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1675.数组的最小偏移量(1)

  • 题目
给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作:
如果元素是 偶数 ,除以 2
例如,如果数组是 [1,2,3,4] ,那么你可以对最后一个元素执行此操作,使其变成 [1,2,3,2]
如果元素是 奇数 ,乘上 2
例如,如果数组是 [1,2,3,4] ,那么你可以对第一个元素执行此操作,使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1:输入:nums = [1,2,3,4] 输出:1
解释:你可以将数组转换为 [1,2,3,2],然后转换成 [2,2,3,2],偏移量是 3 - 2 = 1
示例 2:输入:nums = [4,1,5,20,3] 输出:3
解释:两次操作后,你可以将数组转换为 [4,2,5,5,3],偏移量是 5 - 2 = 3
示例 3:输入:nums = [2,10,8] 输出:3
提示:n == nums.length
2 <= n <= 105
1 <= nums[i] <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
 func minimumDeviation(nums []int) int {
     intHeap := make(IntHeap, 0)
     heap.Init(&intHeap)
     minValue := math.MaxInt32
     for i := 0; i < len(nums); i++ {
         if nums[i]%2 == 1 { // 奇数x2=>变为偶数放入堆, 统一处理为偶数
             nums[i] = nums[i] * 2
         }
         heap.Push(&intHeap, nums[i])
         minValue = min(minValue, nums[i]) // 记录最小值
     }
     res := intHeap[0] - minValue
     for intHeap.Len() > 0 && intHeap[0]%2 == 0 { //  把最大偶数处理/2
         node := heap.Pop(&intHeap).(int)
         minValue = min(minValue, node/2)
         heap.Push(&intHeap, node/2)
         res = min(res, intHeap[0]-minValue) // 目标结果:将最大值除以2,用最大值减去最小值
     }
     return res
 }

 func min(a, b int) int {
     if a > b {
         return b
     }
     return a
 }

 type IntHeap []int

 func (h IntHeap) Len() int {
     return len(h)
 }

 // 小根堆<,大根堆变换方向>
 func (h IntHeap) Less(i, j int) bool {
     return h[i] > h[j]
 }

 func (h IntHeap) Swap(i, j int) {
     h[i], h[j] = h[j], h[i]
 }

 func (h *IntHeap) Push(x interface{}) {
     *h = append(*h, x.(int))
 }

 func (h *IntHeap) Pop() interface{} {
     value := (*h)[len(*h)-1]
     *h = (*h)[:len(*h)-1]
     return value
 }

1691.堆叠长方体的最大高度(1)

  • 题目
给你 n 个长方体 cuboids ,
其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。
请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ,
你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。
返回 堆叠长方体cuboids 可以得到的 最大高度 。
示例 1:输入:cuboids = [[50,45,20],[95,37,53],[45,23,12]] 输出:190
解释:第 1 个长方体放在底部,53x37 的一面朝下,高度为 95 。
第 0 个长方体放在中间,45x20 的一面朝下,高度为 50 。
第 2 个长方体放在上面,23x12 的一面朝下,高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2:输入:cuboids = [[38,25,45],[76,35,3]] 输出:76
解释:无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它,使 35x3 的一面朝下,其高度为 76 。
示例 3:输入:cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出:102
解释:重新排列长方体后,可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下,这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。
提示:n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+动态规划 O(n^2) O(n)
func maxHeight(cuboids [][]int) int {
    for i := 0; i < len(cuboids); i++ {
        arr := cuboids[i]
        sort.Ints(arr)
        cuboids[i] = arr
    }
    sort.Slice(cuboids, func(i, j int) bool {
        if cuboids[i][0] == cuboids[j][0] {
            if cuboids[i][1] == cuboids[j][1] {
                return cuboids[i][2] < cuboids[j][2]
            }
            return cuboids[i][1] < cuboids[j][1]
        }
        return cuboids[i][0] < cuboids[j][0]
    })
    n := len(cuboids)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = cuboids[i][2]
    }
    res := dp[0]
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if cuboids[i][0] >= cuboids[j][0] &&
                cuboids[i][1] >= cuboids[j][1] &&
                cuboids[i][2] >= cuboids[j][2] {
                dp[i] = max(dp[i], dp[j]+cuboids[i][2])
            }
        }
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
Copyright © Zhi2014 2023 all right reserved,powered by Gitbook该文件修订时间: 2023-10-23 15:20:51

results matching ""

    No results matching ""