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

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

0. 吐槽

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

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

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

1. 題目一

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

• 2843. Count Symmetric Integers

1. 解題思路

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

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(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)

提交代碼評(píng)測(cè)得到：耗時(shí)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. 這個(gè)數(shù)為0

我們逐次考察一下這五種情況能否實(shí)現(xiàn)以及需要?jiǎng)h除的數(shù)的個(gè)數(shù)即可。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(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)

提交代碼評(píng)測(cè)得到：耗時(shí)40ms，占用內(nèi)存16.3MB。

3. 題目三

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

• 2845. Count of Interesting Subarrays

1. 解題思路

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

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

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

唯一需要注意的是，如果$k=0$，問(wèn)題需要特殊考慮一下，因?yàn)?span id="vxwlu0yf4" class="katex--inline">$k=0$實(shí)際就是$k=modulo$的情況，此時(shí)兩個(gè)起點(diǎn)和終點(diǎn)需要取在同一個(gè)interval當(dāng)中，因此需要特殊考察一下。

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

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

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(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

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

4. 題目四

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

• 2846. Minimum Edge Weight Equilibrium Queries in a Tree

1. 解題思路

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

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

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

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

因此，這里的問(wèn)題事實(shí)上就變成了如何高效地找到這個(gè)公共父節(jié)點(diǎn)，我一開(kāi)始直接用了一個(gè)遍歷，然后就涼涼了……這里也是卡的我時(shí)間最久的地方，不過(guò)后來(lái)突然想到，可以直接用一個(gè)二分搜索就行了，因?yàn)槭钦业阶詈笠粋€(gè)節(jié)點(diǎn)，是指后續(xù)兩條路徑的走向不同。

由此，我們就不會(huì)再出現(xiàn)超時(shí)問(wèn)題了……

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

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

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(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]

提交代碼評(píng)測(cè)得到：耗時(shí)5087ms，占用內(nèi)存432.4MB。