Leetcode 214 Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution 1: use KMP calculate next array. If R is the reverse of s. Make a combo string which is s+'#'+R.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n==0) return "";  
     StringBuilder sb=new StringBuilder(s);  
     String combo=s+'#'+sb.reverse().toString();  
     int[] next=new int[2*n+2];  
     next[0]=-1;  
     int j=0, k=-1;  
     while (j<2*n+1) {  
       if (k==-1 || combo.charAt(k)==combo.charAt(j)) {  
         k++;  
         j++;  
         next[j]=k;  
       }  
       else k=next[k];  
     }  
     StringBuilder res=new StringBuilder(s.substring(next[2*n+1]));  
     return res.reverse().toString()+s;  
   }  
 }  

Solution 2: calculate next array of s, then search in R. O(n)

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n<2) return s;  
     int[] next=new int[n];  
     int k=-1,j=0;  
     next[0]=-1;  
     while (j<n-1) {  
       if (k==-1 || s.charAt(k)==s.charAt(j)) {  
         k++;  
         j++;  
         next[j]=s.charAt(k)==s.charAt(j)?next[k]:k;  
       }  
       else k=next[k];  
     }  
     String r=new StringBuilder(s).reverse().toString();  
     int i=0;  
     j=0;  
     while (i<n && j<n) {  
       if (j==-1 || r.charAt(i)==s.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     return new StringBuilder(s.substring(j)).reverse().toString()+s;  
   }  
 }  

Solution 3: optimize space and time complexity to be half of solution 2.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n<2) return s;  
     int[] next=new int[n/2];  
     int k=-1,j=0;  
     next[0]=-1;  
     while (j<n/2-1) {  
       if (k==-1 || s.charAt(k)==s.charAt(j)) {  
         k++;  
         j++;  
         next[j]=s.charAt(k)==s.charAt(j)?next[k]:k;  
       }  
       else k=next[k];  
     }  
     String r=new StringBuilder(s).reverse().toString();  
     int i=0;  
     j=0;  
     while (i+j<n) {  
       if (j==-1 || r.charAt(i)==s.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     return r.substring(0,i-j)+s;  
   }  
 }  

Leetcode 213 House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution 1: 0 or n-1, one of them must not be robbed. Use DP and House Robber I solution to calculate [0..n-2] and [1...n-1] then get the max of the two.

 public class Solution {  
   public int rob(int[] nums) {  
     int n=nums.length;  
     if (n==0) return 0;  
     if (n==1) return nums[0];  
     return Math.max(rob(nums,0,n-2),rob(nums,1,n-1));  
   }  
   private int rob(int[] nums, int lo, int hi) {  
     int a=0, b=0;// a rob it, b not rot it  
     for (int i=lo; i<=hi; i++) {  
       if (i==lo) {  
         a=nums[i];  
       }  
       else {  
         int aNext=b+nums[i];  
         b=Math.max(a,b);  
         a=aNext;  
       }  
     }  
     return Math.max(a,b);  
   }  
 }  

Leetcode 212 Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution 1: the combination of graph and trie. First use dictionary to build the trie. Then DFS the char array to come up the result list.

 public class Solution {  
   class TrieNode {  
     private boolean val=false;  
     private TrieNode[] next=new TrieNode[26];  
   }  
   private TrieNode root=new TrieNode();  
   private void add(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   private TrieNode search(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) return null;  
       x=x.next[index];  
     }  
     return x;  
   }  
   private boolean findOne(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return x.val;  
   }  
   private boolean findPrefix(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return true;  
   }  
   public List<String> findWords(char[][] board, String[] words) {  
     Set<String> res=new HashSet<>();  
     for (String s:words) add(s);  
     int m=board.length;  
     if (m==0) return new ArrayList<String>(res);  
     int n=board[0].length;  
     String s="";  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         dfs(board,i,j,m,n,s,res);  
       }  
     }  
     return new ArrayList<String>(res);  
   }  
   private void dfs(char[][] board, int i, int j, int m, int n, String s, Set<String> res) {  
     if (i<0 || i>=m) return;  
     if (j<0 || j>=n) return;  
     if (board[i][j]=='.') return;  
     char c=board[i][j];  
     String word=s+c;  
     if (!findPrefix(word)) return;  
     if (findOne(word)) res.add(word);  
     board[i][j]='.';  
     dfs(board,i+1,j,m,n,word,res);  
     dfs(board,i-1,j,m,n,word,res);  
     dfs(board,i,j+1,m,n,word,res);  
     dfs(board,i,j-1,m,n,word,res);  
     board[i][j]=c;  
   }  
 }  

Leetcode 211 Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Solution 1: use Trie will be much easier for string search.

 public class WordDictionary {  
   class TrieNode {  
     private boolean val=false;  
     private TrieNode[] next=new TrieNode[26];  
   }  
   private TrieNode root=new TrieNode();  
   // Adds a word into the data structure.  
   public void addWord(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   // Returns if the word is in the data structure. A word could  
   // contain the dot character '.' to represent any one letter.  
   public boolean search(String word) {  
     return search(root,word,0);  
   }  
   private boolean search(TrieNode x, String word, int d) {  
     if (x==null) return false;  
     if (d==word.length()) return x.val;  
     for (int i=0; i<26; i++) {  
       char c=word.charAt(d);  
       if (c=='.' || c=='a'+i) {  
         if (search(x.next[i],word,d+1)) return true;  
       }  
     }  
     return false;  
   }  
 }  

Leetcode 210 Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Solution 1: build the graph, then DFS to judge if there is loop. If not topo sort.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     Deque<Integer> stack=new LinkedList<>();  
     for (int v=0; v<V; v++)  
       if (!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle,stack);  
     if (hasCycle[0]) return new int[0];  
     int[] res=new int[V];  
     for (int i=0; i<V; i++) res[i]=stack.pop();  
     return res;  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle, Deque<Integer> stack) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w:adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle,stack);  
       else if(onStack[w]) hasCycle[0]=true;  
     }  
     stack.push(v);  
     onStack[v]=false;  
   }  
 }  

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Solution 1: slide window.

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

Leetcode 208 Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution 1: Implement problem.

 class TrieNode {  
   // Initialize your data structure here.  
   boolean val=false;  
   TrieNode[] next=new TrieNode[26];  
   public TrieNode() {  
   }  
 }  
 public class Trie {  
   private TrieNode root;  
   public Trie() {  
     root = new TrieNode();  
   }  
   // Inserts a word into the trie.  
   public void insert(String word) {  
     int i=0;  
     TrieNode x=root;  
     while (i<word.length()) {  
       int index=word.charAt(i)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       i++;  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i)-'a';  
       if (x.next[index]==null) return false;  
       i++;  
       x=x.next[index];  
     }  
     return x.val;  
   }  
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
     TrieNode x=root;  
     int i=0;  
     while (i<prefix.length()) {  
       int index=prefix.charAt(i)-'a';  
       if (x.next[index]==null) return false;  
       i++;  
       x=x.next[index];  
     }  
     return true;  
   }  
 }  

Leetcode 207 Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solution 1: Directed graph loop question. Build the graph and then DFS.

 public class Solution {  
   public boolean canFinish(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     for (int v=0; v<V; v++)  
       if(!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle);  
     return !hasCycle[0];  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w: adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle);  
       else if (onStack[w]) hasCycle[0]=true;  
     }  
     onStack[v]=false;  
   }  
 }  

Leetcode 206 Reverse Linked List

Reverse a singly linked list.
Solution 1: easy

 public class Solution {  
   public ListNode reverseList(ListNode head) {  
     ListNode i=head, j=null;  
     while (i!=null) {  
       ListNode next=i.next;  
       i.next=j;  
       j=i;  
       i=next;  
     }  
     return j;  
   }  
 }  

Leetcode 205 Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Solution 1: Use 2 hash map record s->t and t->s mapping.

 public class Solution {  
   public boolean isIsomorphic(String s, String t) {  
     if (s.length()!=t.length()) return false;  
     Map<Character,Character> map1=new HashMap<>();  
     Map<Character,Character> map2=new HashMap<>();  
     for (int i=0; i<s.length(); i++) {  
       char c1=s.charAt(i), c2=t.charAt(i);  
       if (map1.containsKey(c1)) {  
         if (map1.get(c1)!=c2) return false;  
       }  
       else map1.put(c1,c2);  
       if (map2.containsKey(c2)) {  
         if (map2.get(c2)!=c1) return false;  
       }  
       else map2.put(c2,c1);  
     }  
     return true;  
   }  
 }  

Leetcode 204 Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Solution 1: close to O(n) time complex.

 public class Solution {  
   public int countPrimes(int n) {  
     boolean[] flag=new boolean[n+1];  
     for (int i=2; i*i<n; i++) {  
       if (!flag[i]) {  
         for (int j=i; j*i<n; j++) flag[i*j]=true;  
       }  
     }  
     int count=0;  
     for (int i=2; i<n; i++)  
       if (!flag[i]) count++;  
     return count;  
   }  
 }  

Leetcode 203 Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Solution 1: easy linked list problem.

 public class Solution {  
   public ListNode removeElements(ListNode head, int val) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode p=dummy;  
     while (p.next!=null) {  
       if (p.next.val==val) p.next=p.next.next;  
       else p=p.next;  
     }  
     return dummy.next;  
   }  
 }  

Leetcode 202 Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Solution 1: use hash table to record if duplicate or not. If Duplication is 1 return true, else return zero.

 public class Solution {  
   public boolean isHappy(int n) {  
     Set<Integer> set=new HashSet<>();  
     while (!set.contains(n)) {  
       set.add(n);  
       n=next(n);  
     }  
     if (n==1) return true;  
     return false;  
   }  
   private int next(int x) {  
     int res=0;  
     while (x!=0) {  
       int t=x%10;  
       res+=t*t;  
       x=x/10;  
     }  
     return res;  
   }  
 }  

Leetcode 201 Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Solution 1: from m to n, the leading common part of binary format will be kept, different part will be all zeros.

 public class Solution {  
   public int rangeBitwiseAnd(int m, int n) {  
     for (int i=0; i<32; i++) {  
       if (m==n) return m<<i;  
       m>>=1;  
       n>>=1;  
     }  
     return 0;  
   }  
 }  

Leetcode 200 Number of Islands

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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Solution 1: max CC question in graph, use DFS.

 public class Solution {  
   public int numIslands(char[][] grid) {  
     int m=grid.length;  
     if (m==0) return 0;  
     int n=grid[0].length;  
     int count=0;  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (grid[i][j]=='1') {  
           count++;  
           dfs(grid,i,j,m,n);  
         }  
       }  
     }  
     return count;  
   }  
   private void dfs(char[][] grid, int i, int j, int m, int n) {  
     if (i<0 || i>=m) return;  
     if (j<0 || j>=n) return;  
     if (grid[i][j]!='1') return;  
     grid[i][j]='x';  
     dfs(grid,i+1,j,m,n);  
     dfs(grid,i-1,j,m,n);  
     dfs(grid,i,j+1,m,n);  
     dfs(grid,i,j-1,m,n);  
   }  
 }  

Leetcode 199 Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Solution 1: Use BFS iterative is better way.

 public class Solution {  
   public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> res=new ArrayList<>();  
     if (root==null) return res;  
     Deque<TreeNode> qu=new LinkedList<>();  
     Deque<TreeNode> next=new LinkedList<>();  
     qu.offer(root);  
     while (!qu.isEmpty()) {  
       TreeNode x=null;  
       while (!qu.isEmpty()) {  
         x=qu.poll();  
         if (x.left!=null) next.offer(x.left);  
         if (x.right!=null) next.offer(x.right);  
       }  
       res.add(x.val);  
       Deque<TreeNode> temp=qu;  
       qu=next;  
       next=temp;  
     }  
     return res;  
   }  

Leetcode 198 House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution 1:  Use DP to record of current max value of rob this one and noRob this one 

 public class Solution {  
   public int rob(int[] nums) {  
     int n=nums.length;  
     if (n==0) return 0;  
     int rob=0;  
     int notRob=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         rob=nums[i];  
         notRob=0;  
       }  
       else {  
         int temp=Math.max(rob,notRob);  
         rob=notRob+nums[i];  
         notRob=temp;  
       }  
     }  
     return Math.max(rob,notRob);  
   }  
 }  

Leetcode 191 Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution 1: easy bit manipulation 

 public class Solution {  
   // you need to treat n as an unsigned value  
   public int hammingWeight(int n) {  
     int count=0;  
     for (int i=0; i<32; i++) {  
       if ((n&1)==1) count++;  
       n>>=1;  
     }  
     return count;  
   }  
 }  

Leetcode 190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Solution 1: Bit manipulation. O(1) 

 public class Solution {  
   // you need treat n as an unsigned value  
   public int reverseBits(int n) {  
     int res=0;  
     for (int i=0; i<32; i++) {  
       res=res<<1|(n&1);  
       n>>=1;  
     }  
     return res;  
   }  
 }  

Leetcode 189 Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Solution 1: O(k) space

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     int n=nums.length;  
     k%=n;  
     int[] t=new int[k];  
     for (int i=n-1; i>=0; i--) {  
       if (i+k>=n) t[i+k-n]=nums[i];  
       else nums[i+k]=nums[i];  
     }  
     for (int i=0; i<k; i++) nums[i]=t[i];  
   }  
 }  

Solution 2: O(n), O(1) use 3 reverse.

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     int n=nums.length;  
     k%=n;  
     reverse(nums,n-k,n-1);  
     reverse(nums,0,n-k-1);  
     reverse(nums,0,n-1);  
   }  
   private void reverse(int[] nums, int lo, int hi) {  
     while (lo<hi) {  
       int temp=nums[lo];  
       nums[lo++]=nums[hi];  
       nums[hi--]=temp;  
     }  
   }  
 }  

Leetcode 188 Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution 1: Use DP, local[i][j] is the max value sell at jth using i transaction. globe[i][j] is global best solution. No need to sell at day j. Space can be optimized to O(k). Also, if k>n/2 can apply fast calculation which is O(n) instead of O(n*k).

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     int n=prices.length;  
     if (k>n/2) return quickSolve(prices);  
     int[] local=new int[k+1];  
     int[] globe=new int[k+1];  
     for (int j=1; j<n; j++) {  
       int pre=0;  
       for (int i=1; i<=k; i++) {  
         int temp=globe[i];  
         local[i]=Math.max(pre,local[i]+prices[j]-prices[j-1]);  
         globe[i]=Math.max(globe[i],local[i]);  
         pre=temp;  
       }  
     }  
     return globe[k];  
   }  
   private int quickSolve(int[] prices) {  
     int res=0;  
     for (int i=1; i<prices.length; i++)  
       if (prices[i]>prices[i-1]) res+=prices[i]-prices[i-1];  
     return res;  
   }  
 }  

Leetcode 187 Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution 1: Use hash map, but store the Integer value instead of String. 2bit can express on DNA bit, 10 DNA bits need 20 binary bits.

 public class Solution {  
   public List<String> findRepeatedDnaSequences(String s) {  
     char[] c=s.toCharArray();  
     List<String> res=new ArrayList<>();  
     int n=c.length, div=1<<20;  
     if (n<10) return res;  
     int num=0;  
     for (int i=0; i<10; i++) num=num*4+value(c[i]);  
     Map<Integer,Integer> map=new HashMap<>();  
     map.put(num,1);  
     for (int i=10; i<n; i++) {  
       num=(num*4+value(c[i]))%div;  
       if (!map.containsKey(num)) map.put(num,1);  
       else if (map.get(num)==1) {  
         map.put(num,2);  
         res.add(new String(c,i-10+1,10));  
       }  
     }  
     return res;  
   }  
   private int value(char c) {  
     if (c=='A') return 0;  
     if (c=='C') return 1;  
     if (c=='G') return 2;  
     return 3;  
   }  
 }  

Leetcode 186 Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Solution 1: rotate each word and then rotate the entire Sting.

 public class Solution {  
   public void reverseWords(char[] s) {  
     int i=0, n=s.length;  
     while (i<n){  
       int j=i;  
       while (j<n && s[j]!=' ') j++;  
       reverse(s,i,j-1);  
       i=++j;  
     }  
     reverse(s,0,n-1);  
   }  
   private void reverse(char[] s, int i, int j) {  
     while (i<j){  
       char temp=s[i];  
       s[i++]=s[j];  
       s[j--]=temp;  
     }  
   }  
 }  

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution 1: use the comparator interface

 public class Solution {  
   class MSBcompare implements Comparator<String> {  
     @Override  
     public int compare(String a, String b){  
       return (a+b).compareTo(b+a);  
     }  
   }  
   public String largestNumber(int[] nums) {  
     int n=nums.length;  
     String[] s=new String[n];  
     for (int i=0; i<n; i++) s[i]=String.valueOf(nums[i]);  
     Arrays.sort(s,new MSBcompare());  
     StringBuilder sb=new StringBuilder();  
     for (int i=n-1; i>=0; i--) sb.append(s[i]);  
     int i=0;  
     while (sb.charAt(i)=='0' && i<n-1) i++;  
     return sb.substring(i);  
   }  
 }  

Leetcode 174 Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution 1: Use DP, the key is start from right bottom and go back to left top.

 public class Solution {  
   public int calculateMinimumHP(int[][] dungeon) {  
     int m=dungeon.length;  
     if (m==0) return 1;  
     int n=dungeon[0].length;  
     if (n==0) return 1;  
     int[] dp=new int[n];  
     for (int i=m-1; i>=0; i--) {  
       for (int j=n-1; j>=0; j--) {  
         if (i==m-1) {  
           if (j==n-1) dp[j]=Math.max(1,1-dungeon[i][j]);  
           else dp[j]=Math.max(1,dp[j+1]-dungeon[i][j]);  
         }  
         else if (j==n-1) dp[j]=Math.max(1,dp[j]-dungeon[i][j]);  
         else dp[j]=Math.max(1,Math.min(dp[j],dp[j+1])-dungeon[i][j]);  
       }  
     }  
     return dp[0];  
   }  
 }  

Leetcode 173 Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution 1: Use iterative in-order traversal.

 public class BSTIterator {  
   private TreeNode x;  
   private Deque<TreeNode> stack;  
   public BSTIterator(TreeNode root) {  
     stack=new LinkedList<>();  
     x=root;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
   }  
   /** @return whether we have a next smallest number */  
   public boolean hasNext() {  
     return !stack.isEmpty();  
   }  
   /** @return the next smallest number */  
   public int next() {  
     x=stack.pop();  
     int res=x.val;  
     x=x.right;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
     return res;  
   }  
 }}  

Leetcode 172 Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution 1:  10=2*5, there is enough 2, just need to find how many "5" in the range of 1...n.

 public class Solution {  
   public int trailingZeroes(int n) {  
     int res=0;  
     for (int div=5; div<=n; div*=5) {  
       res+=n/div;  
       if (div>Integer.MAX_VALUE/5) break;  
     }  
     return res;  
   }  
 }  

Leetcode 171 Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Solution 1: simple math problem.

 public class Solution {  
   public int titleToNumber(String s) {  
     int res=0;  
     for (int i=0; i<s.length(); i++) {  
       int num=s.charAt(i)-'A'+1;  
       res=res*26+num;  
     }  
     return res;  
   }  
 }  

Leetcode 170 Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Solution 1: Use hash table, add is O(1) and find is O(n), not sure why now it TLE.

 public class TwoSum {  
   Map<Integer,Integer> map=new HashMap<>();  
   // Add the number to an internal data structure.  
      public void add(int number) {  
        if (!map.containsKey(number)) map.put(number,1);  
        else map.put(number,map.get(number)+1);  
      }  
   // Find if there exists any pair of numbers which sum is equal to the value.  
      public boolean find(int value) {  
     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
       int i = entry.getKey();  
       int j = value - i;  
       if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {  
         return true;  
       }  
     }  
     return false;  
      }  
 }