최대 비트별 AND를 갖는 가장 긴 하위 배열

2419. 최대 비트 단위 AND

를 사용하는 가장 긴 하위 배열

난이도:중

주제:배열, 비트 조작, 수수께끼

n 크기의 정수 배열 num이 제공됩니다.

최대가능한비트 AND를 갖는 숫자의비어 있지 않은하위 배열을 고려해보세요.

• 즉, k를모든숫자 하위 배열의 비트별 AND의 최대값으로 설정합니다. 그런 다음 비트 AND가 k와 동일한 하위 배열만 고려해야 합니다.

해당 하위 배열가장 긴길이를 반환합니다.

배열의 비트 AND는 배열에 있는 모든 숫자의 비트 AND입니다.

하위 배열은 배열 내 연속된 요소 시퀀스입니다.

예 1:

• 입력:숫자 = [1,2,3,3,2,2]
• 출력:2
• 설명:
  • 하위 배열의 가능한 최대 비트 AND 수는 3입니다.
  • 해당 값을 가진 가장 긴 하위 배열은 [3,3]이므로 2를 반환합니다.

예 2:

• 입력:숫자 = [1,2,3,4]
• 출력:1
• 설명:
  • 하위 배열의 가능한 최대 비트 AND 수는 4입니다.
  • 해당 값을 가진 가장 긴 하위 배열은 [4]이므로 1을 반환합니다.

제약조건:

• 1 <= nums.length <= 10¹
• 1 <= 숫자[i] <= 10⁶

힌트:

1. 두 개의 서로 다른 숫자의 비트 단위 AND는 항상 두 숫자의 최대값보다 엄격하게 작습니다.
2. 이는 우리가 선택해야 하는 하위 배열의 특성에 대해 무엇을 알려줍니까?

해결책:

먼저 문제를 단계별로 분석해 보겠습니다.

주요 통찰력:

1. 비트 AND 속성:

   • 두 숫자의 비트별 AND는 일반적으로 두 숫자보다 작거나 같습니다.
   • 따라서 배열에서 최대값을 찾으면 이 최대 비트별 AND 값을 달성할 하위 배열은 반복되는 이 최대값으로 구성되어야 합니다.

2. 목표:

   • 배열에서 최대값을 찾아보세요.
   • 해당 최대값 중 가장 긴 연속 하위 배열을 찾습니다. 하위 배열에 다른 숫자가 있으면 전체 비트별 AND 결과가 줄어들기 때문입니다.

계획:

1. 배열을 순회하여 최대값을 결정합니다.
2. 배열을 다시 탐색하여 모든 요소가 이 최대값과 동일한 가장 긴 연속 하위 배열을 찾습니다.

예:

입력 배열 [1,2,3,3,2,2]의 경우 최대값은 3입니다. 3개만 있는 가장 긴 연속 하위 배열은 [3,3]이며 길이는 2입니다.

이 솔루션을 PHP로 구현해 보겠습니다:2419. 최대 비트 단위 AND
를 포함하는 가장 긴 하위 배열

        
설명:
        

         
1단계: 먼저 PHP에 내장된 max() 함수를 사용하여 배열에서 최대값을 찾습니다.
         
2단계: 가장 긴 하위 배열의 길이를 저장하는 $maxLength와 최대값의 현재 연속 하위 배열의 길이를 추적하는 $currentLength라는 두 변수를 초기화합니다.
         
3단계: 배열 전체를 반복합니다.
          

           
현재 숫자가 최대값과 같으면 현재 하위 배열의 길이를 늘립니다.
           
현재 숫자가 최대값과 같지 않으면 현재 하위 배열이 지금까지 가장 긴지 확인하고 길이를 재설정합니다.
          
         
최종 단계: 루프 후에 가장 긴 하위 배열이 배열의 끝에 있는지 확인합니다.
         
마지막으로 최대값만 포함하는 가장 긴 하위 배열의 길이를 반환합니다.
        
시간 복잡도:
        

         
최대값을 찾는 데는 (O(n))이 걸립니다.
         
가장 긴 하위 배열을 찾기 위해 배열을 순회하는 데는 (O(n))이 걸립니다.
         
전체 시간 복잡도: (O(n)), 여기서 (n)은 배열의 길이입니다.
        
테스트 케이스:
예상대로 입력 [1, 2, 3, 3, 2, 2]의 경우 출력은 2이고 [1, 2, 3, 4]의 경우 출력은 1입니다.
이 솔루션은 제약 조건을 처리하고 문제를 효율적으로 해결합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:
        

         
LinkedIn
         
GitHub
        
위 내용은 최대 비트별 AND를 갖는 가장 긴 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!