首页 > 8.27 京东笔试Java开发题解(附题目、思路、复杂度)
头像
NgCafai
编辑于 2020-08-28 11:41
+ 关注

8.27 京东笔试Java开发题解(附题目、思路、复杂度)

第一题

题目

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

例如 n 等于 5 时,答案为 23。
因为升序排序依次为 2,3,5,22,23。。。所以第5个数字为23.

思路

把这些数字组织成树的形式。
第一层:2,3,4
第二层:22,23,25,33,32,35,55,52,53
以此类推。
然后找第n个数属于哪一层,是这一层的第几个数。

时间复杂度 O(logn)
空间复杂度 O(1)

/**
 * @author WU Jiahui
 * @date 2020/08/27 18:49
 */
public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int level = 1; // 答案在第几层
        int pow = 3;
        int count = 3;
        while (count < n) {

            level++;
            pow *= 3;
            count += pow;
        }

        int countOfLevel = pow; // 当前层一共有几个数
        int targetOfLevel = level >= 2 ? (n - count + pow) : n; // 答案在当前层的第几个数

        int result = 0; // 答案

        // 在第几层,答案就有几位数
        for (int i = 0; i < level; i++) {
            result *= 10;
            if (targetOfLevel <= (countOfLevel / 3)) {
                result += 2;
            } else if (targetOfLevel <= 2 * (countOfLevel / 3)) {
                result += 3;
                targetOfLevel -= countOfLevel / 3;
            } else {
                result += 5;
                targetOfLevel -= 2 * (countOfLevel / 3);
            }
            countOfLevel /= 3;
        }
        System.out.println(result);
    }
}

第二题

题目

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

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

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

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

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

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

样例输出
7

思路

用动态规划,加空间压缩。

时间复杂度:O(n^2)
空间复杂度:O(n)

/**
 * @author WU Jiahui
 * @date 2020/08/27 20:04
 */
public class Main2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        scanner.nextLine();
        String s = scanner.nextLine().trim();
        // String[] arr = s.split("\\s");
        int[][] dp = new int[2][2 * n - 1];
        dp[0][n - 1] = Integer.parseInt(s);

        int cur = 0;
        int last;
        for (int i = 1; i < n; i++) {
            cur = i % 2;
            last = 1 - cur;

            s = scanner.nextLine().trim();
            String[] arr = s.split("\\s");
            int beginIndex = n - 1 - i;
            // 读当前行的数据
            for (int j = 0; j < arr.length; j++) {
                dp[cur][beginIndex++] = Integer.parseInt(arr[j]);
            }

            beginIndex = n - 1 - i;
            // 更新当前行的路径和
            dp[cur][beginIndex] += dp[last][beginIndex + 1];
            beginIndex ++;
            dp[cur][beginIndex] += Math.max(dp[last][beginIndex], dp[last][beginIndex + 1]);
            beginIndex++;

            for (int j = 2; j < (arr.length - 1); j++) {
                int lastMax = Math.max(dp[last][beginIndex - 1], dp[last][beginIndex]);
                lastMax = Math.max(lastMax, dp[last][beginIndex + 1]);
                dp[cur][beginIndex] += lastMax;
                beginIndex++;
            }

            dp[cur][beginIndex] += dp[last][beginIndex - 1];
        }

        int result = 0;
        for (int j = 0; j < dp[0].length; j++) {
            result = Math.max(result, dp[cur][j]);
        }
        System.out.println(result);
    }
}

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐