本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

模糊不清牛肉面

2101

文章

850363

访问

+关注

分类

暂无分类

日期归档

暂无数据

力扣刷题：DFS篇

发布于2021-05-30 20:13 阅读(1553) 评论(0) 点赞(14) 收藏(4)

112. 路径总和

题目介绍

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。

当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), list);
        return !list.isEmpty();
    }

    /**
     * 深度优先搜索匹配路径，从数根开始，向树叶方向搜索
     *
     * @param node   当前节点
     * @param remain 剩余数值
     * @param nums   用于保存搜索过的节点值
     * @param list   用于保存已匹配上的路径
     */
    private void dfs(TreeNode node, int remain, List<Integer> nums, List<List<Integer>> list) {
        if (node == null) return;
        nums.add(node.val);
        // 如果搜索到叶子节点，并且 remain 等于叶子节点的值，说明此路径匹配
        if (node.left == null && node.right == null && node.val == remain) {
            list.add(new ArrayList<>(nums));
        }
        // 深度优先搜索 node 节点的左子树
        dfs(node.left, remain - node.val, nums, list);
        // 深度优先搜索 node 节点的右子树
        dfs(node.right, remain - node.val, nums, list);
        // 回溯的时候需要删除最后一个数值
        nums.remove(nums.size() - 1);
    }
}

113. 路径总和 II

题目介绍

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。

当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), list);
        return list;
    }

    /**
     * 深度优先搜索匹配路径，从数根开始，向树叶方向搜索
     *
     * @param node   当前节点
     * @param remain 剩余数值
     * @param nums   用于保存搜索过的节点值
     * @param list   用于保存已匹配上的路径
     */
    private void dfs(TreeNode node, int remain, List<Integer> nums, List<List<Integer>> list) {
        if (node == null) return;
        nums.add(node.val);
        // 如果搜索到叶子节点，并且 remain 等于叶子节点的值，说明此路径匹配
        if (node.left == null && node.right == null && node.val == remain) {
            list.add(new ArrayList<>(nums));
        }
        // 深度优先搜索 node 节点的左子树
        dfs(node.left, remain - node.val, nums, list);
        // 深度优先搜索 node 节点的右子树
        dfs(node.right, remain - node.val, nums, list);
        // 回溯的时候需要删除最后一个数值
        nums.remove(nums.size() - 1);
    }
}

17. 电话号码的字母组合

题目介绍

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

定义一个 string 字符数组，用来存储每次遍历完以后，当前遍历过的字符串。整个过程我们使用dfs深度优先，搜索完一个结果后就会回溯到上一层，然后继续向下层查找，直到下一层越界为止。这里给出两个示例图：

输入：digits = “23”

输入：digits = “256”

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null) return null;
        List<String> list = new ArrayList<>();
        char[] chars = digits.toCharArray();
        if (chars.length == 0) return list;
        char[] string = new char[chars.length];
        dfs(0, chars, string, list);
        return list;
    }

    private char[][] lettersArray = {
        {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
        {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
    };

    private void dfs(int index, char[] chars, char[] string, List<String> list) {
        // 不能再往下搜索
        if (index == chars.length) {
            list.add(new String(string));
            return;
        }
        // 枚举这一层元素
        char[] letters = lettersArray[chars[index] - '2'];
        for (char letter : letters) {
            string[index] = letter;
            dfs(index + 1, chars, string, list);
        }
    }
}

22. 括号生成

题目介绍

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

如果 cur 长度达到 n 的两倍，说明完成了一次括号匹配。
如果左括号数量小于 n 的数量，我们可以放一个左括号。
如果右括号数量小于左括号的数量，我们可以放一个右括号。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        dfs(list, new StringBuilder(), 0, 0, n);
        return list;
    }

    public void dfs(List<String> list, StringBuilder cur, int open, int close, int n) {
        // 如果 cur 长度达到 n 的两倍，说明完成了一次括号匹配。
        if (cur.length() == n * 2) {
            list.add(cur.toString());
            return;
        }
        // 如果左括号数量小于  n  的数量，我们可以放一个左括号。
        if (open < n) {
            cur.append('(');
            dfs(list, cur, open + 1, close, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        // 如果右括号数量小于左括号的数量，我们可以放一个右括号。
        if (close < open) {
            cur.append(')');
            dfs(list, cur, open, close + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

39. 组合总和

题目介绍

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

以输入：candidates = [2, 3, 6, 7], target = 7 为例：

说明：

以 target = 7 为 根结点 ，创建一个分支的时 做减法 ；
每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
减到 0 或者负数的时候停止，即：结点 0 和负数结点成为叶子结点；
所有从根结点到结点 00 的路径（只能从上往下，没有回路）就是题目要找的一个结果。

这棵树有 4 个叶子结点的值 0，对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]，而示例中给出的输出只有 [[7], [2, 2, 3]]。即：题目中要求每一个符合要求的解是 不计算顺序 的。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(candidates, 0, target, new ArrayList<>(), list);
        return list;
    }

    private void dfs(int[] candidates,int begin,int remain,List<Integer> nums,List<List<Integer>> list){
        // 如果剩余数值小于0，则表示行不通，直接返回
        if (remain < 0) {
            return;
        }
        // 如果剩余数值等于0，则表示行得通，保存结果
        if (remain == 0) {
            list.add(new ArrayList<>(nums));
            return;
        }
        // 如果剩余数值大于0，则循环遍历进行深度搜索
        for (int i = begin; i < candidates.length; i++) {
            nums.add(candidates[i]);
            dfs(candidates, i, remain - candidates[i], nums, list);
            nums.remove(nums.size() - 1);
        }
    }
}

46. 全排列

题目介绍

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null) return null;
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 0) return list;
        dfs(0, nums, list);
        return list;
    }

    private void dfs(int index, int[] nums, List<List<Integer>> list) {
        // 不能再往下搜索
        if (index == nums.length) {
            List<Integer> ans = new ArrayList<>();
            for (int num : nums) {
                ans.add(num);
            }
            list.add(ans);
            return;
        }
        // 枚举这一层元素
        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);//交换元素
            dfs(index + 1, nums, list);
            swap(nums, index, i);//还原现场
        }
    }

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

47. 全排列 II

题目介绍

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目实现

此题是「46. 全排列」的进阶，序列中包含了重复的数字，要求我们返回不重复的全排列，那么我们依然可以选择使用搜索回溯的方法来做。如果只使用上述解题的递归函数，我们会生成大量重复的排列，因为对于第 index 的位置，如果存在重复的数字 i，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。要解决重复问题，我们只要设定一个规则，保证在填第 index 个数的时候重复数字只会被填入一次即可。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null) return null;
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 0) return list;
        dfs(0, nums, list);
        return list;
    }

    private void dfs(int index, int[] nums, List<List<Integer>> list) {
        // 不能再往下搜索
        if (index == nums.length) {
            List<Integer> ans = new ArrayList<>();
            for (int num : nums) {
                ans.add(num);
            }
            list.add(ans);
            return;
        }
        // 枚举这一层元素
        for (int i = index; i < nums.length; i++) {
            // 要保证一个数字在 index 位置只会出现一次
            if (isRepeat(nums, index, i)) continue;

            swap(nums, index, i);//交换元素
            dfs(index + 1, nums, list);
            swap(nums, index, i);//还原现场
        }
    }

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

    private boolean isRepeat(int[] nums, int index, int i) {
        for (int j = index; j < i; j++) {
            if (nums[j] == nums[i]) {
                return true;
            }
        }
        return false;
    }
}