什么是前綴和？前綴和是一個(gè)數(shù)組的某項(xiàng)下標(biāo)之前(包括此項(xiàng)元素)的所有數(shù)組元素的和。
設(shè) b[] 為前綴和數(shù)組，a[] 為原數(shù)組，根據(jù)這句話可以得到前綴和的定義式和遞推式：
| 定義式 | 遞推式 | |
|---|---|---|
| 一維前綴和 | ||
| 二維前綴和 |
303. 區(qū)域和檢索 - 數(shù)組不可變
題目描述：
給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內(nèi)元素的總和，包含 i, j 兩點(diǎn)。
示例：
給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數(shù)為 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
說明:
你可以假設(shè)數(shù)組不可變。
會(huì)多次調(diào)用 sumRange 方法。
Related Topics 動(dòng)態(tài)規(guī)劃
非?；A(chǔ)的前綴和算法，我們先計(jì)算并保存前綴和數(shù)組，檢索的時(shí)候直接調(diào)用即可：
class NumArray:
def __init__(self, nums):
"""
:param nums: List[int]
"""
self.nums = nums
self.cumSums = [0]
for num in self.nums:
self.cumSums.append(self.cumSums[-1]+num)
def sumRange(self, i: int, j: int) -> int:
return self.cumSums[j+1] - self.cumSums[i]
304. 二維區(qū)域和檢索 - 矩陣不可變
題目描述：
給定一個(gè)二維矩陣，計(jì)算其子矩形范圍內(nèi)元素的總和，該子矩陣的左上角為 (row1, col1) ，
右下角為 (row2, col2)。
上圖子矩陣左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，該子矩形內(nèi)元素的總和為 8。
示例:
給定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
說明:
你可以假設(shè)矩陣不可變。
會(huì)多次調(diào)用 sumRegion 方法。
你可以假設(shè) row1 ≤ row2 且 col1 ≤ col2。
Related Topics 動(dòng)態(tài)規(guī)劃
這又是非?；A(chǔ)的二維前綴和算法，我們先計(jì)算二維的前綴和數(shù)組并保存，檢索的時(shí)候直接調(diào)用結(jié)果：
import numpy as np
class NumMatrix:
def __init__(self, matrix):
"""
前綴和
:param matrix: List[List[int]]
"""
self.matrix = np.array(matrix)
if self.matrix.size == 0:
return
# 計(jì)算前綴和
rows, cols = self.matrix.shape
self.cumSums = np.zeros((rows+1, cols+1), dtype=int)
for i in range(rows):
for j in range(cols):
self.cumSums[i+1, j+1] = self.cumSums[i, j+1] + self.cumSums[i+1, j] \
- self.cumSums[i, j] + self.matrix[i, j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.cumSums[row2+1, col2+1] - self.cumSums[row1, col2+1] - \
self.cumSums[row2+1, col1] + self.cumSums[row1, col1]
525. 連續(xù)數(shù)組
題目描述：
給定一個(gè)二進(jìn)制數(shù)組, 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組（的長度）。
示例 1:
輸入: [0,1]
輸出: 2
說明: [0, 1] 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
示例 2:
輸入: [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
注意: 給定的二進(jìn)制數(shù)組的長度不會(huì)超過50000。
Related Topics 哈希表
首先想到的是暴力解法，遍歷每個(gè)子區(qū)間，統(tǒng)計(jì) 0 和 1 的數(shù)量，如果 0 和 1 的數(shù)量相等，再更新最大長度，這樣的時(shí)間復(fù)雜度為 ；我們可以在這個(gè)基礎(chǔ)上進(jìn)行優(yōu)化，在外層循環(huán)內(nèi)定義兩個(gè)變量
zeros 和 ones 來記錄 0 和 1 的數(shù)量，這樣可以將時(shí)間復(fù)雜度降低至 。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
if nums is None or len(nums) <= 1:
return 0
maxlen = 0
for i in range(len(nums)):
zeros, ones = 0, 0
for j in range(i, len(nums)):
if nums[j] == 0:
zeros += 1
else:
ones += 1
if zeros == ones:
maxlen = max(maxlen, j-i+1)
return maxlen
當(dāng)我們欣喜的點(diǎn)擊提交后，缺遲遲未得到反饋結(jié)果，終于：超出時(shí)間限制。
想想 的時(shí)間復(fù)雜度，確實(shí)不夠高效。那又該從何開始優(yōu)化呢？
仔細(xì)分析上面的解法，如上圖，我們要求的子區(qū)間為 ， 為整個(gè)區(qū)間的起點(diǎn)， 為要求的子區(qū)間的起點(diǎn)， 為要求的子區(qū)間的終點(diǎn)。我們依次固定 點(diǎn)，然后遍歷 、計(jì)數(shù)、判斷、更新結(jié)果。由于 在 之間，我們每次循環(huán)都要重復(fù)遍歷一遍 的某個(gè)子區(qū)間，那有沒有辦法通過一次遍歷就得到結(jié)果呢？一次遍歷，那肯定需要記錄多個(gè)結(jié)果，所以肯定要用到哈希表。我們再來看哈希表記錄什么，由于子區(qū)間 中
0 和 1 數(shù)量相等，假如我們將 0 改為 -1，那區(qū)間 之間 0(-1) 和 1 求和恰好為 0，也就是說 之間 0(-1) 和 1 求和的結(jié)果和 之間 0(-1) 和 1 求和的結(jié)果是相同的！也就是說當(dāng)我們遇到兩個(gè)相同求和結(jié)果的時(shí)候，便是滿足 0 和 1 相等的時(shí)候，此時(shí)的區(qū)間也就是滿足條件的一個(gè)候選區(qū)間，那該如何計(jì)算區(qū)間的長度呢？我們只需要知道上一次該求和結(jié)果的位置。所以哈希表需要記錄的數(shù)據(jù)便也清楚了：求和結(jié)果為鍵，上一次的位置為值。但是仔細(xì)一思考發(fā)現(xiàn)，題目要求的是最長的子區(qū)間，所以我們哈希表記錄的值應(yīng)該為求和結(jié)果第一次出現(xiàn)的位置。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
if nums is None or len(nums) <= 1:
return 0
maxlen, count = 0, 0
# 記錄該count下的第一個(gè)index
hashmap = {0: -1}
for i in range(len(nums)):
count += 1 if nums[i] == 0 else -1
if hashmap.get(count) is not None:
maxlen = max(maxlen, i-hashmap.get(count))
else:
hashmap[count] = i
return maxlen
1371. 每個(gè)元音包含偶數(shù)次的最長子字符串
題目描述：
給你一個(gè)字符串 s ，請你返回滿足以下條件的最長子字符串的長度：每個(gè)元音字母，
即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出現(xiàn)了偶數(shù)次。
示例 1：
輸入：s = "eleetminicoworoep"
輸出：13
解釋：最長子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 個(gè)，以及 0 個(gè) a，u 。
示例 2：
輸入：s = "leetcodeisgreat"
輸出：5
解釋：最長子字符串是 "leetc" ，其中包含 2 個(gè) e 。
示例 3：
輸入：s = "bcbcbc"
輸出：6
解釋：這個(gè)示例中，字符串 "bcbcbc" 本身就是最長的，因?yàn)樗械脑?a，e，i，o，u 都出現(xiàn)了 0 次。
提示：
1 <= s.length <= 5 x 10^5
s 只包含小寫英文字母。
Related Topics 字符串
題目分析：
要求最長子字符串，也就是一個(gè)最長子區(qū)間，那和我們上一題類似。在上一題中，我們的 count 變量是記錄 0 比 1 多出來的次數(shù)，當(dāng)區(qū)間 0 和 1 次數(shù)相等時(shí)，count 變量還是同一個(gè)值。類比到此題，我們希望有一個(gè)變量能夠記錄元音字母 a, e, i, o, u 出現(xiàn)的次數(shù)，并且希望其在元音字母恰好出現(xiàn)了偶數(shù)次的時(shí)候，這個(gè)變量的值能夠和上一次相等。
題目只是要求偶數(shù)次，偶數(shù)，即是 x % 2 == 0，那我們便可以想到利用二進(jìn)制來存儲(chǔ)：當(dāng)出現(xiàn)一次(奇數(shù)次)時(shí)，我們記錄為 1，出現(xiàn)兩次(偶數(shù)次)時(shí)，我們記錄為 0， 于是可以利用異或 ^ 來計(jì)算結(jié)果。由于要記錄5個(gè)元音字母，那我們可以用5個(gè)二進(jìn)制位來進(jìn)行記錄，所以這里的 count 范圍為 00000-11111。當(dāng)區(qū)間中元音字母都出現(xiàn)偶數(shù)次時(shí)，count 還是同一個(gè)結(jié)果。(代碼中的 status 即為分析中的 count)
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
# status 用來記錄元音字母出現(xiàn)的奇偶性組合
maxlen, status = 0, 0
# 記錄status第一次出現(xiàn)的位置
hashmap = {0: -1}
for i in range(len(s)):
if s[i] == 'a':
status ^= 1 << 0
elif s[i] == 'e':
status ^= 1 << 1
elif s[i] == 'i':
status ^= 1 << 2
elif s[i] == 'o':
status ^= 1 << 3
elif s[i] == 'u':
status ^= 1 << 4
if hashmap.get(status) is not None:
maxlen = max(maxlen, i-hashmap.get(status))
else:
hashmap[status] = i
return maxlen
