최대 비트별 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에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

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