首页 > 8.16大疆笔试算法题
头像
JaneRoad
编辑于 2020-08-17 21:21
+ 关注

8.16大疆笔试算法题

题目:https://www.nowcoder.com/discuss/479244?type=0&order=3&pos=8&page=0&channel=666&source_id=discuss_center_0

第一题

求最短路径

核心思想:DFS 以及用二维数组接收数据

核心思想:DFS 以及用二维数组接收数据

启发:https://blog.csdn.net/seagal890/article/details/96048023

package com.ljn.test;
import java.util.Scanner;

public class Test4 {
//最短路径值
static int min = Integer.MAX_VALUE;
//二维数组记录路径值。如:1到2路径3 就是int[1][2]=3
static int[][] edge = new int[100][100];
//普通数组记录该点是否已走过 0-未经过 1-已经过
static int[] vertex = new int[100];
//n-站点数 ,m-路线数 ,endPoint-终点编号
static int n, m,endPoint;
static Scanner input = new Scanner(System.in);

public static void main(String[] args) {
    //输入的第一行第一个数字-站点数
    n = input.nextInt();
    //输入的第一行第二个数字-路线数
    m = input.nextInt();
    //外层循环-站点数
    for (int i = 0; i < n; i++) {
        //内层循环-线路数
        for (int j = 1; j <= m; j++) {
            //如果相等就相当于 1站点到1站点,无意义 置为0
            if (i == j) {
                edge[i][j] = 0;
            } else {
                //路径默认值设为最大值
                edge[i][j] = Integer.MAX_VALUE;
            }
        }
    }
    //根据线路数m 循环遍历 把路径值赋给初始化好的二维数组
    for (int i = 0; i < m; i++) {
        int a = input.nextInt();
        int b = input.nextInt();
        int c = input.nextInt();
        edge[a][b] = c;
    }
    //输入的最后一行是 要计算的终点站
    endPoint =  input.nextInt();
    dfs(0, 0);
    System.out.println(min);
}

/**
 * 
 * @param cur 当前站点
 * @param dis 目前走过的距离
 */
public static void dfs(int cur, int dis) {
    /**
     * 如果当前路径大于之前找到的最小值,可直接返回
     * */
    if (dis > min) {
        return;
    }
    /**
     * 判断是否达到终点,更新最小值,返回
     * */
    if(cur == endPoint) {
        if (dis < min) {
            min = dis;
            return;
        }
    }
    /**
     * 当前点到其他各点之间可连通但是还未添加进来时,遍历执行
     * */
    for (int i = 1; i <= n; i++) {
        if (edge[cur][i] != Integer.MAX_VALUE && vertex[i] == 0) {
            vertex[i] = 1;
            dfs(i, dis+edge[cur][i]);
            /**
             * 回溯
             **/
            vertex[i] = 0;
        }
    }
    return;
}

}

第二题
游戏王

背包问题

核心思想:动态规划
参考:https://blog.csdn.net/Lin_Willen/article/details/105052124

package com.ljn.test;
import java.util.Scanner;

public class Test5 {
public static void main(String[] args) {
    int numberGames,days;
    //每款游戏完成天数 数组
    int[] dayArr = new int[10];
    //每款游戏完成成就值 数组
    int[] honorArr = new int[10];
    Scanner scanner = new Scanner(System.in);
    //输入的第一行第一个数字-游戏数
    numberGames = scanner.nextInt();
    //输入的第一行第二个数字-总天数
    days = scanner.nextInt();
    //外层循环-根据游戏数量
    for (int i = 0; i < numberGames; i++) {
        //当前行的的第一个数字-游戏的成就值
        int a = scanner.nextInt();
        honorArr[i]=a;
        //当前行的的第二个数字-游戏所需完成时间
        int b = scanner.nextInt();
        dayArr[i]=b;
    }
    biggestHonor(dayArr,honorArr,days,numberGames);

}

/**
 *
 * @param w 每款游戏完成天数 数组
 * @param v 每款游戏完成成就值 数组
 * @param m 输入的第一行第二个数字-总天数
 * @param n 输入的第一行第一个数字-游戏数
 */
public static void biggestHonor(int[] w ,int [] v,int m,int n){
    int[][] val = new int[n+1][m+1];//表格中有一行一列为0,表示没有物品时价值为0,背包没有容量时价值为0
    int[][] path = new int[n+1][m+1];//记录背包装物品的记录
    //将val数组的第一行跟第一列置0
    for (int i = 0; i < val.length; i++) {
        val[i][0] = 0;//将列置0
    }
    for (int j = 0; j < val[0].length; j++) {
        val[0][j] = 0;//将行置0
    }

    for (int i = 1; i < val.length; i++) {
        for (int j = 1; j < val[0].length; j++) {
            if(w[i-1] > j){
                val[i][j]=val[i-1][j];
            }else{
                if(val[i-1][j] > v[i-1]+val[i-1][j-w[i-1]]){
                    val[i][j] = val[i-1][j];
                }else{
                    val[i][j] = v[i-1]+val[i-1][j-w[i-1]];
                    path[i][j] = 1;
                }
            }
        }
    }
    System.out.println(val[val.length-1][val[0].length-1]);
}
}

第三题
数学题
贪心算法、栈

package com.janeroad;

import java.util.LinkedList;

/**
 * Created on 2020/8/16.
 *
 * [@author] LJN
 */
public class Test28 {

    public static void main(String[] args)  {
        System.out.println(removeKdigits("71245323308", 4));
    }


    public static String removeKdigits(String num, int k) {
        LinkedList<Character> stack = new LinkedList<Character>();

        for(char digit : num.toCharArray()) {
            while(stack.size() > 0 && k > 0 && stack.peekLast() > digit) {
                stack.removeLast();
                k -= 1;
            }
            stack.addLast(digit);
        }

        /* remove the remaining digits from the tail. */
        for(int i=0; i<k; ++i) {
            stack.removeLast();
        }

        // build the final string, while removing the leading zeros.
        StringBuilder ret = new StringBuilder();
        boolean leadingZero = true;
        for(char digit: stack) {
            if(leadingZero && digit == '0') continue;
            leadingZero = false;
            ret.append(digit);
        }

        /* return the final string  */
        if (ret.length() == 0) return "0";
        return ret.toString();
    }

}

重点:第一次参加笔试,不懂oj输入输出等判题要求,平时刷题都是只要写出算法就行了,很少用Scanner都忘光了,所以痛定思痛多联系输入输出+写算法
牛客网在线判题系统使用帮助:https://www.nowcoder.com/discuss/276

代码写的不好,纯属输出用于日后复习,勿喷

全部评论

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

相关热帖

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

热门推荐