【iOS每日算法】两数相加，给出两个非空的链表用来表示两个非负的

题目：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

考察点：

• 这是一道LeetCode上非常基础的一道算法题。个人觉得考察点就是，用尽量小的时间复杂度去解题。因为如果一开始思路是先把链表中的数转成两个整数再sum，之后再放进链表里也是一个思路，但这样会循环两遍链表。但因为两个链表中的个位，十位百位都是一致的，所以一次循环，各位相加进位，并放入链表就可以解决问题。这样就少做两次循环，是更优解法。

解法：

一、循环两个链表对应各位，并相加

• 这里链表用数组表示，理解算法思路即可

- (NSArray *)sumNum:(NSArray<NSNumber *>*)numArr1 withNum2:(NSArray<NSNumber *>*)numArr2 {
    NSInteger len1 = numArr1.count;
    NSInteger len2 = numArr2.count;
    NSMutableArray *totalArr = [NSMutableArray array];
    for(int i = 0; (i < len1 || i < len2); i++) {
        int sumNum = (i < len1 ? [numArr1[i] intValue] : 0) + (i < len2 ? [numArr2[i] intValue] : 0) + (i < totalArr.count ? [totalArr[i] intValue] : 0);
        if(sumNum < 10) {
            totalArr[i] = @(sumNum);
        } else {
            totalArr[i] = @(sumNum % 10);
            totalArr[i + 1] = @(1);
        }
    }
    return totalArr;
}

二、先算出两数之和，然后放入数组

• 这个解法比上一个复杂，但是更容易想到，毕竟直接相加两个数，要比各位数相加进位要容易。但实际上多进行了两次循环。

- (NSArray *)twoSumNum:(NSArray<NSNumber *>*)numArr1 withNum2:(NSArray<NSNumber *>*)numArr2 {
    int num1 = 0;
    int num2 = 0;
    for (int i = 0; i < numArr1.count; i++) {
        num1 = num1 + [numArr1[i] intValue] * pow(10, i);
    }
    for (int i = 0; i < numArr2.count; i++) {
        num2 = num2 + [numArr2[i] intValue] * pow(10, i);
    }
    int totalNum = num1 + num2;
    NSMutableArray *totalArr = [NSMutableArray array];
    for(int i = 0;;i++) {
        int num = (totalNum % [@(pow(10, i + 1)) intValue]) / [@(pow(10, i)) intValue];
        int yushu = totalNum / [@(pow(10, i + 1)) intValue];
        totalArr[i] = @(num);
        if(yushu <= 0) {
            return totalArr;
        }
    }
}

总结

• 从这道题中我们可以学到如何更好的利用数据和数据的结构，而不是简单的去处理问题，更好的算法和思路能为程序节省很多资源，提升效率。