成都网站建设 培训站长素材网站官网
字符串
双指针
反转字符串(双指针)
力扣题目链接
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 个高频元素
- 要统计元素出现频率
- 对频率排序
- 找出前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;}
};