筆試強訓：Day2

一、字符串中找出連續最長的數字串(雙指針)

字符串中找出連續最長的數字串_牛客題霸_牛客網

#include <iostream>
#include <string>
#include <cctype>
using namespace std;int main() {//雙指針string str;cin>>str;int n=str.size();int begin=-1,len=0;for(int left=0;left<n;++left)if(isdigit(str[left])){//如果left是數字的話int right=left;while(right<n&&isdigit(str[right])) ++right;//走到這說明right在結尾的下一個位置if(right-left>len){begin=left;len=right-left;}left=right;//再++left 沒事 因為該位置一定不是數字 可以跳過}if(begin==-1) cout<<""<<endl;else cout<<str.substr(begin,len)<<endl;
}
// 64 位輸出請用 printf("%lld")

?二、島嶼數量（bfs/dfs）

島嶼數量_牛客題霸_牛客網

class Solution {
public:int m,n;int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};int solve(vector<vector<char>>& grid) {m=grid.size(),n=grid[0].size();int ret=0;for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(grid[i][j]=='1'){++ret;//說明找到了一個島嶼dfs(grid,i,j);}return ret;}void dfs(vector<vector<char>>& grid,int i,int j){grid[i][j]='0';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&&grid[x][y]=='1') dfs(grid,x,y);}}
};

三、**拼三角（優化枚舉）

登錄—專業IT筆試面試備考平臺_牛客網

#include<iostream>
#include<algorithm>//算法頭文件 記得會拼
//優化后的枚舉 只需要考慮4種情況
//012-345 023-145 034-125 045-123
int a[6];
using namespace std;
int main(){int t;cin>>t;while(t--){for(int i=0;i<6;++i) cin>>a[i];sort(a,a+6);//靜態數組的用法if(a[0]+a[1]>a[2]&&a[3]+a[4]>a[5]||a[0]+a[2]>a[3]&&a[1]+a[4]>a[5]||a[0]+a[3]>a[4]&&a[1]+a[2]>a[5]||a[0]+a[4]>a[5]&&a[1]+a[2]>a[3])  cout<<"Yes"<<endl;else cout<<"No"<<endl;}
}

四、**最小公倍數&最大公約數（數學）

求最小公倍數_牛客題霸_牛客網

#include <iostream>
using namespace std;
int gcd(int a,int b){//32%26=6  26%6=2  6%2=0 2%0if(b==0) return a;return gcd(b,a%b);
}
int main() {int a,b;cin>>a>>b;cout<<(a*b/gcd(a,b))<<endl;
}
// 64 位輸出請用 printf("%lld")

五、**數組中的最長連續子序列（排序+雙指針）

數組中的最長連續子序列_牛客題霸_牛客網

class Solution {
public:
//可以直接排序 但是要處理 值相等的情況 1 1 2 3 4 5 5 5 5 6        int MLS(vector<int>&nums) {int n=nums.size();sort(nums.begin(),nums.end());int ret=1;//雙指針 我可以先找到第一個比前面大1的那個數for(int left=0;left<n;){int right=left+1,count=1;//while(right<n){if(nums[right-1]+1==nums[right]){++count;++right;}else if(nums[right-1]==nums[right]) ++right;else break;}ret=max(ret,count);left=right;}return ret;}
};

?六、字母搜集（路徑dp）

字母收集_牛客題霸_牛客網

#include <iostream>
using namespace std;
const int N=501;
char nums[N][N];
int dp[N][N];
int main() {int m,n;cin>>n>>m;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>nums[i][j];for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){int t=0;if(nums[i][j]=='l') t=4;else if(nums[i][j]=='o') t=3;else if(nums[i][j]=='v') t=2;else if(nums[i][j]=='e') t=1;dp[i][j]=max(dp[i-1][j],dp[i][j-1])+t;}cout<<dp[n][m]<<endl;
}
// 64 位輸出請用 printf("%lld")

七、添加逗號（模擬）

添加逗號_牛客題霸_牛客網

#include <iostream>
using namespace std;int main() {string s;cin>>s;string ret;//統計最后結果int n=s.size();for(int i=0;i<n;++i){ret+=s[i];if((n-i-1)%3==0&&i!=n-1) ret+=',';}cout<<ret<<endl;
}
// 64 位輸出請用 printf("%lld")

八、跳臺階（線性dp）

跳臺階_牛客題霸_牛客網

#include <iostream>
using namespace std;int main() {int n;cin>>n;if(n<=2) cout<<n<<endl;else{int a=1,b=2,c; //dp[1]=1 dp[2]=2  dp[3]=dp[1]+dp[2];for(int i=3;i<=n;++i){c=a+b;a=b;b=c;}cout<<c<<endl;}
}

九、**撲克牌順子（排序/位圖+模擬）

撲克牌順子_牛客題霸_牛客網

解法1：排序+模擬?

class Solution {
public:bool IsContinuous(vector<int>& nums) {//要對數組排序 同時統計0的個數 若相鄰數字的空缺總數<=0的個數 那就是連續的sort(nums.begin(),nums.end());int zero=0;//統計0int i=0;while(nums[i]==0){++zero;++i;}int dis=0;//統計距離//記錄五張牌中最大值max到最小值min的距離for(;i<4;++i){if(nums[i]==nums[i+1]) return false;dis+=nums[i+1]-nums[i]-1;}if(zero>=dis) return true;return false;}
};

解法2：找規律+位圖?

class Solution {
public:bool IsContinuous(vector<int>& nums) {int flag=0;int _min=14,_max=0;for(auto&e:nums){if(e==0) continue;if(flag&(1<<e)) return false;//說明重復了flag|=(1<<e);//標記這張票出現過了_min=min(_min,e);//最小牌_max=max(_max,e);//最大牌}return _max-_min<5;}
};

十、**最長回文子串（動歸/馬拉松/中心擴展）

最長回文子串_牛客題霸_牛客網

class Solution {
public:
//中心擴展算法int getLongestPalindrome(string A) {int n=A.size();int ret=1;for(int i=1;i<n;++i){//當長度是奇數的時候int left=i-1,right=i+1;while(left>=0&&right<n&&A[left]==A[right]){--left;++right;}ret=max(ret,right-left-1);//當長度是偶數的時候left=i-1,right=i;while(left>=0&&right<n&&A[left]==A[right]){--left;++right;}ret=max(ret,right-left-1);}return ret;}
};

十一、買賣股票的最好時機1（貪心）

買賣股票的最好時機(一)_牛客題霸_牛客網

#include <iostream>
using namespace std;
const int N=1e5+1;
int a[N];
int main() {int n;cin>>n;for(int i=0;i<n;++i) cin>>a[i];int prevmin=a[0];//記錄前面的最小值int ret=0;//記錄最大利潤 有可能是逆序的 所以結果就是0for(int i=1;i<n;++i){ret=max(ret,a[i]-prevmin);prevmin=min(prevmin,a[i]);}cout<<ret<<endl;
}
// 64 位輸出請用 printf("%lld")

十二、**過河卒（路徑dp）

[NOIP2002 普及組] 過河卒_牛客題霸_牛客網

#include <iostream>
#include <cmath>
using namespace std;
long long dp[22][22];
int main() {int n,m,x,y;cin>>n>>m>>x>>y;x+=1,y+=1;//因為有虛擬節點dp[0][1]=1;for(int i=1;i<=n+1;++i)for(int j=1;j<=m+1;++j)if(i!=x&&j!=y&&abs(i-x)+abs(j-y)==3||i==x&&j==y) dp[i][j]=0;else dp[i][j]=dp[i-1][j]+dp[i][j-1];cout<<dp[n+1][m+1]<<endl;
}
// 64 位輸出請用 printf("%lld")

十三、**游游的水果大禮包（枚舉）

登錄—專業IT筆試面試備考平臺_牛客網

//一般來說枚舉有三種方法 
//1、選幾個就用幾個for循環  如果選超過3個以上的基本不適用
//2、用dfs把位置擺出來 然后嘗試去填
//3、根據某些特性優化枚舉  或者數量少的直接用if else
#include<iostream>
using namespace std;
int main(){long long n,m,a,b;cin>>n>>m>>a>>b;long long ret=0;//我們先嘗試枚舉1號for(int x=0;x<=min(n/2,m);++x){int y=min(n-x*2,(m-x)/2);ret=max(ret,a*x+b*y);}cout<<ret<<endl;
}

十四、**買賣股票的最好時機2（貪心/雙指針）

買賣股票的最好時機(二)_牛客題霸_牛客網

解法1：雙指針

#include <iostream>
using namespace std;
const int N=1e5+3;
int a[N];
int n;
int main() {cin>>n;int ret=0;for(int i=0;i<n;++i) cin>>a[i];for(int i=0;i<n;++i){int j=i;while(j+1<n&&a[j+1]>a[j]) ++j;//此時j正好在頂點ret+=a[j]-a[i];i=j;}cout<<ret<<endl;
}
// 64 位輸出請用 printf("%lld")

解法2：貪心：把交易拆成一天一天

#include <iostream>
using namespace std;
const int N=1e5+3;
int a[N];
int n;
int main() {cin>>n;int ret=0;for(int i=0;i<n;++i) cin>>a[i];for(int i=1;i<n;++i)if(a[i]>a[i-1]) ret+=a[i]-a[i-1];cout<<ret<<endl;
}
// 64 位輸出請用 printf("%lld")

十五、倒置字符串（雙指針）

倒置字符串_牛客題霸_牛客網

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int main() {string s;//先整體逆置 在局部逆置getline(cin,s);reverse(s.begin(),s.end());int n=s.size();for(int left=0;left<n;++left){int right=left;while(right<n&&s[right]!=' ') ++right;//開始逆置reverse(s.begin()+left,s.begin()+right);left=right;}cout<<s<<endl;
}
// 64 位輸出請用 printf("%lld")

十六、刪除公共字符（哈希）

刪除公共字符_牛客題霸_牛客網

#include <iostream>
using namespace std;
int main() {string s,t;getline(cin,s);getline(cin,t);bool hash[128]={0};for(char ch:t) hash[ch]=true;string ret;for(auto&ch:s) if(!hash[ch]) ret+=ch;cout<<ret<<endl;
}
// 64 位輸出請用 printf("%lld")

十七、**兩個鏈表的第一個公共結點（模擬）

兩個鏈表的第一個公共結點_牛客題霸_牛客網

解法1：計數然后讓長的先走然后再一起走

class Solution {public:ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {if (!pHead1 || !pHead2) return nullptr;if(pHead1==pHead2) return pHead1;ListNode*cur1=pHead1,*cur2=pHead2;int a=0,b=0;while(cur1){cur1=cur1->next;++a;}while(cur2){cur2=cur2->next;++b;}//長的先走count2-count1步cur1=pHead1,cur2=pHead2;int m=a>b?b:a;while(a-m){cur1=cur1->next;--a;}while(b-m){cur2=cur2->next;b--;}while(cur1!=cur2){cur1=cur1->next;cur2=cur2->next;}return cur1;}
};

解法2：等價關系（數學特性）?

class Solution {public:ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {if (!pHead1 || !pHead2) return nullptr;if(pHead1==pHead2) return pHead1;ListNode*cur1=pHead1,*cur2=pHead2;while(cur1!=cur2){cur1=cur1?cur1->next:pHead2;cur2=cur2?cur2->next:pHead1;}return cur1;}
};

解法3：借助set

class Solution {public:ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {if (!pHead1 || !pHead2) return nullptr;if(pHead1==pHead2) return pHead1;unordered_set<ListNode*> s;while(pHead1){s.insert(pHead1);pHead1=pHead1->next;}while(pHead2){if(s.count(pHead2)) return pHead2;pHead2=pHead2->next;}return nullptr;}
};

十八、**mari和shiny（狀態dp+優化）

登錄—專業IT筆試面試備考平臺_牛客網

#include<iostream>
#include<string>
using namespace std;
int main(){int n;string str;cin>>n>>str;long long s=0,h=0,y=0;for(int i=0;i<n;++i){char ch=str[i];if(ch=='s')++s;else if(ch=='h')h+=s;else if(ch=='y')y+=h;}cout<<y<<endl;
}