刷题记录

本笔记按题意抽象、核心思路、代码实现、复杂度和易错点记录题目。代码默认使用 Java，所有结论均以给定约束为前提。

flowchart TD
    A[读取题目] --> B[提取约束和目标]
    B --> C[手工推演样例]
    C --> D[选择数据结构]
    D --> E[证明核心步骤]
    E --> F[实现代码]
    F --> G[检查空值 边界 溢出]
    G --> H[分析复杂度]

求出胜利玩家的数目

题意

共有 n 名玩家，pick[i] 表示某名玩家获得某种颜色的球。若玩家编号为 i，只要其任意一种颜色的球数量严格大于 i，该玩家就是胜利玩家。颜色编号范围为 0 到 10。

思路

使用二维数组记录每名玩家拥有的各色球数量。统计完成后，逐个玩家检查是否存在数量大于玩家编号的颜色。每名玩家最多计数一次。

class Solution {
    public int winningPlayerCount(int n, int[][] pick) {
        int[][] count = new int[n][11];
        for (int[] item : pick) {
            count[item[0]][item[1]]++;
        }

        int winners = 0;
        for (int player = 0; player < n; player++) {
            for (int color = 0; color <= 10; color++) {
                if (count[player][color] > player) {
                    winners++;
                    break;
                }
            }
        }
        return winners;
    }
}

时间复杂度为 O(m + nC)，其中 m 是拾取记录数，C 固定为 11。空间复杂度为 O(nC)。若颜色范围未知或非常大，应改用嵌套哈希表，避免分配巨大稀疏数组。

两数之和

题意

给定数组 nums 与目标值 target，返回两个不同元素的下标，使它们的和等于目标值。题目保证存在唯一答案。

暴力枚举

class Solution {
    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};
                }
            }
        }
        throw new IllegalArgumentException("no solution");
    }
}

暴力法时间复杂度为 O(n²)，额外空间复杂度为 O(1)。

哈希表优化

遍历当前数字 nums[i] 时，先查询此前是否出现过补数 target - nums[i]。先查询再写入可以避免同一元素被使用两次，同时正确处理重复值。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer previous = indexByValue.get(complement);
            if (previous != null) {
                return new int[] {previous, i};
            }
            indexByValue.put(nums[i], i);
        }
        throw new IllegalArgumentException("no solution");
    }
}

平均时间复杂度为 O(n)，空间复杂度为 O(n)。

斐波那契数

题意

F(0) = 0，F(1) = 1，且 F(n) = F(n - 1) + F(n - 2)。计算给定 n 的斐波那契数。

迭代解法

直接递归会重复计算大量子问题，时间复杂度接近指数级。只保留前两项即可把空间降为常数级。

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }

        int previous = 0;
        int current = 1;
        for (int i = 2; i <= n; i++) {
            int next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}

时间复杂度为 O(n)，空间复杂度为 O(1)。若 n 较大，需要使用 long、BigInteger 或快速倍增法，并先确认题目是否要求取模。

使数组元素达到阈值的最少操作数

题意

每次取出数组中最小的两个数 x 和 y，加入 2 × min(x, y) + max(x, y)。求使所有元素都不小于 k 的最少操作次数。

思路

每一步都必须操作当前最小的元素，否则它仍然低于阈值。为了让新值尽可能有效且遵循题目指定操作，持续取出最小的两个元素。最小堆可以在对数时间内完成取出与插入。

import java.util.PriorityQueue;

class Solution {
    public int minOperations(int[] nums, int k) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer((long) value);
        }

        int operations = 0;
        while (heap.peek() < k) {
            long first = heap.poll();
            long second = heap.poll();
            heap.offer(first * 2 + second);
            operations++;
        }
        return operations;
    }
}