递归搜索数组 - CodingBat

Question

抱歉标题含糊不清，我想不出更具体的东西。

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

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);
     } 
}

递归搜索数组 - CodingBat

Searching an array recursively - CodingBat

java

arrays

algorithm

recursion