- 2019-04-01
- 2019-04-07
- 2019-04-08
- 2019-04-09
- 99. Recover Binary Search Tree
- 100. Same Tree
- 101. Symmetric Tree
- 102. Binary Tree Level Order Traversal
- 103. Binary Tree Zigzag Level Order Traversal
- 104. Maximum Depth of Binary Tree
- 108. Convert Sorted Array to Binary Search Tree
- 200. Number of Islands
- 5. Longest Palindromic Substring
- 929. Unique Email Addresses
- 904. Fruit Into Baskets
- 2019-04-10
- 2019-04-11
- 2019-04-14
2019-04-01
74. Search a 2D Matrix
Description
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
Solution
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int N = matrix.length;
if(N==0){
return false;
}
int M = matrix[0].length;
int i=0,j=M-1;
while(i<=N-1 && j>=0){
//if it's the target, just return
if(matrix[i][j]==target){
return true;
}else if(matrix[i][j]<target){
//if too small, then go left.
i++;
}else{
//if too large, go down
j--;
}
}
//reach the left bottom and still no match, return false.
return false;
}
}
77. Combinations
Description
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Solution
class Solution {
int N;
int K;
public List<List<Integer>> combine(int n, int k) {
N = n;
K = k;
List<List<Integer>> res = new ArrayList<List<Integer>>();
helper(res,new ArrayList<Integer>(),1);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> temp, int index){
//stop whenever it's the correct length.
if(temp.size()==K){
res.add(new ArrayList<Integer>(temp));
return;
}
for(int i = index;i<=N;i++){
temp.add(i);
//index + 1 to next position.
helper(res, temp,i+1);
temp.remove(temp.size()-1);
}
}
}
78. Subsets
Description
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Solution
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
helper(res, new ArrayList(), nums, 0);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int index){
if(index > nums.length){
return;
}
//add all possible result as long as its length smaller than nums.
res.add(new ArrayList(temp));
for(int i = index;i<nums.length;i++){
temp.add(nums[i]);
helper(res,temp,nums,i+1);
temp.remove(temp.size()-1);
}
}
}
83. Remove Duplicates from Sorted List
Description
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
Solution
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next ==null){
return head;
}
//recursivly add to next.
head.next = deleteDuplicates(head.next);
//if the next one is duplicate, then jump to next.
return head.val==head.next.val?head.next:head;
}
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode dummy = head;
while(dummy.next!=null){
//if duplicate, then discard current next.
if(dummy.next.val== dummy.val){
dummy.next = dummy.next.next;
}else{
//else move to next value.
dummy = dummy.next;
}
}
return head;
}
}
86. Partition List
Description
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Solution
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode great = new ListNode(0);
ListNode smallTemp = small;
ListNode greatTemp = great;
while(head!=null){
if(head.val<x){
smallTemp.next = head;
smallTemp = smallTemp.next;
}else{
greatTemp.next = head;
greatTemp = greatTemp.next;
}
head = head.next;
}
//need to set this to null or will have memory limit exceed.
greatTemp.next = null;
//concat two list.
smallTemp.next = great.next;
return small.next;
}
}
2019-04-07
91. Decode Ways
Description
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solution
class Solution {
public int numDecodings(String s) {
int N = s.length();
int[] dp = new int[N+1];
dp[N] = 1;
//last char is 0 then it will be 0 cause itself is not an option.
dp[N-1] = s.charAt(N-1)=='0'?0:1;
for(int i = N-2;i>=0;i--){
//then i-1 will be 0+dp[i-2] since 0 itself is not valid.
if(s.charAt(i)=='0'){
continue;
}else{
//get the number and check if it's <=26
int n = (s.charAt(i)-'0')*10 + (s.charAt(i+1)-'0');
dp[i] = n<=26? dp[i+1]+dp[i+2]:dp[i+1];
}
}
return dp[0];
}
}
92. Reverse Linked List II
Description
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Solution
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 0; i<m-1; i++) pre = pre.next;
ListNode cur = pre.next;
ListNode then = cur.next;
for(int i = 0; i<n-m; i++){
//look at the pattern:
//looks like a chain.
cur.next = then.next;
then.next = pre.next;
pre.next = then;
then = cur.next;
}
return dummy.next;
}
}
93. Restore IP Addresses
Description
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Solution
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new LinkedList<>();
helper(s,res,new StringBuilder(),0,0);
return res;
}
private void helper(String s, List<String> res, StringBuilder sb, int index, int level){
//become invalid.
if(index > s.length() || level > 4) return;
//an valid result, add to res list.
if(index == s.length() && level == 4){
res.add(sb.toString());
return;
}
//try three possible digits to read a number.
for(int i = 1;i<=3;i++){
if(index+i > s.length()){
break;
}
//get possible number
int num = Integer.parseInt(s.substring(index,index+i));
//only process valid number
if(i==1 || i==2&&num>=10&&num<=99 || i==3&&num>=100&&num<=255){
sb.append(num);
//last level should not add '.'
if(level<3) sb.append('.');
helper(s,res,sb,index+i,level+1);
//remember to remove them afterwards.
if(level<3) sb.deleteCharAt(sb.length()-1);
//delete number.
sb.delete(sb.length()-i,sb.length());
}
}
}
}
94. Binary Tree Inorder Traversal
Description
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Solution
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
//return condition.
if(root==null){
return res;
}
//search left branch.
if(root.left !=null){
res.addAll(inorderTraversal(root.left));
}
//inorder, so add the value in the middle.
res.add(root.val);
//right branch.
if(root.right != null){
res.addAll(inorderTraversal(root.right));
}
return res;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
//go left as far as possible.
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
//retrieve one from stack.
//now we can assure that cur.left have been fully explored.
cur = stack.pop();
res.add(cur.val);
//after add root, go to right.
cur = cur.right;
}
return res;
}
}
144. Binary Tree Preorder Traversal
Description
Given a binary tree, return the preorder traversal of its nodes’ values.
Solution
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
if(root == null) return res;
//add root value first and then left then right.
res.add(root.val);
if(root.left!=null){
res.addAll(preorderTraversal(root.left));
}
if(root.right!=null){
res.addAll(preorderTraversal(root.right));
}
return res;
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val); // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
}
145. Binary Tree Postorder Traversal
Description
Given a binary tree, return the postorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
Solution
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
if(root == null) return res;
if(root.left!=null){
res.addAll(postorderTraversal(root.left));
}
if(root.right!=null){
res.addAll(postorderTraversal(root.right));
}
//left then right then at last add root value.
res.add(root.val);
return res;
}
}
145 Summary of BST Traversal
three way to traversal the whole BST.
Pre Order Traverse
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val); // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
In Order Traverse
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val); // Add after all left children
p = node.right;
}
}
return result;
}
Post Order Traverse
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}
96. Unique Binary Search Trees
Description
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i<=n;i++){
//for each i, we sum up all possible combinations.
for(int j = 1;j<=i;j++){
//for j is the root, then left branch is j-1 and right is i-j.
//so multiply them will be the number of way that left branch have j-1 child.
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}
2019-04-08
97. Interleaving String
Description
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Solution
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int N1 = s1.length();
int N2 = s2.length();
int N3 = s3.length();
//not the same length then it cannot be true;
if(N1+N2!=N3){
return false;
}
boolean[][] dp = new boolean[N2+1][N1+1];
//don't forget to init.
dp[0][0] = true;
//find same prefix.
for(int i = 1;i<=N1;i++){
dp[0][i] = dp[0][i-1] && s1.charAt(i-1)==s3.charAt(i-1);
}
//find the same prefix.
//remember to init something related to 0.
for(int i = 1;i<=N2;i++){
dp[i][0] = dp[i-1][0] && s2.charAt(i-1)==s3.charAt(i-1);
}
for(int i=1;i<=N2;i++){
for(int j = 1;j<=N1;j++){
//find if cur digits in s1 or s2 is a valid pattern.
dp[i][j] =
//find last char in s2 == s3.
(dp[i-1][j]&&s2.charAt(i-1)==s3.charAt(i+j-1)) ||
(dp[i][j-1]&&s1.charAt(j-1)==s3.charAt(i+j-1));
}
}
return dp[N2][N1];
}
}
98. Validate Binary Search Tree
Description
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
Solution
//basiclly it's inorder search except that we keep a pre to check the order.
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
TreeNode pre = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
//chenck if it's valid.
//inorder should be monotonously increasing.
if(pre!=null && cur.val<=pre.val){
return false;
}
pre = cur;
cur = cur.right;
}
return true;
}
}
2019-04-09
99. Recover Binary Search Tree
Description
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]
1
/
3
\
2
Output: [3,1,null,null,2]
3
/
1
\
2
Example 2:
Input: [3,1,4,null,null,2]
3
/ \
1 4
/
2
Output: [2,1,4,null,null,3]
2
/ \
1 4
/
3
Solution
class Solution {
//main idea is to do a inorder search and find two abnormal pair, than switch.
public void recoverTree(TreeNode root) {
if(root==null){
return;
}
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
TreeNode firstElement = null;
TreeNode secondElement = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (firstElement == null && pre.val > cur.val) {
firstElement = pre;
}
// If first element is found, assign the second element to the root (refer to 2 in the example above)
if (firstElement != null && pre.val > cur.val) {
secondElement = cur;
}
pre = cur;
cur = cur.right;
}
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
}
100. Same Tree
Easy
1056
32
Favorite
Share Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
Solution
class Solution {
//simple recursive method.
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null){
return true;
}
if(p!=null&&q!=null){
return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
return false;
}
}
101. Symmetric Tree
Description
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Solution
class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}
private boolean isSymmetricHelp(TreeNode left, TreeNode right){
if(left==null || right==null)
return left==right;
if(left.val!=right.val)
return false;
return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
}
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Stack<TreeNode> st = new Stack();
st.push(root.left);
st.push(root.right);
while(!st.isEmpty()){
if(st.size()%2!=0){
return false;
}
TreeNode t1 = st.pop();
TreeNode t2 = st.pop();
//finished
if(t1 == null && t2 == null && st.isEmpty()) break;
//valid, continue.
if(t1 == null && t2 == null && !st.isEmpty()) continue;
//both invalid.
if(t1 == null || t2 == null) return false;
if(t1.val != t2.val) return false;
//push symmetriclly.
st.push(t1.left);
st.push(t2.right);
st.push(t1.right);
st.push(t2.left);
}
return true;
}
}
102. Binary Tree Level Order Traversal
Description
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Solution
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList();
if(root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> tempL = new LinkedList();
Queue<TreeNode> tempQ = new LinkedList();
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
tempL.add(cur.val);
if(cur.left != null){
tempQ.offer(cur.left);
}
if(cur.right != null){
tempQ.offer(cur.right);
}
}
res.add(new LinkedList(tempL));
queue = tempQ;
}
return res;
}
}
103. Binary Tree Zigzag Level Order Traversal
Description
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList();
if(root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList();
boolean isRev = false;
queue.offer(root);
while(!queue.isEmpty()){
Deque<Integer> temp = new LinkedList();
Queue<TreeNode> tempQ = new LinkedList();
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
//mark reverse or not, if reverse then just add to head.
if(isRev){
temp.addFirst(cur.val);
}else{
temp.addLast(cur.val);
}
if(cur.left != null){
tempQ.offer(cur.left);
}
if(cur.right != null){
tempQ.offer(cur.right);
}
}
//don't forget to create a new onw;
res.add(new LinkedList(temp));
queue = tempQ;
isRev = !isRev;
}
return res;
}
}
104. Maximum Depth of Binary Tree
Description
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
Solution
class Solution {
public int maxDepth(TreeNode root) {
if(root ==null) return 0;
int maxDepth = Integer.MIN_VALUE;
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right)+1);
}
}
108. Convert Sorted Array to Binary Search Tree
Description
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Solution
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums,0,nums.length-1);
}
private TreeNode helper(int[] nums, int start, int end){
//out of range.
if(start>end){
return null;
}
int mid = (start + end)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,start,mid-1);
root.right = helper(nums,mid+1,end);
return root;
}
}
200. Number of Islands
Description
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Solution
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
//for each position, find an island and set the whole island as visited.
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(grid[i][j]=='1'){
res++;
setAll(grid,j,i);
}
}
}
return res;
}
//need to set the whole island to non-1 as mark visited.
private void setAll(char[][] grid,int x, int y){
if(x<0 || x>=grid[0].length || y<0 || y >=grid.length || grid[y][x] == '#'){
return;
}
if(grid[y][x] == '1'){
//must set to # or the recursio will go forever between two node(x-1 -> x+1)
grid[y][x] = '#';
setAll(grid,x+1,y);
setAll(grid,x-1,y);
setAll(grid,x,y+1);
setAll(grid,x,y-1);
}
//if it's 0 set to # as well.
grid[y][x] = '#';
return;
}
}
5. Longest Palindromic Substring
Description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Solution
class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
for (int i = 0; i < len - 1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i + 1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
}
929. Unique Email Addresses
Description
Every email consists of a local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.
Besides lowercase letters, these emails may contain ‘.’s or ‘+’s.
If you add periods (‘.’) between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, “alice.z@leetcode.com” and “alicez@leetcode.com” forward to the same email address. (Note that this rule does not apply for domain names.)
If you add a plus (‘+’) in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)
It is possible to use both of these rules at the same time.
Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?
Example 1:
Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails
Note:
1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one ‘@’ character.
All local and domain names are non-empty.
Local names do not start with a ‘+’ character.
Solution
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet();
for(String s: emails){
String local = "";
String domain = "";
for(int i = s.length()-1;i>=0;i--){
if(s.charAt(i)=='@'){
local = s.substring(0,i);
domain = s.substring(i+1);
break;
}
}
int j = 0;
while(j<local.length() && local.charAt(j)!='+'){
j++;
}
local = local.substring(0,j);
local = local.replaceAll("\\.","");
String temp = local + "@" + domain;
set.add(temp);
}
System.out.print(set);
return set.size();
}
}
904. Fruit Into Baskets
Description
In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:
Add one piece of fruit from this tree to your baskets. If you cannot, stop. Move to the next tree to the right of the current tree. If there is no tree to the right, stop. Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2:
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].
Example 3:
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].
Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.
Note:
1 <= tree.length <= 40000
0 <= tree[i] < tree.length
Solution
class Solution {
public int totalFruit(int[] tree) {
int cur = 0, next = 0, nextCount = 0;
int res = 0, count = 0;
for(int c:tree){
count = c==cur||c==next ? count+1 : nextCount+1;
nextCount = c==next? nextCount+1 : 1;
if(next != c){
cur = next;
next = c;
}
res = Math.max(res,count);
}
return res;
}
}
2019-04-10
42. Trapping Rain Water
Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Solution
instead of calculating area by height*width, we can think it in a cumulative way. In other words, sum water amount of each bin(width=1).
Search from left to right and maintain a max height of left and right separately, which is like a one-side wall of partial container.
Fix the higher one and flow water from the lower part. For example, if current height of left is lower, we fill water in the left bin.
Until left meets right, we filled the whole container.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length-1;
int leftMax = 0, rightMax = 0;
int count = 0;
while(left<right){
leftMax = Math.max(leftMax,height[left]);
rightMax = Math.max(rightMax, height[right]);
if(leftMax<rightMax){
count += (leftMax-height[left]);
left++;
}else{
count += (rightMax-height[right]);
right--;
}
}
return count;
}
}
3. Longest Substring Without Repeating Characters
Description
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap();
int max = 0;
for(int i=0,j=0;i<s.length();i++){
//found repeating.update head.
if(map.containsKey(s.charAt(i))){
//must use max to find the valid head.
j = Math.max(j,map.get(s.charAt(i))+1);
}
//update closet position of char at i.
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
}
138. Copy List with Random Pointer
Description
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Example 1:
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
Note:
You must return the copy of the given head as a reference to the cloned list.
Solution
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
Node dummy = new Node(0,head,head);
Map<Node,Node> map = new HashMap();
Node cur = head;
Node res = dummy;
while(cur!=null){
//need to build the full map for next iteration's reference.
Node clone = new Node(cur.val,cur.next,cur.random);
map.put(cur,clone);
cur = cur.next;
}
cur = head;
while(cur!=null){
Node clone = map.get(cur);
//use the new clone of clone.next and random;
clone.next = map.get(clone.next);
clone.random = map.get(clone.random);
res.next = clone;
cur = cur.next;
res = res.next;
}
return dummy.next;
}
}
121. Best Time to Buy and Sell Stock
Description
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution
class Solution {
public int maxProfit(int[] prices) {
int curMin = Integer.MAX_VALUE;
int max = 0;
for(int n:prices){
//using a variable to store the min value before current position.
max = Math.max(max,n-curMin);
curMin = Math.min(curMin, n);
}
return max;
}
}
238. Product of Array Except Self
Description
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
Solution
class Solution {
public int[] productExceptSelf(int[] nums) {
int N = nums.length;
int[] res = new int[N];
res[0] = 1;
//res[i] now contains value of product from 1 to i-1.
for(int i = 1;i<N;i++){
res[i] = nums[i-1]*res[i-1];
}
int right =1;
for(int i = N-1;i>=0;i--){
//store i+1 to end product with right.
res[i] *= right;
right *= nums[i];
}
return res;
}
}
11. Container With Most Water
Description
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Solution
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length-1;
int leftMax = height[left];
int rightMax = height[right];
int max = 0;
int curMin = 0;
while(left<right){
curMin = Math.min(leftMax,rightMax);
max = Math.max(max,curMin*(right-left));
//move the min one, cause it cannot get any worse, can only be equal or better.
if(leftMax<rightMax){
left++;
//update max value to the left boundry.
leftMax = Math.max(height[left],leftMax);
}else{
right--;
//update right.
rightMax = Math.max(rightMax,height[right]);
}
}
return max;
}
}
2019-04-11
33. Search in Rotated Sorted Array ???
Description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Solution
public int search(int[] A, int target) {
if (A.length == 0) return -1;
int L = 0, R = A.length-1;
if (target < A[L] && target > A[R]) return -1;
while (L < R) {
int M = (L + R)/2;
if (A[M] <= A[R]) {
if (target > A[M] && target <= A[R]) {
L = M+1;
} else {
R = M;
}
} else {
if (target <= A[M] && target >= A[L]) {
R = M;
} else {
L = M+1;
}
}
}
if (A[L] == target) return L;
else return -1;
}
2019-04-14
811. Subdomain Visit Count
Description
A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.
Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.
We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.
Example 1:
Input:
["9001 discuss.leetcode.com"]
Output:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation:
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.
Example 2:
Input:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation:
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.
Notes:
The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 "." characters.
The input count in any count-paired domain will not exceed 10000.
The answer output can be returned in any order.
Solution
class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
Map<String,Integer> map =new HashMap();
for(String s:cpdomains){
String[] temp = s.split(" ");
int n = Integer.parseInt(temp[0]);
String domain = temp[1];
for(int i = 0;i<domain.length();i++){
if(domain.charAt(i)=='.'){
//for each domain, add to map.
String d = domain.substring(i + 1);
map.put(d, map.getOrDefault(d, 0) + n);
}
}
map.put(domain, map.getOrDefault(domain, 0) + n);
}
List<String> res = new ArrayList();
for (String d : map.keySet()) res.add(map.get(d) + " " + d);
return res;
}
}