线段树
简单来说，线段树是一种在空间和时间开销上取得平衡的一种维护区间的结构。
总结一些特征如下：
- 使用数组存储线段树，根节点下标为
1（这是存储树的数组下标），维护的区间下标是1到n（这是要维护的数组下标），其每个孩子都维护一个二分区间，即m = (l + r) // 2作为区间中点，左孩子维护l到m，右孩子维护m + 1到r。 - 实际要维护的数组可能有数个，以具体题目为准。
- 每个结点
o的左孩子下标为o * 2，右孩子下标为o * 2 + 1。 - 通常而言，如果要维护的数组大小为
n，那么分配给线段树的数组大小可以用n * 4，这绰绰有余。而如果想尽量节约空间，可以用m = 2 << n.bit_length()大小的数组，这是最优的空间。例如，n = 10时，10的二进制形式为1010，其长度为 4 ，那么我们应当使用100000，即 32 的空间（16 * 2）。 - 线段树适用于需要频繁查询、更新某个区间的情况。
1. 构造字典序最大的合并字符串
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
写得越快，要改的越多。怎么总是漏掉细节。
看了题解感觉自己真XX，python自带不等号可以判断字符串的字典序，直接用就行了。
代码
# 虽然没有大问题，但是太长了
class Solution:
def largestMerge(self, word1: str, word2: str) -> str:
m = len(word1)
n = len(word2)
i = j = 0
ans = ""
while i < m or j < n:
if i == m and j < n:
ans += word2[j::]
break
elif i < m and j == n:
ans += word1[i::]
break
else:
if word1[i] > word2[j]:
ans += word1[i]
i += 1
elif word1[i] < word2[j]:
ans += word2[j]
j += 1
else:
origin_i, origin_j = i, j
while i < m and j < n and word1[i] == word2[j]:
i += 1
j += 1
if i == m:
i = origin_i
ans += word2[origin_j]
j = origin_j + 1
elif j == n:
j = origin_j
ans += word1[origin_i]
i = origin_i + 1
elif word1[i] < word2[j]:
i = origin_i
ans += word2[origin_j]
j = origin_j + 1
else:
j = origin_j
ans += word1[origin_i]
i = origin_i + 1
return ans正解：
class Solution:
def largestMerge(self, word1: str, word2: str) -> str:
m = len(word1)
n = len(word2)
i = j = 0
ans = ""
while i < m or j < n:
if i == m:
ans += word2[j::]
break
elif j == n:
ans += word1[i::]
break
elif word1[i::] > word2[j::]:
ans += word1[i]
i += 1
else:
ans += word2[j]
j += 1
return ans2. 由单个字符重复的最长子字符串
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
昨天遇到的线段树应用题，今天学习了相关内容，按照题解思路敲了一遍。
代码
class Solution:
def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
s = list(s)
n = len(s)
m = 2 << n.bit_length()
pre = [0 for i in range(m)]
suf = [0 for i in range(m)]
mx = [0 for i in range(m)]
def maintain(o: int, l: int, r: int) -> None:
pre[o] = pre[o << 1]
suf[o] = suf[(o << 1) + 1]
mx[o] = max(mx[o << 1], mx[(o << 1) + 1])
m = (l + r) >> 1
if s[m - 1] == s[m]:
if suf[o << 1] == m - l + 1:
pre[o] += pre[(o << 1) + 1]
if pre[(o << 1) + 1] == r - m:
suf[o] += suf[o << 1]
mx[o] = max(mx[o], suf[o << 1] + pre[(o << 1) + 1])
def build(o: int, l: int, r:int) -> None:
if l == r:
pre[o] = 1
suf[o] = 1
mx[o] = 1
return
m = (l + r) >> 1
build(o << 1, l, m)
build((o << 1) + 1, m + 1, r)
maintain(o, l, r)
def update(o: int, l: int, r: int, i: int) -> None:
if l == r:
return
m = (l + r) >> 1
if i <= m:
update(o << 1, l, m, i)
else:
update((o << 1) + 1, m + 1, r, i)
maintain(o, l, r)
build(1, 1, n)
ans = []
for ch, i in zip(queryCharacters, queryIndices):
s[i] = ch
update(1, 1, n, i + 1)
ans.append(mx[1])
return ans3. 区域和检索 - 数组可修改
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
线段树典型应用，只Debug一次就过了，舒服。
写的时候一定要处处注意下标相差1的问题，不然会很痛苦。
代码
class NumArray:
__sum: List[int]
__n: int
def __init__(self, nums: List[int]):
self.__n = len(nums)
m = 2 << self.__n.bit_length()
self.__sum = [0 for i in range(m)]
def build(o: int, l: int, r: int) -> None:
if l == r:
self.__sum[o] = nums[l - 1]
return
m = (l + r) // 2
build(o << 1, l, m)
build((o << 1) + 1, m + 1, r)
self.maintain(o, l, r)
build(1, 1, self.__n)
def maintain(self, o: int, l: int, r: int) -> None:
self.__sum[o] = self.__sum[o << 1] + self.__sum[(o << 1) + 1]
def change(self, o: int, l: int, r: int, idx: int, val:int) -> None:
if l == r:
self.__sum[o] = val
return
m = (l + r) >> 1
if idx <= m:
self.change(o << 1, l, m, idx, val)
else:
self.change((o << 1) + 1, m + 1, r, idx, val)
self.maintain(o, l, r)
def index(self, o: int, l: int, r: int, L: int, R: int) -> None:
if L == l and R == r:
return self.__sum[o]
else:
m = (l + r) // 2
if R <= m:
return self.index(o << 1, l, m, L, R)
elif L > m:
return self.index((o << 1) + 1, m + 1, r, L, R)
else:
return self.index(o << 1, l, m, L, m) + self.index((o << 1) + 1, m + 1, r, m + 1, R)
def update(self, index: int, val: int) -> None:
self.change(1, 1, self.__n, index + 1, val)
def sumRange(self, left: int, right: int) -> int:
return self.index(1, 1, self.__n, left + 1, right + 1)4. 最长递增子序列的个数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
看起来是用动规解比较容易明白，但没想好怎么设计DP数组，看到题解思路是： dp 存储结尾最大长度， cnt 存储结尾最大长度的数量，然后写出来了。
线段树做法比较奇怪，暂时不考虑。
代码
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1 for i in range(n)]
cnt = [1 for i in range(n)]
maxLen = 1
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
if dp[j] + 1 > dp[i]:
cnt[i] = cnt[j]
dp[i] = dp[j] + 1
elif dp[j] + 1 == dp[i]:
cnt[i] += cnt[j]
maxLen = maxLen if maxLen > dp[i] else dp[i]
ans = 0
for i in range(n):
if dp[i] == maxLen:
ans += cnt[i]
return ans
Comments NOTHING