京东校园招聘算法题目

1.N（1<=N<=9）个小熊分一堆苹果，第一只小熊将苹果分成N份，多了一个，扔掉，然后拿走自己的那一份。第二只熊将剩余的苹果分成N份，又多了一个，扔掉，然后拿走自己的那一份，第三只.....，直到第N只熊；问最初的苹果有多少个？
2.6*6的矩阵，从左上方开始，只经过向下或向右的步骤，到达右下方，找出经过的位置的最大价值；
200,120,400,150,180,300
150,250,360,120,200,130
350,300,250,100,500,260
100,150,260,320,100,150
500,130,260,100,200,170
160,100,250,200,600,200

1、题目中给出的分苹果的过程可以总结为以下规律：

若最初有x个苹果，第一只小熊拿走了自己的那一份后，剩余的苹果数为 (x-1) * (N-1) / N，由于设定了剩余的苹果数必须是整数，所以 (x-1) * (N-1) 必须能整除 N。

同理，第二只小熊拿走了自己的那一份后，剩余的苹果数为 [(x-1) * (N-1) / N - 1] * (N-1) / N，必须满足这个数能整除 N。

以此类推，从第一只小熊到第 N 只小熊，对应的剩余的苹果数依次为：
(x-1) * (N-1) / N
[(x-1) * (N-1) / N - 1] * (N-1) / N
[(x-1) * (N-1) / N - 1] * (N-1) / N - 1] * (N-1) / N
...
...
[((x-1) * (N-1) / N - 1] * (N-1) / N - 1] * (N-1) / N - 1] * ... ] * (N-1) / N

我们可以看到，在依次计算剩余的苹果数时，每次都会减去一个 1，直到计算到最后一只小熊剩余的苹果数，此时会减去了 N-1 个 1。

所以，我们可以将以上的式子表示为：
x * (N-1) ^{(N-1) / N} (N-1)

最初的苹果数应该是满足该等式的最小正整数解。

下面给出求解最初苹果数的Java代码实现：

public class Main {
    public static void main(String[] args) {
        int N = 3; // N个小熊
        int x = 1; // 最初的苹果数，从1开始逐渐增加
        while (true) {
            int result = x;
            for (int i = 0; i < N-1; i++) {
                result = result * (N-1) / N;
                if (result % N != 1) {
                    break;
                }
                if (i == N-2) {
                    System.out.println("最初的苹果数为：" + x);
                    return;
                }
            }
            x++;
        }
    }
}

在上述代码中，我们使用了一个 while 循环来不断尝试不同的最初苹果数，直到找到满足等式的最小整数解位置。假设小熊的个数是 N，最多需要尝试 N-1 次，因为等式左边最大只可能是 0，右边最小是 1。在循环中，我们使用一个 for 循环来依次计算剩余的苹果数，一旦发现有一个剩余的苹果数不能整除 N，就用 break 跳出循环，并递增 x。如果在 for 循环中，计算到最后一个小熊拿走自己的那一份后，剩余的苹果数仍然能整除 N，就说明找到了满足等式的最小整数解，输出最初的苹果数并结束程序。

上述代码输出是 306。

2、这个问题可以使用动态规划的方法来解决。

首先，我们定义一个与给定矩阵相同大小的二维数组dp[][]，用于存储到达每个位置的最大价值。dp[i][j]表示到达矩阵中位置(i, j)时的最大价值。

我们可以根据题目要求，初始化dp[0][0]为矩阵左上角的元素值。

然后，我们可以根据动态规划的递推关系逐个计算出dp[][]中的其他值：

• 对于第一行（i = 0），由于只能向右走，所以dp[0][j] = dp[0][j-1] + matrix[0][j]，其中matrix表示给定的矩阵。
• 对于第一列（j = 0），由于只能向下走，所以dp[i][0] = dp[i-1][0] + matrix[i][0]。
• 对于其他位置，可以选择向右走或向下走，所以dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]。

最后，我们可以得到右下角位置的最大价值，即dp[5][5]。

下面是使用Java代码来实现上述思路的示例：

public class MaxValueMatrix {
    public static void main(String[] args) {
        int[][] matrix = {
            {200,120,400,150,180,300},
            {150,250,360,120,200,130},
            {350,300,250,100,500,260},
            {100,150,260,320,100,150},
            {500,130,260,100,200,170},
            {160,100,250,200,600,200}
        };

        int[][] dp = new int[6][6];
        dp[0][0] = matrix[0][0];

        // 初始化第一行
        for (int j = 1; j < 6; j++) {
            dp[0][j] = dp[0][j-1] + matrix[0][j];
        }

        // 初始化第一列
        for (int i = 1; i < 6; i++) {
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }

        // 计算其他位置的最大价值
        for (int i = 1; i < 6; i++) {
            for (int j = 1; j < 6; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
            }
        }

        // 输出最大价值
        System.out.println("最大价值：" + dp[5][5]);
    }
}

输出结果为：

最大价值：2440