牛客题霸题解

题目:字符串距离计算

题解:

这个题暴力就好了,三层循环枚举哪个字符转换成哪个字符,然后将第一个串中的所有该字符替换,再比较两个串中不同的字符有多少个,每次更新最小值就好了。

代码:

class Solution {
public:
    /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        // write code here
        int ans=0x3f3f3f;
        for(int k=0;k<26;k++){
            for(int l=0;l<26;l++){
                int cnt=0;
                string s=S1;
                for(int i=0;i<s.size();i++){
                    if(s[i]-'a'==k) s[i]='a'+l;
                    if(s[i]!=S2[i]) cnt++;
                }
                ans=min(ans,cnt);
            }
        }
        return ans;
    }
};

题目:牛妹的蛋糕

题解:

因为每天吃掉剩余的1/3+1,到n天只剩1,所以倒推相当于前一天吃掉的是当天的(x+1)*3/2,公式推出来直接求解即可,不会爆long long。 。

代码:

class Solution {
public:
    /**
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的.
     * @return int整型
     */
    int cakeNumber(int n) {
        // write code here
        int ans=1;
        for(int i=1;i<n;i++){
            ans++;
            ans*=3;
            ans/=2;
        }
        return ans;
    }
};

题目: 最少素数拆分

题解:

如果本身就是素数的话,那么直接输出1就好了;
按照哥德巴赫的猜想:
如果这个数是偶数,那么输出2;
奇数的情况可以分成2+N-2,如果N-2是一个质数的话,那么输出2,否则输出3。

代码:

class Solution {
public:
    /**
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */

    int MinPrimeSum(int N) {
        // write code here
        int n=sqrt(N);
        int flag=1;
        for(int i=2;i<=n;i++){
            if(N%i==0){
                flag=0;
                break;
            }
        }
        if(flag) return 1;
        flag=1;
        for(int i=2;i<=n;i++){
            if((N-2)%i==0){
                flag=0;
                break;
            }
        }
        if(flag||N%2==0) return 2;
        return 3;
    }
};

题目: 神奇的数字

题解:

一开始看成了偶数位,,导致一直过不去样例...
就将偶数存起来,然后翻转偶数串,再遍历一遍原串,遇到偶数就将翻转后的位置的字符放上去。

代码:

class Solution {
public:
    /**
     * 
     * @param number string字符串 
     * @return string字符串
     */
    string change(string number) {
        // write code here
        string ans;
        for(int i=0;i<number.size();i++){
            if((number[i]-'0')%2==0) ans+=number[i];
        }
        reverse(ans.begin(),ans.end());
        int k=0;
        for(int i=0;i<number.size();i++){
            if((number[i]-'0')%2==0) number[i]=ans[k++];
        }
        return number;
    }
};

题目:远亲不如近邻

题解:

看数据范围n*m复杂度肯定是不行的,所以要用二分,变成mlogn就可以了。先给a数组排个序,因为二分得是有序的数组才行。然后二分第一个比他大的位置坐标和第一个比他小的位置坐标,取两个位置和x[i]差值的最小值,将每次的答案存入vector中。

代码:

class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        // write code here
        sort(a.begin(),a.end());
        vector<int>ans;
        for(int i=0;i<m;i++){
            int l=0,r=n-1;
            int res=n-1;
            while(l<=r){
                int mid=l+r>>1;
                if(a[mid]>=x[i]){
                    r=mid-1;
                    res=mid;
                }
                else l=mid+1;
            }
            int p=abs(a[res]-x[i]);
            l=0,r=n-1;
            res=0;
            while(l<=r){
                int mid=l+r>>1;
                if(a[mid]<=x[i]){
                    l=mid+1;
                    res=mid;
                }
                else r=mid-1;
            }
            p=min(p,abs(a[res]-x[i]));
            ans.push_back(p);
        }
        return ans;
    }
};
	

题目:  打字

题解:

用栈模拟就好了,每次遇到'<' 判断一下栈是否为空,不为空就栈顶出栈,如果字符不为'<'就往战力

代码:

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string Typing(string s) {
        // write code here
        stack<char>q;
        string ans;
        for(int i=0;i<s.size();i++){
            if(s[i]=='<') {if(!q.empty()) q.pop();}
            else q.push(s[i]);
        }
        while(!q.empty()){
            ans+=q.top();
            q.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

题目: 车站建造问题

题解:

如果本身就是素数或者1的话,那么答案+1;
按照哥德巴赫的猜想:
如果这个数是偶数,那么答案+2;
奇数的情况可以分成2+N-2,如果N-2是一个质数的话,那么答案+2,否则答案+3。
这不就是上边的素数分解题目!
最后答案要加一个车站,因为算的是区间的距离,比车站个数少一个。

代码:

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int MinPrimeSum(int N) {
        // write code here
        int n=sqrt(N);
        int flag=1;
        for(int i=2;i<=n;i++){
            if(N%i==0){
                flag=0;
                break;
            }
        }
        if(flag||N==1) return 1;
        flag=1;
        for(int i=2;i<=n;i++){
            if((N-2)%i==0){
                flag=0;
                break;
            }
        }
        if(flag||N%2==0) return 2;
        return 3;
    }
    
    int work(int n, int* a, int aLen) {
        // write code here
        int ans=n;
        for(int i=0;i<n-1;i++){
            int p=a[i+1]-a[i];
            ans+=MinPrimeSum(p);
            ans--;
        }
        return ans;
    }
};

题目: 牛妹的礼物

题解:

简单dp。
状态转移方程为dp[i][j]=min(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
如果dp从1开始的话就要初始化一下dp[0][i]和dp[i][0]为前缀和,当然从0开始的话只要判断边界能不能走就好了。

代码:

class Solution {
public:
    /**
     * 
     * @param presentVolumn int整型vector<vector<>> N*M的矩阵,每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    int dp[310][310];
    int selectPresent(vector<vector<int> >& presentVolumn) {
        // write code here
        int n=presentVolumn.size();
        int m=presentVolumn[0].size();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=0x3f3f3f;
            }
        }
        for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+presentVolumn[i-1][0];
        for(int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+presentVolumn[0][i-1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=min(dp[i][j],dp[i-1][j]+presentVolumn[i-1][j-1]);
                dp[i][j]=min(dp[i][j],dp[i][j-1]+presentVolumn[i-1][j-1]);
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+presentVolumn[i-1][j-1]);
            }
        }
        return dp[n][m];
    }
};

题目:牛牛算数

题解:

用从小到大排序的优先队列就可以快速的解决问题了。当优先队列的大小大于1时,就不断从中取出两个数,计算他们的和,再放入队列中,答案加上c*(x+y),直到队列大小为1,返回答案;

代码:

class Solution {
public:
    /**
     * 返回一个数字表示输出计算n个数字和的最小花费的时间。
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型vector ai表示第i个数的大小
     * @return long长整型
     */
    long long solve(int n, int c, vector<int>& a) {
        // write code here
        long long ans=0;
        priority_queue<long long,vector<long long>,greater<long long > >q;
        for(int i=0;i<n;i++) q.push((long long )a[i]);
        while(q.size()>1){
            long long x=q.top();
            q.pop();
            long long y=q.top();
            q.pop();
            ans+=c*(x+y);
            q.push(x+y);
        }
        return ans;
    }
};

题目: 分组

题解:

二分最大值就好了,二分判断的时候一直加数字直到大于等于最大值,组数+1,累计数值清零。如果最后组数大于k组,那么返回1,否则返回0。

代码:

class Solution {
public:
    /**
     * 分组
     * @param n int整型
     * @param k int整型
     * @param a int整型vector
     * @return int整型
     */

    bool check(int k,int n,vector<int>a)
    {
        int cnt=0;
        int p=0;
        for(int i=0;i<a.size();i++){
            p+=a[i];
            if(p>=k) p=0,cnt++;
        }
        return cnt>=n;
    }

    int solve(int n, int k, vector<int>& a) {
        // write code here
        int l=0,r=1e9;
        int ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid,k,a)){
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        return ans;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 13:54
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务