今日学习记录
1. 3703. 移除 K-平衡子字符串
关键词：栈
问题分析：
就是括号匹配问题,经典的栈题目
核心思路:
直接暴力模拟
这个方法其实跟栈没关系,每次把符号先进栈,遇到’(‘时直接进栈,遇到’)‘时检查栈内元素是否大于2*k,再检查前 k 个元素是否都为’(‘,后 k 个元素是否都为’)‘,这样就行了,由于没用啥栈,直接用 string
string removeSubstring(string s, int k) {
string st = "";
for (char c : s) {
st.push_back(c);
if (c == ')' && st.size() >= 2 * k) {
bool isKBalanced = true;
for (int i = 0; i < k; i++) {
if (st[st.size() - 2 * k + i] != '(') {
isKBalanced = false;
break;
}
}
for (int i = 0; i < k; i++) {
if (st[st.size() - k + i] != ')') {
isKBalanced = false;
break;
}
}
if (isKBalanced) {
st.resize(st.size() - 2 * k);
}
}
}
return st;
}栈
有个技巧,不进行直接模拟,而是记录相同类型符号的次数使用 pair<char,int>元素,统计每个连续的符号的数量进行储存,每次枚举时检查栈顶的元素,相同则合并不同则可以快速知道对应的数量,然后进行判断匹配
string removeSubstring(string s, int k) {
vector<pair<char,int>> st;
for(char &c:s){
if(!st.empty()&&st.back().first==c) st.back().second++;
else st.push_back({c,1});
if(c==')'&&st.size()>=2&&st.back().second==k&&st[st.size()-2].second>=k){
st.pop_back();
st.back().second -= k;
if(st.back().second==0) st.pop_back();
}
}
string ans = "";
for(auto &p:st){
ans += string(p.second,p.first);
}
return ans;
}学到的点：
- 栈
2. P13787 地毯 加强版 - 洛谷
关键词：前缀和 差分
问题分析：
经典的二维前缀和还有差分,就是盖毯子,对一个区间进行高维的加法
核心思路
二维差分
主要学习前缀和 & 差分 - OI Wiki 这个题就是先读取坐标设置二维差分,最后再处理的时候再使用二维前缀和进行计算每个点的数值,比较模板
#include<bits/stdc++.h>
using namespace std;
const int N = 10000;
int n,m,x1,y,x2,y2;
int arr[N][N];
int main(){
cin>>n>>m;
while(m--){
cin>>x1>>y>>x2>>y2;
arr[x1][y]++;
arr[x1][y2+1]--;arr[x2+1][y]--;
arr[x2+1][y2+1]++;
}
long long ans = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
arr[i][j] += arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
ans += (i+j)^arr[i][j];
}
}
cout<<ans;
return 0;
}学到的点：
- 二维前缀和
- 二维差分