4. Ugly Number

1*2(t2) 2*2 3*2
(t3)1*3 2*3 3*3
(t5)1*5 2*5 3*5


1*2 2*2(t2) 3*2
1*3(t3) 2*3 3*3
(t5)1*5 2*5 3*5


Solution:
public int nthUglyNumber(int n) {
if(n == 1) return 1;
      int t2 = 0, t3 = 0, t5 = 0;
      int[] k = new int[n];
      k[0] = 1;
      for(int i = 1; i < n; i++) {
          k[i] = Math.min(Math.min(k[t2] * 2, k[t3] * 3), k[t5] * 5);
          if (k[i] == k[t2] * 2) t2++;
          if (k[i] == k[t3] * 3) t3++;
          if (k[i] == k[t5] * 5) t5++;
      }
      
      return k[n-1];
}

12. Min Stack

Solution:

1) LinkedList
Node head;
    public MinStack() {
        // do intialization if necessary
        head = null;
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        // write your code here
      if (head == null) {
          head = new Node(number, number, null);
      } else {
          head = new Node(number, Math.min(number, head.min), head);
      }
    }

    /*
     * @return: An integer
     */
    public int pop() {
        // write your code here
        int rst = head.val;
        head = head.next;
        return rst;
    }

    /*
     * @return: An integer
     */
    public int min() {
        // write your code here
        return head.min;
    }
   
    private class Node {
        int val;
        int min;
        Node next;
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }


2) Two stack
Deque<Integer> s1;
    Deque<Integer> s2;
   
    public MinStack() {
        s1 = new ArrayDeque<Integer>();
        s2 = new ArrayDeque<Integer>();
    }
   
    public void push(int number) {
        s1.push(number);
        if (s2.isEmpty() || number <= min()) s2.push(number);
    }
   
    public int pop() {
        if (s1.peek() == min()) s2.pop();
        return s1.pop();
    }
   
    public int min() {
        return s2.peek();
    }

104. Merge K Sorted Lists

Solution:
1) Divide and Conquer:
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
     
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        
        
        ListNode rst = null;
        ListNode dummy = null;
        while(list1 != null && list2 != null) {
            int val = 0;
            if (list1.val < list2.val) {
                val = list1.val;
                list1 = list1.next;
            } else {
                val = list2.val;
                list2 = list2.next;
            }
            
            if(dummy == null) {
                dummy = new ListNode(val);
                rst = dummy;
            } else {
                dummy.next = new ListNode(val);
                dummy = dummy.next;
            }
            
        }
        
        if (list1 == null) dummy.next = list2;
        if (list2 == null) dummy.next = list1;
        
        return rst;
        
    }
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if (lists.size() == 0) return null;
        if (lists.size() == 1) return lists.get(0);
        if (lists.size() == 2) return mergeTwoLists(lists.get(0), lists.get(1));
        return mergeTwoLists(
            mergeKLists(lists.subList(0, lists.size()/2)), 
            mergeKLists(lists.subList(lists.size()/2, lists.size()))
        );
    }
}

107. WordBreak

LintCode:
private int getMaxLength(Set<String> dict) {
        int maxLength = 0;
        for (String word : dict) {
            maxLength = Math.max(maxLength, word.length());
        }
        return maxLength;
    } 

    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int maxLength = getMaxLength(dict);
        boolean[] canSegment = new boolean[s.length() + 1];

        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            canSegment[i] = false;
            for (int lastWordLength = 1;
                     lastWordLength <= maxLength && lastWordLength <= i;
                     lastWordLength++) {
                if (!canSegment[i - lastWordLength]) {
                    continue;
                }
                String word = s.substring(i - lastWordLength, i);
                if (dict.contains(word)) {
                    canSegment[i] = true;
                    break;
                }
            }
        }

        return canSegment[s.length()];
    }


LeetCode ：
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
       
      
       
        int n = s.length();
        boolean[] dp = new boolean[n];
       
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                String sub = s.substring(j, i+1);
              
                // 当这个字存在dict里，要判断要么之前已经break了要么是从头开始的word
                if (wordDict.contains(sub) && (j == 0 || dp[j - 1])) {
                    dp[i] = true;
                    break;
                }
            }
        }
       
        return dp[n - 1];
    }
}

191. Maximum Product Subarray

这道题是Maximum Subarray的follow up
应为乘法所以要考虑负负得正
所以同时记录最小值与最大值

max_products[i] = Math.max(Math.max(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i])；
min_products[i] = Math.min(Math.min(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
        int len = nums.length;
        Integer[] max_products = new Integer[len];
        Integer[] min_products = new Integer[len];
       
        max_products[0] = nums[0];
        min_products[0] = nums[0];
        int max = max_products[0];
        for(int i = 1; i < len; i++) {
            max_products[i] = Math.max(Math.max(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);
            min_products[i] = Math.min(Math.min(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);
            max = Math.max(max_products[i], max);
        }
       
        return max;
    }
}

41. Maximum Subarray

现阶段的最大值等于max（前一位的最大值➕本身 ， 本身）


public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code here
        if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        Integer[] sums = new Integer[len];

        sums[0] = nums[0];
        int max = sums[0];
        for (int i = 1; i < len; i++) {
            sums[i] = Math.max(sums[i-1] + nums[i], nums[i]);
            if(sums[i] > max){
                max = sums[i];
            }
        }
       
        return max;
    }
}

120. Word Ladder

思路：

1. 确认空集，开始词等于结束词的特殊情况
2. 将start string放入queue
3.  length = 1
4. queue进行操作获取当前string的所有transformation
5. 判断dict中是否存在transformation
6. 判断hash中是否已经出现过这个transformation
7. 4 && 5 都没有发生，判断是否为end。 是， 返回length
8. 过即为可能的next level string 加入queue 同时加入hash
1. 任何后出现的同一个transformation string 都是相同length 或者length + 1...
9. 循环直到queue空返回0

public class Solution {
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    public int ladderLength(String start, String end, Set<String> dict) {
      if (dict == null) {
          return 0;
      }
     
      if (start.equals(end)) {
          return 1;
      }
     
      dict.add(start);
      dict.add(end);
     
      // HashSet检查这个word是否已经作为一个transformation出现过
      HashSet<String> hash = new HashSet<String>();
     
      Queue<String> queue = new LinkedList<String>();
      queue.offer(start);
      hash.add(start);
     
      int length = 1;
      //
      while(!queue.isEmpty()) {
          length++;
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              String word = queue.poll();
              // 获得所有现在word的transformation结果
              // CE: typo getnextWords
              for (String nextWord: getNextWords(word, dict)) {
                  // 判断这个transformation出现过没有
                  if (hash.contains(nextWord)) {
                      continue;
                  }
                  if (nextWord.equals(end)) {
                      return length;
                  }
                 
                  hash.add(nextWord);
                  queue.offer(nextWord);
              }
          }
      }
      return 0;
    }
   
    // replace character of a string at given index to a given character
    // return a new string
    private String replace(String s, int index, char c) {
        // CE: typo charp
        char[] chars = s.toCharArray();
        // CE: typo
        chars[index] = c;
        return new String(chars);
    }
   
    // get connections with given word.
    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
    // it will return ['hit', 'hog']
    private ArrayList<String> getNextWords(String word, Set<String> dict) {
        ArrayList<String> nextWords = new ArrayList<String>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c == word.charAt(i)) {
                    continue;
                }

                String nextWord = replace(word, i ,c);
                if (dict.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }
}