LeetCode 39. 组合总和 40.组合总和II 131.分割回文串

欢迎关注个人公众号:爱喝可可牛奶

LeetCode 39. 组合总和 40.组合总和II 131.分割回文串

LeetCode 39. 组合总和

分析

回溯可看成对二叉树节点进行组合枚举,分为横向和纵向

每次往sum添加新元素时,必须明确从can哪个位置开始,定义变量pos

返回条件 sum == target 或 sum > target; 横向结束条件 没有新元素可以添加了即pos<can.length;

bt(can, sum, tar, pos){
    if(sum == tar) add return;
    if(sum > tar) pos++ return;
    for(int i = pos; i < can.len;i++){
        sum+=can[pos];
        bt(can, sum, tar, i);
        sum-=can[pos];
    }
}

这个回溯考虑sum > tar时, pos++不应该写在第3行,这样导致回溯减掉的元素值与递归添加的不一样。而应该放在第4行for()中,只有当纵向回溯结束时(也就是很多个sum+=can[i]导致return后),横向遍历才会往右移动;回溯第n个can[i] 回溯第n-1个can[i];

剪枝

一次回溯只能抵消一层递归;每次return只是从已经添加进sum的众多can[i]中减掉一个

举个栗子:

sum+= n个can[i],回溯一次还剩n-1个can[i];这时要i++了;但是剩下的sum和这个i++后的新can[i]加起来可能也会超过tar,这步操作可以剪枝,避免进入新can[i]的递归;

for (int i = pos; i < candidates.size() && sum + candidates[i] <= target; i++)

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            path.removeLast(); // 回溯,移除路径 path 最后一个元素
        }
    }
}

LeetCode 40.组合总和II

分析

在原有基础上设限每个数字在每个组合中只能使用 一次 且不包含重复的组合

Arrays升序;纵向遍历时就要i++;Set去重

Set去重超时了!!! 要在添加集合的时候就判断是否重复,取res中最后一个path和当前满足条件的path比较 也不行

纵向递归不需要去重,横向递归时采用去重

剪枝

代码

class Solution {
    List<List<Integer>> res = new LinkedList();
    LinkedList<Integer> path = new LinkedList();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 要对横向遍历时使用过的元素进行跳过 因为一样的元素在深度递归时已经把包含此元素的所有可能结果全部枚举过了
            if (i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            //System.out.println("sum="+sum);
            //i++;
            backtracking(candidates, target, i+1);
            //i--;
            //sum -= candidates[i];
            sum-=path.getLast();
            path.removeLast(); // 回溯,移除路径 path 最后一个元素
        }
    }
}

LeetCode 131.分割回文串

分析

切割子串,保证<u>每个子串都是 回文串</u>

找到所有的子串组合,判断子串是否是回文串,根据索引切割 startIndex endIndex if(start-end) is ; res.add

代码

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return res;
    }

    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小,说明找到了一组分割方案
        if (startIndex >= s.length()) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串,则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                continue;
            }
            //起始位置后移,保证不重复
            backTracking(s, i + 1);
            // 一定要有回溯 开始下一种分割
            path.removeLast();
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

总结

  1. 题目给定的数据集如果使用数组的方式,要判断是否有序,没有说明有序最好视情排序
  2. 回溯横向移动的时机一定是某个纵向递归结束
  3. 看清题目要求,将串的所有子串都分割成回文子串
  4. 横向遍历逻辑 纵向递归startIndex++逻辑 回溯逻辑

本文由博客一文多发平台 OpenWrite 发布!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,921评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,635评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,393评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,836评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,833评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,685评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,043评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,694评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,671评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,424评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,027评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2 343

推荐阅读更多精彩内容