在线观看免费AV网站,色老汉在线视频,青青草久久久,无码人妻一区二区三区,蜜芽尤物在线,狠狠人妻久久久久久综合99浪潮,欧美三级专区,色婷婷av

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?強(qiáng)密碼檢驗(yàn)器，我們先來看題面：

https://leetcode-cn.com/problems/strong-password-checker/

一個強(qiáng)密碼應(yīng)滿足以下所有條件：

由至少6個，至多20個字符組成。

至少包含一個小寫字母，一個大寫字母，和一個數(shù)字。

同一字符不能連續(xù)出現(xiàn)三次 (比如 "...aaa..." 是不允許的, 但是 "...aa...a..." 是可以的)。

編寫函數(shù) strongPasswordChecker(s)，s 代表輸入字符串，如果 s 已經(jīng)符合強(qiáng)密碼條件，則返回0；否則返回要將 s 修改為滿足強(qiáng)密碼條件的字符串所需要進(jìn)行修改的最小步數(shù)。

插入、刪除、替換任一字符都算作一次修改。

解題

http://www.manongjc.com/detail/20-zosdnuezjvotflt.html

這是一道數(shù)學(xué)題。

連續(xù)字符串刪除和插入的方式代價高，盡量使用替換。如何理解呢？對于任意>=3的連續(xù)串長度為s，所需要的替換次數(shù)為s//3，

而使用插入(s-1)/2次操作和刪除s-2次。插入和刪除相結(jié)合還是比替換要慢。

對于長度>=3的連續(xù)串，每個修改次數(shù)為s//3, s為連續(xù)串的長度，記錄總的連續(xù)串修改次數(shù)為n_modify

記錄確實(shí)字符個數(shù)為n_lack

length<6，返回max(6-len(s), n_lack)

length<=20，返回max(n_modify, n_lack)

length>20，此時一定要刪除字符的長度為n_delete = len(s) - 20

我們知道連續(xù)串可以通過刪除字符來減少n_modify。我們肯定優(yōu)先刪除連續(xù)串。對于不同長度的連續(xù)串，有這樣的特性。

3n，刪除一個字符，就可以減少一次替換

3n+1, 刪除兩個字符，減少一次替換

3n+2, 刪除三個字符，減少一個替換

要使得最終結(jié)果最小，我們優(yōu)先考慮3n，多出來的繼續(xù)考慮3n+1，和3n+2。最終剩下來的都是3n+2，即如果還有剩余就全部用來減少3n+2的替換次數(shù) 。

class?Solution:
????def?strongPasswordChecker(self, s: str)?-> int:
????????cnt = [0]*3?# 3n, 3n+1, 3n+2

????????a , A, num = 1, 1, 1
????????i = 0
????????n_modify = 0
????????while?i < len(s):
????????????c = s[i]
????????????length = 1
????????????if?s[i] >= '0'?and?s[i] <= '9':
????????????????num = 0
????????????elif?s[i] >= 'a'?and?s[i] <= 'z':
????????????????a = 0
????????????elif?s[i] >= 'A'?and?s[i] <= 'Z':
????????????????A = 0
????????????i += 1????????????
????????????while?i < len(s) and?s[i] == c:
????????????????i += 1
????????????????length += 1?
????????????if?length >= 3:
????????????????n_modify += length//3
????????????????cnt[length%3] += 1
????????????????
????????n_lack = a + A + num
????????if?len(s) < 6:
????????????return?max(n_lack, 6-len(s))
????????if?len(s) <= 20:
????????????return?max(n_lack, n_modify)

????????n_delete = len(s) - 20

????????if?n_delete <= cnt[0]:
????????????return?max(n_modify - n_delete, n_lack) + n_delete

????????if?(n_delete - cnt[0]) <= 2*cnt[1]:
????????????return?max(n_modify - cnt[0]- (n_delete-cnt[0])//2, n_lack) + n_delete

????????if?(n_delete - cnt[0] - 2*cnt[1]) <= 3?* cnt[2]:
????????????return?max(n_modify - cnt[0] - cnt[1]- (n_delete - cnt[0] - 2*cnt[1])//3, n_lack) + n_delete;
????????return?max(n_modify - cnt[0] - cnt[1] - cnt[2] - (n_delete - cnt[0] - 2*cnt[1] 
???????????????????-3*cnt[2])//3, n_lack) + n_delete;