【世界聚看点】复试算法练习Day10
发布时间：2023-01-17 20:40:25
来源：哔哩哔哩
复试算法练习Day10
题目描述
(资料图)
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
数据范围： 0≤n≤2^30−1
输入描述
输入一个int型整数
输出描述
将这个整数以字符串的形式逆序输出
示例1
输入：1516000
输出：0006151
示例2
输入：0
输出：0
思路
思路1：将每次模10 的结果放入一个变量，并每次循环将变量乘10，使位数每次高一位。一直去完到最后输出即可获得结果
思路2：可以构建递归函数实现逆序输出，采用构建一个swap函数交换数据，如果整数在0-9中间，直接输出结果，如果这个整数为多个位数，则利用对10取余之后，对于x/10的整数继续递归处理，直到递归结束之后则得到逆向输出的结果
具体实现
//思路1
//逆序输出数字
//但这个程序有缺陷
//不能输出最后的0，例如3320，会输出233，
//会省略掉一个末尾的0
#include<stdio.h>
int main() {
int x;
scanf("%d",&x);
int digit;
int ret = 0;
while(x>0)
{
digit = x%10;
ret=ret*10+digit;
printf("x=%d,digit=%d,ret=%d\n",x,digit,ret);
x/=10;
}
printf("%d ", ret);
return 0 ;
}
//思路二，逆序输出
//构建一个swap函数交换数据
#include<stdio.h>
//如果整数为一位，直接输出
//如果整数为多位则利用对10取余之后
//递归继续处理x/10的整数继续运算
//直到递归结束
int Swap(int x){
if (0<x&&x<10) printf("%d",x);
else{
printf("%d", x%10);
return Swap(x / 10);
}
}
//输入整数num并测试给出结果
int main(){
int num;
scanf("%d", &num);
Swap(num);
return 0;
}
时间复杂度
思路1：对于x的位数遍历了n次，故时间复杂度为O(n)
思路2：由于采用了递归函数，每一次只遍历一次取余给出结果，多次递归最后输出结果，所以其时间复杂度为O(1)
小结
通过利用模10的结果，每次循环给出逆序输出结果，或者采用递归算法，每次模10后给出一位输出后继续求num/10的结果取模，多次递归即可给出结果。重点是构建swap()函数来反向输出整数结果，思路一对于有0的部分反向输出的结果可能有所偏差，但是取余递归的结果不会出差错。所以可以多采用不同的方式多试试，可能会得到更好的结果，但是递归算法计算时间较长，如果数据量大一般不采用。
