100 题训练启动 — Java 前 12 题

背景

这是"100 道基础题"训练计划的第一批题目。目标是通过编程题巩固 Java 基础语法和常用 API，同时练习防御式编程思维。

训练计划文件：F:/学习记录/100道基础题.md

题目概览（前 12 题）

题号	题目	考察点
1	两数之和	数组遍历、HashMap
2	斐波那契数列	递归/迭代、边界条件
3	判断回文数	字符串反转/数学方法
4	最大公约数	辗转相除法
5	数组去重	Set/双指针
6	字符串压缩	字符串遍历、StringBuilder
7	括号匹配	栈的应用
8	二分查找	有序数组、边界处理
9	快速排序	递归、分治
10	合并两个有序数组	双指针
11	找出出现次数最多的元素	HashMap 计数
12	反转链表	指针操作

两数之和（题 1）

题目：给定一个整数数组和目标值，返回两个数（索引）使它们之和等于目标值。

// 暴力法 O(n²)
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

优化：用 HashMap 一次遍历，O(n)：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

防御式编程要点：

• 数组为空或长度 < 2 时直接返回
• 找不到结果也要返回（不要抛异常）
• HashMap 的 put 语义：新值覆盖旧值，返回旧值

括号匹配（题 7）

题目：判断字符串中的括号是否成对匹配，如 (){}[] 合法，({)} 不合法。

public boolean isValid(String s) {
    if (s == null || s.length() % 2 != 0) return false;

    Map<Character, Character> pairs = new HashMap<>();
    pairs.put(')', '(');
    pairs.put('}', '{');
    pairs.put(']', '[');

    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {
            // 如果是右括号，检查栈顶是否匹配
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        } else {
            // 如果是左括号，入栈
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

反思： 这道题是栈的经典应用。之前学数据结构时知道 Stack 是什么，但遇到实际问题不会用。当前这题之后，再看 JSON 校验、HTML 标签闭合、表达式求值都是类似思路。

反转链表（题 12）

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;  // 保存下一个节点
        curr.next = prev;           // 反转指针
        prev = curr;                // 前移 prev
        curr = next;                // 前移 curr
    }
    return prev;  // 新的头节点
}

指针操作易错点：

• 要在修改 curr.next 之前保存 next 节点
• 循环结束后 prev 指向原链表的尾节点（即新链表的头）
• 递归解法也可以，但递归深度受链表长度限制

训练心得

12 道题做下来，暴露了以下问题：

1. HashMap 语义不清： put 返回旧值 vs 新值的混淆
2. 边界条件遗漏： 数组空、长度不足、null 指针的检查缺失
3. 栈的应用场景不熟悉： 知道 Stack 有什么方法，但不知道括号匹配该用栈
4. 防御式编程不足： 写完代码只考虑正常情况，不考虑异常输入

这些都是写好生产代码的基本功——生产环境的数据永远不会像 LeetCode 输入那样规整。