回溯

1、组合

https://leetcode.cn/problems/combinations/description/

回溯的返回值一般都是void，还有 注意for循环的开始值，不能每次都从集合的第一数值开始。

第二需要注意的是：

不能写成 result.add(list)

因为在 Java 中，ArrayList 和 LinkedList 都是基于引用的。当你直接将 path 添加到 result 中时，实际上添加的是 path 对象的引用，而不是它的当前状态。如果你在递归中对 path 进行修改，那么 result 中存储的所有引用都会被影响，最终 result 中的所有组合会指向同一个 path 对象。

为了避免这个问题，你需要在每次将 path 添加到 result 时，使用 new ArrayList<>(path) 创建 path 的副本。这会确保即使你后续修改了 path，result 中保存的列表内容不会改变。

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

        combine1(n,k,1);
        return result;
    }
    public void combine1(int n ,int k,int start){
        if(list.size()==k){
            result.add(new ArrayList(list));
            return;
        }

        for(int i=start;i<=n;i++){
            list.add(i);
            combine1(n,k,i+1);
             list.removeLast();
        }
        return;
    
}}

剪枝优化版本

剪枝那就需要从for循环入手

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

        combine1(n,k,1);
        return result;
    }
    public void combine1(int n ,int k,int start){
        if(list.size()==k){
            result.add(new ArrayList(list));
            return;
        }

        for(int i=start;i<=n-(k-list.size())+1;i++){
            list.add(i);
            combine1(n,k,i+1);
             list.removeLast();
        }
        return;
    
}}

2、组合Ⅲ

https://leetcode.cn/problems/combination-sum-iii/description/

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list=new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
            int sum=0;
            combinationSum1(k,n,1,sum);
            return result;
    }

    public void combinationSum1(int k,int n,int start,int sum){
        if(sum==n&&list.size()==k){
            result.add(new ArrayList(list));
            return;
        }
        if (sum > n || list.size() > k) {
            return;
        }
        for(int i=start;i <= 9 - (k - list.size()) + 1;i++){
            sum+=i;
            list.add(i);
            combinationSum1(k,n,i+1,sum);
             list.removeLast();
             sum-=i;
        }
    }
} 

3、电话号码的字母组合（注意）

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

class Solution {
    List<String> result =new LinkedList<>();
    StringBuilder  s=new StringBuilder();
    Map<Integer,String> map=new HashMap<>();
    public void addmap(){
    map.put(0,"");
    map.put(1,"");
    map.put(2,"abc");
    map.put(3,"def");
    map.put(4,"ghi");
    map.put(5,"jkl");
    map.put(6,"mno");
    map.put(7,"pqrs");
    map.put(8,"tuv");
    map.put(9,"wxyz");
    }
   
    public List<String> letterCombinations(String digits) {
         if (digits == null || digits.length() == 0) {
            return result;  // 处理空输入
        }
        addmap();
        letterCombination(digits,0);
        return result;
    }
    public void letterCombination(String digits,int index){
        if(index==digits.length()){
            result.add(s.toString());
            return;
        }
        int num = digits.charAt(index) - '0';  // 将字符转换为对应的数字
        String s1 = map.get(num);              // 获取对应数字的字母组合
        int size = s1.length();
        for(int i=0;i<size;i++){
            s.append(s1.charAt(i));
            letterCombination(digits,index+1);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

map 的操作和StringBulider 这些基本的 操作不熟悉

还有就是 刚开始我想的是 for循环，但是这个for循环层数不受我控制，所以看了讲解，回溯就是用来解决for循环问题的。

4、组合问题

https://leetcode.cn/problems/combination-sum/description/

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> list=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        combinationSum1(candidates,target,0);
        return result;
    }

    public void combinationSum1(int[] candidates, int target,int index){
        if(target==0)
        {
            result.add(new ArrayList(list));
            return;
        }       if (target < 0) {
            return; // 目标小于0，返回
        }

        for(int i=index;i<candidates.length;i++){
            list.add(candidates[i]);
            target-=candidates[i];
            combinationSum1(candidates,target,i);
            list.removeLast();
            target+=candidates[i];
        }
    }
}

5、组合总和II（剪枝需要注意）

https://leetcode.cn/problems/combination-sum-ii/description/

class Solution {
   List<List<Integer>> result=new ArrayList<>();
    List<Integer> list=new LinkedList<>();
    boolean[] used; // 改为 boolean 类型
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先排序以处理重复元素
        used = new boolean[candidates.length]; // 根据候选数组的长度初始化
        backTracking(candidates,target,0);
    
        return result;
    }

    public void backTracking(int[] candidates, int target,int index){
        if(target==0)
        {
            result.add(new ArrayList(list));
            return;
        }       
        if (target < 0) {
            return; // 目标小于0，返回
        }

        for(int i=index;i<candidates.length;i++){
            if(i>0&&candidates[i-1]==candidates[i]&&!used[i-1]){
                continue;
            }
//注意要有!used[i-1] 因为如果前一个是1 证明是在从上往下，此时是可以重复的 有重复元素
            list.add(candidates[i]);
            used[i] = true; // 标记为已使用
            target-=candidates[i];
            backTracking(candidates,target,i+1);
            list.removeLast();
            target+=candidates[i];
            used[i]=false;
        }
    }
}

6 、分割回文串（难）

https://leetcode.cn/problems/palindrome-partitioning/description/

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> cur = new ArrayList<>();
    
    public List<List<String>> partition(String s) {
        backtracking(s, 0,new StringBuilder());
        return result;
    }
    
    public void backtracking(String s, int index,StringBuilder sb) {
        if (index == s.length()) {
            // 注意创建一个新的copy
            result.add(new ArrayList<>(cur));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (ischeck(sb)) {
                cur.add(sb.toString());
                backtracking(s, i + 1,new StringBuilder());
                cur.remove(cur.size() - 1);
            }
        }
    }
    
    public boolean ischeck(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

7、复原IP地址

https://leetcode.cn/problems/restore-ip-addresses/description/

①使用String

class Solution {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return result; // 算是剪枝了
        backTrack(s, 0, 0);
        return result;
    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void backTrack(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 逗点数量为3时，分隔结束
            // 判断第四段⼦字符串是否合法，如果合法就放进result中
            if (isValid(s,startIndex,s.length()-1)) {
                result.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个逗点
                pointNum++;
                backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
                pointNum--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
            } else {
                break;
            }
        }
    }

    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }


}

①使用StringBuilder

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return result;
    }
    private void backTracking(StringBuilder s, int startIndex, int dotCount){
        if(dotCount == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s.toString());
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    //[start, end]
    private boolean isValid(StringBuilder s, int start, int end){
        if(start > end)
            return false;
        if(s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255)
                return false;
        }
        return true;
    }
}

③StringBuilder常用方法

1. 构造方法

StringBuilder()

• 说明：创建一个空的 StringBuilder，其初始容量为 16 个字符。

示例：

StringBuilder sb = new StringBuilder();

2、追加

append() 可以追加一个字符串，基本数据类型，字符数组或者其他的Stringbuilder等。

3、插入方法 (insert 系列)

insert(int offset, boolean b)

• 说明：在指定位置插入 boolean 值。

sb.insert(5, true);

insert(int offset, char c)

• 说明：在指定位置插入字符。

sb.insert(2, 'B');

insert(int offset, int i)

• 说明：在指定位置插入整数。

sb.insert(3, 100);

insert(int offset, long l)

• 说明：在指定位置插入长整数。

sb.insert(4, 1000L);

insert(int offset, float f)

• 说明：在指定位置插入浮点数。

sb.insert(1, 2.5f);

insert(int offset, double d)

• 说明：在指定位置插入双精度浮点数。

sb.insert(6, 3.14159);

insert(int offset, char[] str)

• 说明：在指定位置插入字符数组。

char[] chars = {'J', 'a', 'v', 'a'}; sb.insert(0, chars);

insert(int offset, String str)

• 说明：在指定位置插入字符串。

sb.insert(5, " Inserted ");

insert(int offset, CharSequence s)

• 说明：在指定位置插入 CharSequence。

CharSequence cs = " Seq "; sb.insert(3, cs);

insert(int offset, StringBuffer sb)

• 说明：在指定位置插入 StringBuffer 的内容。

StringBuffer stringBuffer = new StringBuffer(" Buffer "); sb.insert(2, stringBuffer);

4、删除和替换方法

delete(int start, int end)

• 说明：删除从 start 到 end（不包括 end）之间的字符。

sb.delete(2, 5);

deleteCharAt(int index)

• 说明：删除指定位置的字符。

sb.deleteCharAt(3);

replace(int start, int end, String str)

• 说明：用指定的字符串替换从 start 到 end（不包括 end）之间的字符。

sb.replace(1, 4, "XYZ");

reverse()

• 说明：将 StringBuilder 中的字符序列反转。

sb.reverse();

setCharAt(int index, char ch)

• 说明：设置指定位置的字符为给定字符。

sb.setCharAt(2, 'Z');

5、查询和获取方法

length()

• 说明：返回当前字符序列的长度。

int len = sb.length();indexOf(String str)

• 说明：返回第一次出现指定子字符串的索引，如果未找到则返回 -1。

int index = sb.indexOf("World");

indexOf(String str, int fromIndex)

• 说明：从指定位置开始，返回第一次出现指定子字符串的索引，如果未找到则返回 -1。

int index = sb.indexOf("a", 5);charAt(int index)

• 说明：返回指定位置的字符。

char c = sb.charAt(1);

8、子集

https://leetcode.cn/problems/subsets/description/

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return result;
    }
    public void backtracking(int[] nums,int start)
{
    result.add(new ArrayList<>(path));
 if (start >= nums.length){ //终止条件可不加
            return;
        }
    for(int i=start;i<nums.length;i++){
        path.add(nums[i]);
        backtracking(nums,i+1);
        path.remove(path.size()-1);
    }

}}

刚开始在 add 时添加了 1==1

if(1==1){
result.add(new ArrayList<>(path));
return;}

的条件 导致结果不会像后执行 直接return 结果只有[]

9、子集Ⅱ

https://leetcode.cn/problems/subsets-ii/description/

class Solution {
        List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length]; // 正确的初始化方式
            Arrays.sort(nums); // 排序，以便后续去重
            backtracking(nums,0);
        return result;
    }

      public void backtracking(int[] nums,int start)
{
    result.add(new ArrayList<>(path));
    if (start >= nums.length){ //终止条件可不加
            return;
        }
    for(int i=start;i<nums.length;i++){
        if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
        continue;
        used[i]=true;
        path.add(nums[i]);
        backtracking(nums,i+1);
        path.remove(path.size()-1);
        used[i]=false;
    }
    }
}

和第五题很像，但是我boolean 赋初值的方法写错了 写成了()

还有就是忘记排序了

以及应该是i>0，我写成了start>0;

10、非递减子序列(注意)

https://leetcode.cn/problems/non-decreasing-subsequences/description/

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) {
        if (path.size() >= 2) {
            result.add(new ArrayList<>(path));
        }
        //用来防止每一层取相同元素，而不是不同层
        HashSet<Integer> hash=new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            // 确保当前元素大于等于路径最后一个元素
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)||hash.contains(nums[i])) {
                continue;
            }
            hash.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        
        }
    }
}

注意这里的剪枝操作，是同一层上不取相同的，不是不同层不能取相同的

11、全排列

https://leetcode.cn/problems/permutations/description/

class Solution {
        List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
        boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length]; // 正确的初始化方式
  backtracking(nums);
        return result;
    }

     public void backtracking(int[] nums) {
        if (path.size() ==nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(used[i])
            continue;
            used[i]=true;
            path.add(nums[i]);
            backtracking(nums);
            path.remove(path.size() - 1);
            used[i]=false;
        
        }
    }
}

这里我刚开始只想到了从0开始，但是就会导致，每次都会一个位置取几次，所以应该有一个标志，判断是否已经添加过该位置的元素。

12 、全排列Ⅱ

https://leetcode.cn/problems/permutations-ii/description/

class Solution {
       List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
        boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length]; // 正确的初始化方式
    Arrays.sort(nums);
  backtracking(nums);
        return result;
    }
  public void backtracking(int[] nums) {
        if (path.size() ==nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]||(i>0&&nums[i]==nums[i-1]&&used[i-1]==false))
            continue;
            used[i]=true;
            path.add(nums[i]);
            backtracking(nums);
            path.remove(path.size() - 1);
            used[i]=false;
        
        }
    }
}

13、重新安排行程

记得反转

class Solution {
    Map<String,PriorityQueue<String>> map=new HashMap<String,PriorityQueue<String>>();
    List<String> res=new LinkedList<String>();


    public List<String> findItinerary(List<List<String>> tickets) {
        for(List<String> ticket:tickets){
            String src=ticket.get(0);
            String des=ticket.get(1);
            if(!map.containsKey(src)){
                map.put(src,new PriorityQueue<String>());
            }
            map.get(src).offer(des);
        }

        dfs("JFK");
        Collections.reverse(res);
        return res;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        res.add(curr);
    }
}

map方法

Map 接口的实现类包括 HashMap、TreeMap 和 LinkedHashMap 等。以下是一些常用方法：

• 创建 Map 实例

  java

  复制代码

  Map<String, Integer> map = new HashMap<>();

• 添加元素

  java

  复制代码

  map.put("key1", 1); // 将键值对放入 Map

• 获取元素

  java

  复制代码

  Integer value = map.get("key1"); // 根据键获取值

• 删除元素

  java

  复制代码

  map.remove("key1"); // 根据键删除元素

• 检查键或值是否存在

  java

  复制代码

  boolean hasKey = map.containsKey("key1"); // 检查键是否存在 boolean hasValue = map.containsValue(1); // 检查值是否存在

• 获取所有键或值

  java

  复制代码

  Set<String> keys = map.keySet(); // 获取所有键 Collection<Integer> values = map.values(); // 获取所有值

• 获取键值对集合

  java

  复制代码

  Set<Map.Entry<String, Integer>> entries = map.entrySet(); // 获取键值对的集合

• 清空 Map

  java

  复制代码

  map.clear(); // 清空 Map

• 获取 Map 的大小

  java

  复制代码

  int size = map.size(); // 获取 Map 的元素个数 List 接口

list方法

List 接口的实现类包括 ArrayList、LinkedList 和 Vector 等。以下是一些常用方法：

• 创建 List 实例

  java

  复制代码

  List<String> list = new ArrayList<>();

• 添加元素

  java

  复制代码

  list.add("element1"); // 在列表末尾添加元素 list.add(0, "element2"); // 在指定索引位置添加元素

• 获取元素

  java

  复制代码

  String element = list.get(0); // 根据索引获取元素

• 删除元素

  java

  复制代码

  list.remove("element1"); // 根据元素值删除 list.remove(0); // 根据索引删除

• 检查元素是否存在

  java

  复制代码

  boolean contains = list.contains("element1"); // 检查元素是否存在

• 获取列表大小

  java

  复制代码

  int size = list.size(); // 获取列表的元素个数

• 清空列表

  java

  复制代码

  list.clear(); // 清空列表

• 获取子列表

  java

  复制代码

  List<String> subList = list.subList(0, 2); // 获取从索引0到2的子列表

• 遍历 List

  java

  复制代码

  for (String item : list) { System.out.println(item); // 使用增强 for 循环遍历 }示例代码

14、n皇后问题

https://leetcode.cn/problems/n-queens/description/

class Solution {
    List<List<String>> res =new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard=new char[n][n];
        for(char[] c:chessboard){
            Arrays.fill(c,'.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }
//row 代表到第几行了
    public void backTrack(int n,int row,char[][] chessboard){
        if(row==n){
            res.add(addList(chessboard));
        }
//相当于全排列 每次从0开始
        for(int i=0;i<n;i++){
            if(isVAalid(n,row,i,chessboard)){
                chessboard[row][i]='Q';
                backTrack(n,row+1,chessboard);
                chessboard[row][i]='.';
            }
        }
    }

     public List addList(char[][] chessboard) {
        List<String> list = new ArrayList<>();
//把字符数组转为字符串
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
//检查合法性
    public boolean isVAalid(int n,int row,int col,char[][] chessboard){
        for(int i=0;i<row;i++){
            if(chessboard[i][col]=='Q'){
                return false;
            }
        }

        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
             if(chessboard[i][j]=='Q'){
                return false;
            }
        }

         for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++){
             if(chessboard[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}

String.copyValueOf 和 String.valueOf 都可以将字符数组转换为字符串，但它们在语义上有所不同：

• String.copyValueOf(char[] data) 强调“复制”字符数组的内容到新字符串。

• String.valueOf(char[] data) 更加通用，表示将字符数组的“值”转换为字符串。

在大多数情况下，这两个方法的功能是相同的，选择使用哪一个主要取决于个人偏好或代码的可读性。

char[] chars = {'H', 'i'};
String str1 = String.copyValueOf(chars);
String str2 = String.valueOf(chars);
System.out.println(str1);  // 输出: Hi
System.out.println(str2);  // 输出: Hi

15、解数独

https://leetcode.cn/problems/sudoku-solver/description/
因为只要有一个结果就可以了，所以回溯函数的返回值是boolean

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                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] == val){
                    return false;
                }
            }
        }
        return true;
    }
}