目錄
- 155. 最小堆疊
- 思路決議
- 20. 有效的括號
- 思路決議
- 1047. 洗掉字串中的所有相鄰重復項
- 思路決議
- 1209. 洗掉字串中的所有相鄰重復項 II
- 思路決議
- 洗掉字串中出現次數 >= 2 次的相鄰字符
- 劍指 Offer 09. 用兩個堆疊實作佇列
- 239. 滑動視窗最大值
- 思路決議
155. 最小堆疊
設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的堆疊，
實作 MinStack 類:
- MinStack() 初始化堆疊物件，
- void push(int val) 將元素val推入堆疊，
- void pop() 洗掉堆疊頂部的元素，
- int top() 獲取堆疊頂部的元素，
- int getMin() 獲取堆疊中的最小元素，
提示：
-
\(-2^{31}\) <= val <= \(2^{31}\) - 1
-
pop、top 和 getMin 操作總是在 非空堆疊 上呼叫
-
push, pop, top, and getMin最多被呼叫 \(3 * 10^4\) 次
-
思路決議
因為會不斷的入堆疊和出堆疊，那就要保證，不論入堆疊還是出堆疊，我時刻知道，到堆疊中當前位置的最小值是誰，
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
對于上述輸入，-2入堆疊時，最小值是-2，0入堆疊是，最小值是-2，-3入堆疊是最小值是-3
也就是我需要兩個堆疊，一個堆疊用于存盤元素，完成元素的push和pop操作；一個堆疊用于存盤當前最小值，如果最小值更新就存入最小堆疊，
class MinStack {
public:
MinStack() {
}
void push(int val) {
if (val <= getMin()) {
minStack.emplace(val);
}
valStack.emplace(val);
}
void pop() {
if (valStack.empty()) {
return;
}
int ret = valStack.top();
valStack.pop();
if (ret == getMin()) {
minStack.pop();
}
}
int top() {
return valStack.top();
}
int getMin() {
if (minStack.empty()) {
return INT_MAX;
}
return minStack.top();
}
private:
stack<int> valStack;
stack<int> minStack;
};
20. 有效的括號
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效，
有效字串需滿足：
-
左括號必須用相同型別的右括號閉合，
-
左括號必須以正確的順序閉合，
-
每個右括號都有一個對應的相同型別的左括號，
-
思路決議
將匹配項做一個map單獨存盤，這樣子有更好的擴展性，
遇到左括號就入堆疊，遇到右括號，判斷是否與堆疊頂元素配對，配上就出堆疊，否則就回傳false，
class Solution {
public:
bool isValid(string s) {
stack<char> bracketsStack;
for (auto &iter : s) {
// 遇到左括號就入堆疊，遇到右括號，判斷堆疊頂是否為其對應的左括號，如果是則出堆疊
if (typeMap.count(iter) != 0) {
bracketsStack.emplace(iter);
} else {
if (bracketsStack.empty() || iter != typeMap[bracketsStack.top()]) {
return false;
}
bracketsStack.pop();
}
}
if (bracketsStack.empty()) {
return true;
}
return false;
}
private:
unordered_map<char, char> typeMap = {
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
};
1047. 洗掉字串中的所有相鄰重復項
給出由小寫字母組成的字串 S，重復項洗掉操作會選擇兩個相鄰且相同的字母，并洗掉它們，
在 S 上反復執行重復項洗掉操作，直到無法繼續洗掉，
在完成所有重復項洗掉操作后回傳最終的字串，答案保證唯一，
輸入："abbaca"
輸出："ca"
輸入："abbbaca"
輸出："abaca"
-
思路決議
string提供了兩個操作
- front：訪問第一個字符
- back：查詢最后一個字符
- pop_back：彈出尾巴字符，實作：length - 1即可
- push_back：插入元素
string removeDuplicates(string s) {
string res;
for (auto &iter : s) {
if (!res.empty() && iter == res.back()) {
res.pop_back();
} else {
res.push_back(iter);
}
}
return res;
}
1209. 洗掉字串中的所有相鄰重復項 II
給你一個字串 s，「k 倍重復項洗掉操作」將會從 s 中選擇 k 個相鄰且相等的字母，并洗掉它們，使被刪去的字串的左側和右側連在一起，
你需要對 s 重復進行無限次這樣的洗掉操作，直到無法繼續為止，
在執行完所有洗掉操作后，回傳最終得到的字串，
輸入：s = "deeedbbcccbdaa", k = 3
輸出："aa"
解釋：
先洗掉 "eee" 和 "ccc"，得到 "ddbbbdaa"
再洗掉 "bbb"，得到 "dddaa"
最后洗掉 "ddd"，得到 "aa"
-
思路決議
遍歷到某個字符的時候，判斷當前字符與堆疊頂字符是否相同
- 如果不同，則直接入堆疊并開始計數
- 如果相同，則判斷當前堆疊頂元素累積了多少個該元素，如果累積的個數小于k-1，則繼續累積，如果累積到了k-1個，當前又相同了，那么堆疊頂元素就可以彈出了，
string removeDuplicates(string s, int k) {
stack<std::pair<char, int>> pairStack; // 每個元素存盤當前的元素及有幾個連續的值
for (size_t i = 0; i < s.length(); i++) {
if (!pairStack.empty() && pairStack.top().first == s[i]) {
// 此時，看一下堆疊中是否已經有k-1個s[i]相同的元素，如果有，則pop出這k-1個，如果沒有，則push進去
if (pairStack.top().second == k - 1) {
pairStack.pop();
} else {
pairStack.top().second++;
}
} else {
pairStack.emplace(std::pair<char, int>(s[i], 1));
}
}
string res;
while(!pairStack.empty()) {
while (pairStack.top().second-- > 0) {
res += pairStack.top().first;
}
pairStack.pop();
}
reverse(res.begin(), res.end());
return res;
}
洗掉字串中出現次數 >= 2 次的相鄰字符
第二次出現的時候，說明出現次數大于2了，這時候就可以洗掉了，同時跳過s中后續與當前字符相同的元素即可，
string removeDuplicates(string s, int k) {
string res; // 每個元素存盤當前的元素及有幾個連續的值
for (size_t i = 0; i < s.length(); ) {
if (!res.empty() && res.back() == s[i]) {
// 此時，說明已經出現過的字符第二次出現了
char currChar = s[i];
while(s[i] == currChar) {
// 跳過s中其他相同的字符
i++;
}
res.pop_back();
} else {
res.push_back(s[i]);
i++;
}
}
return res;
}
劍指 Offer 09. 用兩個堆疊實作佇列
用兩個堆疊實作一個佇列，佇列的宣告如下，請實作它的兩個函式 appendTail 和 deleteHead ，分別完成在佇列尾部插入整數和在佇列頭部洗掉整數的功能，(若佇列中沒有元素，deleteHead 操作回傳 -1 )
class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
stackIn.emplace(value);
}
int deleteHead() {
if (stackOut.empty()) {
while (!stackIn.empty()) {
stackOut.emplace(stackIn.top());
stackIn.pop();
}
}
if (stackOut.empty()) {
return -1;
}
auto ret = stackOut.top();
stackOut.pop();
return ret;
}
private:
stack<int> stackOut; // 輸出堆疊，元素按照輸入順序的堆疊
stack<int> stackIn; // 輸入元素存放堆疊，與輸入順序相反的堆疊
};
239. 滑動視窗最大值
給你一個整數陣列 nums，有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側，你只可以看到在滑動視窗內的 k 個數字，滑動視窗每次只向右移動一位，回傳 滑動視窗中的最大值 ，
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動視窗的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
-
思路決議
假設視窗為[left, right]，那么只要nums[i]比nums[j]小，則nums[i]就不納入考慮范圍，所以，當right進入視窗的時候，前面比nums[right]小的元素統統可以移除考慮范圍了；這樣子，留下的元素是從大到小有序的，
因為我們要移除比當前元素小的元素，也要獲取最大的元素作為當前視窗最大值，因此，可以使用雙端佇列來實作，
// 移除比當前元素小的所有元素,只留下比當前元素大的元素
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
// 獲取當前視窗最大值,放入結果中
resVec.emplace_back(nums[dQ.front()]);
// 如果最大值應該要移除了，則移除
if (dQ.front() + k <= i) {
dQ.pop_front();
}
完整的實作代碼如下：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dQ;
for (size_t i = 0; i < k; i++) {
// 當前佇列中僅保留比當前元素大的元素的位置,佇列中下標對應的元素由大到小
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
dQ.emplace_back(i);
}
vector<int> resVec = {nums[dQ.front()]};
for (size_t i = k; i < nums.size(); i++) {
// 當前佇列中僅保留比當前元素大的元素的位置
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
dQ.emplace_back(i);
if (dQ.front() <= i - k) {
dQ.pop_front();
}
resVec.emplace_back(nums[dQ.front()]);
}
return resVec;
}
需要完整版練習筆記，可關注公眾號后臺私信~~
關注我的公眾號 不定期推送資訊，接受私信許愿
作者：iSherryZhang 出處：https://www.cnblogs.com/shuezhang/ 本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548839.html
標籤：其他
上一篇：最長上升子序列 II
下一篇：16.隧道通信技術