leetcode刷题笔记：2和989这类数字一位一位相加的问题

通用模板

对于数字一位一位相加的问题，一般就是leetcode第2题链表的形式，和第989题数组的形式。参考leetcode上大佬的题解，会有一个通用的加法模板。

1
2
3
4
5
6
7
8
9
10
11
进位carry初始化为0
while ( A 没完 || B 没完 ){
    A 的当前位
    B 的当前位

    和 = A 的当前位 + B 的当前位 + 进位carry

    当前位 = 和 % 10;
    进位 = 和 / 10;
}
判断是否还有进位？

只要依靠这个模板，就能把这两道题很轻松的写出来。

989.数组形式的整数加法

题目

https://leetcode.cn/problems/add-to-array-form-of-integer/

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。

给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：
输入：num = [2,7,4], k = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：
输入：num = [2,1,5], k = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

代码

按上文提供的模板，写这道题是比较容易的，因为数组本身是可以随机访问的，我们从后往前遍历数组，按位与k的当前位相加就可以了。

注意，使用vector做返回值时，我们应该采用先尾插最后逆置的方式，效率会远高于每次都头插。因为vector的头插涉及到了其他元素的移动。

当然，你也可以选择链表来进行头插，最终再转成vector返回。

这里面要注意的是，虽然while的判断条件中已经有了判断，但是两个判断条件是通过||或连接的，可能会出现数组已经结束了，但是k还有位数（或反之）的情况，在操作a和b的时候一定要先进行判断再赋值。

当然，也可以选择用&&与链接，并在while之后单独处理数组或k剩下的数。

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
class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> retV;
        int i = num.size() - 1;
        int carry = 0; // 进位
        // 有一个不为0就需要继续加
        while (i >= 0 || k != 0) {
            // 可能有一个已经结束了，需要判断
            int a = i >= 0 ? num[i] : 0;
            int b = k != 0 ? k % 10 : 0;

            int sum = a + b + carry;
            int cur = sum % 10;          // 当前位
            carry = (sum >= 10) ? 1 : 0; // 如果超过10了需要进位
            // 插入数组
            retV.push_back(cur);
            // 走下一位去
            i--;
            k /= 10;
        }
        // 还有进位，需要再插入一个
        if (carry != 0) {
            retV.push_back(1);
        }
        // 注意，我们插入是尾插（vector头插效率很低），需要逆置
        reverse(retV.begin(), retV.end());
        return retV;
    }
};

image.png

2.两数相加

https://leetcode.cn/problems/add-two-numbers/description/

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
5
6
7
8
9
10
11
12
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

代码

这道题虽然给的是链表，无法随机访问，但是链表是逆序存放的数字，本就符合我们从低位往高位相加的思路。

基本代码和上文一致，当某个链表结束之后，就将其视作0继续操作。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 有一个为空的时候可以直接返回另外一个
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }

        ListNode* phead = new ListNode;
        ListNode* cur = phead;

        int carry = 0; // 进位制
        ListNode* left = l1,*right = l2;
        // 有一个不为空就需要继续
        while(left != nullptr || right !=nullptr)
        {
            int a = left != nullptr?left->val:0;
            int b = right != nullptr?right->val:0;

            int sum = a+b+carry;
            int val = sum % 10; // 当前值
            carry = sum>=10?1:0;
            // 注意，题目要求的是按相同的方式（数字逆序存放）来返回一个链表
            // 所以我们需要进行尾插操作
            cur->next = new ListNode(val);
            cur = cur->next;
            // 去下一位
            if(left != nullptr){    
                left=left->next;
            }
            if(right != nullptr){
                right=right->next;
            }
        }
        // 还有值，需要再尾插一个。
        if(carry!=0){
            cur->next = new ListNode(1);
        }
        return phead->next;
    }
};

备注：上面的代码中，phead指针出现内存泄漏了，但是写OJ的时候并不关心内存泄漏问题。

image.png

165.比较版本号

题目

https://leetcode.cn/problems/compare-version-numbers/description/

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

1
2
3
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：
输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

提示：

1
2
3
4
1 <= version1.length, version2.length <= 500
version1 和 version2 仅包含数字和 '.'
version1 和 version2 都是 有效版本号
version1 和 version2 的所有修订号都可以存储在 32 位整数 中

代码

上文提到的累计相加的思路同样可以扩大到字符串比较的题目中。只要有一个没有结束就继续比较，直到两个字符串都结束或找到结果。

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
class Solution {
public:
    int compareVersion(string version1, string version2) {
        int left = 0, right = 0;
        while (left < version1.size() || right < version2.size()) {
            // version1求和
            int leftSum = 0;
            // 这里并不需要对前导0做任何判断，因为初始值就是0，前导0操作后还是0
            for (; left < version1.size() && version1[left] != '.'; left++) {
                leftSum = leftSum * 10 + (version1[left] - '0');
            }
            left++; // 跳过点

            // version2求和
            int rightSum = 0;
            for (; right < version2.size() && version2[right] != '.'; right++) {
                rightSum = rightSum * 10 + (version2[right] - '0');
            }
            right++; // 跳过点

            // 不相同就说明有一个大了，判断一下
            if (leftSum != rightSum) {
                return leftSum > rightSum ? 1 : -1;
            }
        }
        return 0;
    }
};

image.png

这道题的另外一个思路就是通过'.'字符将两个字符串切割出来，再依次比较版本号。但是那样会有更大的时间复杂度消耗，逻辑也不是很清晰，不如直接在循环内处理。