LeetCode刷题笔记

23. Merge k Sorted Lists

要点：

1. 学会数据结构PriorityQueue（优先队列）的用法，通过给优先队列传入自定义的经过复写compare方法的比较器实现大根堆或者小根堆。

2. PriorityQueue中不能存放null值，所以每次更新优先队列都需要作判空检查，如遇null值直接剔除。

 1 import java.util.Comparator;
 2 import java.util.PriorityQueue;
 3 
 4 class Solution {
 5     public ListNode mergeKLists(ListNode[] lists) {
 6         //要点1
 7         PriorityQueue<ListNode> nodesQueue = new PriorityQueue<>(new Comparator<ListNode>() {
 8             @Override
 9             //将compare方法重写为比较ListNode的val值大小
10             public int compare(ListNode o1, ListNode o2) {
11                 return o1.val-o2.val;
12             }
13         });
14 
15         ListNode head = new ListNode(0);
16         for(ListNode node:lists)
17             if(node!=null)
18                 nodesQueue.add(node);
19 
20         ListNode p = head;
21         while(!nodesQueue.isEmpty()){
22             //判空检查，如果ListNode的下一个Node是null，则取出该Node后不再将其下一个节点放回优先队列。
23             if(nodesQueue.peek().next==null){
24                 p.next = new ListNode(nodesQueue.poll().val);
25                 p = p.next;
26             }else{
27                 ListNode tmp = nodesQueue.poll();
28                 p.next = new ListNode(tmp.val);
29                 p = p.next;
30                 nodesQueue.add(tmp.next);
31             }
32         }
33         return head.next;
34     }
35 
36 }

29. Divide Two Integers

class Solution {
    //用dividend循环减去diviso并计数减了多少次，这种方法会tle
    public static int divide(int dividend, int divisor) {
        //处理两种溢出情况
        if(dividend == -2147483648){
            if(divisor == 1)
                return -2147483648;
            if(divisor == -1)
                return 2147483647;
        }
        /**
           32位整数的取值范围是-2147483648~+2147483647
           将两个数都转为负数，以处理最大溢出-2147483648
        */
        
        //保存符号
        int flag = 1;
        if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
            flag = -1;
        //都转为负数
        dividend = dividend>0?-dividend:dividend;
        divisor = divisor>0?-divisor:divisor;
        int res = 0;
        if(dividend>divisor)
            return 0;
        //开始循环取商
        while(dividend<0){
            int k = 1;
            //divisor_tmp是变量，只要比dividend小就每次加倍，同时k作为商的计数也加倍
            int divisor_tmp = divisor;
            int tmp=0;
            while(dividend<divisor_tmp){
                tmp = divisor_tmp;
                //divisor_tmp在加倍的过程中有可能溢出，需要处理
                if(divisor_tmp+divisor_tmp>0||divisor_tmp+divisor_tmp==-2147483648)
                    break;
                divisor_tmp += divisor_tmp;
                k += k;
            }
            //如果跳出加倍循环后，dividend比divisor_tmp大，说明divisor_tmp加倍超过了dividend，需要撤销上一次的加倍
            if(dividend>divisor_tmp){
                divisor_tmp -= tmp;
                k>>=1;
            }
            //从divideng减去divisor_tmp并保存加倍值
            dividend -= divisor_tmp;
            res += k;
        }
        return res*flag;
    }

}

32. Longest Valid Parentheses

连同下面的解释，参考自 https://www.acwing.com/solution/LeetCode/content/114/

算法

(双指针扫描、贪心) O(n)O(n)
假设当前从前到后统计合法括号子串，令(的权值为1，)的权值为-1。首先记录start为某个起点，则在i向后移动的过程中，若当前[start,i]区间和等于0，该字符串是合法的；若区间和大于0，则说明目前缺少右括号，可以不修改start；若区间和小于0，则说明区间已经不合法了，需要修正start为i+1。初始时start从0开始即可。
可是对于…((((合法)(((这种情况，以上算法不能够准确捕捉到最长的合法子串，此时我们逆向考虑，将以上过程反向，从后向前统计，即可处理所有的情况。

时间复杂度

两次线性扫描，故时间复杂度为O(n)O(n)。

class Solution {
    public int longestValidParentheses(String s) {
       char[] chars = s.toCharArray();
        int[] marks = new int[chars.length];
        for(int i=0; i<chars.length;i++)
            marks[i] = chars[i]=='('?1:-1;

        int pr = 0;
        int pl = 0;
        int distance = 0;
        int tmp = 0;
        while(pr<marks.length){
            tmp+=marks[pr];
            if(tmp<0){
                tmp = 0;
                pl = pr+1;
            }
            if(tmp == 0)
                distance = pr-pl+1>distance?pr-pl+1:distance;
            pr++;
        }

        pr = marks.length-1;
        pl = pr;
        tmp = 0;
        while(pl>=0){
            tmp += marks[pl] ;
            if(tmp>0) {
                tmp = 0;
                pr = pl-1;
            }
            if(tmp == 0)
                distance = pr-pl+1>distance?pr-pl+1:distance;

            pl--;
        }
        return distance;
    }
}