V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[面试] 回溯题目小结

  •  
  •   Acceml ·
    Acceml · 2018-09-25 21:31:59 +08:00 · 1405 次点击
    这是一个创建于 2010 天前的主题,其中的信息可能已经有所发展或是发生改变。

    每天发一道 leetcode 题目,最近发现 A 的回溯题目有点多,基本就用一个模板搞定。

    [ Leetcode ] 79. 子集

    java

    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            Arrays.sort(nums);
            backtrack(list, new ArrayList<>(), nums, 0);
            return list;
        }
    
        private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
            list.add(new ArrayList<>(tempList));
            for (int i = start; i < nums.length; i++) {
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
    

    python

    class Solution:
        def subsets(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            list = []
            nums.sort()
            self.bracktrack(list, [], nums, 0)
            return list
    
        def bracktrack(self, list, tempList, nums, start):
            list.append(tempList.copy())
            for i in range(start, len(nums)):
                tempList.append(nums[i])
                self.bracktrack(list, tempList, nums, i + 1)
                tempList.pop()
    

    [ Leetcode ] 77. 组合

    java 版本

    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            backtrack(res, n, 1, k, new ArrayList<>());
            return res;
        }
    
        public void backtrack(List<List<Integer>> res, int n, int num, int k, List<Integer> list) {
            if (list.size() == k) {
                res.add(new ArrayList<>(list));
            } else {
                for (int i = num; i <= n; i++) {
                    list.add(i);
                    backtrack(res, n, i + 1, k, list);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
    

    python 版本

    class Solution:
        def backtrack(self, res, n, nums, k, current):
            if len(current) == k:
                res.append(current.copy())
            else:
                for i in range(nums, n + 1):
                    current.append(i)
                    self.backtrack(res, n, i + 1, k, current)
                    current.pop()
    
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            res = []
            self.backtrack(res, n, 1, k, [])
            return res
    

    [ Leetcode ] 46.全排列

    class Solution {
        public static List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            backtrack(res, new ArrayList<>(), nums);
            return res;
        }
    
        public static void backtrack(List<List<Integer>> res, List<Integer> tempRes, int[] nums) {
            if (tempRes.size() == nums.length) {
                //遍历完了,不需要回溯了.
                res.add(new ArrayList<>(tempRes));
            } else {
                for (int i = 0; i < nums.length; i++) {
                    if (tempRes.contains(nums[i])) {
                        //System.out.println("i:" + i + "---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(",")));
                        continue;
                    }
                    tempRes.add(nums[i]);
                    //System.out.println("i:" + i + "---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(",")));
                    backtrack(res, tempRes, nums);
                    tempRes.remove(tempRes.size() - 1);
                    //System.out.println("i:" + i + ":afterRemoveLast---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(",")));
                }
            }
        }
    }
    

    [ Leetcode ] 47. 全排列 II

    class Solution {
        public static List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            boolean[] used = new boolean[nums.length];
            backtrack(res, new ArrayList<>(), nums, used);
            return res;
        }
    
        public static void backtrack(List<List<Integer>> res, List<Integer> tempRes, int[] nums, boolean[] used) {
            if (tempRes.size() == nums.length) {
                //遍历完了,不需要回溯了.
                res.add(new ArrayList<>(tempRes));
            } else {
                for (int i = 0; i < nums.length; i++) {
                    if (used[i]) {
                        continue;
                    }
    
                    if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
                        continue;
                    }
    
                    used[i] = true;
                    tempRes.add(nums[i]);
                    backtrack(res, tempRes, nums, used);
                    used[i] = false;
                    tempRes.remove(tempRes.size() - 1);
                }
            }
        }
    }
    

    Leetcode 名企之路

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5251 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 09:37 · PVG 17:37 · LAX 02:37 · JFK 05:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.