代码随想录Day28
93.复原IP地址
思考:本质上还是一种切割问题。
// 时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。
// 空间复杂度: O(n)
class Solution {
public:
vector<string> result;
// 判断字符串s在[start, end]上的数字是否符合IP要求
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
// 不能以0开头
if (s[start] == '0' && start != end) {
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) {
return false;
}
}
return true;
}
void backtracking(string& s, int startIndex, int pointNum) {
// 逗号分隔符的数量为3个,分割结束,来到最后一个区间
if (pointNum == 3) {
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)) {
// 在区间之后插入'.'
s.insert(s.begin() i 1, '.');
pointNum ;
backtracking(s, i 2, pointNum);
pointNum--;
s.erase(s.begin() i 1);
} else break;
}
}
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() < 4 || s.size() > 12) {
return result;
}
backtracking(s, 0, 0);
return result;
}
};
78.子集
// 时间复杂度: O(n * 2^n)
// 空间复杂度: O(n)
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
// 收集子集,要放在终止添加的上面,否则会漏掉自己
// 进来先push个空集
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();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
90.子集II
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>used) {
result.push_back(path);
if (startIndex >= nums.size()) {
return;
}
for (int i = startIndex; i < nums.size(); i) {
// used[i - 1] == false ——>同一层去重
// used[i - 1] == true ——>同一枝干去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
} else {
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i 1, used);
used[i] = false;
path.pop_back();
}
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, 0, used);
return result;
}
};
class Solution1 {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i ) {
// 而我们要对同一树层使用过的元素进行跳过
if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
continue;
}
path.push_back(nums[i]);
backtracking(nums, i 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0);
return result;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgbafih
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01