iT邦幫忙

2022 iThome 鐵人賽

DAY 3
0

學妹看著新的題目列表顯示出來之後,突然發問:「演算法?我聽說過,那好像是大三的必修課吧?學姊妳確定題目的過濾條件沒弄錯?」

「演算法的概念我覺得和數學公式相似,有些簡單的像是國中生也能計算的畢氏定理,但也有的像比較複雜的微積分。我會挑比較簡單的給妳做,畢竟還不知道答錯會有什麼後果⋯⋯」不會拿走腎吧?不會吧?為了避免學妹不聽我話送出錯誤答案,還是在這裡建立一下學姊的威嚴比較好吧!

「比如268. Missing Number這個題目,它要求找出數字陣列中缺漏的數字。妳會怎麼解?」

https://leetcode.com/problems/missing-number/

class Solution {
    fun missingNumber(nums: IntArray): Int {
    }
}

「嗯?一個一個找吧?」

「妳用範例的nums = [3,0,1]說明一遍。」我知道她的意思,但是最好還是用程式的方式表達出來更容易對比出差異。

「就是先找一遍有沒有0,然後再找1,然後發現沒有2,就可以給答案了。」

「如果有2呢?」

「那答案就是3啊!因為題目規定數字上限和陣列大小一樣。」

「歸納一下就是跑一個陣列大小的迴圈,迴圈裡去一個個比對內容,對吧?」

「對啊,怎麼了?」

「嗯,沒有問題,這是其中一個正確答案,不過,當題目規模很大的時候,時間會膨脹,假設每次查看陣列數字都要花一秒鐘。範例才三個數字最多只要花上九秒鐘,但如果是一百個數字就可能花上一萬秒才能出來結果。」因為比對內容其實也用了一個陣列大小的迴圈呢。

學妹臉上寫著「所以呢?我願意等。」

「如果這時候有個人證明他可以一百秒就算出來結果,妳不會很想拿他的算法來用嗎?演算法學的就是怎麼評估和創造一個好方法來減少計算時間和儲存空間。」

學妹哦了一聲。「計算時間我已經知道了,儲存空間又是怎麼一回事?」

「題目裡的陣列也需要空間存放呀,計算過程中也可能產生其他陣列。對電腦來說能節省空間是好事,代表它可以把空間讓給其他程式,比如計算其他題目。」可能是說得有點興奮,覺得有點熱了。我拿出手帕擦汗。

但是在看到學妹也把外套脫掉用手扇風,我很快就領悟到殘酷的事實——室溫上升了!


上一篇
Day02: 僅此一次的資料庫題目
下一篇
Day04: 燒烤危機!
系列文
不解題就不能離開的房間31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言