java - 递归搜索数组 - CodingBat

Question

对于模棱两可的标题，我深表歉意，我想不出更具体的东西。

为了更好地递归解决问题，我一直在处理 CodingBat 上发布的问题.我的问题与以下问题的变体有关。

original problem是:

Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

• array220({1, 2, 20}, 0) → true
• array220({3, 30}, 0) → true
• array220({3}, 0) → false

我对这个问题的解决方案是:

public boolean array220(int[] nums, int index) {
  if (index >= nums.length-1) return false;

  if (nums[index+1] == nums[index] * 10) return true; 

  return array220(nums, ++index);
}

但是，为了挑战自己，我想知道我将如何着手解决我设想的这个问题的以下变体:

Given an array of ints, compute recursively if the array contains somewhere a value that is 10 times larger than any other value. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

For example:

• array220({1, 2, 10}, 0) → true
• array220({3, 2, 9, 38, 20}, 0) → true
• array220({3}, 0) → false

基本上，与原始问题的区别在于值不一定彼此相邻(参见上面的示例)。

我将如何递归执行此操作？我将不胜感激。

我不想更改方法签名或使用全局变量。

Answer 1

这可能是答案，只需使用 HashSet，并在进行递归调用时传递它:

public boolean array220(int[] nums,HashSet<Integer> set,  int index) {
  if (index >= nums.length-1) return false;

  if (set.contains(nums[index]*10)) 
      return true; 
  set.add(nums[index]);
  return array220(nums,set, ++index);
}

如果您不想使用额外的数据结构，排序数组和使用二进制搜索可以为您带来 O(nlogn) 的解决方案，具有两种递归方法。

Arrays.sort(nums);

public boolean array220(int[] nums,  int index) {
  if (index >= nums.length-1) return false;

  if (binarySearch(index + 1, nums.length - 1,nums[index]*10,nums)) 
      return true; 

  return array220(nums, ++index);
}

public boolean binarySearch(int start, int end,int value, int[] nums){
     if(start > end)
        return false;
     int mid = (start + end)/2;
     if(nums[mid] == value){
         return true;
     }else if(nums[mid] > value){
         return binarySearch(start, mid - 1, value, nums);
     }else{
         return binarySearch(mid + 1, end, value, nums);
     } 
}

如果您不想对数组进行排序，使用线性递归搜索将给出 O(n^2) 的解决方案。

public boolean array220(int[] nums,  int index) {
  if (index >= nums.length-1) return false;

  if (linearSearch(0,nums[index]*10,nums)) 
      return true; 

  return array220(nums, ++index);
}

public boolean linearSearch(int start, int value, int[] nums){
     if(start >= nums.length)
        return false;

     if(nums[start] == value){
         return true;
     }else {
         return linearSearch(start + 1, value, nums);
     } 
}