【 NO.1 反转两次的数字】

解题思路

通过不断 %10 取最后一位即可反转数字。

代码展示

class Solution {

   public boolean isSameAfterReversals(int num) {

       return reverse(reverse(num)) == num;

  }

   int reverse(int num) {

       int ret = 0;

       for (; num > 0; num /= 10) {

           ret = ret * 10 + (num % 10);

      }

       return ret;

  }

}

【 NO.2 执行所有后缀指令】

解题思路

模拟执行即可。

代码展示

class Solution {

   int[] dx, dy;

   public int[] executeInstructions(int n, int[] startPos, String s) {

       dx = new int[256];

       dy = new int[256];

       dy['L'] = -1;

       dy['R'] = 1;

       dx['U'] = -1;

       dx['D'] = 1;

       int[] result = new int[s.length()];

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

           result[i] = execute(n, startPos, s.substring(i));

      }

       return result;

  }

   int execute(int n, int[] startPos, String s) {

       int x = startPos[0], y = startPos[1];

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

           char c = s.charAt(i);

           x += dx[c];

           y += dy[c];

           if (x < 0 || x >= n || y < 0 || y >= n) {

               return i;

          }

      }

       return s.length();

  }

}

【 NO.3 相同元素的间隔之和】

解题思路

记录每种值出现的所有位置，将这些位置排序，然后求出前缀和。

利用前缀和快速计算间隔之和。

代码展示

class Solution {

   public long[] getDistances(int[] arr) {

       Map<Integer, List> positions = new HashMap<>();

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

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

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

          }

           positions.get(arr[i]).add((long) i);

      }

       Map<Integer, List> posPreSum = new HashMap<>();

       for (var e : positions.entrySet()) {

           var pos = e.getValue();

           Collections.sort(pos);

           List preSum = new ArrayList<>();

           preSum.add(pos.get(0));

           for (int i = 1; i < pos.size(); i++) {

               preSum.add(preSum.get(i - 1) + pos.get(i));

          }

           posPreSum.put(e.getKey(), preSum);

      }

       long[] result = new long[arr.length];

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

           List pos = positions.get(arr[i]);

           List preSum = posPreSum.get(arr[i]);

           long n = preSum.size();

           long p = bSearch(pos, i);

           long left = 0, right = 0;

           if (p > 0) {

               left = p * i - preSum.get((int) (p - 1));

          }

           if (p < n - 1) {

               right = preSum.get(preSum.size() - 1) - preSum.get((int) p) - (preSum.size() - p - 1) * i;

          }

           result[i] = left + right;

      }

       return result;

  }

   long bSearch(List list, long target) {

       int l = 0, r = list.size() - 1;

       while (l + 1 < r) {

           int mid = (l + r) / 2;

           if (list.get(mid) == target) {

               return mid;

          }

           if (list.get(mid) < target) {

               l = mid;

          } else {

               r = mid;

          }

      }

       return list.get(l) == target ? l : r;

  }

}

【 NO.4 还原原数组】

解题思路

首先要找到 k，枚举 nums 两两差值，统计每种差出现了多少次，若出现次数少于 nums.length / 2 那么这个差值一定不是 k。

然后对于每种出现次数不少于 nums.length / 2 的差值，把它当作 k 尝试还原数组。

代码展示

class Solution {

   public int[] recoverArray(int[] nums) {

       Arrays.sort(nums);

       Map<Integer, Integer> count = new HashMap<>();

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

           for (int j = i + 1; j < nums.length; j++) {

               if (nums[i] != nums[j]) {

                   int diff = Math.abs(nums[i] - nums[j]);

                   count.put(diff, count.getOrDefault(diff, 0) + 1);

              }

          }

      }

       for (var e : count.entrySet()) {

           if (e.getValue() * 2 < nums.length) {

               continue;

          }

           int[] result = recoverArray(nums, e.getKey() / 2);

           if (result != null && result.length == nums.length / 2) {

               return result;

          }

      }

       return null;

  }

   private int[] recoverArray(int[] nums, int k) {

       boolean[] found = new boolean[nums.length];

       List result = new ArrayList<>();

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

           if (found[i]) {

               continue;

          }

           int lower = nums[i];

           int higher = lower + k * 2;

           int p = bSearch(nums, found, higher, i + 1, nums.length - 1);

           if (nums[p] != higher) {

               return null;

          }

           found[i] = true;

           found[p] = true;

           result.add(lower + k);

      }

       return result.stream().mapToInt(i -> i).toArray();

  }

   // 在 [l, r] 中找到第一个 found = false 的 target

   int bSearch(int[] list, boolean[] found, int target, int l, int r) {

       while (l + 1 < r) {

           int mid = (l + r) / 2;

           if (list[mid] < target || (list[mid] == target && found[mid])) {

               l = mid;

          } else {

               r = mid;

          }

      }

       return list[l] == target && !found[l] ? l : r;

  }

}