看板Marginalman
1544. Make The String Great
龍大是個字串處理員他會收到很多字串,如果這個字串壞掉了他就要把字串壞掉的部分切
掉,一個字串是「好」的他必須滿足:
* 任意兩個相鄰字串不可以是一個大寫一個小寫的英文字母
例如:leE(eE是壞的所以要切掉讓他變l)
字串只包含大小寫英文字母。
Example1:
Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will
result "le
Eeetcode" to be reduced to "leetcode".
Example2:
Input: s = "abBAcC"
Output: ""
Explanation: 刪除的順序可能有多種:
"a
bBAcC" --> "
aAcC" --> "
cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
思路:
1.大寫字母可以和小寫字母「兩兩消除」,我們可以聯想到刮號問題,所以這題很明顯
是要用stack來解。
2.先寫一個判斷兩字元是否是大小寫字母的函數。
3.分成兩個case:
* stack為空
把當前字母push進stack
* stack不為空
就把當前字母與stack頂端比較,如果可以消除(一個大寫一個小寫)就從stack
中pop出一個元素,否則把當前字母push進stack
4.如果字串都處理完了,因為stack的特性所以原字串拿出來的時候順序相反,我們把
stack裡的字元全部pop出來,並且倒序構建字串就是解字串了。
JavaCode:
----------------------------------------------------------
class Solution {
public String makeGood(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (stack.isEmpty() || isNotBad(stack.peek(), s.charAt(i))) {
stack.push(s.charAt(i));
} else {
stack.pop();
}
}
char[] chars = new char[stack.size()];
for (int i = stack.size() - 1; i >= 0; i--) {
chars[i] = stack.pop();
}
return new String(chars);
}
private boolean isNotBad(char c1, char c2) {
return Math.abs(c1 - c2) != 32;
}
}
-----------------------------------------------------------
https://i.imgur.com/BtsJXgg.gif
--
https://i.imgur.com/tdaniED.jpg
--
※ 批踢踢實業坊(ptt.cc), 來自: 1.160.66.39 (臺灣)※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667870871.A.48D.html
推 p54661205: 大師 11/08 09:30
推 pandix: 大師 11/08 09:38
→ pandix: java不能直接把stack轉陣列喔 好麻煩 11/08 09:39
→ Rushia: :( 11/08 09:40
→ Rushia: 可以轉泛型陣列Character[] 但是沒啥用因為String沒有對應 11/08 09:46
→ Rushia: 的建構式 只能接受char[] 11/08 09:46
→ PyTorch: 大師 11/08 09:50