LeetCode 题解

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int dp[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = 0x3f3f3f3f;
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                    continue;
                }
                if (i - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + grid[i][j]);
                }
                if (j - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + grid[i][j]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    long last;

    // = = 故意的吧
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        last = Long.MIN_VALUE;
        return dfs(root);
    }

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean left = dfs(node.left);
        if (!left) {
            return false;
        }
        if (node.val > last) {
            last = node.val;
        } else {
            return false;
        }
        return dfs(node.right);
    }
}

public boolean isBalanced(TreeNode root) {
  return checkBalanced(root) >= 0;
}

// 由于 Java 只能有一个返回值，无法同时返回高度和是否平衡
// 所以定义返回值为子树的高度，当为 -1 时表示不平衡
//
// 注意不能只看根节点的左右子树高度，必须判断每个子树
// 比如：
//        1
//       /  \
//      2    3
//     /      \
//    4        5
//   /          \
//  6            7
public int checkBalanced(TreeNode node) {
  if (node == null) return 0;
  int left = checkBalanced(node.left);
  if (left < 0) {
    return -1;
  }
  int right = checkBalanced(node.right);
  if (right < 0) {
    return -1;
  }
  return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
}

class Solution {
    int ans;
    public int sumNumbers(TreeNode root) {
        ans = 0;
        if (root == null) return 0;
        dfs(root, 0);
        return ans;
    }

    void dfs(TreeNode node, int n) {
        if (node.left == null && node.right == null) { // 叶子节点
            ans += n * 10 + node.val;
            return;
        }
        if (node.left != null)
            dfs(node.left, n * 10 + node.val);
        if (node.right != null)
            dfs(node.right, n * 10 + node.val);
    }
}

/*
 * 单链表判环，并找出起点
 * 时间复杂度 O(n)，空间复杂度 O(1)
 *
 * 分析：
 *
 * head -> node -> cycle_start -> node -> node -> node
 *                      ^                          |
 *                      |--------------------------v
 *
 * 如图所示，使用快慢指针遍历链表，假设头节点 head 到 环起始节点 cycle_start 的长度为 m1，从环起始节点 cycle_start 到快慢指针相遇点的长度为 m2，环的长度为 cycle_length
 * 相遇时，slow 指针所走长度为 m1 + m2，fast 指针比 slow 节点多走了一圈，其所走长度为 2 * (m1 + m2) = m1 + m2 + cycle_length，推导出 cycle_length = m1 + m2，即 slow 指针所走的长度
 * 另外，由于 slow 指针到 cycle_start 节点的距离为 cycle_length - m2 = m1，head 指针到 cycle_start 节点的距离也为 m1，所以只需要从 相遇点 和 head 节点同时遍历直到相遇就能找到环起始节点了
 * 为什么快指针和慢指针一定会相遇 且 相遇时前者比后者恰好多走一圈：https://www.zhihu.com/question/23208893/answer/117115415
 */
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode [val=" + val + "]";
    }
}

public class LinkedListCycle {
    public static ListNode checkCycle(ListNode head) {
        if (head == null) return null;

        ListNode slow = head, fast = head;
        do {
            if (fast.next == null || fast.next.next == null) {
                return null; // 不存在环
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        ListNode start = head;
        while (start != slow) {
            start = start.next;
            slow = slow.next;
        }
        return start; // 环起点
    }

    // test
    public static void main(String[] args) {
        ListNode c7 = new ListNode(7, null);
        ListNode c6 = new ListNode(6, c7);
        ListNode c5 = new ListNode(5, c6);
        ListNode c4 = new ListNode(4, c5);
        ListNode c3 = new ListNode(3, c4);
        ListNode c2 = new ListNode(2, c3);
        ListNode c1 = new ListNode(1, c2);

        System.out.println(checkCycle(c1));

        c7.next = c3;

        System.out.println(checkCycle(c1));
    }
}

/*
 * 在普通的栈操作上添加了一个求最小值的操作
 *
 * 举个例子：
 * push 4  [4]           min=4
 * push 2  [4, 2]        min=2
 * push 3  [4, 2, 3]     min=2
 * push 1  [4, 2, 3, 1]  min=1
 * pop     [4, 2, 3]     min=2
 * pop     [4, 2]        min=2
 * pop     [4]           min=4
 *
 * 很容易想到，如果要在 O(1) 时间内求栈中的最小元素，需要用额外的空间来换取时间
 * 可以看出，如果能在栈操作过程中记录下最小值，当然只用单个变量记录当前的最小值肯定不行，因为还有出栈操作，出栈后最小值可能往回变大
 * 所以可以，记录下每一个时刻栈中的最小值
 * 即再用一个栈
 * - 每次 push 后同步插入一个元素 (min(top(), x))，表示当前栈中的最小值
 * - 每次  pop 后同步移除栈顶元素
 */
class MinStack {
    private Stack<Integer> items = new Stack<>();
    private Stack<Integer> minItems = new Stack<>();

    public MinStack() {}
    
    public void push(int x) {
        int min = minItems.empty() ? x : Math.min(minItems.peek(), x);
        items.push(x);
        minItems.push(min);
    }
    
    public void pop() {
        items.pop();
        minItems.pop();
    }
    
    public int top() {
        return items.peek();
    }
    
    public int getMin() {
        return minItems.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

/**
 * 判断链表是否相交，并求出交点
 * 时间复杂度 O(n)，空间复杂度 O(1)
 */
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode[ " + "val: " + val + " ]";
    }
}

public class IntersectionLinkedList {
    public static ListNode checkAcross(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return null;

        int length1 = 1, length2 = 1;
        ListNode p = head1, q = head2;
        while (p.next != null) {
            p = p.next;
            length1++;
        }

        while (q.next != null) {
            q = q.next;
            length2++;
        }

        if (p != q) return null;

        int lengthc = Math.abs(length1 - length2);
        p = head1;
        q = head2;
        if (length1 > length2) {
            for (int i = 0; i < lengthc; i++) {
                p = p.next;
            }
        } else {
            for (int i = 0; i < lengthc; i++) {
                q = q.next;
            }
        }

        while (p != q) {
            p = p.next;
            q = q.next;
        }

        return p;
    }

    // test
    public static void main(String[] args) {
        ListNode p6 = new ListNode(6, null);
        ListNode p5 = new ListNode(5, p6);
        ListNode p4 = new ListNode(4, p5);
        ListNode p3 = new ListNode(3, p4);
        ListNode p2 = new ListNode(2, p3);
        ListNode p1 = new ListNode(1, p2);

        ListNode q2 = new ListNode(8, p5);
        ListNode q1 = new ListNode(9, q2);

        System.out.println(checkAcross(p1, q1));
    }
}

// 最简单的做法当然是不断除以 2，然后判断末尾是否是 1 即可，复杂度：O(logN)，其实已经足够快了
// 不过还有优化的空间，如下所示，二进制中存在大量 0，参考 “231-2的幂”，通过 n & (n - 1) 不断“去掉”最后一个 1，从而跳过一些多余的判断，达到优化的目的
//   10010000001000010
// ^ 10010000001000001
// -------------------
// = 10010000001000000
// ^ 10000000000111111
// -------------------
// = 10010000000000000
//   10000000000000000
//   00000000000000000
public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans ++;
            n &= (n - 1);
        }
        return ans;
    }
}

int ans;
int n, m;
char **grid;
int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};

void dfs(int x, int y) {
    grid[x][y] = '0';
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] != '1') {
            continue;
        }
        dfs(tx, ty);
    }
}

int numIslands(char** input, int gridSize, int* gridColSize) {
    if (gridSize == 0) {
        return 0;
    }

    n = gridSize;
    m =  gridColSize[0];
    ans = 0;
    grid = input;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                ans++;
                dfs(i, j);
            }
        }
    }
    return ans;
}

/**
 * 逆置单链表
 * 时间复杂度 O(n)，空间复杂度 O(1)
 */
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class ReverseLinkedList {

    /*
     * LeetCode 206
     *
     * head 始终指向头结点，p 指向当前需要逆置到头结点的节点，q 是一个辅助指针，用于遍历过程中临时指向 p 的下一个节点
     * 从第二个节点开始，依次将节点插入到头结点处
     *
     * h
     * 1 2 3 4 5
     *   p
     *
     * h
     * 3 2 1 4 5
     *       p q
     */
    public static ListNode reverse(ListNode head) {
        if (head == null) return null; // 0
        if (head.next == null) return head; // 1

        ListNode p = head.next;
        ListNode q = null;
        head.next = null; // 尾指针的下一个节点置为空
        while (p != null) {
            q = p.next;
            p.next = head; // 插入到头结点
            head = p;
            p = q;
        }

        return head;
    }

    /*
     * LeetCode 92
     * 
     * 翻转 [l, r] 区间，下标从 1 开始
     *
     * 题目分为两种情况，一种是从第一个节点开始翻转，一种是中间节点开始翻转
     * 为了简单起见，可以新建一个虚拟的头指针
     *
     * (1) 先找到翻转起点的前一个节点
     * (2) 从翻转起点的后一个节点开始依次翻转，将其插入到起点前一个节点的后面
     *
     *  revPre  revHead    p     q
     *    1         2      3     4     5
     *
     *    1         3      2     4     5
     *
     *                           p     q
     *
     *    1         4      3     2     5
     *
     *                        revHeadCopy
     *                                 p     q
     */
    public ListNode reverseBetween(ListNode head, int l, int r) {
        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;

        ListNode revPre = virtualHead;
        for (int i = 1; i < l; i++) revPre = revPre.next;

        ListNode revHead = revPre.next; // 翻转起点
        ListNode revHeadCopy = revHead;
        ListNode p = revHead.next; // 从翻转起点的下一个节点开始翻转
        for (int i = l + 1; i <= r && p != null; i++) { // 依次翻转
            ListNode q = p.next;
            p.next = revHead; // 插入到头结点
            revHead = p;
            p = q;
        }
        revPre.next = revHead; // 原翻转起点前一个节点的 next 指针修改
        revHeadCopy.next = p;  // 原翻转起点的 next 指针修改
        return virtualHead.next;
    }

    /*
     * 每 K 个一组进行反转
     *
     * 1 2 3  4 5
     * 3 2 1  5 4
     *
     * 分段处理一下就行了，同样地，为了方便，添加一下虚拟头结点
     */
    public ListNode reverseKGroup1(ListNode head, int k) {
        if (k == 1) return head;

        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;

        ListNode c = virtualHead;
        while (c.next != null) {
            ListNode groupPre = c;               // 每组翻转头结点的前一个节点
            ListNode groupHead = groupPre.next;  // 每组翻转的头结点
            ListNode groupHeadCopy = groupHead;
            ListNode p = groupHead.next;         // 从头结点的后一个节点开始翻转
            for (int i = 2; i <= k && p != null; i++) {
                ListNode q = p.next;
                p.next = groupHead;  // 插入到头结点
                groupHead = p;
                p = q;
            }
            groupPre.next = groupHead; // 原翻转起点前一个节点的 next 指针修改
            groupHeadCopy.next = p;    // 原翻转起点的 next 指针修改
            c = groupHeadCopy;         // 修改 c 为下一组翻转区间头节点的前一个节点
        }

        return virtualHead.next;
    }

    /*
     * LeetCode 25
     *
     * 每 K 个一组进行反转，如果不足 k 个保持不变，可以通过长度判断
     *
     * 1 2 3  4 5
     * 3 2 1  4 5
     *
     * 分段处理一下就行了，同样地，为了方便，添加一下虚拟头结点
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        if (k == 1) return head;

        int length = 0;
        for (ListNode p = head; p != null; p = p.next) length++;

        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;

        ListNode c = virtualHead;
        while (c.next != null && length >= k) {
            ListNode groupPre = c;               // 每组翻转头结点的前一个节点
            ListNode groupHead = groupPre.next;  // 每组翻转的头结点
            ListNode groupHeadCopy = groupHead;
            ListNode p = groupHead.next;         // 从头结点的后一个节点开始翻转
            for (int i = 2; i <= k && p != null; i++) {
                ListNode q = p.next;
                p.next = groupHead;  // 插入到头结点
                groupHead = p;
                p = q;
            }
            groupPre.next = groupHead; // 原翻转起点前一个节点的 next 指针修改
            groupHeadCopy.next = p;    // 原翻转起点的 next 指针修改
            c = groupHeadCopy;         // 修改 c 为下一组翻转区间头节点的前一个节点
            length -= k;
        }

        return virtualHead.next;
    }

    // test
    public static void main(String[] args) {
        ListNode n5 = new ListNode(5, null);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);

        ListNode p = new ReverseLinkedList().reverseKGroup2(n1, 3);
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
}

class Solution {
    private int n;
    private List<Integer>[] edges;
    private int[] de;

    public boolean canFinish(int nn, int[][] input) {
        n = nn;
        edges = new ArrayList[n];
        de = new int[n];

        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < input.length; i++) {
            int u = input[i][0];
            int v = input[i][1];
            // 0,1 => 0>1
            edges[u].add(v);
            de[v]++;
        }
        return check();
    }

    private boolean check() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (de[i] == 0) {
                q.add(i);
            }
        }
        int cnt = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            cnt++;
            for (int i = 0; i < edges[u].size(); i++) {
                int v = edges[u].get(i);
                de[v]--;
                if (de[v] == 0) {
                    q.add(v);
                }
            }
        }
        return cnt == n;
    }
}

class Trie {
    static int N = 26;
    static class Node {
        Node[] next = new Node[N];
        int vis;
    }

    private Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node node = root;
        Node next;
        for (int i = 0; i < word.length(); i++) {
            int pos = getPos(word.charAt(i));
            next = node.next[pos];
            if (next == null) {
                next = new Node();
                node.next[pos] = next;
            }
            node = next;
        }
        node.vis++;
    }
    
    public boolean search(String word) {
        return searchInternal(word, false);
    }
    
    public boolean startsWith(String prefix) {
        return searchInternal(prefix, true);
    }

    private boolean searchInternal(String word, boolean prefix) {
        Node node = root;
        Node next;
        for (int i = 0; i < word.length(); i++) {
            int pos = getPos(word.charAt(i));
            next = node.next[pos];
            if (next == null) {
                return false;
            }
            node = next;
        }
        if (prefix) {
            return true;
        }
        return node.vis > 0;
    }

    private int getPos(char c) {
        return c - 'a';
    }
}

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int ans = 0;
        int sum = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            while (j < nums.length && sum < s) {
                sum += nums[j++];
            }
            if (sum >= s) {
                if (ans == 0) {
                    ans = j - i;
                } else {
                    ans = Math.min(ans, j - i);
                }
            }
            sum -= nums[i];
        }
        return ans;
    }
}

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        int l = -1;
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 >= nums.length || nums[i] + 1 != nums[i + 1]) {
                if (l == -1) {
                    ans.add(String.valueOf(nums[i]));
                } else {
                    ans.add(String.format("%s->%s", l, nums[i]));
                    l = -1;
                }
            } else {
                if (l == -1) {
                    l = nums[i];
                }
            }
        }
        return ans;
    }
}

// 2 的幂对应的二进制中一定只有一个 1
// 所以只需要 n & (n - 1)，它的作用是去掉二进制中的最后一个 1，如果结果大于 0，说明不只一个 1，不是 2 的幂
//   00010000
// ^ 00011111
// ----------
// = 00000000
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

/**
 * 两个栈实现队列
 * 为了保持先进先出的特性，使用两个栈
 *
 * - 判空：如果栈 1 和栈 2 都为空则为空
 * - 入队：直接进入栈 1 中
 * - 出队：先判断栈 2 中是否存在元素
 * --- 如果存在：直接出栈
 * --- 如果不存在：将栈 1 中的元素倒入栈 2 中，再出栈
 */
public class DoubleStack2Queue<T> {
    private Stack<T> s1 = new Stack<>();
    private Stack<T> s2 = new Stack<>();

    public DoubleStack2Queue() { }

    // 判空
    private boolean empty() {
        return s1.empty() && s2.empty();
    }

    // 入队
    public void push(T x) {
        s1.push(x);
    }

    // 出队
    public T pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    // test
    public static void main(String[] args) {
        DoubleStack2Queue<Integer> q = new DoubleStack2Queue<>();
        q.push(1);
        q.push(2);
        System.out.println(q.pop());
        System.out.println(q.pop());
        q.push(2);
        q.push(3);
        q.push(4);
        q.push(5);
        while (!q.empty()) {
            System.out.println(q.pop());
        }
    }

}

class Solution {
    public int numSquares(int n) {
        int maxNum = (int)Math.sqrt(n); // 25 1 4 9 16 25
        int[] square = new int[maxNum];
        for (int i = 0; i < maxNum; i++) {
            square[i] = (i + 1) * (i + 1);
        }
        // 1 4 9 16

        // ans[i] = min(ans[i], ans[i - squre[i]] + 1) 
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0));
        while (!q.isEmpty()) {
            Node u = q.poll();
            if (u.val == n) {
                 return u.cnt;
            }
            for (int i = 0; i < maxNum; i++) {
                int nextVal = u.val + square[i];
                if (nextVal <= n) {
                    if (nextVal == n) {
                        return u.cnt + 1;
                    }
                    q.add(new Node(nextVal, u.cnt + 1));
                }
            }
        }
        return 0; // xx
    }

    static class Node {
        int val;
        int cnt;

        Node() {}
        Node(int val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
    }
}

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList();
        if (root == null) {
            return result;
        }
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        int nowLevelNum = 1;
        int nextLevelNum = 0;
        List<Integer> items = new ArrayList<>();
        while (!q.isEmpty()) {
            Node now = q.poll();
            items.add(now.val); // 出队时添加到列表中
            for (Node next : now.children) {
                nextLevelNum++;
                q.add(next);
            }
            nowLevelNum--;
            if (nowLevelNum == 0) { // 这一层遍历完成，新建一个列表
                result.add(items);
                items = new ArrayList<>();
                nowLevelNum = nextLevelNum;
                nextLevelNum = 0;
            }
        }
        return result;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] input) {
        // 1 2       1
        // 1   3
        //   2 3     2
        //     3 4   3

        if (input == null || input.length == 0) {
            return 0;
        }

        int n = input.length;
         Interval[] intervals = new Interval[n];
         for (int i = 0; i < n; i++) {
             intervals[i] = new Interval(input[i][0], input[i][1]);
         }
         Arrays.sort(intervals);
         int cnt = 1;
         Interval last = intervals[0];
         for (int i = 1; i < n; i++) {
             if (intervals[i].start >= last.end) {
                 last = intervals[i];
                 cnt++;
             }
         }
         return n - cnt; // 2
    }

    class Interval implements Comparable<Interval> {
        int start;
        int end;
        
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int compareTo(Interval to) {
            return this.end - to.end;
        }
    }
}

class Solution {
    public int findCircleNum(int[][] input) {
        int n = input.length;
        boolean vis[] = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i, n, input, vis);
                ans++;
            }
        }
        return ans;
    }

    private void dfs(int s, int n, int[][] input, boolean vis[]) {
        vis[s] = true;
        for (int t = 0; t < n; t++) {
            if (input[s][t] > 0 && !vis[t]) {
                dfs(t, n, input, vis);
            }
        }
    }
}