239. 滑动窗口最大值
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = collections.deque()
ans = []
for i in range(len(nums)):
while queue and nums[queue[-1]] < nums[i]: queue.pop()
queue.append(i)
if queue[0] == i - k: queue.popleft()
if i + 1 < k: continue
ans.append(nums[queue[0]])
return ans
面试题59 – II. 队列的最大值
class MaxQueue:
def __init__(self):
self.queue = collections.deque()
self.M_queue = collections.deque()
def max_value(self) -> int:
return self.M_queue[0] if self.M_queue else -1
def push_back(self, value: int) -> None:
self.queue.append(value)
while self.M_queue and self.M_queue[-1] < value: self.M_queue.pop()
self.M_queue.append(value)
def pop_front(self) -> int:
if not self.queue:
return -1
if self.queue[0] == self.M_queue[0]: self.M_queue.popleft()
return self.queue.popleft()
# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
862. 和至少为 K 的最短子数组
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
pre_sum = [0] * (len(nums) + 1)
for i in range(len(pre_sum) - 1):
pre_sum[i + 1] = pre_sum[i] + nums[i]
queue = []
pos = -1
ans = 50001
for i in range(len(pre_sum)):
while queue and pre_sum[i] - pre_sum[queue[0]] >= k:
pos = queue[0]
queue.pop(0)
if pos != -1:
ans = min(ans, i - pos)
while queue and pre_sum[i] < pre_sum[queue[-1]]:
queue.pop()
queue.append(i)
return ans if ans < 50001 else -1
1438. 绝对差不超过限制的最长连续子数组
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
q_max = collections.deque()
q_min = collections.deque()
i, j = 0, 0
ans = 0
for num in nums:
while q_max and q_max[-1] < num: q_max.pop()
while q_min and q_min[-1] > num: q_min.pop()
q_max.append(num)
q_min.append(num)
j += 1
while q_max[0] - q_min[0] > limit:
if q_max[0] == nums[i]: q_max.popleft()
if q_min[0] == nums[i]: q_min.popleft()
i += 1
ans = max(ans, j - i)
return ans
513. 找树左下⻆的值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = collections.deque()
queue.append(root)
ans = 0
while queue:
ans = queue[0].val
for i in range(len(queue)):
node = queue.popleft()
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return ans
135. 分发糖果
class Solution:
def candy(self, ratings: List[int]) -> int:
nums = [0] * len(ratings)
cd = 0
for i in range(len(ratings)):
if i and ratings[i] > ratings[i - 1]: cd += 1
else: cd = 1
nums[i] = cd
for i in range(len(ratings) - 1, -1, -1):
if i < len(ratings) - 1 and ratings[i] > ratings[i + 1]: cd += 1
else: cd = 1
nums[i] = max(cd, nums[i])
return sum(nums)
365. 水壶问题
class Solution:
def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
def next_state(k, x, y, X, Y): # x 和 y 表示当前状态的容量，X 和Y 表示 x 和 y 杯 的总容量
if k == 0: return (0, y)
elif k == 1: return(x, 0)
elif k == 2: return(X, y)
elif k == 3: return(x, Y)
elif k == 4: return(0, y + x) if x + y < Y else (x - (Y - y), Y)
elif k == 5: return(x + y, 0) if x + y < X else (X, y - (X - x))
return (-1, -1)
queue = collections.deque()
vis = set()
queue.append((0, 0))
vis.add((0, 0))
while queue:
cur = queue.popleft()
if cur[0] + cur[1] == targetCapacity or cur[0] == targetCapacity or cur[1] == targetCapacity:
return True
for i in range(6):
tmp = next_state(i, cur[0], cur[1], jug1Capacity, jug2Capacity)
if tmp in vis: continue
vis.add(tmp)
queue.append(tmp)
return False
1760. 袋子里最少数目的球
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
def f(nums, k):
count = 0
for i in range(len(nums)):
count += nums[i] // k
if nums[i] % k: continue
count -= 1
return count
def binary_search(nums, l, r, maxOperations):
if l == r: return l
mid = (l + r) // 2
if f(nums, mid) <= maxOperations: r = mid
else: l = mid + 1
return binary_search(nums, l, r, maxOperations)
return binary_search(nums, max(1, sum(nums) // (len(nums) + maxOperations)), sum(nums) // maxOperations, maxOperations)
45. 跳跃游戏 II
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) < 2: return 0
pos = nums[0]
pre = 1
count = 1
while pos + 1 < len(nums):
max_idx = pre
for i in range(pre, pos + 1):
if i + nums[i] > max_idx + nums[max_idx]:
max_idx = i
pre = pos + 1
pos = max_idx + nums[max_idx]
count += 1
return count
93. 复原 IP 地址
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def dfs(s, k, ind, ret): # k 表示处理第几段（一共四段）
if k == 4:
## 处理最后一段
## 添加到我们的答案集合
if len(s) <= ind: return
if len(s) - ind > 1 and s[ind] == '0': return
num = 0
for i in range(ind, len(s)):
num = num * 10 + ord(s[i]) - ord('0')
if num > 255: return
ret.append(''.join(s))
return
num = 0
for i in range(ind, len(s)):
num = num * 10 + ord(s[i]) - ord('0')
if num > 255: return
if i >= ind + 1 and s[ind] == '0': return
tmp = s.copy()
tmp.insert(i + 1, '.')
dfs(tmp, k + 1, i + 2, ret)
s = list(s)
ret = []
dfs(s, 1, 0, ret)
return ret
46. 全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(nums, idx, buff, ans):
buff.append(nums[idx])
if len(buff) == len(nums):
ans.append(buff)
return
for i in range(len(nums)):
if nums[i] in buff: continue
tmp = buff.copy()
dfs(nums, i, tmp, ans)
ans = []
for i in range(len(nums)):
dfs(nums, i, [], ans)
return ans
43. 字符串相乘
class Solution:
def multiply(self, num1: str, num2: str) -> str:
a = list(map(int, num1[::-1]))
b = list(map(int, num2[::-1]))
c = [0] * (len(a) + len(b))
for i in range(len(a)):
for j in range(len(b)):
c[i + j] += a[i] * b[j]
for i in range(len(c)):
if c[i] < 10: continue
if i + 1 == len(c): c.append(0)
c[i + 1] += c[i] // 10
c[i] %= 10
while len(c) > 1 and c[-1] == 0:
c.pop()
return ''.join(list(map(str, c))[::-1])
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76879.html
