LeetCode-スライドウィンドウ類題まとめ

7649 ワード

python 試験問題集スライドウィンドウ

テンプレート:

初期左ポインタ(left)と右ポインタ(right)はいずれも0

を指す.

右ポインタは絶えず右へ

移動する.

ウィンドウサイズを満たす場合、対応する処理が行われ、この和の過程でleftが

右に移動する必要がある.

def sliding_window(window_size, array):
    left, right = 0, 0
    res = 0
    while right < len(array):
        if condition:
            pass
        while n > window_size or n == window_size:
            ...
            left += 1 #   left
            res = max(res, xxx)
            ...
        res = max(res, xxx)
        right += 1    #   right

    return res

1、重複文字のない長男列
文字列を指定すると、重複文字が含まれていない長男の列の長さを見つけてください.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
この問題はウィンドウのサイズを制限しないで、ウィンドウは重複する文字を含まないでできます

def lengthOfLongestSubstring(self, s):
        left, right = -1, 0  # left = -1             
        maps = {}
        max_len = 0
        while right

2、置換後の最長重複文字
大文字の英字だけからなる文字列をあげます.任意の位置の文字を別の文字に置き換えることができます.全部でk回まで置き換えることができます.上記の操作を実行すると、重複するアルファベットを含む最長子列の長さが見つかります.ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/longest-repeating-character-replacement/
この問題はウィンドウの大きさを制限しないで、ウィンドウは同じ文字に置き換えることができます

def characterReplacement(self, s, k):
        if not s:
            return 0
        letter_num = {}
        left, right = 0, 0
        res = 0
        while right < len(s): 
            letter_num[s[right]] = letter_num.get(s[right], 0) + 1 #       
            max_letter = max(letter_num, key=letter_num.get)  #            
            while right - left + 1 - letter_num[max_letter] > k: #          k，               ，      
                letter_num[s[left]] -= 1
                left += 1
                max_letter = max(letter_num, key=letter_num.get)  #             
            res = max(res, right - left + 1)
            right += 1

        return res

3、スライドウィンドウ中位数
kサイズのウィンドウが左端から右端にスライドする配列numsが与えられる.ウィンドウにk個の数があり、ウィンドウごとに右に1ビット移動します.あなたのタスクは、ウィンドウが移動するたびに得られる新しいウィンドウの要素の中位数を見つけ、それらからなる配列を出力することです.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/sliding-window-median/
ソート配列の挿入と検索には、次のようなモジュールbisectが使用されます.https://www.cnblogs.com/skydesign/archive/2011/09/02/2163592.html

    def medianSlidingWindow(self, nums, k):
        result = []
        if not nums or not k:
            return result
        #      
        def calculate_median(window, k):
            if k % 2 == 1:
                median = window[k//2]
            else:
                median = (window[k//2 - 1] + window[k//2])/2.0
            return median

        n = len(nums)
        left, right = 0, k
        #            
        window = sorted(nums[left:right])
        result.append(calculate_median(window, k))
        while right < n:
            bisect.insort(window, nums[right]) #           
            #        
            index = bisect.bisect_left(window, nums[left])
            del window[index]
            result.append(calculate_median(window, k)) #           
            left += 1
            right += 1

        return result

4、文字列の配列
2つの文字列s 1およびs 2を与え、s 2がs 1の配列を含むか否かを判断する関数を書く.
すなわち、1番目の文字列の配列の1つは、2番目の文字列のサブ列である.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/permutation-in-string/

    def checkInclusion(self, s1, s2):
        if s1 in s2:
            return True
        if len(s1)>len(s2):
            return False
        counter = collections.Counter(s1)  #   s1  
        left, right = 0, 0
        temp_counter = dict(counter)
        while right < len(s2):
            if s2[right] not in temp_counter:  #  s1    ，     ,  counter
                right += 1
                left = right
                temp_counter = dict(counter)
                continue
            else:
                while temp_counter[s2[right]] == 0: #    right       ，       ，         
                    temp_counter[s2[left]] += 1
                    left += 1
                temp_counter[s2[right]] -= 1
                if temp_counter[s2[right]] > 0: #           s1，    ，，         （     all）
                    right += 1
                    continue
            if all(v == 0 for v in temp_counter.values()):  #        
                return True
            right += 1

        return False

5、K個の異なる整数のサブ配列
正の整数配列Aが与えられ、Aのあるサブ配列の異なる整数の個数がKである場合、Aのこの連続的で独立していないサブ配列を良いサブ配列と呼ぶ.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
重複する要素の数を含めます

 def subarraysWithKDistinct(self, A, K):
        if not A or K == 0:
            return 0
        maps = collections.defaultdict(int)
        n = len(A)
        left, res, cnt, tmp = 0, 0, 0, 1
        for right in range(n):
            maps[A[right]] += 1
            if maps[A[right]] == 1: #          ，        +1
                cnt += 1   
            while cnt > K: #      ，     
                tmp = 1   
                cnt -= 1
                maps[A[left]] -= 1
                left += 1
            #         ，      ，               ，      !     tmp++
            while maps[A[left]] > 1: #   1       ，       ，tmp               
                tmp += 1
                maps[A[left]] -= 1
                left += 1
            if cnt == K:
                res += tmp
        return res

6、スライドウィンドウの最大値
配列numsが与えられ、kサイズのスライドウィンドウが配列の一番左側から配列の一番右側に移動する.スライドウィンドウ内のk個の数字しか見えません.スライドウィンドウは毎回1つだけ右に移動します.
スライドウィンドウの最大値を返します.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/sliding-window-maximum/
単調な二重キュー(減算)を適用し、最大値が1つ目であることを保証し、二重キュー用from collections import dequeを実現する

    def maxSlidingWindow(self, nums, k):
        #       
        if not nums or not k :
            return []
        # push    ，     
        def push(queue, nums, i):
            while queue and nums[i] > nums[queue[-1]]:
                queue.pop()
            queue.append(i)
            
        from collections import deque
        res = []
        queue = deque()
        for i in range(k-1):  #      1         
            push(queue, nums, i)
        
        for i in range(k-1, len(nums)):
            push(queue, nums, i)   #        
            res.append(nums[queue[0]])  #       
            if k == i-queue[0]+1: #      ，     
                queue.popleft()
        
        return res

7、最長乱流サブ配列
Aのサブ配列A[i],A[i+1],...,A[j]が以下の条件を満たす場合,乱流サブ配列と呼ぶ.
i<=kA[k+1]、kが偶数の場合、A[k]A[k+1]、kが奇数の場合、A[k]Aの最大乱流サブ配列の長さを返します.リンク:https://leetcode-cn.com/problems/longest-turbulent-subarray/

def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if len(A) < 2:
            return len(A)
        max_len = 1
        left, right = 0, 2
        while right < len(A):
            if A[right - 1] == A[right]:
                left = right
                right += 1
            elif A[right - 2] > A[right - 1] < A[right] or A[right - 2] < A[right - 1] > A[right]:
                max_len = max(max_len, right - left + 1)
                right += 1
            elif A[right - 1] < A[right] or A[right - 1] > A[right]:
                max_len = max(max_len, 2)
                left = right - 1
                right += 1
        return max_len

JPAプライマリ・キー生成ポリシー

Springbootのjpaマルチデータソース構成