怎么做公司销售网站,wordpress添加幻灯片,世界军事新闻最新消息,建设一个网站可以采用那几方案LeetCode笔记#xff1a;Weekly Contest 361 0. 吐槽1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接#xff1a;https://leetcode.com/contest/weekly-contest-361
0. …LeetCode笔记Weekly Contest 361 0. 吐槽1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接https://leetcode.com/contest/weekly-contest-361
0. 吐槽
双周赛的4道题水的不行然后下午就翻车了4道题把我折磨的……
主要做第三题的时候状态太差了一开始遇到超时就懵了不过后来写一下公式之后感觉还是很直接的感觉纯粹就是昨晚没休息好导致大脑还是懵逼的……
第四题倒是多少有点成就感思路其实很直接不过也是遇到了超时问题优化之后能把第四题搞定也是挺爽的。
1. 题目一
给出题目一的试题链接如下
2843. Count Symmetric Integers
1. 解题思路
这一题我的思路很暴力就是在范围内对每个数字进行一下判断就是了……
2. 代码实现
给出python代码实现如下
class Solution:def countSymmetricIntegers(self, low: int, high: int) - int:def is_symmetric(num):s str(num)n len(s)if n % 2 1:return Falses1 sum(int(x) for x in s[:n//2])s2 sum(int(x) for x in s[n//2:])return s1 s2res [x for x in range(low, high1) if is_symmetric(x)]return len(res)提交代码评测得到耗时922ms占用内存16.2MB。
2. 题目二
给出题目二的试题链接如下
2844. Minimum Operations to Make a Special Number
1. 解题思路
这一题获得被25整除的数那么就一定只有5种情况
后两位是00后两位是25后两位是50后两位是75这个数为0
我们逐次考察一下这五种情况能否实现以及需要删除的数的个数即可。
2. 代码实现
给出python代码实现如下
class Solution:def minimumOperations(self, num: str) - int:n len(num)def find_pattern(pattern):idx len(pattern)-1cnt 0for ch in num[::-1]:if ch pattern[idx]:idx - 1else:cnt 1if idx 0:breakreturn n if idx 0 else cntres [find_pattern(00),find_pattern(25),find_pattern(50),find_pattern(75),n - Counter(num)[0]]return min(res)提交代码评测得到耗时40ms占用内存16.3MB。
3. 题目三
给出题目三的试题链接如下
2845. Count of Interesting Subarrays
1. 解题思路
这一题思路上其实挺直接的就是根据给定的modulo和k找到所有关于modulo余数为k的数字所在的位置假设有 n n n个然后就可以将原始的数组分为 n 1 n1 n1段。
我们只需要分别考察起点在这 n 1 n1 n1段当中的情况时考察终点的位置分布即可显然可以得到如下公式 s ∑ i 0 n ∑ j i k n n i × n j s \sum\limits_{i0}^{n}\sum\limits_{jik}^{n}n_i \times n_j si0∑njik∑nni×nj
唯一需要注意的是如果 k 0 k0 k0问题需要特殊考虑一下因为 k 0 k0 k0实际就是 k m o d u l o kmodulo kmodulo的情况此时两个起点和终点需要取在同一个interval当中因此需要特殊考察一下。
Anyway基本也就这样了不过实际在做的时候我脑残了一下直接上了个二重循环然后就炸了……后来想了半天浪费了巨多时间也没想明白直到我把上面那个式子写了一下才发现直接再加一个累积数组也就搞定了……
唉严重失误……
2. 代码实现
给出python代码实现如下
class Solution:def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) - int:s [1 if x % modulo k else 0 for x in nums]indices [idx for idx, x in enumerate(s) if x 1]n, m len(s), len(indices)if indices []:return n*(n1) // 2 if k 0 else 0intervals [indices[0]1] [indices[i1] - indices[i] for i in range(m-1)] [n - indices[m-1]]n len(intervals)res 0 if k ! 0 else sum(x*(x-1)//2 for x in intervals)k modulo if k 0 else ks [x for x in intervals]for i in range(n-1, -1, -1):if imodulo n:s[i] s[imodulo]for i in range(n-k):res intervals[i] * s[ik] return res提交代码评测得到耗时821ms占用内存31.5MB。
4. 题目四
给出题目四的试题链接如下
2846. Minimum Edge Weight Equilibrium Queries in a Tree
1. 解题思路
这一题思路上其实也很直接就是对每一个query找到两点间的路径然后所需要做的op的次数就是路径长度减去其中相同权重的边长出现的最大次数。
于是问题就变成了如何快速地找到任意两个点之间的路径以及其中的各个权重的边长分布。
我们随机选择一个点作为根节点显然用一个dfs我们就能够简单地找到从根节点到任意节点之间的路径。
而要找到任意两点之间的路径我们只需要找到这两个节点最近的一个公共父节点然后把下面分叉的两个子路径拼接在一起就是这两个点之间的连通路径了。
因此这里的问题事实上就变成了如何高效地找到这个公共父节点我一开始直接用了一个遍历然后就凉凉了……这里也是卡的我时间最久的地方不过后来突然想到可以直接用一个二分搜索就行了因为是找到最后一个节点是指后续两条路径的走向不同。
由此我们就不会再出现超时问题了……
然后剩下的问题就在于如何统计这个路径当中的所有权重了当然一种直接的思路就是遍历一下不过估摸着一定会超时……
考虑到题目中限制了权重仅可能为1到26因此事实上我们可以用一个26元的数组来表征从根节点到任意节点地路径当中各个权重的边出现的次数。此时假设两节点 u , v u,v u,v的最近的一个公共父节点为 p p p那么 u , v u,v u,v这段路径当中所有权重的边长出现的次数事实上就是 u − p v − p u-pv-p u−pv−p了。综上我们也就可以快速地得到每一个query的答案了。
2. 代码实现
给出python代码实现如下
class Solution:def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) - List[int]:if n 1:return [0 for _ in queries]graph defaultdict(list)weights defaultdict(int)for u, v, w in edges:graph[u].append(v)graph[v].append(u)weights[(u, v)] wweights[(v, u)] w_max 0for i in range(n):if len(graph[i]) _max:u0 iparent {u0: -1}nodes {u0: tuple([0 for _ in range(26)])}paths {u0: [u0]}def dfs(u):nonlocal parent, nodes, pathsval list(nodes[u])for v in graph[u]:if v parent[u]:continueparent[v] uw weights[(u, v)]val[w-1] 1nodes[v] tuple(val)val[w-1] - 1paths[v] paths[u] [v]dfs(v)returndfs(u0)def get_latest_ancestor(u, v):n min(len(paths[u]), len(paths[v]))if paths[u][n-1] paths[v][n-1]:return paths[u][n-1]i, j 0, n-1while j-i 1:m (ij) // 2if paths[u][m] paths[v][m]:i melse:j mreturn paths[u][i]def query(u, v):p get_latest_ancestor(u, v)path [xy-2*z for x,y,z in zip(nodes[u], nodes[v], nodes[p])]return sum(path) - max(path)return [query(u, v) for u, v in queries]提交代码评测得到耗时5087ms占用内存432.4MB。
