题意整理。

  • 给定一个10进制整数。
  • 将其转换为16进制字符串。

方法一（循环）

1.解题思路

  • 只要原数字不为0，就一直做除16的处理。每次产生的余数拼接起来，即是最终的16进制字符串
  • 由于余数是从低位产生的，所以拼接的时候，应该从前面拼接。

图解展示： alt

2.代码实现

#include <iostream>
#include <string>
using namespace std;

string toHexString(int n);

int main() {

    int n;
    cin >> n;

    string hexStr = toHexString(n);
    cout << hexStr << endl;

    return 0;
}

string toHexString(int n) {
    //定义字符串变量，用于记录最终结果
    string res="";
    while(n!=0){
        //计算当前对16取余的结果
        int mod=n%16;
        //如果是0-9，则对应字符'0'-'9'
        if(mod>=0&&mod<=9){
            char c=mod+'0';
            //将字符加在res前面
            res=c+res;
        }
        //如果是10-15，则对应字符'A'-'F'
        else{
            char c=mod-10+'A';
            //将字符加在res前面
            res=c+res;
        }
        n=n/16;
    }
    return res;
}

3.复杂度分析

  • 时间复杂度：每次n会缩小16倍，所以循环执行log16nlog_{16}n次，所以时间复杂度为O(log16n)O(log_{16}n)。
  • 空间复杂度：不需要额外的空间，所以空间复杂度为O(1)O(1)。