剑指 Offer II 回溯法
2024-10-21 11:55:01
086. 分割回文子字符串
用substr枚举 因为是连续的 不是放与不放的问题
class Solution {
public:
vector<vector<string>>ans;
vector<string>path;
bool check()
{
for(string x:path)
{
for(int i=0;i<x.size();i++)
{
if(x[i]!=x[x.size()-1-i])return false;
}
}
return true;
}
void dfs(int x,string s)
{
if(x==s.size())
{
if(check())ans.push_back(path);
return ;
}
for(int i=1;i<=s.size()-x;i++)
{
string z=s.substr(x,i);//x开始长度为i
path.push_back(z);
dfs(x+i,s);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
dfs(0,s);
return ans;
}
};
087. 复原 IP
剪枝
class Solution {
public:
vector<string>ans;
vector<string>path;
int tonum(string x)
{
int sum=0;
for(int i=0;i<x.size();i++)
{
sum=sum*10+x[i]-'0';
}
return sum;
}
bool check()
{
for(string x: path)
{
if(x.size()>3)return false;
if(x.size()>1&&x[0]=='0')return false;//前导0
if(tonum(x)>255)return false;//IP
}
return true;
}
void dfs(int x, string s)
{
if(x==s.size())
{
if(path.size()!=4)return ;
if(check())
{
string k;
for(string x:path)
{
k+=x;
k+=".";
}
k=k.substr(0,k.size()-1);
ans.push_back(k);
}
}
for(int i=1;i<=s.size()-x;i++)
{
string temp=s.substr(x,i);//以x为起点 长度为i的字符串放进去
path.push_back(temp);
dfs(x+i,s);
path.pop_back();
}
}
vector<string> restoreIpAddresses(string s) {
if(s.size()>4*3)return ans;//数据范围3000吓唬谁呢 255 255 255 255
dfs(0,s);//下标
return ans;
}
};
最新文章
- Codeforces558E A Simple Task（线段树）
- 基于服务（Web Service）的文件管理Winform客户端实现（二）
- matplotlib库的常用知识
- Osmocom-BB MOTO C118硬刷
- MySQL show master / slave status 命令参数
- 关于toncat的Invalid character found in the request target.The valid characters are defined in RFC 7230 and RFC3986
- [Java] SpringMVC工作原理之四：MultipartResolver
- Apache Commons Beanutils 一 （使用PropertyUtils访问Bean属性）
- JavaScript大杂烩11 - 理解事件驱动
- 2018.11.28 poj3294 Life Forms（后缀数组+双指针）
- Codeforces Round #528 Div. 1 自闭记
- C/C++与Java的区别
- 一个简单的增强型PHP curl函数
- java管道通信
- 翻转链表reverse linked list：全部，m~n
- OSC和GitHub中项目公钥和管理公钥
- Mongodb同步数据到hive（二）
- Codechef SEP14 QRECT cdq分治+线段树
- New Concept English there （25）
- PHP - 脚本退出（包括异常退出），执行指定代码