🔥 LeetCode 热题 HOT 100（51-60）

142. 环形链表 II

思路：快慢指针，快慢指针相遇后，慢指针回到头，快慢指针步伐一致一起移动，相遇点即为入环点

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode detectCycle(ListNode head) {

        // 没有结点或只有一个非自环结点

        if (head == null || head.next == null) {

            return null;

        }

        ListNode slow = head;

        ListNode fast = head.next;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

            if (fast == slow) {

                //快指针从第一次相交点下一个节点开始移动, 慢指针重新从头开始移动

                fast = fast.next;  //注意

                slow = head;

                while (fast != slow) {

                    fast = fast.next;

                    slow = slow.next;

                }

                // 相遇点即为入环点

                return fast;

            }

        }

        return null;

    }

}

146. LRU 缓存机制

class LRUCache {

    // 用 map 我们可以实现常数复杂度的get，但无法记录各个页面的先后顺序。

    // 因此引入双向链表来记录页面先后顺序。

    private Map<Integer, Node> map;

    private Node head;

    private Node tail;

    private int capacity;

    private int size = 0;

    public LRUCache(int capacity) {

        this.map = new HashMap<>();

        this.head = new Node(-1, -1);

        this.tail = new Node(-1, -1);

        head.next = tail;

        tail.pre = head;

        this.capacity = capacity;

    }

    public int get(int key) {

        if (map.containsKey(key)) {

            Node temp = map.get(key);

            moveToHead(temp);

            return temp.val;

        } else {

            return -1;

        }

    }

    public void put(int key, int value) {

        if (map.containsKey(key)) {

            Node temp = map.get(key);

            temp.val = value;

            moveToHead(temp);

        } else {

            if (size >= capacity) {

                Node tempTail = removeTail();

                int tempKey = tempTail.key;

                map.remove(tempKey);

                size--;

            }

            Node newNode = new Node(key, value);

            map.put(key, newNode);

            addHead(newNode);

            size++;

        }

    }

    private void moveToHead(Node node) {

        removeNode(node);

        addHead(node);

    }

    private Node removeTail() {

        Node temp = tail.pre;

        removeNode(temp);

        return temp;

    }

    private void removeNode(Node node) {

        node.next.pre = node.pre;

        node.pre.next = node.next;

    }

    private void addHead(Node node) {

        node.next = head.next;

        node.pre = head;

        head.next = node;

        node.next.pre = node;

    }

}

class Node {

    Node pre;

    Node next;

    int key;

    int val;

    Node(int key, int val) {

        this.key = key;

        this.val = val;

    }

}

/**

 * Your LRUCache object will be instantiated and called as such:

 * LRUCache obj = new LRUCache(capacity);

 * int param_1 = obj.get(key);

 * obj.put(key,value);

 */

148. 排序链表

思路：O(nlogn)的复杂度实现排序可以考虑归并或快速排序。

归并排序:

/**

 * 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 sortList(ListNode head) {

        return mergeSort(head);

    }

    private ListNode mergeSort(ListNode head) {

        // base case

        if (head == null || head.next == null) {

            return head;

        }

        ListNode mid = getMidNode(head);

        ListNode temp = mid.next;

        mid.next = null;

        ListNode l1 = mergeSort(head);

        ListNode l2 = mergeSort(temp);

        return merge(l1, l2);

    }

    // 快慢指针找中点

    private ListNode getMidNode(ListNode head) {

        ListNode slow = head;

        ListNode fast = head.next;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        return slow;

    }

    // 合并两个链表

    private ListNode merge(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(-1);

        ListNode temp = dummy;

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {

                temp.next = l1;

                l1 = l1.next;

            } else {

                temp.next = l2;

                l2 = l2.next;

            }

            temp = temp.next;

        }

        if (l1 != null) {

            temp.next = l1;

        } else if (l2 != null) {

            temp.next = l2;

        }

        return dummy.next;

    }

}

快速排序:

class Solution {

    public ListNode sortList(ListNode head) {

        return quickSort(head, null);

    }

    // start, end 之间进行快速排序，左闭右开

    private ListNode quickSort(ListNode start, ListNode end) {

        // base case

        if (start == end || start.next == end) {

            return start;

        }

        // 选择第一个结点为pivot

        ListNode pivot = start;

        // left, right 都指向pivot

        ListNode left = pivot, right = pivot;

        // 遍历 pivot 之后，end之前的所有结点，将小于 pivot 的放到 pivot 之前；否者放到 pivot 后面

        ListNode cur = pivot.next;

        while (cur != end) {

            // 下面的插入操作会修改 cur.next

            ListNode next = cur.next;

            if (cur.val < pivot.val) {

                cur.next = left;

                left = cur;

            } else {

                right.next = cur;

                right = cur;

            }

            cur = next;

        }

        // 重要，将操作好的链表的末尾指向 end

        right.next = end;

        ListNode pre = quickSort(left, pivot);

        ListNode post = quickSort(pivot.next, end);

        // 重要，前后两段链表通过 pivot 连接起来

        pivot.next = post;

        return pre;

    }

}

152. 乘积最大子数组

class Solution {

    public int maxProduct(int[] nums) {

        int len = nums.length;

        // 状态： dp[i][0]:以下标i结尾的子数组的最大乘积

        //       dp[i][1]:以下标i结尾的子数组的最小乘积

        int[][] dp = new int[len][2];

        //base case

        dp[0][0] = nums[0];

        dp[0][1] = nums[0];

        int max = nums[0];

        for (int i = 1; i < len; i++) {

            if (nums[i] > 0) {

                dp[i][0] = Math.max(nums[i], nums[i] * dp[i - 1][0]);

                dp[i][1] = Math.min(nums[i], nums[i] * dp[i - 1][1]);

            } else {

                dp[i][0] = Math.max(nums[i], nums[i] * dp[i - 1][1]);

                dp[i][1] = Math.min(nums[i], nums[i] * dp[i - 1][0]);

            }

            max = Math.max(max, dp[i][0]);

        }

        return max;

    }

}

155. 最小栈

class MinStack {

    /** initialize your data structure here. */

    private Deque<Integer> stack;

    // 用额外一个栈存储最小值

    private Deque<Integer> minstack;

    public MinStack() {

        stack = new LinkedList<>();

        minstack = new LinkedList<>();

    }

    public void push(int val) {

        stack.push(val);

        if (minstack.isEmpty() || val < minstack.peek()) {

            minstack.push(val);

        } else {

            minstack.push(minstack.peek());

        }

    }

    public void pop() {

        stack.pop();

        minstack.pop();

    }

    public int top() {

        return stack.peek();

    }

    public int getMin() {

        return minstack.peek();

    }

}

/**

 * Your MinStack object will be instantiated and called as such:

 * MinStack obj = new MinStack();

 * obj.push(val);

 * obj.pop();

 * int param_3 = obj.top();

 * int param_4 = obj.getMin();

 */

160. 相交链表

思路：指向两个链表的指针一起分别向后移，如果没有剩余元素就移动到另一条链表，然后继续后移。如果有交点，相遇时就不为null。

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode lA = headA, lB = headB;

        while (lA != lB) {

            lA = lA == null ? headB : lA.next;

            lB = lB == null ? headA : lB.next;

        }

        return lA;

    }

}

169. 多数元素

思路一：用map记录每个元素的出现次数：

class Solution {

    public int majorityElement(int[] nums) {

        int threshold = nums.length / 2;

        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {

            map.put(num, map.getOrDefault(num, 0) + 1);

            if (map.get(num) > threshold) {

                return num;

            }

        }

        throw new IllegalArgumentException("majority element not exist!");

    }

}

思路二：排序：

class Solution {

    public int majorityElement(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length / 2];

    }

}

思路三：摩尔投票，很简单：记录当前字符和出现频次，如果字符相同则频次加1，否则减1，减1后若频次为0则直接更换当前字符和频次。

class Solution {

    public int majorityElement(int[] nums) {

        int curElement = nums[0];

        int cnt = 1;

        for (int i = 1; i < nums.length; i++) {

            if (curElement == nums[i]) {

                cnt++;

            } else {

                cnt--;

                if (cnt == 0) {

                    curElement = nums[i];

                    cnt = 1;

                }

            }

        }

        return curElement;

    }

}

198. 打家劫舍

思路：动态规划

class Solution {

    public int rob(int[] nums) {

        int len = nums.length;

		//状态： dp[i] 表示 有i间房屋时可以偷窃的最大金额

        int[] dp = new int[len + 1];

        //base case

        dp[0] = 0;

        dp[1] = nums[0];

        int max = nums[0];

        for (int i = 2; i < len + 1; i++) {

            // 第 i - 1 个房间 可以偷， 也可以不偷

            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);

            max = Math.max(max, dp[i]);

        }

        return max;

    }

}

200. 岛屿数量

思路：DFS。

对于二维矩阵中象成一个对每个节点来说，他有上、下、左、右四个邻居，可以将每个岛屿都看成一个图。
从任意一个陆地进入开始遍历，遍历完1次就代表发现了一个岛屿。注：图不像树那样是有向的，遍历可能会访问重复结点，一般需要用额外结构表示结点是否已经被访问过。此题可以直接在矩阵上将1修改为2表示结点已经访问过。

在原矩阵中标记是否访问过：

class Solution {

    public int numIslands(char[][] grid) {

        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++;

                }

            }

        }

        return count;

    }

    private void dfs(char[][] grid, int row, int col) {

        //base case

        if (!inArea(grid, row, col)) {

            return;

        }

        if (grid[row][col] != '1') {

            return;

        }

        //已访问

        grid[row][col] = '2';

        dfs(grid, row + 1, col);

        dfs(grid, row - 1, col);

        dfs(grid, row, col + 1);

        dfs(grid, row, col - 1);

    }

    private boolean inArea(char[][] grid, int row, int col) {

        return row >= 0 && row < grid.length &&

            col >= 0 && col < grid[0].length;

    }

}

使用额外空间标记是否已经访问过：

class Solution {

    // 标记是否访问过

    private boolean[][] visited;

    public int numIslands(char[][] grid) {

        int row = grid.length;

        int col = grid[0].length;

        visited = new boolean[row][col];

        int cnt = 0;

        for (int i = 0; i < row; i++) {

            for (int j = 0; j < col; j++) {

                if (grid[i][j] == '1' && !visited[i][j]) {

                    dfs(grid, i, j);

                    cnt++;

                }

            }

        }

        return cnt;

    }

    private void dfs (char[][] grid, int i, int j) {

        if (!inArea(grid, i, j)) {

            return;

        }

        if (grid[i][j] != '1' || visited[i][j]) {

            return;

        }

        visited[i][j] = true;

        dfs(grid, i + 1, j);

        dfs(grid, i, j + 1);

        dfs(grid, i - 1, j);

        dfs(grid, i, j - 1);

    }

    private boolean inArea(char[][] grid, int row, int col) {

        return row >= 0 && row < grid.length &&

            col >= 0 && col < grid[0].length;

    }

}

推荐阅读：岛屿类问题的通用解法、DFS 遍历框架，最大人工岛

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) {

        //始终指向当前结点的前一个结点

        ListNode pre = null;

        //当前结点

        ListNode cur = head;

        while (cur != null) {

            //用来保存当前结点的下一个结点

            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

思路二：递归（锻炼递归思维）：

首先给出函数定义，如此题：ListNode reverseList(ListNode head)
1. 反转以head为头结点的链表
2. 返回反转后链表的头结点
不要用脑袋去模拟递归栈，根据函数的定义去处理递归的子问题，即具体到一个结点要做的事情
确定base case

class Solution {

    public ListNode reverseList(ListNode head) {

        if (head == null) {

            return head;

        }

        //base case, 当链表只有一个结点时退出递归

        if (head.next == null) {

            return head;

        }

        /**

         * 具体到头结点来说，反转当前链表只需要两步：

         *  1.反转以head.next为头的链表

         *  2.将head插入head.next为头的链表反转之后的链表末尾

         */

        ListNode vhead = reverseList(head.next); //根据递归函数定义，返回反转之后的链表头

        //反转之后head.next位于链表尾部，将head插入head.next之后

        head.next.next = head;

        head.next = null;

        return vhead;

    }

}

巴特西