LeetCode

LeetCode-对大数的操作

当所处理的对象数值很大时，如(int)32634573563452724846734573，使用整型长整型，都会溢出，这种情况就要使用字符串代替数字。此方法处理大数问题。

两个知识点：

  1. 字符型的数字与其对应的ASCII值：

    char ‘0’ ‘1’ ‘2’ ‘3’ … ‘9’
    int 48 49 50 51 … 57

  2. char与对应int转换

    char->int: '3'-'0' = 3
    int->char: 3 +'0' = '3'

问题描述

给一个n位数，打印从1到最大的n位数。比如n=3，则打印1,2,3，...，998,999.

思路

当n为20，其对应的数值已经远远超过了计算机可以表示的范围，所以用字符串表示一个大数，并且实现中不能出现for循环，因为循环变量i随循环次数也会超出表示范围的。所以用while循环避免使用循环变量。

实现

下面的实现是有冗余的，只用addOne()或subtractOne()其一即可。当使用addOne()时，只要加一后的string不等于最大的n位数，就打印，后循环；当使用subtractOne()，初始string设为最大的n位数，while循环减一，只要这个string不是空，就打印，后循环。

当然两个函数可以配合使用，不过就多余了，但就当练习大数操作了。

一个string表示的大数加一操作如下。先在string首位插入一个’0‘占位，可能加一后要进位：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 初始化为“0”，循环中加到最大值
string addOne(string num) {
    if (num.size() == 0) return " ";
    num.insert(0, 1, '0');

    int carry = 1;
    int i = num.size() - 1;
    while (carry != 0) {
        int sum = (num[i] - '0') + carry;
        carry = sum / 10;
        int remainder = sum % 10;
        num[i] = remainder + '0';
        i--;
    }
    return num[0]=='0' ? num.substr(1) : num;
}

一个string表示的大数减一的实现如下：

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
// 初始化为最大值，循环中减到空
string subtractOne(string Nine) {
    bool borrow = false;
    int length = Nine.size();
    int iter = length - 2;
    int val;
    if (Nine[length - 1] == '0') {
        borrow = true;
        val = 10 + (Nine[length - 1] - '0') - 1;
        Nine[length - 1] = val + '0';
    }
    else Nine[length - 1] = Nine[length - 1] - '0' - 1 + '0';

    while ( borrow && iter >= 0) {
        if (Nine[iter] == '0') 
            val = 10 + (Nine[iter] - '0') - 1;
        else {
            borrow = false;
            val = (Nine[iter] - '0') - 1;
        }
        Nine[iter] = val + '0';
        iter--;
    }
    return Nine[0]=='0' ? Nine.substr(1) : Nine;
}

主函数，仔细分析，上述两个操作，使用一个就可以达到目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solution(int n) {
    if (n <= 0) return;

    // 最大的n位数 str
    string str;
    for (int i = 0; i < n; i++)
        str += '9';
    cout << str << endl;

    string preNum = addOne("0"); // 初始化为“0”，循环中加到最大值
    string isZero = subtractOne(str); // 初始化为最大值，循环中减到空

    while (isZero != "") {
        cout << preNum << " ";
        preNum = addOne(preNum);
        isZero = subtractOne(isZero);
    }
    cout <<str<< endl;
    return;
}

敲黑板

  1. 体会subtractOne中的bool borrow = false;，表示向前借位否，
  2. 实现中总会用到知识点2.

415大数相加

依然使用到上述知识点2，思路直接，实现如下：

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
string addStrings(string num1, string num2) {
    int length1 = num1.size();
    int length2 = num2.size();

    if(length1 != length2){
        int diff = abs(length1-length2);
        length2 > length1 ? 
            num1.insert(0, diff, '0') :
            num2.insert(0, diff, '0');
    }
 
    int length = num1.size() + 1;
    string res(length,'0');

    int carry=0;
    for(int i=length-2; i>=0; i--){
        int sum = (num1[i]-'0') + (num2[i]-'0') + carry;
        carry = sum/10;
        int remainder = sum%10;

        res[i+1] = remainder + '0';
    }
    if (carry) res[0] = carry + '0';

    return res[0]=='0' ? res.substr(1) : res;
}