面试中遇到的一个问题:整数反转

forest

这是在去老虎金融的时候,面试官问的一个问题,当时问题是这样的:
不使用系统原生的函数、方法,去实现将一个整数反转。比如 12345 翻转成 54321 。
不用想,肯定很多同学拿到这个问题以后,会跟我一样,动手就能写起来:

第一行代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int rev(int num) {
int res = 0;
int temp = num;
while (temp > 0) {
res = 10 * res + temp % 10;
temp /= 10;
}
return res;
}
int main(void) {
while(1) {
int a;
printf("输入要翻转的数 : ");
scanf("%d", &a);
printf("输入的%u翻转结果 : %u\n\n", a, rev(a));
}
return 0;
}

这个应该是每个刚学代码的人刚开始都会遇到的问题吧,有点编程思想的都能写的出来。

回忆基础

那么,现在我们来回忆一下int类型的知识。
int用于定义一个整形的变量,在16位编译器中,int类型占2个字节;在32位、64位的编译中,int类型占用4个字节。
由于1个字节占8位,即0000 0000,而对于int类型的整数来说,第一位是属于符号位,所以两种编译器中最大的值分别是2^15-1=327672^31-1=21474836473
如果用的是正整形,即unsigned int类型的话,第一位就不是符号位了,此时最大值分别是2^16-1=655352^32-1=4294967294
说这么些基础内容,回到上面的问题,就是为了说明一个问题,存在一些数,在反转以后会越界。下面举个例子:
在16位编译系统中,int类型最大的值是32767,如果就对这个最大的数进行反转,就成了76723,但是这个超过了int类型所能占有的最大值,就会出现越界的问题。
所以,考虑数值越界才是面试官问这个问题的关键点。

解决方案

当时在写的时候,想到了三个方法吧,都是很容易想到的方法:

  1. 在反转完成以后,再次进行一个wile循环,然后对反转前后的每位数值进行比较。
  2. 通过位移的手段,来比较反转前后的两个数。
  3. 利用栈的后进先出的特点,在反转的时候记录下每一位,然后去进行每一位的比较

优化方案

但是在写代码的时候,愣了一下,一想这样会有两次以上的循环,为什么不能再一次循环里就能做到呢?想了一下,然后就有了下面的思路:
看到上面的写法,整个反转的过程,核心的代码其实就是这两句:

1
2
res = 10 * res + temp % 10;
temp /= 10;

其中能够引起数值越界的是10*restemp%10,所以只需要在这两句上做下判断就能知道数值越界与否了。
下面上代码:

C写法

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
#include <stdio.h>
unsigned int rev(unsigned int num) {
unsigned int res = 0; // 反转以后的结果
unsigned int temp = num; // 存储原反转值的临时变量
while (temp > 0) {
if (res == res * 10 / 10) { // 先乘再除,如果越界的话,这个值肯定会因为越界有所改变
res = 10 * res + temp % 10;
if (res % 10 != temp % 10) { // 如果有越界的话,最后的一位数也会有改变,所以需要做一个判断
printf("越界 - ");
}
temp /= 10;
printf("current --->%d\n", res);
} else {
printf("越界 = \n");
break;
}
}
return res;
}
int main(void) {
while(1) {
unsigned int a;
printf("输入要翻转的数 : ");
scanf("%u", &a);
printf("输入的%u翻转结果 : %u\n\n", a, rev(a));
}
return 0;
}

Python写法

由于Python底层的处理,整型值可以很大,所以在python中不会遇到越界的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# coding: utf-8
def rev(num):
res = 0
temp = num
while temp > 0:
if res == res * 10 / 10:
res = 10 * res + temp % 10
if res % 10 != temp % 10: print('不相等,数值越界了')
temp /= 10
else: print('不相等,数值越界了')
return res
if __name__ == '__main__':
while True: print(rev(input('num: ')))

结尾

在阿里面试的时候,面试官同样的问了一个斐波那契的问题,最后的要点还是数值越界的问题。
现在能想到的好点的方法就是这个了吧,如果还有别的好的方法的话,敬请留言。
写这个呢,不会说是多么难的算法问题,而是想说,在面试的过程中,不能将面试官的问题想的太过于简单,而往往这些简单的东西往往能体现个人对于基础知识的把握和对细节的考虑,也能让面试官对你增加好感。