Koufuchi's blog

題目： 官網題目連結 根據題目敘述，會給一個鍵為 N，值為 K 的非空陣列 A。其中 N 表示秒數，K 表示位置，也就是第 N 秒時會有樹葉掉落到位置 K 上。 題目還會給一個整數 X 表示終點，你必須找出最少第幾秒時 1~X 的位置上都會有落葉。 例如輸入 A=[1, 3, 1, 4, 2, 3, 5, 4]， X=5。 最少在第 6 秒時會有樹葉掉落到位置 5，且位置 1~5 都有樹葉，所以答案為 6。 如果 1~X 永遠不可能都有樹葉的話，你必須回傳 -1。 N 是範圍 [1~100000] 的整數。 陣列 A 裡的所有元素都是範圍 [1~X] 的整數 解法： 這題不像 PermMissingElem 一樣可以用等差數列去減，因為樹葉掉落的位置可能會出現重複的，所以始終是必須記錄走過的不重複合法位置有哪些，空間複雜度最低只能 O(N)。 而由於我們有紀錄走過的不重複合法位置，所以可以得知當你剛好找到第 X 個不重複合法值時，他的時間就會是答案，總共只需遍歷一次。 時間複雜度 O(N) 空間複雜度 O(N) PHP 程式碼： 我的解答 單元測試

💡 適用於 mac os 且使用 Homebrew 管理 php 環境 核心為以下兩行 : 12brew unlink [email protected] brew link -f [email protected] 每次都要記很煩所以寫了個簡單 script : GitHub - Koufuchi/php_version_switcher 用命令行移動到 script 所在目錄，執行以下語法並指定版本即可切換： 1. ~/ps.sh 7.3 # 檔名自己取，執行時後面餵版本參數，如果參數錯誤則會列出你本機安裝的所有版本 或是真的超懶，就在 ~/.zshrc 中加入 : 1export PATH="$PATH:/<your script path>/" # script 所在目錄 之後打開 terminal 後就直接輸入以下就好 : 1ps.sh 7.3 注意所有指令都會跑去你指定的目錄對，所以其實不太推薦這樣玩

題目： 官網題目連結 根據題目敘述，會給一個由 N 個不同整數組成的陣列 A。該陣列包含 [1~(N+1)] 範圍內的整數，這表示正好缺少一個 [1~(N+1)] 的元素，你必須找出他。 例如輸入 A=[2, 3, 1, 5] ，答案應為 4。 N 是範圍 [1~100000] 的整數。 陣列 A 裡的元素都是不重複的。 陣列 A 裡的元素都是範圍 [1~(N+1)] 的整數 解法： 也許你一開始會想到排序後遍歷，但排序需要 O(Nlog N)，所以顯然應該有更好的解法。 再來也許會想到定義一個鍵為 1~(N+1) 的結果陣列，只要遍歷到就從結果陣列中刪除，那麼最後剩下的那個就是答案，這樣的時間複雜度似乎已達標，但是空間是否能用得更少呢? 觀察題目可以發現 1~(N+1) 其實就是等差為 1 的等差數列，那麼我們其實一開始就可以預期他們的總和是多少了，只要用預期總和去減 A 的所有元素就能求解。 這邊需要注意的是公式不要套錯，因為題目其實有少給你 1 個元素，所以正確的長度和高度應是 A 的元素數量再 +1。 像這樣用公式解就能降低空間複雜度到 O(1)。 雖然題目主旨是時間 ...

題目： 官網題目連結 根據題目敘述，會給一個由 N 個不同整數組成的非空陣列 A。遍歷到 A 的任一非 0 索引 P 時，會將陣列分成 A[1], A[2],…, A[P−1] 以及 A[P]、A[P+1],…, A[N−1] 兩個部分，其差異指的就是這兩部分各自加總後相減的絕對值。 例如輸入 A=[3, 1, 2, 4, 3] 時，可能的 P 值就會是 1~4，且他們的差異會是: P = 1，差異 = |3 − 10| = 7 (3 vs 1+2+4+3) P = 2，差異 = |4 − 9| = 5 (3+1 vs 2+4+3) P = 3，差異 = |6 − 7| = 1 P = 4，差異 = |10 − 3| = 7 你的方法必須能吃這個陣列，並返回其中最小的差異，以上述例子來看就是 1 N 是範圍 [2~100000] 的整數。 陣列 A 裡的元素都是範圍 [-1000~1000] 的整數 解法： 這題敘述挺長的，有可能會一時不知道怎麼下手，但其實原則很簡單，就是一樣想辦法遍歷一次就做完。 我們會發現從 P 到 P+1 時，相當於右邊減去 A[P]，而 ...

題目： 官網題目連結 根據題目敘述，會給三個變數，起點是 X，終點是 Y，每次移動距離是 D，需求出最少需要幾次 D 才能剛好抵達或超過終點。 題外話，為甚麼官方是寫 FrogJmp 而不是 FrogJump 啊。 例如輸入 X=10, Y=85, D=30，答案應為 3。 X, Y, D 都是範圍 [1~1000000000] 的整數。 X <= Y。 解法： 既然題目都歸類在 TimeComplexity 裡了，感覺就是注重效能的題目。 實際上也沒錯，看起來就是想騙人去用迴圈去每次減 D，因為這樣在 D 為 1 的時候你的時間複雜度就會提高到 Y-X。 而其實你根本只需要用 (Y-X)/D 再無條件進位就能達到答案，時間複雜度 O(1)。 根本就是小學數學題。 以前在面試時有遇過類似題目，面試官是說希望知道你在看起來秒殺的題目下會不會忽略掉甚麼才是最佳解。 時間複雜度 O(1) 空間複雜度 O(1) PHP 程式碼： 我的解答 單元測試

題目： 官網題目連結 根據題目敘述，會給一個非空陣列 A，包含了 N 個整數，索引從 0 開始。N 為奇數，其中除了唯一一個元素之外，其他每個元素都可以與陣列中另一個有相同值的元素配對，目的就是找出這個無法配對的元素。 例如輸入 A=[9, 3, 9, 3, 9, 7, 9]，答案應為 7。 N 為範圍 [1~1000000] 的奇數。 陣列 A 的每個元素都是 [1~1000000000] 範圍內的整數。 解法： 光看題目第一時間其實想到 LeetCode 的 20. Valid Parentheses，那時是用 stack 解的，不過這題並沒有那麼複雜，不需要考慮開關符號的問題。 再來會想到的是記憶法，用數字種類當索引，用出現次數當值。當初會這樣想是因為題目的範例暗示了同個數字是可以出現超過 2 次的，於是潛意識想要知道每種數字出現幾次，這樣的優點是可以在時間和複雜度 O(N) 的情況下獲得完整資訊。 寫到一半才想到，目的只是要回傳那個沒有重複的值啊，我多做那麼沒用的事情幹嘛! 於是目標會希望改成只對 A 遍歷 1 次，且減少空間的用量，這時候就會發現我並不需要紀錄每種數 ...

題目： 官網題目連結 根據題目敘述，輸入整數陣列 A 和一個整數 K ，將每個陣列元素往右移 K 次。 例如輸入 A=[3, 8, 9, 7, 6], K=3，答案應為 [9, 7, 6, 3, 8]。 N 和 K 都是範圍 [0~100] 的整數。 陣列 A 的每個元素都是 [−1000~1000] 範圍內的整數。 題目特別說專注在正確性而不是效能。 解法： 共做 K 次，每次將陣列的最後一個元素改放到最前面即可。 由於 php array 的特性，用 array_pop() 取出最後一個元素為時間複雜度 O(1)， 但使用 array_unshift() 將元素放到最前面時，需要時間複雜度 O(N) 來保持索引順序，其中 N 為陣列元素數量。 可以複習一下我的另一篇文章 : PHP Array 時間複雜度 O(N * K) 空間複雜度 O(N) / O(N * K) – 我不確定重複的 array_unshift() 會不會用到相同的空間來搬移陣列，之後可以實驗 PHP 程式碼： 我的解答 單元測試

題目： 官網題目連結 根據題目敘述，會需要將輸入的整數 N 轉成二進位，並找出任意夾在兩個 1 中間的最大 0 總數。 例如輸入 529，轉成二進位是 1000010001，答案就是 4，而如果沒有任何 0 是夾在兩個 1 中間的，則會回傳 0。 N 是範圍 [1~2147483647] 的整數。 解法： 先把數字轉成字串再遍歷一次即可，這邊要注意的陷阱是容易疏忽最後一個 1 的判斷。 例如轉成二進位是 1001000 時，由於最後面並沒有結尾的 1 把三個 0 夾住，所以答案是 2 不是 3。 所以重點會在於何時將當前計算的最大值轉成合法的最大值。 時間複雜度 O(N) 空間複雜度 O(1) PHP 程式碼： 我的解答 單元測試

背景 一般來說快取是將會常被取用的資料暫存起來，避免重複的 I/O 以加快速度，而你的空間是有限的，勢必會需要淘汰一些既有資料才能放新的，而快取檔案置換機制就是決定哪些資料會優先淘汰，以最大保持你的快取命中率。 LRU(Least Recently Used) Cache 最近最少使用算法，顧名思義就是會優先清除掉沒被使用的資料。 規則： 最先進入快取的 key 會最先被刪除。 若某一 key 被取用或更新值，則該 key 會視為新寫入，因為要將其被刪除的順序降到最低。 (額外) 由於會使用快取就是為了提高速度，所以實作上必須要求放值和取值都必須達到時間複雜度O(1) 範例： 當你依序放入 a, b, c 三個資料時，他們的優先刪除順序就是 1, 2, 3，所以當空間不夠需要刪除資料時會先刪掉 a，因為他最先加入而且從來沒被取用過。 讓我們時光倒流回到刪除前，現在有 a, b, c 三個資料時，他們的優先刪除順序就是 1, 2, 3，而這時有人取用了 a，因為 a 被取用了， 他的刪除優先順序會從 1 降成 3，而 b, c 的刪除優先順序則會被提升，所以 a, b, c ...

先說結論： PHP 的 array 其實是有序的 HashMap 以一般學習資料結構而言： 陣列（Array）：使用一連串連續的記憶體空間來存資料。同一陣列只會存放同一種資料型態的值，並用索引來記錄順序。優點是查找時間複雜度為 O(1)，缺點是只要移動資料順序或陣列空間不夠用時（需創建另一串更大的連續記憶體來做搬移），時間複雜度會變成 O(N)。 哈希表（HashMap）：先定義好鍵值的型態，並且是無序的。當你放值時會用 hash function 算出雜湊值，以對應放值的記憶體位址。遇到碰撞時不同語言會用不同的方式解決，例如常見的拉鍊法。優點是查找和存放的時間複雜度都是 O(1)，缺點是效能會隨使用的 hash function 不同而有差異，且當哈希表容量不足時，會定義一個新的哈希表，並把舊的鍵值移過去，等於每個舊鍵都要重跑一次 hash function，成本大幅提高。 PHP Array： 在 PHP 裡基於 C 語言將兩者實作成關聯陣列，名稱還是叫 Array。可接受存放不同型態的鍵值對，且為有序的 HashMap 補充： 以 JAVA 而言，HashM ...