01-CodeTop：206~3~146~215~25

206. 反转链表

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0){
            return 0;
        }
        HashMap<Character,Integer> map = new HashMap<>();
        int start = 0;
        int maxLength = 0;
        for(int end = 0; end<s.length();end++){
            if(map.containsKey(s.charAt(end))){
                start = Math.max(start,map.get(s.charAt(end))+1);
            }
            map.put(s.charAt(end),end);
            maxLength = Math.max(maxLength,end-start+1);
        }
        return maxLength;
    }
}

146. LRU 缓存

public class LRUCache {
    private Map<Integer,Node> map = new HashMap<>();
    // 定义双向链表的节点
    static class Node{
        private Integer key;
        private Integer value;
        private Node pre;
        private Node next;
        public Node(){}
        public Node(Integer key,Integer value){
            this.key = key;
            this.value = value;
        }
    }
    private int size;
    private int capacity;
    private Node head;
    private Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    // 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    public int get(int key) {
        Node node = map.get(key);
        if(node==null){
            return -1;
        }
        // 将该节点移动到链表的头部
        // 1. 删除该节点
        removeNode(node);
        // 2. 将链表移动到头部
        moveToHead(node);
        return node.value;
    }
    private void moveToHead(Node node) {
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }
    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    // 如果关键字 key 已经存在，则变更其数据值 value ；
    // 如果不存在，则向缓存中插入该组 key-value 。
    // 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node!=null){
            node.value = value;
            // 将该节点移动到链表头部
            removeNode(node);
            moveToHead(node);
        }else{
            Node newNode = new Node(key,value);
            moveToHead(newNode);
            map.put(key,newNode);
            size++;
            if(size>capacity){
                // 则应该 逐出 最久未使用的关键字。
                Node delteNode = tail.pre;
                removeNode(delteNode);
                map.remove(delteNode.key);
                size--;
            }
        }
    }
}

215. 数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums==null || nums.length==0){
            return -1;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if(i<k){
                priorityQueue.add(nums[i]);
            }else{
                if(!priorityQueue.isEmpty() && nums[i]>priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.add(nums[i]);
                }
            }
        }
        return priorityQueue.peek();
    }
}

25. K 个一组翻转链表

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        dummy.next = head;
        ListNode end = pre;
        ListNode start = pre.next;
        while (end.next!=null){
            for(int i=0;i<k && end!=null;i++){
                end = end.next;
            }
            if(end==null){
                break;
            }
            ListNode temp = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = temp;
            pre = start;
            end = pre;
            start = temp;
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode cur) {
        ListNode pre = null;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}