Day24- 回溯算法part04
2024-01-09 13:38:06
一、复原IP地址
题目一: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
?中的任何数字。你可以按?任何?顺序返回答案。
- 使用回溯法来生成所有可能的 IP 地址。
- 每个 IP 地址包含四段,每段的数字范围是 0 到 255。
- 检查每段数字是否合法(不包含前导零,除非该段为 0)。
restoreIpAddresses
函数初始化结果集合,并开始回溯。backtrack
函数进行回溯,递归地构建 IP 地址的每一段。- 检查每个段的合法性:不以零开头(除非是 0)并且小于等于 255。
- 当有 4 个合法段且遍历完整个字符串时,将其添加到结果集。
/*
* @lc app=leetcode.cn id=93 lang=cpp
*
* [93] 复原 IP 地址
*/
// @lc code=start
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> result;
vector<string> ipAddress;
backtrack(s, 0, ipAddress, result);
return result;
}
private:
void backtrack(const string& s, int start, vector<string>& ipAddress, vector<string>& result) {
if (ipAddress.size() == 4) {
if (start == s.size()) {
result.push_back(ipAddress[0] + "." + ipAddress[1] + "." + ipAddress[2] + "." + ipAddress[3]);
}
return;
}
for (int len = 1; len <= 3 && start + len <= s.size(); ++len) {
string segment = s.substr(start, len);
if ((segment.size() > 1 && segment[0] == '0') || stoi(segment) > 255) continue;
ipAddress.push_back(segment);
backtrack(s, start + len, ipAddress, result);
ipAddress.pop_back();
}
}
};
// @lc code=end
二、子集
题目一:78. 子集
给你一个整数数组?nums
?,数组中的元素?互不相同?。返回该数组所有可能的子集(幂集)。
解集?不能?包含重复的子集。你可以按?任意顺序?返回解集。
subsets
函数初始化结果列表,并开始回溯过程。backtrack
函数执行回溯。它以递归的方式添加或不添加当前元素,从而构建所有可能的子集。- 在每次递归调用中,当前构建的子集被添加到结果列表中。
- 对于
nums
中的每个元素,选择将其包含在当前子集中或不包含。- 当所有元素都被考虑过后,回溯过程结束,得到了所有可能的子集。
/*
* @lc app=leetcode.cn id=78 lang=cpp
*
* [78] 子集
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}
private:
void backtrack(const vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
result.push_back(current);
for (int i = start; i < nums.size(); ++i) {
current.push_back(nums[i]);
backtrack(nums, i + 1, current, result);
current.pop_back();
}
}
};
// @lc code=end
题目二:90. 子集II?
给你一个整数数组?nums
?,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集?不能?包含重复的子集。返回的解集中,子集可以按?任意顺序?排列。
subsetsWithDup
函数首先对输入数组进行排序。- 使用
backtrack
函数进行回溯,它以递归的方式构建子集。- 在每次递归调用中,添加当前构建的子集到结果列表中。
- 重要的一步是检查并跳过重复元素,这样确保不会生成重复的子集。
- 对于
nums
中的每个元素,决定是否将其包含在当前子集中。
/*
* @lc app=leetcode.cn id=90 lang=cpp
*
* [90] 子集 II
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}
private:
void backtrack(const vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
result.push_back(current);
for (int i = start; i < nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
current.push_back(nums[i]);
backtrack(nums, i + 1, current, result);
current.pop_back();
}
}
};
// @lc code=end
文章来源:https://blog.csdn.net/m0_66690787/article/details/135477154
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!