Day27 代码随想录(1刷) 回溯

2024-04-01 13:52
文章标签 随想录 代码 回溯 day27

本文主要是介绍Day27 代码随想录(1刷) 回溯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

131. 分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 

回文串

 。返回  s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

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

 状态:完成

思路:目的是分割使每个子串都是回文串,所以用回溯来解决问题。用result来记录合理的分割方式,用path来装分割的子串,回溯中我们只要从startIndex开始就行了,每一次递归都判断该字串是否是回文串,是就继续不是就继续循环。

class Solution {List<List<String>> result=new ArrayList<>();LinkedList<String> path=new LinkedList<>();public List<List<String>> partition(String s) {backstracking(s,0);return result;}public void backstracking(String s,int startIndex){if(startIndex==s.length()){result.add(new ArrayList(path));}for(int i=startIndex;i<s.length();i++){String sub=s.substring(startIndex,i+1);if(isHui(sub)){path.add(sub);backstracking(s,i+1);path.removeLast();}}}public boolean isHui(String s){int left=0;int right=s.length()-1;while(left<right){if(s.charAt(left)!=s.charAt(right)){return false;}left++;right--;}return true;}
}

93. 复原 IP 地址

有效 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 仅由数字组成

状态:完成,wa了一次。

 思路:跟上一题差不多就是判断条件有区别,上一题是回文串这一题是判断这一部分是否不是0开始并且小于等于255.

class Solution {List<String> result=new ArrayList<>();StringBuilder sb=new StringBuilder();public List<String> restoreIpAddresses(String s) {sb.append(s);backstracking(0,0);return result;}public void backstracking(int startIndex,int level){String temp=sb.substring(startIndex,sb.length());if(level==3){temp=sb.substring(startIndex,sb.length());if(temp.length()==0||temp.length()>3) return;if(temp.startsWith("0")&&temp.length()>1) return;if(Integer.valueOf(temp)>255) return;result.add(sb.toString());}for(int i=1;startIndex+i<=sb.length()&&i<=3;i++){temp=sb.substring(startIndex,startIndex+i);if(i>1&&temp.startsWith("0")) break;if(Integer.valueOf(temp)>255) break;sb.insert(startIndex+i,".");backstracking(startIndex+i+1,level+1);sb.replace(startIndex+i,startIndex+i+1,"");}}
}

 78. 子集

给你一个整数数组 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 中的所有元素 互不相同

状态:完成

思路:求该数组的所有的子集,所以我们回溯的时候要传递一个startIndex的参数来限制,回溯结束的条件就是startIndex>=nums.length说明这时候就走到头了,跟之前的不一样他要求所有的子集所以每次添加之后直接放进结果数组中。

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {result.add(new ArrayList(list));backstracking(0,nums);return result;}public void backstracking(int startIndex,int[] nums){if(startIndex>=nums.length) return;for(int i=startIndex;i<nums.length;i++){list.add(nums[i]);result.add(new ArrayList(list));backstracking(i+1,nums);list.removeLast();}}
}

 90. 子集 II

给你一个整数数组 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

 状态:完成

思路:跟之前求和那题一样,只要使用used数组去做树层去重的判断就可以了。

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> list=new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);result.add(new LinkedList());backstracking(0,new boolean[nums.length],nums);return result;}public void backstracking(int startIndex,boolean[] used,int[] nums){if(startIndex>=nums.length) return;for(int i=startIndex;i<nums.length;i++){if(i>0&&nums[i-1]==nums[i]&&used[i-1]){used[i]=true;continue;}System.out.println(startIndex+" "+i+" "+list);list.add(nums[i]);used[i]=true;result.add(new LinkedList(list));backstracking(i+1,new boolean[nums.length],nums);list.removeLast();}}
}

 感想:重做回溯感觉良好,加快速度争取后天刷完。

这篇关于Day27 代码随想录(1刷) 回溯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

活用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

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 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can