概念解釋 最大子序列和問題（Maximum Slice Problem）是指在一個給定的整數序列中，找到一個連續子序列，使得子序列的和最大。 例如，在序列[-2, 1, -3, 4, -1, 2, 1, -5, 4]中，最大的子序列為[4, -1, 2, 1]，其和為6。 這個問題在實際應用中經常出現，比如在股票交易中，尋找一段時間內股票價格的最大漲幅，或者在信號處理中，尋找一段時間內信號的最大能量。 最大子序列和問題可以通過暴力枚舉和動態規劃兩種方法解決。暴力枚舉的時間複雜度為O(n^2)，動態規劃的時間複雜度為O(n)。其中，動態規劃是更加高效和常用的方法。 下面介紹一下動態規劃的解法思路： 設f[i]表示以第i個元素結尾的最大子序列和，那麼有： f[i] = max(f[i-1] + nums[i],…

題目內容 題目頁面: https://app.codility.com/programmers/lessons/8-leader/dominator/ Leader概念教學 在LeetCode中，”Leader”通常指的是一個數組中出現次數超過數組長度一半的元素。因為這種元素在數組中出現的次數比其他元素都多，所以被稱為”Leader”。 LeetCode中的一些問題會要求你尋找數組中的Leader或者判斷數組中是否存在Leader。解決這些問題的一種常見方法是使用摩爾投票算法（Moore Voting Algorithm）。 摩爾投票算法的基本思想是遍歷數組，對於當前遍歷到的元素，如果它和當前候選元素相同，則將計數器加一，否則將計數器減一。當計數器為零時，更換當前的候選元素。最後剩下的候選元素就是可能的Leader，需要再次遍歷數組來驗證它是否真的是Leader。 需要注意的是，摩爾投票算法的前提是數組中一定存在Leader，如果數組中不存在Leader，那麼算法得出的結果可能是錯誤的。 摩爾投票算法 摩爾投票算法是一種快速尋找數組中出現次數超過一半的元素的方法，其基本思想已經在之前的回答中進行了介紹。這裡再介紹一下摩爾投票算法的實現方法。 假設我們要在數組中尋找出現次數超過一半的元素，可以使用一個計數器count和一個候選元素candidate來輔助實現。初始時，將count和candidate分別設為0和null。 遍歷數組，對於每一個元素： 它的時間複雜度是O(n) 解題紀錄 https://app.codility.com/demo/results/trainingNPG8GS-3QA/ EquiLeader題目內容 題目連結: https://app.codility.com/programmers/lessons/8-leader/equi_leader/ 解題想法 我的解題

題目內容 題目頁面: 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…

題目內容 題目頁面: 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 ],…

題目內容 題目頁面: 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大神!!!