[LeetCode] - Add Two Num

發表於   |  

Question:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

此題需了解liked list的操作，另外必須注意carry的處理，這邊使用了三種方式來處理，第一種為利用一般的乘除餘數運算，第二種將乘除餘數運算改為加減運算來加速，第三種建立table將運算轉換成查表方式，利用不需任何的運算來加速

理論上執行時間1 > 2 > 3，不過實際上 1 = 2 > 3，有可能是因為運算量不夠大到讓乘除運算和加減運算的差異顯現出來，不過完全不經過任何運算還是可以小幅度的縮減時間

乘除及餘數運算

從兩個linked list的node0 node相加且取除10的餘數代表結果，取除10的商代表是否有carry，carry需要記錄下來，下一個mode作相加時必須加上去，反覆對下一個node作相同的運算，直到兩個linked list都到結尾(NULL)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) { //(1)
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val; //(2)
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry; //(3)

		if (sum >= 10) { //(4)
			carry = 1;
			sum %= 10;
		} else {
			carry = 0;
		}

		if (pResult == NULL) { //(5)
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next; //(6)
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) { //(7)
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

(1)必須兩個linked list都指到NULL才算結束

(2)建立兩個local變數來取得兩個node需相加的數字，但若遇到其中一個node先指到NULL，那被拿來相加的值會是0

(3)總和為兩個值相加，需再加上carry，預設為0，若某個node有carry，下一個node就會被加上去

(4)如果總和大於10代表有carry，另外結果需改為除以10的餘數

(5)將運算後的結果放到將回傳的linked list

(6)若指到的node已經是NULL，則不跳到下一個node，因為不存在，跳過去會造成系統crash

(7)如果結束後carry不為0則必須處理

放到leet code上執行的結果為35ms，超過68.34%的上傳程式

錯誤用法

如果有參考其他人寫的範例的時候，可以看到一種寫法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	pResult = (struct ListNode *)malloc(sizeof(*pResult)); //(1)
	pCurr_node3 = pResult;
	pCurr_node3->next = NULL;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry;

		if (sum >= 10) {
			carry = 1;
			sum %= 10;
		} else {
			carry = 0;
		}

		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult)); //(2)
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = sum;
		pCurr_node3->next = NULL;

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult->next;
}

主要是將第一個node的malloc拉到最外面，迴圈內的malloc就可以不用作原本的NULL判斷，最後回傳的時候再回傳第二個node的位址即可

這方法看似可以省掉一個判斷條件，但事實上是有問題的，因為回傳的linked list的free工作是交給caller的，如果回傳的是第二個node，那caller在free的時候會遺漏掉第一個node，造成此段記憶體無法再被使用，直到程式結束

如果要使用這種寫法，那必須在function裡就將第一個node給清掉

使用加減運算

就硬體角度而言，加法減法運算會比乘除餘數運算來的快，尤其是在沒有乘法器和除法器的狀況下更加明顯，這邊可以修改的就是取除以10餘數的地方，因為這邊的加總最多不會超過19(9 + 9 + 1(carry))，所以可以改寫成-10就是餘數了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry;

		if (sum >= 10) {
			carry = 1;
			sum -= 10; //(1)
		} else {
			carry = 0;
		}

		if (pResult == NULL) {
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

(1)取除以10的餘數改寫成-10，因為此例總合不會超過19

不過執行結果並沒有顯著的增加效率，可能是這不是太複雜且頻繁的運算，不足以顯現出明顯的差距

放到leet code上執行的結果為35ms，超過67.08%的上傳程式

使用Table取代運算

乘除運算改為加減運算在這裡並沒有辦法顯著的增加執行速度，不過我們可以利用建立Table的方式，將所有的運算取代成查表的方式，例如我們想要得到{0, 1, 2} + {0, 1, 2}裡面9種組合的運算結果，就可以建立一個像下面這樣的Table

所以就可以將 1 + 1 = 2 ==> [1][1] = 2, 1 + 2 = 3 ==> [1][2] = 3 …

因此我們針對此題建立一張{0 ~ 9} + {0 ~ 9}的Table，但必須考慮到carry的問題，因此這張Table必須有carry的資訊，但是加總之後有可能必須再加上之前低位的carry，因此需再建立一張 {0 ~ 9} + {0, 1} (carry)，相關資訊的Table，直接看程式的Table會更清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct AddTableEle {
	unsigned char carry;
	int sum;
};

struct AddCarryTableEle {
	unsigned char carry;
	int sum;
};
//Table1
const struct AddTableEle AddTable[10][10] = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}},
									 	{{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}},
									 	{{0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}},
									 	{{0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}},
									 	{{0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}},
									 	{{0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}},
									 	{{0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}},
									 	{{0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}},
									 	{{0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}},
									 	{{0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}}
										};
//Table2
const struct AddCarryTableEle AddCarryTable[10][2] = {{{0, 0}, {0, 1}},
									 			{{0, 1}, {0, 2}},
									 			{{0, 2}, {0, 3}},
									 			{{0, 3}, {0, 4}},
									 			{{0, 4}, {0, 5}},
									 			{{0, 5}, {0, 6}},
									 			{{0, 6}, {0, 7}},
									 			{{0, 7}, {0, 8}},
									 			{{0, 8}, {0, 9}},
									 			{{0, 9}, {1, 0}}
												};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0, flag;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = AddTable[val1][val2].sum;	//(1)
		sum = AddCarryTable[sum][carry].sum; //(2)
		carry = AddCarryTable[AddTable[val1][val2].sum][carry].carry; //(3)
		carry |= AddTable[val1][val2].carry; //(4)

		if (pResult == NULL) {
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

Table1 : 以AddTable[3][5] = {0, 8}為例，代表(3 + 5) % 10 = 8，且carry為0，AddTable[6][6] = {1, 2}為例，代表(6 + 6) % 10 = 2，且carry為1

Table2 : 以AddCarryTable[5][0] = {0, 5}為例，代表經過Table1得到結果為5且加上carry = 0，會得到carry = 0，及(5 + 0) % 10 = 5的結果，以AddCarryTable[9][1] = {1, 0}為例，代表經過Table1得到結果為9且加上carry = 1，會得到carry = 1，及(9 + 1) % 10 = 0的結果

(1)透過Table1得到兩個值相加之後取個位數的值

(2)將經由(1)取到的值透過Table2得到加上先前預算是否有殘留carry後取個位數的值

(3)(4)取得此次的運算是否會產生新的carry

執行結果縮短了約3ms

放到leet code上執行的結果為32ms略低於前面兩種方法，超過84.19%的上傳程式