博客网站开发思维导图,网站开发动静分离实践,北京二级建造师查询系统,用v9做的网站上传服务器#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 复原 IP 地址子集子集 II总… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 复原 IP 地址子集子集 II总结 复原 IP 地址
93. 复原 IP 地址 - 力扣LeetCode
复原IP地址这道题也是一道切割字符串的问题也是略有难度的一道题起初我做的时候想不通是怎么精确的把字符串分割成四段做终止条件的后来看了题解知道并不是一开始就能够确定切出多大一块而是一点点试错的虽然我们知道是要将该字符串序列分成四份由三个点分割开来但是我们代码实现时候是无法做到一开始就确定前半部分是切割前几个数字的这是因为字符串序列可能是不一样的题目要求数字前面不能由前导0构成只有0是可以的且每一块分割出来的数字大于等于0小于等于255由于字符序列的不同有的时候我们第一次只能切一个数字就是0的情况0不能做前导有的时候我们可以多切一点这是无法固定的所以我们要一点点切割递归下去好在我们有函数递归可以帮助我们完成这一难题。
其他的困难部分我们在上一期的切割回文子串已经讲的差不多了无非也就是如何表示切割线如何传进去切割区间做判断不明白可以去看上一期。
区别在于这道题的终止判断条件也是有所不同的它的终止条件是我们已经放入了三个逗点做分割了这时候我们进入终止判断分割问题通常都是由题目要求的关键信息作为终止条件它和这几期做的那些组合题不一样不是固定的套路需要自行想出。
class Solution {
private:vectorstring result;// 记录结果// startIndex: 搜索的起始位置pointNum:添加逗点的数量void backtracking(string s, int startIndex, int pointNum) {if (pointNum 3) { // 逗点数量为3时分隔结束// 判断第四段子字符串是否合法如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i startIndex; i s.size(); i) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点pointNum;backtracking(s, i 2, pointNum); // 插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯s.erase(s.begin() i 1); // 回溯删掉逗点} else break; // 不合法直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string s, int start, int end) {if (start end) {return false;}if (s[start] 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s[i] 9 || s[i] 0) { // 遇到非数字字符不合法return false;}num num * 10 (s[i] - 0);if (num 255) { // 如果大于255了不合法return false;}}return true;}
public:vectorstring restoreIpAddresses(string s) {result.clear();if (s.size() 4 || s.size() 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};还有三点需要注意的细节第一点是除了在for循环里要判断该切割区间是否合法我们在终止条件还要额外判断一次这为什么呢原因在于我们终止条件是三个逗点就插入字符串而我们之前只是判断了三次切割串是否合法因为判断一次要放一个标点所以肯定是只判断了三次我们在这里加一次判断的目的是为了知道这最后剩余的部分是否依然具有合法性。第二点是字符串的insert成员函数插入标点是传入下标的前一个位置所以要进行1传入而且我们在进行递归下一层时传入的下一层开始遍历起始位置是i2而不是i1因为加入了一个标点的缘故。第三点是判断部分代码的细节下面的for循环来依次取各个数相加判断和是否大于255其实这里的要点主要在于对每一个字符的判断防止它是字符1-9之外的数但是leetcode上已经明确说了传入的都是数字序列可是题目仍然要求判断感觉可能是题目描述没有全改过来的缘故。
子集
78. 子集 - 力扣LeetCode
子集问题和前面讲过很多的组合问题解法如出一辙只是在处理数据加入结果集里有所不同。
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {result.push_back(path); // 收集子集要放在终止添加的上面否则会漏掉自己if (startIndex nums.size()) { // 终止条件可以不加return;}for (int i startIndex; i nums.size(); i) {path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}
public:vectorvectorint subsets(vectorint nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};和组合问题一样需要注意的是处理数据是每一次都将节点放入结果数组因为求的是子集要保留所有的节点每一个节点都是它的子集所以不存在剪枝操作。那空集是如何放入的呢实际上就是没有节点时候直接放入了path这一点也很好理解。单层递归是用一个for循环这一点就是组合的内容不懂的可以翻看前面组合的章节。
子集 II
90. 子集 II - 力扣LeetCode
子集II整体代码和子集差不多只是加入了组合的去重逻辑。
class Solution {
public:vectorvectorintresult;vectorintpath;void backtraking(vectorintnums,int start,vectorintnums2){result.push_back(path);for(int istart;inums.size();i){if(i1nums[i]nums[i-1]nums2[i-1]0)continue;nums2[i]1;path.push_back(nums[i]);backtraking(nums,i1,nums2);path.pop_back();nums2[i]0;}}vectorvectorint subsetsWithDup(vectorint nums) {vectorintnums2(nums.size(),0);sort(nums.begin(),nums.end());backtraking(nums,0,nums2);return result;}
};用一个辅助数组记录我们所要添加数的数组各个数字的加入情况。这里再简单讲一下去重的逻辑画一个树形图辅助理解当我们在一个数组里加入元素这道题说是给定数组有重复元素当我们构成一个答案数据时候i由于每次递归会i1走到下一个数据位置作为下一次放元素的起始位置所以我们不需要担心会一个数据取两次但是如果有两个数据我们第一次用到它取的一系列答案数据再你第二次用到的时候会将这些答案数据又取一次因为第一次用的这个数字包含了你第二次用的时候取到的全部答案了这一点画出树形图很容易理解所以要将它去掉也就是去重的逻辑需要做的是将给定数组排序让重复数据挨在一起然后用一个数组去辅助做判断如果本次要放入的数据和上一个位置数据值相等且上一个相等数据本次没有放入则说明我们要删除它这是数层上的去重逻辑。
总结
今天我们完成了复原 IP 地址、子集、子集 II三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
