题目分析

1. 题目给出了我们一个数字
2. 我们要颠倒这个数字，以字符串形式逆序输出

方法一：转换为字符串

• 实现思路

  • 首先我们将输入的整数类型转换为字符串类型

  • 然后调用reverse函数来颠倒

  • 输出颠倒后的字符串

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;							// 以字符串格式输入
    reverse(s.begin(), s.end());		// reverse来倒序原有的字符串
    cout << s;
    return 0;
}

复杂度分析

• 时间复杂度：$O(lgn)O(lgn)$，reverse函数的开销与输入的数字位数有关，因此应该取以10为底的对数级别的代价
• 空间复杂度：$O(1)O(1)$，未引入其他额外空间开销

方法二：数学方法转换

• 实现思路
  • 我们通过对原数字取个位的操作来获得数字的最后一位，并立即输出
  • 然后将这个数字整除10
  • 循环前两步的操作，直到这个数字等于0为止
  • 这样最后的输出结果就是倒序的结果

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if(n == 0) cout<<0;
    while(n) {
        cout << n % 10;			// 取个位数字并输出
        n /= 10;				// 整除10
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(lgn)O(lgn)$，因为数据逐位取末位数字，每轮要通过余10来获取末位数字，时间代价和输入数字的位数相关，因此应该取以10为底的对数代价
• 空间复杂度：$O(1)O(1)$，未引入额外空间开销