算法题

> Last Format Time：7/9/2026 23:46:20

冒泡排序（考过）常见的排序算法：

这涉及到 JavaScript 的一个特性：自动分号插入（ASI, Automatic Semicolon Insertion）。 JavaScript 引擎在某些情况下会自动在行尾插入分号。但在一些特殊场景下，ASI 的行为可能会导致代码被错误地解析。

function bubbleSort(arr) {
    const n = arr.length
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr
}

function selectionSort(arr) {
    const n = arr.length
    for (let i = 0; i < n - 1; i++) {
        let minIdx = i
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j
            }
        }
        ;[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]
    }
    return arr
}

function insertionSort(arr) {
    const n = arr.length
    for (let i = 1; i < n; i++) {
        let key = arr[i]
        let j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}

function mergeSort(arr) {
	// 递归的退出条件
    if (arr.length <= 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = mergeSort(arr.slice(0, mid))
    const right = mergeSort(arr.slice(mid))
    
    // 递归
    return merge(left, right)
}

function merge(left, right) {
    const result = []
    let i = 0,
        j = 0
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++])
        } else {
            result.push(right[j++])
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j))
}

function quickSort(arr) {
    if (arr.length <= 1) return arr
    const pivot = arr[arr.length - 1]
    const left = []
    const right = []
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)]
}

function heapSort(arr) {
    const n = arr.length
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i)
    }
    for (let i = n - 1; i > 0; i--) {
        ;[arr[0], arr[i]] = [arr[i], arr[0]]
        heapify(arr, i, 0)
    }
    return arr
}

function heapify(arr, n, i) {
    let largest = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    if (left < n && arr[left] > arr[largest]) largest = left
    if (right < n && arr[right] > arr[largest]) largest = right
    if (largest !== i) {
        ;[arr[i], arr[largest]] = [arr[largest], arr[i]]
        heapify(arr, n, largest)
    }
}

选择排序　　　　2. 插入排序　　3. 快速排序　　4. 归并排序　　5. 二叉搜索树的插入和查找　　6. 哈希表的实现和应用　　7. 栈和队列的应用　　8. 递归和迭代的理解　　9. 链表的反转　　10. 二叉树的遍历　　11. 图的遍历　　12. 最短路径算法（Dijkstra、Floyd-Warshall 等）　　13. 最大流问题（Ford-Fulkerson 算法等）　　14. 动态规划问题（背包问题、最长公共子序列等）　　15. 字符串匹配算法（KMP、Boyer-Moore 等）　　16. 回溯算法　　17. 分治算法　　18. 堆的应用（优先队列等）　　19. 并查集的应用　　20. 二叉堆的实现　　21. 二叉树的层次遍历（考过树的深度优先遍历）　　22. 二叉树的镜像　　23. 二叉树的前序、中序、后序遍历　　24. 二叉树的最大深

我只能说，面试还是太难了

算法题复习

题一：通过插入 "ab" 构造目标字符串

题目：初始空串，每次可在任意位置插入 "ab"。给定只含 'a' 和 'b' 的目标串 s，判断能否通过若干次操作构造出来。

核心结论：操作每次插入一个 'a' 后紧跟一个 'b'，因此最终串必须满足：

'a' 和 'b' 的总数相等
任意前缀中 'a' 的数量 ≥ 'b' 的数量（否则某个 'b' 没有对应的前驱 'a'）

这两个条件充分必要。

实现：维护 balance（遇 'a' +1，遇 'b' -1），过程中 balance 不得为负且最终为 0。


let balance = 0, ok = true;

for (const ch of s) {

    if (ch === 'a') balance++;

    else balance--;

    if (balance < 0) { ok = false; break; }

}

if (balance !== 0) ok = false;

console.log(ok ? 'YES' : 'NO');

复杂度：O(|s|) 每组

| 示例 | balance 过程 | 结果 |

|------|-------------|------|

| ab | +1→0 | YES |

| abab | +1→0→+1→0 | YES |

| aabb | +1→+2→+1→0 | YES |

| abba | +1→0→-1 ✗ | NO |

题二：交换一次相邻元素后的最大相同连续长度

题目：给定数组，恰好交换一次相邻元素，求交换后相同元素的最大连续长度。

核心结论：一次相邻交换最多将一个元素移动一个位置，因此一个连续段最多扩展 1 个元素。能扩展的充要条件：距离该段边界恰好 2 个位置处有同值元素。

实现：预处理每个位置的 run 边界 left[i] / right[i]，然后枚举每个相邻交换模拟。


// 预处理 run 边界

const left = [], right = [];

for (let i = 0; i < n; i++)

    left[i] = (i > 0 && a[i] === a[i-1]) ? left[i-1] : i;

for (let i = n-1; i >= 0; i--)

    right[i] = (i < n-1 && a[i] === a[i+1]) ? right[i+1] : i;

  

let ans = 原始最大run长度;

  

for (let i = 0; i < n-1; i++) {

    if (a[i] === a[i+1]) continue;

    // a[i+1] 移到位置 i：向左连接

    if (i > 0 && a[i-1] === a[i+1])

        ans = max(ans, i - left[i-1] + 1);

    // a[i] 移到位置 i+1：向右连接

    if (i+2 < n && a[i+2] === a[i])

        ans = max(ans, right[i+2] - (i+1) + 1);

    // 被截断的原有段也需纳入比较

    // ...

}

复杂度：O(n)

关键案例：[1,1,1,2,3,3,3,4,3] → 交换位置 7 和 8（4 和 3）→ [1,1,1,2,3,3,3,3,4] → 最长 4 个 3。

常见错误：误以为一次交换能把所有同值元素聚到一起，把出现次数全加起来（如本例错误输出 6）。

题三：区间倍数更新（根号分治）

题目：长度为 n 的数组初始为 0，q 次操作。每次给定 (l, r, v)，对所有满足 l ≤ j ≤ r 且 j % v == 0 的位置 j（1-indexed）加 1。输出最终数组。

朴素做法：每次遍历 [l, r] 判断整除 → O(n×q)，超时。

优化——根号分治：设阈值 B = √n

| 情况 | 特征 | 策略 |

|------|------|------|

| v ≥ B | 倍数稀疏，最多 n/v ≤ √n 个 | 每个查询直接枚举倍数 |

| v < B | 倍数密集，但 v 种类少（< √n 种） | 按 v 分组，每组建压缩差分数组批量处理 |


const B = Math.ceil(Math.sqrt(n));

const queriesByV = new Map();  // 按 v 分组

  

for (const [v, queries] of queriesByV) {

    if (v >= B) {

        // 直接枚举：每个查询 O(n/v) ≤ O(√n)

        for (const { l, r } of queries) {

            let first = Math.ceil(l / v) * v;

            for (let j = first; j <= r; j += v)

                arr[j - 1]++;

        }

    } else {

        // 压缩差分：倍数 v, 2v, 3v... 压缩为下标 1, 2, 3...

        const maxK = Math.floor(n / v);

        const diff = new Array(maxK + 2).fill(0);

        for (const { l, r } of queries) {

            let firstK = Math.ceil(l / v);

            let lastK = Math.floor(r / v);

            if (firstK <= lastK) {

                diff[firstK]++;

                diff[lastK + 1]--;

            }

        }

        let cur = 0;

        for (let k = 1; k <= maxK; k++) {

            cur += diff[k];

            arr[k * v - 1] += cur;

        }

    }

}

复杂度：O(n log n + q√n)

小 v 部分：所有 v 的差分数组大小之和 n×(1 + 1/2 + … + 1/√n) ≈ n log n
大 v 部分：每次查询 √n，共 q√n

以 n = q = 10^5 为例，操作量从 10^10 降至 ~3×10^7，可稳过。

技巧总结

| 题目 | 核心技巧 |

|------|---------|

| 题一 | 前缀平衡校验（类似括号匹配） |

| 题二 | run 边界预处理 + 枚举交换位置模拟 |

| 题三 | 根号分治（小 v 压缩差分，大 v 直接枚举） |