azl397985856 commented 2 years ago

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

eliassama commented 2 years ago

整体思路

整个题可以看作是一个纯粹的数字相加的题，因为不管是数字还是数组，都是有序。

如1024这个数，不管是number类型的1024还是数组类型的 [1,0,2,4]都是一样的，不同的只是展现形式。

所以这道题的关键点在于采用哪种形式进行计算，以及如何转换为最终要的数组形式。其实计算反而不重要。

在解题时需要注意下溢出问题，这个题的测试用例是会有大数的，部分编程语言是不支持大数的 ( 如js的int32只支持18位以内的精确大数 ) ，所以计算要取巧。

解题思路

采用古老而笨拙的按位进制法，即以numArray作为遍历条件，从最低位到最高位依次与k的最低位到最高位进行相加。

在相加的过程中有些东西需要注意：

因为每次相加都是单位数相加，所以最大的值为18 ( 9 + 9 )。而每个元素只能承载单位数，所以会向前进一，所以实际最大值为19 ( 9 + 9 + 1 )。但是这个数不会超过19。所以要考虑两点：
- 除了个位数外，如果上次相加的数有进位的，则每次相加时都要加上进位。
- 如果每次相加的结构需要进位的，需要记录在下一次相加时加上。
因为以numArray作为遍历条件，所以可能会出现下列两种情况从而导致溢出问题，需要考虑进去：
- k的值的位数可能会比numArray的位数大，比如[2,1]和3600。
- 两个数相加，最后要整体向前进一位，比如[9,9,9]和1

版本一

Code

function addToArrayForm(numArray: number[], k: number): number[] {

    const KStr: string = String(k)
    let numArrayIndex: number = numArray.length - 1
    let KStrIndex: number = KStr.length - 1
    let lastNum:number = 0

    for(;numArrayIndex > -1; --numArrayIndex, --KStrIndex){
        numArray[numArrayIndex] += (parseInt(KStr[KStrIndex]) || 0) + lastNum
        lastNum = 0
        if(numArray[numArrayIndex] > 9){
            numArray[numArrayIndex] -= 10
            lastNum = 1
        }
    }

    if(KStrIndex > -1){
        let overflowStr: string = String(parseInt(KStr.substring(0, KStrIndex + 1)) + lastNum)
        KStrIndex = overflowStr.length - 1
        lastNum = 0
        const overflowArray: number[] = []
        for(;KStrIndex > -1; --KStrIndex){
            overflowArray.push(parseInt(overflowStr[KStrIndex]))
        }
        overflowArray.reverse()
        numArray = [...overflowArray,...numArray]
    }

    if(lastNum === 1){
        numArray = [1,...numArray]
    }

    return numArray
};

复杂度分析

时间复杂度：O(N)，其中 N 为 numArray 或 k 的最大长度。
空间复杂度：O(N)，其中 N 为 numArray 加 k 的长度，并有可能会在此基础上 + 1。

版本二

Code

function addToArrayForm(numArray: number[], k: number): number[] {

    const kArray: string[] = String(k).split("")
    let kIndex: number = kArray.length - 1
    let nIndex: number = numArray.length - 1
    const resultArray: number[] = []

    let lastNum:number = 0
    for(;kIndex > -1 || nIndex > -1 ; --kIndex, --nIndex){
        let result = (parseInt(kArray[kIndex]) || 0) + (numArray[nIndex] || 0) + lastNum
        lastNum = 0
        if(result > 9){
            result -= 10
            lastNum = 1
        }
        resultArray.push(result)

        if(kIndex <= 0 && nIndex <= 0 && lastNum === 1){
            resultArray.push(1)
        }

    }

    return resultArray.reverse()
};

复杂度分析

时间复杂度：O(N)，其中 N 为 numArray 或 k 的最大长度。
空间复杂度：O(N)，其中 N 为 numArray 或 k 的最大长度，并有可能会在此基础上 + 1。

noperoc commented 2 years ago

题目地址(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

前置知识

公司

思路

模拟竖式逐位相加

关键点
最后一位剩余进位别忘了加

代码

语言支持：Java

Java Code:


class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        ArrayList<Integer> kk = new ArrayList<>();
        while(k != 0){
            int tmp = k % 10;
            k = k / 10;
            kk.add(0,tmp);
        }
        int ml = num.length;
        int kl = kk.size();    
        ArrayList<Integer> ans = new ArrayList<>();  
        int flag = 0;
        while(ml != 0 && kl != 0){
            int tmp = num[ml-1] + kk.get(kl-1) + flag;
            if(tmp >= 10){
                flag = 1;
                tmp -= 10;
            }
            else
                flag = 0;
            ans.add(0, tmp);
            kl--;
            ml--;
        } 
        if(ml != 0){
            for(int i = ml-1; i>=0 ; i--){
                int tmp = num[i];
                if(flag == 1){
                    tmp++;
                    flag = 0;
                }
                if(tmp == 10){
                    tmp = 0;
                    flag = 1;
                }
                ans.add(0, tmp);
            }
        }else if(kl != 0){
            for(int i = kl-1; i>=0 ; i--){
                int tmp = kk.get(i);
                if(flag == 1){
                    tmp++;
                    flag = 0;
                }
                if(tmp == 10){
                    tmp = 0;
                    flag = 1;
                }
                ans.add(0, tmp);
            }
        }
        if(flag == 1){
            ans.add(0, 1);
        }
        return ans;
    }
}

复杂度分析

令 n 为数组长度。

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

KennethAlgol commented 2 years ago

语言

java

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new LinkedList<>();
        final int len = num.length;
        for(int i = len - 1; i >= 0; i--) {
            int sum = num[i] + k % 10;
            k /= 10;
            if(sum >= 10) {
                k++;
                sum -= 10;
            }   
            res.add(0, sum);
        }
        for(; k > 0; k /= 10) {
            res.add(0, k % 10);
        }
        return res;
    }
}

honeymeng-hub commented 2 years ago

//leetcode submit region begin(Prohibit modification and deletion) //遍历nums[]转化为数值，再遍历返回数组 class Solution { public List addToArrayForm(int[] num, int k) { //idea1 ： FAILED，java中int最大2^32-1,（10位数） // long tmp = 0; // for (int i = num.length - 1, r = 1; i >= 0; i--) { // tmp += num[i] r; // r = r 10; // } // tmp = tmp + k; // //从数值里取出元素放入链表 // String s = Long.toString(tmp); // //String s1 = Integer.toString(); // ArrayList list = new ArrayList<>(); // for (int j = 0; j < s.length(); j++) { // int c = (int)s.charAt(j); // list.add(Integer.parseInt(s1.valueOf(s.charAt(j)))); // } // return list; //看完答案想法二：位运算，位置对象相加，进位加在上一位 //评论区发现：num[]末尾+k ，取末尾添加到链表再抛弃末尾 //时间复杂度：O（n）数组长度 //空间复杂度：O（n） LinkedList list = new LinkedList<>(); int len = num.length; int lastNum = k; int i = len -1; while (i >= 0 || lastNum > 0) { if (i >= 0) { lastNum += num[i]; } //取余放入链表 list.addFirst(lastNum % 10); //看看有没有进位(有就迭代，无就是0还是迭代) lastNum /= 10; i--; } return list; } }

Liuxy94 commented 2 years ago

思路

把num先变成int 然后sum_int = k+num_int 再把sum_int变成sum_array

代码

class Solution(object):
    def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        ## step0: corner case
        if k == 0:
            return num
        ## step1: change the array to number
        n = len(num)
        num_int = 0
        for i in range(n):
            num_int += num[i]*10**(n-1-i)
        ## step2: compute the sum
        sum_int = num_int + k
        sum_array = []
        ## step3: change the sum to array
        while sum_int != 0:
            quotient = sum_int//10
            remainder = sum_int%10
            ## update sum array and int
            sum_array.insert(0,remainder)
            sum_int = quotient

        return sum_array

复杂度分析

时间 O(n^2)

空间 O(n)

chenyaohn commented 2 years ago

int长度不够吧-------- 原始邮件 --------发件人： Xinyu Liu @.>日期： 2021年12月12日周日 18:45收件人： leetcode-pp/91alg-6-daily-check @.>抄送： chenyaohn @.>, Comment @.>主题： Re: [leetcode-pp/91alg-6-daily-check] 【Day 1 】2021-12-12 - 989. 数组形式的整数加法 (Issue #1)

思路

把num先变成int 然后sum_int = k+num_int 再把sum_int变成sum_array

代码

class Solution(object):

def addToArrayForm(self, num, k):

    """

    :type num: List[int]

    :type k: int

    :rtype: List[int]

    """

    ## step0: corner case

    if k == 0:

        return num

    ## step1: change the array to number

    n = len(num)

    num_int = 0

    for i in range(n):

        num_int += num[i]*10**(n-1-i)

    ## step2: compute the sum

    sum_int = num_int + k

    sum_array = []

    ## step3: change the sum to array

    while sum_int != 0:

        quotient = sum_int//10

        remainder = sum_int%10

        ## update sum array and int

        sum_array.insert(0,remainder)

        sum_int = quotient

    return sum_array

复杂度分析

时间 O(n^2)

空间 O(n)

—You are receiving this because you commented.Reply to this email directly, view it on GitHub, or unsubscribe.Triage notifications on the go with GitHub Mobile for iOS or Android.

Liuxy94 commented 2 years ago

@chenyaohn int长度不够吧-------- 原始邮件 --------发件人： Xinyu Liu @.>日期： 2021年12月12日周日 18:45收件人： leetcode-pp/91alg-6-daily-check @.>抄送： chenyaohn @.>, Comment @.>主题： Re: [leetcode-pp/91alg-6-daily-check] 【Day 1 】2021-12-12 - 989. 数组形式的整数加法 (Issue #1)

思路

把num先变成int 然后sum_int = k+num_int 再把sum_int变成sum_array

代码

class Solution(object):
def addToArrayForm(self, num, k):

    """

    :type num: List[int]

    :type k: int

    :rtype: List[int]

    """

    ## step0: corner case

    if k == 0:

        return num

    ## step1: change the array to number

    n = len(num)

    num_int = 0

    for i in range(n):

        num_int += num[i]*10**(n-1-i)

    ## step2: compute the sum

    sum_int = num_int + k

    sum_array = []

    ## step3: change the sum to array

    while sum_int != 0:

        quotient = sum_int//10

        remainder = sum_int%10

        ## update sum array and int

        sum_array.insert(0,remainder)

        sum_int = quotient

    return sum_array
复杂度分析

时间 O(n^2)

空间 O(n)

—You are receiving this because you commented.Reply to this email directly, view it on GitHub, or unsubscribe.Triage notifications on the go with GitHub Mobile for iOS or Android.

其实这个偷懒了应该是先把k变array 然后用carry 计算 sum of two array。长度应该是够的吧，至少submit是没有问题的。

shamworld commented 2 years ago

var addToArrayForm = function(num, k) {
    const res = [];
    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;
        }
        res.push(sum);
    }
    for (; k > 0; k = Math.floor(k / 10)) {
        res.push(k % 10);
    }
    res.reverse();
    return res;
};

eliassama commented 2 years ago

@chenyaohn 我看是@Liuxy94写的是python的代码，python3的话int自动就是long，所以应该是没问题

fredxxj commented 2 years ago

写个C++的版本，基础的大整数求和

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int carry = 0, a, b, c;
        vector<int> result;
        vector<int>::iterator iter = num.end();
        while( iter != num.begin() || k > 0)
        {
            a = iter != num.begin() ? *(--iter) :0;
            b = k % 10;
            k /= 10;
            c = (a + b + carry) % 10;
            carry = (a + b + carry) / 10;
            result.push_back(c);
        }
        if(carry == 1)
            result.push_back(1);
        std::reverse(result.begin(),result.end());      
        return result;
    }
};

2024-ZWR commented 2 years ago

思路

将K表示为数组，两个数组逐位相加。考虑进位。最后对数组取反。

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

        res = []
        i,j = len(A)-1,len(K)-1
        carry = 0

        while i >= 0 and j >= 0:
            res.append(A[i] + K[j] + carry)
            res[-1],carry = res[-1] % 10, res[-1] // 10
            i -= 1
            j -= 1
        while i >= 0:
            res.append(A[i] + carry)
            res[-1],carry = res[-1] % 10, res[-1] // 10
            i -= 1
        while j >= 0:
            res.append(K[j] + carry)
            res[-1],carry = res[-1] % 10, res[-1] // 10
            j -= 1

        if carry:
            res.append(1)

        return res[::-1]

时间复杂度O(n)

1052561252 commented 2 years ago

/**
 * 解题思路：先把题做出来，再考虑优化
 * <p>
 * 1.直观的看，应该属于大整数相加的问题
 * 2.对num从后向前遍历，每次遍历中对k%10获得对应位数的值t，再对k/10
 * 3.使得num[i]+t；考虑两种情况，<=9和>=10；如何是第一种情况，直接相加就行；如何是第二种情况，要考虑进位
 * <p>
 * 时间复杂度：O(n)
 *
 * @author My
 * @date 2021/12/12
 */
class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> temp = new ArrayList<>();

        //用于进位
        int carry = 0;
        for (int i = num.length - 1; i >= 0; i--) {
            int t = k % 10 + num[i] + carry;
            if (t > 9) {
                carry = 1;
            } else {
                carry = 0;
            }
            temp.add(t % 10);
            k /= 10;
        }

        while (k != 0) {
            int t = k % 10 + carry;
            if (t > 9) {
                carry = 1;
            } else {
                carry = 0;
            }
            temp.add(t % 10);
            k /= 10;
        }

        if (carry != 0)
            temp.add(carry);

        List<Integer> res = new ArrayList<>();
        for (int i = temp.size() - 1; i >= 0; i--) {
            res.add(temp.get(i));
        }

        return res;
    }
}

Hawkins-hjq commented 2 years ago

思路

将数组和 k的对应项从右至左以此相加，进位时carry + 1；

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new ArrayList<>();
        int carry = 0;
        int l1 = num.length - 1;

        while (l1 >= 0 || k != 0) {
            int x = l1 < 0 ? 0 : num[l1];
            int y = k == 0 ? 0 : k % 10;

            int sum = x + y + carry;
            res.add(sum % 10);
            carry = sum / 10;
            l1--;
            k = k / 10;
        }
        if (carry != 0) res.add(carry);
        Collections.reverse(res);
        return res;

    }
}

复杂度分析

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

Riuusee commented 2 years ago

思路

模拟一位位相加，处理进位，处理被加数、加数为0的情况

代码

public class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<Integer>();
        int c = 0;  //进位
        for (int i = num.length-1; i >= 0; i--) {   //倒着一位位相加
            int a = num[i] + k%10 + c;
            if (a > 9){
                c = 1;
                a -= 10;
                if (i == 0 && (k/10 == 0)){ //存在进位且加数为0
                    result.add(a);
                    result.add(1);
                    break;
                }
            }else {
                c = 0;
            }
            result.add(a);
            k /= 10;
            while (i==0 && k > 0){ //被加数为0加数不为0
                int b = k%10 + c;
                if (b > 9){
                    if(b==10 && (k/10 == 0)){ //进位
                        result.add(0);
                        result.add(1);
                        break;
                    }
                    b -= 10;
                    c =1;
                }else {
                    c = 0;
                }
                result.add(b);
                k /= 10;
            }
        }
        Collections.reverse(result);  //反转
        return result;
    }
}

复杂度分析

时间复杂度: O(N)
空间复杂度: O(N)

KevinWorkSpace commented 2 years ago

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int i = num.length - 1;
        int x = 0;
        int add = 0;
        while (i >= 0 || k > 0 || add == 1) {
            if (i >= 0) x = num[i];
            else x = 0;
            int res = (x + k % 10 + add) % 10;
            add = (x + k % 10 + add) / 10;
            list.addFirst(res);
            i --;
            k /= 10;
        }
        return list;
    }
}

时间复杂度: O(N) 空间复杂度: O(N)

Zhi22 commented 2 years ago

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        lk = []
        addOne = 0
        while k:
            k, m = divmod(k, 10)
            lk.append(m)
        ln = len(num); llk = len(lk)
        res = [0 for _ in range(max(ln, llk)+1)]
        num.reverse()
        idx = 0
        while idx < ln and idx < llk:
            sum = num[idx] + lk[idx] + addOne
            res[idx] = sum % 10
            addOne = 0
            if sum >= 10: addOne = 1
            idx += 1
        remain = num if ln > llk else lk
        while idx < len(remain) or addOne:
            if idx < len(remain): res[idx] += remain[idx]
            res[idx] += addOne
            addOne = 0
            idx += 1
            if res[idx] >= 10:
                res[idx] %= 10
                addOne = 1
        if res[-1] == 0: res.pop()
        res.reverse()
        return res

luo-FrontEnd commented 2 years ago

JavaScript 思路： 1、遍历数组，从高到低，每项加上K 2、如果res >= 10, 将 k % 10，得到个位保留在num得当前下标，并计算Math.floot(k% 10),得到除个位外的数值res2 例如 num = [1,2,3,4], k= 1234 第一次循环：num[3] === 4, 4 + 1234 = 1238 k% 10 = 8，push到新数组 Math.floot(k% 10) = 123 令k= 123，继续循环第二次循环：num[2] === 3, 3 + 123 = 126 k% 10 = 6，push到新数组 Math.floot(k% 10) = 12 令k= 12，继续循环 ... 最后得到数组[2,4,6,8] 需要注意的是，这里继续循环的条件不一定循环完整个数组，而是，循环完整个数据或循环完k，即 i >= 0 || k > 0 因为k不一定是和数组的length相同，当满足上面两个条件中的一个即可以继续循环

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

时间复杂度O(max(n,log k))

jie-zi commented 2 years ago

思路：转换成两个vector，逐个按位相加，注意k可能比num长，因此要加上k比num长的部分

vector<int> addToArrayForm(vector<int>& num, int k) {
    vector<int> res;
    int n=num.size();
    for(int i=n-1;i>=0;i--){
        int sum=num[i]+k%10;
        k=k/10;
        if(sum>=10){
            sum=sum-10;
            k++;
        }
        res.push_back(sum);
    }
    while(k){
        res.push_back(k%10);
        k=k/10;
    }
    reverse(res.begin(),res.end());
    return res;
    }

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

luo-FrontEnd commented 2 years ago

JavaScript 简单思路：利用JS数组方法、字符串方法数组-》字符串-》bigInt-》字符串-》数组


var addToArrayForm = function(num, k) {
    let result = BigInt(num.join(''))
    result += BigInt(k) 
    return String(result).split('')
};

这个地方需要注意要将字符串转成BigInt，不然会造成精度丢失。时间复杂度度：O(n) => 数组join方法+字符串split方法

xjhcassy commented 2 years ago

思路

采用LinkedList双向链表
将k依次加上num的各位，并取出最后一位

代码

public List<Integer> addToArrayForm(int[] num, int k) {

        int len = num.length;
        int lastNum = k;
        LinkedList<Integer> ret= new LinkedList<>();

        int i = len-1;
        while(i >=0 || lastNum > 0){
            if(i >= 0){
                lastNum+=num[i];
            }
            ret.addFirst(lastNum%10);
            lastNum/=10;
            i--;
        }

        return ret;

    }

复杂度分析

时间复杂度O(N);

liuajingliu commented 2 years ago

解题思路

低位到高位逐位将数字加在一起
若加法的结果大于等于 1010，把进位的 11 加入到下一位的计算中
代码实现

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
    const res = [];
    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;
        }
        res.push(sum);
    }
    for (; k > 0; k = Math.floor(k / 10)) {
        res.push(k % 10);
    }
    res.reverse();
    return res;
};

复杂度分析

时间复杂度: O(max(n,logk), 其中 nn 为数组的长度
空间复杂度: O(1)

kkwu314 commented 2 years ago

思路 1

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> ans = new ArrayList<Integer>();
        int n = num.length;
        for (int i=n-1; i>=0; i--){
            int sum = num[i]+k%10;
            k/=10;
            if (sum>=10){
                k+=sum/10;
                sum%=10;
            }
            ans.add(sum);
        }
        for (;k>0;k/=10){
            ans.add(k%10);
        }
        Collections.reverse(ans);
        return ans;
    }
}

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

思路 2

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> ans = new ArrayList<Integer>();
        int n = num.length;
        for (int i=n-1; i>=0 || k>0; i--,k/=10){
            if (i>=0){
                k+=num[i];
            }
            ans.add(k%10);
        }
        Collections.reverse(ans);
        return ans;
    }
}

复杂度分析

时间复杂度：O(N) O(max(n,logk))

空间复杂度：O(N)

aladingzl commented 2 years ago

思路

从低位开始，将 A 的每一位与 K 的每一位相加，和大于10时，记录进位 “+1”，将和放到数组中，考虑 K 的长度大于 A 的情况，最后将数组翻转，返回结果

代码

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
   const res = [];
   for(let i = num.length - 1; i >= 0; i--) {
       let sum = num[i] + k % 10;
       k = Math.floor(k / 10);
       if(sum >= 10) {
           k++;
           sum -= 10;
       } 
       res.push(sum);
   }
   for(; k > 0; k = Math.floor(k / 10)) {
       res.push(k % 10);
   }
   res.reverse();
   return res;
};

复杂度分析

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

kbfx1234 commented 2 years ago

989. 数组形式的整数加法

// 91-day1-python

class Solution(object):
    def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        i = len(num) - 1
        carry = 0
        res = []
        while i >= 0 or k != 0:
            x = num[i] if i >= 0 else 0
            y = k % 10 if k != 0 else 0

            sum = x + y + carry
            res.append(sum % 10)
            carry = sum // 10

            i -= 1
            k //= 10
        if carry != 0: res.append(carry)
        return res[::-1]

WANGDI-1291 commented 2 years ago

思路：从低位到高位依次计算，逐位将数字加在一起。任何时候，若加法的结果大于等于10，则进位为1。

代码:

class Solution:

def addToArrayForm(self, num: list[int], k: int) -> list[int]:

n = len(num)

ans = list()

carry = 0

for i in range(n):

    res = k % 10

    sum = num[n-i-1] + res + carry

    carry = 0

    k //= 10 

    if sum >= 10:

        carry = 1

        sum = sum % 10

    ans.append(sum)

if k % 10 == 0 and k // 10 == 0 and carry == 1:

    ans.append(1)

else:

    while k % 10 != 0 or k // 10 != 0:

        sum = k % 10 + carry

        carry = 0

        k //= 10

        if sum >= 10:

            carry = 1

            sum = sum % 10

        ans.append(sum)

    if k % 10 == 0 and k // 10 == 0 and carry == 1:

        ans.append(1)

ans.reverse()

return ans

时间复杂度：O(max(len(num), num_k)), num_k 是k的位数。
空间复杂度：O(max(len(num),` num_k)), num_k 是k的位数。

ghost commented 2 years ago

第一天，慢慢学。。。复杂的思路想不出来

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        return [int(s) for s in str(int("".join(list(map(str,num))))+k)]

kandejiandefeng commented 2 years ago

思路：把整数k裁成数组，两个倒叙，数组length大的循环，位数相加

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
    let kArr = k.toString().split('').map(item => parseInt(item));
    let maxArr, minArr, a = 0;
    if(kArr.length > num.length) {
        maxArr = kArr.reverse();
        minArr = num.reverse();
    }else {
        minArr = kArr.reverse();
        maxArr = num.reverse();
    }
    const minLen = minArr.length
    return maxArr.reduce((arr, item, index) => {
        const n = index > minLen - 1 ? 0 : minArr[index];
        arr.push((item + n + a) % 10);
        a = Math.floor((item + n + a) / 10)
        if(index === maxArr.length - 1 && a === 1) {
            arr.push(1);
        }
        return arr;
    }, []).reverse()
};

RMadridXDH commented 2 years ago

代码

class Solution:
    def addToArrayForm(self, A: List[int], K: int) -> List[int]:
        return list(map(int,str(int(''.join(map(str,A))) + K)))

linrAx commented 2 years ago

思路

将数组从低位到高位加到k上,最后反转

代码

语言支持:java

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new ArrayList<>();
        for(int i = num.length-1;i >= 0|| k >0;i--,k/=10){
            if(i>=0){
                k+=num[i];
            }
            res.add(k%10);
        }
        Collections.reverse(res);
        return res;
    }
}

复杂度分析

时间复杂度 O(max(n,log k)) , n为数组长度

空间复杂度 O(1)

zzzpppy commented 2 years ago

思路：使用arraylist做为新数组存最后的值，从后遍历数组中的每一位数，分别与k的个位相加，如果有进位则用一个carry存进位，每一位最后的值就是k的个位+A数组的值+carry，最后当k为0且A遍历完之后，如果carry有进位则要加入新数组，然后因为新数组是从个位加进新数组中的，最后的结果便要把它反过来。

代码： public List addToArrayForm(int[] A, int K) { List res = new ArrayList<>(); int carry = 0; int l1 = A.length - 1; while (l1 >= 0 || K != 0) { int x = l1 < 0 ? 0 : A[l1]; int y = K == 0 ? 0 : K % 10;

    int sum = x + y + carry;
    res.add(sum % 10);
    carry = sum / 10;

    l1--;
    K = K / 10;
}
if (carry != 0) res.add(carry);
Collections.reverse(res);
return res;

}

时间复杂度：O（n）空间复杂度：O（n）

ray-hr commented 2 years ago

思路

1.列竖式法

2.低位到高位相加

3.考虑进位位

4.取反

代码


class Solution(object):
    def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        p1 = len(num) - 1
        carry = 0
        res = []
        while p1 >= 0 or k != 0 or carry > 0:
            adder1 = num[p1] if p1 >= 0 else 0
            adder2 = k % 10
            sum = adder1 + adder2 + carry
            carry = 1 if sum >= 10 else 0
            sum = sum - 10 if sum >= 10 else sum
            res.append(sum)
            p1 -= 1
            k //= 10
        return res[::-1]

uniqlell commented 2 years ago


/**
使用一个字母表示进位情况
 */
class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer>list = new ArrayList<>();
        int n = num.length;
        int f = 0;
        while(k>0||n>0){
           int  yu = k%10;
           int sum = 0;
           if(n>0)
             sum = num[n-1]+yu+f;
            else sum = yu+f;
            f  =0;
            list.add(0,sum%10);
            if(sum>9)
            f  = 1;
            n--;
            k = k/10;
        }
        if(f>0)
        list.add(0,f);
        return list;
    }
}

alongchong commented 2 years ago

思路

从后往前加，然后翻转

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
    List<Integer> ans = new ArrayList<Integer>();
        int l = num.length ;
        int m = 0;
        for (int i = l-1 ; i >= 0 ; i--){
             m = num[i] + k % 10 ;
             k /= 10;
             if (m >= 10){
                 k++;
                 m -=10;
             }
             ans.add(m);
        }
          for (; k > 0; k /= 10) {
           ans.add(k % 10);
        }
        Collections.reverse(ans);
        return ans;        
   }
}

复杂度分析 时间复杂度：$0(N)$ 空间复杂度：$0(N)$

Tesla-1i commented 2 years ago

class Solution:
    def addToArrayForm(self, num, k) :
        res = []
        for n in num[::-1]:
            k += n 
            res.insert(0, k%10)
            k //= 10
        while k:
            res.insert(0, k%10)
            k //= 10
        return res

z1ggy-o commented 2 years ago

思路

从末位相加即可。

实现的很差。放出来当个反例。

我在实现的时候眼睛紧盯着两个数组进行来进行构建，然后想要把答案存放在已有的两个数组之一。

但是这样的实现需要许多的边际确认，让代码变得十分复杂。而且在最后的结果有进位的情况下，还是要对数组进行扩容，然后做 rotation。得不偿失。

代码

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K);
private:
    vector<int> int_to_arr(int n);
};

vector<int> Solution::addToArrayForm(vector<int>& A, int K)
{
    int carry;
    int sum;
    int idx_a, idx_b;
    vector<int> a, b;

    // edge case
    if (K == 0)
        return A;

    // 1. convert K to array format.
    vector<int> K_arr = int_to_arr(K);

    // K can be greater than A
    if (K_arr.size() > A.size()) {
        a = A;
        b = K_arr;    
    } else {
        a = K_arr;
        b = A;
    }

    // 2. Add small number to large number from the last digit to the highest digit.
    //    The result can have (A.lenght + 1) digits
    idx_a = a.size() - 1;
    idx_b = b.size() - 1;
    carry = 0;

    // add all digit 
    int len = a.size();
    for (int i = 0; i < len; i++) {
        sum = a[idx_a] + b[idx_b] + carry;
        if (sum <= 9) {
            b[idx_b] = sum;
            carry = 0;
        } else {
            b[idx_b] = sum - 10;
            carry = 1;
        }
        idx_a--;
        idx_b--;
    }

    if (carry == 0)
        return b;

    if (idx_a == idx_b) {
        b.insert(b.begin(), carry);
        return b;
    }

    // add the last carry to b
    while (carry != 0 && idx_b >= 0) {
        sum = b[idx_b] + carry;
        if (sum <= 9) {
            b[idx_b] = sum;
            carry = 0;
        } else {
            b[idx_b] = sum - 10;
            carry = 1;
        }
        idx_b--;
    }

    if (carry) {
        b.insert(b.begin(), carry);
    }
    return b;
}

vector<int> Solution::int_to_arr(int n)
{
    int r;
    vector<int> arr;

    while (n != 0) {
        r = n % 10;
        n = n / 10;
        arr.push_back(r);
    }

    reverse(arr.begin(), arr.end());
    return arr;
}

复杂度分析

时间复杂度：O(N)，其中 N 为较长数组的长度。
空间复杂度：O(N)

orderkk commented 2 years ago

function fn(arr, number) { let a1 = Number(arr.join('')); let result = BigInt(a1) + BigInt(number) return String(result).split('') }

Clarence5 commented 2 years ago

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
    const res = [];
    const n = num.length;
    for (let i = n - 1; i >= 0 || k > 0; --i, k = Math.floor(k / 10)) {
        if (i >= 0) {
            k += num[i];
        }
        res.push(k % 10);
    }
    res.reverse();
    return res;
};

复杂度：数组长度O(n)

dudongli commented 2 years ago

思路：,将num和k从个位起逐位相加，最终然后反转res即可。 for i in range(len(num)-1,-1, -1): A = num[i] + k % 10 k = k // 10 if A >= 10: k += 1 res.append(A%10) while k >0: res.append(k%10) k = k // 10 res.reverse() return(res) 时间复杂度O（n）

machuangmr commented 2 years ago

代码

class Solution {
    // 思路： 1、将数组的最后一个元素和k的个位开始相加，
    //       2、大于10 就向前进一位（k的前一位 + 1）
     //        3、 重复以上步骤直到数组和k的位数结束
    public List<Integer> addToArrayForm(int[] num, int k) {
     List<Integer> rest = new LinkedList<>();
    int len = num.length - 1;
    for(int i = len;i >= 0;i--) {
        int total = num[i] + k % 10;
        //取 除过后一位的前面的值
        k /= 10;
        if(total >= 10) {
            //大于10，则前面的值需要进1
            k++;
            total = total % 10;
        }
        rest.add(total);
    }
    while(k > 0) {
        rest.add(k % 10);
        k /=10;
    }
     Collections.reverse(rest);
     return rest;
    }
}

复杂度

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

machuangmr commented 2 years ago

代码

class Solution {
    // 思路： 1、将数组的最后一个元素和k的个位开始相加，
    //       2、大于10 就向前进一位（k的前一位 + 1）
     //        3、 重复以上步骤直到数组和k的位数结束
    public List<Integer> addToArrayForm(int[] num, int k) {
     List<Integer> rest = new LinkedList<>();
    int len = num.length - 1;
    for(int i = len;i >= 0;i--) {
        int total = num[i] + k % 10;
        //取 除过后一位的前面的值
        k /= 10;
        if(total >= 10) {
            //大于10，则前面的值需要进1
            k++;
            total = total % 10;
        }
        rest.add(total);
    }
    while(k > 0) {
        rest.add(k % 10);
        k /=10;
    }
     Collections.reverse(rest);
     return rest;
    }
}

复杂度

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

ghost commented 2 years ago

思路

模拟竖式计算

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new LinkedList<>();
        int idx = num.length-1;
        int carry = 0;
        while (idx >= 0 || k > 0) {
            int x = idx >= 0 ? num[idx] : 0;
            int y = k > 0 ? k % 10 : 0;
            int sum = x+y+carry;
            res.add(0, sum%10);
            carry = sum / 10;
            idx--;
            k /= 10;
        }
        if (carry == 1) {
            res.add(0, 1);
        }
        return res;
    }
}

复杂度分析

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

nonevsnull commented 2 years ago

思路

思路与解法
逐位加；
反向存，最后reverse，不然正向存，每次add数组都得挪位；
心得
第一次fail了因为大意了，这题要注意num和k的长短不一，不能一个for on num解决；

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        int carry = 0, i = num.length - 1;
        List<Integer> res = new ArrayList<>();

        while(i >= 0 || k > 0 || carry > 0){
            int left = i >= 0?num[i]:0;
            i--;
            int right = k % 10;
            k = k / 10;
            int sum = left + right + carry;
            res.add(sum % 10);
            carry = sum / 10;
        }

        Collections.reverse(res);
        return res;
    }
}

复杂度

k因为是常数，其实其长度可以忽略。

time: O(Math.max(num.length, Math.log10(k)+1)) space: O(1)，不算结果

lilililisa1998 commented 2 years ago

思路：先把数字k转化为数组，然后比较两个数组的长度，用0将较短的数组填充到与长数组等长，然后进行等位相加 class Solution(object): def addToArrayForm(self, num, k):

    L_k = []
    while (k / 10 != 0):
        L_k.append(k % 10)
        k=int(k / 10)
    num= list(reversed(num))
    ln=len(num)
    lk=len(L_k)
    if lk>ln:
        q=[0]*(lk-ln)
        num.extend(q)
    elif lk==ln:
        num.append(0)
    else:
        q=[0]*(ln-lk)
        L_k.extend(q)

    for i in range(len(num)-1):
        w=num[i] + L_k[i]
        num[i]=w%10
        num[i+1]=int(w/10)+num[i+1]
    if num[len(num)-1]==0:
        num=num[:-1]
    num = list(reversed(num))
    return num

时间复杂度O(n)

Macvh commented 2 years ago

class Solution(object): def addToArrayForm(self, num, k): """ :type num: List[int] :type k: int :rtype: List[int] 思路：类似于大数相加，先把数字k转化为数组， """ L_k = [] while (k / 10 != 0): L_k.append(k % 10) k=int(k / 10) num= list(reversed(num)) ln=len(num) lk=len(L_k) if lk>ln: q=[0](lk-ln) num.extend(q) elif lk==ln: num.append(0) else: q=[0](ln-lk) L_k.extend(q)

    for i in range(len(num)-1):
        w=num[i] + L_k[i]
        num[i]=w%10
        num[i+1]=int(w/10)+num[i+1]
    if num[len(num)-1]==0:
        num=num[:-1]
    num = list(reversed(num))
    return num

callmeerika commented 2 years ago

思路

新增temp数组存上次计算的进位1，每次取三个数组的末位数进行相加，取余数存进res数组中，直到三个数组都空的时候，计算结束

代码

var addToArrayForm = function(num, k) {
    let cur = String(k).split('');
    let res = [];
    let temp = []
    while(num.length > 0 || cur.length > 0 || temp.length > 0) {
        let a = Number(num.pop() || 0);
        let b = Number(cur.pop() || 0);
        let c = Number(temp.pop() || 0);
        if(a + b + c >= 10) {
            res.unshift((a+ b + c)%10);
            temp.push(1);
        } else {
            res.unshift(a+b+c)
        }
    }
    return res
};

复杂度分析

-时间复杂度：O(n)，其中n为num和k的最大长度 -空间复杂度：O(n)，其中n为num和k的最大长度或最大长度+1

Tiquiero commented 2 years ago

思路

把数组A从后开始循环，整数K也从个位数开始，把两个相加，如果大于10有进位，把进位存carry变量，结果res存数组。每次循环把carry一起相加，最后反转res数组。

代码

var addToArray = function(A, K) {
    const res = [];
    let i = A.length - 1, carry = 0;
    while (i >=0 || K != 0) {
        const x = i >= 0 ? num[i] : 0;
        const y = K != 0 ? K % 10 : 0;
        const sum = x + y + carry;

        res.push(sum % 10);
        carry = Math.floor(sum / 10);
        i--;
        K = Math.floor(K / 10);
    }
    if (carry) res.push(carry);
    return res.reverse();
}

复杂度分析

时间复杂度O（n）
空间复杂度O（n）

LiFuQuan1208 commented 2 years ago

思路：首先循环数组的，取得数组的末位进行相加之后的取余，放进结果数组，然后对相加后的结果除10去掉末位，循环结束后需要把相加的最后结果放进结果的集合中。

代码：

  class Solution {

    public List<Integer> addToArrayForm(int[] num, int k) {

         List<Integer> result = new ArrayList<Integer>();

        int len=num.length-1;

        for (int i=len; i>=0;i--){

            int temp=num[i]+k;

            result.add(temp%10);

             k=temp/10;

        }

        while(k!=0){

            result.add(k%10);

            k=k/10;

        }

        Collections.reverse(result);

        return result;

    }

复杂度分析

时间复杂度：0（n)
空间复杂度：0（n)

1916603886 commented 2 years ago

思路：

将其中一个变为数组，之前两个都变数组，纠结怎么获取索引，现在另一个每次自处自动补零。

代码：

var addToArrayForm = function(num, k) { let s = []; let flag = false; let nl = num.length; while(nl != 0 || k != 0) { let a = 0, b = k % 10 ; if(nl !== 0) a = num[--nl]; k = parseInt(k/10);

        let ans = a + b;

        if(flag) {
            ans += 1;
            flag = false;
        }
        if( ans >= 10) flag = true;
        s.push(ans % 10);
    }
    if(flag) s.push(1);
    return s.reverse();

};

weijie-he commented 2 years ago

思路

模拟真正的加法计算过程

从后往前依次逐位相加，如果 >=10 则进位

代码

public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int len = num.length;
        for (int i = len - 1;i >= 0;i--){
            int a = num[i] + k % 10;
            k /= 10;
            // 如果和 > 10，需要进位
            if (a >= 10 ){
                k++;
            }
            result.add(a % 10);
        }

        // 上面循环做完，只求了结果后len位的值，由于可能进位，所以k可能还有很多位
        for (; k > 0; k /= 10) {
            result.add(k % 10);
        }

        Collections.reverse(result);
        return result;

    }

复杂度分析

时间复杂度：O(N)，遍历数组的时间
空间复杂度：O(N)，存储 result 的空间

HWFrankFung commented 2 years ago

Codes

var addToArrayForm = function(num, k) {
    const res = [];
    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;
        }
        res.push(sum);
    }
    for (; k > 0; k = Math.floor(k / 10)) {
        res.push(k % 10);
    }
    res.reverse();
    return res;
};

leetcode-pp / 91alg-6-daily-check

【Day 1 】2021-12-12 - 989. 数组形式的整数加法 #1

989. 数组形式的整数加法

入选理由

题目地址

前置知识

题目描述

整体思路

解题思路

版本一

Code

复杂度分析

版本二

Code

复杂度分析

题目地址(989. 数组形式的整数加法)

题目描述

前置知识

公司

思路

关键点

代码

语言

思路

代码

复杂度分析

写个C++的版本，基础的大整数求和

思路

时间复杂度O(n)

思路

代码

复杂度分析

思路

代码

思路

解题思路

代码实现

复杂度分析

思路 1

代码

复杂度分析

思路 2

代码

复杂度分析

思路

代码

989. 数组形式的整数加法

代码

思路

代码

复杂度分析

思路

代码

思路

代码

思路

代码

代码

复杂度

代码

复杂度

思路

代码

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

思路：首先循环数组的，取得数组的末位进行相加之后的取余，放进结果数组，然后对相加后的结果除10去掉末位，循环结束后需要把相加的最后结果放进结果的集合中。

代码：

思路：

代码：

思路

代码

复杂度分析

Codes