北京通州做网站,网站开发与建设课程设计,娄底网站建设的话术,网站开发 如何定位目录
前言#xff1a;
131. 分割回文串
题目描述#xff1a;
输入输出描述#xff1a;
思路和想法#xff1a;
93. 复原 IP 地址
题目描述#xff1a;
输入输出描述#xff1a;
思路和想法#xff1a; 前言#xff1a; 回溯算法中的分割问题#xff0c;是可以…目录
前言
131. 分割回文串
题目描述
输入输出描述
思路和想法
93. 复原 IP 地址
题目描述
输入输出描述
思路和想法 前言 回溯算法中的分割问题是可以抽象为组合问题的其中模拟切割线、切割问题中递归如何终止以及递归循环中如何截取子串是我们应该比较关注的。
131. 分割回文串
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入输出描述
示例1
输入s aab 输出[[a,a,b],[aa,b]]
示例2
输入s a 输出[[a]] 提示
1 s.length 16s 仅由小写英文字母组成
思路和想法
这里的问题可以大致分为两个切割方式问题以及回文串判断。
这里的切割方式问题可以抽象为树形结构第一层切割一刀切割位置的遍历切割线。第二层在原基础上再切割一刀。
这里的切割线可以对应上组合问题的Index之后就是表示切割后的子串---[Indexi]。
最后确立了切割后的子串判断其是否为回文子串如果是就添加到path里。
#include bits/stdc.husing namespace std;
/** 作者希希雾里* 131. 分割回文串* */
vectorvectorstring result;
vectorstring path;/** 函数 isPalindrome()* 功能 判断回文子串* */
bool isPalindrome(const string s,int start,int end){for (int i start, j end; i j; i, j--) {if(s[i] ! s[j]){return false;}}return true;
}
/** 函数 backtracing* 输入参数 s输入的字符串 index数组元素下标* */
void backtracing(const string s,int Index){//终止条件if(Index s.size()){result.push_back(path);return;}//回溯过程for (int i Index; i s.size(); i) {if (isPalindrome(s, Index, i)) {string str s.substr(Index, i - Index 1);path.push_back(str);} else {continue;}backtracing(s, i 1);path.pop_back();}
};int main() {result.clear();path.clear();string s;getline(cin,s);backtracing(s,0);cout [;for (int i 0; i result.size(); i) {cout [;for (int j 0; j result[i].size(); j) {cout result[i][j];if(j ! result[i].size() - 1) cout ,;}cout ];if(i ! result.size() - 1) cout ,;}cout ];return 0;
}/* 测试样例
aaba** */93. 复原 IP 地址
题目描述
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。
给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
输入输出描述
示例1
输入s 25525511135 输出[255.255.11.135,255.255.111.35]
示例2
输入s 0000 输出[0.0.0.0]
示例3
输入s 101023 输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3] 提示
1 s.length 20s 仅由数字组成
思路和想法
这道题目和上一道题的思路非常的类似。着重解决两个问题切割方式问题以及判断IP地址是否有效。
#include bits/stdc.husing namespace std;
/** 作者希希雾里* 93. 复原IP地址* */
vectorstring result;/** 函数 isrealIP()* 功能 判断IP地址是否有效* */
bool isrealIP(const string s,int start,int end){if(end start){return false;}if(end - start 1 s[start] 0){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;
}
/** 函数 backtracing* 输入参数 s输入的字符串 index数组元素下标 pointnum:逗号点数* */
void backtracing(string s,int Index,int pointnum){//终止条件if(pointnum 3){if (isrealIP(s,Index,s.size() - 1)){result.push_back(s);}return;}//回溯过程for (int i Index; i s.size(); i) {if (isrealIP(s,Index,i)){s.insert(s.begin() i 1,.);pointnum;backtracing(s,i 2,pointnum); //递归下一段pointnum--;s.erase(s.begin() i 1);}else break;}
};int main() {result.clear();string s;getline(cin,s);backtracing(s,0,0);cout [;for (int i 0; i result.size(); i) {for (int j 0; j result[i].size(); j) {cout result[i][j];}if(i ! result.size() - 1) cout ,;}cout ];return 0;
}/* 测试样例
255255111350000101023** */
