首页 > 网易笔试(9.13上午 有道算法工程师)
头像
谁能解忧,唯有代码
编辑于 2020-09-13 12:06
+ 关注

网易笔试(9.13上午 有道算法工程师)

四道编程题,三道100%,第四道没看
第一题:
#include <iostream>

using namespace std;

int main()
{
    string str;
    cin>>str;
    int n=str.size();

    int sum1=0;
    int sum2=0;
    for(int i=0;i<n;i++)
    {
        if(str[i]=='0')
            sum2+=1;
        else
            sum2+=2;
    }

    int result=sum1+sum2;
    for(int i=0;i<n;i++)
    {
        if(str[i]=='0')
            sum1+=2,sum2-=1;
        else
            sum1+=1,sum2-=2;
        result=max(result,sum1+sum2);
    }

    cout<<result<<endl;

    return 0;
}
第二道
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int main()
{
    vector<int> input;
    char ch=' ';
    while(ch!='\n')
    {
        int temp;
        cin>>temp;
        input.push_back(temp);
        scanf("%c",&ch);
    }
    int n=input.size();

    int result=0;
    for(int i=0;i<n;i++)
    {
        if(input[i]==1)
            continue;

        int left=0;
        int j;
        for(j=i-1;j>=0;j--)
        {
            if(input[j]==1)
                break;
            else
                left++;
        }
        if(j<0 || i==0)
            left=2000;

        int right=0;
        for(int j=i+1;j<n;j++)
        {
            if(input[j]==1)
                break;
            else
                right++;
        }
        if(j>=n || i==n-1)
            right=2000;

        result=max(result,min(left,right));

    }

    cout<<result+1<<endl;

    return 0;
}
第三道:迪杰特斯拉算法
#include <iostream>
#include <set>

using namespace std;

int main()
{
    int n,k,m;
    cin>>n>>k>>m;
    int **mat=new int*[n+1];
    for(int i=0;i<n+1;i++)
        mat[i]=new int[n+1];
    for(int i=0;i<n+1;i++)
        for(int j=0;j<n+1;j++)
            mat[i][j]=0;
    for(int i=0;i<m;i++)
    {
        int v,u,w;
        cin>>v>>u>>w;
        mat[v][u]=w;
    }

    int* cost=new int[n+1];
    for(int i=1;i<n+1;i++)
    {
        if(mat[k][i]==0)
            cost[i]=-1;
        else
            cost[i]=mat[k][i];
    }
    cost[k]=0;
    set<int> xv;
    for(int i=1;i<n+1;i++)
        xv.insert(i);
    xv.erase(k);

    while(1)
    {
        if(xv.size()==0)
            break;

        int index=-1;
        for(set<int>::iterator ite=xv.begin();ite!=xv.end();ite++)
        {
            if(cost[*ite]==-1)
                continue;
            if(index==-1)
            {
                index=*ite;
                continue;
            }
            if(cost[*ite]<cost[index])
                index=*ite;
        }
        if(index==-1)
            break;
        xv.erase(index);
        for(set<int>::iterator ite=xv.begin();ite!=xv.end();ite++)
        {
            if(mat[index][*ite]==0)
                continue;
            if(cost[*ite]==-1)
            {
                cost[*ite]=cost[index]+mat[index][*ite];
                continue;
            }
            if(cost[*ite]>cost[index]+mat[index][*ite])
                cost[*ite]=cost[index]+mat[index][*ite];
        }
    }

    int result=-1;
    for(int i=1;i<n+1;i++)
    {
        if(cost[i]==-1)
        {
            cout<<"-1"<<endl;
            return 0;
        }
        if(result==-1)
            result=cost[i];
        else
            result=max(result,cost[i]);
    }

    cout<<result<<endl;

    return 0;
}


全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐