[Codility] 第一課 BinaryGap

一個二進制正整數 N，
舉例來說 9 二進制為 1001 含有二進制的間隙長度為 2，
數字 525 二進制為 1000010001 含有兩種二進制間隙分別為 4 跟 3，
數字 20 二進制為 10100 二進制間隙為 1，
數字 15 二進制為 1111 則沒有二進制間隙。

寫一個 function：

class Solution { public int solution(int N); }

給一個正整數 N ，返回最大的二進制間隙，如果沒有，則返回 0

舉例來說 N = 1041 則 function 返回 5，因為 N 的二進制為 10000010001，則最大的間隙為 5。


條件：

• N的範圍必須是 1.., 2, 147, 483, 647

複雜度：

• 最糟的時間複雜度為 O(log(N))
• 最糟的空間複雜度為 O(1) (不含 input 的參數)

Java 程式碼

// you can also use imports, for example:
class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0;i<A.length;i++){
            if(A[i]<=X){set.add(A[i]);}
           
           if(set.size() == X){
               return i;
           }
        }
        return -1;
    }
}

分數共拿 80%，

訂正版
需考慮 1000 這種後面沒 1 的不成立二進制間隙，
1001000 也會變成  3，須把後面不成立間隙的部分 000 移除。

Java 程式碼

// you can also use imports, for example:
// 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
         // write your code in Java SE 8
        Arrays.sort(A);
        if(A.length == 3){
            return A[0] * A[1] *A[2];
        }
      
        int N = A.length;
        int result = 0;
        if(A[0] * A[1] > 0 && A[0] < 0){
            result = Math.max(A[0] * A[1] *A[N-1],A[N - 1] * A[N - 2] *A[N - 3]);
        }else{
            result =A[N - 1] * A[N - 2] *A[N - 3];
        }
        
        return result;
    }
}

分數共拿 100%
任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想

感謝相關連結
https://www.codility.com/