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

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

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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<Long>> 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<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[arr.length];
   for (int i = 0; i < arr.length; i++) {
         List<Long> pos = positions.get(arr[i]);
         List<Long> 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<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[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<Integer> 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;
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 273解题报告

登录后可回复主题

浏览过的版块