LeetCode Hot 100 题解合集 (81-100)

title81 - 爬楼梯

ClimbingStairs.java

package leecode100.title81;

/**
 * 题目：爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 * 
 * 示例 1:
 * 输入: 2
 * 输出: 2
 * 解释: 有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 
 * 示例 2:
 * 输入: 3
 * 输出: 3
 * 解释: 有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 * 
 * 提示:
 * 1 <= n <= 45
 */
public class ClimbingStairs {
    /**
     * 解题思路：
     * 1. 这是一个典型的动态规划问题
     * 2. 状态定义：dp[i] 表示到达第 i 阶的方法总数
     * 3. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
     *    - 最后一步如果是跨1阶，之前已经站在第i-1阶，方法数是dp[i-1]
     *    - 最后一步如果是跨2阶，之前已经站在第i-2阶，方法数是dp[i-2]
     *    - 因为这两种情况互斥且覆盖全部可能，所以相加
     * 4. 初始条件：dp[0] = 1, dp[1] = 2
     * 5. 时间复杂度O(n)，空间复杂度O(n)
     */

    public static void main(String[] args) {
        // Test case 1
        ClimbingStairs solution = new ClimbingStairs();
        int n1 = 2;
        int result1 = solution.climbStairs(n1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int n2 = 3;
        int result2 = solution.climbStairs(n2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 方法数 = 最后一步跨一阶的方法 + 最后一步跨两阶的方法
        }
        return dp[n - 1];
    }
}

title82 - 杨辉三角

PascalsTriangle.java

package leecode100.title82;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：杨辉三角
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * 
 * 示例 1:
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 * 
 * 示例 2:
 * 输入: numRows = 1
 * 输出: [[1]]
 * 
 * 提示:
 * 1 <= numRows <= 30
 */
public class PascalsTriangle {
    /*
     * 解题思路：
     * 1. 按行生成杨辉三角
     * 2. 每行的第一个和最后一个元素都是1
     * 3. 中间的元素等于上一行相邻两个元素之和
     * 4. 使用动态规划的思想，逐行构建三角形
     */

    public static void main(String[] args) {
        // Test case 1
        PascalsTriangle solution = new PascalsTriangle();
        int numRows1 = 5;
        List<List<Integer>> result1 = solution.generate(numRows1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int numRows2 = 1;
        List<List<Integer>> result2 = solution.generate(numRows2);
        System.out.println("Test case 2 result: " + result2);
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            row.add(1); // 第一个 1
            if (i > 0) {
                List<Integer> prevRow = dp.get(i - 1);
                for (int j = 1; j < i; j++) {
                    row.add(prevRow.get(j - 1) + prevRow.get(j));
                }
                row.add(1); // 最后一个 1
            }
            dp.add(row);
        }
        return dp;
    }
}

title83 - 打家劫舍

HouseRobber.java

package leecode100.title83;

/**
 * 题目：打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下，
 * 一夜之内能够偷窃到的最高金额。
 * 
 * 示例 1:
 * 输入: [1,2,3,1]
 * 输出: 4
 * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4 。
 * 
 * 示例 2:
 * 输入: [2,7,9,3,1]
 * 输出: 12
 * 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * 
 * 提示:
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 */
public class HouseRobber {
    /**
     * 解题思路：
     * 1. 动态规划问题
     * 2. 状态定义：dp[i] 表示偷窃前 i+1 个房屋（即 nums[0] 到 nums[i]）能获得的最大金额
     *           dp[i-1] 表示偷窃前 i 个房屋（即 nums[0] 到 nums[i-1]）能获得的最大金额
     * 3. 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
     *    - dp[i-1] 表示不偷第i个房屋
     *    - dp[i-2] + nums[i] 表示偷第i个房屋
     * 4. 初始条件：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
     */

    public static void main(String[] args) {
        // Test case 1
        HouseRobber solution = new HouseRobber();
        int[] nums1 = {1,2,3,1};
        int result1 = solution.rob(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {2,7,9,3,1};
        int result2 = solution.rob(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length ==0){
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];

        dp[0] = nums[0];
        if (n == 1) return dp[0];

        dp[1] = Math.max(nums[0], nums[1]);
        if (n == 2) return dp[1];

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1],  dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
}

title84 - 完全平方数

PerfectSquares.java

package leecode100.title84;

/**
 * 题目：完全平方数
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
 * 例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 * 
 * 示例 1：
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 
 * 示例 2：
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 * 
 * 提示：
 * 1 <= n <= 10^4
 */
public class PerfectSquares {
    /**
     * 解题思路：
     * 1. 动态规划问题
     * 2. 状态定义：dp[i] 表示组成数字 i 所需的最少完全平方数个数
     * 3. 状态转移方程：dp[i] = min(dp[i - s]) + 1，其中 s 是小于等于 i 的完全平方数
     * 4. 初始化：dp[0] = 0（组成0需要0个平方数）
     * 5. 目标：dp[n]
     */

    public static void main(String[] args) {
        // Test cases
        PerfectSquares solution = new PerfectSquares();
        
        int n1 = 12;
        int res1 = solution.numSquares(n1);
        System.out.println("输入: " + n1 + ", 输出: " + res1); // 期望输出: 3
        
        int n2 = 13;
        int res2 = solution.numSquares(n2);
        System.out.println("输入: " + n2 + ", 输出: " + res2); // 期望输出: 2
    }

    public int numSquares(int n) {
        // dp[i] 表示组成数字 i 所需的最少完全平方数个数
        int[] dp = new int[n + 1];
        // 计算不超过 n 的所有完全平方数
        int m = (int) Math.sqrt(n);
        int[] squares = new int[m];
        for (int k = 1; k <= m; k++) squares[k - 1] = k * k;

        // 动态规划填表
        for (int i = 1; i <= n; i++) {
            int best = Integer.MAX_VALUE;
            // 遍历所有完全平方数，寻找最小组合
            for (int s : squares) {
                if (s > i) break;
                best = Math.min(best, dp[i - s]);
            }
            // 更新 dp[i]，即当前数字所需的最少平方数个数
            dp[i] = best + 1;
        }

        // 返回组成 n 所需的最少完全平方数个数
        return dp[n];
    }
}

title85 - 零钱兑换

CoinChange.java

package leecode100.title85;

import java.util.Arrays;

/**
 * 题目：零钱兑换
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 * 
 * 示例 1:
 * 输入: coins = [1, 2, 5], amount = 11
 * 输出: 3
 * 解释: 11 = 5 + 5 + 1
 * 
 * 示例 2:
 * 输入: coins = [2], amount = 3
 * 输出: -1
 * 
 * 示例 3:
 * 输入: coins = [1], amount = 0
 * 输出: 0
 * 
 * 提示:
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 2^31 - 1
 * 0 <= amount <= 10^4
 */
public class CoinChange {
    /**
     * 解题思路：
     * 1. 这是一个典型的动态规划问题（完全背包问题）
     * 2. 状态定义：dp[i] 表示凑成金额 i 所需的最少硬币个数
     * 3. 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 是硬币面额
     * 4. 初始化：dp[0] = 0（凑成金额0需要0个硬币），其余初始化为一个较大值
     * 5. 最终结果：dp[amount]，如果大于amount则返回-1
     */

    public static void main(String[] args) {
        // Test case 1
        CoinChange solution = new CoinChange();
        int[] coins1 = {1, 2, 5};
        int amount1 = 11;
        int result1 = solution.coinChange(coins1, amount1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] coins2 = {2};
        int amount2 = 3;
        int result2 = solution.coinChange(coins2, amount2);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        int[] coins3 = {1};
        int amount3 = 0;
        int result3 = solution.coinChange(coins3, amount3);
        System.out.println("Test case 3 result: " + result3);
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int max = amount + 1;
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

title86 - 单词拆分

WordBreak.java

package leecode100.title86;

import java.util.*;

/**
 * 题目：单词拆分
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 * 说明：
 * 拆分时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 
 * 示例 1:
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 * 
 * 示例 2:
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 * 注意你可以重复使用字典中的单词。
 * 
 * 示例 3:
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * 
 * 提示:
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅由小写英文字母组成
 */
public class WordBreak {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分
     * 3. 状态转移方程：dp[i] = dp[j] && wordDict.contains(s.substring(j, i))
     *    其中 j < i，表示如果前j个字符可以被拆分且j到i的子串在字典中，则前i个字符可以被拆分
     * 4. 初始化：dp[0] = true（空字符串可以被拆分）
     * 5. 最终结果：dp[s.length()]
     */

    public static void main(String[] args) {
        // Test case 1
        WordBreak solution = new WordBreak();
        String s1 = "leetcode";
        List<String> wordDict1 = Arrays.asList("leet", "code");
        boolean result1 = solution.wordBreak(s1, wordDict1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String s2 = "applepenapple";
        List<String> wordDict2 = Arrays.asList("apple", "pen");
        boolean result2 = solution.wordBreak(s2, wordDict2);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        String s3 = "catsandog";
        List<String> wordDict3 = Arrays.asList("cats", "dog", "sand", "and", "cat");
        boolean result3 = solution.wordBreak(s3, wordDict3);
        System.out.println("Test case 3 result: " + result3);
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}

title87 - 最长递增子序列

LongestIncreasingSubsequence.java

package leecode100.title87;

import java.util.Arrays;

/**
 * 题目：最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
 * 
 * 示例 1:
 * 输入: nums = [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 
 * 示例 2:
 * 输入: nums = [0,1,0,3,2,3]
 * 输出: 4
 * 
 * 示例 3:
 * 输入: nums = [7,7,7,7,7,7,7]
 * 输出: 1
 * 
 * 提示:
 * 1 <= nums.length <= 2500
 * -10^4 <= nums[i] <= 10^4
 * 
 * 进阶:
 * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 */
public class LongestIncreasingSubsequence {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
     * 3. 状态转移方程：dp[i] = max(dp[j] + 1) ，其中 j < i 且 nums[j] < nums[i]
     * 4. 初始化：dp数组全部初始化为1，因为每个元素本身构成长度为1的递增子序列
     * 5. 最终结果：dp数组中的最大值
     */

    public static void main(String[] args) {
        // Test case 1
        LongestIncreasingSubsequence solution = new LongestIncreasingSubsequence();
        int[] nums1 = {10,9,2,5,3,7,101,18};
        int result1 = solution.lengthOfLIS(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {0,1,0,3,2,3};
        int result2 = solution.lengthOfLIS(nums2);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        int[] nums3 = {7,7,7,7,7,7,7};
        int result3 = solution.lengthOfLIS(nums3);
        System.out.println("Test case 3 result: " + result3);
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }
}

title88 - 乘积最大子数组

MaximumProductSubarray.java

package leecode100.title88;

/**
 * 题目：乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），
 * 并返回该子数组所对应的乘积。
 * 测试用例的答案是一个 32-位 整数。
 * 
 * 示例 1:
 * 输入: nums = [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * 
 * 示例 2:
 * 输入: nums = [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 * 
 * 提示:
 * 1 <= nums.length <= 2 * 10^4
 * -10 <= nums[i] <= 10
 * nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
 */
public class MaximumProductSubarray {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 由于负数的存在，最大值可能变成最小值，最小值可能变成最大值
     * 3. 因此需要同时维护两个状态：
     *    - maxDp[i]: 以i结尾的连续子数组的最大乘积
     *    - minDp[i]: 以i结尾的连续子数组的最小乘积
     * 4. 状态转移方程：
     *    maxDp[i] = max(nums[i], maxDp[i-1]*nums[i], minDp[i-1]*nums[i])
     *    minDp[i] = min(nums[i], maxDp[i-1]*nums[i], minDp[i-1]*nums[i])
     * 5. 初始化：maxDp[0] = minDp[0] = nums[0]
     * 6. 最终结果：maxDp数组中的最大值
     */

    public static void main(String[] args) {
        // Test case 1
        MaximumProductSubarray solution = new MaximumProductSubarray();
        int[] nums1 = {2,3,-2,4};
        int result1 = solution.maxProduct(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {-2,0,-1};
        int result2 = solution.maxProduct(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxDp = new int[n];
        int[] minDp = new int[n];

        maxDp[0] = nums[0];
        minDp[0] = nums[0];

        int result = nums[0];
        for (int i = 1; i < n; i++) {
            int cur = nums[i];
            int preMax = maxDp[i - 1];
            int preMin = minDp[i - 1];
            maxDp[i] = Math.max(cur, Math.max(cur * preMax, cur * preMin));
            minDp[i] = Math.min(cur, Math.min(cur * preMax, cur * preMin));
            result = Math.max(result, maxDp[i]);
        }

        return result;
    }
}

title89 - 分割等和子集

PartitionEqualSubsetSum.java

package leecode100.title89;

/**
 * 题目：分割等和子集
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 
 * 示例 1:
 * 输入: nums = [1,5,11,5]
 * 输出: true
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11] 。
 * 
 * 示例 2:
 * 输入: nums = [1,2,3,5]
 * 输出: false
 * 解释: 数组不能分割成两个元素和相等的子集。
 * 
 * 提示:
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 */
public class PartitionEqualSubsetSum {
    /**
     * 解题思路：
     * 1. 这是一个0-1背包问题的变形
     * 2. 如果数组总和为奇数，则不可能分割成两个相等的子集
     * 3. 如果数组总和为偶数，则问题转化为：是否存在若干元素，其和恰好为总和的一半
     * 4. 状态定义：dp[j] 表示是否存在若干元素，其和恰好为 j
     * 5. 状态转移方程：dp[j] = dp[j] || dp[j - num]，其中 num 是当前考虑的元素
     * 6. 初始化：dp[0] = true（和为0的空集总是存在）
     * 7. 遍历顺序：外层遍历元素，内层倒序遍历背包容量（保证每个元素只使用一次）
     */

    public static void main(String[] args) {
        // Test case 1
        PartitionEqualSubsetSum solution = new PartitionEqualSubsetSum();
        int[] nums1 = {1,5,11,5};
        boolean result1 = solution.canPartition(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {1,2,3,5};
        boolean result2 = solution.canPartition(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public boolean canPartition(int[] nums) {
        // 1. 先计算数组总和
        int sum = 0;
        for (int num : nums) sum += num;

        // 2. 如果总和为奇数，则不可能平分成两个相等的子集
        if (sum % 2 != 0) return false;

        // 3. 目标子集和（背包容量）为 sum / 2
        int half = sum / 2;

        // 4. dp[j] 表示：是否存在若干元素，其和恰好为 j
        //    长度为 half + 1，索引范围 [0, half]
        boolean[] dp = new boolean[half + 1];

        // 5. 初始化：和为 0 时，空集可以达到（不选任何元素）
        dp[0] = true;

        // 6. 遍历每个物品（数组中的每个数）
        for (int num : nums) {
            // 7. 对于当前物品，要从后向前遍历 j（从 half 到 num）
            //    倒序是关键：保证每个物品只被使用一次（0-1 背包）
            //    正序的话会重复使用当前物品，变成完全背包问题
            for (int j = half; j >= num; j--) {
                // 8. 状态转移：如果之前有方案能凑出 (j - num)，
                //    那么现在可以通过加上当前 num 来凑出 j
                //    或者之前已经能凑出 j，二者取或
                dp[j] = dp[j] || dp[j - num];
            }
            // （循环结束后切换到下一个 num）
        }

        // 9. 最终结果看 dp[half]：是否能凑出目标和 half
        return dp[half];
    }
}

title90 - 最长有效括号

LongestValidParentheses.java

package leecode100.title90;

/**
 * 题目：最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 
 * 示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 
 * 示例 2：
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 
 * 示例 3：
 * 输入：s = ""
 * 输出：0
 * 
 * 提示：
 * 0 <= s.length <= 3 * 10^4
 * s[i] 为 '(' 或 ')'
 */
public class LongestValidParentheses {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[i] 表示以索引 i 结尾的最长有效括号子串的长度
     * 3. 状态转移：
     *    - s[i] == '(': dp[i] = 0 （不能以左括号结尾）
     *    - s[i] == ')': 分两种情况
     *      a. s[i-1] == '(': 形成 () 模式，dp[i] = dp[i-2] + 2
     *      b. s[i-1] == ')': 形成 )) 模式，检查前面是否有匹配
     * 4. 结果：max(dp[i])
     */

    public static void main(String[] args) {
        // Test cases
        LongestValidParentheses solution = new LongestValidParentheses();
        System.out.println(solution.longestValidParentheses("(()"));     // 2
        System.out.println(solution.longestValidParentheses(")()())"));  // 4
        System.out.println(solution.longestValidParentheses(""));        // 0
    }

    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n];  // dp[i]表示以i结尾的最长有效括号长度
        int maxLen = 0;

        for (int i = 1; i < n; i++) {
            // 只有右括号才可能形成有效括号
            if (s.charAt(i) == ')') {
                // 情况1: ...() 形式
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                // 情况2: ...)) 形式
                else if (dp[i - 1] > 0) { //检查前一个位置是否已经构成了有效括号序列。
                    // 找到与当前)匹配的(位置
                    int matchPos = i - 1 - dp[i - 1];
                    // 检查该位置是否存在且为(
                    if (matchPos >= 0 && s.charAt(matchPos) == '(') {
                        // 当前有效长度 = 中间部分 + 匹配的一对 + 前面的有效长度
                        dp[i] = dp[i - 1] + 2 + (matchPos >= 1 ? dp[matchPos - 1] : 0);
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }
}

title91 - 不同路径

UniquePaths.java

package leecode100.title91;

/**
 * 题目：不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 "Start" ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 "Finish" ）。
 * 问总共有多少条不同的路径？
 * 
 * 示例 1:
 * 输入: m = 3, n = 7
 * 输出: 28
 * 
 * 示例 2:
 * 输入: m = 3, n = 2
 * 输出: 3
 * 解释: 从左上角开始，总共有 3 条路径可以到达右下角。
 * 1. 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向下
 * 
 * 示例 3:
 * 输入: m = 7, n = 3
 * 输出: 28
 * 
 * 示例 4:
 * 输入: m = 3, n = 3
 * 输出: 6
 * 
 * 提示:
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 10^9
 */
public class UniquePaths {
    /**
     * 解题思路：
     * 1. 动态规划问题
     * 2. 状态定义：dp[i][j] 表示从起点到位置(i,j)的不同路径数
     * 3. 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
     *    因为只能从上方或左方到达当前位置
     * 4. 初始化：第一行和第一列的所有位置路径数都为1
     *    因为只能一直向右或一直向下到达这些位置
     * 5. 最终结果：dp[m-1][n-1]
     */

    public static void main(String[] args) {
        // Test case 1
        UniquePaths solution = new UniquePaths();
        int m1 = 3, n1 = 7;
        int result1 = solution.uniquePaths(m1, n1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int m2 = 3, n2 = 2;
        int result2 = solution.uniquePaths(m2, n2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

title92 - 最小路径和

MinimumPathSum.java

package leecode100.title92;

/**
 * 题目：最小路径和
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * 
 * 示例 1:
 * 输入: grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出: 7
 * 解释: 因为路径 1→3→1→1→1 的总和最小。
 * 
 * 示例 2:
 * 输入: grid = [[1,2,3],[4,5,6]]
 * 输出: 12
 * 
 * 提示:
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 200
 */
public class MinimumPathSum {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[i][j] 表示从左上角到位置(i,j)的最小路径和
     * 3. 状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     *    因为只能从上方或左方到达当前位置
     * 4. 初始化：第一行和第一列的路径和需要累加计算
     * 5. 最终结果：dp[m-1][n-1]
     */

    public static void main(String[] args) {
        // Test case 1
        MinimumPathSum solution = new MinimumPathSum();
        int[][] grid1 = {{1,3,1},{1,5,1},{4,2,1}};
        int result1 = solution.minPathSum(grid1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[][] grid2 = {{1,2,3},{4,5,6}};
        int result2 = solution.minPathSum(grid2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] , dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

title93 - 最长回文子串

LongestPalindromicSubstring.java

package leecode100.title93;

/**
 * 题目：最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 
 * 示例 1:
 * 输入: s = "babad"
 * 输出: "bab"
 * 解释: "aba"同样是符合题意的答案。
 * 
 * 示例 2:
 * 输入: s = "cbbd"
 * 输出: "bb"
 * 
 * 提示:
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 */
public class LongestPalindromicSubstring {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[j] 表示从位置j到当前位置i的子串是否为回文
     * 3. 状态转移方程：
     *    - 当i==j时，单个字符必然是回文
     *    - 当j+1==i时，两个字符相等则为回文
     *    - 其他情况：s.charAt(j) == s.charAt(i) 且 dp[j+1] 为true
     * 4. 遍历过程中记录最长回文子串的起始和结束位置
     * 5. 最终结果：返回最长回文子串
     */

    public static void main(String[] args) {
        // Test case 1
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();
        String s1 = "babad";
        String result1 = solution.longestPalindrome(s1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String s2 = "cbbd";
        String result2 = solution.longestPalindrome(s2);
        System.out.println("Test case 2 result: " + result2);
    }

    public String longestPalindrome(String s) {
       boolean[] dp = new boolean[s.length()];
        int start = 0, end = 0;
        // 外层循环：遍历字符串的每个位置作为回文子串的结束索引i
        for (int i = 0; i < s.length(); i++) {
            // 内层循环：遍历从0到i的每个位置作为回文子串的起始索引j
            for (int j = 0; j <= i; j++) {
                if (i == j) {
                    dp[j] = true;
                } else if (j + 1 == i) {
                    dp[j] = s.charAt(j) == s.charAt(i);
                } else {
                    dp[j] = s.charAt(j) == s.charAt(i) && dp[j + 1];
                }

                if (dp[j] && i - j > end - start) {
                    start = j;
                    end = i;
                }
            }
        }

        return s.substring(start, end + 1);
    }
}

title94 - 最长公共子序列

LongestCommonSubsequence.java

package leecode100.title94;

/**
 * 题目：最长公共子序列
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
 * 如果不存在公共子序列，返回 0。
 * 一个字符串的子序列是指这样一个新的字符串：
 * 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 
 * 示例 1:
 * 输入: text1 = "abcde", text2 = "ace"
 * 输出: 3
 * 解释: 最长公共子序列是 "ace"，它的长度为 3。
 * 
 * 示例 2:
 * 输入: text1 = "abc", text2 = "abc"
 * 输出: 3
 * 解释: 最长公共子序列是 "abc"，它的长度为 3。
 * 
 * 示例 3:
 * 输入: text1 = "abc", text2 = "def"
 * 输出: 0
 * 解释: 两个字符串没有公共子序列，返回 0。
 * 
 * 提示:
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成
 */
public class LongestCommonSubsequence {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度
     * 3. 状态转移方程：
     *    - 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
     *    - 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
     * 4. 初始化：dp[0][j] = 0, dp[i][0] = 0（空字符串与任何字符串的公共子序列长度为0）
     * 5. 最终结果：dp[m][n]
     */

    public static void main(String[] args) {
        // Test case 1
        LongestCommonSubsequence solution = new LongestCommonSubsequence();
        String text11 = "abcde", text21 = "ace";
        int result1 = solution.longestCommonSubsequence(text11, text21);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String text12 = "abc", text22 = "abc";
        int result2 = solution.longestCommonSubsequence(text12, text22);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        String text13 = "abc", text23 = "def";
        int result3 = solution.longestCommonSubsequence(text13, text23);
        System.out.println("Test case 3 result: " + result3);
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j < n + 1; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}

title95 - 编辑距离

EditDistance.java

package leecode100.title95;

/**
 * 题目：编辑距离
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 
 * 示例 1:
 * 输入: word1 = "horse", word2 = "ros"
 * 输出: 3
 * 解释:
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * 
 * 示例 2:
 * 输入: word1 = "intention", word2 = "execution"
 * 输出: 5
 * 解释:
 * intention -> inention (删除 't')
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 * 
 * 提示:
 * 0 <= word1.length, word2.length <= 500
 * word1 和 word2 由小写英文字母组成
 */
public class EditDistance {
    /**
     * 解题思路：
     * 1. 动态规划
     * 2. 状态定义：D[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数
     * 3. 状态转移方程：
     *    D[i][j] = min(
     *      D[i-1][j] + 1,      // 删除操作
     *      D[i][j-1] + 1,      // 插入操作
     *      D[i-1][j-1] + (word1[i-1] != word2[j-1] ? 1 : 0)  // 替换或匹配操作
     *    )
     * 4. 初始化：
     *    D[i][0] = i (word1前i个字符转换为空字符串需要i次删除操作)
     *    D[0][j] = j (空字符串转换为word2前j个字符需要j次插入操作)
     * 5. 最终结果：D[word1.length()][word2.length()]
     */

    public static void main(String[] args) {
        // Test case 1
        EditDistance solution = new EditDistance();
        String word11 = "horse", word21 = "ros";
        int result1 = solution.minDistance(word11, word21);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String word12 = "intention", word22 = "execution";
        int result2 = solution.minDistance(word12, word22);
        System.out.println("Test case 2 result: " + result2);
    }

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] D = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < n + 1; j++) {
            D[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }

        return D[m][n];
    }
}

title96 - 只出现一次的数字

SingleNumber.java

package leecode100.title96;

/**
 * 题目：只出现一次的数字
 * 给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。
 * 找出那个只出现了一次的元素。
 * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
 * 
 * 示例 1：
 * 输入：nums = [2,2,1]
 * 输出：1
 * 
 * 示例 2：
 * 输入：nums = [4,1,2,1,2]
 * 输出：4
 * 
 * 示例 3：
 * 输入：nums = [1]
 * 输出：1
 * 
 * 提示：
 * 1 <= nums.length <= 3 * 10^4
 * -3 * 10^4 <= nums[i] <= 3 * 10^4
 * 除了某个元素只出现一次以外，其余每个元素均出现两次。
 */
public class SingleNumber {
    /**
     * 解题思路：
     * 1. 利用异或运算的性质：
     *    - 任何数与自身异或结果为0：a ^ a = 0
     *    - 任何数与0异或结果为其本身：a ^ 0 = a
     *    - 异或运算满足交换律和结合律
     * 2. 将数组中所有数字进行异或运算，出现两次的数字会相互抵消为0，
     *    最终只剩下只出现一次的那个数字
     * 3. 时间复杂度：O(n)，空间复杂度：O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        SingleNumber solution = new SingleNumber();
        int[] nums1 = {2, 2, 1};
        int result1 = solution.singleNumber(nums1);
        System.out.println("Test case 1 result: " + result1); // Expected: 1

        // Test case 2
        int[] nums2 = {4, 1, 2, 1, 2};
        int result2 = solution.singleNumber(nums2);
        System.out.println("Test case 2 result: " + result2); // Expected: 4

        // Test case 3
        int[] nums3 = {1};
        int result3 = solution.singleNumber(nums3);
        System.out.println("Test case 3 result: " + result3); // Expected: 1
    }

    public int singleNumber(int[] nums) {
        int result = 0;
        // 对数组中所有元素进行异或运算
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

title97 - 多数元素

MajorityElement.java

package leecode100.title97;

/**
 * 题目：多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 
 * 示例 1:
 * 输入: [3,2,3]
 * 输出: 3
 * 
 * 示例 2:
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * 
 * 提示:
 * n == nums.length
 * 1 <= n <= 5 * 10^4
 * -2^31 <= nums[i] <= 2^31 - 1
 * 
 * 进阶: 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 */
public class MajorityElement {
    /**
     * 解题思路：
     * 1. 使用Boyer-Moore投票算法解决这个问题
     * 2. 维护一个候选多数元素和计数器
     * 3. 遍历数组：
     *    - 如果计数器为0，更新候选元素为当前元素
     *    - 如果当前元素等于候选元素，计数器加1
     *    - 否则计数器减1
     * 4. 由于多数元素出现次数超过一半，最终候选元素就是多数元素
     * 5. 时间复杂度O(n)，空间复杂度O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        MajorityElement solution = new MajorityElement();
        int[] nums1 = {3,2,3};
        int result1 = solution.majorityElement(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {2,2,1,1,1,2,2};
        int result2 = solution.majorityElement(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? +1 : -1;
        }

        return candidate;
    }
}

title98 - 颜色分类

SortColors.java

package leecode100.title98;

import java.util.Arrays;

/**
 * 题目：颜色分类
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
 * 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
 * 必须在不使用库内置的 sort 函数的情况下解决这个问题。
 * 
 * 示例 1:
 * 输入: nums = [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * 
 * 示例 2:
 * 输入: nums = [2,0,1]
 * 输出: [0,1,2]
 * 
 * 示例 3:
 * 输入: nums = [0]
 * 输出: [0]
 * 
 * 示例 4:
 * 输入: nums = [1]
 * 输出: [1]
 * 
 * 提示:
 * n == nums.length
 * 1 <= n <= 300
 * nums[i] 为 0、1 或 2
 * 
 * 进阶:
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 */
public class SortColors {
    /**
     * 解题思路：
     * 1. 使用三指针技术（荷兰国旗问题）解决这个问题
     * 2. 维护三个指针：
     *    - l: 指向下一个0应该放置的位置
     *    - r: 指向下一个2应该放置的位置
     *    - i: 当前遍历的位置
     * 3. 遍历数组：
     *    - 如果当前元素是0，与l位置交换，l和i都前移
     *    - 如果当前元素是2，与r位置交换，r后移
     *    - 如果当前元素是1，i前移
     * 4. 当i超过r时结束
     * 5. 时间复杂度O(n)，空间复杂度O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        SortColors solution = new SortColors();
        int[] nums1 = {2,0,2,1,1,0};
        solution.sortColors(nums1);
        System.out.println("Test case 1 result: " + Arrays.toString(nums1));

        // Test case 2
        int[] nums2 = {2,0,1};
        solution.sortColors(nums2);
        System.out.println("Test case 2 result: " + Arrays.toString(nums2));
    }

    public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int i = 0;
        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums, i, l);
                i++;
                l++;
            } else if (nums[i] == 2) {
                swap(nums, i, r);
                r--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

title99 - 下一个排列

NextPermutation.java

package leecode100.title99;

import java.util.Arrays;

/**
 * 题目：下一个排列
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须原地修改，只允许使用额外常数空间。
 * 
 * 示例 1:
 * 输入: [1,2,3]
 * 输出: [1,3,2]
 * 
 * 示例 2:
 * 输入: [3,2,1]
 * 输出: [1,2,3]
 * 
 * 示例 3:
 * 输入: [1,1,5]
 * 输出: [1,5,1]
 * 
 * 示例 4:
 * 输入: [1]
 * 输出: [1]
 * 
 * 提示:
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 */
public class NextPermutation {
    /**
     * 解题思路：
     * 1. 从右向左找到第一个降序的位置i（即nums[i] < nums[i+1]）
     * 2. 如果找不到这样的位置，说明整个数组是降序的，直接反转整个数组
     * 3. 如果找到了位置i，再从右向左找到第一个大于nums[i]的元素nums[j]
     * 4. 交换nums[i]和nums[j]
     * 5. 反转i+1到末尾的子数组，使其变为升序（最小排列）
     * 
     * 核心思想：高位微调 + 右侧最小化
     * 时间复杂度O(n)，空间复杂度O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        NextPermutation solution = new NextPermutation();
        int[] nums1 = {1,2,3};
        solution.nextPermutation(nums1);
        System.out.println("Test case 1 result: " + Arrays.toString(nums1));

        // Test case 2
        int[] nums2 = {3,2,1};
        solution.nextPermutation(nums2);
        System.out.println("Test case 2 result: " + Arrays.toString(nums2));

        // Test case 3
        int[] nums3 = {1,1,5};
        solution.nextPermutation(nums3);
        System.out.println("Test case 3 result: " + Arrays.toString(nums3));
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        
        reverse(nums, i + 1, n - 1);
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            swap(nums, l, r);
            l++;
            r--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

title100 - 寻找重复数

FindTheDuplicateNumber.java

package leecode100.title100;

/**
 * 题目：寻找重复数
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），
 * 可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * 你必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
 * 
 * 示例 1:
 * 输入: nums = [1,3,4,2,2]
 * 输出: 2
 * 
 * 示例 2:
 * 输入: nums = [3,1,3,4,2]
 * 输出: 3
 * 
 * 示例 3:
 * 输入: nums = [1,1]
 * 输出: 1
 * 
 * 示例 4:
 * 输入: nums = [1,1,2]
 * 输出: 1
 * 
 * 提示:
 * 1 <= n <= 10^5
 * nums.length == n + 1
 * 1 <= nums[i] <= n
 * nums 中只有一个整数 appear 两次或多次，其余整数均只出现一次
 * 
 * 进阶:
 * 如何证明 nums 中至少存在一个重复的数字?
 * 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?
 */
public class FindTheDuplicateNumber {
    /**
     * 解题思路：
     * 1. 使用Floyd判圈算法（龟兔赛跑算法）解决这个问题
     * 2. 将数组看作链表，索引i指向nums[i]，形成一个链表结构
     * 3. 由于存在重复数字，必然存在环，重复数字就是环的入口
     * 4. 分两阶段操作：
     *    第一阶段：找环内相遇点，慢指针每次走1步，快指针每次走2步
     *    第二阶段：找环的入口，将慢指针重置到起点，两指针都每次走1步
     * 5. 最终相遇点就是环的入口，即重复的数字
     */

    public static void main(String[] args) {
        // Test case 1
        FindTheDuplicateNumber solution = new FindTheDuplicateNumber();
        int[] nums1 = {1,3,4,2,2};
        int result1 = solution.findDuplicate(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {3,1,3,4,2};
        int result2 = solution.findDuplicate(nums2);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        int[] nums3 = {1,1};
        int result3 = solution.findDuplicate(nums3);
        System.out.println("Test case 3 result: " + result3);

        // Test case 4
        int[] nums4 = {1,1,2};
        int result4 = solution.findDuplicate(nums4);
        System.out.println("Test case 4 result: " + result4);
    }

    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}