算法笔试-常用数据结构

Updated Time	2024-12-03
Category	算法面试
Tags

关于语言：一刷用 Golang，二刷用 Rust

题单来源于：分享丨【题单】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）

题单

枚举右，维护左：对于双变量问题，例如两数之和 \(a_i + a_j = t\)，可以枚举右边的 \(a_j\)，转换成单变量问题，也就是在 \(a_j\) 左边查找是否有 \(a_i = t - a_j\)，可以用哈希表维护。

题目	来源	难度	分数
1. 两数之和		简单
1512. 好数对的数目	第 197 场周赛 Q1	简单	1161
219. 存在重复元素 II		简单
121. 买卖股票的最佳时机		简单
2815. 数组中的最大数对和	第 358 场周赛 Q1	简单	1295
2342. 数位和相等数对的最大和	第 302 场周赛 Q2	中等	1309
1679. K 和数对的最大数目	第 218 场周赛 Q2	中等	1346
2260. 必须拿起的最小连续卡牌数	第 291 场周赛 Q2	中等	1365
1010. 总持续时间可被 60 整除的歌曲	第 128 场周赛 Q2	中等	1377
3185. 构成整天的下标对数目 II	第 402 场周赛 Q2	中等	1385
2748. 美丽下标对的数目	第 351 场周赛 Q1	简单	1301
2874. 有序三元组中的最大值 II	第 365 场周赛 Q2	中等	1583
454. 四数相加 II		中等
1014. 最佳观光组合	第 129 场周赛 Q3	中等	1730
1814. 统计一个数组中好对子的数目	第 49 场双周赛 Q3	中等	1814
2905. 找出满足插值条件的下标 II	第 367 场周赛 Q3	中等	1764

前缀和

题目	来源	难度	分数
303. 区域和检索-数组不可变		简单
2259. 统计范围内的元音字符串数	第 331 场周赛 Q2	中等	1435
3152. 特殊数组	第 398 场周赛 Q2	中等	1523
1749. 任意子数组和的绝对值的最大值	第 45 场双周赛 Q2	中等	1542
2389. 和有限的最长子序列	第 308 场周赛 Q1	简单	1388
3361. 两个字符串的切换距离	第 144 场双周赛 Q2	中等	1553
2055. 蜡烛之间的盘子	第 64 场双周赛 Q3	中等	1819
1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？	第 226 场周赛 Q3	中等	1859
930. 和相同的二元子数组	第 108 场周赛 Q2	中等	1592
560. 和为 K 的子数组		中等
1524. 和为奇数的子数组数目	第 31 场双周赛 Q2	中等	1611
974. 和可被 K 整除的子数组	第 119 场周赛 Q3	中等	1676
523. 连续的子数组和		中等
437. 路径总和 III		中等
2588. 统计美丽子数组数目	第 336 场周赛 Q3	中等	1697
525. 连续数组		中等
3026. 最大好子数组和	第 123 场双周赛 Q3	中等	1817
1477. 找两个和为目标值且不重叠的子数组	第 28 场双周赛 Q3	中等	1851
1546. 和为目标值且不重叠的非空子数组的最大数目	第 201 场周赛 Q3	中等	1855

差分

对于数组 \(a\)，定义其差分数组为

\[\begin{align}d[i] = \left\{\begin{matrix}a[0], & i = 0\\a[i] - a[i-1], & i \ge 1\end{matrix}\right.\end{align}\]

性质1：从左到右累加 \(d\) 中的元素，可以得到数组 \(a\)
性质2：如下两个操作是等价的：
- 把 \(a\) 的子数组 \(a[i], a[i+1], \cdots, a[j]\) 都加上 \(x\)
- 把 \(d[i]\) 增加 \(x\)，把 \(d[j+1]\) 减少 \(x\)

一维差分：

题目	来源	难度	分数
2848. 与车相交的点	第 362 场周赛 Q1	简单	1230
1893. 检查是否区域内所有整数都被覆盖	第 54 场双周赛 Q1	简单	1307
1854. 人口最多的年份	第 240 场周赛 Q1	简单	1370
2960. 统计已测试设备	第 375 场周赛 Q1	简单	1169
1094. 拼车	第 142 场周赛 Q2	中等	1441
1109. 航班预订统计	第 144 场周赛 Q2	中等	1570
3355. 零数组变换 I	第 424 场周赛 Q2	中等	1591
56. 合并区间		中等
57. 插入区间		中等
732. 我的日程安排表 III		困难
2406. 将区间分为最少组数	第 310 场周赛 Q3	中等	1713
2381. 字母移位 II	第 85 场双周赛 Q3	中等	1793

题解

1. 两数之和

func twoSum(nums []int, target int) []int {
    for r, v := range nums {
        for l := 0; l < r; l++ {
            if nums[l] + v == target {
                return []int{l, r}
            }
        }
    }
    return nil
}

1512. 好数对的数目

func numIdenticalPairs(nums []int) (ans int) {
    for r, v := range nums {
        for l := 0; l < r; l++ {
            if nums[l] == v {
                ans++
            }
        }
    } 
    return
}

219. 存在重复元素 II

func containsNearbyDuplicate(nums []int, k int) bool {
    vis := make(map[int]int)
    for r, v := range nums {
        if l, ok := vis[v]; ok && r - l <= k {
            return true
        }
        vis[v] = r
    } 
    return false
}

121. 买卖股票的最佳时机

func maxProfit(prices []int) (ans int) {
    mn := math.MaxInt
    for _, v := range prices {
        ans = max(ans, v - mn)
        mn = min(mn, v)
    }
    return
}

2815. 数组中的最大数对和

func maxSum(nums []int) (ans int) {
    vis := make([]int, 10)
    ans = -1
    for _, v := range nums {
        mx := 0
        for i := v; i > 0; i /= 10 {
            mx = max(mx, i % 10)
        } 
        if a := vis[mx]; a != 0 {
            ans = max(ans, a + v)
        }
        vis[mx] = max(vis[mx], v)
    } 
    return
}

2342. 数位和相等数对的最大和

func maximumSum(nums []int) (ans int) {
    m := make(map[int]int)
    ans = -1
    for _, v := range nums {
        sum := 0
        for i := v; i > 0; i /= 10 {
            sum += i % 10
        }
        
        if a, ok := m[sum]; ok {
            ans = max(ans, a + v)
        }
        m[sum] = max(m[sum], v)
    }
    return
}

1679. K 和数对的最大数目

func maxOperations(nums []int, k int) (ans int) {
    cnt := make(map[int]int)
    for _, v := range nums {
        if cnt[k-v] != 0 {
            cnt[k-v]--
            ans++
        } else {
            cnt[v]++
        }
    }
    return 
}

2260. 必须拿起的最小连续卡牌数

func minimumCardPickup(cards []int) int {
    ans := math.MaxInt
    m := make(map[int]int)
    for r, v := range cards {
        if a, ok := m[v]; ok {
            ans = min(ans, r - a + 1)
        }
        m[v] = r
    }
    if ans == math.MaxInt {
        return -1
    }
    return ans
}

1010. 总持续时间可被 60 整除的歌曲

func numPairsDivisibleBy60(time []int) (ans int) {
    cnt := [60]int{}
    for _, v := range time {
        ans += cnt[(60 - v%60)%60]
        cnt[v%60]++
    }
    return
}

3185. 构成整天的下标对数目 II

func countCompleteDayPairs(hours []int) (ans int64) {
    cnt := [24]int{}
    for _, v := range hours {
        ans += int64(cnt[(24 - v % 24) % 24])
        cnt[v % 24]++
    }
    return
}

2748. 美丽下标对的数目

func countBeautifulPairs(nums []int) int {
    ans := 0
    for i, num := range nums {
        for j := i + 1; j < len(nums); j++ {
            if gcd(num, nums[j]) == 1 {
                ans++
            }
        }
    }
    return ans
}

func gcd(a, b int) int {
    if b > 0 {
        return gcd(b, a % b)
    }
    return a
}

2874. 有序三元组中的最大值 II

枚举 \(j\)，维护 \(0 \sim j-1\) 和 \(j+1 \sim n\) 的最大值。

func maximumTripletValue(nums []int) (ans int64) {
    n := len(nums)
    pre, suf := make([]int, n), make([]int, n)
    pre[0], suf[n-1] = nums[0], nums[n-1]
    for i := 1; i < n; i++ {
        pre[i] = max(pre[i-1], nums[i])
    }
    for i := n - 2; i >= 0; i-- {
        suf[i] = max(suf[i+1], nums[i])
    }
    for i := 1; i < n - 1; i++ {
        ans = max(ans, int64(pre[i] - nums[i]) * int64(suf[i+1]))
    }
    return
}

454. 四数相加 II

将四个数组分为两部分，\(A\) 和 \(B\) 为一组，\(C\) 和 \(D\) 为一组，对于 \(A\) 和 \(B\) 使用二重循环对它进行遍历，得到所有的和存入哈希表中，对于 \(C\) 和 \(D\) 也采用痛仰的方法，查看 \(-C[i]-D[j]\) 有多少存在哈希表中。

func fourSumCount(a []int, b []int, c []int, d []int) (ans int) {
    cnt := make(map[int]int)
    for _, v := range a {
        for _, w := range b {
            cnt[v+w]++
        }
    }
    for _, v := range c {
        for _, w := range d {
            ans += cnt[-v-w]
        }
    }
    return
}

1014. 最佳观光组合

func maxScoreSightseeingPair(values []int) int {
    mx, ans := 0, 0
    for j, v := range values {
        ans = max(ans, mx + v - j)
        mx = max(mx, v + j)
    }
    return ans
}

1814. 统计一个数组中好对子的数目

const MOD int = 1e9 + 7
func countNicePairs(nums []int) (ans int) {
    // nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
    n := len(nums)
    rev_nums := make([]int, n)
    for i, a := range nums {
        t := 0
        for a > 0 {
            t = t * 10 + a % 10
            a /= 10
        }
        rev_nums[i] = t
    }

    cnt := make(map[int]int)
    for i, v := range nums {
        ans = (ans + cnt[v-rev_nums[i]]) % MOD
        cnt[v-rev_nums[i]]++
    }
    return
}

2905. 找出满足插值条件的下标 II

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
    maxIdx, minIdx := 0, 0
    for j := indexDifference; j < len(nums); j++ {
        i := j - indexDifference
        if nums[i] > nums[maxIdx] {
            maxIdx = i
        } else if nums[i] < nums[minIdx] {
            minIdx = i
        }
        if nums[maxIdx] - nums[j] >= valueDifference {
            return []int{maxIdx, j}
        } else if nums[j] - nums[minIdx] >= valueDifference {
            return []int{minIdx, j}
        }
    }
    return []int{-1, -1}
}

303. 区域和检索-数组不可变

type NumArray []int

func Constructor(nums []int) NumArray {
    for i := 1; i < len(nums); i++ {
        nums[i] += nums[i-1]
    }
    return nums
}

func (this NumArray) SumRange(left int, right int) int {
    if left == 0 {
        return this[right]
    }
    return this[right] - this[left - 1]
}

2259. 统计范围内的元音字符串数

func vowelStrings(words []string, queries [][]int) []int {
    cnt := make([]int, len(words) + 1)
    check := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }
    for i, word := range words {
        if check(word[0]) && check(word[len(word)-1]) {
            cnt[i+1] = 1
        }
    }
    for i := 1; i < len(cnt); i++ {
        cnt[i] += cnt[i-1]
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = cnt[q[1]+1] - cnt[q[0]]
    }
    return ans
}

3152. 特殊数组

考虑这样一个问题：给定一个只包含 \(0\) 和 \(1\) 的数组，如何快速判断一个子数组是否全为 \(0\)?

如果子数组的元素和等于 \(0\)，那么子数组一定全为 \(0\)；如果子数组的元素和大于 \(0\)，那么子数组一定包含 \(1\)。快速计算子数组元素和可以使用前缀和。

func isArraySpecial(nums []int, queries [][]int) []bool {
    n := len(nums)
    a := make([]int, n)
    a[0] = 0
    for i := 1; i < n; i++ {
        if nums[i] % 2 == nums[i-1] % 2 {
            a[i] = 1
        } else {
            a[i] = 0
        }
        a[i] += a[i-1]
    }
    ans := make([]bool, len(queries))
    for i, q := range queries {
        ans[i] = a[q[0]] == a[q[1]]
    }
    return ans
}

1749. 任意子数组和的绝对值的最大值

func maxAbsoluteSum(nums []int) int {
    s, mn, mx := 0, 0, 0
    for _, v := range nums {
        s += v
        if s > mx {
            mx = s
        } else if s < mn {
            mn = s
        }
    }
    return mx - mn
}

2389. 和有限的最长子序列

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    n, m := len(nums), len(queries)
    for i := 1; i < n; i++ {
        nums[i] += nums[i-1]
    } 
    ans := make([]int, m)
    for k, q := range queries {
        l, r := 0, n
        for l < r {
            mid := (l + r) >> 1
            if nums[mid] < q + 1 {
                l = mid + 1
            } else {
                r = mid
            }
        }
        ans[k] = l
    }
    return ans
}

3361. 两个字符串的切换距离

由于字母表是环形的，可以把前缀延长一倍。

func shiftDistance(s string, t string, nextCost []int, previousCost []int) int64 {
    n := len(nextCost)
    next := make([]int64, 2 * 26 + 1)
    prev := make([]int64, 2 * 26 + 1)

    for i := 0; i < 2 * n; i++ {
        next[i+1] = next[i] + int64(nextCost[i%26])
        prev[i+1] = prev[i] + int64(previousCost[i%26])
    }

    ans := int64(0)
    for i := 0; i < len(s); i++ {
        a := s[i] - 'a'
        b := t[i] - 'a'
        if b < a {
            b += 26
        }
        res1 := next[b] - next[a]
        b = t[i] - 'a'
        if a < b {
            a += 26
        }
        res2 := prev[a+1] - prev[b+1]
        ans += min(res1, res2)
    }
    return ans
}

2055. 蜡烛之间的盘子

对于每一个询问，只需要找到给定区间最左侧和最右侧的两根蜡烛，这样两根蜡烛之间的所有盘子都是符合条件的。

func platesBetweenCandles(s string, queries [][]int) []int {
    n := len(s)
    pre := make([]int, n)
    left, right := make([]int, n), make([]int, n)
    l, r, sum := 0, n - 1, 0
    for i := 0; i < n; i++ {
        if s[i] == '*' {
            sum += 1
        } else {
            l = i
        }
        pre[i] = sum
        left[i] = l
    }
    for i := n - 1; i >= 0; i-- {
        if s[i] == '|' {
            r = i
        }
        right[i] = r
    }
    
    ans := make([]int, len(queries))
    for i, q := range queries {
        x, y := right[q[0]], left[q[1]]
        if x >= 0 && y >= 0 && x < y {
            ans[i] = pre[y] - pre[x]
        }
    }
    return ans
}

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

对于第 \(i\) 个询问 \((t, d, c)\)，每天至少吃 \(1\) 颗糖果，之多吃 \(d\) 天，因此吃的糖果数量落在区间：

\[\left[d + 1, (d + 1) \times c \right]\]

那么只要这个区间包含了一颗 \(t\) 糖果，就可以满足要求了。那么第 \(t\) 颗糖果对应的范围为：

\[\left[sum[t - 1] + 1, sum[t] \right]\]

只需要判断这两个区间是否有交集即可。

func canEat(candiesCount []int, queries [][]int) []bool {
    ans := make([]bool, len(queries))
    // pre[i] 表示需要吃到第 i 种糖之前
    // 需要先吃 pre[i] 颗糖
    pre := make([]int, len(candiesCount) + 1)
    for i := 1; i <= len(candiesCount); i++ {
        pre[i] = pre[i-1] + candiesCount[i-1]
    }

    for i, q := range queries {
        t, d, c := q[0], q[1], q[2]
        // 至少要在最后一天吃到第 t 种糖
        // 在 d 天能够吃完 pre[t] 的所有糖
        x1, y1 := d + 1, (d + 1) * c
        x2, y2 := pre[t] + 1, pre[t+1]
        ans[i] = !(x1 > y2 || y1 < x2)
    }
    return ans 
}

930. 和相同的二元子数组

func numSubarraysWithSum(nums []int, goal int) int {
    ans, sum := 0, 0
    cnt := make(map[int]int)
    cnt[0] = 1
    for _, v := range nums {
        sum += v
        if sum >= goal {
            ans += cnt[(sum - goal)]
        }
        cnt[sum]++
    }
    return ans
}

560. 和为 K 的子数组

func subarraySum(nums []int, k int) int {
    sum, ans := 0, 0
    cnt := make(map[int]int)
    cnt[0] = 1
    for _, v := range nums {
        sum += v
        ans += cnt[sum-k]
        cnt[sum]++
    }            
    return ans
}

1524. 和为奇数的子数组数目

func numOfSubarrays(arr []int) int {
    const MOD =  1e9 + 7
    sum, ans := 0, 0
    zero, one := 1, 0
    for _, v := range arr {
        sum += v
        if sum % 2 == 0 {
            ans = (ans + one) % MOD
            zero++
        } else {
            ans = (ans + zero) % MOD
            one++
        }
    }
    return ans
}

974. 和可被 K 整除的子数组

func subarraysDivByK(nums []int, k int) int {
    cnt := make(map[int]int) 
    cnt[0] = 1
    sum, ans := 0, 0
    for _, v := range nums {
        sum = ((sum + v) % k + k) % k
        ans += (cnt[sum])
        cnt[sum]++
    }
    return ans
}

523. 连续的子数组和

func checkSubarraySum(nums []int, k int) bool {
    cnt := make(map[int]int)
    sum := 0
    cnt[0] = -1
    for i, v := range nums {
        sum = (sum + v) % k
        if j, ok := cnt[sum]; ok {
            if i - j >= 2 {
                return true
            }
        } else {
            cnt[sum] = i
        }
    }
    return false
}

437. 路径总和 III

在二叉树上，前缀和相当于从根节点开始的路径元素和。用哈希表统计前缀和的出现次数。递归到节点 \(node\) 时，设从根到 \(node\) 的路径元素和为 \(s\)，那么就找到了 \(cnt[s-targetSum]\) 个符合要求的路径，加入答案。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
    cnt := make(map[int]int)
    cnt[0] = 1
    ans := 0
    var dfs func (*TreeNode, int)
    dfs = func (r *TreeNode, cur int) {
        if r == nil {
            return
        }
        cur += r.Val
        ans += cnt[cur - targetSum]

        cnt[cur]++
        dfs(r.Left, cur)
        dfs(r.Right, cur)
        cnt[cur]--
    }
    dfs(root, 0) 
    return ans
}

2588. 统计美丽子数组数目

对于数组 \(nums\)，定义它的前缀异或和 \(s[0] = 0\)，\(s[i+1] = \bigoplus^i_{j=0} nums[j]\)。

根据这个定义，有 \(s[i+1] = s[i] \bigoplus nums[i]\)

例如 \(nums=[4, 3, 1, 2, 4]\)，对应的前缀异或和数组为 \(s = [0, 4, 7, 6, 5]\)

通过前缀异或和，可以把子数组的异或和转换成两个前缀异或和的异或，即

\[\bigoplus^{right}_{j=left} nums[j] = \bigoplus_{j=0}^{right} \oplus \bigoplus^{left-1}_{j=0} nums[j] = s[right + 1] \oplus s[left]\]

把所有比特位合起来看，美丽子数组等价于子数组异或和等于 \(0\)。

func beautifulSubarrays(nums []int) int64 {
    ans := int64(0)
    s := 0
    cnt := map[int]int{}
    cnt[0] = 1
    for _, x := range nums {
        s ^= x
        ans += int64(cnt[s])
        cnt[s]++
    }
    return ans
}

525. 连续数组

func findMaxLength(nums []int) int {
    ans := 0
    cnt := make(map[int]int)
    cnt[0] = -1
    s := 0
    for i, x := range nums {
        if x == 0 {
            x = -1
        }
        s += x
        if j, ok := cnt[s]; ok {
            ans = max(ans, i - j)
        } else {
            cnt[s] = i
        }
    }
    return ans
}

3026. 最大好子数组和

子数组 \(a[i\dots] j\) 的元素和为

\[s[j+1] - s[i]\]

枚举 \(j\)，需要找到最小的 \(s[i]\)，满足 \(|a[i] - a[j]| = k\)，即 \(a[i] = a[j] - k\) 或 \(a[i] = a[j] + k\)

定义哈希表 \(sum\)，键为 \(a[i]\)，值为相同 \(a[i]\) 下 \(s[i]\) 的最小值。

子数组最后一个数为 \(a[j]\) 时，子数组的最大元素和为

\[\begin{align} & s[j+1] - sum[a[i]] \\ = &s[j+1] - \min \left( sum[a[j]-k], sum[a[j]+k] \right) \end{align}\]

func maximumSubarraySum(nums []int, k int) int64 {
    var ans int = math.MinInt
    sum := map[int]int{}
    x := 0
    for _, v := range nums {
        s, ok := sum[v+k]
        if ok {
            ans = max(ans, x + v - s)
        }
        s, ok = sum[v-k]
        if ok {
            ans = max(ans, x + v - s)
        }

        s, ok = sum[v]
        if !ok || x < s {
            sum[v] = x 
        }

        x += v
    }
    if ans == math.MinInt {
        return 0
    }
    return int64(ans)
}

1477. 找两个和为目标值且不重叠的子数组

func minSumOfLengths(arr []int, target int) int {
    ans, sum := math.MaxInt, 0
    cnt := map[int]int{0: 0}
    left := make([]int, len(arr) + 1)
    left[0] = math.MaxInt
    for i, v := range arr {
        sum += v
        left[i+1] = left[i]
        if j, ok := cnt[sum-target]; ok {
            // left [i] 表示从 0...i 其中子数组和为 target 的最小长度
            if j > 0 && left[j] != math.MaxInt {
                ans = min(ans, left[j] + i - j + 1)
            } 

            // 找到了一个和为 target 的子数组
            left[i+1] = min(left[i+1], i - j + 1)
        }
        cnt[sum] = i + 1
    }
    if ans == math.MaxInt {
        return -1
    }
    return ans 
}

1546. 和为目标值且不重叠的非空子数组的最大数目

\(f(i)\) 表示从 0...i 中子数组和为 \(target\) 的个数。

func maxNonOverlapping(nums []int, target int) int {
    sum := 0
    cnt := map[int]int{0: 0}
    f := make([]int, len(nums) + 1)
    f[0] = 0
    for i, v := range nums {
        sum += v
        f[i+1] = f[i]
        if j, ok := cnt[sum-target]; ok {
            f[i+1] = max(f[i+1], f[j] + 1)
        }
        cnt[sum] = i + 1
    }
    return f[len(nums)]
}

2848. 与车相交的点

func numberOfPoints(nums [][]int) int {
    diff := make([]int, 102)
    for _, num := range nums {
        s, e := num[0], num[1]
        diff[s]++
        diff[e+1]--
    }

    ans := 0
    for i := 1; i <= 101; i++ {
        diff[i] += diff[i-1]
        if diff[i] > 0 {
            ans++
        }
    }
    return ans
}

1893. 检查是否区域内所有整数都被覆盖

func isCovered(ranges [][]int, left int, right int) bool {
    diff := make([]int, 52)
    for _, r := range ranges {
        s, e := r[0], r[1]
        diff[s]++
        diff[e+1]--
    }
    for i := 1; i < 52; i++ {
        diff[i] += diff[i-1]
    }
    for i := left; i <= right; i++ {
        if diff[i] == 0 {
            return false
        }
    }
    return true
}

1854. 人口最多的年份

func maximumPopulation(logs [][]int) int {
    diff := make([]int, 2050 - 1950 + 2)
    for _, log := range logs {
        s, e := log[0], log[1]
        diff[s-1950]++
        diff[e-1950]--
    }
    for i := 1; i < len(diff); i++ {
        diff[i] += diff[i-1]
    }
    idx, ans := 0, 0
    for i := 0; i < len(diff); i++ {
        if diff[i] > ans {
            ans = diff[i]
            idx = i + 1950
        }
    }
    return idx
}

2960. 统计已测试设备

func countTestedDevices(batteryPercentages []int) int {
    diff := 0
    for _, v := range batteryPercentages {
        v -= diff
        if v > 0 {
            diff++
        }
    }
    return diff
}

1094. 拼车

func carPooling(trips [][]int, capacity int) bool {
    diff := make([]int, 1010)
    for _, trip := range trips {
        n, f, t := trip[0], trip[1], trip[2]
        diff[f] += n
        diff[t] -= n
    }
    for i := 1; i < len(diff); i++ {
        diff[i] += diff[i-1]
    }
    for _, v := range diff {
        if v > capacity {
            return false
        }   
    }
    return true
}

1109. 航班预订统计

func corpFlightBookings(bookings [][]int, n int) []int {
    diff := make([]int, n + 1)
    for _, booking := range bookings {
        f, l, s := booking[0], booking[1], booking[2]
        diff[f-1] += s
        diff[l] -= s
    }
    for i := 1; i < n; i++ {
        diff[i] += diff[i-1]
    }
    return diff[:n]
}

3355. 零数组变换 I

题意可以转换成：把 \([l_i, r_i]\) 中的元素都减 \(1\)，最终数组中的所有元素是否都 \(\le 0\)。

func isZeroArray(nums []int, queries [][]int) bool {
    // diff[i] 表示 下标为 i 的元素需要减去多少
    diff := make([]int, len(nums) + 1) 
    for _, query := range queries {
        s, e := query[0], query[1]
        diff[s]++
        diff[e+1]--
    }
    s := 0
    for i, x := range nums {
        s += diff[i]
        if x - s > 0 {
            return false
        }
    }
    return true
}

56. 合并区间

func merge(intervals [][]int) [][]int {
    slices.SortFunc(intervals, func(p, q []int) int {
        return p[0] - q[0]
    })
    ans := make([][]int, 0)
    for _, p := range intervals {
        m := len(ans)
        if m > 0 && p[0] <= ans[m-1][1] {
            // 合并
            ans[m-1][1] = max(ans[m-1][1], p[1])
        } else {
            // 无法合并
            ans = append(ans, p)
        }
    }
    return ans
}

57. 插入区间

func insert(intervals [][]int, newInterval []int) [][]int {
    ans := make([][]int, 0)
    l, r := newInterval[0], newInterval[1]
    merged := false
    for _, interval := range intervals {
        if interval[0] > r {
            // 在插入区间的右侧且无交集
            if !merged {
                ans = append(ans, []int{l, r})
                merged = true
            }
            ans = append(ans, interval)
        } else if interval[1] < l {
            // 在插入区间的左侧且无交集
            ans = append(ans, interval)
        } else {
            // 与插入区间有交集
            l = min(l, interval[0])
            r = max(r, interval[1])
        }
    }
    if !merged {
        ans = append(ans, []int{l, r})
    }
    return ans
}

732. 我的日程安排表 III

type MyCalendarThree struct {
    *redblacktree.Tree
}


func Constructor() MyCalendarThree {
    return MyCalendarThree{redblacktree.NewWithIntComparator()}
}

func (t *MyCalendarThree) add(x, delta int) {
    if val, ok := t.Get(x); ok {
        delta += val.(int)
    }
    t.Put(x, delta)
}

func (t *MyCalendarThree) Book(start int, end int) (ans int) {
    t.add(start, 1)
    t.add(end, -1) 

    maxBook := 0
    for it := t.Iterator(); it.Next(); {
        maxBook += it.Value().(int)
        if maxBook > ans {
            ans = maxBook
        }
    }
    return
}


/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(startTime,endTime);
 */

2406. 将区间分为最少组数

解法一：按照 \(left\) 排序后，用最小堆模拟，堆顶存储每个组最后一个区间的 \(right\)。

解法二：转换成上下车模型，每个区间看成一个人，在 \(left\) 时刻上车，\(right + 1\) 时刻下车，最后答案为同时在车上的人数的最大值。

func minGroups(intervals [][]int) int {
    h := hp{}
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    for _, p := range intervals {
        if h.Len() == 0 || p[0] <= h.IntSlice[0] {
            heap.Push(&h, p[1])
        } else {
            h.IntSlice[0] = p[1]
            heap.Fix(&h, 0)
        }
    }
    return h.Len()
}

type hp struct { sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int))}
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v}

func minGroups(intervals [][]int) int {
    diff := redblacktree.NewWithIntComparator()
    for _, interval := range intervals {
        a, b := interval[0], interval[1]
        add(diff, a, 1)
        add(diff, b + 1, -1) 
    }
    ans, sum := 0, 0
    for it := diff.Iterator(); it.Next(); {
        sum += it.Value().(int)
        ans = max(ans, sum)
    }
    return ans
}

func add(t *redblacktree.Tree, x, delta int) {
    if val, ok := t.Get(x); ok {
        delta += val.(int)
    }
    t.Put(x, delta)
}

2381. 字母移位 II

func shiftingLetters(str string, shifts [][]int) string {
    diff := make([]int, len(str) + 1) 
    for _, shift := range shifts {
        s, e, d := shift[0], shift[1], shift[2]
        if d == 1 {
            diff[s]++
            diff[e+1]--
        } else {
            diff[s]--
            diff[e+1]++
        }
    }
    s, ans := 0, []byte(str)
    for i, v := range ans {
        s = (s + diff[i]) % 26 + 26
        ans[i] = (v - 'a' + byte(s)) % 26 + 'a'
    }
    return string(ans)
}

1. 题单
1. 1.1. 前缀和
2. 1.2. 差分
2. 题解