代码随想录-算法训练营day27【回溯03：组合总和、分割回文串】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第七章 回溯算法part03

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

 详细布置 

 39. 组合总和 

本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制

题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html 
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ  

 40.组合总和II 

本题开始涉及到一个问题了：去重。

注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。 

题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html   
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A

 131.分割回文串  

本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。 

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html  
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6  

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl

目录

0039_组合总和

0040_组合总和II

0131_分割回文串

0039_组合总和

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;

import java.util.*;

public class _0039_组合总和 {
}

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

    public void backtracking(List<List<Integer>> res, List<Integer> path, 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(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); //回溯，移除路径 path 最后一个元素
        }
    }
}

class Solution0039_2 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量，是 candidates 里的属性，可以不传
     * @param target     每减去一个元素，目标值变小
     * @param path       从根结点到叶子结点的路径，是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        //target 为负数和 0 的时候，不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        //重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            //注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            //状态重置
            path.removeLast();
        }
    }
}

0040_组合总和II

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;

import java.util.*;

public class _0040_组合总和II {
    public static void main(String[] args) {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        Solution0040_3 solution = new Solution0040_3();
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println("输出 => " + res);
    }
}

class Solution0040 {//使用标记数组
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used;
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        //加标志数组，用来辅助判断同层节点是否已经遍历
        Arrays.fill(used, false);
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return ans;
    }

    private void backTracking(int[] candidates, int target, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList(path));
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            //每个节点仅能选择一次，所以从下一位开始
            backTracking(candidates, target, i + 1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

class Solution0040_2 {//不使用标记数组
    List<List<Integer>> res = new ArrayList<>();
    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;
    }

    private void backTracking(int[] candidates, int target, int start) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {
            //正确剔除重复解的办法
            //跳过同一树层使用过的元素
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }

            sum += candidates[i];
            path.add(candidates[i]);
            // i+1 代表当前组内元素只选取一次
            backTracking(candidates, target, i + 1);

            int temp = path.getLast();
            sum -= temp;
            path.removeLast();
        }
    }
}

class Solution0040_3 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        //关键步骤
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, len, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param len        冗余变量
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res
     */
    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            //大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[i] < 0) {
                break;
            }

            //小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.addLast(candidates[i]);
            //调试语句 ①
            //System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates, len, i + 1, target - candidates[i], path, res);

            path.removeLast();
            //调试语句 ②
            //System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
        }
    }
}

0131_分割回文串

package com.question.solve.leetcode.programmerCarl2._08_backtrackingAlgorithms;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class _0131_分割回文串 {
}

class Solution0131 {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();

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

    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(s, i + 1);
            deque.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;
    }
}

class Solution0131_2 {//回溯+动态规划优化回文串判断
    List<List<String>> result;
    LinkedList<String> path;
    boolean[][] dp;

    public List<List<String>> partition(String s) {
        result = new ArrayList<>();
        char[] str = s.toCharArray();
        path = new LinkedList<>();
        dp = new boolean[str.length + 1][str.length + 1];
        isPalindrome(str);
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String str, int startIndex) {
        if (startIndex >= str.length()) {
            //如果起始位置大于s的大小，说明找到了一组分割方案
            result.add(new ArrayList<>(path));
        } else {
            for (int i = startIndex; i < str.length(); ++i) {
                if (dp[startIndex][i]) {
                    //是回文子串，进入下一步递归
                    //先将当前子串保存入path
                    path.addLast(str.substring(startIndex, i + 1));
                    //起始位置后移，保证不重复
                    backtracking(str, i + 1);
                    path.pollLast();
                } else {
                    //不是回文子串，跳过
                    continue;
                }
            }
        }
    }

    //通过动态规划判断是否是回文串,参考动态规划篇 52 回文子串
    public void isPalindrome(char[] str) {
        for (int i = 0; i <= str.length; ++i) {
            dp[i][i] = true;
        }
        for (int i = 1; i < str.length; ++i) {
            for (int j = i; j >= 0; --j) {
                if (str[j] == str[i]) {
                    if (i - j <= 1) {
                        dp[j][i] = true;
                    } else if (dp[j + 1][i - 1]) {
                        dp[j][i] = true;
                    }
                }
            }
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/595083.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

编程入门（六）【Linux系统基础操作一】

编程入门（六）【Linux系统基础操作一】

读者大大们好呀&#xff01;&#xff01;!☀️☀️☀️ &#x1f525; 欢迎来到我的博客 &#x1f440;期待大大的关注哦❗️❗️❗️ &#x1f680;欢迎收看我的主页文章➡️寻至善的主页 文章目录 &#x1f525;前言&#x1f680;Linux操作系统介绍与环境准备Linux操作系统介…
阅读更多...
Kafka源码分析(五) - Server端 - 基于时间轮的延时组件

Kafka源码分析(五) - Server端 - 基于时间轮的延时组件

系列文章目录 Kafka源码分析-目录 一. 背景 Kafka内部涉及大量的"延时"操作&#xff0c;比如收到PRODUCE请求后可为副本等待一个timeout的时间后再响应客户端。 那我们讨论一个问题&#xff1a;Kafka为什么自己实现了一个延时任务组件&#xff0c;而不直接使用ja…
阅读更多...
《从Paxos到Zookeeper》——第五、六章：经典应用场景

《从Paxos到Zookeeper》——第五、六章：经典应用场景

目录 第五章 使用Zookeeper 5.1 服务端部署与运行 5.2 客户端相关 5.2.1 客户端运行 5.2.2 客户端命令 5.3 Java客户端API 5.4 开源客户端 第六章 经典应用场景 6.1 典型应用场景及实现 6.1.1 数据发布/订阅&#xff08;全局配置中心&#xff09; 6.1.2 负载均衡&#xff08;Lo…
阅读更多...
ChatGPT Web Midjourney一键集成最新版

ChatGPT Web Midjourney一键集成最新版

准备工具 服务器一台 推荐使用浪浪云服务器 稳定 安全 有保障 chatgpt api 推荐好用白嫖的api 项目演示 项目部署 浏览器访问casaos 添加软件原添加 https://gitee.com/langlangy_1/CasaOS-AppStore-LangLangy/raw/master/chatmjd.zip 安装此软件 等待安装 安装后再桌面设置…
阅读更多...
什么是模版方法模式,有哪些应用？

什么是模版方法模式,有哪些应用？

模板方法模式是一种行为设计模式&#xff0c;他的主要作用就是复用代码。在很多时候&#xff0c;我们的代码中可能会有-些公共的部分并且还有一些定制的部分&#xff0c;那么公共这部分就可以定义在一个父类中&#xff0c;然后将定制的部分实现在子类中。这样子类可以根据需要扩…
阅读更多...
TRIZ理论助力充电桩产业跨越技术瓶颈，实现产业升级！

TRIZ理论助力充电桩产业跨越技术瓶颈，实现产业升级！

随着新能源汽车市场的迅猛发展和电动汽车保有量的不断增加&#xff0c;充电桩作为电动汽车的“能量补给站”&#xff0c;其重要性日益凸显。然而&#xff0c;充电桩产业在发展过程中也面临着诸多技术瓶颈&#xff0c;如何突破这些瓶颈&#xff0c;推动充电桩产业升级成为行业亟…
阅读更多...
《Video Mamba Suite》论文笔记（2）Mamba对于多模态交互的作用

《Video Mamba Suite》论文笔记（2）Mamba对于多模态交互的作用

原文翻译 4.2 Mamba for Cross-Modal Interaction Tasks and datasets.除了单模态任务外&#xff0c;我们还评估了 Mamba 在跨模态交互方面的性能。我们首先使用视频时间定位 (Video Temporal Grounding) 任务进行评估。所涉及的数据集包含 QvHighlight [44] 和 Charade-STA …
阅读更多...
Vue阶段练习：初始化渲染、获取焦点、记账清单

Vue阶段练习：初始化渲染、获取焦点、记账清单

阶段练习主要承接Vue 生命周期-CSDN博客 &#xff0c;学习完该部分内容后&#xff0c;进行自我检测&#xff0c;每个练习主要分为效果显示、需求分析、静态代码、完整代码、总结 四个部分&#xff0c;效果显示和准备代码已给出&#xff0c;我们需要完成“完整代码”部分。 练习…
阅读更多...
交直流充电桩测试系统解决方案，你了解多少？

交直流充电桩测试系统解决方案，你了解多少？

交直流充电桩测试系统是电动汽车充电设施的重要组成部分&#xff0c;它对充电桩的性能、安全性和可靠性进行全方位的检测和评估。随着电动汽车的普及&#xff0c;充电桩测试系统的需求也在不断增加。本文将对交直流充电桩测试系统的解决方案进行简要介绍。 1. 系统组成 交直流…
阅读更多...
微信小程序如何使用svg矢量图标

微信小程序如何使用svg矢量图标

微信小程序如何使用自定义SVG矢量图标 在微信小程序中&#xff0c;经常会用到小图标来装饰界面&#xff0c;我们常用的方法就是引用第三方的图标&#xff0c;但会存在收费或者找不到合适的图标&#xff0c;这时候我建议可以自行编写svg图标代码&#xff0c;就可以随心所欲的使…
阅读更多...
纯干货，源代码防泄密之环境加密与文档加密的区别

纯干货，源代码防泄密之环境加密与文档加密的区别

环境加密和文档加密是两种不同的数据保护方法&#xff0c;下面用SDC沙盒及文档加密系统作对比&#xff0c;它们在设计理念、管控对象、安全性、性能以及适用场景等方面有所区别&#xff1a; 来百度APP畅享高清图片 1、设计理念&#xff1a; 环境加密&#xff08;如SDC沙盒&am…
阅读更多...
JavaScript继承的方法和优缺点

JavaScript继承的方法和优缺点

原型链继承 让一个构造函数的原型是另一个类型的实例&#xff0c;那么这个构造函数new出来的实例就具有该实例的属性。 优点&#xff1a; 写法方便简洁&#xff0c;容易理解。 缺点&#xff1a; 在父类型构造函数中定义的引用类型值的实例属性&#xff0c;会在子类型原型上…
阅读更多...
华中科技大学雷达站部署

华中科技大学雷达站部署

一&#xff1a;项目地址 GitHub - HUSTLYRM/HUST_Radar_2023: 华中科技大学狼牙战队 RoboMaster 2023赛季 雷达站 二&#xff1a;安装依赖 2.1创建虚拟环境 首先是程序是基于python3.8完成&#xff0c;所以创建虚拟环境的时候&#xff0c;选择3.8的虚拟环境 conda create -…
阅读更多...
【算法刷题日志】吸氧羊的StarryCoding之旅 - 贡献法计算

【算法刷题日志】吸氧羊的StarryCoding之旅 - 贡献法计算

题目链接&#xff1a;https://www.starrycoding.com/problem/3 题目描述 吸氧羊终于注册了一个StarryCoding账号&#xff01;&#xff08;她很开心&#xff09; 但是吸氧羊忘记了它的密码&#xff0c;她想起你是计算机大师&#xff0c;于是就来请教你。 她虽然不记得密码了…
阅读更多...
nacos开启登录开关启动报错“Unable to start embedded Tomcat”

nacos开启登录开关启动报错“Unable to start embedded Tomcat”

nacos 版本&#xff1a;2.3.2 2.2.2版本之前的Nacos默认控制台&#xff0c;无论服务端是否开启鉴权&#xff0c;都会存在一个登录页&#xff1b;在之后的版本关闭了默认登录页面&#xff0c;无需登录直接进入控制台操作。在这里我们可以在官网可以看到相关介绍 而我现在所用的…
阅读更多...
中国各地级市城投债详细数据（2006年-2023年2月）

中国各地级市城投债详细数据（2006年-2023年2月）

01、数据简介 城投债又称为准市政债&#xff0c;发行主体是地方ZF投资平台&#xff0c;公开发行企业债和中期票据&#xff0c;其业主一般是地方基础设施建设&#xff0c;或者公益性项目主体&#xff0c;参与债券发行环节的当地ZF发债。 数据整理中国各地级市的城投债详细数据…
阅读更多...
opencv图片的旋转-------c++

opencv图片的旋转-------c++

图片的旋转 /// <summary> /// 图片的旋转 /// </summary> /// <param name"img"></param> /// <param name"angle">旋转角度:正数&#xff0c;则表示逆时针旋转;负数&#xff0c;则表示顺时针旋转</param> /// <…
阅读更多...
【intro】图卷积神经网络（GCN）

【intro】图卷积神经网络（GCN）

本文为Graph Neural Networks(GNN)学习笔记-CSDN博客后续&#xff0c;内容为GCN论文阅读&#xff0c;相关博客阅读&#xff0c;kaggle上相关的数据集/文章/代码的阅读三部分&#xff0c;考虑到本人是GNN新手&#xff0c;会先从相关博客开始&#xff0c;进一步看kaggle&#xff…
阅读更多...
考虑极端天气线路脆弱性的配电网分布式电源和储能优化配置模型

考虑极端天气线路脆弱性的配电网分布式电源和储能优化配置模型

1 主要内容 程序主要参考《考虑极端天气线路脆弱性的配电网分布式电源配置优化模型-马宇帆》&#xff0c;针对极端天气严重威胁配电网安全稳定运行的问题。基于微气象、微地形对配电网的线路脆弱性进行分析&#xff0c;然后进行分布式电源接入位置与极端天气的关联性分析&…
阅读更多...
优优嗨聚集团：法律明灯，个债处理中的法律咨询力量

优优嗨聚集团：法律明灯，个债处理中的法律咨询力量

在现代社会&#xff0c;个人债务问题日益突出&#xff0c;无论是因生活消费、投资失利还是其他原因&#xff0c;债务问题都可能成为个人财务的一大负担。面对复杂的债务困境&#xff0c;许多人感到迷茫和无助。此时&#xff0c;法律咨询如同一盏明灯&#xff0c;能够为个人债务…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站