2353. 设计食物评分系统
懒删除，查看堆顶的食物评分是否等于其实际值，若不相同则意味着对应的元素已被替换成了其他值，堆顶存的是个垃圾数据，直接弹出堆顶；否则堆顶就是答案。
from collections import defaultdict
import heapq
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.food_rating = {foods[i]: ratings[i] for i in range(len(foods))}
self.food_cuisine = {foods[i]: cuisines[i] for i in range(len(foods))}
self.cuisines: Dict[str, list] = defaultdict(list)
for i in range(len(cuisines)):
self.cuisines[cuisines[i]].append((-self.food_rating[foods[i]], foods[i]))
for k, v in self.cuisines.items():
heapq.heapify(v)
def changeRating(self, food: str, newRating: int) -> None:
self.food_rating[food] = newRating
heapq.heappush(self.cuisines[self.food_cuisine[food]], (-newRating, food))
def highestRated(self, cuisine: str) -> str:
while -self.cuisines[cuisine][0][0] != self.food_rating[self.cuisines[cuisine][0][1]]:
heapq.heappop(self.cuisines[cuisine])
return self.cuisines[cuisine][0][1]1736. 替换隐藏数字得到的最晚时间
class Solution:
def maximumTime(self, time: str) -> str:
ans = ''
for i in range(len(time)):
if time[i] == '?':
if i == 0 and (time[1] < '4' or time[1] == '?'):
ans += '2'
elif i == 0:
ans += '1'
elif i == 1 and ans == '2':
ans += '3'
elif i == 1:
ans += '9'
elif i == 3:
ans += '5'
elif i == 4:
ans += '9'
else:
ans += time[i]
return ans169. 多数元素
from collections import defaultdict
class Solution:
def majorityElement(self, nums: List[int]) -> int:
d = defaultdict(int)
half = len(nums) // 2
for num in nums:
d[num] += 1
if d[num] > half:
return num2057. 值相等的最小索引
class Solution:
def smallestEqual(self, nums: List[int]) -> int:
for i, num in enumerate(nums):
if i % 10 == num:
return i
return -1763. 划分字母区间
from typing import List
class Solution:
def partitionLabels(self, s: str) -> List[int]:
d = {}
for i in range(len(s)):
d[s[i]] = i
ans = []
border_right = -1
border_left = -1
for p in range(len(s)):
border_right = d[s[p]] if border_right < d[s[p]] else border_right
if p == border_right:
ans.append(border_right - border_left)
border_left = border_right
return ansLCR 153. 二叉树中和为目标值的路径
class Solution:
def __init__(self):
self.ans = []
def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:
if not root:
return []
self.dfs(root, target, 0, [])
return self.ans
def dfs(self, node: TreeNode, target, now_val, path):
if not node.left and not node.right:
if now_val + node.val == target:
self.ans.append(path + [node.val])
return
path.append(node.val)
if node.right:
self.dfs(node.right, target, now_val + node.val, path)
if node.left:
self.dfs(node.left, target, now_val + node.val, path)
path.pop()
599. 两个列表的最小索引总和
class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
index1 = {list1[i]: i for i in range(len(list1))}
index2 = {list2[i]: i for i in range(len(list2))}
ans = []
cnt = float('inf')
for item in set(list1) & set(list2):
now_cnt = index1[item] + index2[item]
if cnt > now_cnt:
cnt = now_cnt
ans = [item]
elif cnt == now_cnt:
ans.append(item)
return ans1758. 生成交替二进制字符串的最少操作数
class Solution:
def minOperations(self, s: str) -> int:
dp0 = [0] * (len(s) + 1)
dp1 = [0] * (len(s) + 1)
for i in range(len(s)):
if s[i] == '0':
dp0[i] = dp1[i - 1]
dp1[i] = dp0[i - 1] + 1
else:
dp1[i] = dp0[i - 1]
dp0[i] = dp1[i - 1] + 1
return min(dp0[-2], dp1[-2])1491. 去掉最低工资和最高工资后的工资平均值
class Solution:
def average(self, salary: List[int]) -> float:
min_salary = salary[0]
max_salary = salary[1]
total = 0
for s in salary:
if s < min_salary:
min_salary = s
if s > max_salary:
max_salary = s
total += s
return (total - min_salary - max_salary) / (len(salary) - 2)LCR 084. 全排列 II
class Solution:
def __init__(self):
self.ans = []
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.recursion(nums, [])
return self.ans
def recursion(self, candidate, ans):
if not candidate:
self.ans.append(ans[:])
used = set()
for i in range(len(candidate)):
if candidate[i] not in used:
ans.append(candidate[i])
self.recursion(candidate[:i] + candidate[i + 1:], ans)
ans.pop()
used.add(candidate[i])
Comments | NOTHING