字符串与栈和队列-算法小结

字符串

双指针

反转字符串(双指针)

力扣题目链接

void reverseString(vector<char>& s) {for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {swap(s[i],s[j]);}
}

反转字符串II

力扣题目链接
遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间

    string reverseStr(string s, int k) {for(int i=0;i<s.size();i+=(2*k)){if(i+k <= s.size()){reverse(s.begin()+i,s.begin()+k+i);}else{reverse(s.begin()+i,s.end());}}return s;}

翻转字符串里的单词

我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转
  力扣题目链接

class Solution {
public:string reverseWords(string s) {reverse(s.begin(),s.end());int y=0;for(int i=0;i<=s.size();i++){if(s[i]==' '){reverse(s.begin()+y,s.begin()+i);y=i+1;}     }         reverse(s.begin()+y,s.end());removeExtraSpaces(s);return s;    }//移除元素(双指针)void removeExtraSpaces(string& s) {int slow = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] != ' ') { if (slow != 0) s[slow++] = ' '; while (i < s.size() && s[i] != ' ') { s[slow++] = s[i++];}}}s.resize(slow); }
}; 

实现 strStr()

力扣题目链接

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();for (int i = 0; i + m <= n; i++) {bool flag = true;for (int j = 0; j < m; j++) {if (haystack[i + j] != needle[j]) {flag = false;break;}}if (flag) {return i;}}return -1;}
};

KMP算法-CSDN博客

重复的子字符串

class Solution {
public:void getNext (int* next, const string& s){next[0] = -1;int j = -1;for(int i = 1;i < s.size(); i++){while(j >= 0 && s[i] != s[j + 1]) {j = next[j];}if(s[i] == s[j + 1]) {j++;}next[i] = j;}}bool repeatedSubstringPattern(string s) {if (s.size() == 0) {return false;}int next[s.size()];getNext(next, s);int n = s.size();if(next[n-1]!=-1 && n% (n- (next[n - 1] + 1))==0){return true;}return false;}
};

栈与队列

字符串去重

栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素

从栈里弹出的元素是倒序的，所以再对字符串进行反转一下

class Solution {
public:string removeDuplicates(string S) {stack<char> st;for (char s : S) {if (st.empty() || s != st.top()) {st.push(s);} else {st.pop(); }}string result = "";while (!st.empty()) { result += st.top();st.pop();}reverse (result.begin(), result.end());return result;}
};

可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};

逆波兰表达式求值

计算机可以利用栈来顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的

中缀：a * ( b + c ) - d   ->  ((a * ( b + c )) - d)//将每个运算符左移到当前括号前 
前缀：- * a + b c d       <-  - (*(a +( b  c ))  d)        //波兰式 
//将每个运算符左移到当前括号后
后缀：a b c + * d -       <-   ((a ( b  c )+) *  d)-       //逆波兰式

2分钟秒杀-中缀表达式转前后缀表达式_哔哩哔哩_bilibili
【算法】数据结构中的栈有什么用？_哔哩哔哩_bilibili

优先级可以看为加上括号

bool isOperator(char c)
{return c == '+' || c == '-' || c == '*' || c == '/'||c=='^';}map <char, int> precedence = {{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}
};int applyop(int a, int b, char c)
{switch (c){case'+':return a + b; case'-':return a - b; case'*':return a * b; case'/':return a / b;case'^':return pow(a, b); }}void valute(stack<int>& val, stack<char>& ope)
{int val2 = val.top(); val.pop();int val1 = val.top(); val.pop();char ops = ope.top(); ope.pop();val.push(applyop(val1, val2, ops));
}int compute(const string& input)
{stack<int>val;stack<char> ope;for (int i=0;i<input.length();i++){char ch = input[i];if (isspace(ch))continue;else if (isdigit(ch)) {int num = 0;while (i < input.length() && isdigit(input[i])) {num = num * 10 + (input[i] - '0');i++;}val.push(num);i--;}else if (ch == '(') {ope.push(ch);}else if (ch == ')'){while (!ope.empty() && ope.top() != '('){	valute(val, ope);}ope.pop();}else if (isOperator(ch)) {while (!ope.empty() && precedence[ope.top()] >= precedence[ch]) {valute(val, ope);}ope.push(ch);}}while (!ope.empty()) {valute(val, ope);}return val.top();
}
int main()
{string expression;cin >> expression;cout << compute(expression) << endl;return 0;
}

compute
遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}long long result = st.top();st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）return result;}
};

滑动窗口最大值

![[Pasted image 20250405163224.png]]
大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。

此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么

class Solution {class MyQueue { //单调队列（从大到小）public:deque<int> que;void pop(int value){if(!que.empty()&&que.front()==value){que.pop_front();}}void push(int value){while(!que.empty()&&value>que.back()){que.pop_back();}que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue  n;vector<int>max_num;for(int i=0;i<k;i++){n.push(nums[i]);}max_num.push_back(n.front());for(int i=k;i<nums.size();i++){n.pop(nums[i-k]);  n.push(nums[i]);max_num.push_back(n.front());}return max_num;}
};

前 K 个高频元素

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

使用优先级队列来对部分频率进行排序

为什么不用快排呢， 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的

而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

class Solution {
class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};                
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int>map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for(auto m:map){pri_que.push(m);if(pri_que.size()>k){pri_que.pop();}}vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};