【基础篇 - Day 1】 2023-02-13 - 989. 数组形式的整数加法

[threedayAAAAA]

整数的 数组形式  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 <= 104 0 <= num[i] <= 9 num 不包含任何前导零，除了零本身 1 <= k <= 104

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/add-to-array-form-of-integer 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

1. 倒序遍历数组
2. 每次都将进位的数值与 当前元素相加
3. 相加的和除10取余即为当前元素的新值
4. 相加的和除10取整即为新的进位数值， 重复第一步, 直到进位的值为0 并且数组遍历完

代码

function addToArrayForm(num: number[], k: number): number[] {
    let remaining = k
    let result = []
    let currentIndex = num.length - 1
    while(remaining > 0 || currentIndex >= 0){
        if(currentIndex >= 0){
            remaining += num[currentIndex]
            currentIndex--
        }
        result.push(remaining % 10)
        remaining = Math.floor(remaining / 10)
    }
    return result.reverse()
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[MiumMi]

方案一：

思路

1. 默认remain为传入的K，标识需要加到下一个元素的值
2. 倒序遍历数组，如果当前index已经小于0了，要给数组新增一个元素，并将index指针重置回0的位置【原因：处理remain比> 实际的num更大的情况】
3. 当前元素的最新值为：当前计算的总数（即元素加上余数）再对10取余【原因：因为每个数组元素只存储单个数字，所以不> 会超过10】
4. 根据当前计算的总数重新取remain，进入下一次循环

5. 结束循环判断条件需要数组遍历结束并且remian为0 了才能退出循环【原因：处理remain比实际的num更大的情况】

   代码

   function addToArrayForm(num: number[], k: number): number[] {
   let remain = k;
   let index = num.length -1;
   while(remain > 0 || index > 0) {
       if (index < 0) {
          num.unshift(0);
          index = 0
      }
      let total = num[index] + remain;
      num[index] = total % 10;
      index--;
       remain = Math.floor(total / 10);
   }
   return num;
   };

   ---

   复杂度分析

6. 时间复杂度：O(n)

7. 空间复杂度：O(1)

方案二：

思路

1. 判断num和k的数组，谁长度比较长谁作为最终返回的数组，另一个作为加值
2. 倒序遍历长度较长的数组，声明一个指针指向addArr的尾部，remain作为元素需要加的值，默认为当前指针指向的元素
3. 每次遍历，新的当前元素以当前计算的总数（即remain+当前遍历的元素）对10取余作为最终的值，同时指针向前挪一位
4. 根据当前计算的总数对10取整并加上当前指针指向的元素作为remain，进入下一次循环

5. 循环完成，判断remain是否为0，不为0的话则数组要在头部插入该余数

   代码

   function addToArrayForm(num: number[], k: number): number[] {
   let addArr = String(k).split('').map(Number);
   let isExchange = num.length < addArr.length;
   let result = isExchange ? addArr : num;
   addArr = isExchange ? num : addArr;
   let addIndex = addArr.length - 1;
   let remain = Number(addArr[addIndex]);
   let len = result.length;
   for(let i = len -1; i >= 0; i--) {
       let total = result[i] + remain;
       result[i] = total % 10;
       addIndex--;
       remain = Math.floor(total / 10) + (Number(addArr[addIndex]) || 0);
   }
   if (remain > 0) {
       result.unshift(remain);
   }
   return result;
   };

   ---

   复杂度分析

6. 时间复杂度：O(n)

7. 空间复杂度：O(n)

[yunliuyan]

思路：

• 将K重新赋值，变成可编辑的值copyK
  • 将数组进行倒序遍历
  • 如果k值为0，或者数组遍历完，则结束
  • 当数组未遍历完，copyK，加上当前num元素
  • 结果数组，则取copyK最后一位，copyK则除以10取整

代码

function addToArrayForm(num: number[], k: number): number[] {
    let copyk = k, i = num.length - 1;
    const result: number[] = [];
    while(copyk > 0 || i >= 0) {
        if ( i >= 0) {
            copyk += num[i];
        }
        result.push(copyk % 10);
        copyk = Math.floor(copyk / 10);
        i--;
    }
    return result.reverse();
};

复杂度分析

时间复杂度：O(n) 空间复杂度：O(1)