反转类题目【LeetCode:7/190】

题目

7：整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

190：颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

解析

7：整数反转

这道题其实很容易想到的思路就是讲 数字转为字符串，接着逆反字符串，最后转回数字即可，实际上我也是这样实现的。但是通过字符串中转明显有性能问题，无论我如何优化，最后都停留在2ms，无法前进。看完官方解析之后也才明白，可以通过简单的数学运算就可以按十进制get和push，唯一需要注意的就是32位存储溢出的问题。

190：颠倒二进制位

有了第7道题的练手，这道题就很容易做了，直接按位取和按位push即可。

实现

7：整数反转

字符串思路实现，有性能问题。

/**
 * 思路：转成字符数组，逆反之后，再转回数字
 * 执行用时 : 2 ms , 在所有 java 提交中击败了 73.04% 的用户, 内存消耗击败80%的用户
 */
int reverse(int x) {
    // 转string
    String str = Integer.toString(x);
    int length = str.length();
    // 简单情况直接返回
    if (length == 1) {
        return x;
    }
    // 判断正负数，设定遍历起点位置
    int i = x < 0 ? 1 : 0;
    // 反转字符数组
    for (int y = 0, l = length - i ; y < l; y++) {
        n[y] = str.charAt(length - y - 1);
    }
    // 判断是否会溢出32位存储
    if (length - i == 10) {
        for (int q = 0; q < 10; q++) {
            if (n[q] < number[q]) {
                break;
            } else if (n[q] > number[q]) {
                return 0;
            }
        }
    }
    // 结果转换并返回
    int result = n[0] - 48;
    for (int p = 1; p < length - i; p++) {
        result = result * 10 + (n[p] - 48);
    }
    return i == 0 ? result : -result;
}

190：颠倒二进制位

/**
 * 1ms， 运行速度击败100%， 内存5.5%
 * @param n 32位输入
 * @return 颠倒后输入
 */
int reverseBits(int n) {
    int result = n;
    for (int i = 0; i < 31; i++) {
        result = result << 1;
        n = n >>> 1;
        result = result | n & 1;
    }
    return result;
}