算法学习——LeetCode力扣回溯篇2

算法学习——LeetCode力扣回溯篇2

在这里插入图片描述

40. 组合总和 II

40. 组合总和 II - 力扣（LeetCode）

描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

代码解析

和39的区别是不能重复使用元素

回溯（无去重，超时）

无去重，只能在最后加入时候find查找是否存在一样，再加入

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtarcking(vector<int>& candidates, int target , int sum ,int indnx)
    {
        if(sum > target)return;
        if(sum == target)
        {
            auto it = find(result.begin(),result.end(),path);
            if(it == result.end() ) result.push_back(path);
            return;
        }

        for(int i=indnx ; i < candidates.size() && sum + candidates[i] <= target ; i++)
        {
            path.push_back(candidates[i]);
            backtarcking(candidates,target,sum+candidates[i],i+1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtarcking(candidates,target,0,0);
        return result;
    }
};
回溯去重

在这里插入图片描述
去重：在同一层上，值一样的元素只能用一次。同一枝上可以多次用

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtarcking(vector<int>& candidates, int target , int sum ,int indnx)
    {
        if(sum > target)return;
        if(sum == target)
        {
            result.push_back(path);
            return;
        }

        for(int i=indnx ; i < candidates.size() && sum + candidates[i] <= target ; i++)
        {
        	//发现一样的元素这一层已经用过了，直接跳过这次
            if(i > indnx && candidates[i] == candidates[i-1]) continue;

            path.push_back(candidates[i]);
            backtarcking(candidates,target,sum+candidates[i],i+1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtarcking(candidates,target,0,0);
        return result;
    }
};

131. 分割回文串

131. 分割回文串 - 力扣（LeetCode）

描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

提示

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

代码解析

class Solution {
public:
    vector<vector<string>> result;
   //判断字串是否是回文串
    bool check(const string &s)
    {
        for(int i=0 ; i<s.size()/2 ; i++)
        {
            if(s[i] != s[s.size()- 1 -i]) return false;
        }
        return true;
    }
    void backtracking(string s , int indnx  ,vector<string> &path)
    {
    	//当循环指针大于等于最大值的时候，认为分割出一种结果
        if(indnx >= s.size())
        {
            result.push_back(path);
            return;
        }
		//循环字符串长度，从index当前的运行指针开始切割回文串
        for(int i = indnx ; i<s.size() ;i++ )
        {
            string tmp;
            //切割字串，字串是indnx到i之间。
            for(int j = indnx ; j <= i ;j++)
            {
                tmp += s[j];
            }
            // cout<<tmp<<endl;
            //检验字串是否为回文串，是回文串压入路径，不是i+1，进行下一个长度加1的字串
            if(check(tmp)==1)   path.push_back(tmp);
            else continue;
            //如果当前字串是回文串，递归indnx加1
            backtracking(s,i+1,path);
            //回溯，弹出上一个字串
            path.pop_back();
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        if(s.size()==0) return result;
        vector<string> path;
        backtracking(s,0,path);
        return result;
    }
};

93. 复原 IP 地址

93. 复原 IP 地址 - 力扣（LeetCode）

描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示

  • 1 <= s.length <= 20
  • s 仅由数字组成

代码解析

class Solution {
public:
    vector<string> result;
    vector<string> path;
    //判断是合法IP
    bool cheak(string &s)
    {
        if(s.size()==0)return false;
        if(s.size() > 1 && s[0]=='0') return false;
        if (stoi(s) > 255) return false;
        return true;
    }
    void back_tracking(string &s , int indnx )
    {
    	//IP最大短是4
        if(path.size() > 4)  return;
        //循环指针大于等于长度，并且IP段为四段。合法IP
        if(indnx >= s.size() && path.size()==4)
        {
            string tmp;
            for(int i=0 ;i< path.size()-1 ;i++)
            {
                tmp += path[i];
                tmp += '.';
            }
            tmp += path[path.size()-1];
            result.push_back(tmp);
            return;
        }
		//循环输入字符串，从index开始截取IP段
        for(int i=indnx ; i<s.size() ;i++)
        {
            string tmp;
            //截取一个IP段，但是不超过3位
            for(int j = indnx ; j<=i  &&  (j-indnx)<=3 ;j++)
            {
                tmp += s[j];
            }
			//检测是否为合法段，合法压入路径，不合法跳过该段
            if(cheak(tmp)==1) path.push_back(tmp);
            else continue;
			//递归
            back_tracking(s,i+1);
            //回溯
            path.pop_back();

        }
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        back_tracking(s,0);
        return result;
    }
};

78. 子集

78. 子集 - 力扣（LeetCode）

描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例

示例 1：

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

示例 2：

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

提示

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

代码解析

在这里插入图片描述
与中序遍历N叉树非常的类似
每一个子集就是一个节点，遍历所有的节点

回溯遍历法（不要简单问题复杂化）
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums , int indnx  )
    {
    	//每一个节点都加入，无须判断节点
        result.push_back(path);
        //如果遍历指针大于等于最深处，就返回
        if(indnx >= nums.size()) return;
      	//横向循环
        for(int i=indnx ; i < nums.size() ; i++ )
        {
        	//新值压入
            path.push_back(nums[i]);
            backtracking(nums,i+1);//递归
            path.pop_back();//回溯
        }
        return;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

90. 子集 II

90. 子集 II - 力扣（LeetCode）

描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例

示例 1：

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

示例 2：

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

提示

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

代码解析

在这里插入图片描述

去重分为层次去重和树枝去重

  • 层次去重
    是一个元素只能用一次（一样的两个可以用两次，【1，2，2】两个2各自可用一次）。
    if (i > indnx && nums[i] == nums[i - 1] ) continue; 当前的和上一个相同就跳过
  • 树枝去重
    是数值一样的元素只能用一个，（一样的两个元素也只能用一次。【1，2，2】两个2只能用一个2）
    回溯去重
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int pre;
    void backtracking(vector<int>& nums , int indnx)
    {
      
        result.push_back(path);
       
        if(indnx >= nums.size())return;

        for(int i= indnx ; i < nums.size() ; i++)
        {
            if (i > indnx && nums[i] == nums[i - 1] ) 
            { 
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums , i+1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backtracking(nums,0);
        return result;
    }
};

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

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

相关文章

（二）【Jmeter】专栏实战项目靶场drupal部署

（二）【Jmeter】专栏实战项目靶场drupal部署

该专栏后续实战示例&#xff0c;都以该篇部署的项目展开操作。 前置条件 参考“&#xff08;一&#xff09;【Jmeter】JDK及Jmeter的安装部署及简单配置” 安装部署Jmeter&#xff0c;从文章最后下载“Postman、Rancher.ova、VirtualBox-7.0.12-159484-Win.exe、Xshell-7.0.01…
阅读更多...
CMU和ETH联合研发了一个名为 「敏捷但安全」的新框架，为四足机器人在复杂环境中实现高速运动提供了解决方案

CMU和ETH联合研发了一个名为 「敏捷但安全」的新框架，为四足机器人在复杂环境中实现高速运动提供了解决方案

在高速机器人运动领域&#xff0c;实现同时兼顾速度和安全一直是一大挑战。但现在&#xff0c;卡内基梅隆大学&#xff08;CMU&#xff09;和苏黎世联邦理工学院&#xff08;ETH&#xff09;的研究团队带来了突破性进展。他们开发的新型四足机器人算法&#xff0c;不仅能在复杂…
阅读更多...
Leetcode 452. 用最少数量的箭引爆气球435. 无重叠区间

Leetcode 452. 用最少数量的箭引爆气球435. 无重叠区间

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(o1,o2)->Integer.compare(o1[0], o2[0]));int count1;//箭的数量for(int i1;i<points.length;i) {if(points[i][0]>points[i-1][1]) {count;//边界没重合&#xff0c;又需要一支箭…
阅读更多...
如何重新安装 macOS

如何重新安装 macOS

你可以使用电脑的内建恢复系统“macOS 恢复”来重新安装 Mac 操作系统。不但简单快捷&#xff0c;而且重新安装后不会移除你的个人数据。 将 Mac 关机 选取苹果菜单  >“关机”&#xff0c;然后等待 Mac 关机。如果你无法将 Mac 关机&#xff0c;请按住它的电源按钮最长 …
阅读更多...
第六篇：MySQL图形化管理工具

第六篇：MySQL图形化管理工具

经过前五篇的学习&#xff0c;对于数据库这门技术的理解&#xff0c;我们已经在心中建立了一个城堡大致的雏形&#xff0c;通过命令行窗口&#xff08;cmd&#xff09;快速上手了【SQL语法-DDL-数据定义语言】等相关命令 道阻且长&#xff0c;数据库技术这一宝藏中还有数不清的…
阅读更多...
猫头虎分享: 探索软件系统架构的革新之路

猫头虎分享: 探索软件系统架构的革新之路

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
Swift Combine 网络受限时从备用 URL 请求数据 从入门到精通十四

Swift Combine 网络受限时从备用 URL 请求数据 从入门到精通十四

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划40）

python 基础知识点（蓝桥杯python科目个人复习计划40）

今日复习内容&#xff1a;矩阵乘法&#xff0c;高斯消元 哈哈&#xff0c;我来干回老本行&#xff0c;复习点儿数学类专业学的东西 因为电脑上制作费时间&#xff0c;所以我直接用我的《高等代数》和《数值分析》笔记。 一.矩阵乘法 例题1&#xff1a;矩阵相乘 题目描述&am…
阅读更多...
three.js 细一万倍教程 从入门到精通（三）

three.js 细一万倍教程 从入门到精通（三）

目录 五、详解PBR材质纹理 5.1、详解PBR物理渲染 5.2、标准网格材质与光照物理效果 5.3、置换贴图与顶点细分设置 5.4、设置粗糙度与粗糙度贴图 5.5、设置金属度与金属贴图 5.6、法线贴图应用 5.7、如何获取各种类型纹理贴图 5.8、纹理加载进度情况 单张图片加载 多…
阅读更多...
Java学习手册——第七篇基础语法

Java学习手册——第七篇基础语法

Java学习手册——第七篇基础语法 1. 注释2. 顺序语句3. 条件语句3.1 if语句3.2 switch语句 4. 循环语句4.1 for循环4.2 while 语句4.3 do...while语句 本篇为大家快速入门Java基础语法&#xff0c;了解一个语言的基础语法是必要的&#xff0c; 因为我们后期都是需要用这些基础语…
阅读更多...
基于CU,PO,RD,IPO矩阵图分析数据资产-自创

基于CU,PO,RD,IPO矩阵图分析数据资产-自创

术语 数据资产&#xff1a;数据资产是具有价值的数据资源。没有价值的数据资源&#xff0c;通过采集&#xff0c;整理&#xff0c;汇总等加工后&#xff0c;也可以成为具有直接或间接价值的数据资产。传统企业逐渐数字化转型&#xff0c;尤其是互联网企业&#xff0c;都十分重视…
阅读更多...
文献速递：肿瘤分割---- 弱监督肝肿瘤分割，使用Couinaud区段标注

文献速递：肿瘤分割---- 弱监督肝肿瘤分割，使用Couinaud区段标注

文献速递&#xff1a;肿瘤分割---- 弱监督肝肿瘤分割&#xff0c;使用Couinaud区段标注 01 文献速递介绍 肝癌是世界上导致癌症死亡的主要原因之一&#xff0c;也是第二大常见的癌症死因。本稿件于2021年10月28日收到&#xff0c;2021年11月24日修订&#xff0c;2021年12月1…
阅读更多...
[Linux开发工具]项目自动化构建工具-make/Makefile

[Linux开发工具]项目自动化构建工具-make/Makefile

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.背景2.依赖关系和依…
阅读更多...
【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏17（附项目源码）

【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏17（附项目源码）

本节最终效果演示 文章目录 本节最终效果演示系列目录前言制作木板UI直接复制和工具一样的即可检查背包是否有指定数量的空插槽 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列&#xff01;本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇…
阅读更多...
品牌之门：概率与潜力的无限延伸

品牌之门：概率与潜力的无限延伸

在品牌的世界里&#xff0c;每一个成功的推广都像是打开一扇门&#xff0c;从未知走向已知&#xff0c;从潜在走向显现。这扇门&#xff0c;既是品牌的起点&#xff0c;也是品牌发展的无限可能。 品牌&#xff0c;就像一扇紧闭的门&#xff0c;它静静地矗立在那里&#xff0c;…
阅读更多...
toString()、equals()、clone()用法

toString()、equals()、clone()用法

Java中所有类的对象都可以直接使用Object类中提供的一些方法 1. toString()&#xff1a;返回对象的字符串表示形式&#xff0c;通常在类中重写&#xff0c;以便于返回的是对象的内容 2. equals()&#xff1a;判断两个对象的地址是否相等&#xff0c;直接使用也一样&#xff0c;…
阅读更多...
【蓝桥杯】灭鼠先锋

【蓝桥杯】灭鼠先锋

一.题目描述 二.解题思路 博弈论&#xff1a; 只能转移到必胜态的&#xff0c;均为必败态。 可以转移到必败态的&#xff0c;均为必胜肽。 最优的策略是&#xff0c;下一步一定是必败态。 #include<iostream> #include<map> using namespace std;map<string,bo…
阅读更多...
【Linux系统学习】6.Linux系统软件安装

【Linux系统学习】6.Linux系统软件安装

实战章节&#xff1a;在Linux上部署各类软件 前言 为什么学习各类软件在Linux上的部署 在前面&#xff0c;我们学习了许多的Linux命令和高级技巧&#xff0c;这些知识点比较零散&#xff0c;进行练习虽然可以基础掌握这些命令和技巧的使用&#xff0c;但是并没有一些具体的实…
阅读更多...
C++：priority_queue模拟实现

C++：priority_queue模拟实现

C&#xff1a;priority_queue模拟实现 什么是priority_queue模拟实现向上调整算法向下调整算法插入与删除 仿函数 什么是priority_queue priority_queue称为优先级队列。优先级队列是一种特殊的队列&#xff0c;其中每个元素都有一个相关的优先级。元素的优先级决定了它们在队…
阅读更多...
NSSCTF Round#18 RE GenshinWishSimulator WP

NSSCTF Round#18 RE GenshinWishSimulator WP

恶搞原神抽卡模拟器 看到软件的界面&#xff0c;大致有三种思路&#xff1a; 修改石头数量一直抽&#xff0c;如果概率正常肯定能抽到&#xff08;但是估计设置的概率是0&#xff09;在源码里找flag的数据把抽卡概率改成100%直接抽出来 Unity逆向&#xff0c;根据经验应该dnsp…
阅读更多...
最新文章

Copyright @ 2022~2023