几道高频力扣题

草，老是搞混集合的一些函数，没有IDE的提示举步维艰，特此记录。

stack

Stack<Integer> s1 = new Stack<Integer>();

Queue

put()/add()/offer()区别
- put()
  
  如果队列满了则会阻塞当前线程，直到队列有空间能够放入为止。
- add()
  
  如果入队操作成功则返回true，否则抛出异常。
- offer()
  
  入队操作成功返回true，否则返回false。
poll()/remove()/take()区别
- take()
  
  如果队列为空则会阻塞，直到有元素可以进行出队操作为止。
- remove()
  
  如果出队操作失败则抛出异常。
- poll()
  
  队列为空则返回null，可以设置等待超时时间。

Deque

Deque<ListNode> queue = new LinkedList<>();

isEmpty()

PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆，默认容量为11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆，容量11
    @Override
    public int compare(Integer i1,Integer i2){
        return i2-i1;
    }
});

143. 重排链表（队列，快慢指针，链表翻转）

难度中等708

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

题解：

一、搞个链表或者双向队列，全部放入，直接模拟操作：

public void reorderList(ListNode head) {
    Deque<ListNode> queue = new LinkedList<>(); 

    ListNode p = head.next;
    while(p!=null) {
        queue.addLast(p);
        p = p.next;
    }

    p = head;
    while(true) {
        if(!queue.isEmpty()) {
            p.next = queue.removeLast();
            p = p.next;
        } else {
            break;
        }
        if(!queue.isEmpty()) {
            p.next = queue.removeFirst();
            p = p.next;
        } else {
            break;
        }
    }
    p.next = null;
}

二、递归处理

三、后半翻转链表，再逐个遍历

快慢指针，翻转链表

1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步，将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6
    
第二步，将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4
    
第三步，依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4

代码：

class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        // 快慢指针找中点
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null) {
            if(fast.next == null) {
                break;
            } else {
                fast = fast.next.next;
            }
            slow = slow.next;
        }
        ListNode rightStart = slow.next;
        // System.out.println(rightStart.val);
        rightStart = reverseList(rightStart);
        ListNode fakeHead = new ListNode();
        ListNode p1=head,p2=rightStart;
        while(true) {
            fakeHead.next = p1;
            if(p1==null) return;
            p1 = p1.next;
            fakeHead = fakeHead.next;
            fakeHead.next = p2;
            if(p2==null) return;
            p2 = p2.next;
            fakeHead = fakeHead.next;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode tmp;
        while(cur!=null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

69. Sqrt(x)（二分）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

二分

public int mySqrt(int x) {
    // 一、函数
    // return (int)Math.pow(x,0.5);
    // 二、二分
    long left = 0;
    long right = x;
    long mid;
    do {
        mid = (left+right)/2;
        if(mid*mid==x) return (int)mid;
        if(mid*mid<x) {
            left = mid+1;
            continue;
        } else {
            right = mid-1;
            continue;
        }
    } while(left<=right);
    return (int)(left-1);
}

3. 无重复字符的最长子串（滑窗）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

滑窗：记录最右边出现的位置，需要看一下。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int maxLen = 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++) {
            if(map.containsKey(s.charAt(i))) {
                left = Math.max(map.get(s.charAt(i))+1,left);
            }
            map.put(s.charAt(i),i);
            maxLen = Math.max(maxLen,i-left+1);
            // System.out.printf("%d %d\n",i,left);
        }
        return maxLen;
    }
}

25. K 个一组翻转链表

难度困难1373

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

示例 3：

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

示例 4：

输入：head = [1], k = 1
输出：[1]

提示：

列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

题解:

比较容易想到的思路还是用一个deque，直接模拟。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode fakeHead = new ListNode();
        Deque<ListNode> deque = new LinkedList<>();
        ListNode cur = fakeHead;
        while(true) {
            ListNode p = head;
            deque.clear();
            for(int i=0;i<k;i++) {
                if(head==null) {
                    cur.next = p;
                    return fakeHead.next;
                }
                deque.offerLast(head);
                head = head.next;
            }
            while(!deque.isEmpty()) {
                cur.next = deque.pollLast();
                cur = cur.next;
            }
        }
    }
}

或者直接翻转每一组链表：

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode fakeHead = new ListNode();
    fakeHead.next = head;
    ListNode before = fakeHead;
    ListNode after = fakeHead;
    ListNode left = fakeHead;
    ListNode right = fakeHead;
    int i;
    while(true) {
        for(i=0;i<k;i++) {
            right = right.next;
            if(right==null) return fakeHead.next;
        }
        after = right.next;
        left = before.next;
        before.next = reverseList(left,right);
        before = right = left;
    }
}
private ListNode reverseList(ListNode left,ListNode right) {
    ListNode originRight = right;
    right = right.next;
    ListNode cur = left;
    ListNode pre = right;
    ListNode tmp;
    while(pre!=originRight) {
        tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

148. 排序链表

难度中等1381

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

链表快排：

搞三个结点：存放小的，等的，大的，然后接起来。然后再递归小的，大的。

递归归并排序：

class Solution {
    public ListNode sortList(ListNode head) {
        //System.out.printf("%d\n",head.val);
        if(head==null || head.next==null) return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = sortList(slow.next);
        slow.next = null;
        ListNode left = sortList(head);
        
        ListNode fakeHead = new ListNode(0);
        ListNode cur = fakeHead;
        while(left!=null&&right!=null) {
            if(left.val>=right.val) {
                cur.next = right;
                right = right.next;
            } else {
                cur.next = left;
                left = left.next;
            }
            cur = cur.next;
        }
        while(left!=null) {
            cur.next = left;
            cur = cur.next;
            left = left.next;
        }
        while(right!=null) {
            cur.next = right;
            cur = cur.next;
            right = right.next;
        }
        return fakeHead.next;
    }
}

自底向上的递归：

直接放弃，一时半会是写不对。

top K问题

排序，局部排序（如冒泡，冒K次），堆，只有k个。QuickSelect，类似快排，但不相关的不管。