C/C++教程

2019字节跳动研发笔试题题解(C++)

本文主要是介绍2019字节跳动研发笔试题题解(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第一题:
用STL的string的 find 和 erase:

首先,通过find找到需要删除的字符/字符串的位置:

string str;
string target;
int pos = str.find(target);

然后通过erase进行删除:

n = target.size();
str = str.erase(pos,n);
第二题:
https://www.nowcoder.com/questionTerminal/c0803540c94848baac03096745b55b9b?toCommentId=3154435

#include<iostream>
using namespace std;
 
int main(){
    long long N,D;
    while(cin>>N>>D){
        long long res=0;
        long long *a=new long long[N];
        for(long long i=0,j=0;i<N;i++){
            cin>>a[i];
            while (i >= 2 && (a[i] - a[j]) > D) 
            {    
                j++;
            }
            res +=(i - j-1) * (i - j) / 2;
        }
        cout<<res%99997867;
        return 0;
         
    }
}

我当时做的时候纠结的就是如何才能做到不重不漏啊(梦回高中了属于是),我的算法本来想用双循环找一串符合条件的数来Cn3的,感觉重合了,一时间想不出怎么搞就跳了,这里的话相当于锁定了一个最大数,然后让其他数来进行组合,这样的话就可以实现

这里好像是有坑的,int 还会超限。。long都不行,必须得long long。。
第三题:
雀魂启动!
我写这题的时候一直在想如何判断胡,感觉好难顶,常用函数调用还不是太熟练,而且用的是dfs,不禁令人感叹。

核心代码:

bool isHu(vector<int> nums) {//其实是一个dfs的过程
    if (nums.empty())    return true;//递归出口
    int cnt = count(nums.begin(), nums.begin() + 4, nums[0]);//记录与首元素相同的数字的个数
    if (nums.size() % 3 != 0 && cnt >= 2) {//取雀头(只会取一次)
        if (isHu(vector<int>(nums.begin() + 2, nums.end())))   return true;
    }
    if (cnt >= 3) {//取刻子(三个相同的数字)
        if (isHu(vector<int>(nums.begin() + 3, nums.end())))    return true;
    }
    if (count(nums.begin(), nums.end(), nums[0] + 1) > 0 && count(nums.begin(), nums.end(), nums[0] + 2) > 0) {//取顺子
        int val = nums[0];
        nums.erase(nums.begin());//去掉一个首元素(顺子的第一个)
        nums.erase(find(nums.begin(), nums.end(), val + 1));//去掉一个首元素+1(顺子的第二个)
        nums.erase(find(nums.begin(), nums.end(), val + 2));//去掉一个首元素+2(顺子的第三个)
        if (isHu(nums)) return true;
    }
    return false;
}
 for (int i = 1; i <= 9; ++i) {//遍历下一张可能的牌
        if (count(nums.begin(), nums.end(), i) == 4)    continue;//最多就4张,真的不能再多了
        nums.insert(lower_bound(nums.begin(), nums.end(), i), i);//插入i,函数lower_bound()在first和last中的前闭后开区间,进行二分查找。返回从first开始的第一个大于或等于val的元素的地址。如果所有元素都小于val,则返回last的地址。注意:数组必须是排好序的数组。
        if (isHu(nums))     res.push_back(i);   //判断是否ok
        nums.erase(lower_bound(nums.begin(), nums.end(), i));//恢复原始nums数组
    }

第四题:
特征提取
https://www.nowcoder.com/questionTerminal/5afcf93c419a4aa793e9b325d01957e2?answerType=1&f=discussion

核心知识:map,pair
用双字典轮滚解决
用一个老字典和一个新字典,最后的时候把老的换成新的,新的变空等待输入,这种方法适用于过去数据要传递到未来的情况。(连续问题)

#include<bits/stdc++.h>

using namespace std;
int main(){
    int N,m;
    cin>>N;

    while(N--){

        cin>>m;
        int f,x,y;


        map<pair<int,int>,int> pre;//历史帧数
        map<pair<int,int>,int> now;//现在帧数

        int max_ = 0;

        for(int i =0; i< m;i++){
            cin>>f;

            for(int j =0; j< f;j++){
                cin>>x>>y;
                if(pre.count({x,y})){
                    now[{x,y}] = pre[{x,y}] + 1;//又出现了一次,就是老的加1
                }else{
                    now[{x,y}] = 1;//从来没有出现过
                }

                if(now[{x,y}]>max_){//时时更新任何一个连续帧
                    max_ = now[{x,y}];
                }
            }
            //如果这帧为0,那么就不会保留任何历史信息了,因为now在这轮没有任何内容。
            pre.clear();//清空历史,把now变为历史
            pre.swap(now);//now 置空,同时,now变成上一个,这样的话连续问题就可以解决


        }

        cout<<max_<<endl;


    }


    return 0;
}

// 查询关键字为key的元素的个数,在map里结果非0即1
size_t count( const Key& key ) const; //

第五题:
https://www.nowcoder.com/questionTerminal/3d1adf0f16474c90b27a9954b71d125d?answerType=1&f=discussion
第一篇题解,很详细。
他的代码没有注释,所以写一下基于注释的代码

// 代码
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<vector<int> > cost(n,vector<int>(n));//初始化
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> cost[i][j];//输入

    int all = 1<<(n-1);//位运算,取2个n-1次方
    vector<vector<int> > dp(n,vector<int>(all));//初始化
    for(int i=0;i<n;i++)
        dp[i][0] = cost[i][0];//因为题目要求返回原点
    for(int j=1;j<all;j++){
        for(int i=0;i<n;i++){
            dp[i][j] = INT_MAX;//取最大值防止。。
            if(((j>>(i-1))&1)==0){
                for(int k=1;k<n;k++){
                    if(((j>>(k-1))&1)==1){
                        dp[i][j] = min(dp[i][j],cost[i][k]+dp[k][j^(1<<(k-1))]);
                    }//带着循环看。就是取这几个的最小值。
                }
            }
        }
    }
    cout << dp[0][all-1] << endl;
}

第六题:
略。
第七题:
机器人跳跃问题
数学归纳法了属于是
在这里插入图片描述
方法一:
归纳:
在这里插入图片描述

#include<iostream>
#include<vector>
 #include<cmath>
 using namespace std;
 int main(){
 int N;
 int ans = 0;
 cin >> N;
 vector<int>D(N,0);
 for(int i = 0;i<N;i++)
 cin >>D[i];
 for(auto i in D){
 ans+=D[i]/pow(2,i);
 }
 cout<<ans<<endl;
 return 0;
 }

方法二,逆着解。

#include<iostream>
#include<vector>
 #include<cmath>
 using namespace std;
 int main(){
 int N;
 int ans = 0;
 cin >> N;
 vector<int>D(N,0);
 for(int i = 0;i<N;i++)
 cin >>D[i];
 for(int j=N-1;j>=0;j--){
 ans = ceil((D[j]+ans)/2.0);//注意c++中除法整数/整数为0,ceil向上取整要整数/float类型
 }
 cout<<ans<<endl;
 return 0;
 }

差不多就这样吧,焯!

这篇关于2019字节跳动研发笔试题题解(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!