首页 > 代码库 > 【002】}链表或字符串模拟加法/加一/乘法

【002】}链表或字符串模拟加法/加一/乘法

2024-07-07 18:40:03   226人阅读

链表模拟加法/字符串模拟二进制加法/数组模拟加一操作/打印1到最大的n位数/字符串模拟乘法
============================================
 

Add Two Numbers

两个链表代表两个数字，每个结点的值都是一位数字，单链表逆序存放这两个数字，
构造出一个新的链表，代表这两个链表的和。
链表的尾插法，头结点dummy结点的运用，统一对prev指针的操作，
 
 C++ Code 
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
27
28
29
30
31
32
33
34
35
36
37
38
  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        /*头结点,dummy主要是为了保持prev的统一操作*/
        ListNode dummy(-1);
        int carry = 0;
        ListNode *prev = &dummy;
        ListNode *p1 = l1, *p2 = l2;
        while(p1 != NULL || p2 != NULL)
        {
            const int aCur = (p1 == NULL) ? 0 : p1->val;
            const int bCur = (p2 == NULL) ? 0 : p2->val;
            const int value = (aCur + bCur + carry) % 10;
            carry = (aCur + bCur + carry) / 10;
            /*尾插法*/
            prev->next = new ListNode(value);

            p1 = (p1 == NULL) ? NULL : p1->next;
            p2 = (p2 == NULL) ? NULL : p2->next;
            prev = prev->next;
        }
        if(carry > 0)
        {
            prev->next = new ListNode(carry);
        }
        return dummy.next;
    }
};

Add Binary

两个字符串模拟二进制的加法，二进制的字符串都是正序存放的，区别于链表模拟加法的题目，
    插入的时候，有头插法和尾插法。这里显然要用到头插法。
 
 C++ Code 
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
27
28
29
30
31
32
  
class Solution
{
public:
    string addBinary(string a, string b)
    {
        string result;
        const int n = a.size() > b.size() ? a.size() : b.size();
        /*反转过来，然后从左到右计算*/
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int carry = 0;
        for(int i = 0; i < n; ++i)
        {
            /*有一方，超过了长度就把这一方的设置为0*/
            const int aCur = i < a.size() ? a[i] - ‘0‘ : 0;
            const int bCur = i < b.size() ? b[i] - ‘0‘ : 0;
            /*余数*/
            const int val = (aCur + bCur + carry) % 2;
            /*进位*/
            carry = (aCur + bCur + carry) / 2;

            /*头插法*/
            result.insert(result.begin(), val + ‘0‘);
        }
        if(carry == 1)
        {
            result.insert(result.begin(), ‘1‘);
        }
        return result;
    }
};
 

Plus One

一个数组代表一个正序的数字，给这个数字做加一操作，返回加一后的结果数组。
carry在循环的外面初始化为true可以统一循环内部的操作。每次都得加上carry。
一旦没有进位这个加一的操作就可以结束了。因为，仅仅是一个加一的操作。
 
 C++ Code 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
  
class Solution
{
public:
    /*most significant digit 最高有效位在左边*/
    vector<int> plusOne(vector<int> &digits)
    {

        int length = digits.size();
        if(length == 0)
        {
            return digits;
        }
        /*让carry一开始等于true也就模拟了加一操作*/
        bool carry = true;
        int index = length - 1;
        while(carry && index >= 0)
        {
            /*加1，其实就是加上一个进位*/
            digits[index] += carry;
            if(digits[index] >= 10)
            {
                /*这种加1的进位，必然导致这个位置变成了0*/
                digits[index] = 0;
                carry = true;
                index--;
            }
            else
            {
                carry = false;
                break;
            }
        }
        if(carry)
        {
            /*如果循环到这里还有进位说明，需要添加一位*/
            /*begin的前面插入1*/
            digits.insert(digits.begin(), 1);
        }
        return digits;
    }
};
 
 
 
面试题12：打印1到最大的n位数
输入n，打印1到最大的n位十进制数
 

方法一，是模拟加法运算的过程，

 

 C++ Code 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
  
/*
 * 公共函数
 * 字符串number表示一个数字，数字有若干个0开头
 * 打印出这个数字，并且忽略开头的0
 */
void PrintNumber(char *number)
{
    bool isBeginning0 = true;
    int nLength = strlen(number);

    for(int i = 0; i < nLength; ++i)
    {
        if(isBeginning0 && number[i] != ‘0‘)
        {
            isBeginning0 = false;
        }
        if(!isBeginning0)
        {
            cout << number[i];
        }
    }
    cout << "\t";
}

/*
 * 字符串number表示一个数字，在number上增加1
 * 如果做加法溢出，则返回true，否者为false
 */
bool Increment(char *number)
{
    bool isOverflow = false;
    int carry = 0;
    int nLength = strlen(number);

    for(int i = nLength - 1; i >= 0; i --)
    {
        int nSum = number[i] - ‘0‘ + carry;
        //在循环里面对加1的位置进行了特殊判断
        if(i == nLength - 1)
        {
            nSum ++;
        }

        if(nSum >= 10)
        {
            if(i == 0)
            {
                isOverflow = true;
            }
            else
            {
                nSum -= 10;
                carry = 1;
                number[i] = ‘0‘ + nSum;
            }
        }
        else
        {
            number[i] = ‘0‘ + nSum;
            break;
        }
    }
    return isOverflow;
}

/*方法一*/
void Print1ToMaxOfNDigits_1(int n)
{
    if(n <= 0)
    {
        return ;
    }
    //字符串要为‘\0‘多分配一个空间
    char *number = new char[n + 1];
    memset(number, ‘0‘, n);
    number[n] = ‘\0‘;
    //每次都加一然后打印，打印是从1开始的~
    //溢出的时候就是循环终止的时候~
    while(!Increment(number))
    {
        PrintNumber(number);
    }
    delete []number;
}

 

方法二，是n位所有的十进制数其实就是n个从0到9的全排列，也就是说，我么把数字的每一个位都从0到9排列一遍，就得到了所有的十进制数，dfs的感觉

 

 C++ Code 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
  
/*
 * 公共函数
 * 字符串number表示一个数字，数字有若干个0开头
 * 打印出这个数字，并且忽略开头的0
 */
void PrintNumber(char *number)
{
    bool isBeginning0 = true;
    int nLength = strlen(number);

    for(int i = 0; i < nLength; ++i)
    {
        if(isBeginning0 && number[i] != ‘0‘)
        {
            isBeginning0 = false;
        }
        if(!isBeginning0)
        {
            cout << number[i];
        }
    }
    cout << "\t";
}

//这里的index在控制递归的层数，这里index显然不能大于数字位数范围
void Print1ToMaxOfNDigitsRecursively(char *number, int length, int index)
{
    if(index == length - 1)
    {
        PrintNumber(number);
        return ;
    }
    //每一个位置上都可能是0...9
    for(int i = 0; i < 10; ++i)
    {
        //index在递归的上一层已经放过数字了
        number[index + 1] = i + ‘0‘;
        Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
    }
}

/*方法二*/
void Print1ToMaxOfNDigits_2(int n)
{
    if(n <= 0)
    {
        return ;
    }
    char *number = new char[n + 1];
    number[n] = ‘\0‘;
    //每一个位置上都可能是0...9
    for(int i = 0; i < 10; ++i)
    {
        number[0] = i + ‘0‘;
        Print1ToMaxOfNDigitsRecursively(number, n, 0);
    }
    delete[] number;
}

 

 

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

把字符转换成数字，然后对这些数字做乘法，然后做进位操作，然后在转换成字符，把这些字符拼接成字符串

 
 C++ Code 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  
class Solution
{
public:
    string multiply(string num1, string num2)
    {
        /*因为仅仅说是非负的，可能为0*/
        if(num1 == "0" || num2 == "0")
        {
            return "0";
        }

        int l1 = num1.length(), l2 = num2.length();

        int *n1 = new int[l1];
        int *n2 = new int[l2];
        int *res = new int[l1 + l2];
        /*res数组必须初始化为0*/
        memset(res, 0, sizeof(int) * (l1 + l2));

        for(int i = 0; i < l1; ++i)
        {
            n1[i] = num1[i] - ‘0‘;
        }
        for(int i = 0; i < l2; ++i)
        {
            n2[i] = num2[i] - ‘0‘;
        }

        /*res暂时不存计算结果，为之后的进位操作做准备
         * 1 ... l1+l2-1
         */
        for(int i = 0; i < l1; ++i)
        {
            for (int j = 0; j < l2; ++j)
            {
                res[i + j + 1] += n1[i] * n2[j];
            }
        }
        /*个位数在最右边 (l1 - 1) + (l2 - 1) + 1*/
        string ss = "";
        for (int k = l1 + l2 - 1; k >= 0; --k)
        {
            if(k > 0)
            {
                res[k - 1] += res[k] / 10;
            }
            res[k] %= 10;
            /*头插法*/
            ss = char(res[k] + ‘0‘) + ss;
        }
        /*res[1] / 10进位给res[0]，这个进位可能为0*/
        ss = ss[0] == ‘0‘ ? ss.substr(1) : ss;
        return ss;
    }
};


联系
我们