首页 > 大疆后台工程师笔试 三个题全A,今天给我感谢信
头像
澹台棋晴
编辑于 2020-08-31 21:37
+ 关注

大疆后台工程师笔试 三个题全A,今天给我感谢信

三个题全A,今天给我感谢信 ,我是没想到的,很气!!!!
第一题:删除字符问题
#include "bits/stdc++.h"
using namespace std;
int main(){
    string str;
    int k;
    while(cin>>str){
        scanf("%d", &k);
        int n = str.length();
        for(int i = 0; i < k; i++){
            bool flag = false;
            n  = str.length();
            for(int j = 1; j < n; j++){
                char a = str[j -1];
                char b = str[j];
                if(a > b){
                    flag = true;
                    if(j == 1){
                        str = str.substr(j,n-j);

                    }
                    else{
                        str = str.substr(0,j-1) + str.substr(j,n-j);

                    }
                    break;
                }
                 if(j == n - 1 && ! flag){
                        str = str.substr(0,n-1);      
                }
            }

        }
        int index = 0;
        for(int i=0;i<str.length();i++){
            if(str[i] !='0'){
                index = i;
                break;
            }
        }
        str = str.substr(index,str.length() - index);// 去掉  0000013456这样的数字的。

        int zeoNm = 0;
        for(int i = 0;i < str.length(); i++){
            if(str[i] == '0'){
                zeoNm ++;
            }
        }//  判断是不是全都是0的数字,如果是那就输出0
        if(zeoNm == str.length()){
            cout<<"0\n";
        } else{
            cout<<str<<"\n";
        }
    }
    return 0;
}


第二题: 0 1 背包问题
#include<iostream>  
using namespace std;  
#define  V 1500  
unsigned int f[V];//全局变量,自动初始化为0  
unsigned int weight[10];  
unsigned int value[10];  
#define  max(x,y)   (x)>(y)?(x):(y)  
int main()  
{  
      
    int N,M;  
    cin>>N;//物品个数  
    cin>>M;//背包容量  
    for (int i=1;i<=N; i++)  
    {  
        cin>>weight[i]>>value[i];  
    }  
    for (int i=1; i<=N; i++)  
        for (int j=M; j>=1; j--)  
      //不是倒着   就会出现一个一个物品被装了多次的情况的
        {  
            if (weight[i]<=j)  
            {  
                f[j]=max(f[j],f[j-weight[i]]+value[i]);  
            }             
        }  
      
    cout<<f[M]<<endl;//输出最优解  
  
} 
第三题:迪杰斯特拉最短路径问题
#include "iostream"
#include "algorithm"
#include "bits/stdc++.h"
const  int inf = 1  << 30;
using  namespace  std;
int w[202][202];//权重数值的存储结果
bool vis[205]; //
int d[205];// 存储距离
using namespace  std;
int dij(int n, int from, int to){
    memset(vis, 0,sizeof(vis));//把 vis初始化为0;
    for(int i = 0 ;i < n; i++ ){
        d[i] = (i == from ? 0 : inf);//除了起点   其余设置成为无穷大的

    }
    for(int i = 0; i < n; i++){
        int x = inf;
        int minx = inf;
        for(int y = 0; y < n; y++){
            if(!vis[y] && d[y] <= minx){//没被访问过,并且小于最小的值
                minx = d[y];
                x = y;
            }
        }
        vis[x] = 1;//  x要被访问   设置成 1
        for(int y = 0; y < n; y++){
            d[y] = min(d[y], d[x] + w[x][y]);
        }
    }
    return d[to];

}
int main(){
    int n,p,x;
    //cout<<inf; //1073741824
    while(scanf("%d%d", &n, &p) != EOF){
        int from, to, weight;
        for(int i = 0;i < n; i++){
            for(int j = 0;j < n; j++){
                w[i][j] = inf;
            }
        }
        for(int i=0;i<p;i++){
            cin>>from>>to>>weight;
            if(weight< w[from][to] || weight < w[to][from]){
                w[from][to] = w[to][from] = weight;
            }
        }
        cin>>x;
        int ans = dij(n,0,x);
        cout<<ans<<endl;
    }
    return 0;
}





全部评论

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

推荐话题

相关热帖

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

热门推荐