代码随想录第24天|回溯part4 寻找切割点

2024-06-05 05:12

本文主要是介绍代码随想录第24天|回溯part4 寻找切割点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

93.复原ip地址

在这里插入图片描述
寻找切割点,但是需要注意的是,切割点(即.号)只有三个
将需要拼凑的值先放进一个数组里,等满足条件后再将其拼成字符串

class Solution {
public:vector<string> res;vector<int> path;int check(string s) {if (s.size() > 1 && s[0] == '0')return -1;if (s.size() == 0)return -1;int sum = 0;for (int i = 0; i < s.size(); i++) {if (s[i] > '9' || s[i] < '0')return -1;sum = sum * 10 + s[i] - '0';if (sum > 255)return -1;}return sum;}void backTracking(string s, int step, int dotNum) {if (dotNum == 0) {string temp = s.substr(step, s.size() - step);int t = check(temp);if (t == -1)return;path.push_back(t);string r = to_string(path[0]);for (int i = 1; i < path.size(); i++) {r = r + "." + to_string(path[i]);}res.push_back(r);path.pop_back();return;}for (int i = step; i < s.size(); i++) {string temp = s.substr(step, i - step + 1);int t = check(temp);if (t == -1)break;path.push_back(t);backTracking(s, i + 1, dotNum - 1);path.pop_back();}}vector<string> restoreIpAddresses(string s) {backTracking(s, 0, 3);return res;}
};

go代码

var (res  []stringpath []int
)func check(s string) int {if len(s) > 1 && s[0] == '0' {return -1}if len(s) == 0 {return -1}sum := 0for i := 0; i < len(s); i++ {if s[i] > '9' || s[i] < '0' {return -1}sum = sum*10 + int(s[i]-'0')if sum > 255 {return -1}}return sum
}
func backTracking(s string, step int, dotNum int) {if dotNum == 0 {var temp string = s[step:]t := check(temp)if t == -1 {return}path = append(path, t)r := strconv.Itoa(path[0])for i := 1; i < len(path); i++ {r += "." + strconv.Itoa(path[i])}res = append(res, r)path = path[:len(path)-1]return}for i := step; i < len(s); i++ {temp := s[step : i+1]t := check(temp)if t == -1 {break}path = append(path, t)backTracking(s, i+1, dotNum-1)path = path[:len(path)-1]}
}
func restoreIpAddresses(s string) []string {res = []string{}path = []int{}backTracking(s, 0, 3)return res
}

78.子集

在这里插入图片描述

class Solution {
public:vector<int> path;vector<vector<int>> res;void backTracking(vector<int> nums, int step) {res.push_back(path);if (step >= nums.size()) {return;}for (int i = step; i < nums.size(); i++) {path.push_back(nums[i]);backTracking(nums, i + 1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backTracking(nums, 0);return res;}
};

go语言

var (res  [][]intpath []int
)func backTracking(nums []int, step int) {p := make([]int, len(path))copy(p, path)res = append(res, p)if step >= len(nums) {return}for i := step; i < len(nums); i++ {path = append(path, nums[i])backTracking(nums, i+1)path = path[:len(path)-1]}
}
func subsets(nums []int) [][]int {res = [][]int{}path = []int{}backTracking(nums, 0)return res
}

90.子集II

在这里插入图片描述
和之前的题目一样,需要先排序,然后去重
去重可以用used数组,也可以用step来去重
使用used数组:

class Solution {
public:vector<int> path;vector<vector<int>> res;void backTracking(vector<int>& nums, int step,vector<bool>& used) {res.push_back(path);if (step >= nums.size())return;for (int i = step; i < nums.size(); i++) {if(i > 0 && used[i-1] == false && nums[i] == nums[i-1]) continue;used[i] = true;path.push_back(nums[i]);backTracking(nums,i+1,used);used[i] = false;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(),false);backTracking(nums,0,used);return res;}
};

直接使用step去重,只不过判断的逻辑需要变动一下,这样可以保证在同一树层里不使用相同的数

class Solution {
public:vector<int> path;vector<vector<int>> res;void backTracking(vector<int>& nums, int step) {res.push_back(path);if (step >= nums.size())return;for (int i = step; i < nums.size(); i++) {if (i > step && nums[i] == nums[i - 1])continue;path.push_back(nums[i]);backTracking(nums, i + 1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());backTracking(nums, 0);return res;}
};

下面给上go代码:

var (res  [][]intpath []int
)func backTracking(nums []int, step int) {p := make([]int, len(path))copy(p, path)res = append(res, p)if step >= len(nums) {return}for i := step; i < len(nums); i++ {if i > step && nums[i] == nums[i-1] {continue}path = append(path, nums[i])backTracking(nums, i+1)path = path[:len(path)-1]}
}
func subsetsWithDup(nums []int) [][]int {res = [][]int{}path = []int{}sort.Ints(nums)backTracking(nums, 0)return res
}

这篇关于代码随想录第24天|回溯part4 寻找切割点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032164

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级,来到新班级后发现其他小朋友们身高参差不齐,然后就想基于各小朋友和自己的身高差对他们进行排序,请帮他实现排序。 输入描述: 第一行为正整数H和N,0<H<200,为小明的身高,0<N<50,为新班级其他小朋友个数。第二行为N个正整数H1-HN,分别是其他小朋友的身高,取值范围0<Hi<200(1<=i<=N),且N个正整数各不相同。 输出描述: 输出

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所