OR이 최소 K II인 최단 하위 배열

3097. 최소 K II 이상의 OR을 갖는 최단 하위 배열

난이도:중

주제: 어레이, 비트 조작, 슬라이딩 윈도우

음수가 아닌 정수로 구성된 배열 num과 정수 k가 제공됩니다.

모든 요소의 비트별 OR이 적어도 k인 경우 배열을 특수

라고 합니다.

숫자의 가장 짧고 비어 있지 않은 하위 배열¹의 길이를 반환하거나, 특수 하위 배열이 없으면 -1을 반환합니다.

예 1:

• 입력: nums = [1,2,3], k = 2
• 출력: 1
• 설명: 하위 배열 [3]의 OR 값은 3입니다. 따라서 1을 반환합니다.

예 2:

• 입력: nums = [2,1,8], k = 10
• 출력: 3
• 설명: 하위 배열 [2,1,8]의 OR 값은 11입니다. 따라서 3을 반환합니다.

예 3:

• 입력: nums = [1,2], k = 0
• 출력: 1
• 설명: 하위 배열 [1]의 OR 값은 1입니다. 따라서 1을 반환합니다.

제약조건:

• 1 5
• 0 9
• 0 9

힌트:

1. 각 nums[i]에 대해 그것으로 끝나는 각 하위 배열의 비트별 OR 결과를 유지할 수 있습니다.
2. 비트 OR의 특성은 어떤 비트도 설정 해제하지 않고 새 비트만 설정한다는 것입니다
3. 따라서 각 nums[i]에 대한 서로 다른 결과의 수는 최대 32비트 수입니다.

해결책:

비트 조작과 결합된 슬라이딩 창 접근 방식을 사용하여 창에 있는 요소의 OR을 추적할 수 있습니다.

계획:

1. 슬라이딩 윈도우 접근 방식: OR 값이 확인된 하위 배열을 유지하면서 두 개의 포인터를 사용하여 배열을 반복합니다.
2. 비트별 OR: OR 연산은 값을 누적합니다. 결과는 결코 줄어들지 않습니다(즉, 비트가 1로 설정된 후에는 설정을 해제할 수 없습니다). 즉, 기간을 연장해도 OR 값은 증가하거나 동일하게 유지됩니다.
3. 효율성: deque(양단 큐)를 사용하여 하위 배열의 인덱스를 유지할 수 있습니다. 이를 통해 최소 하위 배열 길이를 추적하면서 창을 효율적으로 슬라이드할 수 있습니다.

단계:

1. 배열을 순회하며 각 요소에 대해 실행 중인 OR을 유지합니다.
2. 각 요소에 대해 OR이 k를 초과하거나 같은지 확인하세요. 그렇다면 왼쪽에서 창을 축소해 보세요.
3. 일정한 시간 슬라이딩 및 축소가 가능하도록 deque 구조에서 OR 값을 추적하여 슬라이딩 창을 효율적으로 이동해야 합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3097. 최소 K II 이상의 OR을 갖는 최단 하위 배열

<?php class Solution {
    const K_MAX_BIT = 30; // Maximum bit position we will check

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function minimumSubarrayLength($nums, $k) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function orNum($ors, $num, &$count) {
        // Update the ors value and count bits that are set
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function undoOrNum($ors, $num, &$count) {
        // Reverse the update on ors and count bits that are reset
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$nums1 = [1, 2, 3];
$k1 = 2;
echo $solution->minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>

설명:

1. minimumSubarrayLength 메서드:

   • ANS를 불가능한 높은 값($n 1)으로 초기화합니다.
   • 두 개의 포인터 l(왼쪽)과 r(오른쪽)을 사용하여 창을 확장하거나 축소합니다.
   • orNum으로 창을 확장하면서 하위 배열의 OR을 계산하고 축소할 때 undoOrNum으로 창을 줄입니다.
   • OR 결과가 k를 충족하거나 초과할 때마다 현재 창 크기가 ans보다 작은지 확인하세요.

2. orNum 및 undoOrNum 메소드:

   • orNum 메소드: 카운트 배열을 업데이트하여 누적 OR에 비트를 추가합니다. 창에 비트가 새로 설정되면(즉 count[i]가 1이 됨) 해당 비트가 ors에 추가됩니다.
   • undoOrNum 메서드: 창을 왼쪽으로 밀 때 누적 OR에서 비트를 제거합니다. 창의 숫자에 비트가 더 이상 설정되지 않으면(count[i]가 0이 됨을 의미) 해당 비트는 ors에서 제거됩니다.

3. 시간 복잡성:

   • 각 인덱스가 데크에 최대 한 번 추가되고 제거되므로 시간 복잡도는 O(n)입니다.
   • n은 입력 배열의 길이입니다.

4*시간 복잡도*:

• 접두사 OR 배열과 데크를 저장하는 경우 공간 복잡도는 O(n)입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

---

1. 하위 배열 : 하위 배열은 배열 내 연속된 비어 있지 않은 요소 시퀀스입니다. ↩

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