两个数字的交集⭐
两个数组的交集_牛客题霸_牛客网 (nowcoder.com)
题目描述:
解题思路:
通过遍历num1,如果遍历到的元素如果在num2中能找到,则这是num1和num2的公告元素;
这里需要借助两个数组来实现:
代码:
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int t=min(nums1.size(),nums2.size());vector<int>f;unordered_set<int>a;unordered_set<int>b(nums2.begin(),nums2.end());for(auto e:nums1){if(b.find(e)!=b.end()&&a.find(e)==a.end()){f.push_back(e);a.insert(e);}}return f;}
};
点击消除⭐⭐
点击消除_牛客题霸_牛客网 (nowcoder.com)
题目描述:
解题思路:(两种)
第一种:
采用压栈,出栈的方法:
入栈前要判断一下要入栈的元素和栈顶元素是否一样,一样则栈顶元素出栈,否则该元素入栈;
代码:
#include <iostream>
using namespace std;int main() {string s;cin>>s;string a;for(auto e:s){if(a.empty()){a.push_back(e);}else if(a.back()==e){a.pop_back();}else{a.push_back(e);}}if(a.empty())cout<<'0'<<endl;else cout<<a<<endl;
}
第二种:
用迭代器来写,题目要求消除相邻的两个一样的,那么就依次遍历如果遍历到的元素和下一个元素一样,则删除这两个元素,注意:如果现在指向元素的前一个存在的话要把他给--;
代码:
#include <iostream>
using namespace std;int main() {string s;cin>>s;string::iterator it=s.begin();while(it!=s.end()){if(*it==*(it+1)){it=s.erase(it,it+2);}else if(*(it-1)&&*it==*(it-1)){it=s.erase(it-1,it+1);}else{it++;}}if(s.empty())cout<<'0'<<endl;elsecout<<s<<endl;
}
最小花费爬楼梯⭐⭐
最小花费爬楼梯_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:
动态规划,到达第i个台阶的花费b[i]=min(b[i-1]+a[i-1],b[i-2]+a[i-2]);
代码:
#include <iostream>
using namespace std;int main() {int n;cin>>n;int a[n+1],b[n+1];for(int i=0;i<n;i++)cin>>a[i];b[0]=0,b[1]=0;for(int i=2;i<=n;i++){b[i]=min(b[i-1]+a[i-1],b[i-2]+a[i-2]);}cout<<b[n]<<endl;}
数组中两个字符串的最小距离⭐⭐
数组中两个字符串的最小距离_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:
模拟+贪心
代码:
#include <iostream>
#include<math.h>
using namespace std;int main() {int n;string str1, str2;cin >> n;cin>>str1>>str2;int pre1=-1,pre2=-1,ret=0X3f3f3f;string s;for(int i=0;i<n;i++){cin>>s;if(s==str1)pre1=i;else if(s==str2)pre2=i;if(pre1!=-1&&pre2!=-1){ret=min(ret,abs(pre1-pre2));}}if(pre1==-1||pre2==-1)cout<<"-1"<<endl;elsecout<<ret<<endl;}
简写单词⭐
简写单词_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:
本题比较简单,主要是注意一下ASCII的大小写字母的转换:
a->97
A->65
代码:
#include <iostream>
using namespace std;int main() {string s;string a;while(cin>>a){if('A'<=a[0]&&a[0]<='Z')s+=a[0];else{s+=a[0]-32;}}cout<<s<<endl;
}
dd爱框框⭐⭐⭐
dd爱框框 (nowcoder.com)
题目描述:
思路:
滑动窗口:
代码:
#include<iostream>
using namespace std;
int n,x;
int main(){cin>>n>>x;int a[n];for(int i=0;i<n;i++){cin>>a[i];}int ret=0X3f3f3f;int l=-1,r=-1;int ll=0,rr=0;int sum=0;while(rr<n){sum+=a[rr];while(sum>=x){if(ret>(rr-ll+1)){ret=rr-ll+1;r=rr;l=ll;}sum-=a[ll];ll++;}rr++;}cout<<l+1<<" "<<r+1<<endl;
}
除2!⭐⭐⭐
除2! (nowcoder.com)
题目描述:
思路:
用优先队列(大堆),在放入数据后自动排序,sum记录数组总和;每次操作,从头遍历,如果是偶数把这个数/2,更新sum,不是的话,直接pop(),因为我们已经用sum记录数据总和,pop()后不会影响sum;
注意数据大小(long long);
代码:
#include<iostream>
#include<queue>
using namespace std;
int n,k;
int main(){cin>>n>>k;priority_queue<long long >q;long long sum=0;for(int i=0;i<n;i++){int a;cin>>a;q.push(a);sum+=a;}while(k--){for(int i=0;i<q.size();i++){if(q.top()%2==0){int t=q.top()/2;q.pop();q.push(t);sum-=t;break;}else{q.pop();}}}cout<<sum<<endl;
}
主持人调度一⭐⭐⭐
主持人调度(一)_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:
本题主要就是二维数组的排序,sort可以直接排;
依[[33,38],[90,92],[87,88],[98,100],[20,32],[11,12],[45,57],[2,4],[63,71],[73,75],[95,96],[13,19]]样例为例;
排序后:
我们只需要判断每一行的第一个数是否大于上一行的第一个数;
如果都大于的话,则返回true;注意:这里要从第二行开始判断⭐
代码:
bool hostschedule(vector<vector<int> >& schedule) {sort(schedule.begin(),schedule.end());int t=schedule[0][1];for(int i=1;i<schedule.size();i++){if(schedule[i][0]<t){return false;}t=schedule[i][1];}return true;}
分割等和子集⭐⭐⭐⭐
分割等和子集_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:本质就是01背包问题:第i个数取还是不取;
代码:
#include <iostream>
#include<cstring>
using namespace std;
const int N=505,M=505*110/2;
int n;
int a[N];
bool f[N][M];
int main() {cin>>n;int sum=0;for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}if(sum%2!=0){cout<<"false"<<endl;}else{sum/=2;f[0][0]=true;for(int i=1;i<n;i++){for(int j=0;j<=sum;j++){if(j<a[i]){f[i][j]=f[i-1][j];}else{f[i][j]=f[i-1][j]||f[i-1][j-a[i]];}}if(f[i][sum]){cout<<"true"<<endl;return 0;}}}
}
小红的ABC⭐⭐
小红的ABC (nowcoder.com)
题目描述:
思路:
依次遍历:分别判断即可;
注意:reserve的使用;头文件:<algorithm>⭐
如:
string a;
reverse(a.begin(),a.end());
代码:
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;int main(){string s;cin>>s;int t=0X3f3f3f;for(int i=0;i<s.size();i++){string b;b+=s[i];for(int j=i+1;j<s.size();j++){b+=s[j];string c=b;reverse(b.begin(),b.end());// cout<<c<<" "<<b<<endl;if(c==b&&b.size()<t){t=b.size();break;}b=c;}}if(t==0X3f3f3f){cout<<"-1"<<endl;}else{ cout<<t<<endl;}
}
不相邻取数⭐⭐⭐
不相邻取数_牛客题霸_牛客网 (nowcoder.com)
题目描述:
思路:(打家劫舍dp)
对于不取的情况又要判断一下:第i-1的前一个是取还是不取------->可得dp方程;
代码:
#include <iostream>
using namespace std;int main() {int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}int f[n][2];f[0][0]=0;f[0][1]=a[0];for(int i=1;i<n;i++){f[i][1]=f[i-1][0]+a[i];f[i][0]=max(f[i-1][0],f[i-1][1]);}cout<<max(f[n-1][0],f[n-1][1]);}