如何通过算法练习-day23掌握长尾词的运用技巧？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1276个文字，预计阅读时间需要6分钟。
回溯算法+93.+复原IP+地址+主题：有效IP+地址+正确由四个整数（每个整数位处于0到255之间，且不能有前导0）组成，且不能用'.'分隔。例如：220.1.2.201和192.168.1.1是有效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地址是否合法
首先是插入和删除部分，我们可以使用库函数insert和erase轻松搞定，但是在插入和删除操作前，需要判断插入是否合适，不合适直接跳过该层循环
其次是判断IP地址，这里需要满足三点：
- 0字符不能是首字符
- 字符串显示的数字不能大于255
- 字符串中出现非数字字符
这三种情况全部排除，才是合法的IP字段
且在保存字段时，由于我们只判断了三个区间，因此还需要对第四个区间进行合法判断才能保存
C++代码：
vector<string> arr;
bool JudgIP(string s,int left,int right)//这里需要判断IP的字段是否合法
{
if(left>right||(s[left]=='0'&&left!=right))//当区间非法，区间首元素为0时都是非法的
{
return false;
}
int sum=0;
for(int i=left;i<=right;i++)
{
if(s[i]<'0'||s[i]>'9')//当出现不为数字的字符，非法
{
return false;
}
sum=sum*10+s[i]-'0';
if(sum>255)//当区间大小大于255时，非法
{
return false;
}
}
return true;
}
void RecvIP(string s,int begin,int points)
{
if(points==3)//当.为三个，说明前三个IP区间正确，在判断第四个正确即可保存
{
if(JudgIP(s,begin,s.size()-1))
{
arr.push_back(s);
}
return;
}
for(int i=begin;i<s.size();i++)
{
if(JudgIP(s,begin,i))//这里只能判断三个IP字段是否合法，合法将。加入其中，i向后移动两格开始
{
s.insert(s.begin()+i+1,'.');
points++;
RecvIP(s,i+2,points);
points--;
s.erase(s.begin()+i+1);
}
else//不对，直接跳出整层回溯
{
break;
}
}
}
vector<string> restoreIpAddresses(string s) {
RecvIP(s,0,0);
return arr;
}
78. 子集
题意：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
示例：
思路：本题我们的思想很简单，就是在每次遍历时都存储组合，且遍历必须不重复，代码也比较简单，如下所示
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComSubset(vector<int>& nums,int begin)
{
arr.push_back(tmp);//这里解决了两个问题：1.保存空数组 2.将每次遍历到的组合都保存到且不重复
if(begin>=nums.size())
{
return;
}
for(int i=begin;i<nums.size();i++)//这样遍历就不会遍历到重复的组合
{
tmp.push_back(nums[i]);
ComSubset(nums,i+1);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
ComSubset(nums,0);
return arr;
}
90. 子集 II
题意：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例：
思路：本题思路和40. 组合总和 II的思路一模一样，这里就不细说了。我们再插入时只需要主要，本题是没有明确的递归结束条件的，我们只需要for循环完毕，递归结束，而存储数组需要在每次循环时都进行操作
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComSubset(vector<int>& nums,int begin,vector<bool> block)
{
arr.push_back(tmp);
for(int i=begin;i<nums.size();i++)
{
if(i>0&&block[i-1]==false&&nums[i-1]==nums[i])
{
continue;
}
tmp.push_back(nums[i]);
block[i]=true;
ComSubset(nums,i+1,block);
block[i]=false;
tmp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> block(nums.size(),false);
sort(nums.begin(),nums.end());
ComSubset(nums,0,block);
return arr;
}
本文共计1276个文字，预计阅读时间需要6分钟。
回溯算法+93.+复原IP+地址+主题：有效IP+地址+正确由四个整数（每个整数位处于0到255之间，且不能有前导0）组成，且不能用'.'分隔。例如：220.1.2.201和192.168.1.1是有效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地址是否合法
首先是插入和删除部分，我们可以使用库函数insert和erase轻松搞定，但是在插入和删除操作前，需要判断插入是否合适，不合适直接跳过该层循环
其次是判断IP地址，这里需要满足三点：
- 0字符不能是首字符
- 字符串显示的数字不能大于255
- 字符串中出现非数字字符
这三种情况全部排除，才是合法的IP字段
且在保存字段时，由于我们只判断了三个区间，因此还需要对第四个区间进行合法判断才能保存
C++代码：
vector<string> arr;
bool JudgIP(string s,int left,int right)//这里需要判断IP的字段是否合法
{
if(left>right||(s[left]=='0'&&left!=right))//当区间非法，区间首元素为0时都是非法的
{
return false;
}
int sum=0;
for(int i=left;i<=right;i++)
{
if(s[i]<'0'||s[i]>'9')//当出现不为数字的字符，非法
{
return false;
}
sum=sum*10+s[i]-'0';
if(sum>255)//当区间大小大于255时，非法
{
return false;
}
}
return true;
}
void RecvIP(string s,int begin,int points)
{
if(points==3)//当.为三个，说明前三个IP区间正确，在判断第四个正确即可保存
{
if(JudgIP(s,begin,s.size()-1))
{
arr.push_back(s);
}
return;
}
for(int i=begin;i<s.size();i++)
{
if(JudgIP(s,begin,i))//这里只能判断三个IP字段是否合法，合法将。加入其中，i向后移动两格开始
{
s.insert(s.begin()+i+1,'.');
points++;
RecvIP(s,i+2,points);
points--;
s.erase(s.begin()+i+1);
}
else//不对，直接跳出整层回溯
{
break;
}
}
}
vector<string> restoreIpAddresses(string s) {
RecvIP(s,0,0);
return arr;
}
78. 子集
题意：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
示例：
思路：本题我们的思想很简单，就是在每次遍历时都存储组合，且遍历必须不重复，代码也比较简单，如下所示
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComSubset(vector<int>& nums,int begin)
{
arr.push_back(tmp);//这里解决了两个问题：1.保存空数组 2.将每次遍历到的组合都保存到且不重复
if(begin>=nums.size())
{
return;
}
for(int i=begin;i<nums.size();i++)//这样遍历就不会遍历到重复的组合
{
tmp.push_back(nums[i]);
ComSubset(nums,i+1);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
ComSubset(nums,0);
return arr;
}
90. 子集 II
题意：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例：
思路：本题思路和40. 组合总和 II的思路一模一样，这里就不细说了。我们再插入时只需要主要，本题是没有明确的递归结束条件的，我们只需要for循环完毕，递归结束，而存储数组需要在每次循环时都进行操作
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComSubset(vector<int>& nums,int begin,vector<bool> block)
{
arr.push_back(tmp);
for(int i=begin;i<nums.size();i++)
{
if(i>0&&block[i-1]==false&&nums[i-1]==nums[i])
{
continue;
}
tmp.push_back(nums[i]);
block[i]=true;
ComSubset(nums,i+1,block);
block[i]=false;
tmp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> block(nums.size(),false);
sort(nums.begin(),nums.end());
ComSubset(nums,0,block);
return arr;
}