一起養成寫作習慣！這是我參與「掘金日新計劃 · 4 月更文挑戰」的第1天，點選檢視活動詳情

題目描述

420. 強密碼檢驗器

如果一個密碼滿足下述所有條件，則認為這個密碼是強密碼：由至少 6 個，至多 20 個字元組成。至少包含一個小寫字母，一個大寫字母，和一個數字。同一字元不能連續出現三次 (比如 "...aaa..." 是不允許的, 但是 "...aa...a..." 如果滿足其他條件也可以算是強密碼)。給你一個字串 password ，返回將 password 修改到滿足強密碼條件需要的最少修改步數。如果 password 已經是強密碼，則返回 0 。

在一步修改操作中，你可以：

插入一個字元到 password ，從 password 中刪除一個字元，或用另一個字元來替換 password 中的某個字元。

| 案例 | 輸入 | 輸出 | | -- | -------- | -- | | 1 | a | 5 | | 2 | aA1 | 3 | | 3 | 1337C0d3 | 0 |

思路分析

這道題難就難在需要你給出優化步驟。不僅僅需要判定他是否符合強密碼要求，還需要針對非強密碼給出優化方案。
優化的方式題目中也給出說明了，我們一次操作僅可以新增，刪除，修改一個字元。在針對密碼長度我們會區分三種情況

那麼我們下面也就是針對這三種情況進行鍼對性的操作

長度過小

題目中要求我們優化的方案僅有三種----新增，修改，刪除1個字元一次。

當密碼長度小於6的時候，我們如果想要優化成強密碼格式。強密碼要求之一是長度在6~20之內。那麼我們刪除的操作就沒必要了。
那麼我們再來看如果出現連續字元出現重複的情況，我們改怎麼做。因為我們現在的密碼長度是小於6的，所以最多出現連續5個字元相同，

相同字元5個

針對連續字元在5個情況中我們可以更新其中一個使其斷開連續3個字元的效果。但是強密碼還需要至少包含3中型別字元。在連續5個相同字元出現的情況下我們進行替換後元素種類才兩種，所以我們還需要執行一次新增才可以滿足強密碼的要求

除了更新之後新增的方案以外，我們還可以直接在連續字元中已新增的方式來同事破解連續並且保證長度。

兩種方案優化的步驟都是2

相同字元4個

因為當前大條件是密碼長度不超過6 ，相同字元4個。那麼密碼長度最大是5，也就是密碼種類最多是2 。那麼此時針對相同字元是該替換還是新增就很明顯了。
新增不僅可以破解連續的問題還可以解決種類新增的問題和長度的問題，而更新無法解決長度的問題，所以這裡我們需要採用新增方式

所以我們選擇在連續位置的中位數位置進行新增一個元素就完成了升級操作了。

相同字元3個

相同密碼3個和4個是一樣的。我們要做的是在中位數位置左右各新增就完成了。

公式

假設我們密碼長度為n . 密碼中出現字元的種類為t

為什麼上面連續字元2,1,0個這三種情況就不在分析了。因為連續字元低於3我們就不需要關心了，直接新增就可以了。也就是說連續字元沒有超過3時，我們優化的步驟6-n , 或者3-t 。這個就取決兩者誰大了。 6-n是為了完成長度的滿足，3-t 是為了完成種類的滿足。
相同字元3時，6-n
相同字元4時，6-n
相同字元5時，6-n

長度適中

長度適中意思就是長度在6~20之內，那麼這個階段很明顯新增就不在適合我們的優化策略了，因為很有可能因為新增導致長度超出了。而且在破解連續字元的問題上我們是可以用更新或者刪除來破解的。很明顯在連續字元超過4的時候刪除也不適合。所以綜合來看在連續字元的問題上還是更新比較適合

不管連續多少個字元，我們只需要不出現連續三個字元出現就行。那麼我們就只需要將連續的字元3個分組。每個組裡我們替換掉1個就行了。假設我們連續字元分別為k1,k2,k3....kx
那麼我們需要更新的操作是k/3之和

$$ X = \frac{k_{1}}{3}+\frac{k_{2}}{3}+\frac{k_{3}}{3}+....+\frac{k_{x}}{3} $$

另外我們還需要記住保持三種類型，假設我們字元型別是t , 3-t就是我們需要的操作；也就是我們去X 和3-t的最大值

長度過大

因為長度過大，所以這裡新增很明顯就不合適了，那麼就是更新和刪除。第一反應就是肯定刪除合適。但是當我們刪除到一定長度後還會出現連續字元這個情況，所以更新就必不可少了。
那麼針對修復我們是先更新後刪除，還是先刪除後更新呢。

- 經過這麼一張圖，相信聰明的你應該也知道改選那種方式了吧。下面我們看下官網給出的解釋，我覺得分析的和清晰

AC

class Solution { public int strongPasswordChecker(String password) { int n = password.length(); int hasLower = 0, hasUpper = 0, hasDigit = 0; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (Character.isLowerCase(ch)) { hasLower = 1; } else if (Character.isUpperCase(ch)) { hasUpper = 1; } else if (Character.isDigit(ch)) { hasDigit = 1; } } int categories = hasLower + hasUpper + hasDigit; if (n < 6) { return Math.max(6 - n, 3 - categories); } else if (n <= 20) { int replace = 0; int cnt = 0; char cur = '#'; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (ch == cur) { ++cnt; } else { replace += cnt / 3; cnt = 1; cur = ch; } } replace += cnt / 3; return Math.max(replace, 3 - categories); } else { // 替換次數和刪除次數 int replace = 0, remove = n - 20; // k mod 3 = 1 的組數，即刪除 2 個字元可以減少 1 次替換操作 int rm2 = 0; int cnt = 0; char cur = '#'; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (ch == cur) { ++cnt; } else { if (remove > 0 && cnt >= 3) { if (cnt % 3 == 0) { // 如果是 k % 3 = 0 的組，那麼優先刪除 1 個字元，減少 1 次替換操作 --remove; --replace; } else if (cnt % 3 == 1) { // 如果是 k % 3 = 1 的組，那麼存下來備用 ++rm2; } // k % 3 = 2 的組無需顯式考慮 } replace += cnt / 3; cnt = 1; cur = ch; } } if (remove > 0 && cnt >= 3) { if (cnt % 3 == 0) { --remove; --replace; } else if (cnt % 3 == 1) { ++rm2; } } replace += cnt / 3; // 使用 k % 3 = 1 的組的數量，由剩餘的替換次數、組數和剩餘的刪除次數共同決定 int use2 = Math.min(Math.min(replace, rm2), remove / 2); replace -= use2; remove -= use2 * 2; // 由於每有一次替換次數就一定有 3 個連續相同的字元（k / 3 決定），因此這裡可以直接計算出使用 k % 3 = 2 的組的數量 int use3 = Math.min(replace, remove / 3); replace -= use3; remove -= use3 * 3; return (n - 20) + Math.max(replace, 3 - categories); } } }

總結

這道題難就難在需要我們運用邏輯數學思維。分類討論，每種情況做不同的策略就行了。具體程式碼按照思路實現即可

學好數理化，寫遍所有程式碼都不怕，我用數學分類討論的思想解決