부분배열 또는 부분행렬의 결과 누적

조합 패턴은 부분배열과 부분행렬의 결과를 누적해야 하는 질문입니다. 이 패턴에서는 모든 부분배열이나 부분행렬을 생성하는 대신 요소가 부분배열이나 부분행렬에서 가능한 후보로 몇 번이나 나타날지 계산합니다. 몇 가지 예를 들어 이것을 이해합시다.

문자열의 총체적 매력

문자열 의 매력 은 문자열 에서 발견되는 고유한 문자의 수입니다. 예를 들어 의 매력은 , , 및 와 같은 고유한 문자 "abbca"가 3있기 때문 입니다. 문자열이 주어지면 모든 하위 문자열의 총 매력을 반환합니다.3'a''b''c's

접근하다

하위 문자열에서 동일한 여러 문자는 한 점만 얻습니다.
따라서 모든 부분 문자열을 찾고 각 문자의 가중치를 계산해야 합니다. 캐릭터가 두 번 이상 나타나면 그 무게는 단 하나입니다.
중복 문자가 있는 경우 첫 번째 항목이 요점을 얻는다고 생각할 수 있습니다. 각 문자 s[i]에 대해 하위 문자열은 s[i]를 포함 하기 전에 시작해야 하고 가 발생한 s[i] 후에 끝나야 합니다 . 그렇지 않으면 문자의 마지막 발생이 점수를 얻습니다. 전체적으로 가능한 시작 위치 와 가능한 끝 위치가 있으므로 포인트 를 제공할 수 있습니다 .lasts[i]s[i]i - last[s[i]]
n - is[i](i - last[s[i]]) * (n - i)

코드 구현

def appealSum(s):
    from collections import defaultdict
    last_seen = defaultdict(lambda: -1)
    res, n = 0, len(s)
    for idx, char in enumerate(s):
        res += (idx - last_seen[char]) * (n - idx)
        last_seen[char] = idx
    return res
print(appealSum("abbca"))

countUniqueChars(s)의 고유 문자 수를 반환 하는 함수를 정의해 보겠습니다 s. 예를 들어, then , , , 을 호출 countUniqueChars(s)하는 s = "LEETCODE"것은 "L", "T"그러므로 "C"에서 "O"한 번만 "D"나타나기 때문에 고유한 문자 입니다. 문자열이 주어지면 가 의 부분 문자열인 곳 의 합계를 반환합니다 . 테스트 케이스는 답이 32비트 정수에 맞도록 생성됩니다.scountUniqueChars(s) = 5scountUniqueChars(t)ts

일부 하위 문자열은 반복될 수 있으므로 이 경우 반복되는 문자열도 계산해야 합니다.

접근하다

이전 문제와 유사하게, 모든 고유한 문자를 세고 가능한 모든 하위 문자열과 씨름하는 대신 S의 모든 문자에 대해 셀 수 있습니다. 이것이 고유한 문자인 곳에 하위 문자열이 몇 개 있는지입니다. 모든 문자에 대해 계산하고 res에 계속 추가하면 이것이 우리의 답이 될 것입니다. 문자가 반복되는 것을 볼 때 해당 문자가 하위 문자열에서 고유했지만 더 이상 last_occurence -second_last_occurence. 우리는 또한 추가된 새로운 캐릭터를 추가해야 합니다 current_idx — last_occurence.

코드 구현

def uniqueLetterString(s):
    index_map = {c: [-1, -1] for c in s}
    res = 0
    current = 0
    for idx, char in enumerate(s):
        second_last_occurence, last_occurence = index_map[char]
        num_removed = last_occurence - second_last_occurence
        num_added = idx - last_occurence
        index_map[char] = [last_occurence, idx]
        
        current += num_added - num_removed
        res += current
    return res
    
print(uniqueLetterString("LEETCODE"))

정수 배열이 주어지면 하위 배열 의 가장 왼쪽 요소가 하위 배열의 다른 요소보다 크지 않은 비어 있지 않은 하위 배열의 수를nums 반환 합니다 .

접근하다

첫 번째 요소가 최소인 모든 하위 배열을 찾아야 합니다. 즉, 각 요소에 대해 다음으로 작은 요소를 찾아야 합니다. 해당 인덱스(다음으로 작은 요소)까지 모든 하위 배열은 최소값으로 num을 가지므로 이러한 모든 기여도가 계산됩니다.

다음으로 작은 요소를 찾기 위해 Monotonic Stack 을 사용 합니다.

코드 구현

def validSubarrays(nums):
    stack = []
    next_smaller = [len(nums)] * len(nums)
    for i, v in enumerate(nums):
        while stack and stack[-1][1] > v:
            next_smaller[stack.pop()[0]] = i
        stack.append([i, v])
    return sum([v - i for i, v in enumerate(next_smaller)])

정수 배열 arr이 주어지면 의 합을 찾으십시오 min(b). 여기서 b범위는 의 모든 (인접한) 하위 배열입니다 arr. 답이 클 수 있으므로 모듈로 10^9 + 7 답을 반환합니다 .

접근하다

이 문제에서는 숫자를 포함하고 숫자가 가장 작은 부분배열이 몇 개 있는지 찾아야 합니다. 이를 찾기 위해 인덱스에서 시작하여 현재 숫자보다 작은 값을 가진 첫 번째 인덱스를 찾을 때까지 배열의 왼쪽으로 이동합니다. 이것은 num이 최소인 곳에 얼마나 많은 실행 가능한 왼쪽 하위 배열이 있는지를 결정합니다. 유사하게, 인덱스의 오른쪽으로 이동하여 첫 번째 작은 수를 찾아 실행 가능한 오른쪽 하위 배열의 수를 계산할 수 있습니다.

코드 구현

def sumSubarrayMins(nums):
    n = len(nums)
    nums.append(0)
    res = 0
    mod = 1000000007
    stack = [-1]
    
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] > num:
            idx = stack.pop()
            res += nums[idx] * (i - idx) * (idx - stack[-1])
            
        stack.append(i)
        
    return res % (mod)
print(sumSubarrayMins([3,1,2,4]))

정수 배열이 제공됩니다 nums. 하위 배열의 범위는 하위 배열 에서 가장nums 큰 요소와 가장 작은 요소 간의 차이입니다. 의 모든 부분배열 범위의 합계를 반환 합니다 .nums

접근하다

마지막 문제와 유사하게 우리는 셀이 하위 배열의 최소 요소에 기여하는 횟수를 계산합니다. 또한 셀이 하위 배열의 최대값으로 기여하는 횟수를 계산합니다. 각 배열에서 최대값과 최소값의 차이를 원하기 때문에 모든 최소 기여도를 빼고 모든 최대 기여도를 더합니다.

코드 구현

def subArrayRanges(nums):
    res = 0
    inf = float('inf')
    A = [-inf] + nums + [-inf]
    s = []
    for i, x in enumerate(A):
        while s and A[s[-1]] > x:
            j = s.pop()
            k = s[-1]
            res -= A[j] * (i - j) * (j - k)
        s.append(i)
        
    A = [inf] + nums + [inf]
    s = []
    for i, x in enumerate(A):
        while s and A[s[-1]] < x:
            j = s.pop()
            k = s[-1]
            res += A[j] * (i - j) * (j - k)
        s.append(i)
    return res
print(subArrayRanges([1,2,3]))

차원이 N*N 인 2D 행렬 A 가 주어지면 가능한 모든 부분행렬의 합을 반환해야 합니다.

접근하다

모든 부분행렬을 생성하면 n⁴의 시간 복잡도가 됩니다. 셀이 전체 합계에서 기여도를 찾을 수 있는 모든 부분행렬에 나타나는 횟수를 계산하면 줄일 수 있습니다. 우리는 아래 그림과 같이 이 접근 방식을 취합니다.

코드 구현

def subMatricesSum(A):
    m, n = len(A), len(A[0])
    res = 0
    for i in range(m):
        for j in range(n):
            res += A[i][j]*(i+1)*(j+1)*(m-i)*(n-j)
    return res
print(subMatricesSum([ [1, 1], [1, 1]]))