刷爆力扣之数组形式的整数加法

刷爆力扣之数组形式的整数加法

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈
今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

989. 数组形式的整数加法

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

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

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

示例 1：

输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234
1
2
3

示例 2：

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

示例 3：

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

提示：

• 1 <= num.length <= 104
• 0 <= num[i] <= 9
• num 不包含任何前导零，除了零本身
• 1 <= k <= 104

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎

题干很容易理解，就是把输入数组和数字逐位相加嘛🌸🌸🌸

例如 计算 123 + 912，我们从低位到高位依次计算 3+2、2+1 和 1+9。任何时候，若加法的结果大于等于 10，把进位的 1 加入到下一位的计算中，所以最终结果为 1035 🌺🌺🌺

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

这道题和 2. 两数相加一样，一个公式 当前位 = (A 的当前位 + B 的当前位 + 进位carry) % 10

注意 ① ，AB两数都加完后，最后判断一下进位 carry，进位不为 0 的话加在前面 💐💐💐

注意 ② ，数组是尾插法，故输出结果前需反转（reverse）💐💐💐

【加法模板】同解 165. 比较版本号

while ( A 没完 || B 没完)
A 的当前位
B 的当前位

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

当前位 = 和 % 10;
进位 = 和 / 10;

判断还有进位吗 🌼🌼🌼

【比较模板】推广到字符串比较，809. 情感丰富的文字（谷歌高频题）

while( A 没完 && B 没完)
A 的当前字符
B 的当前字符

​ A 的当前字符长度
​ B 的当前字符长度

判读符合比较条件吗 🌻🌻🌻

整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

std::vector addToArrayForm(std::vector& A, int K) {
	std::vector res; //定义结果数组
    for(int i = A.size(); i || K; K /= 10){ //同时遍历输入数组和数字
        res.emplace_back(i ? (K += A[--i]) % 10 : K % 10); //(K + A 当前位) 取余
    }
    reverse(res.begin(), res.end()); //翻转数组
    return res; //返回结果
}
1
2
3
4
5
6
7
8

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

i || K; //循环结束的条件是输入数组和数字都遍历完
1

当且仅当输入数组和数字逐位相加，并两者皆遍历完成时，循环终止，如下例所示 🌹🌹🌹

输入：num = [1,2,3,5], k = 34
输出：[1,2,6,9]
解释： 1 = num[0], 2 = num[1], 6 = num[2] + k / 10^1 % 10 , 9 = num[3] + k /10^0 % 10 
1
2
3

K /= 10 //遍历 K 时每次循环都将其除以 10，将当前的十位转换为个位
1

以下代码为求某数各位数字的实现，K /= 10 的注释就很好理解了 🌹🌹🌹

while (k > 0) {
	int val = k % 10; //求出个位上的数字
	k = k / 10; //将当前的十位转换为个位
}
1
2
3
4

i ? (K += A[--i]) % 10 : K % 10 //(K + A 当前位) 取余
1

A[--i] 是取当前 i 处的数字（int i = A.size()），i 左减减还是右减减依个人对 i 的初始化

采用 A 的当前位 + B 的当前位+ 进位carry 实现方式也可以，但 (K += A[--i]) 巧妙解决了进位问题（因为进位会直接加到 k 上，参与下一次循环），代码更简洁 🌹🌹🌹

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理中联想加法模板，但未联想到使用 reverse 😶😶😶

代码实现时未联想到使用 (K + A 当前位) 取余，简洁性差 😭😭😭 ，代码如下 👇👇👇👇

vector addToArrayForm(vector& num, int k) {
        std::vector res;
        int len = num.size(), numIndex = num.size() - 1;
        int tmpNum = 0, sumNum = 0, resCount = 0; //tmpNum表示进位，sumNum表示当前位之和
        while (true) {
            sumNum = tmpNum, tmpNum = 0; //进位之后立马归零
            if (numIndex >= 0) { 
                sumNum += num[numIndex]; //取数组同位
                --numIndex;
            }

            if (k > 0) {
                sumNum += k % 10; //求出个位上的数字
                k = k / 10; //将当前的十位转换为个位
            }

            if (sumNum >= 10) sumNum = sumNum % 10, tmpNum = 1; //判断是否有进位

            res.emplace_back(sumNum);
            ++resCount; //记录结果集个数(用以返回时的数组翻转)
            if (numIndex < 0 && k == 0 && tmpNum == 0) break;
        }
        
        return std::vector(res.rbegin() + res.size() - resCount, res.rend());
    }
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

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪