최소 배열 끝

3133. 최소 배열 종료

난이도:중

주제: 비트 조작

두 개의 정수 n과 x가 주어졌습니다. 양수 크기 n의 정수 배열을 구성해야 합니다. 여기서 모든 0 <= i < n - 1, nums[i 1]은 nums[i]보다 크고 nums의 모든 요소 간 비트 AND 연산의 결과는 x입니다.

숫자[n - 1]의 가능한 최소값을 반환합니다.

예 1:

• 입력: n = 3, x = 4
• 출력: 6
• 설명: 숫자는 [4,5,6]이 될 수 있으며 마지막 요소는 6입니다.

예 2:

• 입력: n = 2, x = 7
• 출력: 15
• 설명: 숫자는 [7,15]일 수 있으며 마지막 요소는 15입니다.

예 3:

• 입력: 비용 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 출력: 10

제약조건:

• 1 <= n, x <= 10⁸

힌트:

1. 배열의 각 요소는 x와 v를 "병합"하여 얻어야 합니다. 여기서 v = 0, 1, 2, …(n - 1)입니다.
2. x를 다른 숫자 v와 병합하려면 x의 설정 비트를 그대로 유지하고, 다른 모든 비트에 대해서는 v의 설정 비트를 오른쪽에서 왼쪽으로 하나씩 순서대로 채웁니다.
3. 그래서 최종 답은 x와 n - 1의 '병합'입니다.

해결책:

우리는 크기가 n인 양의 정수로 구성된 nums 배열을 구성해야 합니다. 여기서 연속되는 각 요소는 이전 요소보다 큽니다. nums의 모든 요소에 대한 비트 단위 AND는 x를 산출해야 합니다. nums[n-1]의 가능한 최소값을 찾으라는 요청을 받습니다.

내역은 다음과 같습니다.

1. 비트 조작 통찰력: x를 정수 0, 1, ..., n-1과 병합하여 nums[i]를 구축해야 함을 관찰할 수 있습니다. 이는 x를 밑으로 시작하므로 비트 단위 AND 결과가 x를 산출하도록 하는 데 도움이 됩니다.

2. 배열 요소 구축: 각 요소는 x가 일부 정수와 병합된 것으로 생각할 수 있으며 x의 비트를 그대로 유지하는 것을 목표로 합니다. AND 결과를 x로 유지하면서 숫자가 증가하도록 정수에서 추가 비트를 채웁니다.

3. 병합 전략: 최소 숫자[n-1]을 찾으려면 x를 n-1과 병합하면 됩니다. 이 맥락에서 병합은 x의 비트가 1이면 1로 유지된다는 의미입니다. n-1의 비트를 사용하여 x에 설정된 비트를 변경하지 않고 필요한 추가 비트를 추가합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3133. 최소 배열 종료

  
  
  설명:




비트 확인 및 설정:


ans의 각 비트(x부터 시작)를 확인하고, ans의 비트가 0이면 k(n-1)에서 해당 비트를 찾습니다.
k의 해당 비트가 1이면 ans의 비트를 1로 설정합니다. 이 프로세스는 x에 설정된 비트를 유지하면서 값의 최소 증가를 보장합니다.



루프 제약:


계산된 최대값(kMaxBit)까지 각 비트 위치를 반복하여 x와 n 모두에서 필요한 비트를 포함합니다.



결과:


ans의 최종 값은 조건을 만족하는 nums[n-1]의 가능한 최소값입니다.





  
  
  복잡성:



이 범위에 있는 모든 정수의 비트 수가 32로 제한되므로 알고리즘은 일정한 시간에 작동하므로 n과 x의 큰 값에 대해서도 이 접근 방식이 효율적입니다.


이 솔루션은 필수 속성을 유지하면서 원하는 최소 숫자[n-1]를 산출합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 최소 배열 끝의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!