【 NO.1 两栋颜色不同且距离最远的房子】

解题思路

签到题，循环判断即可。

代码展示

class Solution {

   public int maxDistance(int[] colors) {

       for (int len = colors.length; len >= 1; len--) {

           for (int i = 0; i + len <= colors.length; i++) {

               if (colors[i] != colors[i + len - 1]) {

                   return len - 1;

              }

          }

      }

       return 0;

  }

}

【 NO.2 给植物浇水】

解题思路

模拟浇水过程即可。

代码展示

class Solution {

   public int wateringPlants(int[] plants, int capacity) {

       int res = 0;

       int water = capacity;

       for (int i = 0; i < plants.length; i++) {

           if (water < plants[i]) {

               water = capacity;

               res += i * 2;

          }

           res++;

           water -= plants[i];

      }

       return res;

  }

}

【 NO.3 区间内查询数字的频率】

解题思路

二分查找。统计出每个数字的所有出现位置，然后在位置列表上进行二分查找即可得到该列表中位于 [left, right] 范围的元素有多少个。

代码展示

class RangeFreqQuery {

   Map<Integer, List> pos;

   public RangeFreqQuery(int[] arr) {

       pos = new HashMap<>();

       for (int i = 0; i < arr.length; i++) {

           if (!pos.containsKey(arr[i])) {

               pos.put(arr[i], new ArrayList<>());

          }

           pos.get(arr[i]).add(i);

      }

  }

   public int query(int left, int right, int value) {

       if (!pos.containsKey(value)) {

           return 0;

      }

       List p = pos.get(value);

       int start = bSearch2(p, left);

       int end = bSearch(p, right);

       return end - start + 1;

  }

   // 二分查找最后一个 <= value 的元素下标

   int bSearch(List arr, int value) {

       if (arr.size() == 0 || value < arr.get(0)) {

           return -1;

      }

       int left = 0, right = arr.size() - 1;

       while (left + 1 < right) {

           int mid = (left + right) / 2;

           if (arr.get(mid) <= value) {

               left = mid;

          } else {

               right = mid;

          }

      }

       return arr.get(right) <= value ? right : left;

  }

   // 二分查找第一个 >= value 的元素下标

   int bSearch2(List arr, int value) {

       if (arr.size() == 0 || arr.get(arr.size() - 1) < value) {

           return arr.size();

      }

       int left = 0, right = arr.size() - 1;

       while (left + 1 < right) {

           int mid = (left + right) / 2;

           if (arr.get(mid) < value) {

               left = mid;

          } else {

               right = mid;

          }

      }

       return arr.get(left) < value ? right : left;

  }

}

【 NO.4 k 镜像数字的和】

解题思路

回溯法枚举即可。

代码展示

class Solution {

   int n;

   long sum;

   public long kMirror(int k, int n) {

       this.sum = 0;

       this.n = n;

       for (int len = 1; this.n > 0; len++) {

           // 长度为 len 的 k 进制的镜像数字

           char[] chars = new char[len];

           dfs(chars, 0, chars.length - 1, k);

      }

       return sum;

  }

   private void dfs(char[] chars, int i, int j, int k) {

       if (this.n == 0) {

           return;

      }

       if (i == j) {

           for (int p = 0; p < k; p++) {

               if (p == 0 && i == 0) {

                   continue;

              }

               chars[i] = (char) ('0' + p);

               dfs(chars, i + 1, j - 1, k);

          }

           return;

      }

       if (i > j) {

           long ten = Long.parseLong(String.valueOf(chars), k);

           String str = String.valueOf(ten);

           for (int l = 0, r = str.length() - 1; l < r; l++, r--) {

               if (str.charAt(l) != str.charAt(r)) {

                   return;

              }

          }

           this.n--;

           sum += ten;

           return;

      }

       for (int p = 0; p < k && this.n > 0; p++) {

           if (i == 0 && p == 0) {

               continue;

          }

           chars[i] = chars[j] = (char) ('0' + p);

           dfs(chars, i + 1, j - 1, k);

      }

  }

}