【Day 1 】2024-04-08 - 989. 数组形式的整数加法

[azl397985856]

989. 数组形式的整数加法

入选理由

暂无

题目地址

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

前置知识

• 数组的遍历

  题目描述

  
  对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

 

示例 1：

输入：A = [1,2,0,0], K = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234 示例 2：

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

输入：A = [2,1,5], K = 806 输出：[1,0,2,1] 解释：215 + 806 = 1021 示例 4：

输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1 输出：[1,0,0,0,0,0,0,0,0,0,0] 解释：9999999999 + 1 = 10000000000  

提示：

1 <= A.length <= 10000 0 <= A[i] <= 9 0 <= K <= 10000 如果 A.length > 1，那么 A[0] != 0

[zhiyuanpeng]

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        ans = []
        overflow = 0
        k = [int(i) for i in str(k)]
        num = num[::-1]
        k = k[::-1]
        for i in range(max(len(num), len(k))):
            if i <= len(num) - 1 and i <= len(k) - 1:
                overflow, cur = divmod((num[i] + k[i] + overflow), 10)
                ans.append(cur)
            elif i <= len(num) - 1:
                overflow, cur = divmod((num[i] + overflow), 10)
                ans.append(cur)
            elif i <= len(k) - 1:
                overflow, cur = divmod((k[i] + overflow), 10)
                ans.append(cur)
        if overflow != 0:
            ans.append(overflow)
        return ans[::-1] 

time: O(len(num)+len(k)) space max(len(num), len(k))

[wwz223]

var addToArrayForm = function (num, k) {
  const knum = k.toString().split('').reverse();
  num = num.reverse();
  const max = Math.max(num.length, knum.length);
  let isUp = 0;
  let ni = 0,
    ki = 0,
    sub = 0;
  for (let i = 0; i < max; i++) {
    ni = Number(num[i]) || 0;
    ki = Number(knum[i]) || 0;
    sub = ni + ki + isUp;
    num[i] = sub % 10;
    isUp = Number(sub >= 10);
  }
  if (isUp) num.push(1);
  return num.reverse();
};

time：O(n) space：O(1)

[zin-next]

题解

var addToArrayForm = function(num, k) {
  const arr = [];
  let carry = 0;
  for (let i = num.length - 1; i >= 0; i--) {
    let sum = num[i] + k % 10 + carry;
    carry = Math.floor(sum / 10);
    sum = sum % 10;
    arr.unshift(sum);
    k = Math.floor(k / 10); 
  }

  for (; k > 0 || carry > 0 ;) {
    let sum = k % 10 + carry;
    carry = Math.floor(sum / 10);
    arr.unshift(sum % 10);
    k = Math.floor(k / 10);
  }

  return arr;
};

复杂度

时间复杂度： 取决于num的长度和k的大小(取最大)：O(n) 空间复杂度：常量忽略，只定义了一个arr：O(n)

[atom-set]

思路

这个题目可以理解为大数相加的变形。

• step1: 去 num 和 k 的最大长度
• step2: 对 num 和 k(k 需要转换为数组) 进行前置补 0
• step3: 逆序遍历按位相加，同时需要考虑是否有进位(大于 9，即有进位)

代码

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function (num, k) {
  if (num === 0) return k;

  // k 计算 k 的长度
  var kLen = 0;
  var secondNum = [];
  var firstNum = [];
  var kLen = String(k).length;
  // 最大长度
  var maxLen = num.length > kLen ? num.length : kLen;

  // 补0
  for (var j = maxLen - 1; j >= 0; j--) {
    if (j > num.length - 1) {
      firstNum.push(0);
    } else {
      firstNum.push(num.shift());
    }
  }

  for (var i = maxLen - 1; i >= 0; i--) {
    if (i > kLen.length - 1) {
      secondNum.push(0);
    } else {
      secondNum.unshift(k % 10);
      k = (k - (k % 10)) / 10;
    }
  }

  // 遍历相加
  var bit = 0;
  for (var k = maxLen - 1; k >= 0; k--) {
    var sum = firstNum[k] + secondNum[k] + bit;
    if (sum >= 10) {
      secondNum[k] = sum % 10;
      bit = (sum - (sum % 10)) / 10;
    } else {
      bit = 0;
      secondNum[k] = sum;
    }
  }

  if (bit > 0) {
    return [bit, ...secondNum];
  }

  return secondNum;
};

复杂度分析

对数据进补 0 和按位相加，进行了遍历，时间复杂度为 O(N)；

声明了 firstNum 和 secondNum 临时变量存放数据，空间负责度为 O(N)

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

[coderXiaowq]

Java 时间复杂度 O(n) ` public List addToArrayForm(int[] a, int k) { List list = new ArrayList<>(); List K = new ArrayList<>(); //将数据k保存到集合K while(k > 0){ K.add(k % 10); k /= 10; } //开始计算 int p = a.length - 1;//从右往左遍历a int i = 0;//从左往右遍历K int left = 0;//进位值 while(p>=0 || i<K.size()){ int sum = 0;//保存相加的和 if(p>=0 && i<K.size()){ sum = a[p]+K.get(i)+left; }else if(p<0){ sum = K.get(i)+left; }else{ sum = a[p]+left; } if(sum>9){ list.add(sum % 10); left = sum / 10; }else{ list.add(sum); left = 0; } p--; i++; } if(left != 0){ list.add(left); }

List<Integer> rs = new ArrayList<>();
//反转list
for(int j = list.size() - 1; j>=0; j--){
    rs.add(list.get(j));
}

return rs;

}`

[hillsonziqiu]

思路

首先想到的方法是两个数求解嘛，直接数组转数字相加后再放到数组中。提交的时候发现了问题，js大数操作的时候精度会G掉，故这个方案不可行； 那么就只能按位相加了，加法是从个位开始进行计算，那么反向获取一下数组, 按位相加. 另一种情况：如果k的位数大于sum，那么需要将k多出来的位数追加到前面。 最后数组取反即可；

代码

  const res = [];
  const n = num.length;
  for (let i = n - 1; i >= 0; --i) {
    let sum = num[i] + (k % 10);
    k = ~~(k / 10);
    if (sum >= 10) {
      k++;
      sum -= 10;
    }
    res.push(sum);
  }
  while (k > 0) {
    res.push(k % 10);
    k = ~~(k / 10);
  }
  res.reverse();
  return res;

复杂度

n为sum的length，m为k的个数 时间复杂度：O(n + |n-m|) 空间复杂度：O(1) 没有用到新的存储空间

[Alexzhang-Mini]

代码

class Solution:
    def addToArrayForm(self, A: List[int], K: int) -> List[int]:
        K = list(map(int,str(K)))

        diff = len(K) - len(A)
        if diff: A = [0] * diff + A 
        if diff < 0: K = [0] * (-diff) + K

        flag = 0
        for i in range(len(A)-1,-1,-1):
            bit = A[i] + K[i] + flag
            flag = 0
            if bit >= 10:
                flag = 1
                bit %= 10
            A[i] = bit 
        if flag: A = [1] + A 
        return A

时间复杂度：O(N)

[xil324]

var addToArrayForm = function (num, k) {
    const res = []; 
    let index = num.length - 1; 
    let currSum = k; 
    while(index >= 0 || currSum > 0) {
        if(index >= 0) {
            currSum += num[index]; 
            index--; 
        }
        res.push(currSum % 10);
        currSum = Math.floor(currSum / 10); 
    }
    return res.reverse()
};

思路：

一个数组num和数字k相加，第一个想法是把数字转换层数组，然后从两个数组的末尾依次相加， 如何和超过10则进一位。 这样和用k与每一个num的数字相加，然后保留和的尾数，k除以10 是一样的。 例如： num = [1,2,3] k = 79

• 79 + 3 = 82 [2]
• 82/ 10 -> 8
• 8 + 2 = 10 [2, 0]
• 10/10 -> 1
• 1 + 1 = 2 [2, 0, 2]

数组反转： [2,0,2]

时间复杂度： num长度为n, k包含的数组为m

• n >= m O(n)
• n < m. O(log(k)) 综合 O(max(n, log(k))

空间复杂度： O(1)

[borderGong]

var addToArrayForm = function(num, k) { var numK = (k + '').split(''); var diff = num.length - numK.length > 0 ? num.length : numK.length; var result = []; var isStep = false; for (var i = 0; i < diff; i++) { var a = num[num.length - (1 + i)] || 0; var b = numK[numK.length - (1 + i)] || 0; var r = a + Number(b) + Number(isStep); isStep = r >= 10; result.unshift(r%10); } if (isStep) { result.unshift(1); } return result; };

时间复杂度： O(n)

思路： 总体思路是模拟数学的加法 1·数据格式对齐 2.从各位开始遍历（数组尾部），依次累加，超过十进位取余

[hillsonziqiu]

思路

首先想到的方法是两个数求解嘛，直接数组转数字相加后再放到数组中。提交的时候发现了问题，js大数操作的时候精度会G掉，故这个方案不可行； 那么就只能按位相加了，加法是从个位开始进行计算，那么反向获取一下数组, 按位相加. 另一种情况：如果k的位数大于sum，那么需要将k多出来的位数追加到前面。 最后数组取反即可；

代码

  const res = [];
  const n = num.length;
  for (let i = n - 1; i >= 0; --i) {
    let sum = num[i] + (k % 10);
    k = ~~(k / 10);
    if (sum >= 10) {
      k++;
      sum -= 10;
    }
    res.push(sum);
  }
  while (k > 0) {
    res.push(k % 10);
    k = ~~(k / 10);
  }
  res.reverse();
  return res;

复杂度

n为sum的length，m为k的个数 时间复杂度：O(n + |n-m|) 空间复杂度：O(1) 没有用到新的存储空间

纠错

while 循环的时间复杂度是 O(log m) 故整体的时间复杂度应该是 O(n+log m); reverse也有一个O(n); 相加应该为O(2n + logm); 去掉常量O(n+log m)

[Hawkins-hjq]

思路

遍历数组，将数组和K的每一位数字 ，从右到左 ，逐一相加，如果两个数相加大于等于10，则进位+1；

代码

class Solution {
public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        for (int i = num.length - 1; i >= 0; i--) {
            // 逐位相加
            int sum = num[i] + k % 10;
            k /= 10;
            // 进位
            if (sum >= 10) {
                k++;
                sum -= 10;
            }
            result.add(0, sum); 
        }

        for (; k > 0; k/= 10) {
            result.add(0, k % 10);
        }
        return result;
    }
}

复杂度

时间复杂度：O(max(n,logk)); 空间复杂度：O(1)

[snmyj]

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res,ans;
        int jw = 0;
        int pos = num.size() - 1;
        for ( int i = pos; i>=0; i-- ) {
             int s = num[i] + k % 10 + jw;
             jw = s/10;
             k/=10;
             res.push_back(s % 10);

        }
        while (jw > 0 || k > 0) {
            int s =( jw + k%10 );
            jw = s/10;
            k /= 10;
            res.push_back(s%10);
        }
        for ( int i = res.size() - 1 ;i>=0;i--) {
           ans.push_back(res[i]);
        }
        return ans;
    }
};

[CathyShang]

思路:

1. 数组转换整数
2. 相加
3. 判断和的长度
4. 整数转换数组

代码:

vector<int> addToArrayForm(vector<int>& num, int k) {
    long long int h=0;
    int n = num.size();
    int cur_m = n-1;
    for(int i=0; i<n; i++){
        h = h + num[i]*pow(10,cur_m);
        cur_m = cur_m -1; 
    }
    //2
    long long r; int l; //求和，输出长度
    r = h+k;
    //3
    if(r>=pow(10,n)){
        l = n+1;
    } else{ l = n;}
    // 判断一下k的长度，kl
    int kl = 0;
    if(k>=pow(10,4)){kl = 5;}
    else if (k>=pow(10,3)){kl = 4;}
    else if (k>=pow(10,2)){kl = 3;}
    else if (k>=10){kl = 2;}
    else{ kl = 1;}
    if(kl > l){ l = kl;}
    if(r>=pow(10, l)){
        l = l+1;
    }
    //4
    vector<int> res(l,0);
    cur_m = l-1;

    for(int j=0; j < l; j++){
        if(j==l-1){ res[j]= r;}
        else{
            int temp = floor(r/pow(10,cur_m));
            res[j] = temp;
            r = r - res[j]*pow(10,cur_m);
            cur_m = cur_m-1;
            // cout << r;
        }
    }
    return res;
    }

复杂度: 时间复杂度 $O(N)$ N = num.length()

错误: 由于是以num为主导，没有注意它范围很大，超出了程序变量的长度。 后发现，将k转换为数组，再模拟数字加法，适合本题。

[smallppgirl]

思路： 遍历 数组和整数k的每一个数字，然后逐位相加，如果遇到进位，加在下一轮 算法

class Solution:
    def addToArrayForm(self, A: List[int], K: int) -> List[int]:
        i = len(A) - 1
        while K:
            A[i] += K
            K, A[i] = A[i] // 10, A[i] % 10
            i -= 1

            if i < 0 and K:
                A.insert(0,0)
                i = 0
        return A

时间复杂：O(len(num)+len(K)) 空间复杂： O(max(len(num)+len(K)))

[GReyQT]

题解思路： （1）整型按位翻转存放在容器中 （2）翻转num容器，然后按位相加，并考虑进位情况 （3）翻转最后的结果即为答案 代码：

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int digit = 0;
        vector<int> k_num;
        vector<int> result;
        for (int i = 0; ; i++)
        {
            digit = (k / (int)pow(10, i)) % 10;
            if (digit == 0 && (int)pow(10, i) > k )
            {
                break;
            }
            k_num.push_back(digit); //翻转存放
        }
        int carry = 0; // 进位
        int size = max(num.size(), k_num.size()); // 选择两个容器中较大的大小作为循环次数
        reverse(num.begin(), num.end());    //num容器翻转
        for (int i = 0; i < size; ++i) 
        {
            int digit1 = (i < num.size()) ? num[i] : 0; // 如果 i 超出 num 的索引范围，取 0
            int digit2 = (i < k_num.size()) ? k_num[i] : 0; // 如果 i 超出 k_num 的索引范围，取 0
            int sum = digit1 + digit2 + carry; // 计算当前位的和
            carry = sum / 10; // 更新进位
            result.push_back(sum % 10); // 将当前位的结果添加到结果容器中
        }
        // 如果最高位有进位，需要额外添加一位
        if (carry > 0) 
        {
            result.push_back(carry);
        }
        reverse(result.begin(), result.end());  //翻转获得结果
        return result;
    }
};

复杂度分析： 时间复杂度：取决于整数 k 的位数和 num 容器的大小，因此为O(n) 空间复杂度：取决于空间复杂度主要取决于 k_num 和 result 容器的大小，因此为O(n)

[rao-qianlin]

• 思路：按位进行运算，相加大于10，则进位。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = scanner.nextInt();
        }

        int k = scanner.nextInt();
        int mid;

        for(int i = n-1; i >=0 ; i--){
            if((int)arr[i] + k >= 10){
                mid = (arr[i] + k)/10;
                arr[i] = arr[i] + k - 10 * mid;
                k = mid;
            }
            else{
                arr[i] = arr[i] + k;
                k = 0;
            }
        }
        if(k!=0){
            System.out.println(k+" ");
        }

        for(int i = 0; i < arr.length; i++){
            System.out.println(arr[i]+" ");
        }
    }
}

[YANGLimbo]

补day1

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        // 注意！32位的int最大值2147483647，是十位数，题干说明数组长度最大为10^4
        // 如果把数组转成整数计算，会出现溢出的问题
        // 所以只能用数组计算
        int len = num.size();
        vector<int> rev = num;
        reverse(rev.begin(),  rev.end());
        int i = 0;
        int a = k / 10;
        int b = k % 10;
        int sum = 0;
        int extra = 0; // 进位
        int x = 0;
        vector<int> res;
        do {
            if(i <len){
                x = rev[i];
            }else{
                x = 0;
            }
            sum = x + b + extra;
            extra = sum / 10;
            //printf("%d + %d = %d\n",rev[i],b, sum);
            res.push_back(sum % 10);
            i++;
            k = a;
            a = k / 10;
            b = k % 10;

        } while (k != 0 || i < len || extra!= 0);

        reverse(res.begin(), res.end());
        return res;

    }
};

[Martina001]

补打卡day 1 思路： 直接记录进位 不断向前++ 即可，注意最后还需处理剩余的进位值和k剩余部分

public List<Integer> addToArrayForm(int[] num, int k) {
            int n = num.length;
            int carry = 0;
            LinkedList<Integer> linkedList = new LinkedList<>();
            for (int i = n - 1; i >= 0; i--) {
                int val = num[i];
                int newVal = val + k % 10 + carry;
                linkedList.addFirst(newVal % 10);
                // num[i] = newVal % 10;
                k /= 10;
                carry = newVal / 10;
            }
            if(carry !=0 || k !=0){
                int val = carry+k;
                while(val !=0){
                    linkedList.addFirst(val%10);
                    val = val/10;
                }
            }
            /*List<Integer> list = new ArrayList<>();
            if(carry != 0){
                list.add(carry);
            }
            for(int val:num){
                list.add(val);
            }*/
            return linkedList;
        }

时间复杂度On 空间复杂度O1

[pandapls]

补day1

// 利用k的取余操作 对num中倒叙进行相加
var addToArrayForm = function(num, k) {
    const ret = [];
    const n = num.length;

    for(let i = n - 1; i >= 0; --i) {
        let sum = num[i] + k % 10;
        k = Math.floor(k /10)
        if (sum >= 10) {
            k++;
            sum -= 10;
        }
        ret.push(sum)
    }

    for(; k > 0; k = Math.floor(k / 10)) {
        ret.push(k % 10)
    }
    return ret.reverse();
};