任务是编写一种方法,该方法使用二进制递归在不使用任何循环的情况下大量查找所有符号变化。符号变化由一对特殊字符元素给出,它们之间有零个或多个 0 值 元素。如果输入是
[0,0,4,0,0,0,0,0,0,0,-9,0,0,0]
输出必须是1,如果输入是[22,0,-9,8,-9,0,0,-12,18,0,28,0,25,0,25,0,10]
输出必须是4.
我已经使用一元递归完成了这个,但我不知道如何将这个问题“拆分”成更小的部分。 这是我使用一元递归的代码:
public class App {
// Tree recursion function wrapper
public static int unary(int[] a) {
// Add the correct starting parameters to the recursive function
return unary(a, 0, 1);
}
// Tree recursion function
public static int unary(int[] a, int i, int j) {
// Return 0 if the array can't possibly contain a sign change (array contains
// less then 2 elements) or we have reached the end of the array
if (a.length <= 1 || j >= a.length)
return 0;
// Visual representation of the steps:
// System.out.println(String.format("%d|%d - %d|%d", i, j, a[i], a[j]));
if (a[i] == 0) {
// If the first value in comparison is a zero, let's move to the next pair
// This is needed if the array starts with zeros, because once j finds a valid
// value, then for every next call i will have a valid value
return unary(a, i + 1, i + 2);
} else if (a[j] == 0) {
// If the second value in comparison is a zero let's keep the first value, but
// move the second value forward
// This is needed if the array has zeros between valid values or at the end
return unary(a, i, j + 1);
}
// Add either a zero or one to the value of the next function call
// When looking for the next pair to compare, we start looking at the end of the
// current pair, hence for the next call i = j
if (a[i] * a[j] < 0){
return 1 + unary(a, j, j+1);
}
return unary(a, j, j+1);
}
public static void main(String[] args) {
// Create test arrays
int[] a = {0,0,4,0,0,0,0,0,0,0,-9,0,0,0}; // Should return 1
int[] b = {22,0,-9,8,-9,0,0,-12,18,0,28,0,25,0,25,0,10}; // Should return 4
System.out.println(unary(a));
System.out.println(unary(b));
}
}