一、本周周賽總結(jié)
- T1 模擬。
- T2 數(shù)學(xué)貪心。
- T3 dp。
- T4 分組+滑窗。
![[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820,力扣周賽復(fù)盤,leetcode,算法,職場(chǎng)和發(fā)展](https://imgs.yssmx.com/Uploads/2023/08/671399-1.png)
2828. 判別首字母縮略詞
2828. 判別首字母縮略詞
1. 題目描述
![[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820,力扣周賽復(fù)盤,leetcode,算法,職場(chǎng)和發(fā)展](https://imgs.yssmx.com/Uploads/2023/08/671399-2.png)
2. 思路分析
按題意模擬即可。
3. 代碼實(shí)現(xiàn)
class Solution:
def isAcronym(self, words: List[str], s: str) -> bool:
return s == ''.join(w[0] for w in words)
2829. k-avoiding 數(shù)組的最小總和
2829. k-avoiding 數(shù)組的最小總和
1. 題目描述
![[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820,力扣周賽復(fù)盤,leetcode,算法,職場(chǎng)和發(fā)展](https://imgs.yssmx.com/Uploads/2023/08/671399-3.png)
2. 思路分析
貪心
- 1~k-1中，選了1就不能選k-1;選了2就不能選k-2…
- 因此可以選1~k//2
- 剩余的從k開(kāi)始向上選。
- 可以模擬，也可以等差數(shù)列求和公式。
3. 代碼實(shí)現(xiàn)
class Solution:
def minimumSum(self, n: int, k: int) -> int:
ans = 0
p = min(n,k//2)
ans += (1+p)*p//2
ans += (k+k+n-p-1)*(n-p)//2
return ans
2830. 銷售利潤(rùn)最大化
2830. 銷售利潤(rùn)最大化
1. 題目描述
![[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820,力扣周賽復(fù)盤,leetcode,算法,職場(chǎng)和發(fā)展](https://imgs.yssmx.com/Uploads/2023/08/671399-4.png)
2. 思路分析
看到值域范圍，考慮用值域當(dāng)下標(biāo)dp。
令f[i]表示從0~i的房屋的銷售最大值。
- 枚舉offers[i]=a,b,c, 只要知道f[a-1]則可以轉(zhuǎn)移到f[b]，f[b]=f[a-1]+b。
- 如何知道f[a-1]呢，顯然它是一個(gè)前綴最大值，那么其實(shí)可以用線段樹(shù)等區(qū)間最大值的數(shù)據(jù)結(jié)構(gòu)。
- 這題還可以遞推，用p記錄當(dāng)前a之前的最大值，那么可以把offers按左端點(diǎn)排序，記一下即可，然后雙指針遞推。
3. 代碼實(shí)現(xiàn)
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
f = [0]*n
j = p = 0
offers.sort()
for a,b,c in offers:
while j < a:
p = max(p,f[j])
j += 1
f[b] = max(f[b],p+c)
return max(f[j:])
2831. 找出最長(zhǎng)等值子數(shù)組
2831. 找出最長(zhǎng)等值子數(shù)組
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-671399.html
1. 題目描述
![[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820,力扣周賽復(fù)盤,leetcode,算法,職場(chǎng)和發(fā)展](https://imgs.yssmx.com/Uploads/2023/08/671399-5.png)
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-671399.html
2. 思路分析
- 由于只能刪除k個(gè)數(shù)，保留的數(shù)不能變，那么按值分組，記錄下標(biāo)。
- 對(duì)每個(gè)組，看刪除k個(gè)的窗口內(nèi)，最多有幾個(gè)下標(biāo)。
- 那么變長(zhǎng)滑窗思路就出現(xiàn)了。
- 枚舉每個(gè)位置為窗口右邊界，如果窗口內(nèi)需要?jiǎng)h除的數(shù)字超過(guò)k個(gè)，那么縮左窗。
3. 代碼實(shí)現(xiàn)
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
n = len(nums)
g = [[] for _ in range(n+1)]
for i,v in enumerate(nums):
g[v].append(i)
ans = 1
for a in g:
q = deque()
for v in a:
q.append(v)
while q[-1]-q[0]+1 - len(q) > k:
q.popleft()
ans = max(ans,len(q))
return ans
參考鏈接
到了這里，關(guān)于[LeetCode周賽復(fù)盤] 第 359 場(chǎng)周賽20230820的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
