k*****o
发帖数: 1972 | 1 下面这段代码有什么错？
leetcode的一个问题，
最小cut次数，调试不出来，
请教一下，谢谢
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int cut_times=0;
return cut_times=cal_cut(s,cut_times);
};//minCut
//////
int cal_cut(string s, int cut_times){
int a,b;
string s1,s2;
s1=longestPalindrome(s);
a=s.find(s1,0);
b=s1.length()+a-1;
//左边留下的字符
if (a>0) {
cut_times++;
s2=s.substr(0,a);
cut_times=cal_cut(s2, cut_times);
}
//右边留下的字符
if (b
cut_times++;
s2=s.substr(b+1,s.length()-b-1);
cut_times=cal_cut(s2, cut_times);
}
return cut_times;
};//cal_cut | w******j
发帖数: 185 | 2 public int minCut(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(isvalid(s)) return 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < s.length() - 1; i++)
{
int cut = minCut(s.substring(0, i + 1)) + minCut(s.substring(i +
1)) + 1;
min = Math.min(min, cut);
}
return min;
}
这样行吗 | p*****p
发帖数: 379 | 3 你这个代码看着就头疼，基本的缩进都没有
没看出来哪里min了，cut_times好像只会增加
就算代码是对的，用递归写的dp复杂度是n！吧，得用循环
【在 k*****o 的大作中提到】
: 下面这段代码有什么错？
: leetcode的一个问题，
: 最小cut次数，调试不出来，
: 请教一下，谢谢
: int minCut(string s) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int cut_times=0;
: return cut_times=cal_cut(s,cut_times);
: };//minCut
| k*****o
发帖数: 1972 | 4 谢谢，我试试
+
【在 w******j 的大作中提到】
: public int minCut(String s) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(isvalid(s)) return 0;
: int min = Integer.MAX_VALUE;
:
: for(int i = 0; i < s.length() - 1; i++)
: {
: int cut = minCut(s.substring(0, i + 1)) + minCut(s.substring(i +
: 1)) + 1;
| k*****o
发帖数: 1972 | 5 循环？我试试
思路：找最大的回文，如果再中间，cut两次，
否则一次。
不过每次找到最大的回文，确实有可能不能确保最后答案是最优的,
学习了。
有几个大数据测试通不过，所以纠结了一下
【在 p*****p 的大作中提到】
: 你这个代码看着就头疼，基本的缩进都没有
: 没看出来哪里min了，cut_times好像只会增加
: 就算代码是对的，用递归写的dp复杂度是n！吧，得用循环
|
|
