京东2021校园招聘笔试(8.27编程部分)——数据开发工程师(数列变换A了9%)

时间:2020-8-28 作者:admin


目录

一、滚球游戏

时间限制: 3000MS
内存限制: 589824KB

题目描述:
某滚球游戏规则如下:球从入口处(第一层)开始向下滚动,每次可向下滚动一层,直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个,每个方格都有一个得分,如下图所示。第1层有1个方格,第2层有3个方格,……,以此类推,第n层有2*n-1个方格。设计一个算法,使得球从入口滚至最下面一层的总得分和最大。

京东2021校园招聘笔试(8.27编程部分)——数据开发工程师(数列变换A了9%)

代码:DP

import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author: 张志浩 Zhang Zhihao
 * @Email: 3382885270@qq.com
 * @Date: 2020/8/27
 * @Time: 19:55
 * @Version: 1.0
 * @Description: Description
 */
public class First {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt();
        int col = 2 * row - 1;
        int[][] matrix = new int[row][col];
        int beginRow = 0;    //起始行
        int beginCol = row - 1;    //每行的起始列
        sc.nextLine();    //从下一行开始
        while (sc.hasNextLine()) {
            String[] line = sc.nextLine().split(" ");
            int c = beginCol;
            for (String num : line) {
                if (!("".equals(num))) {    //过滤空格
                    matrix[beginRow][c] = Integer.parseInt(num);
                    c++;
                }
            }
            beginRow++;
            beginCol--;
        }

        //从下往上加
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] != 0) {
                    matrix[i][j] += Math.max(matrix[i + 1][j - 1], Math.max(matrix[i + 1][j], matrix[i + 1][j + 1]));   //每个位置的元素为当前值+左下、下、右下的最大值
                }
            }
        }

        System.out.println(matrix[0][row - 1]); //结果为第一行的元素
    }
}

输入描述
第1行的正整数n表示数字三角形的层数。(n<=100)

接下来n行包含一个数字三角形,每一行包含2n-1个方格,对应有2n-1个表示得分的正整数(不超过10^5),每两个数字之间用空格隔开。

输出描述
球从入口(第一层)滚至最下面一层的最大得分和。

样例输入
3
1
2 1 2
3 4 2 1 3

样例输出
7

import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author: 张志浩 Zhang Zhihao
 * @Email: 3382885270@qq.com
 * @Date: 2020/8/27
 * @Time: 20:01
 * @Version: 1.0
 * @Description: Description
 */
public class First {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt();
        int col = 2 * row - 1;
        int[][] matrix = new int[row][col];
        int beginRow = 0;    //起始行
        int beginCol = row - 1;    //每行的起始列
        sc.nextLine();    //从下一行开始
        while (sc.hasNextLine()) {
            String[] line = sc.nextLine().split(" ");
            int c = beginCol;
            for (String num : line) {
                if (!("".equals(num))) {    //过滤空格
                    matrix[beginRow][c] = Integer.parseInt(num);
                    c++;
                }
            }
            beginRow++;
            beginCol--;
        }
        
        //从下往上加
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] != 0) {
                    matrix[i][j] += Math.max(matrix[i + 1][j - 1], Math.max(matrix[i + 1][j], matrix[i + 1][j + 1]));   //每个位置的元素为当前值+左下、下、右下的最大值
                }
            }
        }

        System.out.println(matrix[0][row - 1]); //结果为第一行的元素
    }
}

二、数列变换(调试了一个小时A了9%,盖了帽了 print(3 4)就是9%)

时间限制: 5000MS
内存限制: 655360KB

题目描述:
有一个初始长度为0的数列,现在对其实施以下三种操作:

(1) 插入某一个元素;

(2) 将某一个元素删除;

(3) 查询当前数列的状态(输出数列中每一个元素的值)。

输入描述
单组输入。
第1行一个正整数m表示一共有m个操作。
接下来m行表示m个操作,每行输入的第1个数字为op(操作类型)。
如果op=1表示第(1)种操作,后面接着两个数字a和b分别表示在第a个位置插入b(a以及a以后的数字将后移)。
如果op=2表示第(2)种操作,后面接着一个数字a,表示删除第a个数字。
如果op=3表示第(3)种操作,查询当前数列的状态。
(m<=1000,输入操作保证合法。)

输出描述
对于每一个op=3,输出当前数列的状态(输出数列中每一个元素的值)。

样例输入
3
1 1 3
1 2 4
3

样例输出
3 4

代码:常规

import java.util.LinkedList;
import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author: 张志浩 Zhang Zhihao
 * @Email: 3382885270@qq.com
 * @Date: 2020/8/27
 * @Time: 20:11
 * @Version: 1.0
 * @Description: Description
 */
public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
//        ArrayList<Integer> list = new ArrayList<Integer>();

        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                int index = sc.nextInt();
                int num = sc.nextInt();
                list.add(index - 1, num);
            } else if (op == 2) {
                int index = sc.nextInt();
                if (index <= list.size()) {
                    list.remove(index - 1);
                }
            } else if (op == 3) {
                for (int num : list) {
                    System.out.print(num + " ");
                }
            }
        }
        sc.close();
    }
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。