代码随想录第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

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu