LeetCode(56) -- 2, 973

P2. Add Two Numbers (Medium)

两个linkedList, 分别以倒序的形式表示两个数，比如：用2 -> 4 -> 3 来表示342。 把这两个数加起来，也用linkedlist来表示它们的和。

我的思路

非常简单的linkedlist操作，没啥可说的，直接写代码了。

我的代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = 0;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            current.next = new ListNode(sum % 10);
            current = current.next;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

81%

最优解

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        System.exit(0);
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
          int sum = ((l1 == null) ? 0 : l1.val) + ((l2 == null) ? 0 : l2.val) + carry;
          carry = sum / 10;
          cur.next = new ListNode(sum % 10);
          cur = cur.next;

          l1 = (l1 == null) ? l1 : l1.next;
          l2 = (l2 == null) ? l2 : l2.next;
        }
        return dummyHead.next;
    }
}

基本思路一样，只不过用了三目运算符。

P973. K Closest Points to Origin (Easy)

找出离原点前k个最近的点。

我的思路

用priorityqueue

我的代码

public class M_973_KClosestPointstoOrigin {
    public int[][] kClosest(int[][] points, int K) {
        int[][] ans = new int[K][2];
        PriorityQueue<Point> queue = new PriorityQueue<>(K, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return (o2.x * o2.x + o2.y * o2.y) - (o1.x * o1.x + o1.y * o1.y);
            }
        });
        for (int[] point : points) {
            queue.add(new Point(point));
            if (queue.size() > K) {
                queue.poll();
            }
        }
        for (int i = 0; i < K; i++) {
            Point point = queue.poll();
            ans[i] = new int[] {point.x, point.y};
        }
        return ans;
    }

    class Point {
        int x;
        int y;

        public Point(int[] point) {
            this.x = point[0];
            this.y = point[1];
        }
    }
}

58%

最优解

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        // // Sort and return copy of K -> O(NlogN)
        // Arrays.sort(points, (p1, p2) -> p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1]);
        // return Arrays.copyOfRange(points, 0, K);

//         // Keep K nearest points in the priorityQueue -> NlogK
//         PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p2[0]*p2[0] + p2[1]*p2[1] - p1[0]*p1[0] - p1[1]*p1[1]);

//         for(int[] p: points){
//             pq.offer(p);
//             if(pq.size() > K){
//                 pq.poll();
//             }
//         }

//         int[][] result = new int[K][2];
//         while(K > 0){
//             result[--K] = pq.poll();
//         }
//         return result;

        // Quick Sort and select -> O(N) and worst case O(N^2) when it is ascending

        int left = 0;
        int right =  points.length-1;
        while(left < right){
            int pivot = partition(points, left, right);
            if(pivot == K){
                break;
            }else if(pivot < K){
               left  = pivot;
            } else if(pivot > K){
                right = pivot-1;
            }
        }
        return Arrays.copyOfRange(points, 0, K);
    }

    private int partition(int[][] points, int left, int right){
        int mid = (left+right)/2;
        int[] pivot = points[mid];
        while(left <= right){
            while(compare(points[left], pivot) < 0) left++;
            while(compare(points[right], pivot) > 0) right--;

            if(left <= right){
                int[] tmp = points[left];
                points[left] = points[right];
                points[right] = tmp;
                left++;
                right--;
            }
        }
        return left;
    }

    private int compare(int[] p1, int[] p2){
        return p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1];
    }
}

QuickSort还要再巩固一下。