OJ05：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

思路分析

两个数相加，我们首先要考虑结果存在哪，我们该开辟多大的空间；我们知道两个数相加，结果的位数最大不会超过两个加数中最大的位数+1；所以我们先要判断传进的k是多少位数：

int kSize = 0;//存储k的位数
int kNum = k; //拷贝一份，方便下面求k的位数
while (kNum)
{++kSize;kNum /= 10;
}

然后我们再通过两个位数的最大值来开辟空间：

 //相加的时候以位数多的数来进行开扩空间和循环的判断
int len = numSize > kSize ? numSize : kSize; 
int* retArr = (int*)malloc(sizeof(int) * (len + 1));
if (retArr == NULL)
{perror("malloc");exit(-1);
}

有了开辟的空间，我们就要将计算的结果存进空间里，由于进位我们一定是从左到右进行计算的：
为了让大家好理解：我们可以先将每位算出的结果从左到右按顺序存好，最后将其倒置：

整理以上的思路：所以循环体我们可以这样写

while (len--)
{int a = 0;ret = num[end] + nextNums + k % 10;if (ret > 9){ret -= 10;nextNums = 1;}else{nextNums = 0;}retArr[reti] = ret;reti++;k /= 10;end--;
}

但是这时候我们就有一个问题了，如果k的位数比num的元素个数大，这时num就会存在越界的问题：

这时我们可以定义一个变量a = 0，如果end在有效的范围的时候我们就可以直接将num[end]赋值给a，让a与k的对应位相加，但是，如果不是有效位，我们可以将a与其相加：

int a = 0;
if (end >= 0)
{a = num[end];end--;
}
ret = a + nextNums + k % 10;

最后不要忘记了倒置数组：

//倒置数组
int left = 0;
int right = reti - 1;
while (left < right)
{int tmp = retArr[left];retArr[left] = retArr[right];retArr[right] = tmp;left++;right--;
}

代码展示

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {int kSize = 0;//存储k的位数int kNum = k; //拷贝一份，方便下面求k的位数while (kNum){++kSize;kNum /= 10;}int len = numSize > kSize ? numSize : kSize;  //相加的时候以位数多的数来进行开扩空间和循环的判断int* retArr = (int*)malloc(sizeof(int) * (len + 1));if (retArr == NULL){perror("malloc");exit(-1);}int end = numSize - 1;int reti = 0;int nextNums = 0;  //判断是否进位int ret = 0;while (len--){//防止k的位数大于num元素个数，导致越界int a = 0;if (end >= 0){a = num[end];end--;}ret = a + nextNums + k % 10;if (ret > 9){ret -= 10;nextNums = 1;}else{nextNums = 0;}retArr[reti] = ret;reti++;k /= 10;}if (nextNums == 1){retArr[reti] = 1;reti++;}//倒置数组int left = 0;int right = reti - 1;while (left < right){int tmp = retArr[left];retArr[left] = retArr[right];retArr[right] = tmp;left++;right--;}*returnSize = reti;return retArr;}

当然，这种算法可以过leetcode的

---