令 w 为长度为 n 的数组。用java写一个分治算法,判断3个连续相同字符出现的次数。下面是我写的算法。答案应该是 5 但它给了我一个 0。任何人都可以发现错误吗? 给定 w = abrabbbcccccfhdddgfr 算法应返回 5,因为它满足 3 个连续相同字符的 5 次出现:1 次 bbb,3 次 ccc e 1 次 ddd
public class Test {
public static void main (String[] args){
char[] w = {'a','b','r','a','b','b','b','c','c','c','c',
'c','f','h','d','d','d','g','f','r'};
System.out.println(conta_triple_main(w));
}
public static int conta_triple_main(char[] w){
if (w.length <= 2)
return 0;
else
return conta_triple(w, 0, w.length-1);
}
public static int conta_triple(char[] w, int i, int f){
int m,result;
if( i >= f-1)
return 0;
else {
m = (i + f)/2;
int sx = conta_triple(w, i, m);
int dx = conta_triple(w, m+1, f);
result = sx + dx;
if ((m >= w.length-1) && (w[m-1] == w[m]) && (w[m] == w[m+1]))
result++;
if ((m >= w.length-2) && (w[m] == w[m+1]) && (w[m+1] == w[m+2]))
result++;
}
return result;
}
}
最佳答案
这个
if ((m >= w.length-1) && (w[m-1] == w[m]) && (w[m] == w[m+1]))
result++;
应该是
if ((m-1 >= i) && (m+1 <= f) && (w[m-1] == w[m]) && (w[m] == w[m+1]))
result++;
与下一个 if 语句类似。
最后,您需要检查 (w[m] == w[m-1]) && (w[m] == w[m-2])
。
关于java - 分而治之算法 [字符数组],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19932424/