7.翻转整数

题目

Reverse digits of an integer.

Example1:

1
x = 123, return 321

Example2: 

1
x = -123, return -321

分析

这是一道相当经典的算法题，题目本身不难，看你自己考虑的是否全面，需要考虑的有几个问题

  • 变换数字问题，是由int转化为int，溢出问题如何避免与检测？
  • 需要对整数的每一位进行提取，如何编写代码？

思路

面对上面的两个问题

  • 首先，溢出问题的解决我们可以用一个long long型的变量来存放翻转过程的数，最后检查如果输出的结果溢出(res > INT_MAX || res < INT_MIN），这边是我们滴水不漏版的答案。但是我们思考因为输入的x也是一个整型数，所以x的范围也应该在 -2147483648～2147483647 之间，那么x的第一位只能是1或者2，翻转之后res的最后一位只能是1或2，所以res只能是 2147483641 或 2147483642 都在int的范围内。但是它们对应的x为 1463847412 和 2463847412，后者超出了数值范围。所以当过程中res等于 214748364 时， 输入的x只能为 1463847412， 翻转后的结果为 2147483641，都在正确的范围内，所以不用check。这便是官方给出的精简版。
  • 无论是哪个版本，提取每一位的方法都是一样的，顺序是从低位往高位取，例如123456，我们先对他进行取余=6，提取出最后一位，再把123456整体除以10，将最后一位抹去，循环往复。

代码

滴水不漏版

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

9.判断回文数

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

`Example 1:

1
2
Input: 121
Output: true

Example 2:

1
2
3
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:
Coud you solve it without converting the integer to a string?

分析

首先只要是负数就一定不是回文数，可以首先排除；然后就是找第1位和对应的第n位，这里提供了一种思路就是首先用n次循环计算出位数，然后 $\text{div}=10^n$，设立这个数的目的是为了找到前向位，后向位我们通过上面的翻转整数（取余）很快得到。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int div = 1;
        while (x / div >= 10) 
            div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
};

个人总结

这两道题都是很经典的入门题，涉及到的只是不多

  1. int类型溢出判断
  2. 整数得到每一位数

这两个是很基础的知识，以后可能会经常用到，今天两道题不涉及特殊的数据结构，所以可说的不多，继续努力吧。感觉easy题以后要是明白的话没必要在往博客上写了。