Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Solution: we can solve this problem by starting from an example. Assume n=3, we have

000 - 0

001 - 1

011 - 3

010 - 2

110 - 6

111 - 7

101 - 5

100 - 4

The actual sequence of integers is,

000 - 0

001 - 1

010 - 2

011 - 3

100 - 4

101 - 5

110 - 6

111 - 7

By comparing them we find that, the highest bit does not change. Actually, there is a magic to generate the gray code.

http://en.wikipedia.org/wiki/Gray_code

Java语言: GrayCode

01 public ArrayList<Integer> grayCode(int n) {
02     ArrayList<Integer> results=new ArrayList<Integer>();
03     int totalNum=1<<n;
04     for(int i=0;i<totalNum;i++)
05     {
06         int number=i^(i>>1);
07         results.add(number);
08     }
09     return results;
10 }

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Hint: simulate the process just as you are doing decimal division by hand.

01 public int divide(int dividend, int divisor) {
02    long dividend_long=dividend;
03    long divisor_long=divisor;
04    boolean isNegative=false;
05  
06    if(dividend_long<0)
07    {
08        isNegative=true;
09        dividend_long=-dividend_long;
10    }
11  
12    if(divisor_long<0)
13    {
14        isNegative=!isNegative;
15        divisor_long=-divisor_long;
16    }
17  
18    int quotient=0;      
19    while(dividend_long>=divisor_long)
20    {
21        long sum=divisor_long;
22        int digit=1;
23        while((sum+sum)<=dividend_long)
24        {
25            sum+=sum;
26            digit<<=1;
27        }
28        quotient+=digit;
29        dividend_long-=sum;
30    }
31  
32    if(isNegative)
33        quotient=-quotient;
34  
35    return quotient;
36 }

Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Hint: for a set of N distinct numbers, the total number of subsets is 2^N. The idea is to use a boolean array used[], which has the same length with S, to indicate whether a number of S at position i is selected.

Solution 1: 

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {

02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        

03     if(S.length==0)

04         return results;

05   

06     //use a boolean array to indicate whether a number is selected

07     boolean [] used =new boolean [S.length];

08   

09     //first sort S, so that outputs are in correct order

10     Arrays.sort(S);

11     findSubsets(used, 0, S, results);

12     return results;

13 }

14 public void findSubsets(boolean [] used, int pos, int [] S, ArrayList<ArrayList<Integer>> results)

15 {

16     //reach the last position, output our selection

17     if(pos==S.length)

18     {

19         ArrayList<Integer> out =new ArrayList<Integer>();

20         for(int i=0;i<used.length;i++)

21         {

22             if(used[i])

23             {

24                 out.add(S[i]);

25             }

26         }

27         results.add(out);

28         return;

29     }

30   

31     //each position can be false or true,

32     //indicating whether the number at this position is selected or not

33     //then handle the next position

34     used[pos]=false;

35     findSubsets(used, pos+1, S, results);

36   

37     used[pos]=true;

38     findSubsets(used, pos+1, S, results);

39 }

Solution 2:

Instead of using an additional boolean array to store the information of which numbers are selected, we can use an integer to do so. In this manner, we pre-calculate how many subsets we will have in total, say, N. Then we use number 0 to N-1 to represent each subset. For example, we use 0, 1, 2, 3 to represent the subsets of 2 numbers, i.e., 00, 01, 10, 11. This is an iterative solution instead of a recursion one.

Java语言: Subsets

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        
03     Arrays.sort(S);              
04     //calculate total number of subsets        
05     for(int i=0;i<(1<<S.length);i++)
06     {
07         ArrayList<Integer> set=new ArrayList<Integer>();          
08         //convert this number representation into set
09         int number=i;          
10         for(int j=0;j<S.length;j++)
11         {              
12             if(number==0)
13                 break;
14             //the digit is 1, indicate the number is selected
15             if(number%2==1)
16             {
17                 set.add(S[j]);
18             }
19             //shift one bit to right, then check the next digit
20             number>>=1;
21         }
22         results.add(set);
23     }
24     return results;      
25 }