文章目錄
- 😉毛遂自薦
- ?題目
- 🌝解題
- 雙堆疊
- 思路
- 代碼實作
- 貪心
- 思路
- 代碼實作
- 💖最后
Code皮皮蝦 一個沙雕而又有趣的憨憨少年，和大多數小伙伴們一樣喜歡聽歌、游戲，當然除此之外還有寫作的興趣，emm…，日子還很長，讓我們一起加油努力叭🌈
🚀🚀🚀話不多說，直達底部有粉絲專享福利！！！
😉毛遂自薦
毛遂自薦一下，給大家推薦一下自己的專欄😁，歡迎小伙伴們收藏關注😊
大廠面試題專欄
Java專欄
爬蟲專欄
更多專欄盡在主頁，點我😁！！！
?題目
🌝解題
雙堆疊
思路
因為題目有*的存在，而且*既可以為左括號，也可以為右括號或者空字串，所以需要使用兩個堆疊來實作
leftStack堆疊存盤左括號的索引，starStack堆疊存盤星號的索引
在遍歷程序中，如果遇到右括號
- 優先匹配左括號，即對
leftStack進行pop - 如果
leftStack為空，則對starStack進行pop - 如果
starStack為空，說明匹配不了了，直接return false
在遍歷完成之后，可能存在leftStack 和 starStack不為空的情況，那么此時，就需要將*當作右括號，從而對括號進行匹配，
最后，如果leftStack為空，說明匹配完成，return true，否則，return false
代碼實作
class Solution {
public boolean checkValidString(String s) {
//存盤左括號索引
Deque<Integer> leftStack = new LinkedList<>();
//存盤*索引
Deque<Integer> starStack = new LinkedList<>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
leftStack.push(i);
} else if (c == '*') {
starStack.push(i);
} else {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!starStack.isEmpty()) {
starStack.pop();
} else return false;
}
}
while (!leftStack.isEmpty() && !starStack.isEmpty()) {
//把*當成右括號，但是必須右括號的索引 > 左括號才能匹配
//因為是堆疊結構，所以根據遍歷，堆疊頂元素的索引是最大的索引，如果不滿足就return false
if (leftStack.pop() > starStack.pop()) {
return false;
}
}
return leftStack.isEmpty();
}
}
貪心
思路
因為題目有*的存在，而*既可以為左括號，也可以為右括號或者空字串
所以我們可以維護一個未匹配左括號的范圍，即[min,max]，遍歷完成后，直接return min == 0
🔥怎么維護？？？
- 遇到左括號，則
min++ , max++ - 遇到右括號，則
min-- , max--，如果max == 0了，說了沒有可以匹配的了，那么直接return false - 遇到
*號，則min-- , max++，因為*既可以為左括號，也可以為右括號
代碼實作
class Solution {
public boolean checkValidString(String s) {
int min = 0, max = 0; // 維護當前左括號的數量范圍：[min, max]
char[] chars = s.toCharArray();
for(char i : chars) {
if(i == '(') {
min++;
max++;
}else if(i == ')') {
//min > 0才--
if(min > 0) min--;
if(max-- == 0) return false;
}else {
//min > 0才--
if(min > 0) min--;
max++;
}
}
return min == 0;
}
}
💖最后
我是 Code皮皮蝦，一個熱愛分享知識的 皮皮蝦愛好者，未來的日子里會不斷更新出對大家有益的博文，期待大家的關注！！！
創作不易，如果這篇博文對各位有幫助，希望各位小伙伴可以一鍵三連哦！，感謝支持，我們下次再見~~~
公眾號干貨內容輸出，囊括Java、Python爬蟲、力扣題解、大廠面試題 四大系列，更有長時間總結的干貨資源分享，后臺回復：面試資料即可領取
最后，祝各位步步高升🚀🚀🚀
粉絲福利👇🏻👇🏻👇🏻
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300227.html
標籤：java