題目：
給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)括尸。其中巷蚪，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字濒翻。
如果屁柏，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和有送。
您可以假設(shè)除了數(shù)字 0 之外淌喻，這兩個(gè)數(shù)都不會(huì)以 0 開頭。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有雀摘。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)裸删，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
考察點(diǎn)：
- 這是一道LeetCode上非痴笤基礎(chǔ)的一道算法題涯塔。個(gè)人覺得考察點(diǎn)就是，用盡量小的時(shí)間復(fù)雜度去解題清蚀。因?yàn)槿绻婚_始思路是先把鏈表中的數(shù)轉(zhuǎn)成兩個(gè)整數(shù)再sum匕荸，之后再放進(jìn)鏈表里也是一個(gè)思路，但這樣會(huì)循環(huán)兩遍鏈表轧铁。但因?yàn)閮蓚€(gè)鏈表中的個(gè)位每聪，十位百位都是一致的，所以一次循環(huán)，各位相加進(jìn)位药薯，并放入鏈表就可以解決問(wèn)題绑洛。這樣就少做兩次循環(huán)，是更優(yōu)解法童本。
解法：
一真屯、循環(huán)兩個(gè)鏈表對(duì)應(yīng)各位，并相加
- 這里鏈表用數(shù)組表示穷娱，理解算法思路即可
- (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;
}
二绑蔫、先算出兩數(shù)之和，然后放入數(shù)組
- 這個(gè)解法比上一個(gè)復(fù)雜泵额，但是更容易想到配深，畢竟直接相加兩個(gè)數(shù)，要比各位數(shù)相加進(jìn)位要容易嫁盲。但實(shí)際上多進(jìn)行了兩次循環(huán)篓叶。
- (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;
}
}
}
總結(jié)
- 從這道題中我們可以學(xué)到如何更好的利用數(shù)據(jù)和數(shù)據(jù)的結(jié)構(gòu)，而不是簡(jiǎn)單的去處理問(wèn)題羞秤，更好的算法和思路能為程序節(jié)省很多資源缸托，提升效率。
