题解 | #进制转换#

#include<iostream>
#include<vector>
#include<stack>
using namespace std;


//此题整数多达30位，无法用整型存储
//需要重新写一个函数来实现除法
//过程与平时在纸上实现除法的过程一样
/*
* 1 即把字符串从高到低逐位除以除数。
* 如果某位不能整除，那么就保留它除以除数的余数
* 余数乘以10后和低一位一起进行处理
* 2 这种做法可能会前置多余的0
* 这时只需取首个非0位之后的字符串
*/
//取模过程还是一样的，对最低位取模就可以了

void showV(vector<int>& v) {
    for (int i = 0; i < v.size(); i++) {
        printf("%d", v[i]);
    }
    printf("\n");
}

//如果传进去0或者1，返回的就是个空vector
vector<int>& div(vector<int>& v, int x) {
    int r = 0; //余数 remainder
    int q = 0; // 商 quotient
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        q = (10 * r + *it) / x;
        r = (10 * r + *it) % x;
        *it = q;
        //showV(v);
    }
    vector<int>::iterator it = v.begin();
    if (v.size() == 1 && *it == 0) {
        v.erase(it);
    } else if (v.size() != 1) {
        while (*it == 0) {
            v.erase(it); //erase之后后面所有元素都会先前移动
            //非常隐蔽的错误，120563/2=60281
            //变成了6281,发现除出来是对的，erase给搞错了
            //但是这样的时间复杂度可能会很高
            //不如string取第1个非0的开始当字串
        }
    }
    return v;
} //注意!! 函数返回值为引用时，必须确保返回值在函数结束后存在
//不能采用函数内部的局部变量作为返回值

//取字串等操作 string比vector好用！string很多函数参数可以用int, vector不行



int main() {
    string str;
    while (cin >> str) {
        vector<int> v;
        stack<int> binary;
        for (int i = 0; i < str.length(); i++) {
            v.push_back(str[i] - '0');
        }
        while (!v.empty()) {
            binary.push(v[v.size() - 1] % 2);
            div(v, 2);
            //showV(v);
        }
        if (binary.empty()) {
            binary.push(0);
        }
        int s = binary.size();
        //for(int i=0;i<binary.size();i++){   //不能一边pop, 一边以binary.size()作为界限
        for (int i = 0; i < s; i++) {
            printf("%d", binary.top());
            binary.pop();
        }
        printf("\n");
    }
    return 0;
}

Caution：

//for(int i=0;i<binary.size();i++){ //不能一边pop, 一边以binary.size()作为界限

for (int i = 0; i < s; i++) {

printf("%d", binary.top());

binary.pop();

}

1. //vector.erase之后后面所有元素都会向前移动，时间复杂度可能会高
2. 函数返回值为引用时，必须确保返回值在函数结束后存在，不能采用函数内部的局部变量作为返回值
3. vector很多函数的参数都是vector<type>::iterator，不如string很多用int就可以