題目內容 題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ 題目理解 天啊~我最討厭有故事性的題目了如汽車或DNA，好長阿~~~讓我認真看他在說啥! DNA和factor可表示為: {‘A’:1,’C’:2,’G’:3,’T’:4}，S = CAGCCTA，P=[2,5,0]，Q=[4,5,6] 然後要找第 K 個查詢（0 ≤ K < M），找到 P[K] 和 Q[K]（含）之間的 DNA 序列中包含的核苷酸的最小影響因子。也就是要計算出一個長度為M(M為P、Q的長度)的陣列，然後返回最小影響因子 例如M[0] = Math.min(S[2],S[3]) = Math.min(‘G’,’C’)…

題目內容 題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/ 解題思路 給定三個整數 A、B 和 K，返回 [A..B] 範圍內可被 K 整除的整數個數，且A 和 B 是 [ 0 .. 2,000,000,000 ]範圍內的整數； K 是 [ 1 ..…

甚麼是Prefix Sums（前綴和） 當需要快速查詢數組中某一區間的元素和時，Prefix Sums可以幫助我們在O(1)的時間複雜度內進行查詢。 具體做法是先對數組進行預處理，計算出從第一個元素到當前位置的所有元素的和，然後通過兩個元素的前綴和之差來計算出任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。 Prefix Sums通常用於需要頻繁查詢數組中某一區間的元素和的情況，例如在數學、統計學、計算機科學和機器學習等領域中。Prefix Sums的計算可以在預處理的階段中完成，因此可以在之後的查詢中以O(1)的時間複雜度快速地回答各種區間求和問題。 例如，在計算機科學中，Prefix Sums通常用於解決數組中的區間查詢問題，例如求解區間最大子段和、區間平均值、區間中位數等。Prefix Sums還可以用於在數據壓縮、圖像處理和信號處理等領域中，進行離散化、濾波和卷積等操作。 計算出從第一個元素到當前位置的所有元素的和，是因為這樣可以在之後的區間求和操作中，通過兩個元素的前綴和之差來快速計算任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。這樣可以大大降低區間求和操作的時間複雜度，提高算法效率。 Prefix Sums使用時機 在許多需要進行區間求和操作的問題中，Prefix Sums都是一種常用的解決方案。因此，在識別哪些問題需要使用Prefix Sums時，可以考慮以下幾點： 綜合以上幾點，可以初步判斷哪些問題可能需要使用Prefix Sums。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。 使用Binary Indexed…

概念介紹 Counting Elements是一種計算數組中元素出現次數的概念。它通常用於解決一些與計數有關的問題，例如找出數組中出現次數超過一定閾值的元素，計算數組中不同元素的個數等。 在Counting Elements中，我們可以使用一個額外的數組counts，將數組中每個元素出現的次數記錄下來。counts[i]表示數組中元素i出現的次數，如果數組中不存在元素i，則counts[i]=0。 具體來說，Counting Elements算法的步驟如下： Counting Elements算法的時間複雜度為O(n)，其中n是數組的長度。它可以在線性時間內計算數組中元素的出現次數，因此非常適用於需要頻繁計算元素次數的問題。另外，Counting Elements算法還可以與其他算法結合使用，例如快速排序和二分查找等，以進一步優化計算效率。 使用時機 在許多與計數有關的問題中，Counting Elements是一種常見的解決方案。因此，在考慮使用Counting Elements時，可以考慮以下幾點： 綜合以上幾點，可以初步判斷哪些問題可能需要使用Counting Elements。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。 練習題目1 題目連結: FrogRiverOne – VIEW 我的解法 測試通過，為100%! 練習題目2 題目連結: PermCheck…

什麼是BigO 時間複雜度是指算法所需的運行時間與輸入數據規模之間的關係。在計算機科學中，我們使用 BigO 表示法來表示算法的時間複雜度。 BigO 表示法中的 O 代表 “on the order of”，即算法的運行時間隨著輸入規模的增長，按照某種數量級的速度增長。常見的時間複雜度從低到高分別是 O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n) 和 O(n!)。 在實際應用中，我們通常希望選擇時間複雜度盡可能低的算法。然而，不同的算法在不同的應用場景下可能表現不同，因此選擇合適的算法需要根據具體問題進行綜合考慮。 另外需要注意的是，時間複雜度只是對算法的一個粗略估計，實際運行時間還受到很多其他因素的影響，如輸入數據的特性、計算機硬件性能等。因此，在實際應用中需要進行充分的測試和優化，以獲得更準確的運行時間估計。 降低常數 在 BigO 表示法中，常數因子通常被省略，因為它們對算法的增長速度影響相對較小。在特定輸入下O(N)可能會比O(1)更小，一般來說，BIG O只是在描述增加的速率。…

Maximum Value of K Coins From Piles 這是遞迴方式的寫法, 但我可能存太多垃圾資訊,當k值變大之後,會發生heap allocation錯誤的問題,也受限於遞迴的限制當k變大效率非常差….. 看來又要動態規劃(哭), 晚點再來補上改善版

Coin Change2 這也是一題動態規劃的題目，但是比起上一題，上一題每一個暫時儲存的東西是有意義的，我們可以了解說每一個的暫時狀態是某個數字用所給的硬幣列表裡，能用最少數量達成答案的數目，但是這一題的中間狀態所儲存的真的就是『中間的狀態』，我是看著別人的答案去回推理論的，真的很難想像在遇到這樣的問題時，該用什麼角度去把複雜的問題拆分，並找尋出重複步驟並找到可暫存狀態來計算出最終結果。 這是最後的結果 var change = function(amount, coins) { let dp = new Array(amount+1).fill(0); dp[0]=1; for(let coin of coins){ for(let i=coin;i

https://leetcode.com/problems/coin-change 最近開始刷leetcode覺得思考這些邏輯問題還滿好玩的 第一個刷的是這個,他是一個動態規劃的題目 一般我們在思考的時候會去思考以錢幣為基準,例如1,3,5的錢幣要怎麼湊成11元,我們會拿1,3,5去隨機湊硬幣,但是當數值大了以後,要計算最小的錢幣組合就會變成很困難. 像這種極限求值就會需要將思考轉換過來, 我們可以一步步的拆解, 先了解1,3,5,若要組成1是用幾個(1個1),那組成2要用幾個(2個1),若要組成3要用幾個,到3時我們就會發現,3可以用”3個1″或”1個3″組成, 這時候就可以來比較誰用的硬幣比較少,然後把最小可組成的數字”1″存到可組成結果為3的陣列。 接下來在思考4的時候,我們就可以思考4減掉硬幣1,也就是3,的最小使用硬幣數量,那就代表我們使用3,再加上硬幣1,可以組成4。接下來算要組成6要幾個硬幣,6減掉硬幣3,可以拿到硬幣3要用幾個硬幣,所以就是硬幣3使用的硬幣數量+1。 var coinChange = function (coins, amount) { if (amount == 0) return 0; let amountRecord =…