set matrix zero in place

xiaoningning · xiaoningning · commit a6b4d09e2bce · 2012-07-14T18:58:09.000-07:00
diff --git a/PuzzleCoding/src/DecodeNumber.java b/PuzzleCoding/src/DecodeNumber.java
@@ -34,7 +34,10 @@ public static void decodeNumber(String s) {
         for (int i = 1; i < len; i++) {
             char p = s.charAt(i - 1);
             char c = s.charAt(i);
-            if (p == '1' || (p == '2' && c <= '6') || (p == '0' && c != '0' && ways[i-1]==0)) {
+            if (p == '0' && c != '0' && ways[i-1]==0){
+                ways[i-1] =1;
+            }
+            if (p == '1' || (p == '2' && c <= '6') ) {
                 ways[i] = ways[i - 1] *2;
             } else
                 ways[i] = ways[i - 1];
diff --git a/PuzzleCoding/src/SetMartixZero.java b/PuzzleCoding/src/SetMartixZero.java
@@ -0,0 +1,83 @@
+import java.util.Arrays;
+
+/**
+ * Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
+ * <p/>
+ * Follow up:
+ * Did you use extra space?
+ * A straight forward solution using O(mn) space is probably a bad idea.
+ * A simple improvement uses O(m + n) space, but still not the best solution.
+ * Could you devise a constant space solution?
+ */
+public class SetMartixZero {
+    public static void main(String[] args) {
+        int[][] matrix = new int[][]{
+                {1, 2, 3, 5},
+                {2, 4, 0, 1},
+                {2, 4, 2, 1},
+                {0, 4, 2, 1},
+        };
+
+        System.out.println(Arrays.deepToString(matrix));
+        setMatrixZero(matrix);
+        System.out.println(Arrays.deepToString(matrix));
+
+    }
+
+    // do it in place
+    // use first row/col to record zero flag
+    public static void setMatrixZero(int[][] m) {
+        if (m.length <= 0) return;
+        int row = m.length;
+        int col = m[0].length;
+
+        boolean firstRowZero = false;
+        boolean firstColZero = false;
+
+        for (int j = 0; j < col; j++) {
+            if (m[0][j] == 0) {
+                firstRowZero = true;
+                break;
+            }
+        }
+        for (int i = 0; i < row; i++) {
+            if (m[i][0] == 0) {
+                firstColZero = true;
+                break;
+            }
+        }
+
+        for (int i = 1; i < row; i++) {
+            for (int j = 1; j < col; j++) {
+                if (m[i][j] == 0) {
+                    // set zero flag on the first row/col
+                    m[0][j] = 0;
+                    m[i][0] = 0;
+                }
+            }
+        }
+
+        // set zero based on zero flag
+        for (int i = 1; i < row; i++) {
+            for (int j = 1; j < col; j++) {
+                if (m[0][j] == 0 || m[i][0] == 0) {
+                    m[i][j] = 0;
+                }
+            }
+        }
+
+        if (firstRowZero) {
+            for (int j = 0; j < col; j++) {
+                m[0][j] = 0;
+            }
+        }
+
+        if (firstColZero) {
+            for (int i = 0; i < col; i++) {
+                m[i][0] = 0;
+            }
+        }
+
+        return;
+    }
+}
