2018年10月29日 星期一

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

題目和解法...

講義...

一連串長度為X的數值矩陣,如何知道單位M和N之間有不為零的數值?(M>N,且絕對不小於零或大於等於X,所以M和N單位絕對都在矩陣內。)


這其實是個變相計算總和的技巧。
如果把矩陣從頭(最小單位)跑一次迴圈,並且每次都把前一個單位的值和自己做加總,例如「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出現了兩次。這個C[i] - C[i+a]如果稱為F(C, i, 2),則按照題目的要求,F(A, i, j)不為0時答案為1,F(C, j, j)不為零時答案為1......

沒有留言:

張貼留言