java - codingbat maxMirror 练习的问题

Question

所以基本上，我一直在研究这些 codingBat 问题，当我真的遇到困难时，我通常会检查解决方案并跟踪逻辑，这帮助我不会陷入后来使用类似想法的问题。

这个最大镜像问题对我个人来说不像其他问题；我不知道如何实际编写代码来解决它，即使形成算法对我来说也有点棘手

We'll say that a "mirror" section in an array is a group of contiguous elements such that somewhere in the array, the same group appears in reverse order. For example, the largest mirror section in {1, 2, 3, 8, 9, 3, 2, 1} is length 3 (the {1, 2, 3} part). Return the size of the largest mirror section found in the given array.

maxMirror({1, 2, 3, 8, 9, 3, 2, 1}) → 3
maxMirror({1, 2, 1, 4}) → 3
maxMirror({7, 1, 2, 9, 7, 2, 1}) → 2

现在，就算法而言，我想说的是，如果我们首先检查整个数组是否是镜像，如果不是，则将检查的区域大小减 1。但就伪代码和真实代码而言，我不知道。

Answer 1

在这种情况下，我的解决方案是您的代码应该始终手动执行，然后弄清楚我处理解决方案的本质。

对于这个问题，我发现自己在查看原始数组的可能子集，然后向后查看原始数组以查看是否可以再次找到相同的子集。

接下来，我将其翻译成伪代码，

for each segment in nums
   check if nums contains segment backwards

重复，但这次制定了更多实现细节。

for each segment in nums, starting with the largest
   reverse the segment
   check if nums contains reversed segment
   if it does, return the size of that segment

接下来，在伪代码中找到一些可能的候选方法并编写它们。我选择这样做是为了“反向”和“包含”:

private int[] reverse(int[] nums) {
   int[] rtn = new int[nums.length];
   for (int pos = 0; pos < nums.length; pos++) {
      rtn[nums.length - pos - 1] = nums[pos];
   }
   return rtn;
}

private boolean contains(int[] nums, int[] segment) {
   for (int i = 0; i <= nums.length - segment.length; i++) {
      boolean matches = true;
      for (int j = 0; j < segment.length; j++) {
         if (nums[i + j] != segment[j]) {
            matches = false;
            break;
         }
      }
      if (matches) return true;
   }
   return false;
}

最后，实现剩下的:

public int maxMirror(int[] nums) {
   for (int window = nums.length; window > 0; window--) {
      for (int pos = 0; pos <= nums.length - window; pos++) {

         int[] segment = new int[window];
         for (int innerpos = 0; innerpos < window; innerpos++) {
            segment[innerpos] = nums[pos + innerpos];
         }

         segment = reverse(segment);
         if (contains(nums, segment)) {
            return window;
         }
      }
   }
   return 0;
}