Reverse Integer
Question
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Analysis
越界判断：
tmp加上tail后看是否还能变回原来的数字，不可直接利用int型的加和来判断越界（tmp*10+tail>Integer.MAX_VALUE）
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class
public int reverse (int x)
boolean flag=false ;
if (x<0 ) flag=true ;
x=Math.abs(x);
int res=0 ;
int tmp=0 ;
while (x!=0 ){
int tail=x%10 ;
tmp=tmp*10 +tail;
if ((tmp-tail)/10 !=res)
return 0 ;
res=tmp;
x=x/10 ;
}
if (flag) return -res;
return res;
}
}
Reverse Bit
Question
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100 ), return 964176192 (represented in binary as 00111001011110000010100101000000 ).
Analysis
每次取出数字n的最后一位给res，res在前31位的时候不断左移
优化后，将32-bit分为四段，利用map来保存倒转的结果
LeetCode Discuss Answer
中文参考
Code
Basic Version
1
2
3
4
5
6
7
8
9
10
11
12
13
public class
public int reverseBits (int n)
int res=0 ;
for (int i=0 ;i<32 ;i++){
res+=n&1 ;
n>>>=1 ;
if (i<31 )
res<<=1 ;
}
return res;
}
}
Optimized Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class
public final Map<Byte,Integer> cache=new HashMap<Byte,Integer>();
public int reverseBits (int n)
int res=0 ;
byte [] bytes=new byte [4 ];
for (int i=0 ;i<4 ;i++){
bytes[i]=(byte )((n>>>8 *i)&0xFF );
}
for (int j=0 ;j<4 ;j++){
int tmp=munipulation(bytes[j]);
res+=tmp;
if (j<3 )
res<<=8 ;
}
return res;
}
public int munipulation (Byte b)
Integer value=cache.get(b);
if (value!=null ){
return value;
}
value=0 ;
for (int i=0 ;i<8 ;i++){
value+=(b>>>i)&1 ;
if (i<7 )
value<<=1 ;
}
cache.put(b,value);
return value;
}
}
近期评论