【c++日常刷题】两个数字的交集、点击消除、最小花费爬楼梯
两个数字的交集⭐
两个数组的交集_牛客题霸_牛客网 (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;
else
cout<<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;
else
cout<<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]);
}