bit oepration to generategray code

xiaoningning · xiaoningning · commit cdd3d5835758 · 2012-07-22T12:35:53.000-07:00
diff --git a/PuzzleCoding/src/AddBinary.java b/PuzzleCoding/src/AddBinary.java
@@ -30,7 +30,7 @@ public static int string2Integer(String s, int code) {
 
     public static String toBinary(int integer) {
         StringBuilder builder = new StringBuilder();
-        int temp = 0;
+        int temp;
         while (integer > 0) {
             temp = integer;
             integer = (temp >> 1);
diff --git a/PuzzleCoding/src/GrayCode.java b/PuzzleCoding/src/GrayCode.java
@@ -1,3 +1,5 @@
+import java.util.Arrays;
+
 /**
  * Created with IntelliJ IDEA.
  * Print the N-bit binary reflected Gray code using recursion.
@@ -16,6 +18,7 @@ public class GrayCode {
     public static void main(String[] args) {
         int N = 3;
         grayCode(N, new boolean[N]);
+        grayCode(N);
     }
 
     public static void grayCode(int n, boolean[] show) {
@@ -54,4 +57,39 @@ public static void showCode(boolean[] show) {
         // System.out.println(Integer.parseInt(code, 2));
     }
 
+    /*
+    **	The BinaryToGray method is base on the bit of gray cod loop occur: 0,1,1,0
+    **	Hence, we could calculate each bits of gray code by mod 4 to find the matching value
+    **
+    **	However, after search on the website, the convert formula is just simply as (i>>1) ^ i.
+    **	The ith bit is equal to ith bit plus (i+1)th bit with no carry.
+    */
+
+    public static String[] grayCode(int n) {
+        int[] code = new int[1 << n];
+        String[] codeString = new String[1 << n];
+
+        for (int i = 0; i < (1 << n); i++) {
+            code[i] = (i >> 1) ^ i;
+            // codeString[i] = Integer.toBinaryString((i >> 1) ^ i);
+            codeString[i] = toBinaryString((i >> 1) ^ i);
+        }
+
+        System.out.println(Arrays.toString(codeString));
+        System.out.println(Arrays.toString(code));
+
+        return codeString;
+    }
+
+    public static String toBinaryString(int integer) {
+        StringBuilder builder = new StringBuilder();
+        int temp;
+        while (integer > 0) {
+            temp = integer;
+            integer = (temp >> 1);
+            builder.append(temp % 2);
+        }
+        return builder.reverse().toString();
+    }
+
 }
diff --git a/PuzzleCoding/src/IsBSTPostOrder.java b/PuzzleCoding/src/IsBSTPostOrder.java
@@ -4,16 +4,23 @@
  */
 public class IsBSTPostOrder {
     public static void main(String[] args) {
-        int[] a = new int[]{0, 2, 1, 4, 5, 3};
+        int[] a = new int[]{0, 2, 1, 9, 12, 10, 6};
         boolean postOrder = isBstPostOrder(a, 0, a.length - 1);
         System.out.println(postOrder);
     }
 
     public static boolean isBstPostOrder(int[] a, int left, int right) {
         if (left > right)
             return false;
-        if (right - left == 1 || right == left)
+        if ( right == left)
             return true;
+        if(right - left == 1){
+            if(a[left] < a[right])
+                return false;
+            else
+                return true;
+        }
+
         int i = left;
         while (a[i] < a[right])
             i++;
