The most verbose code ever

idf · idf · commit 174ec3453263 · 2015-01-27T00:04:40.000+08:00
diff --git a/src/MaximalRectangle/Solution.java b/src/MaximalRectangle/Solution.java
@@ -84,9 +84,6 @@ public int maximalRectangle_error(char[][] matrix) {
                 for(int k=i; k>i-vertical[i+1][j+1]; k--)
                     length = Math.min(length, horizontal[k+1][j+1]);
                 maxa = Math.max(maxa, Math.max(horizontal[i+1][j+1]*height, vertical[i+1][j+1]*length));  // logic flaw
-                if(maxa==12) {
-                    System.out.println(maxa);
-                }
             }
 
         return maxa;
diff --git a/src/Triangle/Solution.java b/src/Triangle/Solution.java
@@ -0,0 +1,49 @@
+package Triangle;
+
+import java.util.List;
+import java.util.stream.Collectors;
+
+/**
+ * User: Danyang
+ * Date: 1/26/2015
+ * Time: 23:52
+ *
+ * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row
+ * below.
+
+ For example, given the following triangle
+ [
+ [2],
+ [3,4],
+ [6,5,7],
+ [4,1,8,3]
+ ]
+ The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
+
+ Note:
+ Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
+ */
+public class Solution {
+    /**
+     * dp
+     * let f[i][j] represent the minimal path sum from bottom to i, j
+     * f[i][j] = min(f[i+1][j], f[i+1][j+1])+t[i][j]
+     * @param triangle
+     * @return
+     */
+    public int minimumTotal(List<List<Integer>> triangle) {
+        List<List<Integer>> f = triangle.stream()
+                .map(e -> e.stream().map(e2->0).collect(Collectors.toList()))
+                .collect(Collectors.toList());
+        for(int i=0; i<triangle.get(triangle.size()-1).size(); i++) {
+            f.get(f.size()-1).set(i, triangle.get(triangle.size()-1).get(i));
+        }
+        for(int i=triangle.size()-2; i>-1; i--) {
+            for(int j=0; j<triangle.get(i).size(); j++) {
+                int min = Math.min(f.get(i+1).get(j), f.get(i+1).get(j+1))+triangle.get(i).get(j);
+                f.get(i).set(j, min);
+            }
+        }
+        return f.get(0).get(0);
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -84,9 +84,6 @@ public int maximalRectangle_error(char[][] matrix) {`
`84`	`84`	`for(int k=i; k>i-vertical[i+1][j+1]; k--)`
`85`	`85`	`length = Math.min(length, horizontal[k+1][j+1]);`
`86`	`86`	`maxa = Math.max(maxa, Math.max(horizontal[i+1][j+1]height, vertical[i+1][j+1]length)); // logic flaw`
`87`		`- if(maxa==12) {`
`88`		`- System.out.println(maxa);`
`89`		`- }`
`90`	`87`	`}`
`91`	`88`
`92`	`89`	`return maxa;`