비트 문자열에서 가장 긴 0 시퀀스 찾기

"0001100001"과 같은 비트 문자열이 주어지면 가장 긴 0 시퀀스 (이 예에서는 4)의 길이를 찾아야합니다.비트 문자열에서 가장 긴 0 시퀀스 찾기

알고리즘은 O (log (b)) 시간에서 수행해야합니다. 여기서 b는 문자열의 길이입니다. 난 단지에 의해 선형 시간에 작업을 수행하는 방법을 알고

...

는 내가 원하는 복잡성을 달성하기 위해, 어떻게 든 왼쪽으로 비트를 이동해야한다는, 들었지만, 나는 왜 단서가 없다 문자열을 반복합니다.

로그 시간은 어떻게 받습니까?

2017-04-23 de_dust

입력을 읽는 중 이미 O (b) 시간이 걸립니다. – Henry

@Henry : 그러면 어떨까요? 아직 로그 시간을 달성 할 수있는 방법이 있습니까? 과제의 힌트에 따르면 비트를 왼쪽으로 이동해야한다고 나와 있습니다. 처음에는 1 비트, 2 비트, 4 비트, 8 비트, 16 비트 등 ... 각 이동 후 AND 함수를 사용해야합니다. 그 사람을 위해 그리고 그것은 내게 변화하는 다음 순서를 줄 것이다 ... 그러나 나는 그것을 사용하는 방법을 모른다. –

나는 그것을 증명할 수 없다. 그러나 나의 직감은 내가 없다고 말한다. – Henry

-2

수를 문자열로 제공되기 때문에, 우리는 우리가 이진 1000000 가장 긴 0 길이가 6 인 인 64 말을 전달하는 경우

Integer.parseInt(String,Base)

를 사용하여 수를 분석 할 수, while 루프는 실행해야 log2 (64)가 6이면이 솔루션이 사용자가 찾고자하는 솔루션이어야합니다. 내가 16, 32 및 64이 프로그램을 실행하고 그것이 로그 (n)의 작동 시간이 경우에 포함 된 문자 없음 구문 분석 문자가 없기 때문에도에 대한 비트 연산자를 사용

public class CountZeroes { 
private static long getZeroes(String s) { 
    int x = Integer.parseInt(s,2); 
    long count = 0, maxSoFar = 0; 
    while (x > 0) { 
     System.out.println("Running"); 
     if ((x & 1) == 1) { 
      if (count > maxSoFar) { 
       maxSoFar = count; 
      } 
      count = 0; 
     } else { 
      count += 1; 
     } 
     x = x >> 1; 
    } 
    return maxSoFar; 
} 

public static void main(String[] args) { 
    System.out.println(getZeroes("10000")); 
    System.out.println(getZeroes("100000")); 
    System.out.println(getZeroes("1000000")); 
} 
}

아래의 솔루션을 확인하시기 바랍니다 똑같다. 괜찮 으면 한 번 확인하십시오.

감사합니다.

출처

2017-04-23 16:06:23

1.'Integer.parseInt'는 문자열을 문자 단위로 파싱합니다 2. 오른쪽 시프트는 문자 단위로 파싱하는 것과 같습니다 (1 비트 만 이동합니다). 따라서 효율적으로 두 번 수행합니다. –

문자열이 아닌 정수를 오른쪽으로 시프트했습니다. 본질적으로 log (n) 시간의 경우이어야하는 2로 정수를 나눕니다. –

시프트는 정수를 2로 나눕니다. 그러나 비트 길이를 2 줄이거 나하지 않고, 모든 비트가 1 인 숫자로 시도하고 시프트가 수행되는 횟수를 계산하십시오. –

비트 문자열에서 가장 긴 0 시퀀스 찾기

답변

관련 문제