LeetCode刷题笔记——HOT100面试题（7）

回溯法

17. 电话号码的字母组合

class Solution {

    public String[] strs = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> res;
    public StringBuilder sb;

    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits.length()==0) return res;
        sb = new StringBuilder();
        dfs(digits, 0);
        return res;
    }

    public void dfs(String digits, int i) {
        if (i==digits.length()) {
            res.add(sb.toString());
            return;
        }
        int num = digits.charAt(i) - '0';
        String str = strs[num];
        for (int j=0; j<str.length(); j++) {
            sb.append(str.charAt(j));
            dfs(digits, i+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

22. 括号生成

用字符串容器中已有的左括号和右括号的数量来控制深度搜索的分支和出口。

class Solution {

    public List<String> res;
    public StringBuilder sb;
    public int N;

    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        sb = new StringBuilder();
        N = n;
        dfs(0, 0);
        return res;
    }

    public void dfs(int left, int right) {
        if (sb.length()==2*N) {
            res.add(sb.toString());
            return;
        }
        if (left<N) {
            sb.append("(");
            dfs(left+1, right);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right<left) {
            sb.append(")");
            dfs(left, right+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

39. 组合总和

对数组排序，防止出现重复的路径。

class Solution {

    public List<List<Integer>> res;
    public List<Integer> tmp;
    public int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        tmp = new ArrayList<>();
        Arrays.sort(candidates);
        this.candidates = candidates;
        dfs(target, 0);
        return res;
    }

    public void dfs(int sum, int i) {
        if (sum==0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int j=i; j<candidates.length; j++) {
            if (sum-candidates[j]<0) break;//提前剪枝
            tmp.add(candidates[j]);
            dfs(sum-candidates[j], j);
            tmp.remove(tmp.size()-1);
        }
    }
}

46. 全排列

全排列类问题，结果字符串需要包含所有的字符，因此要对字符串中每一个字符进行遍历。

class Solution {

    public List<List<Integer>> res;
    public List<Integer> tmp;
    public boolean[] used;
    public int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        tmp = new ArrayList<>();
        used = new boolean[nums.length];
        this.nums = nums;
        dfs();
        return res;
    }

    public void dfs() {
        if (tmp.size()==nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i=0; i<nums.length; i++) {
            if (used[i]) continue;
            tmp.add(nums[i]);
            used[i] = true;
            dfs();
            tmp.remove(tmp.size()-1);
            used[i] = false;
        }
    }
}

78. 子集

子集类问题，已经顺序访问过的字符无需再次访问，因此用一个偏移量来控制。

class Solution {

    public List<List<Integer>> res;
    public List<Integer> tmp;
    public int[] nums;
    public boolean[] used;

    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        tmp = new ArrayList<>();
        this.nums = nums;
        used = new boolean[nums.length];
        dfs(0);
        return res;
    }

    public void dfs(int i) {
        res.add(new ArrayList<>(tmp));
        if (i==nums.length) return;
        for (int j=i; j<nums.length; j++) {
            if (used[j]) continue;
            tmp.add(nums[j]);
            used[j] = true;
            dfs(j+1);
            tmp.remove(tmp.size()-1);
            used[j] = false;
        }
    }
}

79. 单词搜索

将已经搜索过的格点用#标记，防止重复进入。

class Solution {

    public char[][] board;
    public String word;
    int M;
    int N;
    
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.M = board.length;
        this.N = board[0].length;
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                boolean flag = dfs(i, j, 0);
                if (flag) return true;
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int i) {
        if (x<0 || y<0 || x>=M || y>=N || i==word.length()) return false;
        if (board[x][y]!=word.charAt(i)) return false;
        if (i==word.length()-1) return true;
        char t = board[x][y];
        board[x][y] = '#';
        boolean flag = dfs(x-1, y, i+1) || dfs(x+1, y, i+1) || dfs(x, y-1, i+1) || dfs(x, y+1, i+1);
        board[x][y] = t;
        return flag;
    }
}

200. 岛屿数量

以值为1的格点为起点进行深度搜索，把相连接的1变为0以防止重复进入，一次深度搜索后就“沉没”一个岛屿。统计“沉没”的岛屿的数量。

class Solution {

    char[][] grid;
    int M;
    int N;

    public int numIslands(char[][] grid) {
        this.grid = grid;
        this.M = grid.length;
        this.N = grid[0].length;
        int count = 0;
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                if (grid[i][j]=='1') {
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void dfs(int i, int j) {
        if (i<0 || j<0 || i>=M || j>=N) return;
        if (grid[i][j]!='1') return;
        grid[i][j] = '0';
        dfs(i-1, j);
        dfs(i+1, j);
        dfs(i, j-1);
        dfs(i, j+1);
    }
}

301. 删除无效的括号

先遍历数组，确定需要删除多少个'('和')'才能使字符串有效，然后深度搜索，直到删除的'('和')'达到数量要求。

class Solution {

    List<String> res = new ArrayList<>();
    StringBuilder sb;

    public List<String> removeInvalidParentheses(String s) {
        this.sb = new StringBuilder(s);
        int left = 0, right = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') left++;
            else if (s.charAt(i)==')') {
                if (left>0) left--;
                else right++;
            }
        }
        dfs(0, left, right);
        return res;
    }

    public void dfs(int index, int left, int right) {
        if (left==0 && right==0) {
            if (check()) res.add(sb.toString());
            return;
        }
        for (int i=index; i<sb.length(); i++) {
            // 去重
            if (i>index && sb.charAt(i)==sb.charAt(i-1)) continue;
            if (sb.charAt(i)=='(' && left>0) {
                sb.deleteCharAt(i);
                dfs(i, left-1, right);
                sb.insert(i, "(");
            }
            if (sb.charAt(i)==')' && right>0) {
                sb.deleteCharAt(i);
                dfs(i, left, right-1);
                sb.insert(i, ")");
            }
        }
    }

    public boolean check() {
        int count = 0;
        for (int i=0; i<sb.length(); i++) {
            if (sb.charAt(i)=='(') count++;
            else if (sb.charAt(i)==')') {
                if (count==0) return false;
                count--;
            }
        }
        return count==0;
    }
}

437. 路径总和 III

两层递归，①先序遍历，将每个节点作为DFS的起始节点；②深度优先搜索找到和为sum的路径。

class Solution {
    public int res = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root==null) return res;
        preOrder(root, sum);
        return res;
    }

    public void preOrder(TreeNode root, int sum) {
        if (root==null) return;
        preOrder(root.left, sum);
        dfs(root, sum-root.val);
        preOrder(root.right, sum);
    }

    public void dfs(TreeNode root, int sum) {
        if (sum==0) {
            res++;
        }
        if (root.left!=null) dfs(root.left, sum-root.left.val);
        if (root.right!=null) dfs(root.right, sum-root.right.val);
    }
}

图

207. 课程表

使用深度优先搜索判断图中是否存在环。courses[i]有三种状态，0为初始状态，1表示当前正在搜索这门课程，如果此次搜索再度访问到它说明存在环，返回false，-1表示该门课程搜索完毕且未发现环。

class Solution {
    int N;
    int[][] R;
    int[] courses;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        this.N = numCourses;
        this.R = prerequisites;
        this.courses = new int [N];
        for (int i=0; i<N; i++) {
            if (!dfs(i)) return false;
        }
        return true;
    }

    public boolean dfs(int i) {
        if (courses[i]==1) return false;
        if (courses[i]==-1) return true;
        courses[i] = 1;
        for (int[] requests: R) {
            if (requests[0]==i) {
                if (!dfs(requests[1])) return false;
            }
        }
        courses[i] = -1;
        return true;
    }
}

399. 除法求值

构造有向图，使用HashMap<String, List<Node>>存储所有节点，列表List<Node>存储与该节点相邻接的节点，同时记录它们之间的倍数关系。以每个问题的被除数作为深度优先搜索的起点，除数作为终点进行搜索，并且用一个set防止出现环。

class Solution {

    // 定义图的节点
    class Node {

        String id;
        double multiple;

        public Node(String id, double multiple) {
            this.id = id;
            this.multiple = multiple;
        }
    }

    HashMap<String, List<Node>> map;

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map = new HashMap<>();
        // 按照相除关系构造图
        for (int i=0; i<equations.size(); i++) {
            String dividend = equations.get(i).get(0);
            String divisor = equations.get(i).get(1);
            // 处理被除数
            List<Node> dividend_list = map.getOrDefault(dividend, new ArrayList<>());
            dividend_list.add(new Node(divisor, values[i]));
            map.put(dividend, dividend_list);
            // 处理除数，其与被除数的倍数为values[i]的倒数
            List<Node> divisor_list = map.getOrDefault(divisor, new ArrayList<>());
            divisor_list.add(new Node(dividend, 1./values[i]));
            map.put(divisor, divisor_list);
        }
        double[] res = new double[queries.size()];
        for (int i=0; i<queries.size(); i++) {
            String dividend = queries.get(i).get(0);
            String divisor = queries.get(i).get(1);
            res[i] = dfs(dividend, divisor, 1., new HashSet<>());
        }
        return res;
    }

    public double dfs(String dividend, String divisor, double multi, Set<String> set) {
        // 如果被除数不存在，或者已经遍历过（存在环），返回-1
        if (!map.containsKey(dividend) || set.contains(dividend)) {
            return -1.;
        }
        // 如果被除数等于除数，搜索结束，返回当前的倍数
        if (dividend.equals(divisor)) return multi;
        // 把当前被除数放入set，防止出现环
        set.add(dividend);
        // 深度搜索被除数的list
        for (Node node: map.get(dividend)) {
            double tmp = dfs(node.id, divisor, multi*node.multiple, set);
            if (tmp != -1.) return tmp;
        }
        return -1.;
    }
}