首页 > 8-27京东笔试Java开发题解
头像
xust_Hangc
编辑于 2020-08-27 21:06
+ 关注

8-27京东笔试Java开发题解

给了2个小时时间。
30道选择题,2道编程题。
(上一篇帖子我删了 差点成了答案分享区🤣

编程题第一题:

题面

某人只喜欢数字 2, 3, 5这三个数字,如222,333,235这样的。但是12345这样就不是他喜欢的,因为包含了除了2,3,5以外的数字。
现询问这个人喜欢的第n个数字(升序排列的第n个数字)是多少。 n <= 1000;

思路

考虑1000的数据范围并不大。所以可以直接预处理前1000项。
可以以数字的位数作为枚举量,弄出所有的组合而成的数字。
如数字长度为1位时,有2,3,5,这3种情况。
数字长度为2时,有22,23,25,33,32,35,55,52,53。这9种情况。
考虑到这里,我们就不难想到,我们可以枚举第i位的数字,直到长度为预期值即可。
以长度为2举例,首位可能是2,3,5.第二位可能是2,3,5。所以直接深搜即可。

参考代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] vis = new int[100];
    public static void main(String[] args) {
        int[] arr = solve();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(arr[n - 1]);
    }
    public static int[] solve(){
        ArrayList<Integer> arr = new ArrayList<>();
        demo:
        for(int i = 1; arr.size() <= 1000; i++){
            dfs(0, i, arr);
        }
        int[] result = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++){
            result[i] = arr.get(i);
        }
        Arrays.sort(result);
        return result;
    }
    public static void dfs(int k, int n, ArrayList<Integer> arr){
        if(k == n){
            int val = 0;
            for(int i = 0; i < n; i++){
                val = val * 10 + vis[i];
            }
            arr.add(val);
            return ;
        }
        vis[k] = 2;
        dfs(k + 1, n, arr);
        vis[k] = 3;
        dfs(k + 1, n, arr);
        vis[k] = 5;
        dfs(k + 1, n, arr);
    }
}

代码中的vis数组为第k项数字所取的值,累加即可得到所组成的值。

第二题

题目:

给你一个二维数组,每次可以往左下,正下,右下走。 询问得到的最大值。
输入n, 代表n行, 每行2 * n - 1个元素。
示例如下图:


思路:

类似于经典的那个三角形之类的dp。
比较简单的做法就是在原数组上直接做;
我们考虑这个过程,第二行第二列这个元素,只能到达第三行1,2,3列这三个元素中的某一个。
所以我们可以倒推,若得到的最大值经过了第二行第二列这个元素,那么第三行取到的一定是max(arr[3][1],arr[3][2],arr[3][3]);
Ok,同理若取了arr[2][3]这个元素,且得到了最大值,那么,则第三行取的必是max(arr[3][2], arr[3][3], arr[3][4]);
。。。。。
都是这样,
对于第k行的每个元素,其整个链取最大时,则必取第k+1行的左下,下方,右下三个元素中的最大值。
即 arr[i][j] = arr[i][j] + max(arr[i + 1][j - 1], arr[i + 1][j], arr[i + 1][j + 1]);
从第n-1行开始转移,直到转移到arr[1][n]这个元素,那么arr[1][n]这个元素,就是整个链的最大值。

参考代码:
import java.util.Scanner;

public class Two {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] arr = new long[n + 1][2 * n];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= 2 * i - 1; j++){
                arr[i][n - i + j] = sc.nextLong();
            }
        }
        for(int i = n - 1; i >= 1; i--){
            for(int j = 1; j <= 2 * i - 1; j++){
                arr[i][n - i + j] += Math.max(Math.max(arr[i + 1][n - i + j - 1], arr[i + 1][n - i + j]), arr[i + 1][n - i + j + 1]);
            }
        }
        System.out.println(arr[1][n]);
    }
}

代码中的n - i, 为每列的前缀空个数。



全部评论

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

相关热帖

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

近期精华帖

热门推荐