Claire's Blog

題目內容 題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/ 題目解釋 在這個例子中，最後要建造的牆的寬度是 N = 9 米，高度在不同的位置上是不同的。牆的左端高度是 H[0] = 8，右端高度是 H[8] = 8。 這道題的目標是計算構建牆所需的最小石塊數，因此我們需要找到一種方法來計算構建牆所需的石塊數。我們可以使用一個堆疊來維護已經堆疊的石塊，然後從左到右遍歷數組，將石塊一層一層地堆疊起來。當當前高度高於前面高度時，應該添加一個新石塊。在堆疊石塊時，我們應該儘可能地重複使用現有的石塊，以減少新石塊的使用量。 你要建造一堵石牆，牆長 N 公尺，而牆的厚度是恆定的，但不同的位置高度不同。牆的高度由一個長度為 N 的正整數數組 H 指定。H[i] 表示牆的左端到右側 i 公尺處的高度。特別地，H[0] 是牆的左端高度，H[N-1] 是牆的右端高度。 石牆應由長方體石塊建造，所有面都是矩形。你的任務是計算構建牆所需的最小石塊數。 比方說，給定一個包含 N = 9 個整數的數組 H： H[0] = 8 H[1] =…

題目內容 題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/ 題意分析 又是一個有故事的題目，最討厭了，不要管魚的故事的話，大概就是有一個循序數列會從0~N-1這樣子，例如[1,2,3,4,5]，但是不會照著順序排列，而是會打散著的排列，如[4,3,2,1,5]，然後有另一個陣列B，會指定該數字是往上還是往下，如[0,1,0,0,0]，接著往下的若是遇到往上的，就比大小，刪掉較小的數字。 然後回傳最後剩下的數字的數量 解題紀錄 這是我第一次的解題紀錄 只拿了12分，慘不忍睹，應該有思考邏輯上的錯誤。 仔細想一下這一題，我覺得應該會是2N左右的複雜度，就是往上遍歷一次、往下遍歷一次。往下遍歷時，選擇方向為下的，且之後的數字的方向為上的，把該吃掉的吃掉。接著再從下往上一次，選擇方向為上的，且之前的數字的方向為下的，把該吃掉的吃掉，應該就會試剩下的了。 下面為嘗試的實作程式碼 25%，慘不忍睹+1。 我發現問題是他們往上或往下可能不會只有兩次，而是會不停地變換方向，所以應該會需要把這樣的程式碼抽出來，然後使用迴圈或遞迴的去呼叫。但是比較慘的是，下面的效能測試其實是超時的，若是再透過遞迴或者迴圈，整個效能應該會更差。 觀察之後，因為我是整個陣列去掃，而事實上，他們往上或往下的範圍不會是整個陣列，而會是遇到與自己方向不同的範圍。所以我覺得應該不會是完整的掃過兩次迴圈，而是會有兩層的迴圈，然後根據現在的方向，掃到以自己方向為準最多可吃掉的位置做停止，在構想上應該比較類似我第一次的做法。 邏輯正確了，但是效能不佳…要來優化了! 上面的作法會耗時間是因為下面的原因 為了解決這個問題，我們可以使用一個堆疊，它用於記錄下游游動的魚，這些魚還沒有被吃掉。從頭到尾遍歷所有魚，並將所有向上游動的魚推入堆疊。如果遇到向下游動的魚，則將其與堆疊中的魚進行比較。如果堆疊中的魚較小，則將其彈出，並繼續與新的堆疊頂部進行比較，直到它遇到較大的魚，或者堆疊為空。 在這個算法中，堆疊中的魚保證向下游動，因此它們是可以被吃掉的魚。當向上游動的魚遇到堆疊頂部的魚時，它們的大小也被比較。如果它們相等，它們都可以保持存活，因為它們不會相互吃掉。如果向上游動的魚比堆疊頂部的魚大，則堆疊中的魚會被吃掉，否則向上游動的魚會被堆疊頂部的魚吃掉。在此過程中，我們不斷更新堆疊的內容，以便在下一輪比較中使用。 最後，堆疊中剩下的所有魚都可以保持存活，因為它們沒有遇到向下游動的魚，或者在它們前面的向下游動的魚都比它們大。 https://app.codility.com/demo/results/trainingHMNQVG-XRN/

題目內容 題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/ 解題紀錄 感覺很簡單的題目，先隨便寫一個答案 這種簡單的題目真的就是陷阱多，這應該是也要考慮到})]為開頭的狀況，要過濾掉這種CASE 這種考細心度的我最吃虧了= =但是還是過了(https://app.codility.com/c/run/training2C9S74-MHH/)

題目內容 題目頁面:  https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/ 解題思考 這個是在算N個圓是否有交集，例如以題目來說，A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0單純以範圍來看，會是這樣的範圍陣列[ -1, 1 ], [ -4, 6 ], [ 0, 4 ], [ 2, 4 ], [ 0, 8…

題目內容 題目頁面: https://app.codility.com/programmers/lessons/6-sorting/triangle/ 題意解析 除了任兩邊的長度必須大於第三邊之外，組成三角形的線段還有一些其他的限制： 如果以上任何一個條件不滿足，則無法組成三角形。 0 ≤ P < Q < R < N 解題過程 先寫一個一定會被打槍的暴力解，複雜度為O(N^3) 結果0%，，沒一個過的了，不是答案錯誤就是runtime error 直覺猜測，這一定和三角形的定義有關，查了一下谷歌大神，找到這段 當一個陣列已經排好序時，如果能夠構成三角形，那麼任意三個相鄰的元素都能構成三角形。 假設排序後的陣列為arr，元素個數為n。我們使用一個for循環遍歷arr中的元素arr[i]。由於arr已經排好序，因此arr[i]一定是arr[i]、arr[i+1]和arr[i+2]中最小的一個，arr[i+1]是中間的一個，arr[i+2]是最大的一個。如果這三個元素能夠構成三角形，那麼其他任意三個相鄰的元素也能構成三角形。 如果arr[i]+arr[i+1]>arr[i+2]，那麼一定存在一組三個相鄰的元素可以構成三角形。因此，在檢查完arr[i]、arr[i+1]和arr[i+2]之後，我們可以繼續檢查arr[i+1]、arr[i+2]和arr[i+3]，arr[i+2]、arr[i+3]和arr[i+4]，以此類推，直到遍歷完整個陣列。 總之，當一個陣列已經排好序時，只需要檢查相鄰的三個元素是否能夠構成三角形，即可判斷是否存在三個元素能夠構成三角形。這比遍歷所有可能的三元組要更高效。 所以就是要知道這個定理就可以了

題目內容 題目頁面: https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/ 題目理解 總之就是取得陣列A裡面，由N個數字所挑選隨意三個相乘的最大值，這些數字可能是-1000~1000，然後陣列長度最少3個最多10萬個 解題紀錄 首先我想到，形成最大值的三個值，當該值為正數時，只有可能由3個正數或2個負數*1個正數組成。當該值為負數時，則有可能由3個負數或2個正數*1個負數組成。所以，現在所需的就是先遍歷整個陣列，然後確認正數和負數的數量。當有可能有正數乘積時，則以正數乘積為優先，否則則需要考慮負數的乘積。 因此，我決定先遍歷A陣列，找尋最大的前三個正數數字以及最小的前三個負數數字(當正值時使用)，以及最小的前三個正數數字以及最大的負數數字(當負值時使用)，然後統計正值的數量和負值的數量，以決定最後輸出的會是正值還是負值 100%!!!一次成功~感動(https://app.codility.com/demo/results/trainingR9PVFF-P78/)

題目內容 題目頁面: https://app.codility.com/programmers/lessons/6-sorting/distinct/ 題目解析 這一題之前其實出現過，但是因為這一題A的範圍是負一百萬到正一百萬，實在太大了，沒辦法直接用查表的方式儲存，所以會需要使用到二分搜尋法去建立這個不重複陣列 我的解題記錄 第一次的解法 對於這結果，我真是滿腹委屈，明明二分搜尋法就是O(logN)阿!到底是誰把他變成O(N^2)的…我覺得應該是原本遍歷陣列為N,又乘上搜尋的LogN，因此變得很耗時 經過了一陣思考後，我覺得我根本被這一個章節的篇名所騙了，我幹嘛要建立有序陣列呢?用物件不就好了嗎?甚麼二分搜尋法根本自討苦吃!! 結果根本沒在鳥甚麼Sorting不Sorting的反而過關，100%PASS!(https://app.codility.com/demo/results/trainingTR8QQS-TDU/)

題目內容 題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/ 題目理解 尋找 (P, Q)，其中0 ≤ P < Q < N，為陣列A的切片，N介於2~100000之間，並尋找最小平均切片的起始位置，要注意的是，陣列的內容為-10000~10000 感覺起來就是要先儲存從0~N的加總，然後再來尋找最小平均切片，但是思考起來這樣子複雜度應該也會有O(N**2)，但是先這樣試看看 解題思路 第一次的嘗試 我就知道….60%，timeout errors。複雜度還是太高，現在的解法是很直接的思考平均算法，先嘗試思考看看”平均”有沒有其他可能的算法 本來想嘗試必定包含最小值得所有可能，但是發現有邏輯錯誤，因為一個最小值不代表平均起來就一定最小，因為若該最小值的左右兩邊比較大，旁邊有兩個比較小的值，平均值會比包含最小值的還要小。所以即便是最小的值也不一定在最小平均之內。 萬般無助之下，詢問了ChatGPT，沒想到他都比我聰明(哭)，好吧這就來改寫!! 以下為改寫後的程式碼 好，100%!謝謝ChatGPT大神!!!