[leetcode] Two sum，初次體驗 leetcode

發表於

前言

自從創了帳號後都沒有認真的看裡面的題目

以前玩 UVA 的時候，頭腦動得很多，現在上班後有時候變成像是碼農一樣，只在專注的解問題，儘量求速度求 KPI

有時候還是應該檢視自己寫的程式到底是不是效能最好，是不是記憶體用量最低，或是這種寫法好不好維護，易讀性如何等等

當然在做 code review 的時候還是可以提醒同事或是讓同事指點程式寫得好不好，成本高不高

但因為我還是有點不懂裡面的運作方式，所以就先找最簡易的一題，先看看 leetcode 怎麼運作吧

Leetcode 的運作模式

leetcode 主要似乎不太苛求 IO 的操作，他比較專注於演算法與系統設計
所以給你一個核心程式的 prototype ，在不更動 prototype 的情況下撰寫內部的核心演算法
之後 runtime 會透過此宣告的 IO 去執行函式，並取得解答

Problem description

1
2
3
4
5
6
7
8
9
10
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我的解法

brute force (暴力解)

簡單說就是使用巢狀迴圈處理

如果用上面的 test case 來說明的話

就是會依循 [0, 1], [0, 2], [0, 3] 一直進行兩數和解
之後若相同就 return array index，這樣而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {  
    int i, j;
    int *a = (int *)malloc(sizeof(int) * 2);
    
    for (i=0; i<numsSize; i++) {
        for(j=i+1; j<numsSize; j++) {
            if ((nums[i] + nums[j]) == target) {
                returnSize[0]=2;
                a[0] = i;
                a[1] = j;
            }
        }
    }
    return a;
}

而我們先看一下 function prototype

1
int* twoSum(int* nums, int numsSize, int target, int* returnSize)

我們可以從這個 prototype 知道

  • nums 是 runtime 會傳入的陣列
  • numsSize 是 runtime 會傳入的陣列大小
  • target 是兩數和的解
  • returnSize 我覺得這個沒有意義，就是 return 陣列的大小

然後這題他給我的時候 prototype 還少了一個 int* returnSize，讓我一直 compiler error，感覺不是很好……

調整解法：從 Loop 直接 return

這應該是最簡易的優化了，也就是說，我們本來是跑完全部總共 O(n^2) 的方式，這時候我們判斷好結果後就直接 return pointer 出去就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {  
    int i, j;
    int *a = (int *)malloc(sizeof(int) * 2);
    
    for (i=0; i<numsSize; i++) {
        for(j=i+1; j<numsSize; j++) {
            if ((nums[i] + nums[j]) == target) {
                returnSize[0]=2;
                a[0] = i;
                a[1] = j;
+		return a;
            }
        }
    }
-   return a;
+   return NULL;
}

submit 所花的執行時間可以從 210 ms 進展到 135 ms