【 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;
}
}
创作新主题