笔试强训：Day4

一、*小易的升级之路（数学+模拟+cin处理多组输出）

小易的升级之路_牛客题霸_牛客网

#include <iostream>
using namespace std;
int n,a;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main() {
    int x;//负责接受防御力
    while(cin>>n>>a){
    while(n--){
        cin>>x;
        a+=(a>=x?x:gcd(a,x));
    }
    cout<<a<<endl;
    }
}
// 64 位输出请用 printf("%lld")

二、礼物的最大价值（路径dp/记忆化搜索）

礼物的最大价值_牛客题霸_牛客网

解法1：动态规划

class Solution {
public:
    int dp[201][201]={0};
    int maxValue(vector<vector<int> >& nums) {
        int m=nums.size(),n=nums[0].size();
        for(int i=1;i<=m;++i)
          for(int j=1;j<=n;++j)
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+nums[i-1][j-1];
        return dp[m][n];
    }
};

解法2：记忆化搜索

class Solution {
public:
    int m,n;
    int maxValue(vector<vector<int> >& nums) {
        m=nums.size(),n=nums[0].size();
        //dp[i][j]表示从i j位置选了之后的最大价值
       vector<vector<int>> memory(m,vector<int>(n));
       return dfs(nums,m-1,n-1,memory);//统计最大价值
    }
    int dfs(vector<vector<int> >& nums,int i,int j,vector<vector<int> >& memory){
        if(i==0&&j==0) return nums[0][0];//到达了起点
        if(memory[i][j]) return memory[i][j];
        if(i==0) return memory[0][j]=nums[0][j]+dfs(nums,0,j-1,memory);
        if(j==0) return memory[i][0]=nums[i][0]+dfs(nums,i-1,0,memory);
        return memory[i][j]=nums[i][j]+max(dfs(nums,i-1,j,memory),dfs(nums,i,j-1,memory));
    }
};

三、**对称之美（哈希）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
bool vis[110][26];//用来标记每一行 字母是否存在
int t,n;
string s;
bool check(int left,int right){
    for(int i=0;i<26;++i)
        if(vis[left][i]&&vis[right][i]) return true;
    return false;
}
int main(){
    cin>>t;
    while(t--){
        //先清空hash表
        memset(vis,0,sizeof vis);
        cin>>n;//知道了有多少个字符串
        for(int i=0;i<n;++i){
            cin>>s;
            for(auto&ch:s) vis[i][ch-'a']=true;
        }
        //双指针向中间靠
        int left=0,right=n-1;
        for(;left<right;++left,--right)
            if(!check(left,right)) break;
        cout<<(left<right?"No":"Yes")<<endl;
    }
}

四、*经此一役小红所向无敌（数学+模拟）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
typedef long long LL;
LL a,h,b,k;
int main(){
    cin>>a>>h>>b>>k;
    LL ret=0;//累计伤害
    //看看两个人能互砍多少回合
    LL n=min(h/b,k/a);
    ret+=n*(a+b);
    //计算剩余血量
    h-=b*n;
    k-=a*n;
    //看看是不是都活着 如果都活着就再砍一下
    if(h>0&&k>0){
        h-=b;
        k-=a;
        ret+=a+b;
    }
    //这时候至少死了一个  或者两个都死了
    if(h>0||k>0)  ret+=10*(h>0?a:b);
    cout<<ret<<endl;
}

五、连续子数组的最大和（线性dp）

连续子数组最大和_牛客题霸_牛客网

#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+10;
int nums[N],dp[N];
int n;
int main() {
   cin>>n;
   int ret=-101;
   for(int i=1;i<=n;++i) cin>>nums[i];
   for(int i=1;i<=n;++i){
     dp[i]=max(dp[i-1],0)+nums[i];
     ret=max(dp[i],ret);
   }
   cout<<ret<<endl;
}

六、非对称之美（贪心+规律）

登录—专业IT笔试面试备考平台_牛客网

情况1：所以字符都一样 return 0

情况2：整个串都是回文 return n-1

情况3：整个串不是回文 return n 

#include<iostream>
#include<string>
using namespace std;
string s;
int func(){
    int n=s.size();
    //首先要判断是否全都相同
    int i=1;
    for(;i<n;++i)
        if(s[i]!=s[0]) break;
    if(i==n) return 0;
    //接下来双指针往中间靠，判断整个字符串是否都是回文串
    int left=0,right=n-1;
    for(;left<right;++left,--right)
        if(s[left]!=s[right]) break;
    return left<right?n:n-1;
}
int main(){
    cin>>s;
    cout<<func()<<endl;
}

七、爱丽丝的人偶（贪心）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
int n;
int main(){
    cin>>n;
    //必须有单调性，所以就一高一矮 这样放
    int left=1,right=n;
    while(left<=right){
        cout<<left++<<" ";
        if(left<=right) cout<<right--<<" ";
    }
}

八、*集合（排序+归并/set去重）

集合_牛客题霸_牛客网

解法1：排序+归并

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
const int N=1e4+10;
int a[N],b[N];
int main() {
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<m;++i) cin>>b[i];
    sort(a,a+n);
    sort(b,b+m);
    //双指针归并 小的插入后++  
    int cur1=0,cur2=0;
    while(cur1<n&&cur2<m){
        if(a[cur1]<b[cur2]){
            cout<<a[cur1++]<<" ";
            while(a[cur1]==a[cur1-1]) ++cur1;
        } 
        else if(a[cur1]>b[cur2]){
            cout<<b[cur2++]<<" ";
            while(b[cur2]==a[cur2-1]) ++cur2;
        }
        else{
            cout<<a[cur1++]<<" ";
            ++cur2;
            while(a[cur1]==a[cur1-1]) ++cur1;
            while(b[cur2]==a[cur2-1]) ++cur2;
        }
    }
    //有一组还没走完
    while(cur1<n){
        if(cur1==0||a[cur1]!=a[cur1-1]) cout<<a[cur1]<<" ";
        ++cur1;
    }
     while(cur2<m){
        if(cur2==0||b[cur2]!=b[cur2-1]) cout<<b[cur2]<<" ";
        ++cur2;
    }
}
// 64 位输出请用 printf("%lld")

解法2：set

#include <iostream>
#include <set>
using namespace std;
int n,m;
set<int> s;
int main() {
    cin>>n>>m;
    int x;
    while(n--){
        cin>>x;
        s.insert(x);
    }
    while(m--){
        cin>>x;
        s.insert(x);
    }
    for(auto&e:s) cout<<e<<" ";
}
// 64 位输出请用 printf("%lld")

九、**最长回文子序列（区间dp）

最长回文子序列_牛客题霸_牛客网

#include <iostream>
using namespace std;
string s;
int dp[1010][1010];//[i,j]范围内最长回文子串的长度
int main() {
   cin>>s;
   int n=s.size();
   //当s[i]==s[j] dp[i][j]=dp[i+1][j-1]+2
   //当s[i]!=s[j] dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
   for(int i=n-1;i>=0;--i){
      dp[i][i]=1;
      for(int j=i+1;j<n;++j)
         if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
         else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
   }
   cout<<dp[0][n-1]<<endl;
}
// 64 位输出请用 printf("%lld")

十、*添加字符 (枚举)

添加字符_牛客笔试题_牛客网

#include <iostream>
#include <string>
using namespace std;
string a,b;
int main() {
  cin>>a>>b;
  int m=a.size(),n=b.size();
  //不相等的最多就是m个
  int ret=m;
  for(int i=0;i<=n-m;++i){//枚举b的起始位置
      int tmp=0;//统计不同位数的个数
      for(int j=0;j<m;++j)
        if(a[j]!=b[i+j]) ++tmp;
      ret=min(ret,tmp);
  }
  cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")

十一、**数组变换（贪心+位运算+数学）

数组变换__牛客网

#include <iostream>
using namespace std;
int a[51];
int n,maxval;
bool func(){
    for(int i=0;i<n;++i){
        if(maxval%a[i]) return false;
        int x=maxval/a[i];
        //if(x&(x-1)) return false;
        if(x-(x&-x)) return false;
    }
    return true;
}
int main() {
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
        maxval=max(maxval,a[i]);
    }
    cout<<(func()?"YES":"NO")<<endl;
}
// 64 位输出请用 printf("%lld")

十二、装箱问题（01背包）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
//dp[i][j]表示选前i个物品 容积不超过j  所占的最大容积
const int N=2e4+1;
int arr[31];
int dp[N];
int v,n;
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=1;i<=n;++i)
        for(int j=v;j>=arr[i];--j)
            dp[j]=max(dp[j],dp[j-arr[i]]+arr[i]);
    cout<<v-dp[v]<<endl;
}

十三、打怪（数学+模拟）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
int t,h,a,H,A;
int func(){
    //这种情况就是我攻击力比他血多 我就是无敌的
    if(a>=H) return -1;
    //如果我们杀死怪物 那么我一定比他多攻击一下 
    //所以我们可以先算一个怪物可以抗多少下攻击才死
    int m=(H/a)+(H%a?1:0);
    int x=(m-1)*A;//杀死一只玩家会掉多少血
    return h/x-(h%x?0:1);//如果可以整除的话 就得-1
}
int main(){
    cin>>t;
    //如果我的攻击力比对方的血多  那就无敌 
    while(t--){
        cin>>h>>a>>H>>A;
        cout<<func()<<endl;
    }
}

十四、字符串的分类（排序+哈希）

字符串分类_牛客笔试题_牛客网

#include <iostream>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;
int n;
string s;
int main() {
   cin>>n;
   unordered_set<string> hash;
   while(n--){
    cin>>s;
    sort(s.begin(),s.end());
    hash.insert(s);
   }
   cout<<hash.size()<<endl;
}
// 64 位输出请用 printf("%lld")

十五、**城市群数量（floodfill/并查集+lambda）

城市群数量_牛客题霸_牛客网

解法1：floodfill算法

class Solution {
public:
//联通块问题
bool vis[201]={0};//标记每个城市是否被搜索过
int n;
    int citys(vector<vector<int>>& nums) {
        n=nums.size();
        int ret=0;
        for(int i=0;i<n;++i)
          if(!vis[i]){
            ++ret;
            dfs(nums,i);//没被搜索过 就从该点开始找联通块
         }
        return ret;
    }
    void dfs(vector<vector<int>>& nums,int pos){
        vis[pos]=true;
        for(int i=0;i<n;++i)
           if(!vis[i]&&nums[pos][i]) dfs(nums,i);
    }
};

解法2：并查集+lambda

更多细节看：DS进阶：并查集_如何统计并查集中的数量-CSDN博客

循环的版本： 

class Solution {
public:
    int citys(vector<vector<int>>&nums) {
        //用并查集
        int n=nums.size();
        vector<int> ufs(n,-1);//初始状态
        auto Findroot=[&ufs](int x){
            while(ufs[x]>=0) x=ufs[x];
            return x;
        };
        for(int i=0;i<n;++i)
           for(int j=0;j<n;++j)
             if(i!=j&&nums[i][j]==1){//丢到并查集里
                 int root1=Findroot(i);
                 int root2=Findroot(j);
                 if(root1==root2) continue;
                 if(ufs[root1]>ufs[root2]) swap(root1,root2);
                 ufs[root1] += ufs[root2];
                 ufs[root2] = root1;
             }
        //统计一下城市群
        int ret=0;
        for(auto&e:ufs)
           if(e<0) ++ret;
        return ret;
    }
};

改进版本：让lambda函数可以递归调用，需要用到function封装

#include <functional>
class Solution {
public:
    int citys(vector<vector<int>>&nums) {
        //用并查集
        int n=nums.size();
        vector<int> ufs(n,-1);//初始状态
        function<int(int)> Findroot=[&](int x){
            if(ufs[x]<0) return x;
            return ufs[x]=Findroot(ufs[x]);
        };
        for(int i=0;i<n;++i)
           for(int j=0;j<n;++j)
             if(i!=j&&nums[i][j]==1){//丢到并查集里
                 int root1=Findroot(i);
                 int root2=Findroot(j);
                 if(root1==root2) continue;
                 if(ufs[root1]>ufs[root2]) swap(root1,root2);//统一让人少的服从人多的
                 ufs[root1] += ufs[root2];
                 ufs[root2] = root1;
             }
        //统计一下城市群
        int ret=0;
        for(auto&e:ufs)
           if(e<0) ++ret;
        return ret;
    }
};

改进版本：将lambda作为参数

class Solution {
public:
    int citys(vector<vector<int>>&nums) {
        //用并查集
        int n=nums.size();
        vector<int> ufs(n,-1);//初始状态
        auto Findroot=[&](auto&&Findroot,int x)->int{
            if(ufs[x]<0) return x;
            return ufs[x]=Findroot(Findroot,ufs[x]);
        };
        for(int i=0;i<n;++i)
           for(int j=0;j<n;++j)
             if(i!=j&&nums[i][j]==1){//丢到并查集里
                 int root1=Findroot(Findroot,i);
                 int root2=Findroot(Findroot,j);
                 if(root1==root2) continue;
                 //if(ufs[root1]>ufs[root2]) swap(root1,root2);
                 ufs[root1] += ufs[root2];
                 ufs[root2] = root1;
             }
        //统计一下城市群
        int ret=0;
        for(auto&e:ufs)
           if(e<0) ++ret;
        return ret;
    }
};

十六、判断是不是平衡二叉树（递归）

判断是不是平衡二叉树_牛客题霸_牛客网

利用返回值将树的高度带回，-1表示不是平衡二叉树

class Solution {
public:
    int IsBalanced(TreeNode* root){
        if(!root) return true;
        //递归计算左右子树的高度
        int left=IsBalanced(root->left);
        if(left==-1) return -1;//剪枝
        int right=IsBalanced(root->right);
        if(right==-1) return -1;//剪枝
        return abs(left-right)<=1?max(left,right)+1:-1;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        return IsBalanced(root)!=-1;
    }
};

利用引用将树的高度带回 

class Solution {
public:
    bool IsBalanced(TreeNode* root,int &depth){
        if(!root) return true;
        //递归计算左右子树的高度
        int left=0,right=0;
        //后序遍历
        if(IsBalanced(root->left,left)&&IsBalanced(root->right,right))
            if(abs(left-right)<=1){
                depth=1+max(left,right);
                return true;
            }
        return false;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        int depth=0;
        return IsBalanced(root,depth);
    }
};

十七、*最大子矩阵（二维前缀和dp预处理+枚举）

最大子矩阵_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=110;
int dp[N][N];
int n;
int main() {
    int x;
    cin>>n;
   //二维前缀和进行预处理
   for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j){
        cin>>x;
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+x;
     }
    //开始枚举找区间
    int ret=-127*N;
    for(int x1=1;x1<=n;++x1)
      for(int y1=1;y1<=n;++y1)
        for(int x2=x1;x2<=n;++x2)
          for(int y2=y1;y2<=n;++y2)
            ret=max(ret,dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
    cout<<ret<<endl;
}

十八、*小葱的01串（定长滑动窗口）

登录—专业IT笔试面试备考平台_牛客网

//滑动窗口 窗口内的0和1 是总数的一半  
#include<string>
#include<iostream>
using namespace std;
int n;
string s;
int main(){
    cin>>n>>s;
    //预处理 先统计一下所有的0和1总数
    int sum[2]={0};
    for(auto&ch:s) ++sum[ch-'0'];
    int ret=0;//统计方案总数
    int left=0,right=0,half=n/2;
    int count[2]={0};//统计窗口0 1的数量
    //定长滑动窗口  先走
    for(;right<half-1;++right) ++count[s[right]-'0'];
    //接下来走的话都要处理
    for(;right<n-1;++right,++left){
        ++count[s[right]-'0'];
        if(count[0]*2==sum[0]) ret+=2;
        --count[s[left]-'0'];
    }
    cout<<ret<<endl;
}