LeetCode演算法題-License Key Formatting（Java實現）
這是悅樂書的第241 次更新，第254 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第108題（順位題號是482）。您將獲得一個表示為字串S的許可證金鑰，該字串僅包含字母數字字元和短劃線。該字串被N個破折號分成N + 1個組。
給定數字K，我們希望重新格式化字串，使得每個組包含正好的K個字元，但第一個組可能比K短，但仍然必須包含至少一個字元。此外，必須在兩個組之間插入短劃線，並且所有小寫字母都應轉換為大寫。給定非空字串S和數字K，根據上述規則格式化字串。例如：
輸入：S =“5F3Z-2e-9-w”，K = 4
輸出：“5F3Z-2E9W”
說明：字串S分為兩部分，每部分有4個字元。請注意，不需要兩個額外的破折號，可以刪除。
輸入：S =“2-5g-3-J”，K = 2
輸出：“2-5G-3J”
說明：字串S被分成三個部分，每個部分除了第一部分之外有2個字元，因為它可以更短，如上所述。
注意：
-
字串S的長度不超過12,000，K是正整數。
-
字串S僅由字母數字字元（a-z和/或A-Z和/或0-9）和短劃線（ - ）組成。
-
字串S非空。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
先將S中的"-"給替換掉，然後從後往前進行擷取K個子串，並將其用“-”連線，如果最後一次擷取的長度不夠K，就直接從0開始擷取，最後將新的字串轉為大寫字母並返回。
public String licenseKeyFormatting(String S, int K) {
StringBuilder sb= new StringBuilder();
String ss = S.replace("-", "");
for (int i=ss.length(); i>0; i-= K) {
if (i-K > 0) {
sb.insert(0, "-"+ss.substring(i-K, i));
} else {
sb.insert(0, ss.substring(0, i));
}
}
return sb.toString().toUpperCase();
}
03 第二種解法
將S變為字元陣列，然後從後往前遍歷，使用一個變數記數，來判斷是否使用“-”連線兩端，使用完“-”後，count要重歸於1，以便下次繼續使用。
public String licenseKeyFormatting2(String S, int K) {
StringBuilder sb= new StringBuilder();
char[] arr = S.toCharArray();
int count = 0, len = S.length()-1;
for (int i=len; i>=0; i--) {
if (arr[i] != '-') {
if (count < K) {
sb.append(arr[i]+"");
count++;
} else {
sb.append("-");
sb.append(arr[i]+"");
count = 1;
}
}
}
return sb.reverse().toString().toUpperCase();
}
04 第三種解法
和第二種思路一樣，在判斷什麼時候使用"-"時，用了一點取巧，
sb.length() % (K + 1)
使用新字串的長度對K+1取餘，如果等於K，就說明新字串到了該拼接"-"的位置了。
public String licenseKeyFormatting3(String S, int K) {
StringBuilder sb = new StringBuilder();
for (int i = S.length() - 1; i >= 0; i--) {
if (S.charAt(i) != '-'){
sb.append(sb.length() % (K + 1) == K ? '-' : "").append(S.charAt(i));
}
}
return sb.reverse().toString().toUpperCase();
}
05 小結
演算法專題目前已日更超過三個月，演算法題文章108+篇，公眾號對話方塊回覆【資料結構與演算法】、【演算法】、【資料結構】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！