LeetCode DayBackTracking 第 2 部分-java教程-PHP中文网

LeetCode DayBackTracking 第 2 部分

WBOY

发布： 2024-07-09 17:40:30

转载

264人浏览过

leetcode daybacktracking 第 2 部分

39. 组合和

给定一组不同的整数候选者和一个目标整数目标，返回所有唯一的候选者组合的列表，其中所选数字之和达到目标。您可以按任何顺序返回组合。

同一个号码可以无限次地从候选人中选择。两个组合是唯一的，如果
频率
至少有一个所选数字不同。

生成的测试用例使得对于给定输入而言，总和达到目标的唯一组合数量少于 150 个组合。

示例1：

输入：候选人 = [2,3,6,7]，目标 = 7
输出：[[2,2,3],[7]]
说明：
2和3是候选，2 + 2 + 3 = 7。注意2可以多次使用。
7 是候选者，7 = 7.
这是仅有的两种组合。
示例2：

输入：候选人 = [2,3,5]，目标 = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]
示例3：

输入：候选人 = [2]，目标 = 1
输出：[]

限制：

1 2 候选人的所有元素都是独特的。
1

原始页面

这道题和昨天解决的题差别不是很大。

BackTracking 仍然可以很好地搜索深度的可能性并使用循环进行宽度控制。

需要注意的是，这里我们可以添加相同的元素，然后保持整个组合的独特性

 public List<List<Integer>>combinationSum(int[] Candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> Coms = new LinkedList<>();
        backTracking(列表, 梳子, 候选者, 目标, 0, 0);
        返回列表；
    }

    公共无效 backTracking（列表<列表<整数>>列表，列表<整数>梳，int []候选人，int目标，int总和，int开始）{
        如果（总和>目标）{
            返回;
        }
        如果（总和==目标）{
            list.add(new ArrayList<>(combs));
            返回;
        }

        for(int i=start; i<candidates.length; i++){
            梳子.add（候选者[i]）；
            总和+=候选人[i]；
            backTracking(列表、梳子、候选者、目标、总和、i);
            梳子.删除(梳子.size()-1);
            sum -= 候选人[i];
        }

登录后复制

40. 组合和 II

超过时间限制

 Set<List<Integer>> set = new HashSet<>();
    公共列表<列表<整数>>组合Sum2（int []候选人，int目标）{
        List<Integer> Coms = new LinkedList<>();
        Arrays.sort(候选);
        backTracking(combs, 目标, 候选者, 0, 0);

        返回新的 ArrayList<>(set);
    }

    public void backTracking(List<Integer>combs, int target, int[]candidates, int start, int sum){
        如果（总和>目标）{
            返回;
        }
        如果（总和==目标）{
            set.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > 目标){
                继续;
            }

            总和+=候选人[i]；
            梳子.add（候选者[i]）；
            backTracking(combs, 目标, 候选者, i+1, sum);
            sum -= 候选人[i];
            梳子.删除(梳子.size()-1);

        }
    }

登录后复制

因为有一些元素之前已经使用过，例如[1,1,1,2,3] 第一次递归中使用了112，但是循环会遍历从1到3开始的所有元素，并且存在三个“1”，所以当遇到第二个“1”时，组合112也会找到，这在之前的递归步骤中已经找到了，所以我们应该减少这些多余的步骤（类似地，它也可能发生在递归的遍历和递归的横向递归中。

解决问题

 List<List<Integer>> list = new ArrayList<>();
    公共列表<列表<整数>>组合Sum2（int []候选人，int目标）{
        List<Integer> Coms = new LinkedList<>();
        Arrays.sort(候选);
        backTracking(combs, 目标, 候选者, 0, 0, false);

        返回列表；
    }

    public void backTracking(List<Integer>combs, int target, int[]candidates, int start, int sum, boolean Horizon){
        如果（总和>目标）{
            返回;
        }
        如果（总和==目标）{
            list.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > 目标){
                继续;
            }

            if(i!=0 && 候选人[i] == 候选人[i-1] && 地平线){
                继续;
            }

            总和+=候选人[i]；
            梳子.add（候选者[i]）；
            backTracking(combs, 目标, 候选者, i+1, sum, false);
            sum -= 候选人[i]；
            梳子.删除(梳子.size()-1);
            地平线=真；
        }
    }

登录后复制

131. 回文分区

给定一个字符串 s，对 s 进行分区使得每个
子串
分区的是
回文
。返回 s.

所有可能的回文划分

示例1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例2：

输入：s = "a"
输出：[["a"]]

限制：

1 s 仅包含小写英文字母。
原始页面

 List<List<String>> list = new ArrayList<>();
    公共列表<列表<字符串>>分区（字符串s）{
        List<String> 梳 = new ArrayList<>();

        backTracking(combs, new StringBuilder(s), 0);
        返回列表；
    }

    公共无效 backTracking（List<String> 梳子，StringBuilder str，int start）{
        if(start == str.length()){
            list.add(new ArrayList<>(combs));
            返回;
        }

        for(int i=1; i+start <= str.length(); i++){

            String cur = str.substring(start, start+i);

            if(!isParlindrome(cur)){
                继续; 
            } 

            梳子.add(cur);
            backTracking(combs, str, start+i);
            梳子.删除(梳子.size()-1);
        }

    }

    公共布尔 isParlindrome(String s){
        左整数 = 0;
        int 右 = s.length()-1;

        而（左<右）{
            if(s.charAt(左++)!=s.charAt(右--)){
                返回假；
            }
        }
        返回真；
    }

登录后复制

以上就是LeetCode DayBackTracking 第 2 部分的详细内容，更多请关注php中文网其它相关文章！