[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