Java 算法与常用类库笔记

算法题的核心是把问题转换为明确的数据模型，选择匹配的数据结构，并通过复杂度分析判断方案能否在约束内运行。Java 代码还要注意输入解析、数值范围、比较器约定和可变对象的使用方式。

解题流程

1
2
3
4
5
6
7
8
9
flowchart TD
    A[阅读题目与约束] --> B[定义输入输出和边界]
    B --> C[构造最小示例]
    C --> D[设计朴素解法]
    D --> E[分析时间与空间复杂度]
    E --> F[选择数据结构或优化方法]
    F --> G[编码]
    G --> H[使用边界用例验证]
    H --> I[复盘不变量与可复用模板]

复杂度

双重遍历通常为 O(n^2)，在数据量较大时需要考虑哈希表、排序、双指针或前缀结构。复杂度估算应包含最坏情况，并同时考虑额外空间。

规模 常见可接受复杂度
n <= 20 指数搜索或状态压缩
n <= 10^3 O(n^2)
n <= 10^5 O(n log n) 或 O(n)
n >= 10^6 接近线性，且需关注常数与内存

这些只是经验范围，实际限制还取决于语言、时限和每步操作成本。

字符串

String 不可变，频繁拼接会创建中间对象。循环构造字符串时优先使用 StringBuilder。

1
2
3
4
5
6
StringBuilder builder = new StringBuilder();
builder.append("abc");
builder.insert(0, "prefix-");
builder.replace(0, 6, "head");
builder.deleteCharAt(builder.length() - 1);
String result = builder.reverse().toString();

常用 String 方法包括 length、charAt、substring、indexOf、split、equals 和 compareTo。使用 == 比较字符串只会比较对象引用，应使用 equals 比较内容。

数字解析

1
2
3
4
5
6
try {
    int value = Integer.parseInt(text.trim());
    System.out.println(value);
} catch (NumberFormatException exception) {
    System.out.println("invalid integer");
}

空字符串、非数字字符和超出 int 范围都会触发 NumberFormatException。更大的整数可使用 Long.parseLong 或 BigInteger。不要使用浮点解析后再转整数，因为大数和精度会产生错误。

输入处理

Scanner 易读但速度较慢，竞赛中可使用 BufferedReader 与 StringTokenizer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = Integer.parseInt(tokenizer.nextToken());
        }
    }
}

nextLine 读取整行，nextInt 只读取下一个整数。混合使用时，残留换行符容易导致读取空行。若每个数据占一行，应逐行读取；若同一行有多个数据，应使用分词器，不应假设一行必然包含全部输入，除非题目已经保证。

数组与排序

1
2
3
4
5
6
int[] values = {4, 2, 7, 1};
Arrays.sort(values);

String[] numbers = {"3", "30", "34", "5", "9"};
Arrays.sort(numbers, (a, b) -> (b + a).compareTo(a + b));
String largest = String.join("", numbers);

拼接最大数的比较器比较 b + a 与 a + b，决定两个字符串的相对顺序。比较器必须保持自反性、反对称性和传递性，否则排序结果可能异常。

二维数组排序时，可使用 Integer.compare 防止减法溢出：

1
2
3
4
Arrays.sort(intervals, (a, b) -> {
    int byStart = Integer.compare(a[0], b[0]);
    return byStart != 0 ? byStart : Integer.compare(a[1], b[1]);
});

栈、队列与双端队列

Java 中优先使用 ArrayDeque，不建议使用旧式 Stack。

1
2
3
4
5
6
7
8
9
10
11
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.peek();
int removed = stack.pop();

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
queue.offer(20);
int first = queue.peek();
int value = queue.poll();

push 与 pop 表示栈操作，offer 与 poll 表示队列操作。peek 在容器为空时返回 null，而 element 和 remove 会抛出异常。

Map

HashMap 提供平均常数时间的查找，不保证遍历顺序，并允许一个空键。TreeMap 按键排序，操作复杂度为 O(log n)，使用自然顺序时通常不接受空键。

1
2
3
4
5
6
7
8
Map<String, Integer> frequency = new HashMap<>();
for (String word : words) {
    frequency.merge(word, 1, Integer::sum);
}

for (Map.Entry<String, Integer> entry : frequency.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

常用方法包括 put、get、getOrDefault、containsKey、putIfAbsent、computeIfAbsent、merge、keySet、values 和 entrySet。

Math

1
2
3
4
5
6
double absolute = Math.abs(-3.5);
double root = Math.sqrt(81);
double power = Math.pow(2, 10);
long rounded = Math.round(3.6);
int minimum = Math.min(10, 20);
int maximum = Math.max(10, 20);

金额和需要精确小数表示的值不应使用 double。Math.pow 返回浮点数，不适合整数模幂或高精度运算。

BigInteger

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.math.BigInteger;

BigInteger a = new BigInteger("12345678901234567890");
BigInteger b = new BigInteger("9876543210");

BigInteger sum = a.add(b);
BigInteger difference = a.subtract(b);
BigInteger product = a.multiply(b);
BigInteger quotient = a.divide(b);
BigInteger remainder = a.mod(b);
BigInteger power = b.pow(3);
int comparison = a.compareTo(b);
String hexadecimal = a.toString(16);

BigInteger 是不可变对象，每次运算都会返回新值。除数不能为零，mod 要求模数为正。需要高效模幂时使用 modPow，不要先计算巨大幂再取模。

二分查找

二分查找适用于具有单调性质的搜索空间。循环不变量必须明确，以下模板查找第一个大于等于目标值的位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
static int lowerBound(int[] values, int target) {
    int left = 0;
    int right = values.length;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (values[middle] < target) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }
    return left;
}

搜索区间采用左闭右开形式 [left, right)。循环结束时 left == right，该位置就是第一个满足条件的下标，若返回数组长度则说明不存在满足条件的元素。

双指针与滑动窗口

滑动窗口适合维护连续区间。当右端扩展使条件不满足时，移动左端恢复不变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int longestWithoutDuplicate(String text) {
    Map<Character, Integer> last = new HashMap<>();
    int left = 0;
    int answer = 0;
    for (int right = 0; right < text.length(); right++) {
        char value = text.charAt(right);
        if (last.containsKey(value)) {
            left = Math.max(left, last.get(value) + 1);
        }
        last.put(value, right);
        answer = Math.max(answer, right - left + 1);
    }
    return answer;
}

前缀和

前缀和把多次区间求和从线性时间降低为常数时间。

1
2
3
4
5
long[] prefix = new long[values.length + 1];
for (int i = 0; i < values.length; i++) {
    prefix[i + 1] = prefix[i] + values[i];
}
long rangeSum = prefix[right + 1] - prefix[left];

累加结果可能超过 int，通常使用 long。二维前缀和还需要处理重复加减的交集区域。

回溯

回溯通过选择、递归和撤销选择枚举候选解。剪枝必须保证不会删除可能的正确答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void permutations(int[] values, boolean[] used, List<Integer> path) {
    if (path.size() == values.length) {
        System.out.println(path);
        return;
    }
    for (int i = 0; i < values.length; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        path.add(values[i]);
        permutations(values, used, path);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

动态规划

动态规划需要定义状态、转移、初始值和计算顺序。以斐波那契为例，只保留前两个状态即可将空间降为常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
static long fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    long previous = 0;
    long current = 1;
    for (int i = 2; i <= n; i++) {
        long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

贪心

贪心算法每一步选择当前最优方案。使用前必须证明局部选择不会破坏全局最优，常用证明方式包括交换论证和反证法。区间调度中，按结束时间最早选择可以留下最大的后续空间。

1
2
3
4
5
6
7
8
9
10
11
12
static int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(item -> item[1]));
    int count = 0;
    int end = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= end) {
            count++;
            end = interval[1];
        }
    }
    return count;
}

常见错误检查

  1. 空数组、单元素、重复元素和负数是否处理正确。
  2. int 加法或乘法是否可能溢出。
  3. 下标边界与闭区间、开区间是否一致。
  4. 比较器是否使用安全的比较方法。
  5. 递归深度是否可能导致栈溢出。
  6. 哈希表键是否正确实现相等性与哈希规则。
  7. 输入是否可能跨多行或包含多余空白。
  8. 算法复杂度是否符合最大数据规模。