一、数字统计（数字+模拟）
[NOIP2010]数字统计_牛客题霸_牛客网
循环提取末尾，然后干掉末尾
#include <iostream>
using namespace std;
int l,r;
int main() {cin>>l>>r;int ret=0;for(int i=l;i<=r;++i){int tmp=i;while(tmp){ret+=tmp%10==2;tmp/=10;}}cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")二、两个数组的交集（哈希）
两个数组的交集_牛客题霸_牛客网
a. 将其中⼀个数组丢进哈希表中；
b. 遍历另⼀个数组的时候，在哈希表中看看就好了。插入ret后要把该数在哈希表中移除
class Solution {
public:bool hash[1010]={0};vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;for(auto&e:nums1) hash[e]=true;for(auto&e:nums2) if(hash[e]){ret.emplace_back(e);hash[e]=false;}return ret;}
};三、点击消除（栈）
点击消除_牛客题霸_牛客网
⽤字符串模拟栈进行消除的过程。
#include <iostream>
#include <stack>
#include <string>
using namespace std;int main() {string s,st;cin>>s;for(auto&ch:s)if(st.empty()||st.back()!=ch) st+=ch;else st.pop_back();cout << (st.empty()?"0":st) << endl;}
// 64 位输出请用 printf("%lld")四、*牛牛的快递（模拟）
牛牛的快递_牛客题霸_牛客网
模拟：分情况讨论即可。
扩展两个库函数： ceil（向上取整） 和 floor（向下取整） （天花板和地板）在cmath的头文件里
#include <iostream>
#include <cmath>
using namespace std;int main() {float a;//重量char b;//是否加急cin>>a>>b;int ret=20;//无论如何都至少有20if(a>1) ret+=ceil(a-1);//向上取整if(b=='y') ret+=5;cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")五、最小花费爬楼梯（线性dp）
最小花费爬楼梯_牛客题霸_牛客网
#include <iostream>
using namespace std;
const int N=1e5+1;
int dp[N];
int cost[N];
int main() {//dp[i]表示以i位置结尾时 所需要的最小花费int n;cin>>n;for(int i=0;i<n;++i) cin>>cost[i];//记录上花费for(int i=2;i<=n;++i) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);cout<<dp[n]<<endl;
}
// 64 位输出请用 printf("%lld")六、数组中两个字符串的最小距离（模拟+贪心）
数组中两个字符串的最小距离__牛客网
⼩贪⼼，或者是⼩dp：
◦ ⽤prev1 标记 i 位置之前最近⼀次出现的第⼀个字符串的下标；
◦ ⽤prev2 标记 i 位置之前最近⼀次出现的第⼆个字符串的下标。
#include <iostream>
#include<string>
using namespace std;int main() {int n;string str1,str2;cin>>n>>str1>>str2;string s;int prev1=-1,prev2=-1,ret=0x3f3f3f3f;for(int i=0;i<n;++i){cin>>s;//因为我们要找的是最近的 所以我们只要保留尽量靠后的下标就行了if(s==str1){//当找到相同的时候if(prev2!=-1) ret=min(ret,i-prev2);prev1=i;}else if(s==str2){if(prev1!=-1) ret=min(ret,i-prev1);prev2=i;}}if(ret==0x3f3f3f3f) cout<<-1<<endl;else cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")七、*简单单词（模拟）
简写单词_牛客题霸_牛客网
简单模拟题，主要是处理⼀下输⼊的问题。 while(cin>>a) 可以帮助我们跳过空格
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
//cctype头文件 0-9 isdigit a-z islower A-Z isupper 字母isalpha 字母+数字isalnum
int main() {string s;while(cin>>s){//可以自动跳过空格//cout<<(char)(towupper(s[0]));//他返回的是int类型ascii if(islower(s[0])) s[0]-=32;//-=32是小写转大写 ^=是大小写互换cout<<s[0];}
}
// 64 位输出请用 printf("%lld")//cctype头文件
0-9 isdigit
a-z islower
A-Z isupper
字母 isalpha
字母+数字isalnum
变成大写toupper
变成小写tolower
大小写转换^=32
八、*dd爱框框（可变滑动窗口）
登录—专业IT笔试面试备考平台_牛客网
可变滑动窗口，如果找最小区间出窗口时也要更新，如果找最大区间窗口出完再更新
数组可以尽量多用全局静态数组
#include<iostream>
const int N=1e7+1;
int nums[N];//要多用这种数组
//滑动窗口 如果找区间最小，更新就要在循环里，如果找的是最大的 那么更新可以在循环外面
using namespace std;
int main(){int n,x;cin>>n>>x;//n是个数 x是要>=的for(int i=1;i<=n;++i) cin>>nums[i];int l=-1,r=n;//该题不需要长度 所以我们不管长度int sum=0;//用来统计是否超过x//开始进行滑动窗口for(int left=1,right=1;right<=n;++right){sum+=nums[right];while(sum>=x){//因为是最小，所以出窗口前都要判断一下if(right-left<r-l) l=left,r=right;sum-=nums[left++];}}cout<<l<<" "<<r<<endl;
}九、除2！（贪心+优先级队列）
登录—专业IT笔试面试备考平台_牛客网
//用一个堆模拟一下 该题数据量很大，所以可以用long
//但是最好还是不要用long 因为有的平台下他也是4个字节
#include<iostream>
#include<queue>//优先级队列是在这个头文件里面的
using namespace std;
typedef long long LL;//对类型重命名，这样方便写
int main(){int n,k;cin>>n>>k;LL x,sum;//一个用来统计数据，一个用来计算总和priority_queue<LL> q;while(n--){//如果这个变量无所谓变化的话,其实用while比for循环会更简洁一点cin>>x;sum+=x;if(x%2==0) q.push(x);}while(!q.empty()&&k--){x=q.top()/2;q.pop();sum-=x;if(x%2==0) q.push(x);}cout<<sum<<endl;
}十、Fibonacci数列（递推）
Fibonacci数列_牛客题霸_牛客网
#include <iostream>
using namespace std;
//0 1 1 2 3 5 8 13 21 34…… 相当于是某个数在这个序列某两个数之间 然后选离其中一个最近的距离
//问题是我们怎么构建这个序列呢 如果搞个数组肯定没必要
//我们可以直接用变量存储 找到他的前一个数和后一个数 即可
int main() {int n;cin>>n;int a=0,b=1,c=1;while(n>c){a=b;b=c;c=a+b;}cout<<min(c-n,n-b)<<endl;
}
// 64 位输出请用 printf("%lld")十一、单词搜索（dfs）
单词搜索_牛客题霸_牛客网
class Solution {
public:
//dfs专题
int m,n;
bool vis[101][101];//标记数组
int dx[4]={0,0,1,-1};//向量数组
int dy[4]={1,-1,0,0};bool exist(vector<string>& board, string word) {m=board.size(),n=board[0].size();for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(board[i][j]==word[0]&&dfs(board,i,j,word,0)) return true;return false; }bool dfs(vector<string>& board,int i,int j,string&word,int pos){if(pos==word.size()-1) return true;vis[i][j]=true;for(int k=0;k<4;++k){int x=dx[k]+i,y=dy[k]+j;if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&board[x][y]==word[pos+1]&&dfs(board,x,y,word,pos+1)) return true;}return vis[i][j]=false;}
};十二、杨辉三角（线性dp）
杨辉三角_牛客题霸_牛客网
#include <iostream>
using namespace std;
int dp[31][31];//一层虚拟边界
int main() {int n;cin>>n;dp[1][1]=1;for(int i=2;i<=n;++i)for(int j=1;j<=i;++j) dp[i][j]=dp[i-1][j]+dp[i-1][j-1];//开始打印 要按照输出格式for(int i=1;i<=n;++i){for(int j=1;j<=i;++j)printf("%5d",dp[i][j]);printf("\n");}
}
// 64 位输出请用 printf("%lld")十三、游游的you（贪心+模拟）
游游的you__牛客网
you和oo是相互独⽴的；
◦ 但是you的分值更⾼，因此我们应该优先去拼凑you，然后再考虑oo
#include <iostream>
using namespace std;
//贪心策略 最好的情况下我们拼出尽可能多的you 然后剩下的拼oo
//oo是第一个不算 剩下的连在一起的可以算
int main() {int q,a,b,c;//q是询问次数 a b c是you分别的个数cin>>q;while(q--){cin>>a>>b>>c;int x=min(a,min(b,c));//最小值决定了可以有几个youcout<<(x*2+max((b-x-1),0))<<endl;}
}
// 64 位输出请用 printf("%lld")十四、腐烂的苹果（多源bfs最短路）
腐烂的苹果_牛客题霸_牛客网
#include <queue>
class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int rotApple(vector<vector<int> >& grid) {//多源BFS 超级源点int m=grid.size(),n=grid[0].size();queue<pair<int,int>> q;for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(grid[i][j]==2) q.emplace(i,j);int ret=0;//统计时间while(!q.empty()){++ret;int sz=q.size();for(int i=0;i<sz;++i){auto [a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){q.emplace(x,y);grid[x][y]=2;}}}}//这个时候已经扩散完了 还需要去检查一下有没有完好的苹果for(auto&v:grid) for(auto&e:v)if(e==1) return -1;return ret-1;}
};十五、**约瑟夫环（模拟/数学规律）
孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网
解法1：环形链表模拟（要熟悉迭代器删除）
class Solution {
public:int LastRemaining_Solution(int n, int m) {if(n<1||m<1) return -1;//环形链表模拟list<int> nums;for(int i=0;i<n;++i) nums.emplace_back(i);//开始进行模拟auto it=nums.begin();while(nums.size()>1){//开始数mfor(int i=1;i<m;++i)if(++it==nums.end()) it=nums.begin();//越界了就要恢复it=nums.erase(it);//迭代器删除后返回的是被删除元素的下一个位置if(it==nums.end()) it=nums.begin();//可能恰好删除的是最后一个}return *it;}
};解法2：数学规律（递推、动归）
class Solution {
public:int LastRemaining_Solution(int n, int m) {int f=0;for(int i=2;i<=n;++i) f=(f+m)%i;return f;}
};十六、**大数加法（高精度加法模拟）
大数加法_牛客题霸_牛客网
class Solution {
public:string solve(string s, string t) {int m=s.size(),n=t.size();if(m==0) return t;if(n==0) return s;string ret;ret.reserve(max(m,n)+1);//提前扩容int cur1=m-1,cur2=n-1;int tmp=0;//进位信息while(cur1>=0||cur2>=0||tmp){if(cur1>=0) tmp+=s[cur1--]-'0';if(cur2>=0) tmp+=t[cur2--]-'0';ret+=tmp%10+'0';tmp/=10;}reverse(ret.begin(),ret.end());return ret;}
};十七、**链表相加（高精度加法模拟）
链表相加(二)_牛客题霸_牛客网
class Solution {
public:ListNode* reverse(ListNode*head){//用三指针if(!head&&!head->next) return head;ListNode*p1=nullptr,*p2=head,*p3=head->next;while(p2){p2->next=p1;p1=p2;p2=p3;if(p3) p3=p3->next;}return p1;}ListNode* addInList(ListNode* head1, ListNode* head2) {//因为要从后往前加 所以必须要先想办法把链表进行逆序 head1=reverse(head1);head2=reverse(head2);//给新链表搞一个哨兵头节点ListNode*cur1=head1,*cur2=head2;ListNode*neahead=new ListNode(-1);ListNode*ptail=neahead;//用来尾插用的int t=0;//保持高精度while(cur1||cur2||t){if(cur1){t+=cur1->val;cur1=cur1->next;}if(cur2){t+=cur2->val;cur2=cur2->next;}ptail=ptail->next=new ListNode(t%10);t/=10;}cur1=neahead->next;delete neahead;return reverse(cur1);}
};十八、**大数乘法（高精度乘法模拟）
大数乘法_牛客题霸_牛客网
class Solution {
public: //从后往前不需要处理前导0string solve(string num1, string num2){ //高位相乘补0 处理前导0 最后处理进位if(num1=="0"||num2=="0") return "0";string ret="0";//处理返回值 方便进行相加int m = num1.size(), n = num2.size();for(int i=n-1;i>=0;--i){string cur;int add=0;//处理进位for(int j=n-1;j>i;--j) //为了高位的补0cur.push_back('0');int y=num2[i]-'0';//取出这一位for(int j=m-1;j>=0;--j){int x=num1[j]-'0';int product=x*y+add;cur.push_back(product%10+'0');add=product/10;//保留进位}while(add){cur.push_back(add%10+'0');add/=10;}reverse(cur.begin(),cur.end());ret= addBinary(ret, cur);}return ret;}string addBinary(string a, string b) {//模拟进位相加，但是区别就是逢2进1size_t n1=a.size(),n2=b.size();string ret;//返回 从后往前模拟进位相加ret.reserve(n1>n2?n1+1:n2+1);//提前开空间 减少时间消耗int cur1=n1-1; int cur2=n2-1;int t=0;while(cur1>=0||cur2>=0||t) //可能会有进位的遗失{if(cur1>=0) t+=a[cur1--]-'0';if(cur2>=0) t+=b[cur2--]-'0';ret+=t%10+'0';t/=10;}reverse(ret.begin(),ret.end());//结果要反转一下return ret;}
};
class Solution {
public:
//先处理无进位相乘 且相加的结果 最后再处理进位string solve(string s, string t) {int m=s.size(),n=t.size();reverse(s.begin(),s.end());reverse(t.begin(),t.end());vector<int> tmp(m+n-1);//无进位相乘相加for(int i=0;i<m;++i)for(int j=0;j<n;++j)tmp[i+j]+=(s[i]-'0')*(t[j]-'0');//处理进位信息string ret;ret.reserve(m+n);int c=0;//进位信息for(auto&e:tmp){c+=e;ret+=c%10+'0';c/=10;}if(c) ret+=c+'0';//处理前导零while(ret.size()>1&&ret.back()=='0') ret.pop_back();//至少要保留一个0reverse(ret.begin(),ret.end());return ret;}
};
