[LEET-0000] clean up

fishercoder1534 · fishercoder1534 · commit bd9ef9bccfd3 · 2017-02-07T21:06:23.000-08:00
diff --git a/leetcode-algorithms/README.md b/leetcode-algorithms/README.md
@@ -74,6 +74,7 @@
 |308|[Range Sum Query 2D - Mutable](https://leetcode.com/problems/range-sum-query-2d-mutable/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/RangeSumQuery2DMutable.java)| ? | ? | Hard| Tree
 |306|[Additive Number](https://leetcode.com/problems/additive-number/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/AdditiveNumber.java)| ? | ? | Medium|
 |305|[Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/NumberofIslandsII.java)| ? | ? | Hard| Union Find
+|304|[Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/RangeSumQuery2DImmutable.java)| ? | ? |Medium| 
 |302|[Smallest Rectangle Enclosing Black Pixels](https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/SmallestRectangleEnclosingBlackPixels.java)| ? | O(m*n) | Hard| DFS, BFS
 |301|[Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/RemoveInvalidParentheses.java)| ? | ? | Hard| BFS
 |299|[Bulls and Cows](https://leetcode.com/problems/bulls-and-cows/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BullsandCows.java)| O(n)|O(1) | Easy| 
@@ -182,9 +183,11 @@
 |141|[Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/LinkedListCycle.java)| O(n)|O(1) | Easy| Linked List
 |140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/WordBreakII.java)| ? |O(n^2) | Hard| Backtracking/DFS
 |139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/WordBreak.java)| O(n^2)|O(n) | Medium| DP
+|137|[Single Number II](https://leetcode.com/problems/single-number-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/SingleNumberII.java)| O(n)|O(n) | Medium|
 |135|[Candy](https://leetcode.com/problems/candy/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/Candy.java)| O(n)|O(1) | Hard| Greedy
 |133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS 
 |132|[Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ImplementQueueUsingStacks.java)| O(n)|O(n) | Easy| Stack, Queue
+|129|[Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/SumRootToLeafNumbers.java)| O(n)|O(h) | Medium| DFS
 |125|[Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ValidPalindrome.java)| O(n)|O(1) | Easy| Two Pointers
 |124|[Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BinaryTreeMaximumPathSum.java)| O(n)|O(h) | Hard | Tree
 |122|[Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BestTimeToBuyAndSellStockII.java)| O(n)|O(1) | Medium | Greedy
@@ -194,6 +197,7 @@
 |118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/PascalsTriangle.java)| O(n^2)|O(1) | Easy| 
 |117|[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/PopulatingNextRightPointersinEachNodeII.java)| O(n)|O(1) | Hard| BFS
 |116|[Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/PopulatingNextRightPointersinEachNode.java)| O(n)|O(1) | Medium| BFS
+|115|[Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/DistinctSubsequences.java)| O(m*n)|O(m*n) | Hard| DP
 |114|[Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FlattenBinaryTreetoLinkedList.java)| O(n)|O(h) | Medium| Tree
 |112|[Path Sum](https://leetcode.com/problems/path-sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/PathSum.java)| O(n)|O(1) | Easy| DFS
 |111|[Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MinimumDepthofBinaryTree.java)| O(n)|O(1)~O(h) | Easy| BFS, DFS
@@ -208,6 +212,7 @@
 |97|[Interleaving String](https://leetcode.com/problems/interleaving-string/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/InterleavingString.java)| O(?)|O(?) | Hard| DP
 |96|[Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/UniqueBinarySearchTrees.java) | O(n^2) | O(n) | Medium | Recursion, DP
 |94|[Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BinaryTreeInorderTraversal.java)| O(n)|O(h) | Medium| Binary Tree
+|92|[Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ReverseLinkedListII.java)| O(n)|O(1) | Medium
 |91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/DecodeWays.java)| O(n)|O(n) | Medium| DP
 |89|[Gray Code](https://leetcode.com/problems/gray-code/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/GrayCode.java)|O(n) |O(1)|Medium|Bit Manipulation
 |86|[Partition List](https://leetcode.com/problems/partition-list/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/PartitionList.java)|O(?) |O(?)|Medium|
@@ -252,6 +257,7 @@
 |22|[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/GenerateParentheses.java)|TBD|O(n)|Medium|Backtracking
 |21|[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MergeTwoSortedLists.java)|O(n)|O(1)|Easy|
 |20|[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ValidParentheses.java)|O(n)|O(n)|Easy|Stack
+|19|[Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/RemoveNthNodeFromEndOfList)|O(n)|O(1)|Medium| Linked List
 |18|[4Sum](https://leetcode.com/problems/4sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/_4Sum.java)|O(n^2)|O(1)|Medium|Two Pointers
 |17|[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/LetterCombinationsofaPhoneNumber.java)|O(n*4^n)|O(n)|Medium|Backtracking
 |16|[3Sum Closest](https://leetcode.com/problems/3sum-closest/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/_3SumClosest.java)|O(nlogn)|O(1)|Medium|Two Pointers
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/RangeSumQuery2DImmutable.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/RangeSumQuery2DImmutable.java
@@ -0,0 +1,56 @@
+package com.stevesun.solutions;
+
+/**
+ * Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
+
+ Range Sum Query 2D
+ The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
+
+ Example:
+ Given matrix = [
+ [3, 0, 1, 4, 2],
+ [5, 6, 3, 2, 1],
+ [1, 2, 0, 1, 5],
+ [4, 1, 0, 1, 7],
+ [1, 0, 3, 0, 5]
+ ]
+
+ sumRegion(2, 1, 4, 3) -> 8
+ sumRegion(1, 1, 2, 2) -> 11
+ sumRegion(1, 2, 2, 4) -> 12
+ Note:
+ You may assume that the matrix does not change.
+ There are many calls to sumRegion function.
+ You may assume that row1 ≤ row2 and col1 ≤ col2.
+ */
+public class RangeSumQuery2DImmutable {
+
+    public class NumMatrix {
+
+        public NumMatrix(int[][] matrix) {
+            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
+                return;
+
+            /**The dimensions of this tot matrix is actually 1 bigger than the given matrix, cool!*/
+            tot = new int[matrix.length + 1][matrix[0].length + 1];
+            for (int i = 0; i < matrix.length; i++) {
+                for (int j = 0; j < matrix[0].length; j++) {
+                    tot[i + 1][j + 1] = matrix[i][j] + tot[i + 1][j] + tot[i][j + 1] - tot[i][j];
+                }
+            }
+        }
+
+        public int sumRegion(int row1, int col1, int row2, int col2) {
+            return tot[row2 + 1][col2 + 1] - tot[row2 + 1][col1] - tot[row1][col2 + 1]
+                    + tot[row1][col1];
+        }
+
+        int[][] tot;
+    }
+
+/**
+ * Your NumMatrix object will be instantiated and called as such:
+ * NumMatrix obj = new NumMatrix(matrix);
+ * int param_1 = obj.sumRegion(row1,col1,row2,col2);
+ */
+}
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/RemoveNthNodeFromEndOfList.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/RemoveNthNodeFromEndOfList.java
@@ -3,10 +3,7 @@
 import com.stevesun.common.classes.ListNode;
 import com.stevesun.common.utils.CommonUtils;
 
-/**19. Remove Nth Node From End of List  QuestionEditorial Solution  My Submissions
-Total Accepted: 122330
-Total Submissions: 400291
-Difficulty: Easy
+/**19. Remove Nth Node From End of List
 Given a linked list, remove the nth node from the end of list and return its head.
 
 For example,
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/ReverseLinkedListII.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/ReverseLinkedListII.java
@@ -3,6 +3,16 @@
 import com.stevesun.common.classes.ListNode;
 import com.stevesun.common.utils.CommonUtils;
 
+/**Reverse a linked list from position m to n. Do it in-place and in one-pass.
+
+ For example:
+ Given 1->2->3->4->5->NULL, m = 2 and n = 4,
+
+ return 1->4->3->2->5->NULL.
+
+ Note:
+ Given m, n satisfy the following condition:
+ 1 ≤ m ≤ n ≤ length of list.*/
 public class ReverseLinkedListII {
 
     // then I turned to Discuss and find this most upvoted solution:
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/RomantoInteger.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/RomantoInteger.java
@@ -3,6 +3,9 @@
 import java.util.HashMap;
 import java.util.Map;
 
+/**Given a roman numeral, convert it to an integer.
+
+ Input is guaranteed to be within the range from 1 to 3999.*/
 public class RomantoInteger {
 
     public int romanToInt(String s) {
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/SingleNumberII.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/SingleNumberII.java
@@ -3,22 +3,15 @@
 import java.util.HashMap;
 import java.util.Map;
 
-/**137. Single Number II  QuestionEditorial Solution  My Submissions
-Total Accepted: 91512
-Total Submissions: 236469
-Difficulty: Medium
+/**137. Single Number II
 Given an array of integers, every element appears three times except for one. Find that single one.
 
 Note:
 Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
 
-Hide Tags Bit Manipulation
-Show Similar Problems
 */
 public class SingleNumberII {
 
-    //TODO: study its bit manipulation approach, this is a MUST!
-    
     public int singleNumber(int[] nums) {
         Map<Integer, Integer> map = new HashMap();
         for(int i : nums){
diff --git a/leetcode-algorithms/src/main/java/com/stevesun/solutions/SumRootToLeafNumbers.java b/leetcode-algorithms/src/main/java/com/stevesun/solutions/SumRootToLeafNumbers.java
@@ -5,9 +5,24 @@
 import java.util.ArrayList;
 import java.util.List;
 
+/**Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
+
+ An example is the root-to-leaf path 1->2->3 which represents the number 123.
+
+ Find the total sum of all root-to-leaf numbers.
+
+ For example,
+
+ 1
+ / \
+ 2   3
+ The root-to-leaf path 1->2 represents the number 12.
+ The root-to-leaf path 1->3 represents the number 13.
+
+ Return the sum = 12 + 13 = 25.
+
+ */
 public class SumRootToLeafNumbers {
-    //it could overflow when the tree is very deep/large, so definitely use long
-    //let's assume it won't overflow first
     public int sumNumbers(TreeNode root) {
         if(root == null) return 0;
         List<Integer> allNumbers = new ArrayList();
