蓝桥杯之阶段考核

📖 Day 7：阶段考核 - 蓝桥杯官方模拟赛（限时 4 小时）

📖 一、如何高效完成模拟赛？

模拟赛是一种接近真实竞赛的训练方式。要高效完成模拟赛，需要掌握以下策略：

1. 赛前准备

✅ 环境搭建：确保 Java 开发环境、IDE（如 IntelliJ IDEA、Eclipse、VS Code）正常运行，输入输出调试正常。
✅ 熟悉常见模板：准备好 DFS、回溯、动态规划、位运算等常用算法模板，避免比赛时临时推导。
✅ 阅读题目速度：比赛时，快速理解题意，确定题目涉及的算法类型。

2. 赛时策略

📌 ① 先做简单题：先做 确定思路的题，比如基础遍历、贪心算法、双指针等题目。
📌 ② 观察数据规模：如果数据规模 ≤10^6，考虑 O(n) 或 O(n log n) 解法；如果 ≤100，考虑 O(n²) 解法；如果 ≤20，考虑回溯 + 剪枝。
📌 ③ 分析边界情况：比如 n=1、n=0、极端输入情况，防止 ArrayIndexOutOfBoundsException。
📌 ④ 超时优化：如果代码超时，优化时间复杂度（如 O(n²) → O(n log n)），或改用位运算、哈希表、前缀和等加速。

3. 赛后复盘

🔍 ① 查看错误代码：分析错误原因，如 索引越界、浮点精度、整数溢出、边界处理错误。
🔍 ② 记录思路：如果某题没做出来，找出 最优解法 并理解其时间复杂度。
🔍 ③ 归纳高频考点：整理本场比赛涉及的算法，找出自己薄弱的地方，强化训练。

📖 二、常见题型及解法

模拟赛一般包含以下几种类型的题目，我们来看几道典型题目的解法：

📌 1. 经典贪心题目：区间覆盖

题目描述

给定 n 个区间 [li, ri]，选择最少数量的区间，使得区间 start 到 end 都被覆盖。

解题思路

先按 左端点排序，然后贪心地选择能覆盖更多区域的区间。
如果当前区间无法覆盖 start，返回 -1，否则更新当前 end。

代码实现

import java.util.*;

public class IntervalCover {
    public static int minIntervals(int[][] intervals, int start, int end) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); // 按左端点排序
        int count = 0, curEnd = start, i = 0;

        while (curEnd < end) {
            int maxEnd = curEnd;
            while (i < intervals.length && intervals[i][0] <= curEnd) {
                maxEnd = Math.max(maxEnd, intervals[i][1]);
                i++;
            }
            if (maxEnd == curEnd) return -1; // 无法覆盖
            curEnd = maxEnd;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 5}, {3, 6}, {5, 8}};
        System.out.println(minIntervals(intervals, 1, 8)); // 输出 2
    }
}

时间复杂度：O(n log n)（排序） + O(n)（遍历） = O(n log n)。

📌 2. 经典回溯题目：全排列

题目描述

给定一个不含重复数字的数组 nums，返回所有可能的全排列。

解题思路

使用 回溯 + 递归，每次选择一个数字加入排列，回溯时撤销选择。

代码实现

import java.util.*;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                tempList.add(nums[i]);
                backtrack(result, tempList, nums, used);
                tempList.remove(tempList.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}

时间复杂度：O(n!)，因为每个元素都会被排列。

📌 3. 经典动态规划题目：最长递增子序列（LIS）

题目描述

给定一个整数数组 nums，找到其中最长递增子序列的长度。

解题思路

dp[i] 代表以 nums[i] 结尾的最长递增子序列长度。
对于每个 nums[i]，遍历 nums[j] (j < i)，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。

代码实现

import java.util.*;

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("最长递增子序列长度: " + lis.lengthOfLIS(nums)); // 输出 4
    }
}

时间复杂度：O(n²)，优化可用 O(n log n)（二分查找 + 贪心）。