南翔做网站公司,百度网络营销app下载,网站开发所用的技术,网站被js植入广告目录 93. 复原 IP 地址题目描述题解 78. 子集题目描述题解 90. 子集 II题目描述题解 93. 复原 IP 地址
点此跳转题目链接
题目描述
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用… 目录 93. 复原 IP 地址题目描述题解 78. 子集题目描述题解 90. 子集 II题目描述题解 93. 复原 IP 地址
点此跳转题目链接
题目描述
有效 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 仅由数字组成
题解
回溯算法解决整体思路和 131. 分割回文串 差不多可参见其 对应题解 。
需要注意的主要是一些细节方面的问题比如
分割成功的标志为 恰好分为4段每段都是[0, 255]之间的整数且不能有先导0 每次添加一段时还要添加 .回溯时要删除上次添加的整个子串和 .
代码实现如下思路及细节处理见注释
class Solution
{
private:string ip;vectorstring res;int partCount 0; // 有效ip地址应由4个部分组成bool isLegalIpPart(const string s) {if (s.size() 1 s[0] 0) // 不能含有前导0return false;if (s.size() 3) // 不能超过3位最大255return false;return stoi(s) 0 stoi(s) 255;}public:void backTracking(const string s, int cutPos) {// 递归出口分割位置到达字符串末尾或分割出大于4个部分纵向遍历if (partCount 4)return;if (cutPos s.size()) {if (partCount 4)res.push_back(ip.substr(1, ip.size() - 1)); // 注意ip开头的.要去除return;}// 横向遍历for (int i cutPos; i s.size(); i) {// 处理string sub s.substr(cutPos, i - cutPos 1);if (!isLegalIpPart(sub))continue;ip . sub;partCount;// 递归backTracking(s, i 1);// 回溯while (!ip.empty() ip.back() ! .) ip.pop_back(); // 删除上次添加的子串if (!ip.empty())ip.pop_back(); // 删除结尾的 .partCount--;}}vectorstring restoreIpAddresses(string s){backTracking(s, 0);return res;}
};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] 10nums 中的所有元素 互不相同
题解
用回溯算法解决和基本的 组合问题 框架差不多还是 处理、递归、回溯 的三部曲框架要注意的是 ⚠️
由于需要获得 所有 子集不用像一般组合问题那样在递归出口才将组合加入结果集而是每次递归过程中都将当前组合加入结果集。
代码C
class Solution
{
private:vectorint path;vectorvectorint res;public:void backTracking(const vectorint nums, int start){// 要求所有子集故每次都要将path加入结果集res.push_back(path);// 递归出口纵向遍历if (start nums.size())return;// 横向遍历for (int i start; i nums.size(); i){path.push_back(nums[i]); // 处理backTracking(nums, i 1); // 递归path.pop_back(); // 回溯}}vectorvectorint subsets(vectorint nums){backTracking(nums, 0);return res;}
};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
题解
这题在 78. 子集 的基础上多了一个条件 nums 中 可能包含重复元素 这就要求我们对子集结果进行去重。去重需要在搜索过程中解决具体思路和 40. 组合总和 II 如出一辙都是采用 used 数组解决可以移步我之前的笔记 40-题解(github) 或 40-题解(CSDN) 查看。
代码C
class Solution
{
private:vectorint path;vectorvectorint res;vectorint used;public:void backTracking(const vectorint nums, int start) {// 求全部子集每次都要将path加入结果集resres.push_back(path);// 递归出口纵向遍历if (start nums.size())return;// 横向遍历for (int i start; i nums.size(); i) {// 去重if (i 0 nums[i] nums[i - 1] !used[i - 1])continue;// 处理path.push_back(nums[i]);used[i] 1;// 递归backTracking(nums, i 1);// 回溯path.pop_back();used[i] 0;}}vectorvectorint subsetsWithDup(vectorint nums){used.resize(nums.size());sort(nums.begin(), nums.end()); // 先排序便于去重backTracking(nums, 0);return res;}
};
