숫자가 주어지면 N 가장 긴 연속의 길이를 구하는 것이 과제이다. 1초 이진 표현의 시리즈.
예:
입력: n = 14
산출: 3
설명: 14의 이진 표현은 다음과 같습니다. 111 0.
입력: n = 222
산출: 4
설명: 222의 이진 표현은 110입니다. 1111 0.
목차
[순진한 접근 방식] 반복 시간 O(1) 및 공간 O(1)
C++#include
public class GFG { static int maxConsecutiveOne(int n) { int count = 0; int maxi = 0; // traverse and check if bit set increment the count for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } else { maxi = Math.max(maxi count); count = 0; } } return maxi; } public static void main(String[] args) { int n = 14; System.out.println(maxConsecutiveOne(n)); } }
def maxConsecutiveOne(n): count = 0 maxi = 0 # traverse and check if bit set increment the count for i in range(32): if n & (1 << i): count += 1 else: maxi = max(maxi count) count = 0 return maxi if __name__ == '__main__': n = 14 print(maxConsecutiveOne(n))
using System; class GFG { static int MaxConsecutiveOne(int n) { int count = 0; int maxi = 0; // traverse and check if bit set increment the count for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } else { maxi = Math.Max(maxi count); count = 0; } } return maxi; } static void Main() { int n = 14; Console.WriteLine(MaxConsecutiveOne(n)); } }
function maxConsecutiveOne(n) { let count = 0; let maxi = 0; // traverse and check if bit set increment the count for (let i = 0; i < 32; i++) { if (n & (1 << i)) { count++; } else { maxi = Math.max(maxi count); count = 0; } } return maxi; } // Driver code let n = 14; console.log(maxConsecutiveOne(n));
산출
3
[효율적인 접근 방법] 비트 조작을 이용한 O(1) 시간과 O(1) 공간
아이디어는 다음과 같은 개념을 기반으로 합니다. 그리고 비트 시퀀스의 왼쪽으로 1만큼 이동 자체 버전은 후행을 효과적으로 제거합니다. 1 연속된 모든 순서에서 1초 .
그래서 수술은 N = (n & (n<< 1)) 모든 시퀀스의 길이를 줄입니다. 1초 이진 표현으로 하나씩 N . 루프에서 이 작업을 계속 수행하면 다음과 같이 끝납니다. N = 0. 도달하는 데 필요한 반복 횟수 실제로 가장 긴 연속 시퀀스의 길이입니다. 1초 .
삽화:
위의 접근 방식을 구현하려면 아래 단계를 따르세요.
- 값으로 초기화된 변수 개수 만들기 .
- while 루프를 실행하십시오. N 아니다 0.
- 각 반복에서 작업을 수행합니다. N = (n & (n<< 1))
- 1씩 증가합니다.
- 반품 횟수
#include
class GFG { private static int maxConsecutiveOnes(int x) { // Initialize result int count = 0; // Count the number of iterations to // reach x = 0. while (x!=0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } public static void main(String strings[]) { System.out.println(maxConsecutiveOnes(14)); } }
def maxConsecutiveOnes(x): # Initialize result count = 0 # Count the number of iterations to # reach x = 0. while (x!=0): # This operation reduces length # of every sequence of 1s by one. x = (x & (x << 1)) count=count+1 return count if __name__ == '__main__': print(maxConsecutiveOnes(14)) # by Anant Agarwal.
using System; class GFG { // Function to find length of the // longest consecutive 1s in binary // representation of a number private static int maxConsecutiveOnes(int x) { // Initialize result int count = 0; // Count the number of iterations // to reach x = 0. while (x != 0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } // Driver code public static void Main() { Console.WriteLine(maxConsecutiveOnes(14)); } } // This code is contributed by Nitin Mittal.
function maxConsecutiveOnes(x) { // Initialize result let count = 0; // Count the number of iterations to reach x = 0 while (x !== 0) { // This operation reduces length of // every sequence of 1s by one x = (x & (x << 1)); count++; } return count; } // Driver code console.log(maxConsecutiveOnes(14));
// PHP program to find length function maxConsecutiveOnes($n) { // Initialize result $count = 0; // Count the number of // iterations to reach x = 0. while ($n != 0) { // This operation reduces // length of every sequence // of 1s by one. $n = ($n & ($n << 1)); $count++; } return $count; } echo maxConsecutiveOnes(14) 'n'; ?> 산출
3
시간 복잡도: 오(1)
보조 공간: 오(1)
[다른 접근법] 문자열 변환을 사용
두 변수 max_len과 cur_len을 0으로 초기화합니다. 그런 다음 정수 n의 각 비트를 반복합니다. 최하위 비트(LSB)가 1이면 현재 연속 1이 실행되는 횟수를 계산하기 위해 cur_len을 증가시킵니다. LSB가 0이면 현재 시퀀스가 중단되므로 cur_len이 더 크면 max_len을 업데이트하고 cur_len을 0으로 재설정합니다. 각 비트를 확인한 후 n을 1만큼 오른쪽으로 이동하여 다음 비트로 이동합니다. 마지막으로 루프가 끝난 후 최종 cur_len이 더 크면 max_len의 마지막 업데이트를 수행하고 연속 1의 가장 긴 시퀀스 길이로 max_len을 반환합니다.
C++#include
import java.util.*; public class Main { static int maxConsecutiveOnes(int n) { String binary = String.format('%32s' Integer.toBinaryString(n)).replace(' ' '0'); int count = 0; int maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s for (int i = 0; i < binary.length(); i++) { if (binary.charAt(i) == '1') { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Return the result return maxCount; } public static void main(String[] args) { int n = 14; System.out.println(maxConsecutiveOnes(n)); } }
def maxConsecutiveOnes(n): binary = format(n '032b') count = 0 maxCount = 0 # Loop through the binary string to # find the longest consecutive 1s for bit in binary: if bit == '1': count += 1 if count > maxCount: maxCount = count else: count = 0 # Return the result return maxCount if __name__ == '__main__': n = 14 print(maxConsecutiveOnes(n))
using System; class GFG { static int MaxConsecutiveOnes(int n) { string binary = Convert.ToString(n 2).PadLeft(32 '0'); int count = 0; int maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s foreach (char bit in binary) { if (bit == '1') { count++; if (count > maxCount) maxCount = count; } else { count = 0; } } // Return the result return maxCount; } static void Main() { int n = 14; Console.WriteLine(MaxConsecutiveOnes(n)); } }
function maxConsecutiveOnes(n) { let binary = n.toString(2).padStart(32 '0'); let count = 0; let maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s for (let i = 0; i < binary.length; i++) { if (binary[i] === '1') { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Return the result return maxCount; } // Driver code let n = 14; console.log(maxConsecutiveOnes(n));
산출
3