93.复原IP地址
还是分割字符串类型的，不过path集合是一个完整的string，还要加.,注意size是会动态变化的。
- 用.来分割，由于path是完整的（当然也可以用vector存最后合并，我一开始就是这么做的），要用,的数量pointNum进行终止条件的判断
- 和day25 17.电话号码的字母组合一样，终止条件里 == s.size 要往下一位才结束
- 像这种string转int的，stoll还是有可能超，遍历string数组累加求和是最好的。
//C++ 自己想的，就是判断是否合理那先导0处理的不是很好
class Solution {
public:
vector<string> res;
vector<string> path;
vector<string> restoreIpAddresses(string s) {
BackTracking(s, 0);
return res;
}
void BackTracking(string s, int startIndex) {
if (path.size() == 4 && startIndex == s.size()) {
string ss = "";
for (int i = 0; i < path.size(); i++) {
ss += path[i];
if (i < 3) {
ss += ".";
}
}
res.push_back(ss);
return;
}
for (int i = startIndex; i < s.size(); i++) {
string sub = s.substr(startIndex, i - startIndex + 1);
if (isValid(sub)) {
path.push_back(sub);
BackTracking(s, i + 1);
path.pop_back();
}
}
}
bool isValid(string sub) {
int num = 0;
for (int i = 0; i < sub.size(); i++) {
if (sub[0] == '0' && sub.size() != 1) return false;
if (sub[i] > '9' || sub[i] < '0') return false;
num = num * 10 + (sub[i] - '0');
if (num > 255) return false;
}
//if (stoll(sub) > 255 || stoll(sub) < 0)
// return false;
return true;
}
};
C#string不可变构造不方便，虽然也可以用StringBuilder，最好用上面的方法。
//C#
public class Solution {
List<string> res = new List<string>();
List<string> path = new List<string>();
//string path;
public IList<string> RestoreIpAddresses(string s) {
BackTracking(s, 0);
return res;
}
void BackTracking(string s, int startIndex) {
if (path.Count == 4 && startIndex == s.Length) {
string ss = "";
for (int i = 0; i < path.Count; i++) {
ss += path[i];
if (i < 3) {
ss += ".";
}
}
res.Add(ss);
return;
}
for (int i = startIndex; i < s.Length; i++) {
string sub = s.Substring(startIndex, i - startIndex + 1);
if (isValid(sub)) {
path.Add(sub);
BackTracking(s, i + 1);
path.RemoveAt(path.Count - 1);
} else return;
}
}
bool isValid(string s) {
if (s[0] == '0' && s.Length != 1) return false;
int num = 0;
for (int i = 0; i < s.Length; i++) {
if (s[i] < '0' || s[i] > '9') return false;
num = num * 10 + (s[i] - '0');
if (num > 255) return false;
}
return true;
}
}
代随引入逗号做终止条件和分割，注意s因为加了逗号是在动态变化的,也就不需要path了，注意下isValid里面分割结果不为“”的判断，前面的方法因为保证了到最后已经分割了4个，不存在到第三个后面分割为空的情况，当分割到最后一个元素为单独一部分时(startIndex == size() - 1)，s.size() - 1 - startIndex = 1 [startIndex, s.size() - 1], 再往后分割左闭右闭区间的左边界会大于有边界，这时候分割出来的为"", 产生这种原因是终止条件里夹杂着最后一次分割的越界情况且只能根据逗号判断无法排除第三个逗号恰好分到末尾之后，要单独讨论。
class Solution {
public:
vector<string> res;
vector<string> restoreIpAddresses(string s) {
BackTracking(s, 0, 0);
return res;
}
void BackTracking(string s, int startIndex, int pointNum) {
if (pointNum == 3) {
if (isValid(s.substr(startIndex, s.size() - 1 - startIndex + 1)))
res.push_back(s);
return;
}
for (int i = startIndex; i < s.size(); i++) {
string sub = s.substr(startIndex, i - startIndex + 1);
if (isValid(sub)) {
s.insert(s.begin() + i + 1, '.');
pointNum++;
BackTracking(s, i + 2, pointNum);
pointNum--;
s.erase(s.begin() + i + 1);
} else return;
}
}
bool isValid(string sub) {
if (sub == "") return false;
if (sub[0] == '0' && sub.size() != 1) return false;
int num = 0;
for (int i = 0; i < sub.size(); i++) {
if (sub[i] > '9' || sub[i] < '0') return false;
num = num * 10 + (sub[i] - '0');
if (num > 255) return false;
}
return true;
}
};
78.子集
不需要做任何剪枝，只要保证不重复就行，搜到底，包含根节点的空集所以收集时提前。
3min秒了。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
BackTracking(nums, 0);
return res;
}
void BackTracking(vector<int>& nums, int startIndex) {
res.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();
}
}
};
90.子集II
和78.子集一样区别就是集合里有重复元素树层去重，4min秒了，注意去重需要先对集合排序让重复的元素相邻。
//C++ startindex区分树层去重
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
BackTracking(nums, 0);
return res;
}
void BackTracking(vector<int>& nums, int startIndex) {
res.push_back(path);
if (startIndex == nums.size()) return;
for (int i = startIndex; i < nums.size(); i++) {
if (i > startIndex && nums[i] == nums[i - 1]) {
//树层去重
continue;
}
path.push_back(nums[i]);
BackTracking(nums, i + 1);
path.pop_back();
}
}
};
本题也以不使用used数组来去重，因为递归的时候下一个startIndex是i+1而不是0。如果要是全排列的话，每次要从0开始遍历，为了跳过已入栈的元素，需要使用used。
//C# used区分树层去重
public class Solution {
IList<IList<int>> res = new List<IList<int>>();
List<int> path = new List<int>();
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
bool[] used = new bool[nums.Length];
BackTracking(nums, 0, used);
return res;
}
public void BackTracking(int[] nums, int startIndex, bool[] used) {
res.Add(new List<int>(path));
if (startIndex == nums.Length) return;
for (int i = startIndex; i < nums.Length; i++) {
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
continue;
}
path.Add(nums[i]);
used[i] = true;
BackTracking(nums, i + 1, used);
used[i] = false;
path.RemoveAt(path.Count - 1);
}
}
}
- 注意是used[i] 不是used[nums[i]]，used是用来看在这一条路当前点上面有没有用到过前一个节点，只有没用过时才是跨路的重复也就是层重复，要不就是枝重复，是允许集合中有重复元素的，但不能前一条路的分组包含这一条路。
- 二刷看看set去重。
京公网安备 11010502036488号