参考资料：https://programmercarl.com/
https://codetop.cc/home

回溯算法

组合

电话号码的字母组合（17）- 13

// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
// 输入：digits = "23"
// 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 输入：digits = "2"
// 输出：["a","b","c"]
class Solution {
    // 设置全局列表存储最后的结果
    List<String> result = new ArrayList<>();
    // 初始对应所有的数字
    String[] numString = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        // 迭代处理
        backTracking(digits, 0);
        return result;
    }
    // 存储回溯过程中的字符
    StringBuilder path = new StringBuilder();
    public void backTracking(String digits, int index) {
        // 终止条件：字母组合长度 与 输入字符长度相等
        if (path.length() == digits.length()) {
            result.add(path.toString());
            return;
        }
        // 数字到字母映射的对应位置（字符 - 字符）
        int pos = digits.charAt(index) - '2';
        // 遍历当前数字对应的字符集（比如数字2对应的字符集为abc）
        for (int i = 0; i < numString[pos].length(); i++) { 
            path.append(numString[pos].charAt(i));  // 把单个字母添加到路径
            backTracking(digits, index + 1);        // 进入下一个数字
            path.deleteCharAt(path.length()-1);     // 去除路径中最后添加的字母
        }
    }
}

组合总和（39）- 62

// https://leetcode.cn/problems/combination-sum/
// 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合
// candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的
// 对于给定的输入，保证和为 target 的不同组合数少于 150 个
// 输入：candidates = [2,3,6,7], target = 7
// 输出：[[2,2,3],[7]]
// 解释：
// 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
// 7 也是一个候选， 7 = 7 。
// 仅有这两种组合。
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    // 存储计算过程中的值
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0);
        return result;
    }
    public void backtrack(int[] candidates, int target, int start){
        if(sum == target){
            // 此处不能直接使用path
            result.add(new ArrayList<>(path));
            return;
        }
        // 剪枝操作：若sum + candidates[i] > target, 则不进入循环
        for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++){
            sum = sum + candidates[i];
            path.add(candidates[i]);
            // 因为candidates中的元素可以无限制重复被选取，所以此处递归传入i，而不是start+1
            backtrack(candidates, target, i);
            // 去除路径中最后添加的数字
            path.remove(path.size() - 1);
            // 减去最后添加的数字（此时可能刚好满足条件，或者和超过target）
            sum = sum - candidates[i];
        }
    }
}

组合总和 II（40）- 34

// https://leetcode.cn/problems/combination-sum-ii/
// 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
// candidates 中的每个数字在每个组合中只能使用 一次
// 注意：解集不能包含重复的组合
// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 输出:
// [
//     [1,1,6],
//     [1,2,5],
//     [1,7],
//     [2,6]
// ]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        process(candidates, target, 0);
        return result;
    }
    public void process(int[] candidates, int target, int start){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++){
            // 去重，若candidates中存在重复元素，只需要取其中一个元素进行递归操作即可
            // 后续相同的元素就不需要再进行求和操作，因为肯定与前一个相同元素求出的结果一致，此时就重复了
            if(i > start && candidates[i] == candidates[i-1]) continue;
            sum = sum + candidates[i];
            path.add(candidates[i]);
            process(candidates, target, i + 1);
            // 回溯
            path.remove(path.size() - 1);
            sum = sum - candidates[i];
        }
    }
}

组合（77）- 11

// https://leetcode.cn/problems/combinations/description/
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合
// 你可以按 任何顺序 返回答案
// 输入：n = 4, k = 2
// 输出：
// [
//   [2,4],
//   [3,4],
//   [2,3],
//   [1,2],
//   [1,3],
//   [1,4],
// ]
class Solution {
    // 存放符合条件结果的集合
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(n, k, 1);
        return result;
    }
    // 用来存放符合条件结果
    LinkedList<Integer> path = new LinkedList<Integer>();
    // startIndex记录下一层递归，搜索的起始位置
    private void backtrack(int n, int k, int startIndex){
        // 终止条件
        if(path.size() == k){
            result.add(new ArrayList<>(path));  // 存放结果
            return;
        }
        // 控制树的横向遍历
        // n-(k-path.size())+1：表示起始位置最多能到达的位置
        for(int i = startIndex; i <= n-(k-path.size())+1; i++){
            // 处理节点
            path.add(i);
            // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            backtrack(n, k, i + 1);
            // 回溯，撤销处理的节点
            path.removeLast();
        }
    }
}

组合总和 III（216）- 34

// https://leetcode.cn/problems/combination-sum-iii/
// 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
//         只使用数字1到9
//         每个数字 最多使用一次 
// 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回
// 输入: k = 3, n = 9
// 输出: [[1,2,6], [1,3,5], [2,3,4]]
// 解释:
// 1 + 2 + 6 = 9
// 1 + 3 + 5 = 9
// 2 + 3 + 4 = 9
// 没有其他符合的组合了
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        process(k, n, 1);
        return result;
    }
    public void process(int num, int target, int start){
        // 终止条件
        if(path.size() == num || target <= 0){
            if(path.size() == num && target == 0){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i = start; i < 10; i++){
            path.add(i);
            process(num, target-i, i+1);
            path.remove(path.size() - 1);
        }
    }
}

组合总和 Ⅳ（377）- 3

// https://leetcode.cn/problems/combination-sum-iv/description/
// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
// 题目数据保证答案符合 32 位整数范围
// 输入：nums = [1,2,3], target = 4
// 输出：7
// 解释：
// 所有可能的组合为：
// (1, 1, 1, 1)
// (1, 1, 2)
// (1, 2, 1)
// (1, 3)
// (2, 1, 1)
// (2, 2)
// (3, 1)
// 请注意，顺序不同的序列被视作不同的组合
class Solution {
    public int combinationSum4(int[] nums, int target) {
        //【1】dp[i]表示凑成目标正整数为i的排列个数为dp[i]
        int[] dp = new int[target + 1];
        //【2】dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础
        dp[0] = 1;
        // 如果求组合数就是外层for循环遍历物品，内层for循环遍历背包
        // 如果求排列数就是外层for循环遍历背包，内层for循环遍历物品
        //【3】先遍历背包容量，再遍历物品
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                //【4】只有当背包容量大于等于物品i的容量时，才需要考虑装 或 不装物品i
                if (i >= nums[j]) {
                    //【5】dp[i]表示不装物品j后凑成目标i的排列个数，dp[i - nums[j]]表示装物品j后凑成目标i的排列个数
                    // i - nums[j]表示装填物品j需要的容量
                    dp[i] = dp[i] + dp[i - nums[j]];
                }
            }
        }
        //【6】凑成目标为target的排列个数
        return dp[target];
    }
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    int sum = 0;
    // 解答错误
    public int combinationSum41(int[] nums, int target) {
        process(nums, target, 0);
        return result.size();
    }
    public void process(int[] nums, int target, int start){
        if(start == nums.length){
            return;
        }
        if(sum == target){
            result.add(new ArrayList<>(path));
        }
        for(int i = start; i < nums.length && sum + nums[i] <= target; i++){
            sum = sum + nums[i];
            path.add(nums[i]);
            process(nums, target, start);
            sum = sum - nums[i];
            path.remove(path.size() - 1);
        }
    }
}

分割

复原IP地址（93）

// https://leetcode.cn/problems/restore-ip-addresses/
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
// 输入：s = "101023"
// 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
class Solution {
    List<String> result = new ArrayList<String>();
    Deque<String> path = new ArrayDeque<>(4);
    public List<String> restoreIpAddresses(String s) {
        process(s, 0, 4);
        return result;
    }
    // start表示当前索引位置，reside表示剩余段数
    public void process(String s, int start, int reside){
        // 终止条件
        if(start == s.length()){
            // 当变量到最后一个字符 且 剩余段数为0时，将此时的path添加到结果集中
            if(reside == 0){
                result.add(String.join(".", path));
            }
            return;
        }
        for(int i = start; i < start + 3 && i < s.length(); i++){
            // 若字符串剩余长度 大于 剩余分段所需最大长度，表明先前的分段不合理，最后会存在剩余字符
            if(s.length() - i > reside * 3){
                continue;
            }
            // 截取的字符串满足条件
            if(judgeNumber(s, start, i)){
                // 截取部分字符添加到path中
                String cur = s.substring(start, i+1);
                path.addLast(cur);
                // 纵向递归
                process(s, i+1, reside-1);
                path.removeLast();
            }
        }
    }
    // 判断截取的字符串是否满足要求
    public boolean judgeNumber(String s, int left, int right){
        int len = right - left + 1;
        // 当前为0开头 且 长度大于1的数字需要剪枝
        if(s.charAt(left) == '0' && len > 1){
            return false;
        }
        // 将当前截取的字符串转化成数字
        int res = Integer.parseInt(s.substring(left, right+1));
        // 判断截取到的数字是否符合
        return res >= 0 && res <= 255;
    }
}

分割回文串（131）- 9

// https://leetcode.cn/problems/palindrome-partitioning/
// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案
// 回文串 是正着读和反着读都一样的字符串
// 输入：s = "aab"
// 输出：[["a","a","b"],["aa","b"]]
class Solution {
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> path = new ArrayList<String>();
    // 分割后所有子串相加后的总长度
    // int lenSum = 0;
    public List<List<String>> partition(String s) {
        process(s, 0);
        return result;
    }
    public void process(String s, int start){
        // 终止条件：分割后所有子串相加后的总长度 等于 原字符串长度
        // if (lenSum == s.length()){
        // 终止条件：起始位置 大于 s长度，表明找到一组分割方案
        if (start >= s.length()){       
            result.add(new ArrayList<>(path));
            return;
        }
        // 横向遍历字符串
        for (int i = start; i < s.length(); i++) {
            // 截取字符串判断是否回文串
            String str = s.substring(start, i+1);
            if (!isPalindrome(str)){
                continue;
            }
            // 若是回文串，加入path
            path.add(str);
            // 被截取字符串的长度
            // int len = i + 1 - start;
            // lenSum += len;
            // 纵向遍历：递归
            process(s, i+1);
            // lenSum -= len;
            path.remove(path.size()-1);
        }
    }
    // 判断回文串
    public boolean isPalindrome(String s){
        for(int i = 0; i < s.length() / 2; i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}

22222 - 分割回文串 II（132）

子集

子集（78）- 72

// https://leetcode.cn/problems/subsets/
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> subsets(int[] nums) {
        process(nums, 0);
        return result;
    }
    public void process(int[] nums, int start){
        // 每更新一次list，都加入结果集  首次进来加的是空集（把所有节点都记录下来，就是要求的子集集合）
        result.add(new ArrayList<>(path));
        // 到数组末尾结束当前递归
        if(start == nums.length){
            return;
        }
        for(int i = start; i < nums.length; i++){
            path.add(nums[i]);
            process(nums, i+1);
            path.remove(path.size() - 1);
        }
    }
    public List<List<Integer>> subsets1(int[] nums) {
        // 首先将空集加入解集中
        result.add(new ArrayList<Integer>()); 
        for(int i = 0; i < nums.length; i++){
            // 当前子集数
            int size = result.size(); 
            for(int j = 0; j < size; j++){ 
                // 拷贝所有子集
                List<Integer> newList = new ArrayList<>(result.get(j));
                // 向拷贝的子集中加入当前数形成新的子集
                newList.add(nums[i]); 
                // 向lists中加入新子集
                result.add(newList); 
            }
        }
        return result;
    }
}

子集 II（90）- 4

// https://leetcode.cn/problems/subsets-ii/
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列
// 输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        process(nums, 0);
        return result;
    }
    public void process(int[] nums, int start){
        result.add(new ArrayList<>(path));
        // 终止条件，可以不添加
        if(start >= nums.length){
            return;
        }
        // i必须从start开始进行剪枝，否则运行会超过内存限制
        for(int i = start; i < nums.length; i++){
            // 去重，此处就体现了首先对nums排序的重要性
            if(i > start && nums[i] == nums[i-1]) continue;
            path.add(nums[i]);
            process(nums, i+1);
            path.remove(path.size()-1);
        }
    }
}

排列

全排列（46）- 178

// https://leetcode.cn/problems/permutations/
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
// 输入：nums = [1,2,3]
// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> permute(int[] nums) {
        process(nums);
        return result;
    }
    public void process(int[] nums){
        // 此处不要加终止条件，根据纵向递归判断终止条件
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
        }
        // 纵向递归：有终止条件
        for(int i = 0; i < nums.length; i++){
            // path中已存在，则跳过
            if(path.contains(nums[i])) continue;   
            path.add(nums[i]);
            process(nums);
            path.remove(path.size()-1);
        }
    }
}

0 - 全排列II（47）- 33

// https://leetcode.cn/problems/permutations-ii/
// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列
// 
// 输入：nums = [1,1,2]
// 输出：
// [[1,1,2], [1,2,1], [2,1,1]]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 方式一：将nums排序，后续判断nums[i] == nums[i-1]
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        process(nums, used);
        return result;
        // 方式二：对最终的结果进行排序
        // return result.stream().distinct().collect(Collectors.toList());
    }
    public void process(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
        }
        for(int i = 0; i < nums.length; i++){
            // 当前元素被使用过 或者 （当前元素与上一元素相同 同时 上一元素未被使用过），则跳过此次循环
            // !used[i-1]也可以使用成used[i-1]，不过效率要降低
            if(used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
            path.add(nums[i]);
            used[i] = true;
            process(nums, used);
            used[i] = false;
            path.remove(path.size()-1);
        }
    }
}

棋盘问题

解数独（37）- 17

// https://leetcode.cn/problems/sudoku-solver/description/
// 编写一个程序，通过填充空格来解决数独问题。
// 数独的解法需遵循如下规则：
//     数字 1-9 在每一行只能出现一次。
//     数字 1-9 在每一列只能出现一次。
//     数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
//     数独部分空格内已填入了数字，空白格用 '.' 表示
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
    public boolean dfs(char[][] board){
        //【1】遍历二维棋盘
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                //【2】跳过原始数字
                if(board[i][j] != '.') continue;    
                //【3】在位置(i, j)放入数字k，检查棋盘是否合法
                for(char k = '1'; k <= '9'; k++){
                    //【3.1】若合法，则将数字k放入当前位置，并递归遍历
                    if(isValidSudoku(board, i, j, k) ){
                        board[i][j] = k;
                        //【3.2】递归遍历，此时当前位置及其前面空位都已经放入数字，在遍历时会跳过，所以此处不需要移动当前位置i、j
                        // 找到一组合适的数字，表示从当前位置放入k开始，后续所有空位都能放入合适数字
                        if(dfs(board)){ 
                            return true;
                        }
                        //【3.3】回溯操作，未找到一组合适的数字，要撤销当前位置的k，重新赋值
                        board[i][j] = '.';  
                    }
                }
                //【4】9个数字均尝试一遍放入当前位置，都未找到一组合适的数字，返回false，相当于回溯操作，结束当层递归，上一个空位置重新赋值
                return false;
            }
        }
        //【5】遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }
    // 在位置(row, col)放入数字value，检查棋盘是否合法
    public boolean isValidSudoku(char[][] board, int row, int col, char value){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == value){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == value){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == value){
                    return false;
                }
            }
        }
        return true;
    }
}

N皇后（51）- 15

// https://leetcode.cn/problems/n-queens/description/
// 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
// 输入：n = 4
// 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
// 解释：如上图所示，4 皇后问题存在两个不同的解法。
class Solution {
    List<List<String>> result = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        //【1】初始化n*n的棋盘
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(chessboard, n, 0);
        return result;
    }
    public void backTrack(char[][] chessboard, int n, int rowStart) {
        //【2】递归终止条件：遍历到末尾行，将解法(path)加入结果集
        if (rowStart == n) {
            result.add(ArrayToList(chessboard));
            return;
        }
        //【3】遍历每列
        for (int col = 0; col < n; col++) {
            //【4】判断当前位置放入皇后是否合法
            if (isValid (chessboard, rowStart, col, n)) {
                chessboard[rowStart][col] = 'Q';         // 放置皇后
                backTrack(chessboard, n, rowStart + 1);  // 向下一行递归遍历   
                chessboard[rowStart][col] = '.';         // 回溯，撤销皇后
            }
        }
    }
    //【5】字符数组 转换 为字符串集合
    public List ArrayToList(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
    //【6】在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用检查行进行去重
    public boolean isValid(char[][] chessboard, int row, int col, int n) {
        // 检查列是否有皇后
        for (int i = 0; i < row; i++) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线是否有皇后
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线是否有皇后
        for (int i = row-1, j = col+1; i >= 0 && j <= n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

其他

22222 - 重新安排行程（332）

递增子序列（491）- 2

// https://leetcode.cn/problems/non-decreasing-subsequences/description/
// 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
// 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return result;
    }
    public void backtracking (int[] nums, int start) {
        //【1】终止条件，只要满足path长度大于等于2，就加入结果集
        if (path.size() >= 2) {
            result.add(new ArrayList<>(path));
        }
        //【2】使用used数组来进行去重操作，题目说数值范围[-100, 100]
        //     数值范围元素均加100，转化为used数组的下标，[-100+100, 100+100] -> [0, 200]
        int[] used = new int[201];
        //【3】横向遍历数组
        for (int i = start; i < nums.length; i++) {
            //【4】剪枝操作：
            // 当前元素 小于 path中最后一个元素，表明当前元素针对path不是一个递增的数
            // used[nums[i] + 100] == 1表示当前元素已经被使用过了
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                    (used[nums[i] + 100] == 1)) continue;
            //【5】记录当前元素在本层已使用，本层后面就不能再使用
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            //【6】纵向递归遍历
            backtracking(nums, i + 1);      
            path.remove(path.size() - 1);   // 回溯
        }
    }
}

单词搜索（79）- 36

// https://leetcode.cn/problems/word-search/description/?favorite=2cktkvj
// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
// 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
// 输出：true
class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // 若board数组当前位置元素 与 word的首个字符相等，才需要进行下一步判断
                if (board[i][j] == word.charAt(0)) {
                    // board数组从当前位置出发、通过上下左右搜索，能否搜索到word从下标0开始的整个字符串
                    // 若能够搜索到word，则直接返回true，结束循环；若根据当前位置未搜索到word，则继续循环
                    if (dfs(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    // 返回值表示board数组从当前位置出发、通过上下左右搜索，能否搜索到word从当前下标元素至末尾的子字符串
    public boolean dfs(char[][] board, int i, int j, String word, int index) {
        //【1】递归终止条件1：word中所有单词均被搜索到
        if (index == word.length()) {
            return true;
        }
        //【2】递归终止条件2：board数组越界
        if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
            return false;
        }
        //【3】递归终止条件3：word当前索引元素 与 board数组中当前位置元素不相等
        if (word.charAt(index) != board[i][j]) {
            return false;
        }
        char temp = board[i][j];
        //【4】将当前位置元素置为'0'，防止在递归过程中被重复使用
        board[i][j] = '0';
        //【5】从当前位置上下左右递归遍历，搜索word下一索引元素
        boolean res = dfs(board, i-1, j, word, index+1) || dfs(board, i+1, j, word, index+1) || 
                      dfs(board, i, j-1, word, index+1) || dfs(board, i, j+1, word, index+1);
        //【6】在递归完成后需要恢复board[i][j]的值，不然从其他节点出发经过该节点时，值为'0'而造成错误判断           
        board[i][j] = temp;
        return res;
    }
}

双指针法

移除元素（27）- 4

// https://leetcode.cn/problems/remove-element/
// 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度
// 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组
// 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
// 输入：nums = [0,1,2,2,3,0,4,2], val = 2
// 输出：5, nums = [0,1,4,0,3]
// 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for(int rigth = 0; rigth < nums.length; rigth++){
            if(nums[rigth] != val){
                nums[left] = nums[rigth];
                left++;
            }
        }
        return left;
    }
}

反转字符串（344）- 17

// https://leetcode.cn/problems/reverse-string/
// 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出
// 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
// 输入：s = ["h","e","l","l","o"]
// 输出：["o","l","l","e","h"]
// 输入：s = ["H","a","n","n","a","h"]
// 输出：["h","a","n","n","a","H"]
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

2 - 反转字符串 II（541）- 2

// https://leetcode.cn/problems/reverse-string-ii/description/
// 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
// 如果剩余字符少于 k 个，则将剩余字符全部反转。
// 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
// 输入：s = "abcdefg", k = 2
// 输出："bacdfeg"
class Solution {
    public String reverseStr(String s, int k) {
        int len =s.length();
        // 将字符串变为字符数组，方便当个字符遍历
        char[] chars= s.toCharArray();
        for(int left = 0; lef t< len; left += 2*k){
            // 左指针是为了定义反转位置的开始，右指针定义反转位置的结束。
            // 特别备注下，这边的Math.min()起到的作用是，字符小于k时，全部反转的小姑。
            // 当k>len的时候，就取len。
            // 例如；“a” 4。这种情况就rigth不能取4，应该取1。
            reverse(chars, left, Math.min(left+k, len)-1);
        }
        // 返回结果
        return new String(chars);
    }
    public void reverse(char[] chars, int left, int rigth){
        // 只要左指针小于右指针就反转
        // 这边是为了兼容处理 k > len情况下，将所有字符都反转
        while(left < rigth){
            char temp = chars[left];
            chars[left] =chars[rigth];
            chars[rigth] = temp;
            // 左指针向右移动
            left++;
            // 右指针向左移动
            rigth--;
        }
    }
}

替换空格（剑指 Offer 05）- 4

// https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
// 请实现一个函数，把字符串 s 中的每个空格替换成"%20"
// 输入：s = "We are happy."
// 输出："We%20are%20happy."
class Solution {
    public String replaceSpace(String s) {
        StringBuilder string = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == ' '){
                string.append("%20");
            } else {
                string.append(c);
            }
        }
        return string.toString();
        // 直接调用API
        // return s.replace(" ", "%20");
    }
}

反转字符串中的单词 III（557）- 17

// https://leetcode.cn/problems/reverse-words-in-a-string-iii/
// 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序
// 输入：s = "Let's take LeetCode contest"
// 输出："s'teL ekat edoCteeL tsetnoc"
class Solution {
    public String reverseWords(String s) {
        StringBuffer result = new StringBuffer();
        int i = 0;
        while (i < s.length()) {
            int start = i;
            while (i < s.length() && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                result.append(s.charAt(start + i - 1 - p));
            }
            while (i < s.length() && s.charAt(i) == ' ') {
                i++;
                result.append(' ');
            }
        }
        return result.toString();
    }
    public String reverseWords1(String s) {
        String[] split = s.split(" ");
        for (int i = 0; i < split.length; i++) {
            split[i] = new StringBuffer(split[i]).reverse().toString();
        }
        return String.join(" ", split);
    }
}

反转链表（206）- 529

// https://leetcode.cn/problems/reverse-linked-list/
// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
// 输入：head = [1,2,3,4,5]
// 输出：[5,4,3,2,1]
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2 - 反转链表 II（92）- 151

// https://leetcode.cn/problems/reverse-linked-list-ii/
// 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
// 输入：head = [1,2,3,4,5], left = 2, right = 4
// 输出：[1,4,3,2,5]  
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 重新设置头节点
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        // pre最终指向left上一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // cur指向left节点
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            // 下移指针
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}