算法笔试-常用数据结构2

Updated Time	2025-02-26
Category	面试算法
Tags

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

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

题单

栈

题目	来源	难度	分数
1441. 用栈操作构建数组	第 188 场周赛 Q1	中等	1180
844. 比较含退格的字符串	第 87 场周赛 Q1	简单	1228
682. 棒球比赛		简单
2390. 从字符串中移除星号	第 308 场周赛 Q2	中等	1348
946. 验证栈序列	第 112 场周赛 Q2	中等	1462
3412. 计算字符串的镜像分数	第 431 场周赛 Q2	中等	1578
2696. 删除子串后的字符串最小长度	第 346 场周赛 Q1	简单	1282
1047. 删除字符串中的所有相邻重复项	第 137 场周赛 Q2	简单	1286
1544. 整理字符串	第 201 场周赛 Q1	简单	1344
1003. 检查替换后的词是否有效	第 126 场周赛 Q2	中等	1427
2216. 美化数组的最少删除数	第 286 场周赛 Q2	中等	1510
1209. 删除字符串中的所有相邻重复项 II	第 156 场周赛 Q3	中等	1542
2211. 统计道路上的碰撞次数	第 285 场周赛 Q2	中等	1581

单调栈

单调栈要点：及时去除无用元素，保持栈内有序

题目	来源	难度	分数
739. 每日温度		中等
1475. 商品折扣后的最终价格	第 28 场双周赛 Q1	简单	1212
496. 下一个更大元素 I		简单
503. 下一个更大元素 II		中等
1019. 链表中的下一个更大节点	第 130 场周赛 Q3	中等	1571
962. 最大宽度坡	第 116 场周赛 Q2	中等	1608
853. 车队	第 89 场周赛 Q2	中等	1678
901. 股票价格跨度	第 101 场周赛 Q2	中等	1709
1124. 表现良好的最长时间段	第 145 场周赛 Q3	中等	1908

队列

单调队列求解问题：区间最大值，最长连续区间，最短连续区间（子数组）问题

有时候需要用前缀和来转换问题。

题目	来源	难度	分数
950. 按递增顺序显示卡牌	第 113 场周赛 Q3	中等	1686
239. 滑动窗口最大值		困难
1438. 绝对差不超过限制的最长连续子数组	第 187 场周赛 Q3	中等	1672
2762. 不间断子数组	第 352 场周赛 Q3	中等	1940
2398. 预算内的最多机器人数目	第 86 场双周赛 Q4	困难	1917
862. 和至少为 K 的最短子数组	第 91 场周赛 Q4	2307

优先队列：

题目	来源	难度	分数
1046. 最后一块石头的重量	第 137 场周赛 Q1	简单	1173
2558. 从数量最多的堆取走礼物	第 331 场周赛 Q1	简单	1277

字典树

题目	来源	难度	分数
208. 实现 Trie (前缀树)		中等
720. 词典中最长的单词		中等

并查集

题目	来源	难度	分数
990. 等式方程的可满足性	第 123 场周赛 Q2	中等	1638
1202. 交换字符串中的元素	第 155 场 Q3	中等	1855
1061. 按字典序排列最小的等效字符串		中等
1722. 执行交换操作后的最小汉明距离	第 223 场周赛 Q3	中等	1892
765. 情侣牵手	第 67 场周赛 Q4	困难	1999

题解

1441. 用栈操作构建数组

func buildArray(target []int, n int) []string {
    ans := make([]string, 0) 
    for i, j := 1, 0; j < len(target) && i <= n; i++ {
        if i == target[j] {
            ans = append(ans, "Push")
            j++
        } else {
            ans = append(ans, "Push")
            ans = append(ans, "Pop")
        }
    }
    return ans
}

844. 比较含退格的字符串

func backspaceCompare(s string, t string) bool {
    helper := func (a string) string {
        stk := make([]byte, 0)
        for _, v := range []byte(a) {
            if v != '#' {
                stk = append(stk, v)
            } else if len(stk) > 0 {
                stk = stk[:len(stk)-1]
            }
        }
        return string(stk)
    }
    return helper(s) == helper(t)
}

682. 棒球比赛

func calPoints(ops []string) int {
    ans := []int{}
    for _, v := range ops {
        if v == "C" {
            ans = ans[:len(ans)-1]
        } else if v == "D" {
            ans = append(ans, ans[len(ans)-1]*2)
        } else if v == "+" {
            n := len(ans)
            s1, s2 := ans[n-2], ans[n-1]
            ans = append(ans, s1+s2)
        } else {
            s, _ := strconv.Atoi(v)
            ans = append(ans, s)
        }
    }
    sum := 0
    for _, v := range ans {
        sum += v
    }
    return sum
}

2390. 从字符串中移除星号

func removeStars(s string) string {
	stk := []rune{}
	for _, c := range s {
		if c == '*' && len(stk) > 0 {
			stk = stk[:len(stk)-1]
		} else {
			stk = append(stk, c)
		}
	}
	return string(stk)
}

946. 验证栈序列

模拟

func validateStackSequences(pushed []int, popped []int) bool {
    stk := []int{}
    j := 0
    for _, v := range pushed {
        stk = append(stk, v)
        for len(stk) > 0 && popped[j] == stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
            j++
        }
    } 
    return j == len(popped)
}

3412. 计算字符串的镜像分数

用 26 个栈

func calculateScore(s string) (ans int64) {
    stk := [26][]int{}
    for i, v := range s {
        v -= 'a'
        if st := stk[25-v]; len(st) > 0 {
            ans += int64(i - st[len(st) - 1])
            stk[25-v] = st[:len(st)-1]
        } else {
            stk[v] = append(stk[v], i)
        }
    }
    return
}

2696. 删除子串后的字符串最小长度

func minLength(s string) int {
    stk := []byte{}
    for _, v := range []byte(s) {
        if v == 'B' && len(stk) > 0 && stk[len(stk)-1] == 'A' {
            stk = stk[:len(stk)-1]
        } else if v == 'D' && len(stk) > 0 && stk[len(stk)-1] == 'C' {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, v)
        } 
    }
    return len(stk)
}

1047. 删除字符串中的所有相邻重复项

func removeDuplicates(s string) string {
    stk := []byte{}
    for _, v := range []byte(s) {
        if len(stk) > 0 && v == stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, v)
        }
    }
    return string(stk) 
}

1544. 整理字符串

func makeGood(s string) string {
    stk := []byte{}
    for _, v := range []byte(s) {
        if len(stk) > 0 && (v ^ 32) == stk[len(stk) - 1] {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, v)
        }
    }
    return string(stk) 
}

1003. 检查替换后的词是否有效

func isValid(s string) bool {
    stk := []byte{}
    for _, v := range []byte(s) {
        if len(stk) >= 2 && v == 'c' && stk[len(stk)-1] == 'b' && stk[len(stk)-2] == 'a' {
            stk = stk[:len(stk)-2]
        } else {
            stk = append(stk, v)
        }
    }
    return len(stk) == 0 
}

2216. 美化数组的最少删除数

用栈模拟，如果当前栈是偶数，那么可以随意加入，否则栈顶不能相同，最后如果栈为奇数，则移除栈顶。

func minDeletion(nums []int) (ans int) {
    stk := []int{}
    for _, v := range nums {
        if len(stk) % 2 == 1 && len(stk) > 0 && v == stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
            ans++
        }
        stk = append(stk, v)
    }
    if len(stk) % 2 == 1 {
        ans++
    }
    return
}

1209. 删除字符串中的所有相邻重复项 II

栈顶存出现的次数，和出现的那个字符，如果达到 \(k\)，直接移除栈顶。最后只需要根据栈的内容重建字符串。

func removeDuplicates(s string, k int) string {
    type tuple struct {
        cnt int
        val byte
    }
    stk := []tuple{}
    for _, v := range []byte(s) {
        if len(stk) > 0 && v == stk[len(stk)-1].val {
            stk[len(stk)-1].cnt++
        } else {
            stk = append(stk, tuple{1, v})
        }
        if stk[len(stk)-1].cnt >= k {
            stk = stk[:len(stk)-1]
        }
    }
    ans := ""
    for _, v := range stk {
        ans += strings.Repeat(string(v.val), v.cnt)
    }
    return ans
}

2211. 统计道路上的碰撞次数

结论题

func countCollisions(s string) int {
	s = strings.TrimLeft(s, "L")          // 前缀向左的车不会发生碰撞
	s = strings.TrimRight(s, "R")         // 后缀向右的车不会发生碰撞
	return len(s) - strings.Count(s, "S") // 剩下非停止的车必然会碰撞
}

739. 每日温度

func dailyTemperatures(temperatures []int) []int {
    ans := make([]int, len(temperatures))
    stk := []int{}
    for i := len(temperatures) - 1; i >= 0; i-- {
        for len(stk) > 0 && temperatures[i] >= temperatures[stk[len(stk)-1]] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            ans[i] = stk[len(stk)-1] - i
        }
        stk = append(stk, i)
    }
    return ans 
}

1475. 商品折扣后的最终价格

func finalPrices(prices []int) []int {
    ans := make([]int, len(prices))
    stk := []int{}
    for i := len(prices) - 1; i >= 0; i-- {
        for len(stk) > 0 && prices[i] < prices[stk[len(stk)-1]] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            ans[i] = prices[i] - prices[stk[len(stk)-1]]
        } else {
            ans[i] = prices[i]
        }
        stk = append(stk, i)
    }
    return ans
}

496. 下一个更大元素 I

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    ans := make([]int, len(nums1)) 
    cnt := map[int]int{}
    stk := []int{}
    for i := len(nums2) - 1; i >= 0; i-- {
        for len(stk) > 0 && nums2[i] >= nums2[stk[len(stk)-1]] {
            stk = stk[:len(stk) - 1]
        }
        if len(stk) > 0 {
            cnt[nums2[i]] = nums2[stk[len(stk)-1]]
        } else {
            cnt[nums2[i]] = -1
        }
        stk = append(stk, i)
    }
    for i, v := range nums1 {
        ans[i] = cnt[v]
    }
    return ans
}

503. 下一个更大元素 II

注意如何处理循环

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    stk := []int{}
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    for i := 2 * n - 1; i >= 0; i-- {
        x := nums[i%n]
        for len(stk) > 0 && x >= stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
        }
        if i < n && len(stk) > 0 {
            ans[i] = stk[len(stk)-1]
        }
        stk = append(stk, x)
    }
    return ans
}

1019. 链表中的下一个更大节点

注意链表的从后往前遍历

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nextLargerNodes(head *ListNode) (ans []int) {
    stk := []int{}
    var dfs func(*ListNode, int)
    dfs = func(node *ListNode, i int) {
        if node == nil {
            ans = make([]int, i)
            return
        }
        dfs(node.Next, i + 1)
        for len(stk) > 0 && node.Val >= stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            ans[i] = stk[len(stk)-1]
        }
        stk = append(stk, node.Val)
    }
    dfs(head, 0)
    return ans
}

962. 最大宽度坡

单调栈变种，两次遍历，第一次遍历从左到右计算严格递减序列。若不是递减序列，那么即存在一个 \(j\)，能够与 \(k\) 组成最大宽度。那么必然存在 \(i < j\) 且 \(A[i] \le A[j]\)，那么 \(i\) 与 \(k\) 组成的宽度比 \(j\) 更有，因此矛盾。

第二次遍历从右往左，计算最大宽度。

func maxWidthRamp(nums []int) (ans int) {
    stk := []int{0}
    for i, v := range nums {
        if v < nums[stk[len(stk)-1]] {
            stk = append(stk, i)
        }
    }
    for i := len(nums) - 1; i >= 0; i-- {
        for len(stk) > 0 && nums[stk[len(stk)-1]] <= nums[i] {
            ans = max(ans, i - stk[len(stk)-1])
            stk = stk[:len(stk)-1]
        }
    }
    return ans 
}

853. 车队

题目说了前车是无法超过后车的。如果追上之后就会按照车队中速度最慢的那个速度继续前行。所以我们可以求出从每个位置出发，到达终点所需时间是多少的这个数组。

当前车是在前车后面的，后车不能超过我。如果当前车出发到终点的所需时间>=栈顶车队到终点的所需时间（我开的慢，也就是前车都比我快会被我堵住所以就要跟着我走。我前面的车队就会和我形成一个车队，并且以我为准了），此时直接栈顶出栈，说明前面的车队和我要合并了。保证栈内元素是单调增的(从底到顶)。

最后将自己入栈，作为一个车队。

func carFleet(target int, position []int, speed []int) int {
    time := make([]float64, target) // 代表第 i 个位置出发的车到达终点所需的时间
    for i, v := range position {
        time[v] = float64(target - v) / float64(speed[i])
    }
    stk := []float64{}
    for i := 0; i < target; i++ {
        if time[i] > 0 {
            for len(stk) > 0 && time[i] >= stk[len(stk)-1] {
                stk = stk[:len(stk)-1]
            }
            stk = append(stk, time[i])
        }
    }
    return len(stk)
}

func carFleet(target int, position []int, speed []int) int {
    time := make([]float64, target) // 代表第 i 个位置出发的车到达终点所需的时间
    for i, v := range position {
        time[v] = float64(target - v) / float64(speed[i])
    }
    stk := []float64{}
    for i := target - 1; i >= 0; i-- {
        if time[i] > 0 {
            if len(stk) == 0 {
                stk = append(stk, time[i])
            } else if time[i] > stk[len(stk)-1] {
                stk = append(stk, time[i])
            }
        }
    }
    return len(stk)
}

901. 股票价格跨度

type stock struct {
    day int
    val int
}

type StockSpanner struct {
    stk []stock
    today int
}

func Constructor() StockSpanner {
    return StockSpanner{
        stk: []stock{
            {-1, math.MaxInt},
        }, // 不用判断空栈
        today: -1,
    } 
}

func (this *StockSpanner) Next(price int) int {
    for price >= this.stk[len(this.stk)-1].val {
        this.stk = this.stk[:len(this.stk)-1]
    }

    this.today++

    this.stk = append(this.stk, stock{this.today, price})

    return this.today - this.stk[len(this.stk)-2].day
}

1124. 表现良好的最长时间段

首先将问题转换为前缀和，其次用单调栈优化前缀和需要枚举左右端点。

func longestWPI(hours []int) (ans int) {
    n := len(hours)
    s := make([]int, n + 1)
    stk := []int{0}
    for i, h := range hours {
        s[i+1] = s[i]
        if h > 8 {
            s[i+1]++
        } else {
            s[i+1]--
        }
        if s[i+1] < s[stk[len(stk)-1]] {
            stk = append(stk, i+1)
        }
    }

    for i := n; i > 0; i-- {
        for len(stk) > 0 && s[i] > s[stk[len(stk)-1]] {
            ans = max(ans, i - stk[len(stk)-1])
            stk = stk[:len(stk)-1]
        }
    }
    return
}

950. 按递增顺序显示卡牌

想像成一个循环的圆，每次在空位上放置一个数，随后跳过一个空位。

func deckRevealedIncreasing(deck []int) []int {
    slices.Sort(deck)
    q := make([]int, len(deck))
    for i := 0; i < len(deck); i++ {
        q[i] = i
    }
    ans := make([]int, len(deck))
    k := 0
    for len(q) > 0 {
        t := q[0]
        q = q[1:]
        ans[t] = deck[k] 
        k++
        if len(q) > 0 {
            t = q[0]
            q = append(q, t)
            q = q[1:]
        }
    }
    return ans
}

239. 滑动窗口最大值

func maxSlidingWindow(nums []int, k int) []int {
    ans := make([]int, 0) 
    dq := make([]int, 0)
    for i, v := range nums {
        // 1. 入
        for len(dq) > 0 && nums[dq[len(dq)-1]] <= v {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        // 2. 出
        if i - dq[0] + 1 > k {
            dq = dq[1:]
        }
        // 3. 更新答案
        if i >= k - 1 {
            ans = append(ans, nums[dq[0]])
        }
    }
    return ans
}

1438. 绝对差不超过限制的最长连续子数组

分别用两个队列维护最大值和最小值。

func longestSubarray(nums []int, limit int) (ans int) {
    minQ, maxQ := []int{}, []int{}
    left := 0
    for right, v := range nums {
        for len(minQ) > 0 && minQ[len(minQ)-1] > v {
            minQ = minQ[:len(minQ)-1]
        }
        for len(maxQ) > 0 && maxQ[len(maxQ)-1] < v {
            maxQ = maxQ[:len(maxQ)-1]
        }
        minQ = append(minQ, v) 
        maxQ = append(maxQ, v)
        for maxQ[0] - minQ[0] > limit {
            if nums[left] == minQ[0] {
                minQ = minQ[1:]
            }
            if nums[left] == maxQ[0] {
                maxQ = maxQ[1:]
            }
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return
}

2762. 不间断子数组

func continuousSubarrays(nums []int) (ans int64) {
    minQ, maxQ := []int{}, []int{} 
    left := 0
    for right, v := range nums {
        for len(minQ) > 0 && minQ[len(minQ)-1] > v {
            minQ = minQ[:len(minQ)-1]
        }
        for len(maxQ) > 0 && maxQ[len(maxQ)-1] < v {
            maxQ = maxQ[:len(maxQ)-1]
        }
        minQ = append(minQ, v)
        maxQ = append(maxQ, v)
        for maxQ[0] - minQ[0] > 2 {
            if nums[left] == minQ[0] {
                minQ = minQ[1:]
            }
            if nums[left] == maxQ[0] {
                maxQ = maxQ[1:]
            }
            left++
        }
        ans += int64(right - left + 1)
    }
    return
}

862. 和至少为 K 的最短子数组

func shortestSubarray(nums []int, k int) (ans int) {
    n := len(nums)
    s := make([]int, n + 1)
    for i, v := range nums {
        s[i+1] = s[i] + v
    }

    ans = n + 1
    q := []int{}
    for i, v := range s {
        for len(q) > 0 && v - s[q[0]] >= k {
            ans = min(ans, i - q[0])
            q = q[1:]
        }
        for len(q) > 0 && s[q[len(q)-1]] >= v {
            q = q[:len(q)-1]
        }
        q = append(q, i)
    }
    if ans > n {
        return -1
    }
    return
}

2558. 从数量最多的堆取走礼物

func pickGifts(gifts []int, k int) (ans int64) {
    pq := priorityqueue.NewWith(func (a, b interface{}) int {
        return b.(int) - a.(int)
    })    
    for _, g := range gifts {
        pq.Enqueue(g)
    }

    for i := 0; i < k; i++ {
        g, _ := pq.Dequeue()
        g = int(math.Sqrt(float64(g.(int))))
        pq.Enqueue(g)
    }

    for pq.Size() > 0 {
        g, _ := pq.Dequeue()
        ans += int64(g.(int))
    }
    return
}

720. 词典中最长的单词

type Trie struct {
    son [26]*Trie
    isEnd bool
}

func (t *Trie) Insert(word string) {
    cur := t
    for _, c := range word {
        c -= 'a'
        if cur.son[c] == nil {
            cur.son[c] = &Trie{}
        }
        cur = cur.son[c]
    }
    cur.isEnd = true
}

func (t *Trie) Search(word string) bool {
    cur := t
    for _, c := range word {
        c -= 'a'
        if cur.son[c] == nil || !cur.son[c].isEnd {
            return false
        }
        cur = cur.son[c]
    }
    return true
}

func longestWord(words []string) (ans string) {
    t := &Trie{}
    for _, word := range words {
        t.Insert(word)
    }    
    for _, word := range words {
        if t.Search(word) && (len(word) > len(ans) || len(word) == len(ans) && word < ans) {
            ans = word
        }
    }
    return
}

1202. 交换字符串中的元素

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    fa := make([]int, n)
    for i := range fa {
        fa[i] = i
    } 

    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }
    
    for _, p := range pairs {
        a, b := p[0], p[1]
        a, b = find(a), find(b)
        if a != b {
            fa[b] = a
        }
    }

    q := make([][]byte, n)
    for i := range s {
        fi := find(i)
        q[fi] = append(q[fi], s[i])
    }

    for i := range q {
        slices.Sort(q[i])
    }

    ans := ""
    for i := range s {
        fi := find(i)
        ans += string(q[fi][0])
        q[fi] = q[fi][1:]
    } 
    return ans
}

1061. 按字典序排列最小的等效字符串

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    fa := [26]int{}
    for i := range fa {
        fa[i] = i
    } 

    var find func(int) int 
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    for i := range s1 {
        a, b := find(int(s1[i] - 'a')), find(int(s2[i] - 'a'))
        if a < b {
            fa[b] = a
        } else {
            fa[a] = b
        }
    }

    ans := ""
    for i := range baseStr {
        a := find(int(baseStr[i] - 'a'))
        ans += string(a + 'a')
    }
    return ans
}

1722. 执行交换操作后的最小汉明距离

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) (ans int) {
    n := len(source)
    fa := make([]int, n) 
    for i := range fa {
        fa[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    for _, swap := range allowedSwaps {
        a, b := find(swap[0]), find(swap[1])
        fa[b] = a
    }
    
    m := make([]map[int]int, n)
    for i := range m {
        m[i] = make(map[int]int)
    }
    for i, v := range source {
        a := find(i)
        m[a][v]++
    } 

    for i, v := range target {
        a := find(i)
        if m[a][v] > 0 {
            m[a][v]--
        } else {
            ans++
        }
    }
    return
}

765. 情侣牵手

func minSwapsCouples(row []int) int {
    fa := make([]int, len(row) / 2)
    for i := range fa {
        fa[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    cnt := len(row) / 2
    for i := 0; i < len(row); i += 2 {
        a, b := row[i] / 2, row[i+1] / 2
        a, b = find(a), find(b)
        if a != b {
            fa[b] = a
            cnt--
        }
    }
    return len(row) / 2 - cnt
}

1. 题单
2. 题解