国家工程建设质量奖网站,米定制网的网站是那个公司做,校园活动策划案的范文,西安cms建站模板目录 一、做题心得
二、题目与题解
题目一#xff1a;93.复原IP地址
题目链接
题解#xff1a;回溯--分割问题
题目二#xff1a;78.子集
题目链接
题解#xff1a;回溯--子集问题
题目三#xff1a;90.子集II
题目链接
题解#xff1a;回溯--子集问题
三、小…目录 一、做题心得
二、题目与题解
题目一93.复原IP地址
题目链接
题解回溯--分割问题
题目二78.子集
题目链接
题解回溯--子集问题
题目三90.子集II
题目链接
题解回溯--子集问题
三、小结 一、做题心得
今天的题个人感觉第一道 93. 复原 IP 地址 - 力扣LeetCode还是挺有难度的虽然跟昨天打卡的分割回文串很相似但是自己做的时候还是有点吃力。后边两道题就很简单了感觉和前两天练的组合问题差不多个人感觉问题不大。
这里直接开始今天的题目吧。
二、题目与题解
题目一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.1681.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 20s 仅由数字组成 题解回溯--分割问题
这个题也是很明显的分割问题。 、
分析题意有效IP地址分为4个部分每一部分由.隔开每一部分都有限制要求这个限制要求往往会出现if从句如果复杂的话需要自定义函数
关键
1.自定义函数判断IP地址某部分是否有效即是否符合题目要求
2.如何截取字符串s的各种子串substr()函数
3.如何实现剪枝具体看代码三处--两处是特殊情况的单独处理一处是循环遍历对终止条件的缩小
4.终止条件是什么递归遍历完整个字符串的同时IP地址恰好被分为4个部分
想清楚上边四点这道题也就好解决了剩下的就跟昨天 131. 分割回文串 一个道理。
代码如下
class Solution {
public: vectorstring ans; vectorstring vec;bool isRange(string substring) { //判断字符串是否为有效IP地址的一部分if (substring.size() ! 1 substring[0] 0) { //前导0无效如012,023等等return false; } int num stoi(substring); //将字符串转化为数字字符串只包含数字不考虑负数return num 255; } void backtrack(string s, int start) { if (vec.size() 4 start s.size()) { //终止条件当vec中存储了4个部分并且刚好遍历完了整个字符串s时说明找到了一个有效的IP地址string ip ; for (int i 0; i vec.size(); i) { //vec每一部分结束后添加.最终结果存放在ip里ip vec[i]; if (i vec.size() - 1) { ip .; } } ans.push_back(ip); return; } if (start s.size() vec.size() ! 4) { //剪枝1当遍历完了整个s但IP地址部分数不为4时重新返回递归return;}for (int i start; i start 3 i s.size(); i) { //剪枝2i start 3表示IP地址每一部分不超过三位数string substring s.substr(start, i - start 1); //截取字符串start到i的子串if (!isRange(substring)) { continue;} vec.push_back(substring); backtrack(s, i 1); vec.pop_back(); } } vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) { //剪枝3不可能存在有效IP地址情况直接返回空向量return ans;}backtrack(s, 0); return ans; }
};
题目二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] 10nums 中的所有元素 互不相同 题解回溯--子集问题 子集问题个人感觉跟组合问题差不多可能最大的不同就在于终止条件那里。
这里我们需要注意了对于对于子集问题当我们要得到一个数组集合的全部子集其实是没有终止条件的当然你也可以想成有就是全部都自然遍历添加完不过这其实跟没有也没区别也就是说我们只需要把每一个递归得到的数组添加到结果里边去即可。这里就要求我们对模板的有效运用了不要没有终止条件就硬想半天。
代码如下
class Solution {
public:vectorvectorint ans;vectorint vec;void backtrack(vectorint nums, int start) {ans.push_back(vec); //注意所有子集都要添加没有终止条件限制 for (int i start; i nums.size(); i) {vec.push_back(nums[i]);backtrack(nums, i 1);vec.pop_back();} }vectorvectorint subsets(vectorint nums) {backtrack(nums, 0);return ans;}
};题目三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 题解回溯--子集问题
这个题算是上面那道的进化版吧不过思路也差不多只是数组里出现了重复元素而要求结果中不能出现重复子集--这不就和昨天打卡不能出现重复组合一样了对数组排序 跳过数组相邻相同的元素横向同层处理使结果不出现重复子集。
不理解的话可以看看昨天的打卡内容这里就不做分析了。
代码如下
class Solution {
public:vectorvectorint ans;vectorint vec;void backtrack(vectorint nums, int start) {ans.push_back(vec);for (int i start; i nums.size(); i) {if (i start nums[i] nums[i - 1]) { //横向去重用以跳过同一树层使用过的重复元素continue; //注意这里是continue而不是breakbreak会直接跳出循环这样一旦出现重复元素会完全停止遍历剩余的元素这会导致生成的子集不完整}vec.push_back(nums[i]);backtrack(nums, i 1);vec.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end()); //先排序这样重复的元素就会相邻backtrack(nums, 0);return ans;}
};
三、小结
今天的打卡就到此结束了后边也会继续加油。最后我是算法小白但也希望终有所获。
