第一题

题目

某人只喜欢数字 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);
    }
}