classSolution: defconsecutiveNumbersSum(self, n: int) -> int: i, result = 1, 0 while n / i - (i + 1) / 2 >= 0: # i个数相加, 这i个数的最小值至少是1, n/i是这i个数的均值, 该值一定要比长度的一半大, e.g. n: 15, 5数和是临界状态 if i % 2andnot n % i: # 若i是奇数, 则n必被i整除, 且商为i个数的中位数 result += 1 elifnot i % 2andabs(n / i - 0.5 - n // i) < 1e-6: # 若i是偶数, 则i个数的中位数必为n/i, 且n/i必须是某个整数+0.5 result += 1 i += 1 return result
classSolution: # 排序后, 维护一个子列的最大和最小值, 然后按顺序判断是否能加入这个子列 defpartitionArray(self, nums: List[int], k: int) -> int: sorted_nums = sorted(nums) result = 1 min_temp, max_temp = sorted_nums[0], sorted_nums[0] for n in sorted_nums[1:]: if min_temp <= n <= max_temp: # 在区间内, 直接可以放入 continue if n > max_temp: if n - min_temp <= k: # 在区间外, 但能接受, 需要更新最大值 max_temp = n else: # 在区间外, 不能接受, 更新子序列, 看下一个 min_temp, max_temp = n, n result += 1 elif n < min_temp: if max_temp - n <= k: min_temp = n else: min_temp, max_temp = n, n result += 1 return result
💛2295.
替换数组中的元素
模拟 - Carlos
1 2 3 4 5 6 7 8 9
classSolution: # 存一个值到序号映射的字典, 按题目意思来 defarrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]: d = {n: i for i, n inenumerate(nums)} for old, new in operations: i = d[old] del d[old] d[new] = i nums[i] = new return nums
classSolution: def__init__(self, rects: List[List[int]]): self.rects = [{'coord': (a, b, x, y), 'area': (x - a + 1) * (y - b + 1)} for a, b, x, y in rects] # 注意算面积时要+1, 因为考虑的是整数点的个数!! self.cumsum_area = [_ / sum(temp) for _ in accumulate(temp)] if (temp := [_['area'] for _ in self.rects]) elseNone# [How to find the cumulative sum of numbers in a list?](https://stackoverflow.com/a/53754768/12224183) defpick(self) -> List[int]: idx = bisect_left(self.cumsum_area, random.random()) a, b, x, y = self.rects[idx]['coord'] return [random.randint(a, x), random.randint(b, y)]
🐉[一行Python]
按面积抽样+二分 - Carlos
1 2 3 4 5
classSolution: def__init__(self, rects: List[List[int]]): self.rects = [{'coord': (a, b, x, y), 'area': (x - a + 1) * (y - b + 1)} for a, b, x, y in rects] defpick(self) -> List[int]: return [random.randint(abxy[0], abxy[2]), random.randint(abxy[1], abxy[3])] if (abxy := self.rects[bisect_left([_ / sum(temp) for _ in accumulate(temp)] if (temp := [_['area'] for _ in self.rects]) else [], random.random())]['coord']) else [0, 0]
classSolution: defmatchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool: temp = {_:[_] for _ in s} for a, b in mappings: temp[a] = temp.get(a, []) temp[a].append(b) for i inrange(len(s) - len(sub) + 1): myiter = list(range(len(sub))) random.shuffle(myiter) for j in myiter: if s[i + j] notin temp.get(sub[j], []): break else: returnTrue returnFalse
❤❗
==2302.
统计得分小于 K 的子数组数目==
🎯第 297 场周赛 -
地平线
8 / 19, 1585 / 5915.
💚2303.
计算应缴税款总额
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: defcalculateTax(self, brackets: List[List[int]], income: int) -> float: last_upper = 0 result = 0 for upper, percent in brackets: if income >= upper: result += (upper - last_upper) * percent / 100 elif income >= last_upper: result += (income - last_upper) * percent / 100 else: break last_upper = upper return result
💛2304.
网格中的最小路径代价
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution: defminPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) defmove(grid1, grid2): return [min(grid1[j] + moveCost[grid1[j]][i] for j inrange(n)) for i inrange(n)] grid1 = grid[0] for i inrange(1, m): grid2 = grid[i] temp = move(grid1, grid2) for j inrange(n): for k inrange(n): moveCost[grid2[j]][k] += temp[j] grid1 = grid2 returnmin(grid[-1][_] + temp[_] for _ inrange(n))
classSolution: defdistributeCookies(self, cookies: List[int], k: int) -> int: part = list(range(1, n := len(cookies))) returnmin(max(sum(t[l: r]) for l, r in pairwise((0, ) + cm + (n,))) for t in permutations(cookies) for cm in combinations(part, k - 1))
classSolution: defdistinctNames(self, ideas: List[str]) -> int: n = len(ideas) temp = dict() temp2 = dict() count = dict() for idea in ideas: temp[idea[1:]] = temp.get(idea[1:], []) temp[idea[1:]].append(idea[0]) temp2[idea[0]] = temp2.get(idea[0], []) temp2[idea[0]].append(idea[1:]) print(temp) print(temp2) # {'offee': ['c', 't'], 'onuts': ['d'], 'ime': ['t']} # coffee和toffee不行 # 和所有c打头的不行 # 和所有t打头的不行, coffee和time换后变成toffee, toffee和time也不行 result = n * (n - 1) for key, value in temp.items(): result -= len(value) * (len(value)) -1 #print('self', result) iflen(value) > 1: for s in value: if s in temp2: print(s, len(temp2[s]) - 1, len(value)) result -= (len(temp2[s]) - 1) * len(value) print('>1', result) else: #print(value[0]) #print(temp2[value[0]]) #print([len(temp[_]) for _ in temp2[value[0]]]) result -= sum(len(temp[_]) for _ in temp2[value[0]] iflen(temp[_]) > 1) #print('=1', result) return result
数学统计题, 熬到最后一刻, 没对.
💛890.
查找和替换模式
维护一一映射 - Carlos
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution: deffindAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: result = [] for word in words: temp = dict() # 维护一个一一映射, 把pattern中的字符映到word中 for i inrange(len(pattern)): if pattern[i] in temp: # 该元素已经在映射中出现过了 if temp[pattern[i]] != word[i]: # 若检查到待构造的映射是一映多的, break break else: if word[i] in temp.values(): # 这一行是为了防止把ccc判为abb, 即防止映射多映一!! break else: temp[pattern[i]] = word[i] # 构造映射 else: result.append(word) return result
💚1051.
高度检查器
排序 - Carlos
1 2 3
classSolution: # 即返回与递增排序不同位置得元素个数, 写了个排序糊弄, 时间满足要求 defheightChecker(self, heights: List[int]) -> int: returnsum(_ != heights[i] for i, _ inenumerate(sorted(heights)))
classSolution: deffindPairs(self, nums: List[int], k: int) -> int: nums = sorted(nums) n = len(nums) temp = [] result = 0 for i inrange(n): for j inrange(i + 1, n): if nums[j] - nums[i] == k and (nums[i], nums[j]) notin temp: result += 1 temp.append((nums[i], nums[j])) elif nums[j] - nums[i] > k: break return result
数组中的
k-diff 数对 - 力扣官方题解
方法一: 哈希表 (时On空On)
1 2 3 4 5 6 7 8 9 10
classSolution: # 核心观察是目标数组的同位置元素是各不相同的, 因此便利一边, 观察其为最小元素时, 左侧所有元素是否有满足的 deffindPairs(self, nums: List[int], k: int) -> int: visited, res = set(), set() for num in nums: if num - k in visited: res.add(num - k) # 加入最小的!! if num + k in visited: res.add(num) # 加入最小的!! visited.add(num) returnlen(res)
classSolution: # x为小数下表, y为大数下标 deffindPairs(self, nums: List[int], k: int) -> int: nums.sort() n, y, res = len(nums), 0, 0 for x inrange(n): if x == 0or nums[x] != nums[x - 1]: while y < n and (nums[y] < nums[x] + k or y <= x): # y<=x是为了保证k=0时下标不同 y += 1 if y < n and nums[y] == nums[x] + k: res += 1 return res ======= # :yellow_heart: [875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/)
classSolution: defduplicateZeros(self, arr: List[int]) -> None: num = 0 for i inrange(len(arr)): if i + num < len(arr) and arr[i + num] == 0: arr.insert(i + num, 0) arr.pop() num += 1
classSolution: # 字母表挨个检查就完了 defgreatestLetter(self, s: str) -> str: for i inrange(26)[::-1]: ifchr(65 + i) in s andchr(97 + i) in s: returnchr(65 + i) return""
💛2310.
个位数字为 K 的整数之和
1 2 3 4 5 6 7
classSolution: # 观察到所求只与num的个位数有关, num=0和k=0时分别WA一发, 都特殊处理就好了 defminimumNumbers(self, num: int, k: int) -> int: if num == 0: return0 if k == 0: return -1if num % 10else1 for i inrange(1, int(num // k + 1)): if (i * k) % 10 == num % 10: return i return -1
classSolution: deffindBottomLeftValue(self, root: Optional[TreeNode]) -> int: q = deque([root]) # 维护一个队列, 先进先出 while q: node = q.popleft() # 节点是从右侧加入的, 因此要从左侧删去 if node.right: q.append(node.right) if node.left: q.append(node.left) ans = node.val return ans
❤30.
串联所有单词的子串
逐个检查 - Carlos
1 2 3 4 5 6 7 8 9 10 11
classSolution: deffindSubstring(self, s: str, words: List[str]) -> List[int]: length = len(words[0]) result = [] for i inrange(len(s) - length * len(words) + 1): # 一定要+1, 否则会漏掉一个 temp = words[:] # 记录一个words的拷贝, 逐个检查, 查到一个删掉一个 for j inrange(len(words)): if (word := s[i+j*length:i+(j+1)*length]) in temp: temp.remove(word) else: break else: result.append(i) # 此时temp为空, 符合条件 return result
[Python/Java/TypeScript/Go]
哈希计数暴力 - Benhao
1 2 3 4
classSolution: # [i for i in 起始位置 if Counter相同] deffindSubstring(self, s: str, words: List[str]) -> List[int]: cnts, step = Counter(words), len(words[0]) return [i for i inrange(len(s) - step * len(words) + 1) if Counter([s[i+j*step:i+(j+1)*step] for j inrange(len(words))]) == cnts]
思路和我的一致, 但使用Counter避免了拷贝再检查的循环.
💛515.
在每个树行中找最大值
BFS层序遍历 - Carlos
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: deflargestValues(self, root: Optional[TreeNode]) -> List[int]: ifnot root: return [] queue, result = [root], [] while queue: result.append(max(_.val for _ in queue)) temp = [] for n in queue: if n.left: temp.append(n.left) if n.right: temp.append(n.right) queue = temp return result
classSolution: # 贪心, 每次贪可选的两个颜色中价格最低的 defminCost(self, costs: List[List[int]]) -> int: result = [0, 0, 0] for i inrange(3): result[i] = min(costs[0]) idx = i for cost in costs[1:]: idx, temp = min([(j, _) for j, _ inenumerate(cost) if j != idx], key=lambda x: x[1]) result[i] += temp returnmin(result) # WA: 对于[[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]], 得到result为[47, 47, 44], 而答案为43
1 2 3 4 5 6
classSolution: # DP, 第i个房间, 分别涂成颜色c的最低花费为, 该花费加上第i个房间涂成非c颜色的最小值 defminCost(self, costs: List[List[int]]) -> int: for i inrange(1, len(costs)): for j inrange(3): costs[i][j] += min(costs[i - 1][_] for _ inrange(3) if _ != j) returnmin(costs[-1])
🎯 第 81 场双周赛 - BOE
京东方
3 / 19, 1735 / 3847.
💚2315.
统计星号
1 2 3 4 5 6 7 8 9 10
classSolution: # 判断成对括号外的*, 设置一个state标志逐个统计就好 defcountAsterisks(self, s: str) -> int: state = True result = 0 for _ in s: if _ == '|': ifnot state: state = True else: state = False if state and _ == '*': result += 1 return result
classSolution: # 我理解为统计各个连通分支的顶点个数, 然后考虑怎么算出答案就好, 最后在1e5的最大实例上TLE了 defcountPairs(self, n: int, edges: List[List[int]]) -> int: adj_list = {_: set() for _ inrange(n)} for a, b in edges: adj_list[a].add(b) adj_list[b].add(a) ccs_num = [] # connected component的顶点个数列表, 且顶点个数时 nodes = set(range(n)) # 未访问的顶点集合 while nodes: # 整体思路和贪吃蛇3v3和奥林匹克环境的spread函数比较像 start_node = nodes.pop() visited = {start_node} cc = {start_node} while visited: # temp = set() # for v in visited: # for u in adj_list[v]: # if u not in cc: # temp.add(u) # temp = {u for u in adj_list[v] if u not in cc for v in visited} temp = {u for v in visited for u in adj_list[v] if u notin cc} # 不在连通分支的1邻居 visited = temp cc = cc.union(temp) ccs_num.append(len(cc)) nodes -= cc returnsum(_ * (n - _) for _ in ccs_num) // 2# 每个连通分支上的点都和其余所有点不相连, 遍历每个连通分支, 最后因为每个点对被算了两边, 因此要除以2
❗💛 ==2317.
操作后的最大异或和==
概念不懂.
❗❤ ==2318.
不同骰子序列的数目==
好难, 考虑三维DP, 不会做.
🎯第 299 场周赛 -
神策数据
7 / 18, 2168 / 6108.
💚2319.
判断矩阵是否是一个 X 矩阵
1 2 3 4 5 6 7 8
classSolution: # 逐个判断即可 defcheckXMatrix(self, grid: List[List[int]]) -> bool: n = len(grid) for i inrange(n): for j inrange(n): if (i == j or i + j == n - 1) and grid[i][j] == 0: returnFalse if i != j and i + j != n - 1and grid[i][j] != 0: returnFalse returnTrue
classSolution: def__init__(self, n: int, blacklist: List[int]): m = len(blacklist) self.bound = w = n - m black = {b for b in blacklist if b >= self.bound} self.b2w = {} for b in blacklist: if b < self.bound: while w in black: w += 1 self.b2w[b] = w w += 1 defpick(self) -> int: x = randrange(self.bound) return self.b2w.get(x, x)
Given
two strings, find if first string is a subsequence of second:
isSubSequence(string1, string2, len(string1), len(string2))输出string1是否为string2的子序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution: deffindLUSlength(self, strs: List[str]) -> int: defisSubSequence(string1, string2, m, n): # Base Cases if m == 0: returnTrue if n == 0: returnFalse # If last characters of two strings are matching if string1[m-1] == string2[n-1]: return isSubSequence(string1, string2, m-1, n-1) # If last characters are not matching return isSubSequence(string1, string2, m, n-1) strs.sort(key=len, reverse=True) # 最长的特殊序列更可能在最长的序列产生, 排序后逐个判断 counter = Counter(strs) # 计数一下, 若最长序列只出现过一次, 那就是要找的特殊序列 temp = set() # 储存非特殊序列, 用来判断序列s是否是它们的子序列 for s in strs: # 遍历每个序列, 当其计数为1且非前面所有序列的子序列时, 返回其长度 if counter[s] == 1andall([not isSubSequence(s, t, len(s), len(t)) for t in temp]): returnlen(s) temp.add(s) return -1
💛324. 摆动排序
II
排序后列表操作调整 - Carlos
1 2 3 4 5 6 7 8 9 10
classSolution: # 从大到小排列后, 把后半部分的序列逐个插入前半部分即可 defwiggleSort(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ nums.sort(reverse=True) count = 0 for i inrange(n := len(nums) // 2): nums.insert(i + count, nums.pop(n + i)) count += 1
classCodec: # 不搞后端, 乱做一通 defencode(self, longUrl: str) -> str: """Encodes a URL to a shortened URL. """ return longUrl defdecode(self, shortUrl: str) -> str: """Decodes a shortened URL to its original URL. """ return shortUrl # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.decode(codec.encode(url))
TinyURL
的加密与解密 - 力扣官方题解
方法一:自增
方法二:哈希生成
方法三:随机生成
[Python/Java/TypeScript/Go]
模拟 - Benhao
高级方法, 指出用rsa库, 但平台没有, 转而使用了hashlib库.
💚1175.
质数排列
判断质数 - Carlos
1 2 3 4 5 6 7 8 9 10
classSolution: defnumPrimeArrangements(self, n: int) -> int: # [How to Check if a Number is Prime in Python] # (https://geekflare.com/prime-number-in-python/#geekflare-toc-o-n-algorithm-to-check-for-prime-number-in-python) defis_prime(n): for i inrange(2,int(math.sqrt(n))+1): if (n % i) == 0: returnFalse returnTrueif n > 1elseFalse temp = sum(is_prime(_) for _ inrange(1, n+1)) return (math.factorial(temp) * math.factorial(n - temp)) % (10 ** 9 + 7)