decode number

xiaoningning · xiaoningning · commit 660340fccfef · 2012-07-14T14:31:18.000-07:00
diff --git a/PuzzleCoding/src/DecodeNumber.java b/PuzzleCoding/src/DecodeNumber.java
@@ -0,0 +1,44 @@
+/**
+ * A message containing letters from A-Z is being encoded to numbers using the following mapping:
+ * <p/>
+ * 'A' -> 1
+ * 'B' -> 2
+ * ...
+ * 'Z' -> 26
+ * Given an encoded message containing digits, determine the total number of ways to decode it.
+ * <p/>
+ * For example,
+ * Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
+ * <p/>
+ * The number of ways decoding "12" is 2.
+ */
+public class DecodeNumber {
+    public static void main(String[] args) {
+        String s1 = "11";
+        String s2 = "2019";
+        decodeNumber(s1);
+        decodeNumber(s2);
+
+    }
+
+    public static void decodeNumber(String s) {
+        int len = s.length();
+        for (int i = 0; i < len; i++) {
+            if (!((s.charAt(i) - '0') <= 9) && !(('9' - s.charAt(i)) >= 0)) {
+                System.out.println(s + " is not number.");
+                return;
+            }
+        }
+        int[] ways = new int[len];
+        ways[0] = (s.charAt(0) == '0') ? 0 : 1;
+        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)) {
+                ways[i] = ways[i - 1] *2;
+            } else
+                ways[i] = ways[i - 1];
+        }
+        System.out.println(s + ":" + ways[len - 1]);
+    }
+}
diff --git a/PuzzleCoding/src/JumpGame.java b/PuzzleCoding/src/JumpGame.java
@@ -21,10 +21,10 @@ public static void main(String[] args) {
     public static void jumpGame(int[] a) {
         if (a.length == 0) return;
 
-        int[] preStep = new int[a.length];
+        int[] previousStep = new int[a.length];
 
-        for (int i = 0; i < preStep.length; i++)
-            preStep[i] = -1;
+        for (int i = 0; i < previousStep.length; i++)
+            previousStep[i] = -1;
 
         boolean reachEnd = false;
         int furthest = a[0];
@@ -33,11 +33,11 @@ public static void jumpGame(int[] a) {
             furthest = Math.max(furthest, a[i] + i);
             for (int j = 0; j <= furthest; j++) {
                 if (j < a.length) {
-                    if (preStep[j] == -1)
-                        preStep[j] = i;
+                    if (previousStep[j] == -1)
+                        previousStep[j] = i;
                     else {
-                        if (preStep[j] > i)
-                            preStep[j] = i;
+                        if (previousStep[j] > i)
+                            previousStep[j] = i;
                     }
                 }
             }
@@ -54,7 +54,7 @@ public static void jumpGame(int[] a) {
             int end = a.length - 1;
             while (end != 0) {
                 System.out.print(a[end] +"->");
-                end = preStep[end];
+                end = previousStep[end];
             }
             System.out.print(a[end]);
             System.out.println();
diff --git a/PuzzleCoding/src/TreeLeafPath.java b/PuzzleCoding/src/TreeLeafPath.java
@@ -66,6 +66,7 @@ public static void leafPath(TreeLeafPath node, Stack<TreeLeafPath> stack) {
 
     }
 
+
     public static void main(String[] args) {
 
         TreeLeafPath root = new TreeLeafPath(12);
@@ -91,5 +92,7 @@ public static void main(String[] args) {
 
         Stack<TreeLeafPath> stack = new Stack<TreeLeafPath>();
         leafPath(root, stack);
+        System.out.println();
+
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -66,6 +66,7 @@ public static void leafPath(TreeLeafPath node, Stack<TreeLeafPath> stack) {`
`66`	`66`
`67`	`67`	`}`
`68`	`68`
	`69`	`+`
`69`	`70`	`public static void main(String[] args) {`
`70`	`71`
`71`	`72`	`TreeLeafPath root = new TreeLeafPath(12);`
`@@ -91,5 +92,7 @@ public static void main(String[] args) {`
`91`	`92`
`92`	`93`	`Stack<TreeLeafPath> stack = new Stack<TreeLeafPath>();`
`93`	`94`	`leafPath(root, stack);`
	`95`	`+ System.out.println();`
	`96`	`+`
`94`	`97`	`}`
`95`	`98`	`}`