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/
解题思路如下：
- 寻找到当前节点右子树中最右的节点，如果为空则寻找其兄弟左节点
- 更新当前节点的右子为
prev，这样能之前flatten的子树接到当前节点上；左子为空 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/
解题流程分为三步：
- 初始分配给每个孩子一个糖
- 从左向右，确保位于右侧，
rating更高的孩子比左侧孩子获得更多的糖 - 从右向左，确保位于左侧，
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。
由此我们拆分出两个核心步骤：
-
如果没有将
num记录在ones中，更新ones；否则不记录ones = ones ^ num & ~twos -
如果没有将
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/
解题步骤分为三步：
- 寻找链表的中间元素，将链表分为两部分
- 颠倒后半部分的链表
- 调整指针顺序，将两部分链表交错相连。
/**
* 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/
三步检查：
- 判断
lower和nums的第一个数之间的关系 - 判断每两个数之间是否产生了大于1的间隔（生成缺失区间）
- 判断
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/
解题步骤可划分为：
- 确定正负号
- 将int型输入变量转化为long型，避免溢出
- 小数部分，不断倍增
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/
进行三次数组倒序：
- 整个数组倒序
- 前
k个数倒序 - 剩余数倒序
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步：
result左移1位，空出最右的一位- 判断当前
n的最后一位是否为1，如果是1，result也要加1。因为此前result的最后一位肯定是0，所以这一步能保证目前result的最后一位和n的最后一位是同步的 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}'表示打印第二个字段。
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中的文本搜索工具，运用正则表达式搜索符合指定格式的字符串。
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语言近似。
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);
}
}
PREVIOUSLeetCode 1-100
NEXTLeetCode 201-300