[C] Project LeetCode 365–0x02

C語言的自我練習計畫

*代表之後還需要再重新練習幾次

[6/365] 2022.08.09

Question 88.Merge Sorted Array

Solution

• Runtime: 0 ms
• Memory Usage: 6 MB

Review

因為是在nums1 in-place修改，所以如果n=0就可直接return。m=0也是直接搬過去就可以了。原本打算直接指過去，但因為nums1不是**所以沒辦法這樣做。

在下面把m當作最後有效位數，如果i>m就表示nums1已經排完了，只剩下nums2的直接放進去就好。最後如果m加到跟nums1Size一樣就代表全部排完了。以下psudo code。

for (i = 0 ~ n1Size)
    if (n2[j] >= n1[i] && i< lastValidDigit) continue
    else
        for (k = m-1 ~ i) n1[k+1]=n1[k]
    n1[i] = n2[j]
    m++; j++;
    if (m==n1Size) return 

*[7/365] 2022.08.10–08.14

Question 118.Pascal Triangle

Solution

• Runtime: 0 ms
• Memory Usage: 5.8MB

Review

這題卡了很久，一部分原因是對於pointer of pointer還不太熟練，另一部份是一直弄不清楚*returnSize, **resturnColumnSizes想要回傳什麼。以numRows = 5來舉例的話，矩陣會長以下這樣。

ret_arr = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
returnSize = 5
retutnColumnSize = [[1, 2, 3, 4, 5]]

原本一直以為 returnColumnSize = [[1], [2], [3], [4], [5]] ，後來參考其他人的作法才發現題目要的不是這個意思，知道題目的要求之後要完成應該就容易許多了。

程式碼的註解是另一種returnColumnSize 的寫法，直接 malloc在returnColumnSize裡面，或是也可以向上面寫的一樣另外配置一個位置再指定給returnColumnSize

[8/365] 2022.08.15

Question 119.Pascal Triangle II

Solution

• Runtime: 0 ms
• Memory Usage: 5.7MB

Review

做出上一題之後，加上題目需要只是一維的陣列，這題就容易許多了。

基本上還是要從第一層開始往下走，只是不需要全部都存起來。我的做法是用兩個array，一個存第n-1層( pre_arr)的數字，接著利用n-1層的數字就可以算出第n層( ret_arr)；再把 ret_arr的內容放入 pre_arr ，這樣就能一直不斷往下計算。

*[9/365] 2022.08.16–2022.08.22

Question 108. Convert Sorted Array to Binary Search Tree

Solution

• Runtime: 16 ms
• Memory Usage: 16.2MB

Review

這題卡了一個快禮拜，因為對BST不夠熟練，所以花了點時間複習Tree的操作(上完課就還給老師QQ，甚至連應該用遞迴都忘了)，後來實在沒想法只好參考其他人的做法，才發現應該用遞迴。這題的關鍵在於node的操作跟遞迴的寫法，後來抓到要怎麼遞迴之後問題也就迎刃而解，

*[10/365] 2022.09.01–02

Question 121. Best Time to Buy and Sell Stock

Solution

• Runtime: 274ms
• Memory Usage: 12.9MB

Review

這題也是卡了好一陣子，加上中間一週跑去休假。我自己一開始的做法是先建立一個從0~pricesSize-1的陣列當作index，然後跟prices一起做排序，再分別從頭尾去做比對，但這樣在遇到資料量大的測資時就會超過時間限制（既然沒辦法通過就不放程式碼上來了）。後來看了討論區的其他的作法，直接從頭開始走過一次，遇到最小的當作買入就好了，其實沒有想像中的複雜XD