0X00 leetcode 刷题 5 道
- leetcode 312. Burst Balloons
- leetcode 443. String Compression
- leetcode 209. Minimum Size Subarray Sum
- leetcode 3. Longest Substring Without Repeating Characters
- leetcode 76. Minimum Window Substring
0X01 每道题的小小记录
312. Burst Balloons
区间型动态规划, 大致思路就是
- 首先这是一种「消去型」的问题,要将问题转换成左右子问题
- 添加两个不能扎破的气球
-
dp[i][j]代表 [i+1 j-1] 区间内的最大得分,也就是说当长度为 2 的时候为 0 因为不能扎破 - 长度递增,再枚举中间分割的气球
class Solution:
def maxCoins(self, nums: List[int]) -> int:
# 区间型动态规划
# 消去型的问题,不能按着题目意思来
# 一定要想成左边右边的子问题
# dp[i][j] 代表 i+1 j-1 的最大 coins
# 所以要加上两端不能扎破的气球
if len(nums) == 0: return 0
m = len(nums) + 2
coins = [0] * m
for i in range(m):
if i == 0 or i == m-1: coins[i] = 1
else: coins[i] = nums[i-1]
dp = [[0] * m for _ in range(m+1)]
# len 2 全是 0
# 从 len 3 开始
for l in range(3, m+1):
for i in range(m - l + 1):
j = i + l - 1
dp[i][j] = float("-inf")
# 遍历比 l 小的长度
for k in range(i+1, j):
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins[i] * coins[k] * coins[j])
return dp[0][-1]
443. String Compression
双指针的变种,因为没有理解题目,坑了我很久
class Solution:
def compress(self, chars: List[str]) -> int:
if len(chars) == 0: return 0
# 三指针去做这个
m = len(chars)
i = j = w = 0
while i < m:
j += 1
if j == m:
chars[w] = chars[i]
if j - i != 1:
t = str(j - i)
for k in range(len(t)):
w += 1
chars[w] = t[k]
w += 1
break
else:
if chars[i] != chars[j]:
chars[w] = chars[i]
if j - i != 1:
t = str(j - i)
for k in range(len(t)):
w += 1
chars[w] = t[k]
w += 1
i = j
return w
坑在:
- 返回最后长度而且要在原 array 上修改
- i, j 记录子串 w 记录写在哪
209. Minimum Size Subarray Sum
接下来的三道题都是滑动窗口的题目
这是一道经典的滑动窗口的题目,废话不多说,直接上代码:
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if len(nums) == 0: return 0
m = len(nums)
j = 0
ans = float("inf")
for i in range(m):
while j < m and target > 0:
target -= nums[j]
j += 1
if target <= 0:
ans = min(ans, j - i )
target += nums[i]
return ans if ans != float("inf") else 0
其中用到的小技巧就是 正数 -
滑动窗口的模板就是
for i in range(m):
while j < m and target > 0:
target -= nums[j]
j += 1
if target <= 0:
ans = min(ans, j - i )
target += nums[i]
注意这里的 j 不是索引,要比索引大 1
3. Longest Substring Without Repeating Characters
滑动窗口题目,用 set 优化
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0: return 0
look_up = set()
left, max_len, cur_len = 0, 0, 0
for c in s:
cur_len += 1
while c in look_up:
look_up.remove(s[left])
cur_len -= 1
left += 1
max_len = max(max_len, cur_len)
look_up.add(c)
return max_len
76. Minimum Window Substring
难一点的滑动窗口题目,里面用了一个小技巧
class Solution:
def minWindow(self, s: str, t: str) -> str:
if t == "": return ""
sourceHash = [0] * 256
targetHash = [0] * 256
# init
for c in t:
targetHash[ord(c)] += 1
minStr = ""
ans = float("inf")
j = 0
for i in range(len(s)):
while not self.valid(sourceHash, targetHash) and j < len(s):
sourceHash[ord(s[j])] += 1
j += 1
if self.valid(sourceHash, targetHash):
if ans > j - i:
minStr = s[i:j]
ans = j - i
sourceHash[ord(s[i])] -= 1
return minStr
def valid(self, sourceHash, targetHash):
for i in range(256):
if targetHash[i] > sourceHash[i]:
return False
return True
这里的时间复杂度是 O(256n),因为所有的字符都是 ASIIC 所以用 256, 而且这里有一个比较坑的东西是
target 里面可以有重复...所以要记录每个字母的出现数量
网友评论