leecode反转系列

Posted on   |   In   |  

各种反转，反转整数，按二进制位反转

Reverse Interger

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

给出提示的是，如果反转的数溢出了，就返回0；

思路:注意是负数的情况，处理时取绝对值(注意哦，INT_MIN的绝对值可不是INT_MAX)
反转负数的时候有可能越界，所以需要一个long long类型来保存反转结果，在判断是否越界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int reverse(int x) {
        bool isPositive = true;
        if(x == INT_MIN) return 0;
        if(x < 0){
            isPositive = false;
            x = -x;
        }
        int mod = 0;
        long res = 0;
        
        while(x != 0){
            mod = x % 10;
            res = res * 10 + mod;
            x /=10;
        }
        if(res > INT_MAX)   return 0;
        return isPositive?res:-res;
    }
};

简化代码:

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int reverse(int x) {
        long res = 0;
        for(; x!= 0; x /= 10)
            res = res*10 + x % 10;
        
        return res > INT_MAX || res <INT_MIN ? 0: (int)res;
    }
};

Reverse Bits

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).

此处由于是无符号数，所以右移是最高位会补0；

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int reverse = 0;
        
        for(int i = 0; i < 32; i++){
            reverse = reverse<<1 | (n&1);
            n = n>>1;
        }
        return reverse;
    }
};

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n & 0xAAAAAAAA) >>1 ) | ((n & 0x55555555) <<1);
        n = ((n & 0xCCCCCCCC) >>2 ) | ((n & 0x33333333) <<2);
        n = ((n & 0xF0F0F0F0) >>4 ) | ((n & 0x0F0F0F0F) <<4);
        n = ((n & 0xFF00FF00) >>8 ) | ((n & 0x00FF00FF) <<8);
        n = ((n & 0xFFFF0000) >>16 ) |((n & 0x0000FFFF)<<16);
        return n;
    }
};