LeetCode Reverse Integer & Palindrome Number 题解

发表于 | 分类于 | 阅读次数:
字数统计: 518 字

LeetCode 题解

Reverse Integer

题目的意思就是翻转一个整数（其中可能是负数），一开始想到的方案是分正数和负数进行讨论：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int reverse(int x) {
        int cnt=0,negative_flag = 0;
        long long res =0;
        if(x<0)
        {
            x = -x;
            negative_flag = 1;
        }
        while(x>0)
        {
            res = res*10 + x%10;
            x/=10;
        }
        if(res>INT_MAX) return 0;
        if(negative_flag)
            return -res;
        else
            return res;
    }
};

其实是可以不用处理负数的问题的，更加简洁的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int reverse(int x) {
        int res =0;
        while(x)
        {
            if(abs(res)>INT_MAX/10) return 0;
            res = res*10 + x%10;
            x/=10;
        }
        return res;
    }
};

其中涉及到C++的负数的除法和取余问题，在后面会讲到

Palindrome Number

判断一个数是不是回文数，不可以使用额外的空间

一开始考虑将数进行翻转然后确定是否相等进行判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        int y = x,res = 0;
        if(x<0) return false;
        while(y)
        {
            res = res *10 + y%10;
            y/=10;
        }
        if(res == x)
            return true ;
        else
            return false ;
    }
};

结果：
Your runtime beats 22.66 % of cpp submissions

另外一种方案就是先计算出这个数的位数，然后从两边开始判断，但是好像也没有优化多少。
还有可以通过转化为String进行判断，一开始以为这种方案不满足题目的“不可以使用额外的空间”的要求，但是还是能够通过，只不过时间比前面两种方案多很多。

C++负数的除法和取余问题

C++ 的除法和取余问题：（C++11标准）

  • 商一律向0取整（即直接切除小数部分）
  • 对于m/n，如果m和n的符号相同，则结果为正
  • m%n不等于0，则其结果的符号的m相同
  • (-m)/n = m/(-n) = -(m/n) ； m%(-n) = m%n ； (-m)%n = -(m%n)

示例：

  • (-21)%(-8) = (-21)%8 = - (21%8) = -5
  • -21/-8 = 21/8 = 2
  • 21%(-5) = 21%5 = 1
  • 21/(-5) = -(21/5) = -4