[C] Project LeetCode 365–0x01

C語言的自我練習計畫

[1/365] 2022.08.03

Question 1. TwoSum

Solution [O(n²)]

• Runtime: 155 ms
• Memory Usage: 6.5 MB

Review

相較其他語言少了點工具，用C最直觀的作法就是暴力解。後來看到其他做法可以做到O(nlogn)，先把整個 nums 先排序，再用左右逼近的方法求解，基本上就是排序的複雜度+n。以下pseudo code

sort(nums);
while(nums[lo] + nums[hi] != target){
    if(nums[lo] + nums[hi] < target) lo++;
    else hi--;
}

[2/365] 2022.08.04

Question 26. Remove Duplicates from Sorted Array

Solution [O(n), O(1)]

• Runtime: 11 ms
• Memory Usage: 7.8 MB

Review

• 其他參考做法

先把cnt, i都設為1，跟i-1比較可以避免最後一個溢位的問題，也就可以省去上面 if(i+1 == numsSize-1) 那一段。cnt++可以直接寫進*(nums)裡面。以下C code

int removeDuplicates(int* nums, int numsSize){    
    if (numsSize < 2) return numsSize;
    int cnt = 1;
    for(int i=1; i<numsSize; i++){
        if (*(nums+i) != *(nums+i-1)) *(nums + (cnt++)) = *(nums+i);
    }
    return cnt;
}

[3/365] 2022.08.05

Question 27. Remove Element

Solution [O(n), O(1)]

• Runtime: 0 ms
• Memory Usage: 5.9 MB

Review

基本上跟昨天 Remove Duplicates from Sorted Array 思路差不多，用count計算有效元素的index，然後把第i的跟val不一樣的值寫在count的位置。

[4/365] 2022.08.06

Question 35. Search Insert Position

Solution [O(log n), O(1)]

• Runtime: 6 ms
• Memory Usage: 6.2 MB

Review

一開始直接用O(n)的方法寫，所以就用while從0開始一個一個找，找到比較大的就停下來 。後來才看到題目要求要用O(log n)，改用for從頭尾一起找。但還是沒有到O(log n)

[5/365] 2022.08.07–08

Question 66. Plus One

Solution [O(n), O(1)]

• Runtime: 0 ms
• Memory Usage: 5.8 MB

Review

最一開始先想說用數字的方法寫，把每一位數乘以10的i次方，取出來之後+1再放回去，但後來發現數字太大會超過int 跟 long 的大小。才改成現在的做法。

在malloc的時候要注意，一開始沒有把digitsSize括號起來，一直報錯…

ret_arr = (int*)malloc((digitsSize+1)*sizeof(int));

基本上概念是先判斷整個矩陣需不需要進位，全部都是9才需要開一個digitsSize+1大小的矩陣。然後從digits最後一位開始，先+1。再來判斷有沒有要進位，要就把這位寫成0，然後把進位的flag設1；沒有要進位的話剩下的就照抄，把進位的flag歸0，依此類推。