[数据结构与算法]LeetCode-回溯

矩阵中的路径

package huisu;

public class Solution_01 {
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(rows == 0 || cols == 0) return false;
        char[][] matrix2 = new char[rows][cols];
        int index = 0;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                matrix2[i][j] = matrix[index++];
            }
        }
        //用于标记是否访问过
        int[][] flag = new int[rows][cols];
        //首先对于matrix中的每一个都可能是起点，需要遍历。
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(process(matrix2, flag, str, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean process(char[][] matrix, int[][] flag, char[] str, int m, int n, int a){
        int row = matrix.length;
        int col = matrix[0].length;
        if(flag[m][n] == 0 && matrix[m][n] == str[a]){
            if(a == str.length - 1){
                return true;
            }else{
                flag[m][n] = 1;
                if(m > 0 &&process(matrix, flag, str, m - 1, n, a + 1)) 
                    return true;
                if(m < row - 1 && process(matrix, flag, str, m + 1, n, a+ 1)) 
                    return true;
                if(n > 0 && process(matrix, flag, str, m, n - 1, a + 1)) 
                    return true;
                if(n < col - 1 && process(matrix, flag, str, m, n + 1, a + 1)) 
                    return true;
                //至关重要的一步，该分支失败，需要将该元素标记为未访问过。
                flag[m][n] = 0;
                return false;
            }
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        String string = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";
        char[] matrix = string.toCharArray();
        String string2 = "SGGFIECVAASABCEHJIGQEM";
        char[] str = string2.toCharArray();
        System.out.println(hasPath(matrix, 5,8, str));
    }
}

ip地址划分

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

public class Solution_93 {
    public static List<String> restoreIpAddresses(String s) {
        List<String> lists = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        doRestore(0, sb, lists, s);
        return lists;
    }

    /**
     * 回溯函数：每次处理得到ip地址的一部分，将得到的这一部分加到tempAddress后面
     * @param k:ip地址可以分为四部分，求出ip地址的第k个部分
     * @param tempAddress：当前求得的ip地址，当k=4时，tempAddress为完整的ip地址
     * @param lists：将正确的ip地址放入lists中
     * @param s：从s中取最多三个字符组成ip地址的一部分，要求取出的字符小于255且开头不能为0
     */
    public static void doRestore(int k, StringBuilder tempAddress, List<String> lists, String s){
        //有可能s的长度一开始就不够12位，比如说时3位，计算第一部分时，把其全囊括进去了，s的长度就为0了。所以判断条件必须是两个
        if(k == 4 || s.length() == 0){
            if( k == 4 && s.length() == 0){
                lists.add(tempAddress.toString());
            }
            return;
        }
        for(int i = 0; i < s.length() && i <= 2; i++){//遍历三次，每次取s的前i+1个字符，当成ip的一部分
            if(i != 0 && s.charAt(0) == '0'){//ip地址的某部分可以为0，但是不能有前缀0；某部分也可以为0值
                break;
            }
            String temp = s.substring(0, i + 1);
            if(Integer.parseInt(temp) <= 255){
                if(k != 0){//ip地址除了第一部分前面不加'.'，其余都加.
                    temp = "." + temp;
                }
                tempAddress.append(temp);
                doRestore(k + 1, tempAddress, lists, s.substring(i + 1));
                //StringBuilder delete(int start, int end)左闭右开
                tempAddress.delete(tempAddress.length() - temp.length(), tempAddress.length());
            }
        }
    }

    public static void main(String[] args) {
        String s = "25525511255";
        List<String> lists = restoreIpAddresses(s);
        System.out.println(lists.toString());
    }
}

电话号码的字母组合

17. 电话号码的字母组合

盲区：在类中定义一个map集合，并填充。

package digui;

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

public class Solution_17 {

    public static HashMap<String, String> map = new HashMap<String, String>(){
        {
            put("2", "abc");
            put("3", "def");
            put("4", "ghi");
            put("5", "jkl");
            put("6", "mno");
            put("7", "pqrs");
            put("8", "tuv");
            put("9", "wxyz");
        }
    };

    public static List<String> lists = new ArrayList<>();

    public static List<String> letterCombinations(String digits) {
        lists.clear();
        if(digits.length() != 0){
            backtrack("", digits);
        }
        return lists;
    }

    public static void backtrack(String combination, String digits){
        if(digits.length() == 0){
            lists.add(combination);
        }else{
            String digit = digits.substring(0, 1);
            String letters = map.get(digit);
            for(int i = 0; i < letters.length(); i++){
                backtrack(combination + letters.charAt(i), digits.substring(1));
            }
        }
    }

    public static void main(String[] args) {
        String digits = "";
        lists = letterCombinations(digits);
        for(String s : lists){
            System.out.println(s);
        }
    }
}

括号生成

22. 括号生成

class Solution {
    public static List<String> lists = new ArrayList<>();
    public static List<String> generateParenthesis(int n) {
        lists.clear();
        function("",0, n, n);
        return lists;
    }

    public static void function(String sub, int score, int left, int right){
        if(score == 0 && left == 0 && right == 0){
            lists.add(sub);
        }else{
            if(score == 0){
                function(sub + "(", 1, left - 1, right);
            }else if(score > 0){
                if(left > 0){
                    function(sub + "(", score + 1, left - 1, right);
                }
                function(sub + ")", score - 1, left, right - 1);
            }
        }
    }
}

组合总和

39. 组合总和

需要注意：结果中不能出现重复的链表，需要对过程进行剪枝。

先对数组排序，也能剪枝。

import java.util.*;

public class Solution_39 {
    static List<List<Integer>> results = new ArrayList<>();
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        results.clear();
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        dfs(candidates, 0, list, target);
        return results;
    }

    private static void dfs(int[] candidates, int start, List<Integer> list, int target) {
        if(target == 0){
            results.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            //由于数组已经排好序，只需遍历数组前面符合条件的元素。
            if(target - candidates[i] >= 0){
                list.add(candidates[i]);
                //下一次递归需要从当前位置开始遍历，而不是从数组首部开始遍历。
                //这样的话，加入链表中的元素是非递减的。所以就不会出现重复的结果
                dfs(candidates, i, list, target - candidates[i]);
                list.remove(list.size() - 1);
            }else{
                break;
            }
        }
    }
}