Leetcode989:数组形式的整数相加 (C语言版本)

在数据结构学习初期,数组形式的整数相加会是我们遇到的一类题型。此类题型对于我们的思维缜密程度有很大考验,虽然它的思路比较简单,但是如果粗枝大叶,马马虎虎,那很多的细节我们就会忽视,从而导致功亏一篑,功败垂成!

对于非负整数 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

来源:力扣(LeetCode)
 

int* addToArrayForm(int* num, int numSize, int k, int* returnSize){
    int kSize = 0;
    int knum = k;
    while(knum)
    {
        kSize += 1;
        knum = knum / 10;
    }
    int len = (numSize > kSize? numSize:kSize);
    int*retArr = (int*)malloc(sizeof(int)*(len + 1));//这里为什么要加一呢?
    原因是有可能出现两数相加大于自身位数的可能  
    比如289+900=1189 这就出现了两个三位数数字相加得到四位数的情况
    int add = 0;
    int pos = 0;
    int i = numSize - 1;    //在数组中个位数字会在最后一位
    int carnums = 0;        //如果有进位出现 我们用这个来代表进位
    while(len--)                            //215 和 806 举例
    {
        int a = 0;          //如此做的原因是有可能k的位数是多于num的此时会造成越界访问的错误
        if(i >= 0)                          //i = 2       //i = 1       //i = 0
        {
            a = num[i]; 
            i--;                         
        }
        add = a + k % 10 + carnums;         //add = 11    //add = 2     //add = 10
          if(add > 9)
        {
            carnums = 1;
            add -=10;
        }
        else
        {
            carnums = 0;
        }
        k = k/10;                           //k = 80     //k = 8      //0
        retArr[pos] = add;                  //ret[0] = 1 //ret[1] = 2 //ret[2] = 0
        ++pos;                              //pos = 1    //pos = 2    //pos = 3
    }
      if(carnums == 1)     //完成对千位数字的保留 这一步极其重要  为什么是1?后面我会做出解释   
        {               
            retArr[pos] = 1;                //retArr[3] = 1
            ++pos;                          //pos = 4
        }
    int left = 0,right = pos - 1;
    int temp = 0;
    while(left<right)
    {
        temp = retArr[left];
        retArr[left] = retArr[right];
        retArr[right] = temp;
        left++;
        right--;
    }
    *returnSize = pos; 
    return retArr;
}

在这里可能大家会对后面的逆序做出提问,为什么我们要做一个逆序,而不是直接将相加好的数字按正序放入数组中?

下面我来举个例子

Leetcode989:数组形式的整数相加 (C语言版本)

 

我是否讲清楚了呢?如果还有疑问的话一定记得告诉我,你的纠正是我进步的巨大动力!!

上一篇:illustrator插件--常用功能开发--标注纵尺寸--js脚本开发--AI插件


下一篇:容器