Find the Duplicate Number 題目: 有一個數字陣列,有n + 1的數字,數字的值為1~n,求陣列中重複的數字 解法: 建立一個陣列,用數字為key,值為bool,數字出現過設定為true,如果數字為true,代表重複出現 code func findDuplicate(nums []int) int { exist := make([]boo...

Remove Nth Node From End of List 題目: 有一個列表,刪除從後面數來第n個節點 解法: 因為我們要找出後面數來第n個,所以我們可以用初始點和出點後往後n個當作依據,同時往後,執到後面那個跑到最後一個,前面的就會是需要刪除節點的前一個節點,把前一個節點的下一個節點,設定為下兩個節點,就可以刪除該節點 code /** * Definition...

Pacific Atlantic Water Flow 題目: 有一個數字矩陣代表了水的高度,上方和左方為太平洋,右方和下方為大西洋,水會往低處流,求哪幾個節點同時流往太平洋和大西洋 解法: 如果使用每個節點往四周跑dfs的話,有很多點需要重複執行,導致timeout,所以定義兩個布林矩陣,為能到達太平洋或大西洋,從邊界開始往四周跑,最後看每個點是否通過太平洋和大西洋 cod...

Maximum Product Subarray 題目: 有一個數字陣列,求子陣列中,乘積最大 解法: 使用動態規劃,定義乘積最大和最小,如果值為正,乘積最大為max(dpMax[i-1]*nums[i],nums[i]),乘積最小為min(dpMin[i-1]*nums[i],nums[i]),如果值為負數,乘積最大為max(dpMin[i-1]*nums[i],nums[i])...

Next Permutation 題目: 有一個數字陣列,找出下一個比較大的最小數,如果都沒有的話,返回最小數 解法: 從後往前看,如果為順序遞增的話,返回排序陣列,如果中間有一數較小,找出該數位置,再由後往前找出最小大於該數的位置,由於後往前一定為遞增,所以從後往前遇到的第一個比較大的數一定是最小的,兩個位置交換,在將i後面的數字排序 code func nextPerm...

House Robber 題目: 一個數字陣列,值代表多少金額,有個小偷偷錢,如果偷相鄰的兩個會觸發警報,求小偷最多能偷多少錢 解法: 當前最大為前一個或是當前值+前第二個誰大,返回陣列最後的值,為最大值 code func rob(nums []int) int { if len(nums) == 1 { return nums[0] } ...

Daily Temperatures 題目: 有一個數字陣列,代表了每天的溫度,返回隔k天之後氣溫比較高該天高的陣列,如果沒有比較高的溫度,天數為0 解法: 用stack把之前的idx存起來,在跟現在的比大小,就可以找出k天 code func dailyTemperatures(temperatures []int) []int { ans := make([]i...

LRU Cache 題目: 有一個暫存只有capacity個容量,如果資料超過容量,會把最早使用過的資料刪除 解法: 一個存容量一個存資料,如果容量不夠還需要存入,把資料最前面的刪除,再存入,因為取得資料也算是使用,所以取得如果有找到,需要把資料放到最後面 code type Node struct { Key int Val int Prev *N...

Minimum Height Trees 題目: n為0~n-1的數字,edges為兩個數字的相連關西,此關西能組成一個樹,求哪個數字為根的話有最小的深度 解法: 因圖型一定為樹,所以找出此樹最外層的點,最外層的點為只有一個相鄰的數字,將最外層的點剝離後,判斷剩下的數字是否只剩下一個或兩個,如果是的話,返回答案,如果不是的話,將繼續把最外層的數字剝離 code func f...

Find All Anagrams in a String 題目: 有兩個字串,s和p,找出s字串中和p字串相似的子字串,並返回子字串開始的idx陣列 解法: 先找出p字串中字母的出現次數為P,再將s陣列從頭掃過一次,P將字母--,如果該字母為0的話將,idx刪除,如果i大於等於p的長度,需把前面的字母加回來,如果P長度為0的話,表示為相似字串,將idx-p長度+1存入結果中 ...