Claire's Blog

題目內容 題目頁面: 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’) = Math.min(2,3) =2 陷阱在這: each element of arrays P and Q is an integer within…

題目內容 題目頁面: 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 .. 2,000,000,000 ]範圍內的整數。 嗯…看起來這是一題用效能卡死人的題目，因為最大值可到2,000,000,000，但是為了求正確性，我們還是先從簡單的方法寫起，再來慢慢改善效能，不要一下想太難的方法。先把暴力破解法寫出來 但是有了上次的經驗，我根本不想送出這個答案被打槍。所以先來想改善方法，首先，我想找到比A大，最小能夠被整除的數字，和比B小最大能夠被整除的數字然後相減後直接除以K 結果!!甚麼!!!中等程度這麼快解決!!太棒了!!!https://app.codility.com/demo/results/trainingCYGC6K-3H8/

甚麼是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 Tree來計算前綴和 BIT的基本思想是將原始數組轉換為一個二進制表示的數組，並在其中儲存一些特定位置的前綴和。BIT的建立和查詢操作都可以在O(n log n)的時間複雜度內完成，其中n是數組的長度。BIT的更新操作可以在O(log n)的時間複雜度內完成。 更多詳細介紹: https://yuihuang.com/binary-indexed-tree/ 範例題目 – PassingCars 題目連結 https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/ 我的第一次解法(javascript) 成績如下，雖然答案是正確的，但是效率不夠，為O(N**2)，只拿到70%的分數 改善方向…

概念介紹 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 – VIEW 我的作答 練習題目3- MaxCounters 題目連結: MaxCounters – VIEW 我的解法 結果正確，但時間超時，只得到66的分數，代表需要再修改做法 我檢查了一下寫法，發現arr.fill(max_value)這行雖然只有一行，但是會是O(N)的複雜度，會增加許多的時間複雜度，因此，我嘗試最後再一次性的更新這個值，並且在每一步做加總時，檢查這個值是否需要被更新，就可以避免每次當A[i]>N時都得增加一次O(N)的時間複雜度。 https://app.codility.com/demo/results/training556V6C-HBV/ 練習題目4- MissingInteger…

什麼是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只是在描述增加的速率。 降低非優勢條件 在算法的時間複雜度分析中，我們通常會關注最壞情況下的時間複雜度，即算法在處理最壞情況下的輸入時所需的時間複雜度。但是，在實際應用中，算法所處理的輸入可能並不總是最壞情況，因此可能存在一些非優勢條件，即輸入規模較小、輸入具有特殊性質等情況。 刷題範例 題目連結: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ 我的解答 – https://app.codility.com/demo/results/training5HCTQQ-UW6/ 結果如下