OPPO后端笔试0313

20道单选+3道编程题

编程都是核心代码模式

第一题：给定六个数，求可以组成的最大的数；如[3,4] 最大数为43；

排序后遍历即可。

    public static int max(int[] num) {
        Arrays.sort(num);
        int sum = 0;
        for (int i = 0; i < num.length; i++) {
            sum += num[i] * Math.pow(10,i);
        }
        return sum;
    }

第二题：给定两个无序链表，合并成一个有序链表。

我是先合并再排序的。

第三题：去西藏玩，路旁给定景点数n，每次可以游玩1~2个景点，不可以回头，请问有多少种游玩方法

二维动态规划

public static long differentRoutes(int n){
        long routes = 0;
        long[][] states = new long[n/2 + 1][n+1];
        //初始化 第一行第一列均1
        for (int i = 0; i < n/2 + 1; i++) {
            states[i][0] = 1;
        }
        for (int j = 0; j < n + 1; j++) {
            states[0][j] = 1;
        }
        //routes[i,j]表示到达该点的方案数 = routes[i-1][j] + routes[i][j-1];
        for (int i = 1; i < n/2 + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                states[i][j] = states[i-1][j] + states[i][j-1];
                if(states[i][j] >= n) {
                    break;//后面就不用算了
                }
            }
        }
        int j = n;
        for (int i = 0; i < n/2 + 1; i++) {
            //倒着查比较快
            while (2*i + j != n) {
                j --;
            }
            routes += states[i][j];
        }
        return routes;
    }
}