[LeetCode周賽複盤] 第 330 場周賽20230129
-
- 一、本周周賽總結
- 二、 [Easy] 6337. 統計桌面上的不同數字
-
- 1. 題目描述
- 2. 思路分析
- 3. 代碼實作
- 三、[Medium] 6338. 猴子碰撞的方法數
-
- 1. 題目描述
- 2. 思路分析
- 3. 代碼實作
- 四、[Hard] 6339. 将珠子放入背包中
-
- 1. 題目描述
- 2. 思路分析
- 3. 代碼實作
- 五、[Hard] 6340. 統計上升四元組
-
- 1. 題目描述
- 2. 思路分析
- 3. 代碼實作
- 六、參考連結
一、本周周賽總結
- T3又被腦筋急轉彎卡了，想了一小時Dp。
- T1 腦筋急轉彎+數學。
- T2 腦筋急轉彎+快速幂取模。
- T3 腦筋急轉彎+排序。
- T4 枚舉計算/DP。
[LeetCode周賽複盤] 第 330 場周賽20230129
二、 [Easy] 6337. 統計桌面上的不同數字
連結: 6337. 統計桌面上的不同數字
1. 題目描述
2. 思路分析
- 每次操作，每個數的i-1都會新增出來。但1不會。
- 也就是最終2~n之間的數都會出來。
- 題目限制n<=100,但 進行1e9次操作，是以必能操作到頭。
- 也就是除了n=1的情況，其它都會出現2~n，即n-1個數。
3. 代碼實作
class Solution:
def distinctIntegers(self, n: int) -> int:
if n == 1:
return 1
return n-1
三、[Medium] 6338. 猴子碰撞的方法數
連結: 6338. 猴子碰撞的方法數
1. 題目描述
2. 思路分析
題目有歧義。實際上路徑也不能相撞，否則偶數的話可以相鄰猴子兩兩交換位置。
- 考慮不撞的方法，隻有兩種，就是一起順時針或逆時針走。
- 所有走法一共有2**n。需要用快速幂取模模闆。
- 這裡是py就逃課了。
- 一開始太相信py的大數，直接2**n-2，再取模，确實TLE，pow就沒問題。
3. 代碼實作
MOD = 10**9+7
class Solution:
def monkeyMove(self, n: int) -> int:
return (pow(2,n,MOD) - 2) % MOD
四、[Hard] 6339. 将珠子放入背包中
連結: 6339. 将珠子放入背包中
1. 題目描述
2. 思路分析
這題看似能DP，于是優化了一個小時都沒做出來。
轉化下思路就過了。
- 在最大最小值裡，首尾兩個數必會出現1次，是以無視。
- 那麼剩下的從哪取呢，想想有k-1根棍子分割這n個柱子。
- 柱子兩邊的數就是這根棍子的貢獻。那麼排序所有可能的貢獻，最大的k-1個和最小的k-1個就是答案。
3. 代碼實作
class Solution:
def putMarbles(self, w: List[int], k: int) -> int:
if k == 1 or k == len(w):
return 0
a = []
for x,y in pairwise(w):
a.append(x+y)
a.sort()
return sum(a[-k+1:]) - sum(a[:k-1])
五、[Hard] 6340. 統計上升四元組
連結: 6340. 統計上升四元組
1. 題目描述
2. 思路分析
注意題目要求裡k和j的相對位置，要求a1<a3<a2。
- 兩層循環枚舉j和l。即第二個數和第四個數。
- 在j和l之間的數k，如果小于nums[j]，則可以去j前邊找有多少個i滿足nums[i]小于num[k]，那就是幾個ik對；如果大于，則可以加上所有k的貢獻（即有多少ik對）。
- 是以用一個有序集合pre跟着j走，記錄j之前所有數，便于二分。
- 外層循環枚舉j，内層循環可以看成兩種：
- j右側的數大于nums[j]的是l，小于的是k。
- 即同時枚舉k和l。
- 這裡用的nnlgn的做法，後續補充一個n*n的dp。
- 補充n方做法。
- 枚舉j和k，這樣當nums[j]>nums[k]時，k後邊能選大于nums[j]的數，j前邊能選小于nums[k]的數。
- 如果能計數，則乘起來即可。
- 可以用n方的時間計算這兩個二維數組:
- great[i][v]代表i右邊大于v的數有多少個。
- less[i][v]代表i左邊小于v的數有多少個。
- 具體計算方法有點類似子序列自動機，從前一個狀态整體遷移過來，然後再計算本身的差異。
- 注：我後來試了樹狀數組，發現nnlgn的樹狀數組做法和n方的dp時間表現沒什麼差異：py的空間大了确實費性能。
- 補充一個方法三，空間O(n)，時間O(n2)，注釋寫的很詳細。表現良好
1276ms
3. 代碼實作
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
from sortedcontainers import SortedList
pre = SortedList()
for j in range(n):
mid = 0
for l in range(j+1,n):
if nums[l] < nums[j]:
mid += pre.bisect_left(nums[l])
else:
ans += mid
pre.add(nums[j])
return ans
n方dp
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
great = [[]] * n
great[-1] = [0]*(n+1)
for k in range(n-2,-1,-1):
great[k] = great[k+1][:]
for v in range(1,nums[k+1]):
great[k][v] += 1
ans = 0
less = [0]*(n+1)
for j in range(1,n-1):
for v in range(nums[j-1],n+1):
less[v] += 1
for k in range(j+1,n-1):
if nums[j] > nums[k]:
ans += less[nums[k]] * great[k][nums[j]]
return ans
方法三
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
cnt = [0] * n # cnt[j]表示以j為高點的，132形狀的三元組數量
for l in range(n):
small = 0 # j前邊小于nums[l]的數量
for j in range(l):
if nums[j] < nums[l]: # 如果高點小，就是滿足
ans += cnt[j]
small += 1 # 且記一個小的數
else:
cnt[j] += small # 否則可以貢獻small個三元組
return ans