网站转化率低的原因,西安有几个区,广东建设银行网站首页,国外哪些网站是python做的文档链接#xff1a;https://programmercarl.com/
LeetCode131.分割回文串
题目链接#xff1a;https://leetcode.cn/problems/palindrome-partitioning/
思路#xff1a;把回溯的树画出来就好很多。startIndex用来控制切割的位置
例如对于字符串abcdef#xff1a;
组…文档链接https://programmercarl.com/
LeetCode131.分割回文串
题目链接https://leetcode.cn/problems/palindrome-partitioning/
思路把回溯的树画出来就好很多。startIndex用来控制切割的位置
例如对于字符串abcdef
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段.....。
感受出来了不
切割问题类似组合问题。
回溯
class Solution {
public:vectorstring path;vectorvectorstring result;void backtracking(const string s, int startIndex) {if(startIndex s.size()) {result.push_back(path);return ;}for(int i startIndex; i s.size(); i) {if(isPalindrome(s, startIndex, i)) {string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else continue;backtracking(s, i 1);path.pop_back();}}bool isPalindrome(const string s, int start, int end) {while(start end) {if(s[start] ! s[end]) return false;start;end--;}return true;}vectorvectorstring partition(string s) {backtracking(s, 0);return result;}
}; LeetCode93.复原IP地址
题目链接https://leetcode.cn/problems/restore-ip-addresses/
思路同上一题思路基本一致。只不过需要另设pointNum变量记录一下.的个数从而达到终止条件。这题巩固了insert和erase函数使用。
回溯
class Solution {
public:vectorstring result;void backtracking(string s, int startIndex, int pointNum) {if(pointNum 3) {if(isValid(s, startIndex, s.size() - 1)) {result.push_back(s);return ;}}for(int i startIndex; i s.size(); i) {if(isValid(s, startIndex, i)) {s.insert(s.begin() i 1, .);pointNum;backtracking(s, i 2, pointNum);s.erase(s.begin() i 1);pointNum--;} else break;}}bool isValid(string s, int start, int end) {if(start end) return false;if(s[start] 0 start ! end) return false;int num 0;for(int i start; i end; i) {num num * 10 (s[i] - 0);if(num 255) return false;}return true;}vectorstring restoreIpAddresses(string s) {backtracking(s, 0, 0);return result;}
};
问题
总结受益匪浅路还很长继续努力。
