• LeetCode筆記：Weekly Contest 361
  • 0. 吐槽
  • 1. 題目一
    • 1. 解題思路
    • 2. 代碼實現(xiàn)
  • 2. 題目二
    • 1. 解題思路
    • 2. 代碼實現(xiàn)
  • 3. 題目三
    • 1. 解題思路
    • 2. 代碼實現(xiàn)
  • 4. 題目四
    • 1. 解題思路
    • 2. 代碼實現(xiàn)

• 比賽鏈接：https://leetcode.com/contest/weekly-contest-361

0. 吐槽

雙周賽的4道題水的不行，然后下午就翻車了，4道題把我折磨的……

主要做第三題的時候狀態(tài)太差了，一開始遇到超時就懵了，不過后來寫一下公式之后感覺還是很直接的，感覺純粹就是昨晚沒休息好導(dǎo)致大腦還是懵逼的……

第四題倒是多少有點(diǎn)成就感，思路其實很直接，不過也是遇到了超時問題，優(yōu)化之后能把第四題搞定也是挺爽的。

1. 題目一

給出題目一的試題鏈接如下：

• 2843. Count Symmetric Integers

1. 解題思路

這一題我的思路很暴力，就是在范圍內(nèi)對每個數(shù)字進(jìn)行一下判斷就是了……

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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, high+1) if is_symmetric(x)]return len(res)

提交代碼評測得到：耗時922ms，占用內(nèi)存16.2MB。

2. 題目二

給出題目二的試題鏈接如下：

• 2844. Minimum Operations to Make a Special Number

1. 解題思路

這一題獲得被25整除的數(shù)，那么就一定只有5種情況：

1. 后兩位是00
2. 后兩位是25
3. 后兩位是50
4. 后兩位是75
5. 這個數(shù)為0

我們逐次考察一下這五種情況能否實現(xiàn)以及需要刪除的數(shù)的個數(shù)即可。

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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，占用內(nèi)存16.3MB。

3. 題目三

給出題目三的試題鏈接如下：

• 2845. Count of Interesting Subarrays

1. 解題思路

這一題思路上其實挺直接的，就是根據(jù)給定的modulo和k，找到所有關(guān)于modulo余數(shù)為k的數(shù)字所在的位置（假設(shè)有$n$個），然后就可以將原始的數(shù)組分為$n+1$段。

我們只需要分別考察起點(diǎn)在這$n+1$段當(dāng)中的情況時，考察終點(diǎn)的位置分布即可，顯然可以得到如下公式：

$$s=\sum _{i=0}^n\sum _{j=i+k}^n{n}_i\times n_j$$

唯一需要注意的是，如果$k=0$，問題需要特殊考慮一下，因為$k=0$實際就是$k=modulo$的情況，此時兩個起點(diǎn)和終點(diǎn)需要取在同一個interval當(dāng)中，因此需要特殊考察一下。

Anyway，基本也就這樣了，不過實際在做的時候我腦殘了一下，直接上了個二重循環(huán)，然后就炸了……后來想了半天浪費(fèi)了巨多時間也沒想明白，直到我把上面那個式子寫了一下，才發(fā)現(xiàn)直接再加一個累積數(shù)組也就搞定了……

唉，嚴(yán)重失誤……

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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*(n+1) // 2 if k == 0 else 0intervals = [indices[0]+1] + [indices[i+1] - 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 i+modulo < n:s[i] += s[i+modulo]for i in range(n-k):res += intervals[i] * s[i+k]        return res

提交代碼評測得到：耗時821ms，占用內(nèi)存31.5MB。

4. 題目四

給出題目四的試題鏈接如下：

• 2846. Minimum Edge Weight Equilibrium Queries in a Tree

1. 解題思路

這一題思路上其實也很直接，就是對每一個query，找到兩點(diǎn)間的路徑，然后所需要做的op的次數(shù)就是路徑長度減去其中相同權(quán)重的邊長出現(xiàn)的最大次數(shù)。

于是，問題就變成了如何快速地找到任意兩個點(diǎn)之間的路徑，以及其中的各個權(quán)重的邊長分布。

我們隨機(jī)選擇一個點(diǎn)作為根節(jié)點(diǎn)，顯然，用一個dfs我們就能夠簡單地找到從根節(jié)點(diǎn)到任意節(jié)點(diǎn)之間的路徑。

而要找到任意兩點(diǎn)之間的路徑，我們只需要找到這兩個節(jié)點(diǎn)最近的一個公共父節(jié)點(diǎn)，然后把下面分叉的兩個子路徑拼接在一起就是這兩個點(diǎn)之間的連通路徑了。

因此，這里的問題事實上就變成了如何高效地找到這個公共父節(jié)點(diǎn)，我一開始直接用了一個遍歷，然后就涼涼了……這里也是卡的我時間最久的地方，不過后來突然想到，可以直接用一個二分搜索就行了，因為是找到最后一個節(jié)點(diǎn)，是指后續(xù)兩條路徑的走向不同。

由此，我們就不會再出現(xiàn)超時問題了……

然后，剩下的問題就在于如何統(tǒng)計這個路徑當(dāng)中的所有權(quán)重了，當(dāng)然，一種直接的思路就是遍歷一下，不過估摸著一定會超時……

考慮到題目中限制了權(quán)重僅可能為1到26，因此事實上我們可以用一個26元的數(shù)組來表征從根節(jié)點(diǎn)到任意節(jié)點(diǎn)地路徑當(dāng)中各個權(quán)重的邊出現(xiàn)的次數(shù)。此時，假設(shè)兩節(jié)點(diǎn)$u,v$的最近的一個公共父節(jié)點(diǎn)為$p$，那么$u,v$這段路徑當(dāng)中所有權(quán)重的邊長出現(xiàn)的次數(shù)事實上就是$u?p+v?p$了。綜上，我們也就可以快速地得到每一個query的答案了。

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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 = (i+j) // 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 = [x+y-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，占用內(nèi)存432.4MB。