免费主机空间网站,网络建设公司不只是,莱芜贴吧论坛,魅姬直播算法#xff1a;
有很多分割结果#xff0c;按照for循环去做肯定做不来
这个时候就要想到回溯#xff01;那就要画树#xff01;
画树 分割的画树过程其实和组合很像。
例如对于字符串aab#xff1a;
组合问题#xff1a;选取一个a之后#xff0c;在ab中再去选取第…
算法
有很多分割结果按照for循环去做肯定做不来
这个时候就要想到回溯那就要画树
画树 分割的画树过程其实和组合很像。
例如对于字符串aab
组合问题选取一个a之后在ab中再去选取第二个选取a之后b中再选取第三个.....。切割问题切割一个a之后在ab中再去切割第二段切割a之后在b再切割第三段.....。
回溯三部曲
1.确定返回值和参数
返回值void
参数
string s 题目自带的
int startindex 确定每次递归从哪个字符开始切割
2.确定终止条件
切割到字符串最后就是终止
startindex就是切割线 startindex s.length()
并且要收集结果
3.单层递归逻辑
子串怎么表示的
答[startindex, i]
i是这样定义的
for (int i startIndex; i s.length(); i) 收集结果
若子串是回文要定义一个新的函数判断子串是否为回文
将子串add入path收集
若不是回文continue跳出该递归
递归
注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1
backtracking (s, i1)
回溯
弹出本次已经添加的子串
path.removeLast()
判断回文子串
最后我们看一下回文子串要如何判断了判断一个字符串是否是回文。
可以使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了。
调试过程
第一次调试
class Solution {//全局变量path和resultListListString result new LinkedList();ListString path new LinkedList();public ListListString partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件收集结果if (startindex s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文if (isplalindrome (s, startindex, i)){//若是加入pathpath.add (s[startindex, i]);}else {continue;}//递归backtracking (s, i1);//回溯path.removeLast();}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int i, int j; i s.length(), j i; i, j--){if (s[i] s[j]) return true;return false;}}
} 原因
1.path.add (s[startindex, i]); 这一行存在语法错误。想要将子串添加到 path 列表中。为了修正这个问题应该使用 substring 方法而不是方括号。修正后的代码应该是path.add(s.substring(startIndex, i 1));
在Java中方括号主要用于数组的索引访问而不用于提取子串方括号是适用于python的java不能用。
对于字符串提取子串可以使用substring方法该方法接受起始索引和结束索引作为参数以提取指定范围内的子串。[左闭右开
String str Hello, World!;
String sub str.substring(startIndex, endIndex);
在这里str是要提取子串的字符串startIndex是子串的起始索引endIndex是子串的结束索引不包括在内。提取的子串将包括从startIndex到endIndex-1的字符。
因此在您的代码中path.add(s.substring(startIndex, i 1));将会提取s字符串中从startIndex到i包括i的子串并将其添加到path列表中。
2.isPalindrome 方法中的for循环存在几个语法错误。看起来您想要在for循环中声明和初始化多个变量但是语法是不正确的。让我们进行以下更正
for (int i start, j end; i j; i, j--) { // ... (代码的其余部分)
}
在 Java 中当在 for 循环中声明多个变量时不需要在每个变量前都加上 int。
在 for 循环的初始化部分只需要在第一个变量声明前加上类型而后续的变量声明则只需要写变量名和初始值即可。
修改后 原因单层递归时忘记加for循环了 第二次调试 原因
string不能用方括号
应改为
s.charAt(i) s.charAt(j)
第三次调试 原因把字符串本身也输出了。
主要问题在判断回文的逻辑上
判断是否为xxx一定要先判错有错即错
当发现不是回文就要立刻false有不对的就不往下遍历了。一旦我们找到了一个不同的字符对我们就可以确定这个字符串不是回文因此可以立即返回 false。这样可以提前结束检查因为一旦发现不匹配就不需要继续向后检查。
我原来判断的是先判断前后是否相等若相等则true。
假设字符串是 “abca”。如果我们在检查第一个和最后一个字符相等时就提前返回 true那么我们会错误地认为 “abca” 是一个回文字符串因为我们没有检查中间的字符。而且当我们找到不同的字符时就无法及时结束检查而需要继续检查下去这会降低算法的效率。 正确代码
class Solution {//全局变量path和resultListListString result new LinkedList();ListString path new LinkedList();public ListListString partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件收集结果if (startindex s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文for (int istartindex; is.length();i){ if (isplalindrome (s, startindex, i)){//若是加入pathpath.add(s.substring(startindex, i1));}else {continue;}//递归backtracking (s, i1);//回溯path.removeLast();}}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int istart, jend; j i; i, j--){if (s.charAt(i) ! s.charAt(j)) return false; }return true;}
}
时间空间复杂度
