一個二進制正整數 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/