Leetcode/各大家--139. Word Break(DP)

139. Word Break(DP)

• Difficulty: Medium 

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

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Company:

Google Uber Facebook Amazon Yahoo Bloomberg Pocket Gems

Kind of similar idea to  Maximum subarray LinkedIn 微软

http://rainykat.blogspot.com/2016/12/leetcodelinkedin-maximum-subarraydp-or.html

思路：Sub-problem is to check if s[j...i） 是否在dict中，double for loop to track,
eg:leetcode dp[0(j)]&&contains key s[0-3(i=4)], set dp[4] = true
                    dp[4(j)]&& contains key s[4-7(i=8)], return dp[8(n)]
 

关键字：DP,substring[start,end)
Complexity：O(N^2) for DP 
 

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];//dp[i+1] means the current s[0...i] check
        dp[0] = true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if (dp[j]&&wordDict.contains(s.substring(j,i))){//s[j,i)
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

Leetcode/Linkedin -- 53.Maximum Subarray(DP or Dvide&Conquer)

53. Maximum Subarray

• Difficulty: Medium

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

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Company:LinkedIn Bloomberg Microsoft
相关题：http://rainykat.blogspot.com/2017/01/leetcode-121-best-time-to-buy-and-sell.html

关键字： DP，Kadene's algorithm(专解maximum subarray相关题)
专业分析： https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts  

思路： fill dp[i] with current max sum, either itself only or dp[i-] + itself(if dp[i-1]>0)
Complexity： Time O(n) Space O(n)

public class Solution {
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];//max sum of arr[0..i]
        for(int i = 1; i < n; i++){
            dp[i] = A[i]+ (dp[i-1]>0?dp[i-1]:0);//in subproblem, A[i] must be contained in max value of current subarray with A[i]
            max = Math.max(max,dp[i]);//max to track the maximum of each max of current subarray A[i]
        }
        return max;
    }
}

Kadene's Algorithm

解法2： 用Kadene's algorithm。 calculate with previous index(max_ending_here), add if res iof A[i-1](max_ending_here)>0, track the end position of max

public class Solution {
    public int maxSubArray(int[] A) {
        int n = A.length;
        
        int max_so_far = A[0],max_ending_here = A[0];
        for(int i = 1; i < n; i++){
            max_ending_here = Math.max(A[i],max_ending_here+A[i]);
            max_so_far = Math.max(max_so_far,max_ending_here);
        }
        return max_so_far;
    }
}

算法小结--LinkedList Recursive/Iterative解法

LinkedList
list.get(index)//O(N)
list.size()//O(1)
 
➤ Dummy Node
巧用一个dummy node的next 来locate一个关键的。比如说，
- tree track the start of the level above current level
 » 117. Populating Next Right Pointers in Each Node II F家微软
http://rainykat.blogspot.com/2017/02/leetcode-33-search-in-rotated-sorted.html


➤ Two Pointer
两个pointer
* 1.slow，slow = slow.next正常loop + 2.fast , fast = fast.next.next 每次走快一步

Ex: find Middle
while(fast != end && fast.next != end){ ...;} slow is middle
» 109. Convert Sorted List to Binary Search Tree(dfs) Zenefit
http://rainykat.blogspot.com/2017/01/leetcodeairbnb-108-convert-sorted-array.html 
» 143. Reorder List
http://rainykat.blogspot.com/2017/03/leetcode-143-reorder-listlinkedlist.html

Ex：查cycle
» 234. Palindrome Linked List F家A家
-- fast/slow ptr to find the half of the list（也用于 148.merge sort，在下面 ）
http://rainykat.blogspot.com/2017/01/leetcodefa-234-palindrome-linked.html

* 1.正常loop， 2 focus关键位置
» 147. Insertion Sort List 各大家
http://rainykat.blogspot.com/2017/03/leetcode-147-insertion-sort-list.html

*2 pointer update while looping 1 pointer focus关键位置（evenlist的start）
» 328. Odd Even Linked List 高频
http://rainykat.blogspot.com/2017/04/leetcode-328-odd-even-linked-list.html

2.partition
Ex:用merge sort来sort list ,巧用2个链表

3.用stack存倒序读数
Ex:add two number, palindrome
 https://leetcode.com/problems/add-two-numbers-ii/

➤ 普通iteration
 » 61. Rotate List
http://rainykat.blogspot.com/2017/05/leetcode-61-rotate-listlinkedlist.html 

➤ Recursive 解法
»  83.82.Remove Duplicates from Sorted List I/II
http://rainykat.blogspot.com/2017/03/8384remove-duplicates-from-sorted-list.html
»  83. Remove Duplicates from Sorted List
head.next接的是下一没有duplicates的list

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode nextN = head.next;
        head.next = deleteDuplicates(head.next);
        //[0,1,1,2,5] head: 2,1,1,0 vs nextN: 5,2,1,1 -- this way from end to start
        if(nextN.val == head.val){//skip dup
            head.next = nextN.next;
            nextN = nextN.next;
        }
        return head;
    }

Loop/Iterative List 题集
» 160. Intersection of Two Linked Lists 各大家
到两个list长度相同的点开始走，找交叉点
http://rainykat.blogspot.com/2017/01/leetcode-160-intersection-of-two-linked.html
»  369. Plus One Linked List(two pointer) G家
http://rainykat.blogspot.com.tr/2017/01/leetcodeg-369-plus-one-linked-listtwo.html
» 92. Reverse Linked List II (Iteration) 
http://rainykat.blogspot.com/2017/01/leetcodef-92-reverse-linked-list-ii.html
Recursion -- O(n) time for n depth, O(n) space for stack
» 22. Merge Two Sorted List(can also iterative) Amazon LinkedIn Apple Microsoft
https://leetcode.com/problems/merge-two-sorted-lists/ 

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        if(l1.val<l2.val){
            l1.next = mergeTwoLists(l1.next,l2);//l1小就取l1,接着merge l2和l1之后的
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }    
 }

» 148. Sort List(上题+merge sort)
http://rainykat.blogspot.com.tr/2017/01/leetcode-148-sort-list-mergesort.html 
» 24. Swap Nodes in Pairs 微软 Bloomberg Uber 
https://leetcode.com/problems/swap-nodes-in-pairs/ 

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode nextN = head.next;
        head.next = swapPairs(nextN.next);
        nextN.next = head;
        return nextN;
    }
}

» 83. Remove duplates in LinkedList
Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list/

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){ return head;}
        head.next = deleteDuplicates(head.next);
        if(head.val==head.next.val){
            head=head.next;//means skip one node             
        }
        return head;
    }
}
 
//sample output 
3&3 

* 

2&3

1&2 

1&1 

*

---

» 203.Remove Linked List Elements - 类似上题
https://leetcode.com/problems/remove-linked-list-elements/ 

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){return head;}//base case different,list can be empty
        head.next = removeElements(head.next,val);//head.next from last num to 1st
        
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

---

 » 206. Reverse LinkedList 各大家的基础题
https://leetcode.com/problems/reverse-linked-list/ 

Recurrsion 
每次回溯把nextnode连到head，head连到null

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null){return head;}
        ListNode nextnode = head.next;
        ListNode newhead = reverseList(head.next);//last node in list
        nextnode.next=head;
        head.next= null;
        return newhead;
    }
}

Iterative:
注意最后是在head=null，所以返回prev（即newhead）

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){ return head;}
        ListNode prev = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;//prev is newhead, head is null
    }
}

---

Interchange LinkedList Nodes
Given a singly linked list: 1->2->3->4->5 
Change it to 1->5->2->4->3 using O(1) space
https://leetcode.com/problems/reverse-linked-list-ii/

Leetcode/LinkedIn -- 366. Find Leaves of Binary Tree - dfs

366. Find Leaves of Binary Tree - dfs

• Difficulty: Medium

https://leetcode.com/problems/find-leaves-of-binary-tree/

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Returns [4, 5, 3], [2], [1].

Explanation:

1. Removing the leaves [4, 5, 3] would result in this tree:

          1
         / 
        2          

2. Now removing the leaf [2] would result in this tree:

          1          

3. Now removing the leaf [1] would result in the empty tree:

          []         

Returns [4, 5, 3], [2], [1].

思路分析：https://discuss.leetcode.com/topic/49194/10-lines-simple-java-solution-using-recursion-with-explanation

 注意点：当前node的高度是 1 + Max（height(node.left),height(node.right)）。leaf的高度是0

             The height of a node is also the its index in the result list (res).

关键字：dfs(recurrsion)

public class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(root,res);
        return res;
    }
    public int dfs(TreeNode root,List<List<Integer>> res){
        if(root==null){ return -1;}
        int height = 1+Math.max(dfs(root.left,res),dfs(root.right,res));
        if(res.size()<height+1) res.add(new ArrayList<Integer>());//if(arr.get(height)==null) will give error
        res.get(height).add(root.val);
        return height;
    }
}

Leetcode/F家 G家 LinkedIn -- 173. Binary Search Tree Iterator (Stack)

173. Binary Search Tree Iterator (Stack)

• Difficulty: Medium

https://leetcode.com/problems/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.

 LinkedIn Google Facebook Microsoft

思路：由于是求最小的数，有点像inorder successor。 一开始加root 和最左的branch(因为最小值在leftmost那里)。每次pop一个中间的node,要把下面的右树补上,只需要右node及它的左枝（下一个最小的数是右node的leftmost one）

public class BSTIterator {
    private Deque<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new LinkedList<TreeNode>();// you can also inialize at var declaration
        pushNode(root);//adding the node leftbranch to get the min
    }

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

    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        int res = cur.val;
        pushNode(cur.right);//when remove a node, need to add its right node's left branch
        return res;
    }
    /*adding the node with its left branch*/
    public void pushNode(TreeNode root){
        while (root != null){
            stack.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */