LeetCode 101-200

17785 字
89 分钟
LeetCode 101-200
2020-01-01
LeetCode
LeetCode
/
Algorithms

LeetCode Problems 101-200.

101. Symmetric Tree#

https://leetcode.com/problems/symmetric-tree/

一棵树对称有两种情况：

  • 当前节点为空
  • 左右子树对称

因此我们可以构造一个辅助比较函数判断左右子树是否对称。如果一边为空节点，另一边也必须为空节点；另外对称节点的值应当相等，并且左子的儿子还要和右子的儿子对称相等（无论是否为空节点）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || helper(root.left, root.right);
    }


    public boolean helper(TreeNode left, TreeNode right) {
        // if one side is null, the other side must be null either
        if (left == null || right == null) {
            return left == right;
        }


        // nodes at two sides should have same value
        if (left.val != right.val) {
            return false;
        }


        // children's children should be same
        return helper(left.left, right.right) && helper(left.right, right.left);
    }
}

102. Binary Tree Level Order Traversal#

https://leetcode.com/problems/binary-tree-level-order-traversal/

第一种方法，使用DFS，遍历至当前节点时，直接将其添加到这个节点所在的层数数组中。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        helper(root, result, 0);
        return result;
    }


    private void helper(TreeNode curNode, List<List<Integer>> result, int level) {
        if (curNode == null) {
            return;
        }


        // add new level
        if (result.size() <= level) {
            result.add(new LinkedList<Integer>());
        }


        result.get(level).add(curNode.val);
        helper(curNode.left, result, level + 1);
        helper(curNode.right, result, level + 1);
    }
}

第二种方法，使用队列进行层次遍历。每一层循环时，队列中的元素都是当前层的元素。遍历队列中每个元素，只要其左子右子不空，就加入队列，再将当前队首元素弹出。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }


        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> tempList = new LinkedList<Integer>();
            for (int i = 0; i < size; i++) {
                if (q.peek().left != null) {
                    q.offer(q.peek().left);
                }
                if (q.peek().right != null) {
                    q.offer(q.peek().right);
                }
                tempList.add(q.poll().val);
            }


            result.add(tempList);
        }
        return result;
    }
}

103. Binary Tree Zigzag Level Order Traversal#

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

在上一题的DFS基础上略加修改，根据当前层数的奇偶性，决定按顺序添加还是倒序添加即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        helper(root, result, 0);
        return result;
    }


    public void helper(TreeNode curNode, List<List<Integer>> result, int level) {
        if (curNode == null) {
            return;
        }


        // add new level
        if (result.size() <= level) {
            result.add(new LinkedList<Integer>());
        }


        // decide insert position by odd / even level
        if (level % 2 == 0) {
            result.get(level).add(curNode.val);
        } else {
            result.get(level).add(0, curNode.val);
        }


        helper(curNode.left, result, level + 1);
        helper(curNode.right, result, level + 1);
    }
}

104. Maximum Depth of Binary Tree#

https://leetcode.com/problems/maximum-depth-of-binary-tree/

使用DFS，分别比较左子树和右子树的深度，取最大值+1（加上自身的深度），累积至根节点得到结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return height(root);
    }


    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }


        // height of left subtree and right subtree
        int left = height(node.left), right = height(node.right);
        return Math.max(left, right) + 1;
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal#

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

在只有前序遍历的情况下，我们只能模糊地知道我们会先遍历到根节点，但之后遍历左右子树时，我们不知道什么时候结束遍历左子树，开始遍历右子树。所以我们需要中序遍历进行辅助，因为中序遍历会先于遍历根节点之前遍历完左子树。我们只需要拿preorder遇到的根节点到inorder中搜索，就能知道左、右子树分别是哪些元素。

使用一个变量rootIdx跟踪前序遍历数组，在inorder中到当前根节点preorder[rootIdx]。inorder左侧的点全部在根节点左子树上，右侧的点都在根节点右子树上。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int rootIdx = 0; // index of current root node in preorder


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length || inorder.length == 0) {
            return null;
        }


        return builder(preorder, inorder, 0, inorder.length - 1);
    }


    private TreeNode builder(int[] preorder, int[] inorder, int start, int end) {
        if (start > end) {
            return null;
        }


        TreeNode node = new TreeNode(preorder[rootIdx]);
        rootIdx++;


        if (start == end) {
            return node;
        }


        // find current element in inorder array
        // this element will be the split point
        int index = 0;
        for (int i = end; i >= start; i--) {
            if (inorder[i] == node.val) {
                index = i;
                break;
            }
        }


        node.left = builder(preorder, inorder, start, index - 1);
        node.right = builder(preorder, inorder, index + 1, end);
        return node;
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal#

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

与上一题思路类似，需要注意的是先构造右子树，再构造左子树。这是因为后序遍历先遍历右子树再遍历左子树，和前序遍历相反。另外根据对称性，从postorder中提取根节点时也应该从后往前遍历。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int rootIdx = 0;  // index of current root node in postorder


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length || inorder.length == 0) {
            return null;
        }


        // initialization, searched from the end of postorder
        rootIdx = postorder.length - 1;


        return builder(postorder, inorder, 0, postorder.length - 1);
    }


    private TreeNode builder(int[] postorder, int[] inorder, int start, int end) {
        if (start > end) {
            return null;
        }


        TreeNode node = new TreeNode(postorder[rootIdx]);
        rootIdx--;


        if (start == end) {
            return node;
        }


        // find current element in inorder array
        // this element will be the split point
        int index = 0;
        for (int i = end; i >= start; i--) {
            if (inorder[i] == node.val) {
                index = i;
                break;
            }
        }


        node.right = builder(postorder, inorder, index + 1, end);
        node.left = builder(postorder, inorder, start, index - 1);
        return node;
    }
}

107. Binary Tree Level Order Traversal II#

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

仍然使用DFS，但补齐至当前层数时，需要倒序添加层数（第一层为最后，第二层为倒数第二，…），获取层数的结果时应以总数和当前层数之差作为索引。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        helper(root, result, 0);
        return result;
    }


    private void helper(TreeNode curNode, List<List<Integer>> result, int level) {
        if (curNode == null) {
            return;
        }


        // add new level
        if (result.size() <= level) {
            result.add(0, new LinkedList<Integer>());
        }


        result.get(result.size() - 1 - level).add(curNode.val);
        helper(curNode.left, result, level + 1);
        helper(curNode.right, result, level + 1);
    }
}

108. Convert Sorted Array to Binary Search Tree#

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

结合二分查找思想，总是将当前中位数作为根节点，比其小的数位于左子树，比其大的数位于右子树。当子数组区间下标重叠，返回空节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        TreeNode result = helper(nums, 0, nums.length - 1);
        return result;
    }


    private TreeNode helper(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }


        // find median of the array, set as root node
        int mid = low + (high - low) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, low, mid - 1);
        node.right = helper(nums, mid + 1, high);


        return node;
    }
}

109. Convert Sorted List to Binary Search Tree#

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

使用快慢指针获取到子链表的中间节点，其余仍然使用二分法。

/**
 * 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; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return helper(head, null);
    }


    private TreeNode helper(ListNode head, ListNode tail) {
        if (head == tail) {
            return null;
        }


        // find the median node, set it as root
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }


        TreeNode mid = new TreeNode(slow.val);
        mid.left = helper(head, slow);
        mid.right = helper(slow.next, tail);
        return mid;
    }
}

110. Balanced Binary Tree#

https://leetcode.com/problems/balanced-binary-tree/

此题实际是一个计算树高度的过程，如果树的高度不是-1（不平衡的情况），说明树是平衡的。讨论特殊情况如下：

  • 遇到空节点，返回0
  • 左子树或右子树的高度为-1，说明子树已经不平衡，那么以当前节点为根的树高度也为-1
  • 左、右子树高度差值大于1，则当前节点高度为-1

最后取左、右子树的高度最大值，并+1（节点自身），得到以当前节点为根的树的高度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1;
    }


    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }


        int leftHeight = helper(node.left);
        if (leftHeight == -1) {
            return -1;
        }


        int rightHeight = helper(node.right);
        if (rightHeight == -1) {
            return -1;
        }


        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }


        return Math.max(leftHeight, rightHeight) + 1;
    }
}

111. Minimum Depth of Binary Tree#

https://leetcode.com/problems/minimum-depth-of-binary-tree/

第一种方法，使用递归，与寻找最大深度的解法类似。注意当某一子树为空时，树的高度实际上就是另一个子树的高度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }


        int leftHeight = minDepth(root.left);
        int rightHeight = minDepth(root.right);
        return leftHeight == 0 || rightHeight == 0 ? leftHeight + rightHeight + 1
                                                   : Math.min(leftHeight, rightHeight) + 1;
    }
}

第二种方法，借用树的层次遍历思想，检查是否有某个节点不存在儿子。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }


        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int depth = 0;


        while (!q.isEmpty()) {
            int size = q.size();
            depth++;


            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();


                // no children, so one subtree will end here
                if (node.left == null && node.right == null) {
                    return depth;
                }


                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
        }


        return depth;
    }
}

112. Path Sum#

https://leetcode.com/problems/path-sum/

每向下一层递归时就更新targetSum的值，遇到叶子节点的值与当前sum相同则返回true。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }


        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }


        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

113. Path Sum II#

https://leetcode.com/problems/path-sum-ii/

回溯算法，无论当前递归内是否找到一条path，都需要在完成遍历后从临时数组中弹出最后一个数，这样才能尝试其他path。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new LinkedList<>();
        helper(result, new LinkedList<>(), root, sum);
        return result;
    }


    private void helper(List<List<Integer>> result, List<Integer> temp, TreeNode node, int sum) {
        if (node == null) {
            return;
        }


        temp.add(node.val);




        if (node.left == null && node.right == null && node.val == sum) {
            // find a path, remove the last node and return
            result.add(new LinkedList<>(temp));
            temp.remove(temp.size() - 1);
            return;
        } else {
            // else continue traveling down
            helper(result, temp, node.left, sum - node.val);
            helper(result, temp, node.right, sum - node.val);
        }


        // no path found, remove the last node
        temp.remove(temp.size() - 1);
    }
}

114. Flatten Binary Tree to Linked List#

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

解题思路如下：

  1. 寻找到当前节点右子树中最右的节点，如果为空则寻找其兄弟左节点
  2. 更新当前节点的右子为prev，这样能之前flatten的子树接到当前节点上；左子为空
  3. prev更新为当前节点，因为当前节点是最后一个被flatten的根节点
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode prev = null; // previous flattened node


    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }


        flatten(root.right);
        flatten(root.left);


        root.right = prev;
        root.left = null;


        prev = root;
    }
}

115. Distinct Subsequences#

https://leetcode.com/problems/distinct-subsequences/

使用动态规划，dp[i][j]表示s的前j个字符中，包含t的前i个字符的次数。考虑两种情况：

  • s的第j个字符与t的第i个字符不同，则dp[i+1][j+1]与dp[i+1][j]相同，因为s多出的这个字母不影响次数
  • s的第j个字符与t的第i个字符相同，则dp[i+1][j+1]不仅包括dp[i+1][j]，还包括dp[i][j]，因为要加上同时去掉了这对相同字母后，剩下的匹配次数。
class Solution {
    public int numDistinct(String s, String t) {
        int slen = s.length(), tlen = t.length();


        int[][] dp = new int[tlen+1][slen+1];


        // initialization, substring of s can always contain exactly 1 empty string
        for (int j = 0; j < slen; j++) {
            dp[0][j] = 1;
        }


        for (int i = 0; i < tlen; i++) {
            for (int j = i; j < slen; j++)  {
                dp[i+1][j+1] = (t.charAt(i) == s.charAt(j)) ? dp[i+1][j] + dp[i][j] : dp[i+1][j];
            }
        }


        return dp[tlen][slen];
    }
}

116. Populating Next Right Pointers in Each Node#

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

使用两个指针level和cur遍历整个树，其中level遍历逐层，cur遍历一层中的节点。对于每一个节点，完成两步修改：

  • 将cur的左儿子指向cur的右儿子
  • 如果cur本身和另一个兄弟相连，那么cur的右儿子和cur的兄弟的左儿子就是邻居关系，二者需要连起来
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;


    public Node() {}


    public Node(int _val) {
        val = _val;
    }


    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/


class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }


        Node level = root; // track each level
        Node cur = null; // track each node in one level


        while (level.left != null) {
            cur = level;


            while (cur != null) {
                // left child points to right child
                cur.left.next = cur.right;


                // if there is a right neighbor, right child points to right neighbor's left child
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }


                //
                cur = cur.next;
            }


            // move to next level
            level = level.left;
        }


        return root;
    }
}

117. Populating Next Right Pointers in Each Node II#

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

模拟层次遍历，cur指针指向当前层，curChild指向下一层。判断是否存在左子或右子，以此移动指针。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;


    public Node() {}


    public Node(int _val) {
        val = _val;
    }


    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/


class Solution {
    public Node connect(Node root) {
        Node cur = root;


        while (cur != null) {
            Node head = new Node(0); // dummy head of next level
            Node curChild = head; // child in the next level


            while (cur != null) {
                if (cur.left != null) {
                    curChild.next = cur.left;
                    curChild = curChild.next;
                }


                if (cur.right != null) {
                    curChild.next = cur.right;
                    curChild = curChild.next;
                }


                // move to cur's sibling
                cur = cur.next;
            }


            // move to next level
            cur = head.next;
        }


        return root;
    }
}

118. Pascal’s Triangle#

https://leetcode.com/problems/pascals-triangle/

遍历每一行的开始时，都在行首添加一个1，之后从第二个元素至倒数第二个元素，与下一个相邻元素进行累加即可。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if (numRows <= 0) {
            return result;
        }
        List<Integer> row = new ArrayList<>();


        for (int i = 0; i < numRows; i++) {
            // add '1' at head of each row
            row.add(0, 1);


            for (int j = 1; j < row.size() - 1; j++) {
                row.set(j, row.get(j) + row.get(j+1));
            }


            result.add(new ArrayList<>(row));
        }


        return result;
    }
}

119. Pascal’s Triangle II#

https://leetcode.com/problems/pascals-triangle-ii/

在上一题代码的基础上略作修改，只将最后一行作为结果输出即可。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);


        for (int i = 0; i < rowIndex; i++) {
            // add '1' at head of each row
            row.add(0, 1);


            for (int j = 1; j < row.size() - 1; j++) {
                row.set(j, row.get(j) + row.get(j+1));
            }
        }


        return row;
    }
}

120. Triangle#

https://leetcode.com/problems/triangle/

使用一维动态规划，自底向上迭代更新dp，选取相邻元素的最小值，再加上当前遍历的元素。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size() + 1];


        // bottom-up
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }


        return dp[0];
    }
}

121. Best Time to Buy and Sell Stock#

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

算出每天价格之间的差值，获利最大的时刻其实就是差值之和最大的时刻。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int maxDiff = 0, result = 0;


        for (int i = 1; i < prices.length; i++) {
            // difference between today and yesterday's prices
            maxDiff += (prices[i] - prices[i-1]);


            // find the max price difference
            maxDiff = Math.max(0, maxDiff);
            result = Math.max(maxDiff, result);
        }


        return result;
    }
}

122. Best Time to Buy and Sell Stock II#

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

贪心思想，只要有一天能赚钱，都用一次买卖赚走，累积利润即可得到结果。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int result = 0;


        for (int i = 1; i < prices.length; i++) {
            result += Math.max(0, prices[i] - prices[i-1]);
        }


        return result;
    }
}

123. Best Time to Buy and Sell Stock III#

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

使用两组变量cost和profit，分别表示两次买入的最小成本和两次卖出的最大利润。

需要注意，第二次买入的最小成本，建立在第一次卖出的最大利润之上（相当于拿已有的利润，再买入当前股票，两个数值合成为总成本）。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }


        int cost1 = Integer.MAX_VALUE, cost2 = Integer.MAX_VALUE;
        int profit1 = 0, profit2 = 0;


        for (int i = 0; i < prices.length; i++) {
            cost1 = Math.min(cost1, prices[i]);
            profit1 = Math.max(profit1, prices[i] - cost1);


            // cost2 will be based on profit1
            cost2 = Math.min(cost2, prices[i] - profit1);
            profit2 = Math.max(profit2, prices[i] - cost2);
        }


        return profit2;
    }
}

124. Binary Tree Maximum Path Sum#

https://leetcode.com/problems/binary-tree-maximum-path-sum/

对每一个节点，计算其左子树和右子树上的最大和，返回较大一侧的值与自身节点值之和。注意，Path Sum可包括两个分支，因此对于最大值的更新，要包括当前节点和左右子节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result = Integer.MIN_VALUE;


    public int maxPathSum(TreeNode root) {
        helper(root);
        return result;
    }


    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = Math.max(0, helper(node.left));
        int rightSum = Math.max(0, helper(node.right));


        // update current path sum
        result = Math.max(result, leftSum + rightSum + node.val);


        // max subtree sum + current node's value
        return Math.max(leftSum, rightSum) + node.val;
    }
}

125. Valid Palindrome#

https://leetcode.com/problems/valid-palindrome/

使用Character类的API，或者正则表达式解决。

class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() == 0 || s.length() == 1) {
            return true;
        }


        // String modified = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();


        int head = 0, tail = s.length() - 1;


        while (head <= tail) {
            if (Character.isLetter(s.charAt(head)) || Character.isDigit(s.charAt(head))) {
                if (Character.isLetter(s.charAt(tail)) || Character.isDigit(s.charAt(tail))) {
                    if (Character.toLowerCase(s.charAt(head)) != Character.toLowerCase(s.charAt(tail))) {
                        return false;
                    }


                    head++;
                    tail--;
                } else {
                    tail--;
                }
            } else {
                head++;
            }
        }


        return true;
    }
}

126. Word Ladder II#

https://leetcode.com/problems/word-ladder-ii/

先用用BFS，替换begin中每个单词的每一个字母，汇总得到每个单词能够转化得到的单词列表，存在map中。再使用DFS，依据单词列表的演化，将结果录入。

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();


        Set<String> dicts = new HashSet<>(wordList);
        if (!dicts.contains(endWord)) {
            return result;
        }


        Set<String> begin = new HashSet<>(), end = new HashSet<>();
        Map<String, List<String>> map = new HashMap<>();
        begin.add(beginWord);
        end.add(endWord);


        bfs(map, begin, end, dicts, false);


        List<String> tempList = new ArrayList<>();
        tempList.add(beginWord);
        dfs(map, result, tempList, beginWord, endWord);


        return result;
    }


    private void bfs(Map<String, List<String>> map, Set<String> begin, Set<String> end, Set<String> dicts, boolean reverse) {
        if (begin.size() == 0) {
            return;
        }
        dicts.removeAll(begin);


        // beginning set in next search
        Set<String> newBegin = new HashSet<>();


        boolean finish = false;


        for (String str : begin) {
            char[] chars = str.toCharArray();


            for (int i = 0; i < chars.length; i++) {
                // backup old alphabet
                char old = chars[i];


                // replace an alphabet with another
                for (char c = 'a'; c <= 'z'; c++) {
                    if (old == c) {
                        continue;
                    }
                    chars[i] = c;


                    String candidate = String.valueOf(chars);


                    // new word must be in wordList
                    if (!dicts.contains(candidate)) {
                        continue;
                    }


                    // new word is in end list
                    if (end.contains(candidate)) {
                        finish = true;
                    } else {
                        newBegin.add(candidate);
                    }


                    // str -> candidate's list
                    String key = reverse ? candidate : str;
                    String value = reverse ? str : candidate;
                    if (!map.containsKey(key)) {
                        map.put(key, new ArrayList<>());
                    }
                    map.get(key).add(value);
                }


                // restore old word
                chars[i] = old;
            }
        }


        // optional, swap newBegin and end to speed up
        if (!finish) {
            if (newBegin.size() > end.size()) {
                bfs(map, end, newBegin, dicts, !reverse);
            } else {
                bfs(map, newBegin, end, dicts, reverse);
            }
        }
    }


    private void dfs(Map<String, List<String>> map, List<List<String>> result, List<String> tempList, String beginWord, String endWord) {
        if (beginWord.equals(endWord)) {
            result.add(new ArrayList<>(tempList));
            return;
        }


        // current beginWord cannot transform to another work
        if (!map.containsKey(beginWord)) {
            return;
        }


        for (String word : map.get(beginWord)) {
            tempList.add(word);
            dfs(map, result, tempList, word, endWord);
            tempList.remove(tempList.size() - 1);
        }
    }
}

127. Word Ladder#

https://leetcode.com/problems/word-ladder/

由于这一题不需要不需要输出结果的具体值，因此没必要使用DFS跟踪变换过程，直接使用BFS获取结果长度即可。此外也不需要使用map，直接使用一个set统计已经访问过的单词即可。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);


        // wordList does not contain endWord
        if (!dict.contains(endWord)) {
            return 0;
        }


        Set<String> begin = new HashSet<>(), end = new HashSet<>(), visited = new HashSet<>();
        begin.add(beginWord);
        end.add(endWord);
        visited.add(beginWord);
        visited.add(endWord);


        int result = 1;


        while (!begin.isEmpty() && !end.isEmpty()) {
            // beginning set in next search
            Set<String> newBegin = new HashSet<>();


            for (String str : begin) {
                char[] chars = str.toCharArray();


                // replace an alphabet with another
                for (int i = 0; i < chars.length; i++) {
                    // backup old alphabet
                    char old = chars[i];


                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == old) {
                            continue;
                        }
                        chars[i] = c;


                        String candidate = String.valueOf(chars);


                        // new word must be in word list
                        if (!dict.contains(candidate)) {
                            continue;
                        }


                        // current transformation reaches the target
                        if (end.contains(candidate)) {
                            result++;
                            return result;
                        }


                        // skip visited word
                        if (visited.contains(candidate)) {
                            continue;
                        }


                        visited.add(candidate);
                        newBegin.add(candidate);
                    }


                    // restore old word
                    chars[i] = old;
                }
            }


            // one transformation
            result++;


            // optional, swap newBegin and end to speed up
            if (newBegin.size() > end.size()) {
                Set<String> temp = newBegin;
                newBegin = end;
                end = temp;
            }


            begin = newBegin;
        }


        return 0;
    }
}

128. Longest Consecutive Sequence#

https://leetcode.com/problems/longest-consecutive-sequence/

第一种做法，利用Set的迭代器，移除当前元素的相邻元素，统计能移除的最大个数。

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }


        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }


        int result = 0;
        while (!set.isEmpty()) {
            int base = set.iterator().next();
            set.remove(base);


            // start from base, remove adjacent elements
            int left = base, right = base;
            while (set.remove(--left));
            while (set.remove(++right));


            result = Math.max(result, right - left - 1);
        }


        return result;
    }
}

第二种做法，利用HashMap模拟Set，提取所有key，判断有多少个连续的key在map中。

class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], true);
        }


        int result = 0;
        for (Integer key: map.keySet()) {
            // avoid repeat counting
            if (!map.containsKey(key - 1)) {
                int length = 1;


                while (map.containsKey(key + length)) {
                    length++;
                }


                result = Math.max(result, length);
            }
        }


        return result;
    }
}

129. Sum Root to Leaf Numbers#

https://leetcode.com/problems/sum-root-to-leaf-numbers/

自顶向下，每达到一个节点，sum乘10再加上当前节点的值。如果当前节点有儿子，继续向下递归计算子树中的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }


    private int helper(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }


        int updatedVal = sum * 10 + node.val;


        if (node.left == null && node.right == null) {
            return updatedVal;
        }


        return helper(node.left, updatedVal) + helper(node.right, updatedVal);
    }
}

130. Surrounded Regions#

https://leetcode.com/problems/surrounded-regions/

使用DFS：

  • 从矩阵边缘开始检查，如果某个元素为'O'，将这个元素以及邻近的'O'都改为'E'。这些格子没有完全被'X'包围，因此需要排除
  • 将图上剩余所有的'O'改为'X'，再将所有的'E'改为'O'
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int row = board.length, col = board[0].length;


        // exclude 'O' om first and last columns
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col - 1);
            }
        }


        // exclude 'O' in first and last rows
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row - 1][j] == 'O') {
                dfs(board, row - 1, j);
            }
        }


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }


                // restore excluded grids
                if (board[i][j] == 'E') {
                    board[i][j] = 'O';
                }
            }
        }
    }


    private void dfs(char[][] board, int x, int y) {
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 || board[x][y] == 'E' || board[x][y] == 'X') {
            return;
        }


        // exclude this grid since it is not surrounded by 'X' 4-directionally
        board[x][y] = 'E';


        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

131. Palindrome Partitioning#

https://leetcode.com/problems/palindrome-partitioning/

使用回溯算法，从当前index开始，截取s[index : i+1]的字符串，判断是否为回文串；之后再判断s[i+1 : ]是否存在回文串。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        backtrack(result, new LinkedList<>(), s, 0);
        return result;
    }


    private void backtrack(List<List<String>> result, List<String> temp, String s, int index) {
        if (index == s.length()) {
            result.add(new LinkedList<>(temp));
            return;
        }


        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                temp.add(s.substring(index, i + 1));
                backtrack(result, temp, s, i + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }


    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }


        return true;
    }
}

132. Palindrome Partitioning II#

https://leetcode.com/problems/palindrome-partitioning-ii/

使用动态规划，其中dp[i]表示s[:i]的范围内共需要多少次分割才能满足题意。

观察发现，如果s[left:right]是回文串，那么可以考虑将s[left:right]这个字符串分割出来，截止到下标right时，dp[right]的组成就是s[:left - 1]之内的分割数量，再加上s[left:right]这一次分割。

当然，随着left和right的不断外扩，也许我们能找到更长的回文串，这样也可能使得总的分割次数越来越少。

class Solution {
    public int minCut(String s) {
        char[] arr = s.toCharArray();


        int len = s.length();
        int[] dp = new int[len + 1];
        Arrays.fill(dp, len - 1);
        dp[0] = 0;


        // odd or even length
        for (int i = 1; i < len; i++) {
            updatePalindromeCut(arr, i, i, dp, len);
            updatePalindromeCut(arr, i - 1, i, dp, len);
        }


        return dp[len - 1];
    }


    void updatePalindromeCut(char[] str, int left, int right, int[] dp, int len) {
        while (left >= 0 && right < len && str[left] == str[right]) {


            dp[right] = left > 0 ? Math.min(dp[right], dp[left - 1] + 1)
                                 : Math.min(dp[right], 0);


            left--;
            right++;
        }
    }
}

133. Clone Graph#

https://leetcode.com/problems/clone-graph/

使用一个map，存储新旧节点之间的映射，遇到已经复制过的节点，直接从map中获取；复制一个节点时，新节点newNode直接用原来的值node.val初始化，而newNode的邻居则用深度优先思想，循环从node.neighbors里分别调用cloneGraph方法复制。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/


class Solution {
    // map from old to new nodes
    private Map<Node, Node> map = new HashMap<Node, Node>();


    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }


        // current node has been cloned
        if (map.containsKey(node)) {
            return map.get(node);
        }


        Node newNode = new Node(node.val, new ArrayList<Node>());
        map.put(node, newNode);


        for (int i = 0; i < node.neighbors.size(); i++) {
            Node clonedNeighbor = cloneGraph(node.neighbors.get(i));
            newNode.neighbors.add(clonedNeighbor);
        }


        return newNode;
    }
}

134. Gas Station#

https://leetcode.com/problems/gas-station/

使用一个变量tankGas跟踪当前油箱中的油量。如果从第i个加油站开到第i+1个加油站的路上油箱里的油量变成负数，说明油不够用，只能换一个起点。

再使用一个变量totalGas计算整趟旅程下来加油 - 耗油的差值，总的耗油不能比加油量多。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // total gas filled - total gas cost
        int totalGasDiff = 0;


        // current gas in the tank
        int tankGas = 0;


        // starting gas station's index
        int start = 0;


        for (int i = 0; i < cost.length; i++) {
            // gas consumption amount from i-th station to (i+1)-th station
            int cur = gas[i] - cost[i];


            // update total consumed gas
            totalGasDiff += cur;


            // update gas in the tank
            // if tank drops below 0, we have to start from another station
            tankGas += cur;
            if (tankGas < 0) {
                start = i + 1;
                tankGas = 0;
            }
        }


        return totalGasDiff < 0 ? -1 : start;
    }
}

135. Candy#

https://leetcode.com/problems/candy/

解题流程分为三步：

  1. 初始分配给每个孩子一个糖
  2. 从左向右，确保位于右侧，rating更高的孩子比左侧孩子获得更多的糖
  3. 从右向左，确保位于左侧，rating更高的孩子比右侧孩子获得更多的糖。注意有可能在此前从左到右的分配中，num[i - 1]的值很大，因此我们需要比较num[i - 1]和 num[i] + 1的值，选更大的那个值，确保不违背之前的分发方式。

最后只需要将结果累加即可。

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if (len == 0) {
            return 0;
        }


        int result = 0;


        int[] num = new int[len + 1];
        Arrays.fill(num, 1);


        // left to right, make sure that right child with higher rating receive more candy
        for (int i = 0; i < len - 1; i++) {
            if (ratings[i] < ratings[i + 1]) {
                num[i+1] = num[i] + 1;
            }
        }


        // right to left, make sure that left child with higher rating receive more candy
        // we cannot break the previous left-to-right rule as well
        for (int i = len - 1; i > 0; i--) {
            if (ratings[i - 1] > ratings[i]) {
                num[i - 1] = Math.max(num[i - 1], num[i] + 1);
            }
            result += num[i];
        }


        result += num[0];
        return result;
    }
}

136. Single Number#

https://leetcode.com/problems/single-number/

任意两个相同的数，异或值为0。遍历整个数组并不断取异或，只有single number自身无法通过成对异或得到0，因此最后的结果就是single number。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

137. Single Number II#

https://leetcode.com/problems/single-number-ii/

解决本题有2个前提：

  • 遇到num两次时，不应该记录这个数
  • 遇到num三次后，将num对结果的影响清除

结合上述前提以及上一题的解决方案，只需要在第一次和第三次遇到一个数时进行记录即可；并且，如果ones ^ num == 0，表示当前遇到了num。

由此我们拆分出两个核心步骤：

  1. 如果没有将num记录在ones中，更新ones；否则不记录

    ones = ones ^ num & ~twos

  2. 如果没有将num记录在twos中，更新twos；否则将twos清零

    twos = twos ^ num & ~ones
class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}

138. Copy List with Random Pointer#

https://leetcode.com/problems/copy-list-with-random-pointer/

与此前的Clone Graph问题类似，仍然是一张map，记录当前复制的进度，遇到已经复制过的节点直接从map中获取结果；并且仍然是使用递归，优先完成后续节点的复制。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;


    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/


class Solution {
    // map from old to new nodes
    private Map<Node, Node> map = new HashMap<Node, Node>();


    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }


        // current node has been cloned
        if (map.containsKey(head)) {
            return map.get(head);
        }


        // copy node
        Node newHead = new Node(0);
        newHead.val = head.val;
        map.put(head, newHead);


        newHead.next = copyRandomList(head.next);
        newHead.random = copyRandomList(head.random);


        return newHead;
    }
}

139. Word Break#

https://leetcode.com/problems/word-break/

使用动态规划，dp[i]表示截止至第i个字符时，s的子字符串s[0:i]是否符合题意。

使用两层遍历，从第i-1个字母开始向前搜索，如果遇到子字符串s[j:i-1]在wordDict中，并且起始下标j处有dp[j]为true，则将dp[i]标记为true。可以限定向前搜索的长度（wordDict中最长单词的长度）来加快运行时间。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);


        // maximum word length in wordDict
        int maxWordLen = 0;
        for (String each : dict) {
            maxWordLen = Math.max(maxWordLen, each.length());
        }


        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;


        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= Math.max(0, i - maxWordLen); j--) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }


        return dp[s.length()];
    }
}

140. Word Break II#

https://leetcode.com/problems/word-break-ii/

使用回溯算法，尝试每一个s[index:i]能不能组成一个存在于wordDict中的单词。

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        backtrack(result, s, wordDict, 0, new ArrayList<>());
        return result;
    }


    private void backtrack(List<String> result, String s, List<String> wordDict, int index, List<String> temp) {
        if (index == s.length()) {
            result.add(String.join(" ", temp));
            return;
        }


        // try each s[index:i]
        for (int i = index; i <= s.length(); i++) {
            if (wordDict.contains(s.substring(index, i))) {
                temp.add(s.substring(index, i));


                // start index should be i now
                backtrack(result, s, wordDict, i, temp);


                temp.remove(temp.size() - 1);
            }
        }
    }
}


// Time: O(2^n * n)
// Space: O(n)

141. Linked List Cycle#

https://leetcode.com/problems/linked-list-cycle/

使用快慢指针，慢指针一次移动一格，快指针一次移动两格。如果存在环，快慢指针将在某个时刻相遇。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head, fast = head;


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


            // fast and slow pointers will eventually meet if there is a cycle
            if (slow == fast) {
                return true;
            }
        }


        return false;
    }
}

142. Linked List Cycle II#

https://leetcode.com/problems/linked-list-cycle-ii/

实际上这是一个数学问题。仍然使用上一题中的快慢指针方法。假设链表头距离环起始点的距离为A，环起始点距离快慢指针相遇点的距离为B，环的长度为N，则：

A + B + N = 2A + 2B (快指针比慢指针多走了一个环的距离)

可以解得：

N - B = A

即快慢指针相遇点距离链表终点的距离也为A，因此慢指针只需要再移动A+1距离，便能够回到环的起点。使用另一个指针slow2从头开始，与慢指针共同位移，二者相遇的位置就是环起点。

/**
 * 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) {
            return null;
        }


        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;


            if (slow == fast) {
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }


        return null;
    }
}

143. Reorder List#

https://leetcode.com/problems/reorder-list/

解题步骤分为三步：

  1. 寻找链表的中间元素，将链表分为两部分
  2. 颠倒后半部分的链表
  3. 调整指针顺序，将两部分链表交错相连。
/**
 * 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 void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }


        // find middle element
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }


        // reverse the second half of the list
        ListNode preMiddle = slow;
        ListNode preCurrent = slow.next;
        while (preCurrent.next != null) {
            ListNode current = preCurrent.next;
            preCurrent.next = current.next;
            current.next = preMiddle.next;
            preMiddle.next = current;
        }


        // merge two sub-lists
        slow = head;
        fast = preMiddle.next;
        while (slow != preMiddle) {
            preMiddle.next = fast.next;
            fast.next = slow.next;
            slow.next = fast;
            slow = fast.next;
            fast = preMiddle.next;
        }
    }
}

144. Binary Tree Preorder Traversal#

https://leetcode.com/problems/binary-tree-preorder-traversal/

第一种做法，迭代使用栈解决问题。注意由于栈先进后出，因此要先加入每个节点的右分支。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }


        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            result.add(node.val);


            if (node.right != null) {
                st.push(node.right);
            }
            if (node.left != null) {
                st.push(node.left);
            }
        }


        return result;
    }
}

第二种做法，递归遍历：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorder(result, root);
        return result;
    }


    private void preorder(List<Integer> result, TreeNode node) {
        if (node == null) {
            return;
        }


        result.add(node.val);
        preorder(result, node.left);
        preorder(result, node.right);
    }
}

145. Binary Tree Postorder Traversal#

https://leetcode.com/problems/binary-tree-postorder-traversal/

第一种做法，仍然使用栈，调整st和result添加的顺序即可：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }


        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            result.add(0, node.val);


            if (node.left != null) {
                st.push(node.left);
            }


            if (node.right != null) {
                st.push(node.right);
            }
        }


        return result;
    }
}

第二种做法，递归遍历：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        postorder(result, root);
        return result;
    }


    private void postorder(List<Integer> result, TreeNode node) {
        if (node == null) {
            return;
        }


        postorder(result, node.left);
        postorder(result, node.right);
        result.add(node.val);
    }
}

146. LRU Cache#

https://leetcode.com/problems/lru-cache/

第一种是简便做法。LRU缓存是LinkedHashMap的一种应用。对一个键执行get/put操作后，对应的键值对会移动到链表末尾，因此最末尾的元素是最近访问的。在LinkedHashMap添加元素后，会调用removeEldestEntry()方法，传递的参数为最久没有被访问的键值对时，如果方法返回true，这个最久的键值对就会被删除。因此，LRUCache类只需在LinkedHashMap类的基础上进行继承扩展即可。

class LRUCache extends LinkedHashMap<Integer, Integer>{


    private int capacity;


    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }


    public int get(int key) {
        return super.getOrDefault(key, -1);
    }


    public void put(int key, int value) {
        super.put(key, value);
    }


    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

第二种做法，使用一个链表和一个数组。数组记录所有出现过的key与value对应的信息；而链表则负责维护最近使用过的节点情况，如果某个节点最近被使用过，就把它先从链表中删掉，再把它加到链表的尾部。这样能确保链表始终是按照最近使用时间由远到近进行排序，如果要替换节点直接从链表头选择节点替换即可。

class Node {
    Node next, prev;
    int key, val;
    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}


class LRUCache {
    Node map[];
    Node head, tail;
    int CAP, SIZE;


    public LRUCache(int capacity) {
        CAP = capacity;
        SIZE = 0;
        map = new Node[10001]; // default max capacity is 10000
        head = tail = null;
    }


    private void add(Node n) {
        // first node, set it as both head and tail
        if (head == null) {
            head = tail = n;
            return;
        }


        // add to tail
        tail.next = n;
        n.prev = tail;
        tail = n;
    }


    private void remove(Node n) {
        if (head == tail) {
            // remove the only node
            head = tail = null;
        } else if (head == n) {
            // remove head node
            head = head.next;
        } else if (tail == n) {
            // remove tail node
            tail = tail.prev;
        } else {
            // find previous and next nodes, then connect them
            Node prev = n.prev, next = n.next;
            prev.next = next;
            next.prev = prev;
        }
    }


    public int get(int key) {
        if (map[key] == null) {
            return -1;
        }


        // recently used, update it's position in linked list
        remove(map[key]);
        add(map[key]);


        return map[key].val;
    }


    public void put(int key, int value) {
        // update the value of the key, if the key exists
        if (map[key] != null) {
            remove(map[key]);
            add(map[key]);
            map[key].val = value;
            return;
        }


        // need to evict a node and replace with current key
        if (SIZE >= CAP) {
            Node nodeToRemove = head;
            remove(nodeToRemove);
            map[nodeToRemove.key] = null;
            SIZE--;
        }


        Node newNode = new Node(key, value);
        add(newNode);
        map[key] = newNode;
        SIZE++;
    }
}

147. Insertion Sort List#

https://leetcode.com/problems/insertion-sort-list/

使用三个指针，其中pre总是从链表头开始向后移动，寻找插入位置；cur指向当前待插入的元素；next指向下一个待插入的元素。

/**
 * 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 insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }


        ListNode dummyHead = new ListNode(0);


        // current node to be inserted
        ListNode cur = head;


        // pre -> cur -> next
        ListNode pre = dummyHead, next = null;


        while (cur != null) {
            next = cur.next;


            // find the first element which breaks the ascending order
            // this is the insertion position
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }


            cur.next = pre.next;
            pre.next = cur;
            cur = next;


            // reset pre
            pre = dummyHead;
        }


        return dummyHead.next;
    }
}

148. Sort List#

https://leetcode.com/problems/sort-list/

Divide and conquer，不断将链表二分为左、右两部分，按顺序合并两个子链表，组成一个完整的有序链表。

/**
 * 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) {
        if (head == null || head.next == null) {
            return head;
        }


        // divide the list into two half
        ListNode pre = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;


        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);


        return mergeTwoLists(l1, l2);
    }


    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }


        // merge after smaller node
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

149. Max Points on a Line#

https://leetcode.com/problems/max-points-on-a-line/

三重循环，如果两点重合，则寻找所有的重合点；否则，计算出两点连线的斜率，并遍历其他点，寻找与当前点连线斜率相同的点。每一轮循环结束后的结果是斜率相同 + 相同点的总个数。注意，如果全部点都相同，还需要在结尾进行额外判断，决定samepoint值是否需要 + 1。

class Solution {
    public int maxPoints(int[][] points) {
        if (points == null) {
            return 0;
        }
        if (points.length < 3) {
            return points.length;
        }


        int result = 0;
        int n = points.length;


        for (int i = 0; i < n; i++) {
            int samepoint = 0;


            for (int j = i+1; j < n; j++) {
                int count = 2;
                long x = points[j][0] - points[i][0];
                long y = points[j][1] - points[i][1];


                boolean isValidSlope = true;
                if (x == 0 && y == 0) {
                    samepoint++;
                    continue;
                }


                if (x == 0) {
                    isValidSlope = false;
                }


                long interdx = x * points[i][1] - y * points[i][0];


                // slope exists and equal inter multiplication, or slope not exist and same point
                for (int k = j+1; k < n; k++) {
                    if (isValidSlope) {
                        if (interdx == x*points[k][1] - y*points[k][0]) {
                            count++;
                        }
                    } else if (points[k][0] == points[i][0]) {
                        count++;
                    }
                }


                result = Math.max(count + samepoint, result);
            }


            result = Math.max(samepoint + 1, result); // [[1,1],[1,1],[1,1]]
        }


        return result;
    }
}

150. Evaluate Reverse Polish Notation#

https://leetcode.com/problems/evaluate-reverse-polish-notation/

逆波兰式实际对应的就是树的后序遍历，根据后续遍历的顺序，我们会先遇到操作数a，再遇到操作数b，之后才是操作符。因此当我们遇到操作数的时候，直接推入栈中；遇到操作符时，从栈顶推出的操作数是先b再a，这个顺序在减法和除法中很重要。

class Solution {
    public int evalRPN(String[] tokens) {
        int a, b;
        Stack<Integer> st = new Stack<Integer>();


        for (String s : tokens) {
            if (s.equals("+")) {
                st.add(st.pop() + st.pop());
            } else if (s.equals("-")) {
                b = st.pop();
                a = st.pop();
                st.add(a - b);
            } else if (s.equals("*")) {
                st.add(st.pop() * st.pop());
            } else if (s.equals("/")) {
                b = st.pop();
                a = st.pop();
                st.add(a / b);
            } else {
                st.add(Integer.parseInt(s));
            }
        }


        return st.pop();
    }
}

151. Reverse Words in a String#

https://leetcode.com/problems/reverse-words-in-a-string/

使用trim()函数除去起始的空白，再使用split()函数分割每个单词，汇集成一个单词数组。之后倒序输出所有单词，并添加空格。

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();


        // trim preceding & leading whitespaces, then split by " "
        String[] words = s.trim().split(" ");


        for (int i = words.length - 1; i >= 0; i--) {
            if (words[i].length() > 0) {
                sb.append(words[i]);
                if (i > 0) {
                    sb.append(" ");
                }
            }
        }


        return sb.toString();
    }
}

152. Maximum Product Subarray#

https://leetcode.com/problems/maximum-product-subarray/

从左向右遍历一遍，不断累乘，如果当前乘积为0需要重新修改为1。

考虑到存在负数的情况（例如[3, -1, 4])，可能会导致数组被负数分割成若干部分，因此从左到右不一定能找到最大子区间。因此我们还需要从右向左再遍历一次，确保筛选出最大子序列。

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }


        int result = Integer.MIN_VALUE, product = 1;
        for (int i = 0; i < nums.length; i++) {
            product *= nums[i];
            result = Math.max(result, product);
            if (product == 0) {
                product = 1;
            }
        }


        product = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            product *= nums[i];


            result = Math.max(result, product);
            if (product == 0) {
                product = 1;
            }
        }


        return result;
    }
}

153. Find Minimum in Rotated Sorted Array#

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

这题借鉴了此前Search in Rotated Sorted Array的数组对半划分思想，通过比较nums[left]、nums[mid]和nums[right]确定下一轮的搜索区间。

如果nums[mid]不小于边界两个值，说明nums[left, mid]是一段递增序列，最小值在nums[mid + 1, right]中；反之，最小值在nums[left, mid]中。因为我们希望找到数组最小值，根据左边界查找思想，在确定最小值所在范围后我们仍然希望尽量向左扩展范围，试图能在范围中找到更小的值符合要求。

注意这题还可以用辅助加速的手段快速检查nums[mid]值是否为最小值，提升运行效率。

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }


        if (nums.length == 1) {
            return nums[0];
        }


        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;


            // optional speed-up, quickly determine if nums[mid] is minimum
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }


            if (nums[left] <= nums[mid] && nums[right] < nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }


        return nums[left];
    }
}

154. Find Minimum in Rotated Sorted Array II#

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

最小值初始情况下在肯定在nums[0, nums.length - 1]之间。分类讨论：

  • 如果nums[mid] > nums[right]，最小值在nums[mid + 1, right]之间，因此有left = mid + 1
  • 如果nums[mid] < nums[left]，最小值在nums[left + 1, mid]之间，因此有right = mid；同时我们也知道nums[left]不可能是最小值，因此让left++稍微加快一些运行效率
  • 其他情况下，对应nums[left] <= nums[mid] <= nums[right]，我们只知道最小值为nums[left]，不知道nums[mid]和两端的关系，因此只能让right--

完成二分查找循环后，left与right相等，返回nums[left]即可。

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }


        if (nums.length == 1) {
            return nums[0];
        }


        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;


            if (nums[right] < nums[mid]) {
                left = mid + 1;
            } else if (nums[mid] < nums[left]) {
                right = mid;
                left++;
            } else {
                right--;
            }
        }


        return nums[left];
    }
}

155. Min Stack#

https://leetcode.com/problems/min-stack/

主体可以构造一个链表存储。对于最小值的跟踪，可以在push时顺便完成，直接和当前头元素中存储的已有最小值比较，节省搜索的时间。

class MinStack {


    private class Node {
        int val;
        int min;
        Node next;


        private Node(int val, int min) {
            this(val, min, null);
        }


        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }


    private Node head;


    /** initialize your data structure here. */
    public MinStack() {


    }


    public void push(int x) {
        if (head == null) {
            head = new Node(x, x);
        } else {
            // store global min value into each incoming node
            head = new Node(x, Math.min(x, head.min), head);
        }
    }


    public void pop() {
        head = head.next;
    }


    public int top() {
        return head.val;
    }


    public int getMin() {
        return head.min;
    }
}

156. Binary Tree Upside Down#

https://leetcode.com/problems/binary-tree-upside-down/

可以将最左支(1-2-4)视为树的骨干，其余节点视为枝叶。参考XYZ例图，旋转后骨干变成最右支，枝叶则位于左侧。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }


        TreeNode newRoot = upsideDownBinaryTree(root.left);


        // Y -> Z
        root.left.left = root.right;


        // Y -> X
        root.left.right = root;


        // root has become a leaf now
        root.left = root.right = null;


        return newRoot;
    }
}

157. Read N Characters Given Read4#

https://leetcode.com/problems/read-n-characters-given-read4/

问题限制只能使用read4()函数来实现read()函数。read4()函数限制了一次性读入的字符最多为4，因此read()函数必须不断调用read4()，将字符从read4()专用的缓存read4TempBuff中拷贝到自己的缓存buf内。

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4);
 */


public class Solution extends Reader4 {


    // the buffer for read4 API
    private char[] read4TempBuff = new char[4];


    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int read(char[] buf, int n) {


        // how many characters have been read
        int result = 0;


        // read 4 characters to buff
        int bytes = read4(read4TempBuff);


        while (bytes > 0) {
            for (int i = 0; i < bytes; i++) {
                if (n == result) {
                    break;
                }


                // copy 1 char
                buf[result] = read4TempBuff[i];
                result++;
            }
            bytes = read4(read4TempBuff);
        }


        return result;
    }
}

158. Read N Characters Given read4 II - Call Multiple Times#

https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/

由于read()可能被调用多次，因此需要及时更新缓存指针，每次read4()读字符进来，就将字符逐个从read4TempBuff拷贝到buf，复制完一个就移动一次缓存指针。4个都复制完了，重置缓存指针到0，只有为0的时候才可以接受下一批读入的字符。

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4);
 */


public class Solution extends Reader4 {


    private int buffPtr = 0;
    private int bytes = 0; // characters length read to buffer


    private char[] read4TempBuff = new char[4];


    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int read(char[] buf, int n) {


        // how many characters have been read
        int result = 0;


        while (result < n) {
            // write buff when buffer is ready
            if (buffPtr == 0) {
                bytes = read4(read4TempBuff);
            }


            // copy chars from read4TempBuff to buf
            while (result < n && buffPtr < bytes) {
                buf[result] = read4TempBuff[buffPtr];
                result++;
                buffPtr++;
            }


            // finish copying current 4 chars, reset to 0, ready to receive new chars
            if (buffPtr == bytes) {
                buffPtr = 0;
            }


            // read4() return a number less than 4, EOF
            if (bytes < 4) {
                break;
            }
        }


        return result;
    }
}

159. Longest Substring with At Most Two Distinct Characters#

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

滑动窗口思想，使用一个map存储每个字符出现的次数；使用双指针i, j记录当前遍历输入字符串的前、后字符，确保map中不超过2个字符。一旦超过，就需要从前指针开始剔除一个老字符。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }


        char[] arr = s.toCharArray();


        // <Character, Integer>
        int[] map = new int[256];


        // how many distinct characters in current substring
        int count = 0;


        // longest substring length
        int result = 0;


        for (int i = 0, j = 0; j < arr.length; j++) {
            // a new character
            if (map[ arr[j] ] == 0) {
                count++;
            }


            map[ arr[j] ]++;


            // more than 2 characters in current substring, delete one character
            while (count > 2) {
                map[ arr[i] ]--;


                // delete one
                if (map[ arr[i] ] == 0) {
                    count--;
                }


                i++;
            }


            result = Math.max(result, j - i + 1);
        }


        return result;
    }
}

160. Intersection of Two Linked Lists#

https://leetcode.com/problems/intersection-of-two-linked-lists/

无需计算A、B链表的长度，直接分别从头到尾进行遍历，如果遇到结尾，跳转至另一链表的头部继续遍历。这样一来，如果两个链表有交集，遍历指针一定会在交集点相遇；否则，同时移动至链表结尾，返回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) {
        if (headA == null || headB == null) {
            return null;
        }


        ListNode curA = headA, curB = headB;
        while (curA != curB) {
            curA = (curA == null) ? headB : curA.next;
            curB = (curB == null) ? headA : curB.next;
        }


        return curA;
    }
}

161. One Edit Distance#

https://leetcode.com/problems/one-edit-distance/

要想在一次编辑内实现s, t两个字符串的相等，必须只有一个字符在下标i处不同，并且

  • 如果s, t等长，下标i之后s, t仍旧要相等
  • s比t短，则t删掉t[i]之后剩余字符串和s从s[i]起的字符串相等
  • t比s短，与上一种情况对应

最后还有一种特殊情况，即最后一个字符才出现不同，需要判断两个字符串的长度差值是否为1。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.length() == t.length()) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } else if (s.length() < t.length()) {
                    return s.substring(i).equals(t.substring(i + 1));
                } else {
                    return s.substring(i + 1).equals(t.substring(i));
                }
            }
        }


        return Math.abs(s.length() - t.length()) == 1;
    }
}

162. Find Peak Element#

https://leetcode.com/problems/find-peak-element/

使用二分查找，找到任意一个极大值便返回。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;


            // find a local maximum
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }


        return left;
    }
}

163. Missing Ranges#

https://leetcode.com/problems/missing-ranges/

三步检查：

  1. 判断lower和nums的第一个数之间的关系
  2. 判断每两个数之间是否产生了大于1的间隔（生成缺失区间）
  3. 判断upper和nums的最后一个数之间的关系
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<>();


        if (nums == null || nums.length == 0) {
            result.add(formRange(lower, upper)); // generate the whole range
            return result;
        }


        // initial gap
        if (nums[0] > lower) {
            result.add(formRange(lower,nums[0] - 1));
        }


        // find a gap greeater than 1
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i+1] != nums[i] && nums[i+1] > nums[i] + 1) {
                result.add(formRange(nums[i] + 1, nums[i+1] - 1));
            }
        }


        // last gap
        if (nums[nums.length-1] < upper) {
            result.add(formRange(nums[nums.length-1] + 1, upper));
        }


        return result;
    }


    public String formRange(int low, int high) {
        return low == high ? String.valueOf(low) : (low + "->" + high);
    }
}

164. Maximum Gap#

https://leetcode.com/problems/maximum-gap/

先遍历一次数组，得出数组的最小值min和最大值max；将数组划分为若干个桶，每个桶覆盖一段区间[min + (k-1)gap, min + k*gap)。对于每个桶，重点记录桶内的最小值和最大值，最后比较不同桶之间最值之间的间距。

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }


        // find minimum and maximum value of nums
        int min = nums[0], max = nums[0];
        for (int n: nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }


        if (min == max) {
            return 0;
        }


        int n = nums.length;


        // each bucket is an interval，[min + (k-1)gap, min + k*gap)
        int gap = (int)Math.ceil((double)(max - min) / (n - 1)); // max gap must be greater than this
        int bucketMin[] = new int[n];
        int bucketMax[] = new int[n];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);


        // put current number in the bucket and update this bucket's min/max value
        for (int num: nums) {
            int i = (num - min) / gap;
            bucketMin[i] = Math.min(bucketMin[i], num);
            bucketMax[i] = Math.max(bucketMax[i], num);
        }


        // for the first bucket, compare bucket's min value and num's min value
        // for other buckets, compare this bucket's min value and previous bucket's max value
        for (int i = 0; i < n; i++) {
            // only compare when the bucket is not empty
            if (bucketMin[i] != Integer.MAX_VALUE) {
                gap = Math.max(gap, bucketMin[i] - min);
                min = bucketMax[i];
            }
        }


        return gap;
    }
}

165. Compare Version Numbers#

https://leetcode.com/problems/compare-version-numbers/

使用split()函数，根据'.'提取出每个子版本号进行比较。可以调用parseInt()函数转化格式。比较过程中，如果较短的版本号已经遍历完毕，之后的子版本号可以看作都是0。

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");


        for (int i = 0; i < Math.max(s1.length, s2.length); i++) {
            // if version number too long, treat as 0
            Integer v1 = i < s1.length ? Integer.parseInt(s1[i]) : 0;
            Integer v2 = i < s2.length ? Integer.parseInt(s2[i]) : 0;


            if (v1 > v2) {
                return 1;
            } else if (v1 < v2) {
                return -1;
            }
        }


        return 0;
    }
}

166. Fraction to Recurring Decimal#

https://leetcode.com/problems/fraction-to-recurring-decimal/

解题步骤可划分为：

  1. 确定正负号
  2. 将int型输入变量转化为long型，避免溢出
  3. 小数部分，不断倍增numerator,每循环做一次除法，便用map存储当前的余数以及长度。如果当前余数已经在map中，则终止循环
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }


        StringBuffer sb = new StringBuffer();


        // determine sign
        if ((numerator > 0) ^ (denominator > 0)) {
            sb.append('-');
        }


        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);


        sb.append(num / den);
        num %= den;
        if (num == 0) {
            return sb.toString();
        }
        sb.append('.');


        // <recurring decimal, recurring string length>
        HashMap<Long, Integer> map = new HashMap<>();
        while (num != 0) {
            num *= 10;


            // detect recurring part
            if (map.containsKey(num)) {
                sb.insert((int) map.get(num), '(');
                sb.append(')');
                return sb.toString();
            }


            map.put(num, sb.length());
            sb.append(num / den);
            num %= den;
        }


        return sb.toString();
    }
}

167. Two Sum II - Input Array Is Sorted#

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

左右双指针法，遍历解决。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;


        int[] result = new int[2];
        if (numbers == null || numbers.length < 2) {
            return result;
        }


        int index1 = 0, index2 = len-1;
        while (index1 < index2) {
            if (numbers[index1] + numbers[index2] == target) {
                result[0] = index1 + 1;
                result[1] = index2 + 1;
                return result;
            } else if (numbers[index1] + numbers[index2] < target) {
                index1++;
            } else {
                index2--;
            }
        }


        return result;
    }
}

168. Excel Sheet Column Title#

https://leetcode.com/problems/excel-sheet-column-title/

相当于10进制转特殊的26进制，按位倒序添加每一位数。

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder result = new StringBuilder();


        while (columnNumber > 0) {
            columnNumber--;
            result.insert(0, (char)('A' + columnNumber % 26));
            columnNumber /= 26;
        }


        return result.toString();
    }
}

169. Majority Element#

https://leetcode.com/problems/majority-element/

运用Boyer-Moore投票算法，遍历整个数组，判断当前数nums[i]是否和当前的candidate相等，进而加减投票。由于输入数据中一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素，即majority element。

class Solution {
    public int majorityElement(int[] nums) {
        // current candicate and its occurrence
        int count = 0, candidate = Integer.MIN_VALUE;


        for (int i = 0; i < nums.length; i++) {
            // set as current new candidate
            if (count == 0) {
                candidate = nums[i];
            }


            // "vote" for current candidate, or "vote" for others
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }


        return candidate;
    }
}

170. Two Sum III - Data structure design#

https://leetcode.com/problems/two-sum-iii-data-structure-design/

用ArrayList存储每个添加的数字；使用HashMap存储每个数字出现的次数。每次添加一个数字后，就立即更新当前list内的最小值和最大值，这样能在find()时提前判定不合理范围，节省时间。

class TwoSum {


    // all numbers
    private List<Integer> list = new ArrayList<>();


    // every number's occurrence
    private Map<Integer, Integer> map = new HashMap<>();


    // record max and minimum value
    int max, min;


    /** Initialize your data structure here. */
    public TwoSum() {}


    /** Add the number to an internal data structure.. */
    public void add(int number) {
        list.add(number);


        min = Math.min(number, min);
        max = Math.max(number, max);


        map.put(number, map.getOrDefault(number, 0) + 1);
    }


    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        if (value < 2 * min || value > 2 * max) {
            return false;
        }


        for (int num : list) {
            int num2 = value - num;


            if ((num == num2 && map.getOrDefault(num, 0) > 1) ||
                (num != num2 && map.containsKey(num2))) {
                return true;
            }
        }


        return false;
    }
}

171. Excel Sheet Column Number#

https://leetcode.com/problems/excel-sheet-column-number/

遍历每个字符，进行26进制 -> 10进制的转换。

class Solution {
    public int titleToNumber(String s) {
        if (s.length() < 1) {
            return 0;
        }


        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            result = result * 26 + (s.charAt(i) - 'A' + 1);
        }


        return result;
    }
}

172. Factorial Trailing Zeroes#

https://leetcode.com/problems/factorial-trailing-zeroes/

阶乘中的10，本质上来源于5这个因子(5*2)。考虑到每个偶数都能提供一个2作为因子，因此2因子的数量一定比5因子多，尾数0的个数只取决于5的个数。

class Solution {
    public int trailingZeroes(int n) {
        int result = 0;


        while (n > 0) {
            result += n / 5;
            n /= 5;
        }


        return result;
    }
}

173. Binary Search Tree Iterator#

https://leetcode.com/problems/binary-search-tree-iterator/

根据BST的特点，观察如果按照中序遍历从左到右遍历整颗BST，将得到一个有序的list。每次调用next()函数获取当前树中最小值时，其实就是获取list当前的头元素。不断使用poll()函数清空list，最终list为空时，hasNext()便返回false。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {


    LinkedList<Integer> tree = new LinkedList<>();


    public BSTIterator(TreeNode root) {
        visit(root);
    }


    void visit(TreeNode root) {
        if (root == null) {
            return;
        }


        // in-order
        visit(root.left);
        tree.offer(root.val);
        visit(root.right);
    }


    /** @return the next smallest number */
    public int next() {
        return tree.poll();
    }


    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !tree.isEmpty();
    }
}

174. Dungeon Game#

https://leetcode.com/problems/dungeon-game/

动态规划，从终点向起点递推。如果当前房间可以加血，并且回复的血量比相邻房间所消耗的最低血量还多，说明只需要1滴血就能进入当前的回血房间，并且继续进入下一个房间；否则，所需的最小血量就要加上当前房间所扣除的血量。

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];




        // unreachable bound
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[m][i] = Integer.MAX_VALUE;
        }


        // before finally enter the bottom-right room, the knight should have at least 1 health
        dp[m][n-1] = 1;
        dp[m-1][n] = 1;


        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int minToNext = Math.min(dp[i][j+1], dp[i+1][j]);
                dp[i][j] = (dungeon[i][j] >= minToNext) ? 1 : minToNext - dungeon[i][j];
            }
        }


        return dp[0][0];
    }
}

175. Combine Two Tables#

https://leetcode.com/problems/combine-two-tables/

两个表的PersonId字段可以充当桥梁。另外注意到即使Address表缺乏记录，也要返回Person表中的对应人物数据，因此需要用到LEFT JOIN。

SELECT FirstName, LastName, City, State
FROM Person LEFT JOIN Address
ON Person.PersonId = Address.PersonId;

176. Second Highest Salary#

https://leetcode.com/problems/second-highest-salary/

从高到低排序后，获取第二大的结果。

SELECT
    (SELECT DISTINCT Salary
     FROM Employee
     ORDER BY Salary DESC
     LIMIT 1 /* LIMIT: number of rows returned */
     OFFSET 1 /* OFFSET：starting row index */
    )
AS SecondHighestSalary

177. Nth Highest Salary#

https://leetcode.com/problems/nth-highest-salary/

与上一题类似，仍然是从高到低排序，只不过OFFSET变成了N - 1。

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    DECLARE M INT;
    SET M = N - 1;
  RETURN (
      SELECT DISTINCT Salary
      FROM Employee
      ORDER BY Salary DESC
      LIMIT 1
      OFFSET M
  );
END

178. Rank Scores#

https://leetcode.com/problems/rank-scores/

第一种方法，对于当前分数，不断计算出大于等于当前分数的数量，这个数量对应排名。

SELECT Score,
  (SELECT COUNT(*)
    FROM (SELECT DISTINCT Score s FROM Scores) AS tmp /* greater or equal to current score */
    WHERE s >= Score) AS 'Rank'
FROM Scores
ORDER BY Score DESC

第二种方法，可以直接使用DENSE_RANK()函数。

SELECT Score, DENSE_RANK() OVER (ORDER BY Score DESC) AS 'Rank'
FROM Scores

179. Largest Number#

https://leetcode.com/problems/largest-number/

重定义Arrays.sort()的Comparator。如果Comparator调用的compare(obj param1, obj param2)函数返回结果大于0，说明排序时param1位于param2之后，达到升序的效果；等于0和小于0的情况以此类推。

为了排除字典序首字符的干扰，需要将两个待比较字符串参数s1，s2合并，即比较s1+s2和s2+s1。如果s2+s1“大于”s1+s2，排序的结果中s2将前于s1。

class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }


        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }


        // sort from the largest num to the smallest
        Arrays.sort(strs, (String s1, String s2) -> {
            return (s2 + s1).compareTo(s1 + s2);
        });


        // starting digit is 0, then it must be 0
        if (strs[0].charAt(0) == '0') {
            return "0";
        }


        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }


        return sb.toString();
    }
}

180. Consecutive Numbers#

https://leetcode.com/problems/consecutive-numbers/

自连接三遍，比较三张表是否有连续的三个ID对应的数字相等。

SELECT DISTINCT l1.Num AS ConsecutiveNums
FROM Logs l1, Logs l2, Logs l3
WHERE l1.Id = l2.Id - 1 AND l2.Id = l3.Id - 1 AND l1.Num = l2.Num AND l2.Num = l3.Num

181. Employees Earning More Than Their Managers#

https://leetcode.com/problems/employees-earning-more-than-their-managers/

进行一次左连接，左表是Employee表自身，右表选出Id和Salary即可。左表的managerId需要和右表的id相等，并且左表的工资比右表高。

SELECT E1.Name AS Employee
FROM Employee E1 LEFT JOIN (
    SELECT Id, Salary
    FROM Employee
    GROUP BY Id
) E2
ON E1.ManagerId = E2.Id
WHERE E1.Salary > E2.Salary;

182. Duplicate Emails#

https://leetcode.com/problems/duplicate-emails/

使用COUNT()函数，找出出现次数不止1次的邮箱。注意需要先GROUP BY Email，才能统计次数。

SELECT Email
FROM Person
GROUP BY Email
HAVING COUNT(*) > 1

183. Customers Who Never Order#

https://leetcode.com/problems/customers-who-never-order/

从Customers表中选出符合条件的顾客，这些顾客的ID没有出现在Orders表中。

SELECT Name AS Customers
FROM Customers
WHERE Id NOT IN (
    SELECT DISTINCT(CustomerId)
    FROM Orders
)

184. Department Highest Salary#

https://leetcode.com/problems/department-highest-salary/

用一个子查询，按照每个部门选出最高的工资，得到若干(DepartmentId, Salary)组合；再遍历Employee表，找到匹配的记录。

SELECT D.Name AS Department, E.Name AS Employee, E.Salary
FROM Employee E, Department D
WHERE E.DepartmentId = D.Id AND (E.DepartmentId, E.Salary) IN (
    SELECT DepartmentId, max(Salary) AS max
    FROM Employee
    GROUP BY DepartmentId
)

185. Department Top Three Salaries#

https://leetcode.com/problems/department-top-three-salaries/

与上一题思路类似，仍然使用子查询。

SELECT D.name Department, E.name Employee, E.salary Salary
FROM Employee E, Department D
WHERE E.DepartmentId = d.Id AND (
        SELECT COUNT(*)
        FROM (SELECT DISTINCT Salary, DepartmentId FROM Employee) T
        WHERE T.DepartmentId = E.DepartmentId AND T.Salary >= E.Salary
    ) <= 3
ORDER BY D.name, E.salary desc

186. Reverse Words in a String II#

https://leetcode.com/problems/reverse-words-in-a-string-ii/

先颠倒整个字符串，之后利用空格或是字符串终点，判定当前单词的范围，再颠倒每一个单词。

class Solution {
    public void reverseWords(char[] s) {
        if (s == null || s.length <= 1) {
            return;
        }


        reverse(s, 0, s.length - 1);


        for (int i = 0, j = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                // reverse current word
                reverse(s, j, i - 1);


                // set j to next word's start
                j = i + 1;
            }
        }
    }


    // reverse characters in [begin, end]
    private void reverse(char[] s, int begin, int end) {
        while (begin < end) {
            char c = s[begin];
            s[begin] = s[end];
            s[end] = c;


            begin++;
            end--;
        }
    }
}

187. Repeated DNA Sequences#

https://leetcode.com/problems/repeated-dna-sequences/

使用两个集合seen和repeated。每10个字符作为一个字符串，加入到seen中，如果seen加不进去，说明已经重复出现过了，加到repeated去。最后将repeated转为list即可。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set seen = new HashSet(), repeated = new HashSet();


        for (int i = 0; i < s.length() - 9; i++) {
            String cur = s.substring(i, i + 10);


            if (!seen.add(cur)) {
                repeated.add(cur);
            }
        }


        return new ArrayList(repeated);
    }
}

188. Best Time to Buy and Sell Stock IV#

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

当输入的k很大，超过prices的长度时，无法用完这么多次交易的次数，因此转化为最简单的情况：只要有钱赚，当天买第二天就卖。

k不够大时，设立两个数组buy和sell，其中buy[i]表示第i次买入后用户剩余多少钱，sell[i]表示第i次卖出后用户剩余多少钱。显然有：

  • buy[i] = 上一次卖出后的钱 - 当前股票价格
  • sell[i] = 当前买入之前的钱 + 当前股票价格

视情况决定是否有必要进行交易。结果关注sell[k]即可。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k == 0 || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;


        // k is very large, let's become greedy
        if (k >= len - 1) {
            int result = 0;
            for (int i = 1; i < len; i++) {
                if (prices[i] > prices[i - 1]) {
                    result += prices[i] - prices[i - 1];
                }
            }


            return result;
        }


        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        Arrays.fill(sell, 0);


        for (Integer cur : prices) {
            for (int i = 1; i <= k; i++) {
                buy[i] = Math.max(sell[i - 1] - cur, buy[i]);
                sell[i] = Math.max(buy[i] + cur, sell[i]);
            }
        }


        return sell[k];
    }
}

189. Rotate Array#

https://leetcode.com/problems/rotate-array/

进行三次数组倒序：

  1. 整个数组倒序
  2. 前k个数倒序
  3. 剩余数倒序
class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k < 1) {
            return;
        }
        int len = nums.length;
        if (k > len) {
            k %= len;
        }


        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }


    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;


            start++;
            end--;
        }
    }
}

190. Reverse Bits#

https://leetcode.com/problems/reverse-bits/

解题步骤分为3步：

  1. result左移1位，空出最右的一位
  2. 判断当前n的最后一位是否为1，如果是1，result也要加1。因为此前result的最后一位肯定是0，所以这一步能保证目前result的最后一位和n的最后一位是同步的
  3. n右移一位，表示完成了一位的处理。

循环32次，便可完成逐位转化。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;


        for (int i = 0; i < 32; i++) {
            result <<= 1;


            // add 1 to result if the last bif of n is 1
            result += (n & 1);


            // logic right shift, always complement 0
            n >>>= 1;
        }


        return result;
    }
}

191. Number of 1 Bits#

https://leetcode.com/problems/number-of-1-bits/

利用n & 1提取最后一位的值，再使用右移推进至前一位。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;


        while (n != 0) {
            result += (n & 1);
            n >>>= 1;
        }


        return result;
    }
}

192. Word Frequency#

https://leetcode.com/problems/word-frequency/

bash部分命令：

  • cat: 查看某文件的内容
  • tr: 删除文件中控制字符或进行字符转换。-s参数表示删除所有重复出现字符序列，只保留第一个
  • sort: 将文本文件内容加以排序。-r参数表示以相反顺序排序
  • uniq: 检查及删除文本文件中重复出现的行列。-c参数表示在每列旁边显示该行重复出现的次数。
  • awk: 文本格式化命令。 awk '{print $2}' 表示打印第二个字段。
Terminal window
cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{ print $2, $1 }'

193. Valid Phone Numbers#

https://leetcode.com/problems/valid-phone-numbers/

grep / egrep是Linux中的文本搜索工具，运用正则表达式搜索符合指定格式的字符串。

Terminal window
egrep "^((\([0-9]{3}\) )|([0-9]{3}-))[0-9]{3}-[0-9]{4}$" file.txt

194. Transpose File#

https://leetcode.com/problems/transpose-file/

awk命令中，

  • NF记录域个数，此题中可以理解为文件的行数
  • NR表示已经读取的记录数，此题可以理解为已经读取的文件行数

同时在bash中，字符串的追加非常容易，例如s = s a表示将字符串a追加于s之后。完成awk后，还有一个END部分用于处理输出。其余语法与C语言近似。

Terminal window
awk '
{
  for (i = 1; i <= NF; i++) {
    if (NR == 1) result[i] = $i;
    else result[i] = result[i] " " $i
  }
}
END {
  for (i = 1; result[i] != ""; i++) print result[i];
}' file.txt

195. Tenth Line#

https://leetcode.com/problems/tenth-line/

一种方法是使用cat和awk的组合命令：

cat file.txt | awk 'NR == 10'

另一种方法是使用sed命令。sed可依照脚本的指令来处理、编辑文本文件，单位是行。

sed -n 10p file.txt

其中，-n表示仅显示处理后的结果，p表示打印某个选择的数据。

196. Delete Duplicate Emails#

https://leetcode.com/problems/delete-duplicate-emails/

将相同的邮件地址记录group by合并，只选出每一条合并记录的最小id，其余的id舍弃。

DELETE FROM Person
WHERE Id NOT IN (
    SELECT A.Id
    FROM (
        SELECT Min(Id) AS Id
        FROM Person
        GROUP BY Email
    ) AS A
)

197. Rising Temperature#

https://leetcode.com/problems/rising-temperature/

使用TO_DAYS()函数转化DATE形式的变量，这样一来可以进行日期的比较。

SELECT W2.Id
FROM Weather W1, Weather W2
WHERE TO_DAYS(W2.RecordDate) - TO_DAYS(W1.RecordDate) = 1 AND W2.Temperature > W1.Temperature

198. House Robber#

https://leetcode.com/problems/house-robber/

使用两个变量，prev2表示不考虑当前数的前一个数时，获取的最大收益；prev则综合比较prev2与当前数之和，与不考虑当前数时的收益，哪一个更大选哪个。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }


        // prev2: max profit without current number's prior number
        // prev: max profit between (1. without current number 2. prev2 + current number)
        int prev2 = 0, prev = 0;
        for (int num : nums) {
            int temp = prev;
            prev = Math.max(prev, prev2 + num);
            prev2 = temp;
        }


        return prev;
    }
}

199. Binary Tree Right Side View#

https://leetcode.com/problems/binary-tree-right-side-view/

正常情况下，不断向下搜索当前节点的右节点；但如果右节点为空，则返回搜索左节点。搜索过程中，层数和结果list的长度应当始终对应。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        helper(result, root, 1);
        return result;
    }


    private void helper(List<Integer> result, TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        if (result.size() < depth) {
            result.add(node.val);
        }


        helper(result, node.right, depth + 1);
        helper(result, node.left, depth + 1);
    }
}

200. Number of Islands#

https://leetcode.com/problems/number-of-islands/

使用DFS，已经走过的格子需要置为0，每遇到一个’1’岛屿数就加一。这是因为如果陆地是连续的，在计数之前，在此前的DFS递归调用已经将当前岛屿的邻近’1’全部变为0了。

class Solution {
    private int row = 0, col = 0;


    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }


        row = grid.length;
        col = grid[0].length;


        int result = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    result++;
                }
            }
        }


        return result;
    }


    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] != '1') {
            return;
        }


        grid[x][y] = '0';


        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}
LeetCode 1-100
LeetCode 201-300
Profile Image of the Author
MikeYan01
Hello world!
GitHub
站点统计
文章
23
分类
7
标签
12
总字数
215,225
运行时长
0 天
最后活动
0 天前
1
101. Symmetric Tree
2
102. Binary Tree Level Order Traversal
3
103. Binary Tree Zigzag Level Order Traversal
4
104. Maximum Depth of Binary Tree
5
105. Construct Binary Tree from Preorder and Inorder Traversal
6
106. Construct Binary Tree from Inorder and Postorder Traversal
7
107. Binary Tree Level Order Traversal II
8
108. Convert Sorted Array to Binary Search Tree
9
109. Convert Sorted List to Binary Search Tree
10
110. Balanced Binary Tree
11
111. Minimum Depth of Binary Tree
12
112. Path Sum
13
113. Path Sum II
14
114. Flatten Binary Tree to Linked List
15
115. Distinct Subsequences
16
116. Populating Next Right Pointers in Each Node
17
117. Populating Next Right Pointers in Each Node II
18
118. Pascal’s Triangle
19
119. Pascal’s Triangle II
20
120. Triangle
21
121. Best Time to Buy and Sell Stock
22
122. Best Time to Buy and Sell Stock II
23
123. Best Time to Buy and Sell Stock III
24
124. Binary Tree Maximum Path Sum
25
125. Valid Palindrome
26
126. Word Ladder II
27
127. Word Ladder
28
128. Longest Consecutive Sequence
29
129. Sum Root to Leaf Numbers
30
130. Surrounded Regions
31
131. Palindrome Partitioning
32
132. Palindrome Partitioning II
33
133. Clone Graph
34
134. Gas Station
35
135. Candy
36
136. Single Number
37
137. Single Number II
38
138. Copy List with Random Pointer
39
139. Word Break
40
140. Word Break II
41
141. Linked List Cycle
42
142. Linked List Cycle II
43
143. Reorder List
44
144. Binary Tree Preorder Traversal
45
145. Binary Tree Postorder Traversal
46
146. LRU Cache
47
147. Insertion Sort List
48
148. Sort List
49
149. Max Points on a Line
50
150. Evaluate Reverse Polish Notation
51
151. Reverse Words in a String
52
152. Maximum Product Subarray
53
153. Find Minimum in Rotated Sorted Array
54
154. Find Minimum in Rotated Sorted Array II
55
155. Min Stack
56
156. Binary Tree Upside Down
57
157. Read N Characters Given Read4
58
158. Read N Characters Given read4 II - Call Multiple Times
59
159. Longest Substring with At Most Two Distinct Characters
60
160. Intersection of Two Linked Lists
61
161. One Edit Distance
62
162. Find Peak Element
63
163. Missing Ranges
64
164. Maximum Gap
65
165. Compare Version Numbers
66
166. Fraction to Recurring Decimal
67
167. Two Sum II - Input Array Is Sorted
68
168. Excel Sheet Column Title
69
169. Majority Element
70
170. Two Sum III - Data structure design
71
171. Excel Sheet Column Number
72
172. Factorial Trailing Zeroes
73
173. Binary Search Tree Iterator
74
174. Dungeon Game
75
175. Combine Two Tables
76
176. Second Highest Salary
77
177. Nth Highest Salary
78
178. Rank Scores
79
179. Largest Number
80
180. Consecutive Numbers
81
181. Employees Earning More Than Their Managers
82
182. Duplicate Emails
83
183. Customers Who Never Order
84
184. Department Highest Salary
85
185. Department Top Three Salaries
86
186. Reverse Words in a String II
87
187. Repeated DNA Sequences
88
188. Best Time to Buy and Sell Stock IV
89
189. Rotate Array
90
190. Reverse Bits
91
191. Number of 1 Bits
92
192. Word Frequency
93
193. Valid Phone Numbers
94
194. Transpose File
95
195. Tenth Line
96
196. Delete Duplicate Emails
97
197. Rising Temperature
98
198. House Robber
99
199. Binary Tree Right Side View
100
200. Number of Islands
文章目录
1
101. Symmetric Tree
2
102. Binary Tree Level Order Traversal
3
103. Binary Tree Zigzag Level Order Traversal
4
104. Maximum Depth of Binary Tree
5
105. Construct Binary Tree from Preorder and Inorder Traversal
6
106. Construct Binary Tree from Inorder and Postorder Traversal
7
107. Binary Tree Level Order Traversal II
8
108. Convert Sorted Array to Binary Search Tree
9
109. Convert Sorted List to Binary Search Tree
10
110. Balanced Binary Tree
11
111. Minimum Depth of Binary Tree
12
112. Path Sum
13
113. Path Sum II
14
114. Flatten Binary Tree to Linked List
15
115. Distinct Subsequences
16
116. Populating Next Right Pointers in Each Node
17
117. Populating Next Right Pointers in Each Node II
18
118. Pascal’s Triangle
19
119. Pascal’s Triangle II
20
120. Triangle
21
121. Best Time to Buy and Sell Stock
22
122. Best Time to Buy and Sell Stock II
23
123. Best Time to Buy and Sell Stock III
24
124. Binary Tree Maximum Path Sum
25
125. Valid Palindrome
26
126. Word Ladder II
27
127. Word Ladder
28
128. Longest Consecutive Sequence
29
129. Sum Root to Leaf Numbers
30
130. Surrounded Regions
31
131. Palindrome Partitioning
32
132. Palindrome Partitioning II
33
133. Clone Graph
34
134. Gas Station
35
135. Candy
36
136. Single Number
37
137. Single Number II
38
138. Copy List with Random Pointer
39
139. Word Break
40
140. Word Break II
41
141. Linked List Cycle
42
142. Linked List Cycle II
43
143. Reorder List
44
144. Binary Tree Preorder Traversal
45
145. Binary Tree Postorder Traversal
46
146. LRU Cache
47
147. Insertion Sort List
48
148. Sort List
49
149. Max Points on a Line
50
150. Evaluate Reverse Polish Notation
51
151. Reverse Words in a String
52
152. Maximum Product Subarray
53
153. Find Minimum in Rotated Sorted Array
54
154. Find Minimum in Rotated Sorted Array II
55
155. Min Stack
56
156. Binary Tree Upside Down
57
157. Read N Characters Given Read4
58
158. Read N Characters Given read4 II - Call Multiple Times
59
159. Longest Substring with At Most Two Distinct Characters
60
160. Intersection of Two Linked Lists
61
161. One Edit Distance
62
162. Find Peak Element
63
163. Missing Ranges
64
164. Maximum Gap
65
165. Compare Version Numbers
66
166. Fraction to Recurring Decimal
67
167. Two Sum II - Input Array Is Sorted
68
168. Excel Sheet Column Title
69
169. Majority Element
70
170. Two Sum III - Data structure design
71
171. Excel Sheet Column Number
72
172. Factorial Trailing Zeroes
73
173. Binary Search Tree Iterator
74
174. Dungeon Game
75
175. Combine Two Tables
76
176. Second Highest Salary
77
177. Nth Highest Salary
78
178. Rank Scores
79
179. Largest Number
80
180. Consecutive Numbers
81
181. Employees Earning More Than Their Managers
82
182. Duplicate Emails
83
183. Customers Who Never Order
84
184. Department Highest Salary
85
185. Department Top Three Salaries
86
186. Reverse Words in a String II
87
187. Repeated DNA Sequences
88
188. Best Time to Buy and Sell Stock IV
89
189. Rotate Array
90
190. Reverse Bits
91
191. Number of 1 Bits
92
192. Word Frequency
93
193. Valid Phone Numbers
94
194. Transpose File
95
195. Tenth Line
96
196. Delete Duplicate Emails
97
197. Rising Temperature
98
198. House Robber
99
199. Binary Tree Right Side View
100
200. Number of Islands