演算法練習「Candidate Report: Anonymous」

解答...


這題是「Stacks and Queues」的第一題練習。

簡單來說就是「後進先出」：用一個矩陣逐一紀錄並疊加收到的資料。

例如：資料1收在矩陣0，資料2收在矩陣1...資料N收在矩陣N-1，但等到要處理資料時，先從資料Ｎ、資料N-1...逐一開始往回處理，如果臨時又有資料加入，則繼續疊加程序。


這跟一般來說的「排隊」不同，這是文本或編譯器的基礎。

例如JSON翻譯器，或程式碼編譯時用來辨識「區段」的開始與結束，例如for迴圈或類別檔的內容。

本身反而沒難度，搞懂邏輯程序、確保題目結果正確後，效能並沒有什麼難度。（因為題目本身就是個一維迴圈。）

演算法練習 「GenomicRangeQuery」 （快速計算矩陣內單位總和的方式）

題目和解法...

講義...

一連串長度為Ｘ的數值矩陣，如何知道單位Ｍ和Ｎ之間有不為零的數值？（Ｍ>N，且絕對不小於零或大於等於X，所以Ｍ和Ｎ單位絕對都在矩陣內。）

這其實是個變相計算總和的技巧。
如果把矩陣從頭（最小單位）跑一次迴圈，並且每次都把前一個單位的值和自己做加總，例如「X[A] = X[A] + X[A-1]」，則等到迴圈跑完，這個迴圈的每個單位（i）會變成「從0到i單位的總和」，如果要知道每個單位原本的值，只需要把單位（i）減去單位（i-1）就好。
如果要問「i到j之間單位的數值總和（假設j > i）」，也只需要把單位（j）減去單位（i）就好。

所以如果題目要知道ATCG在基因序列中出現的頻率，那就宣告四個和基因序列等長的矩陣，個別對應到ATCG，每次只要出現相對應的序列，就在那個矩陣單位中加一（X[A]=1)。

如果C[i] = N，而C[i + a] = N+2，這就表示在「i」到「i+a」這中間的單位裡，Ｃ出現了兩次。這個C[i] - C[i+a]如果稱為Ｆ（Ｃ, i, 2)，則按照題目的要求，F(Ａ, i, j）不為0時答案為1，F(C, j, j)不為零時答案為1......