京东02-18 Java开发笔试

还是题刷少了，感觉自己只会暴力解T_T，有更好的思路希望大佬教教

第一题：数列：1,4,9,16,...,n^2;

输入正整数 1 <= r, l <= 10^5;

统计第r位 -> 第l位 '0'~'9'以及','各字符的个数。

先生成一个满足题意的字符串: s = i^2 + ","

然后遍历，没超时；

补充代码：

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int r = 0, l = 0;
        r = scan.nextInt();
        l = scan.nextInt();
        int[] count = new int[11];
        String s = new String();
        for (int i = 1; i < l; i++) {
            s = s + i * i + ",";
        }
        for (int i = r-1; i < l; i++) {
            switch (s.charAt(i))
            {
                case '0' :
                    count[0] ++;
                    break;
                case '1' :
                    count[1] ++;
                    break;
                case '2' :
                    count[2] ++;
                    break;
                case '3' :
                    count[3] ++;
                    break;
                case '4' :
                    count[4] ++;
                    break;
                case '5' :
                    count[5] ++;
                    break;
                case '6' :
                    count[6] ++;
                    break;
                case '7' :
                    count[7] ++;
                    break;
                case '8' :
                    count[8] ++;
                    break;
                case '9' :
                    count[9] ++;
                    break;
                case ',' :
                    count[10] ++;
                    break;
            }
        }
        System.out.println("'0':" + count[0]);
        System.out.println("'1':" + count[1]);
        System.out.println("'2':" + count[2]);
        System.out.println("'3':" + count[3]);
        System.out.println("'4':" + count[4]);
        System.out.println("'5':" + count[5]);
        System.out.println("'6':" + count[6]);
        System.out.println("'7':" + count[7]);
        System.out.println("'8':" + count[8]);
        System.out.println("'9':" + count[9]);
        System.out.println("',':" + count[10]);
    }

第二题：

小红定义一个数组的陡峭值为: 任意两个相邻元素的差的绝对值之和。例如: 数组[2,4,3,3]的陡峭值为|2-4|+|4-3|+|3-3|=3。小红希望你构造一个长度为n的数组，数组的每个元素都是不大于m的正整数，且数组的陡峭值为k。你能帮帮她吗?

输入描述:

三个正整数n,m,k，用空格隔开。

1 < n, m < 105

1 < k < 109

输出描述:

任意一个满足条件的数组。

输入:

5 3 4

输出：

1 2 1 2 1

第二题也是暴力解的：

初始化为 [1,1,1,1,1,...,1]；然后偶数项置m，直到陡峭值>=k，然后再往回遍历；

这样的时间复杂度是O(logn)，但感觉应该还能优化下，代码贴在评论区：

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = 0,m = 0,k = 0, sum = 0;
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        int[] num = new int[n];
        Arrays.fill(num,1);
        sum = (n-1)*(m-1);
        if (sum < k) System.out.println(-1);
        else {
            int i = 0;
            sum = 0;
            while (sum < k && i < n) {
                if(i % 2 == 1) {
                    num[i] = m;
                    sum = 2 * (m - 1) + sum;
                }
                i++;
            }
            if (k % 2 ==0) {
                while (sum != k) {
                    num[i - 1] = num[i - 1] - 1;
                    sum = sum - 2;
                    if (num[i - 1] == 1) i = i - 2;
                }
            }else {
                while (sum != k+1) {
                    num[i - 1] = num[i - 1] - 1;
                    sum = sum - 2;
                    if (num[i - 1] == 1) i = i - 2;
                }
                num[0] = num[0] + 1;
            }
//            //验算
//            sum = 0;
//            for (int j = 1; j < n; j++) {
//                sum += Math.abs(num[j]-num[j-1]);
//            }
//            System.out.println(sum);
            for (int j = 0; j < n; j++) {
                System.out.print(num[j] + " ");
            }
        }
    }

第三题明天再码