算法笔记合集：排序、二分、DP 与图论

排序

手写快速排序（LeetCode 912. 排序数组）

base 初始化时需要先暂存，如果是放在 left 侧，则需要在结束时利用 right 指针做一次 swap

// 初始化时放在左侧
swap(nums, i, base);

while()...

// 结束时，利用 right 指针元素肯定 <= base，把原来的位置换出来
swap(nums, j, left);

一次调用结束，base 左侧都是 < 它的元素，右侧都是 > 它的元素，所以该元素在整个数组中严格有序时的位置就能推出来了

边界问题

while(i <= j) {
    while(i <= j && nums[i] < x) i++;
    while(i <= j && nums[j] > x) j--;
    // 这里一定是 <=，如果是 < 有可能进入死循环
    if(i <= j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}
// Hoare 风双指针分区的循环条件：外层、内层都写 i <= j，退出时保证 i > j（指针已经交叉）。分类完成、pivot 才能正确归位。

二分查找

搜索旋转排序数组（LeetCode 33）

对比红蓝区间染色，这里的定义是：

红色（right 控制）：下标 i 满足「nums[i] 应当排在 target 及其右侧」。换句话说，从 target 应当出现的下标开始，一直到 n-1，全部是红色。
蓝色（left 控制）：下标 i 满足「nums[i] 应当排在 target 的左边」。也就是 0 .. (target 应当出现的下标 - 1)，全部是蓝色。

不用内置函数求算术平方根

题目描述： 给你一个非负数 x，计算并返回其算术平方根，结果要求保留一位小数（向下截断）。注意： 不允许使用任何内置开方函数（如 math.sqrt()、pow(x, 0.5) 等）。

示例 1：输入 x = 4，输出 2.0
示例 2：输入 x = 8，输出 2.8

x = 8
x = x*100
left = -1
right = x
while left < right-1:
    mid = right - (right-left) // 2
    if mid*mid <= x:
        left = mid
    else:
        right = mid
print(left/10.0)

动态规划

最长回文子串（LeetCode 5）

动态规划版本的推导式：

1 2	s.charAt(i) == s.charAt(j) && (j - i <= 2 \|\| dp[i+1][j-1]) // j - i <= 2 是指：只要满足左右边界字符相等，形如 [a]、[aa]、[aba] 这样的子串都可以直接被归为 true

笔记翻倍后的最大子段和

题目描述： 博主小红发布了一组共 n 篇笔记，每篇笔记有一个初始热度值 a_i（正数表示受欢迎，负数表示反响不佳）。

运营团队允许小红执行一次推流加倍操作：选择一个连续笔记区间 [l, r]（1 ≤ l ≤ r ≤ n），将该区间内所有笔记的热度值变为原来的两倍。当然，他也可以选择不执行此操作。

操作结束后（或不操作），小红想知道连续笔记的最大热度总和是多少。注意：所选子段不能为空，至少包含一篇笔记。

状态	含义	第 i 个数的贡献
`dp[i][0]`	子段还在翻倍区间前面（没翻倍）	`a[i]`
`dp[i][1]`	子段正在翻倍区间里	`2*a[i]`
`dp[i][2]`	子段已经越过翻倍区间（翻倍结束）	`a[i]`

dp[i][0] = max(dp[i-1][0] + x, x)
dp[i][1] = max(
    2*x,                 // 子段从 i 开始，翻倍区间也从 i 开始
    dp[i-1][0] + 2*x,    // 普通段后面接上 i，从 i 开始进入翻倍
    dp[i-1][1] + 2*x     // 本来就在翻倍区间里，继续往后扩
)
dp[i][2] = max(
    dp[i-1][1] + x,    // i-1 还在翻倍，到 i 结束翻倍
    dp[i-1][2] + x     // 早已结束翻倍，继续接普通后缀
)

from math import inf
a = list(map(int, input().split()))
n = len(a)
dp = [[0] * (3) for _ in range(n+1)]
print(dp)
dp[0][0] = -inf
dp[0][1] = -inf
dp[0][2] = -inf
ans = 0
for i in range(n):
    x = a[i-1]
    dp[i+1][0] = max(x, dp[i][0]+x)
    dp[i+1][1] = max(2*x, dp[i][1]+2*x, dp[i][0]+2*x)
    dp[i+1][2] = max(dp[i][2]+x, dp[i][1]+x)
    ans = max(dp[i+1][0], dp[i+1][1], dp[i+1][2])

print(ans)

贪心 / 堆

重排数组使相邻元素不同且字典序最小

给定一个整数数组 nums，其中可能包含重复元素。请重新排列数组，使得相邻两个元素不相同，并返回字典序最小的排列结果。若不存在合法排列，返回空数组。

示例：

1 2	输入：nums = [1,1,2,3] 输出：[1,2,1,3]

约束：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4

思路：

最大频次小于或等于 n/2 下取整即可满足题意
按照字典序重新排 kv，字典序小的优先

import java.util.*;

public class App {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Integer, Integer> cnt = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            cnt.merge(sc.nextInt(), 1, Integer::sum);
        }

        // 无解检测
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            if (e.getValue() > (n + 1) / 2) {
                System.out.println("[]");
                return;
            }
        }

        // 小根堆：数值小的优先（字典序最小）
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            pq.add(new int[]{e.getKey(), e.getValue()});
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int[] top = pq.poll();
            if (i == 0 || ans[i - 1] != top[0]) {
                // 直接用最小的
                ans[i] = top[0];
                if (top[1] > 1) pq.add(new int[]{top[0], top[1] - 1});
            } else {
                // 和上一个相同，取次小的
                int[] next = pq.poll();
                ans[i] = next[0];
                if (next[1] > 1) pq.add(new int[]{next[0], next[1] - 1});
                pq.add(top); // 放回
            }
        }

        System.out.println(Arrays.toString(ans));
    }
}

下载器与译码器的最优调度

题目描述： 有一个下载器和一个译码器。现共有 n 个任务，第 i 个任务的下载时间为 a_i，译码时间为 b_i。

每个任务都必须先由下载器完整地下载，之后才能由译码器译码。同一时刻，下载器最多只能处理一个任务，译码器也最多只能处理一个任务；但下载器与译码器可以同时工作——即下载器下载某个任务时，译码器可以译码另一个已经下载完成的任务。

你可以任意安排这 n 个任务的执行顺序（每个任务都执行恰好一次）。求完成所有任务所需的最短时间（即从时刻 0 开始，到最后一个任务译码完毕的时刻）。

n = 3
a = [4,3,2]
b = [1,4,3]
s1 = []
s2 = []
for i in range(n):
    if a[i] <= b[i]:
        s1.append(i)
    else:
        s2.append(i)
s1.sort(key=lambda i:a[i])
s2.sort(key=lambda i:-b[i])
order = s1 + s2
sum_a = sum_b = ans = 0
for i in range(n):
    sum_a += a[order[i]]
    sum_b = max(sum_a, sum_b)
    sum_b += b[order[i]]
print(sum_b)

字符串

最长 A/B 数量相等子字符串

给定一个只包含字符 'A' 和 'B' 的字符串 s，找出其中 A 和 B 数量相等的最长连续子字符串的长度。

1 2	输入：s = "AABBA" 输出：4

约束：

1 <= s.length <= 10^5
s[i] 只为 'A' 或 'B'

图论

一次免费通行的最短路径

给定 n 个节点（编号 0 到 n-1）和若干条带权无向边，求从节点 0 到节点 n-1 的最短路径。你有一次机会可以将经过的某条边的权重视为 0（即免费通行一次）。返回使用该机会后能得到的最小路径权重。

1 2	输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,2,5]] 输出：2

约束：

2 <= n <= 10^4
0 <= edges.length <= 10^5
edges[i] = [u, v, w]，其中 1 <= w <= 10^6

扩展：k 次免费通行的状态最短路（Dijkstra + 状态维度 dist[u][剩余免费次数][上一步是否用过免费]，实现片段如下）

// 2. dist[u][r][escapedLast]
int[][][] dist = new int[n][k + 1][2];
for (int i = 0; i < n; i++) {
    for (int r = 0; r <= k; r++) {
        Arrays.fill(dist[i][r], Integer.MAX_VALUE);
    }
}

// 3. 优先队列: [cost, u, r, escapedLast]
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
dist[start][k][0] = 0;
pq.offer(new int[]{0, start, k, 0});

while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int d = curr[0], u = curr[1], r = curr[2], escapedLast = curr[3];

    if (d > dist[u][r][escapedLast]) continue;
    if (u == end) return d;

    for (int[] next : graph[u]) {
        int v = next[0], w = next[1];

        // 决策 1: 正常通行
        if (d + w < dist[v][r][0]) {
            dist[v][r][0] = d + w;
            pq.offer(new int[]{d + w, v, r, 0});
        }

        // 决策 2: 逃逸通行
        if (r > 0 && escapedLast == 0) {
            if (d < dist[v][r - 1][1]) {
                dist[v][r - 1][1] = d;
                pq.offer(new int[]{d, v, r - 1, 1});
            }
        }
    }
}

return -1;