8.16大疆软件类B卷调查

第一题 最短路
第二题 玩游戏
第三题 数字游戏
别走错了
代码:
第一题:
标准的单源最短路径问题,用迪杰斯特拉就可以,但是比较抽象,用算法4 的写发:优先队列+松弛顶点,复杂度 VlogV + E
步骤:
1 用一个数组w保存所有顶点的权值,权值的含义是起点到当前顶点的距离,初始起始点权值0,其余顶点正无穷
2 弄一个优先队列,保存顶点,顶点权值越小越优先,然后把起始点加入队列
3 循环,每次从队列删除一个权值最小的顶点x,然后对于每条从x出发的边x-y,如果w[x] + w(x,y) < w[y]) ,则更新w[y] 和 把y加入队列,直到队列为空,结束循环
所以上述操作都是每次选择权值最小的,去更新w,所以说是松弛顶点,并且由于如果绕圈子肯定权值越绕越大,所以肯定不会绕圈子
第二题
01背包
第三题
贪心删除拐点,最后删除多余的0
import java.util.*;
public class Main {
    /**
     * @param
     * @return bool布尔型
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int k = in.nextInt();
        for(int i=0;i<k;i++){
            boolean b =false;
            for(int j =0;j<s.length()-1;j++){//拐点
                if(s.charAt(j) > s.charAt(j+1) ){
                    s = s.substring(0,j) + s.substring(j+1);
                    b = true;
                    break;
                }
            }
            if(!b){
                s = s.substring(0,s.length()-1);
            }

        }
        int g = -1;
        for(int i=0;i<s.length();i++){
            if (s.charAt(i)!='0'){
                g =i;
                break;
            }
        }
        s= g==-1 ? "0" : s.substring(g);
        System.out.println(s);


    }
}



#笔试题目##大疆#
全部评论
最短路a了吗  楼主 我是在是a不出来 就交卷了  能瞅瞅代码
1 回复 分享
发布于 2020-08-16 20:36
在线顿个最短路,自己写死活27%
1 回复 分享
发布于 2020-08-16 20:52
太菜了一题都没a
点赞 回复 分享
发布于 2020-08-16 20:32
嵌入式两道编程题都是动态规划,也是醉了
点赞 回复 分享
发布于 2020-08-16 20:33
交卷了,想康一下大佬们的代码
点赞 回复 分享
发布于 2020-08-16 20:42
ak了
点赞 回复 分享
发布于 2020-08-16 20:52
我一个前端太卑微了
点赞 回复 分享
发布于 2020-08-16 20:55
太难了
点赞 回复 分享
发布于 2020-08-16 20:56
一题没全a😅,第一题dfs不行么?
点赞 回复 分享
发布于 2020-08-16 21:03
用Floyd三行代码就可以A 73%😂😂
点赞 回复 分享
发布于 2020-08-16 21:06
第三题82%,不知道问题在哪🙄
点赞 回复 分享
发布于 2020-08-16 21:17
竟然全A,牛逼!
点赞 回复 分享
发布于 2020-08-17 10:27

相关推荐

评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务