LeetCode Weekly Contest 45解题思路
LeetCode Weekly Contest 45解题思路
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434663
LeetCode Weekly Contest 45解题思路
详细代码可以fork下Github上leetcode项目，不定期更新。
赛题
本次周赛主要分为以下4道题：
- Leetcode 657. Judge Route Circle
- Leetcode 658. Find K Closest Elements
- Leetcode 659. Split Array into Consecutive Subsequences
- Leetcode 660. Remove 9
Leetcode 657. Judge Route Circle
Problem:
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place. The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:
Input: “UD” Output: true
Example 2:
Input: “LL” Output: false
无脑题，直接分别判断L和R，U和D出现的次数是否相等，并不是严格意义上的circle，代码如下：
public boolean judgeCircle(String moves) {
int[] map = new int[26];
for (char c : moves.toCharArray()){
map[c - 'A'] ++;
}
if (map['L' - 'A'] == map['R' - 'A'] && map['U' - 'A'] == map['D' - 'A']) return true;
return false;
}Leetcode 658. Find K Closest Elements
Problem:
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: 1,2,3,4,5, k=4, x=3 Output: 1,2,3,4
Example 2:
Input: 1,2,3,4,5, k=4, x=-1 Output: 1,2,3,4
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 10^4
- Absolute value of elements in the array and x will not exceed 10^4
先说自己的思路吧，首先找到与x【最接近】的数，接着把它邻近的左k-1个位置和右k-1个位置放入优先队列，起初直接放值，但发现这种没法准确判断和x的差距，所以优先队列改成放差，当然还需要记录id，方便后续构造解。
题目要求是都最小的情况下，返回较小id，那么只需要对优先队列的排序做些限制即可，代码如下：
class Pair implements Comparable<Pair>{
int id;
int min;
public Pair(int id, int min){
this.id = id;
this.min = min;
}
@Override
public int compareTo(Pair that) {
return this.min == that.min ? this.id - that.id : this.min - that.min;
}
}
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
Integer[] aux = arr.toArray(new Integer[0]);
int index = binarySearch(aux, x);
List<Integer> ans = new ArrayList<>();
if (arr.size() == 0) return ans;
Queue<Pair> queue = new PriorityQueue<>();
queue.offer(new Pair(index, Math.abs(aux[index] - x)));
for (int i = 1; i < k; ++i){
if (i + index < aux.length) queue.offer(new Pair(i + index, Math.abs(aux[index + i] - x)));
if (index - i >= 0) queue.offer(new Pair(index - i, Math.abs(aux[index - i] - x)));
}
for (int i = 0; i < k; ++i){
ans.add(aux[queue.poll().id]);
}
Collections.sort(ans);
return ans;
}
public int binarySearch(Integer[] arra, int x){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (arra[mid] > x) rt = mid - 1;
else lf = mid;
}
if (arra[lf] <= x) return lf;
return 0;
}优秀精短答案：
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
List<Integer> ans = new ArrayList<>();
if (arr.size() == 0) return ans;
Collections.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
int ax = Math.abs(a - x);
int bx = Math.abs(b - x);
if (ax != bx) return ax - bx;
return a - b;
}
});
ans = new ArrayList<Integer>(arr.subList(0, Math.min(k, arr.size())));
Collections.sort(ans);
return ans;
}其实是个排序问题。。。根据给定目标x，对所有元素的差值进行排序，因为给定数组是递增，所以排序给出的结果一定是邻近的，这点非常关键。
Leetcode 659. Split Array into Consecutive Subsequences
Problem:
You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.
Example 1:
Input: 1,2,3,3,4,5 Output: True Explanation: You can split them into two consecutive subsequences :undefined 1, 2, 3 3, 4, 5
Example 2:
Input: 1,2,3,3,4,4,5,5 Output: True Explanation: You can split them into two consecutive subsequences :undefined 1, 2, 3, 4, 5 3, 4, 5
Example 3:
Input: 1,2,3,4,4,5 Output: False
Note:
The length of the input is in range of 1, 10000
此题相对较难，要抓住一些性质不容易，采用模拟，模拟的策略很有意思，首先按要求求出至少三个连续序列组成的所有情况，接着就是【拼接】了。
很有意思的是，在写代码时，先考虑拼接，最后才考虑是否单独（即分桶摆放）摆放。
像此题，我的思路是从频次最大的那个数开始着手，先假设某个数num的频次最大，因此，一定会从num开始，找到num+1，和num+2，组成至少三个序列的情况，如果不存在则可以直接返回false。
那么问题来了，num+1，num+2的频次一定小于等于num，遇到不能分配的情况该怎么办？啥时候是不能分配的时候？
条件： num 还存在待分配的名额时，num+2的个数为0 所以不管num + 1是否被分配完毕，我们都需要将剩余的num 和 num + 1拼接到之前的某个桶的结尾处。
如果找不到这样的桶，同样返回false，否则拼接后，更新桶的最后一个元素。（map实现）
拼谁？一定是num，拼完num，该桶下一步就应该拼num+1的元素，此时再把num+1放进去，两步完成了num和num+1的拼接，完美。
代码如下：
public boolean isPossible(int[] nums) {
TreeMap<Integer, Integer> map = new TreeMap<>();
Map<Integer, Integer> append = new HashMap<>();
for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
for (int i : nums){
if (map.get(i) == 0) continue;
if (append.getOrDefault(i, 0) > 0){ // 先拼接
append.put(i, append.get(i) - 1);
append.put(i + 1, append.getOrDefault(i + 1, 0) + 1);
}
else if (map.getOrDefault(i + 1, 0) > 0 && map.getOrDefault(i + 2, 0) > 0){ // 再独立
map.put(i + 1, map.get(i + 1) - 1);
map.put(i + 2, map.get(i + 2) - 1);
append.put(i + 3, append.getOrDefault(i + 3, 0) + 1);
}
else return false;
map.put(i, map.get(i) - 1);
}
return true;
}思路总结：把每个独立的片段先求出来，接着考虑如何拼凑在一起，因为只能往前拼凑，所以解是唯一的，模拟就好了。
Leetcode 660. Remove 9
Problem:
Start from integer 1, remove any integer that contains 9 such as 9, 19, 29… So now, you will have a new integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, … Given a positive integer n, you need to return the n-th integer after removing. Note that 1 will be the first integer.
Example :
Input: 9 Output: 10
好吧，因为删除的是最后一位9，所以实际上就是10进制转9进制的算法，代码如下：
public int newInteger(int n) {
return Integer.parseInt(Integer.toString(n, 9));
}当然你也可以自己写个进制转换，代码如下：
public int newInteger(int n) {
int ans = 0;
int base = 1;
while (n > 0){
ans += n % 9 * base;
n /= 9;
base *= 10;
}
return ans;
}