- LeetCode筆記：Weekly Contest 206
- 0. 賽后總結
- 1. 題目一
- 1. 解題思路
- 2. 代碼實作
- 2. 題目二
- 1. 解題思路
- 2. 代碼實作
- 3. 題目三
- 1. 解題思路
- 2. 代碼實作
- 4. 題目四
- 1. 解題思路
- 2. 代碼實作
0. 賽后總結
最近不知是換到中文leetcode平臺之后水土不服還是怎么樣，感覺真的是到了瓶頸期了，最近幾次打比賽真的是一次不如一次，做起來例外不順手，
看了一下頭部幾位大佬們的做題耗時，基本都還是在10分鐘左右，因此基本不存在這幾次的題目特別難的說法，那么就是我這邊自身發揮的問題了，
感覺真的是需要休息一陣子好好調整一下了，等到國慶放假的時候好好休息一下吧，但愿之后的狀態能有回暖吧，，，
{{{(>_<)}}}
1. 題目一
給出題目一的試題鏈接如下：
- 5511. 二進制矩陣中的特殊位置
1. 解題思路
這一題的關鍵點就是統計只出現一行和一列中的1中的元素的個數，
因此，只要統計每一行中只有一個1的行，然后再對對應元素的列看一下是否該列中也恰好只出現了一個1，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
ans = 0
n = len(mat)
m = len(mat[0])
for i in range(n):
eff = []
for j in range(m):
if mat[i][j] == 1:
eff.append((i, j))
if len(eff) == 1:
j = eff[0][1]
count = 0
for k in range(n):
if mat[k][j] == 1:
count += 1
if count == 1:
ans += 1
return ans
提交代碼之后評測得到：耗時168ms，占用記憶體14.1MB，姑且屬于當前第一梯隊，
2. 題目二
給出題目二的試題鏈接如下：
- 5512. 統計不開心的朋友
1. 解題思路
這一題感覺是這次比賽中最蠢的一題，純粹就是看題目的問題，問題描述極其繞嘴，比賽的時候看題目看了半天，還理解錯了，然后就直接呵呵了，
等到最后終于把題目看明白之后，就直接暴力求解解決了，，，
本來以為是我自己的問題，然后現在去看了一下題目的評價，發現25個點贊，然后98個差評，呵呵，，，
算了，讀者注意一下不開心的定義就行，是要同時滿足兩個條件，然后按照他說的規則直接暴力遍歷一遍就行了，沒啥技術含量，甚至說千萬不要去想什么更精妙的解法，這題目純粹就是靠怎么讀題目而已！！！
2. 代碼實作
直接給出代碼實作如下：
class Solution:
def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
n = len(pairs)
ans = 0
for i in range(n):
x, y = pairs[i]
xh = True
yh = True
for j in range(n):
if i == j:
continue
u, v = pairs[j]
if preferences[x].index(u) < preferences[x].index(y) and preferences[u].index(x) < preferences[u].index(v):
xh = False
break
if preferences[x].index(v) < preferences[x].index(y) and preferences[v].index(x) < preferences[v].index(u):
xh = False
break
for j in range(n):
if i == j:
continue
u, v = pairs[j]
if preferences[y].index(u) < preferences[y].index(x) and preferences[u].index(y) < preferences[u].index(v):
yh = False
break
if preferences[y].index(v) < preferences[y].index(x) and preferences[v].index(y) < preferences[v].index(u):
yh = False
break
if not xh:
ans += 1
if not yh:
ans += 1
return ans
提交代碼之后得到：耗時472ms，占用記憶體27.1MB，
很挫的代碼實作，但是懶得去看別人的實作了，反正沒有什么量級上的差異，如果有興趣的讀者可以自行去看一下，這里就不多做介紹了，
3. 題目三
給出題目三的試題鏈接如下：
- 5513. 連接所有點的最小費用
1. 解題思路
這一題的本質就是求最小聯通圖，
普遍的演算法就是Dijkstra演算法，一般的資料結構課上都有，不過我有點忘了，就用了他的等價演算法，Dijkstra演算法是每次取連通區域外的最小邊添加到圖中，直到整張圖都連通起來，
這邊的演算法名字我給忘了，不過是每次取最短邊使得原本不連通的兩個區域能夠連通起來，直到整張圖都連通起來，
2. 代碼實作
給出代碼實作如下：
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
distances = [[abs(x[0] - y[0]) + abs(x[1] - y[1]) for y in points] for x in points]
distances = sorted((distances[x][y], x, y) for x in range(n-1) for y in range(x+1, n))
ans = 0
have_connected = [set([i]) for i in range(n)]
for d, x, y in distances:
if any(x in s and y in s for s in have_connected):
continue
s1 = -1
s2 = -1
for j, s in enumerate(have_connected):
if x in s:
s1 = j
if y in s:
s2 = j
if s1 > s2:
s1, s2 = s2, s1
have_connected.append(have_connected[s1] | have_connected[s2])
have_connected.pop(s2)
have_connected.pop(s1)
ans += d
if len(have_connected) == 1:
break
return ans
提交代碼評測得到：耗時2192ms，占用記憶體105.6MB，
當前最優演算法耗時僅為1060ms，看了一下，使用的是Dijkstra演算法，如果有感興趣的讀者可以自行實作一下，這里我就先放棄了，，，
4. 題目四
給出題目四的試題鏈接如下：
- 5514. 檢查字串是否可以通過排序子字串得到另一個字串
1. 解題思路
這一題比賽的時候是完全沒能做出來，因為一開始的思路就是錯的，后來也是比賽結束之后看了一下頭部幾位大神們的做法，然后終于有了一些思路，后來算是終于實作出來了，
這一題的關鍵在于每一次的操作都是對于子序列的排序操作，因此，顯然必有：原始序列中一個元素后方比他小的元素只會減少不可能會增加，
因此，要判斷s序列能否通過一系列操作轉換為t序列，我們只需要考察：
- 兩者所擁有的字符集合是否完全一致；
- 對于s中的每一個字符與t中對應的字符，s中字符后方每一個比它小的字符的數目均不少于t中對應的字符數目，
2. 代碼實作
我們將其整理為代碼實作即有：
class Solution:
def isTransformable(self, s: str, t: str) -> bool:
n = len(t)
scounter = [{c: 0 for c in "0123456789"} for _ in range(n+1)]
tcounter = [{c: 0 for c in "0123456789"} for _ in range(n+1)]
for i in range(n-1, -1, -1):
for c in "0123456789":
scounter[i][c] = scounter[i+1][c]
tcounter[i][c] = tcounter[i+1][c]
scounter[i][s[i]] += 1
tcounter[i][t[i]] += 1
if not all(scounter[0][c] == tcounter[0][c] for c in "0123456789"):
return False
scounter_v2 = {c: [] for c in "0123456789"}
for i in range(n):
scounter_v2[s[i]].append(i+1)
tcounter_v2 = {c: [] for c in "0123456789"}
for i in range(n):
tcounter_v2[t[i]].append(i+1)
for c in "123456789":
for idx1, idx2 in zip(scounter_v2[c], tcounter_v2[c]):
if not all(scounter[idx1][str(k)] >= tcounter[idx2][str(k)] for k in range(int(c))):
return False
return True
上述代碼提交可以通過，評測得到：耗時3332ms，占用記憶體104.2MB，
而當前最優代碼實作耗時僅為332ms，比我們的演算法高了一整個量級，因此，后續還有很大的優化空間，
需要好好看一下對方的代碼實作，
感興趣的讀者可以自己先看一下，這里我就先放著了，過兩天有空了再來研究一下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47914.html
標籤：其他
下一篇：中興MKT崗位面試程序記錄