上岸算法 发表于 2021-12-26 20:14:55

上岸算法LeetCode Weekly Contest 273解题报告

【 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;
       dy = new int;
       dy['L'] = -1;
       dy['R'] = 1;
       dx['U'] = -1;
       dx['D'] = 1;
       int[] result = new int;
       for (int i = 0; i < s.length(); i++) {
         result = execute(n, startPos, s.substring(i));
      }
       return result;
}

   int execute(int n, int[] startPos, String s) {
       int x = startPos, y = startPos;
       for (int i = 0; i < s.length(); i++) {
         char c = s.charAt(i);
         x += dx;
         y += dy;
         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<Long>> positions = new HashMap<>();
       for (int i = 0; i < arr.length; i++) {
         if (!positions.containsKey(arr)) {
               positions.put(arr, new ArrayList<>());
          }
         positions.get(arr).add((long) i);
      }
       Map<Integer, List<Long>> posPreSum = new HashMap<>();
       for (var e : positions.entrySet()) {
         var pos = e.getValue();
         Collections.sort(pos);
         List<Long> 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;
       for (int i = 0; i < arr.length; i++) {
         List<Long> pos = positions.get(arr);
         List<Long> preSum = posPreSum.get(arr);
         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 = left + right;
      }
       return result;
}

   long bSearch(List<Long> 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 != nums) {
                   int diff = Math.abs(nums - nums);
                   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;
       List<Integer> result = new ArrayList<>();
       for (int i = 0; i < nums.length; i++) {
         if (found) {
               continue;
          }
         int lower = nums;
         int higher = lower + k * 2;
         int p = bSearch(nums, found, higher, i + 1, nums.length - 1);
         if (nums != higher) {
               return null;
          }
         found = true;
         found = true;
         result.add(lower + k);
      }
       return result.stream().mapToInt(i -> i).toArray();
}

   // 在 中找到第一个 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 < target || (list == target && found)) {
               l = mid;
          } else {
               r = mid;
          }
      }
       return list == target && !found ? l : r;
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 273解题报告