[数据结构与算法]力扣记录：Hot100（6）——142-206

142 环形链表 II

• 双指针，之前做过，先判断是否存在环（141 环形链表），然后判断环的入口
  • 时间复杂度O(n)，空间复杂度O(1)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //双指针
        ListNode slow = head;
        ListNode fast = head;
        //先判断是否存在环
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                //然后判断环的入口
                ListNode p1 = slow;
                ListNode p2 = head;
                while(true){
                    if(p1 == p2) return p1;
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }
        }
        return null;
    }
}

*146 LRU 缓存

• 哈希表+双向链表，哈希表存储key及其在双向链表中的位置，双向链表按照被使用的顺序存储键值对（头部最近使用，尾部最久未使用）。get方法若key存在，将双向链表中对应节点移到头部；put方法若key不存在，在链表头部、哈希表添加节点，然后判断双向链表节点数量是否超过容量，超过了就删除尾部节点，同时删除哈希表中对应节点。注意：可以直接使用LinkedHashMap实现，但是最好手动实现一个双向链表。修改时使用虚拟头节点和虚拟尾节点，虚拟头节点head.next才是真正的头节点，虚拟尾节点tail.prev才是真正的尾节点；真头节点prev为head，真尾节点next为tail，是双向链表而不是双向循环链表！
  • 时间复杂度O(1)，空间复杂度O(capacity)

    //哈希表+双向链表
    //哈希表存储key及其在双向链表中的位置
    //双向链表按照被使用的顺序存储键值对（头部最近使用，尾部最久未使用）
    private Map<Integer, MyDLinkedNode> map;    //哈希表
    private int size;    //当前容量
    private int cap;   //容量上限
    private MyDLinkedNode head, tail;   //虚拟头节点，虚拟尾节点

    public LRUCache(int capacity) {
        //初始化
        map = new HashMap<Integer, MyDLinkedNode>();
        size = 0;
        cap = capacity;
        head = new MyDLinkedNode();
        tail = new MyDLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    //get方法若key存在，将双向链表中对应节点移到头部
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }else{
            MyDLinkedNode node = map.get(key);
            moveHead(node);
            return node.value;
        }
    }
    
    //put方法若key不存在，在链表头部、哈希表添加节点
    //然后判断双向链表节点数量是否超过容量，超过了就删除尾部节点，同时删除哈希表中对应节点
    public void put(int key, int value) {
        if(map.containsKey(key)){
            MyDLinkedNode node = map.get(key);
            node.value = value;
            moveHead(node);
        }else{
            MyDLinkedNode node = new MyDLinkedNode(key, value);
            addHead(node);
            map.put(key, node);
            size += 1;
            if(size > cap){
                //删除尾部节点
                int delKey = tail.prev.key;
                delNode(tail.prev);
                map.remove(delKey);
                size -= 1;
            }
        }
    }

    //手动实现双向链表
    class MyDLinkedNode{
        int key;
        int value;
        MyDLinkedNode prev;
        MyDLinkedNode next;
        public MyDLinkedNode(){}
        public MyDLinkedNode(int k, int v){
            key = k;
            value = v;
        }
    }
    //头部插入节点
    //虚拟头节点head.next才是真正的头节点
    //虚拟尾节点tail.prev才是真正的尾节点
    //真头节点prev为head，真尾节点next为tail
    private void addHead(MyDLinkedNode node){
        node.next = head.next;
        node.prev = head;
        // node.prev = tail.prev;//这里是不对的，双向但不循环
        head.next.prev = node;
        head.next = node;
        // tail.prev.next = node;
        // tail.prev = node;
    }
    //删除节点
    private void delNode(MyDLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    //移动节点到头部
    private void moveHead(MyDLinkedNode node){
        delNode(node);
        addHead(node);
    }
}

148 排序链表

• 归并排序，自顶向下递归空间复杂度为O(n)，从底至顶直接合并空间复杂度为O(1)，合并时同JZ25 合并两个排序的链表。
• 注意：使用快慢指针寻找链表中点，快指针每次移动两步，慢指针每次移动一步，快指针到达链表尾部时慢指针即为中点。
• 自顶向下递归，分割区间为左闭右开，前半部分为[head, slow)，后半部分为[slow, tail)，直到每部分只有一个节点再进行合并（两个有序链表合并）。
• 从底至顶直接合并，相当于从一个节点开始，两两合并，合并后的链表（两个节点）再两两合并，直到全部合并。定义当前合并的单个链表长度，每轮乘以2，若大于链表总长，则说明全部合并。使用虚拟头节点，定义
  • 时间复杂度O(nlogn)，空间复杂度O(1)

class Solution {
    public ListNode sortList(ListNode head) {
        //自顶向下递归
        return mergeSort(head, null);
    }
    //归并排序函数，输入链表头尾
    public ListNode mergeSort(ListNode head, ListNode tail){
        //终止条件
        if(head == null){
            return null;
        }
        if(head.next == tail){
            head.next = null;   //切断
            return head;
        }
        //使用快慢指针寻找链表中点
        ListNode slow = head;
        ListNode fast = head;
        //快指针每次移动两步，慢指针每次移动一步，快指针到达链表尾部时慢指针即为中点
        while(fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        //递归分割
        ListNode mid = slow;    //这里需要重新定义mid防止被修改
        //前半部分为[head, slow)，后半部分为[slow, tail)
        ListNode left = mergeSort(head, mid);
        ListNode right = mergeSort(mid, tail);
        //直到每部分只有一个节点再进行合并（两个有序链表合并）
        return mergeTwoLists(left, right);
    }
    //合并两个排序的链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //定义虚拟头结点
        ListNode virtualHead = new ListNode(0);
        //定义处理的当前节点
        ListNode cur = virtualHead;
        //将节点指向两个链表中较小的那个节点
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                cur.next = l2;
                l2 = l2.next;
            }else{
                cur.next = l1;
                l1 = l1.next;
            }
            //移动当前节点
            cur = cur.next;
        }
        //将剩下非空的链表直接放在后面
        cur.next = (l1 == null ? l2 : l1);
        //返回结果
        return virtualHead.next;
    }
    //从底至顶直接合并
    public ListNode sortList2(ListNode head) {
        //从底至顶直接合并
        if(head == null){
            return null;
        }
        //计算链表长度
        int leng = 0;
        ListNode node = head;
        while(node != null){
            leng++;
            node = node.next;
        }
        //使用虚拟头节点
        ListNode virtualHead = new ListNode(0, head);
        //从一个节点开始，两两合并，合并后的链表（两个节点）再两两合并，直到全部合并
        //定义当前合并的单个链表长度，每轮乘以2，若大于链表总长，则说明全部合并
        for(int i = 1; i < leng; i <<= 1){
            ListNode pre = virtualHead; //每轮合并都从头开始
            ListNode cur = virtualHead.next;
            while(cur != null){
                ListNode head1 = cur;   //合并的第一个链表头部
                for(int j = 1; j < i && cur.next != null; j++){  //注意判断cur.next不为null
                    cur = cur.next;
                }
                ListNode head2 = cur.next;  //合并的第二个链表头部
                cur.next = null;    //切出第一个链表
                cur = head2;    //这里cur可能为null
                for(int j = 1; j < i && cur != null && cur.next != null; j++){  //注意判断cur和cur.next不为null
                    cur = cur.next;
                }
                //这里cur同样可能为null，同上，需要做判断，为null的时候就不需要切了，下一对直接结束
                ListNode next = null;
                if(cur != null){
                    next = cur.next;   //保存下一轮合并的头节点
                    cur.next = null;    //切出第二个链表
                }
                ListNode m = mergeTwoLists(head1, head2);   //合并两个有序链表
                pre.next = m;   //将合并后的链表接上
                //准备下一对合并
                while(pre.next != null){    //这里pre应该移动到已合并的新链表尾部
                    pre = pre.next;
                }
                cur = next;
            }
        }
        return virtualHead.next;
    }
}

152 乘积最大子数组

• 动态规划，注意：这里需要根据当前位置的正负性进行分类讨论，应该维护两个dp数组，一个保存大于0的最大积，另一个保存小于0的最小积，当前位置为负数时，求（最小积乘当前值，最大积乘当前值，当前值）的最大最小值。优化：可使用滚动数组。
  • 时间复杂度O(n)，空间复杂度O(n)，优化为O(1)

class Solution {
    public int maxProduct(int[] nums) {
        //动态规划
        //这里需要根据当前位置的正负性进行分类讨论
        //当前位置为负数时，前面的乘积越小越好（小于0）
        //应该维护两个dp数组
        //一个保存大于0的最大积，另一个保存小于0的最小积
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        //初始化
        int max = nums[0];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            //求（最小积乘当前值，最大积乘当前值，当前值）的最大最小值
            dpMax[i] = Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
            dpMin[i] = Math.min(Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
            max = Math.max(max, dpMax[i]);
        }
        return max;
    }
}
//优化
class Solution {
    public int maxProduct(int[] nums) {
        //动态规划，优化为滚动数组
        int dpMax = nums[0];
        int dpMin = nums[0];
        //初始化
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            //注意这里需要重新定义变量进行计算
            int m1 = dpMax;
            int m2 = dpMin;
            dpMax = Math.max(Math.max(m1 * nums[i], m2 * nums[i]), nums[i]);
            dpMin = Math.min(Math.min(m1 * nums[i], m2 * nums[i]), nums[i]);
            max = Math.max(max, dpMax);
        }
        return max;
    }
}

155 最小栈

• 定义辅助栈保存最小值，同JZ30 包含min函数的栈。
  • 时间复杂度O(1)，空间复杂度O(n)

class MinStack {
    //定义辅助栈保存最小值
    Deque<Integer> mainStack;
    Deque<Integer> auxStack;
    public MinStack() {
        mainStack = new LinkedList<>();
        auxStack = new LinkedList<>();
    }
    
    public void push(int val) {
        mainStack.push(val);
        if(auxStack.isEmpty()){
            auxStack.push(val);
        }else{
            //辅助栈顶保存当前最小值
            if(val <= auxStack.peek()){
                auxStack.push(val);
            }
        }
    }
    
    public void pop() {
        int cur = mainStack.pop();
        //辅助栈只在当前最小值弹出时弹出
        if(cur == auxStack.peek()){
            auxStack.pop();
        }
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int getMin() {
        return auxStack.peek();
    }
}

160 相交链表

• 同JZ52 两个链表的第一个公共节点，若两个链表相交，则两个链表尾部节点对齐，分别计算两个链表长度，从相应位置开始对比直到遍历结束。
  • 时间复杂度O(m+n)，空间复杂度O(1)

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //若两个链表相交，则两个链表尾部节点对齐
        //分别计算两个链表长度，从相应位置开始对比直到遍历结束
        int lengA = 0;
        int lengB = 0;
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != null){
            lengA++;
            pA = pA.next;
        }
        while(pB != null){
            lengB++;
            pB = pB.next;
        }
        //设置A为较长的链表
        if(lengA < lengB){
            ListNode temp = headB;
            headB = headA;
            headA = temp;
            int leng = lengB;
            lengB = lengA;
            lengA = leng;
        }
        pA = headA;
        pB = headB;
        while(lengA > lengB){
            pA = pA.next;
            lengA--;
        }
        while(pA != null && pB != null){
            if(pA == pB){
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }
        return null;
    }
}

169 多数元素

• 摩尔投票法，同JZ39 数组中出现次数超过一半的数字
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int majorityElement(int[] nums) {
        //摩尔投票法
        int mode = nums[0];  //假设众数
        int sum = 1;    //票数
        for(int i = 1; i < nums.length; i++){
            if(sum == 0){   //重新选举众数
                mode = nums[i];
            }
            //相同则加票，不同则减票
            if(nums[i] == mode){
                sum++;
            }else{
                sum--;
            }
        }
        return mode;
    }
}

198 打家劫舍

• 动态规划，之前做过，优化：保存前两个值即可。
  • 时间复杂度O(n)，空间复杂度O(n)，优化后O(1)

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        //动态规划
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}
//优化
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        //动态规划，优化
        int dp0 = nums[0];
        int dp1 = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int dp2 = Math.max(dp1, dp0 + nums[i]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp1;
    }
}

*200 岛屿数量

• DFS，题目意思是水平或垂直相连的1看作一个岛屿，为了避免重复，需要修改遍历过的格子数（1改为0，复杂的情况可以改为新状态2）。计算递归的次数为岛屿数量。
• BFS，使用队列，遍历格子，若当前节点为1且在各自内，则入队，入队后将该格子修改为0，然后将其上下左右格子加入队列，直到队列为空。计算入队的次数为岛屿数量。
  • 时间复杂度O(mn)，空间复杂度O(mn)，BFS为O(min(m,n))

class Solution {
    public int numIslands(char[][] grid) {
        // //DFS，题目意思是水平或垂直相连的1看作一个岛屿
        // //计算递归的次数为岛屿数量
        // int count = 0;
        // for(int i = 0; i < grid.length; i++){
        //     for(int j = 0; j < grid[0].length; j++){
        //         if(grid[i][j] == '1'){
        //             dfs(grid, i, j);
        //             count++;
        //         }
        //     }
        // }
        //BFS，使用队列，遍历格子，若当前节点为1且在各自内，则入队
        //计算入队的次数为岛屿数量
        int count = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        //终止条件
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
            return;
        }
        if(grid[i][j] != '1'){  //在这里判断是否为1，减少递归前判断
            return;
        }
        //为了避免重复，需要修改遍历过的格子数（1改为0，复杂的情况可以改为新状态2）
        grid[i][j] = 0;
        //递归
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
    }
    private void bfs(char[][] grid, int i, int j){
        //终止条件
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
            return;
        }
        if(grid[i][j] != '1'){  //在这里判断是否为1，减少递归前判断
            return;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        //入队后将该格子修改为0，然后将其上下左右格子加入队列，直到队列为空
        grid[i][j] = 0;
        //递归
        bfs(grid, i, j - 1);
        bfs(grid, i, j + 1);
        bfs(grid, i - 1, j);
        bfs(grid, i + 1, j);
    }
}

206 反转链表

• 双指针，之前做过，原地翻转。
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针
        //原地翻转
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}