作者主页：@进击的安度因
学习社区：进击的安度因（个人社区）
专栏链接：每日挠头算法题

文章目录

  • 一、题目描述
  • 二、思路及代码实现

如果无聊的话，就来逛逛 我的博客栈 吧!

今天为大家带来的是力扣上的一道简单题：数组形式的整数加法。这道题我在2个月前就尝试过，但是没有解答出来。两个月后再做这道题目，就变得没那么难了。这次我将以高精度加法进行求解，让我们开始吧！

一、题目描述

链接：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

示例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

提示：

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

二、思路及代码实现

这道题题目大意就是：将数组转化为整数与整数 k 相加后的结果存入新数组中，将结果返回。

比如 num = [1, 2, 0, 0], k = 34，计算后，返回结果就是 [1, 2, 3, 4] 。

但是可能有进位的存在，比如 [2, 1, 5] 和 806 相加就会变成 1021 ，原本数组大小就不够了 。

总结一下 num 和 k 相加后的情况 ：

  • 相加结果等于 num 数组位数
  • 相加结果等于 k 的位数
  • 相加结果比 num 和 k 中较大的多 1

题目给定了 num 数组的大小 ，那么我只要求出 k 的大小然后比较一下，取较大的一个作为返回数组长度 ， 开辟空间时多开辟一个空间方便进位 就好了 。

考虑到进位的问题，所以这道题目我采用了 高精度加法 。其实博主之前只是大概知道高精度加法，所以做题目的时候专门去查了一下高精度加法是怎么使的。

高精度加法其实就是几个步骤：倒序存储数字 → 计算 → 存出结果

至于为什么倒着存，就是方便进位嘛，你想想对于一个数来说是在0下标前进位简单，还是在数组末尾进位简单？那当然是在数组末尾，因为往后偏移一个下标就可以。

对于这题算出长度 len ，开个 len + 1 大小的数组来处理 进位 。

然后就是相关变量的定义 ：

  • oldNum ：记录 num 数组中的数据
  • oldSize ：记录原数组的下标
  • nextNum ：存储相加后的数据，并判断是否进位
  • cnt ：当前返回数组中的元素个数

计算并存储的过程：

  1. 遍历 返回数组 res ，倒着取 num 数组元素，存到 oldNum 中，并 oldSize-- 。

  2. 然后将 oldNum 和 k % 10 ( k 对应位数的值) 的和 累加到 nextNum 中 。

  3. 将 nextNum 的有效数字存入 res 数组当前位置，并将 cnt++ ，表示 res 数组有效数据位数增加。

  4. 再把 nextNum / 10 ，看结果是否为1，为 1 则有 进位 。

  5. 最后调整一下 k ，k / 10 去掉一位。

循环往复如上过程，也就基本把数据 倒着 存到了 res 数组中 。

但是注意了！！！：

我们只遍历 len 次，只能计算出 相加结果等于 num 数组位数 和 相加结果等于 k 的位数 的情况。

比如 num = [2, 1, 5] k = 806 的情况，在经过上述过程中，res 数组中数据为：

这样没有考虑到进位的情况。

所以退出循环时，如果 相加结果有进位的话(nextNum == 1) ，是要额外处理一下的。就是在 cnt 下标处填 1 ，然后把 cnt++ 。

最后由于我们这个是倒着存的，所以需要把 res 数组的有效数据逆置一下 。

提一句：逆置的有效数据就是 cnt 的个数。因为我们先开始多开了一个空间，在没有进位的情况中，多开空间的位置是不会被填入数据的。

最后算出来，将 res 数组返回就好了。

接下来看看代码怎么写：

/* * oldNumnum数组中的数据 * oldSize num数组的下标 * nextNum 判断是否进位 * cnt res数组中有效数据的个数 */int* addToArrayForm(int* num, int numSize, int k, int* returnSize){// 算出 k 的位数int kSize = 0;int tmp = k;while (tmp) {++kSize;tmp /= 10;}// 比较 k 和 数组的长度，求大的int len = numSize > kSize " />: kSize;// 多开一个空间，以便进位int* res = (int*)malloc(sizeof(int) * (len + 1));// 高精度加法int oldNum = 0, oldSize = numSize - 1, nextNum = 0, cnt = 0;for (int i = 0; i < len; ++i) {oldNum = 0;if (oldSize + 1) {oldNum = num[oldSize--];}nextNum += oldNum + k % 10;res[cnt++] = nextNum % 10;nextNum /= 10;k /= 10;}if (nextNum) {res[cnt++] = 1;}// 将有效数据逆置int l = 0, r = cnt - 1;while (l < r) {int tmp = res[l];res[l] = res[r];res[r] = tmp;l++;r--;}*returnSize = cnt;return res;}

完结撒花