演算法練習「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......

[Codility] Training ticket -- 100%

Score 83
效能不合格....

123456789101112131415161718192021222324252627282930313233

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int l = A.length;
        int l2 = A.length;
        
        for(int i = 0 ; i < l ;i++){
            int tmp = A[i];
            for(int j = i+1 ; j < l ;j++){
                
                if(A[j] == tmp){
                    i++;
                    A[j] += A[i];
                    A[i] = A[j] - A[i];
                    A[j] = A[j] - A[i];
                    l2--;
                }
                
            }
            
            
        }
        
        return l2;
    }
}

https://codility.com/demo/results/trainingYKSGPS-9KJ/

123456789101112131415161718192021222324252627282930313233343536373839404142434445

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int l = A.length;
        
        for(int i = 1 ; i < l ;i++){
            for(int j = 0 ; j < i ;j++){
                
                if(A[i] == A[j]){
                    A[j] = 1000001;
                }
                if(A[j] == 1000001){
                    A[j] = A[i];
                    A[i] = 1000001;
                    
                    if(j > 0){
                        A[j-1] += A[j];
                        A[j] = A[j-1] - A[j];
                        A[j-1] = A[j-1] - A[j];
                    }
                    
                    
                    j = i;
                }
                
            }
            
        }
        
        for(int i = 0 ; i < l ;i++){
            if(A[i] == 1000001)
                return i;
        }
        
        return l;
        
    }
}

https://codility.com/demo/results/trainingZKNY6F-3GA/
成績沒有改善

123456789101112131415161718192021222324252627282930

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int l = A.length;
        int count = 0;
        
        for(int i = 0 ; i < l ; i++){
            if(A[i] != 1000001){
                count++;
                for(int j = i+1; j < l ; j++){
                    if(A[j] == A[i]){
                        A[j] = 1000001;
                        if(j == l-1)
                            l--;
                    }
                }
                A[i] = 1000001;
            }
        }
        
        return count;
    }
}

https://codility.com/demo/results/training2H2FYZ-FT7/
依然沒有改善

1234567891011121314151617181920212223242526

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int l = A.length;
        int count = 0;
        int[] A2 = new int[2000001];
        
        for(int i = 0 ; i < l ; i++){
            int tmp = A[i] + 1000000;
            if(A2[tmp] == 0)
                count++;
            A2[tmp]++;
        }
        
        return count;
        
        
    }
}

https://codility.com/demo/results/trainingCXSQ2W-JFG/
其實資料長度只有100000，並不算大！
直接計算出現次數就可以輕鬆解決效能問題！並不會造成記憶體不足的問題！
跟青蛙過河有異曲同工之妙！