携程笔试记录

1题交通拥塞路段。浮点数比较大小可能出现问题，最好转换成整数比较

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        // 窗口范围[k,n], 平均值最大，次之窗口最宽
        int[] preSum = new int[n + 1];
        for (int i = 1; i<= n; ++i) {
            preSum[i] = preSum[i-1] +  arr[i-1]; // preSum[i] = sum(arr[1..i))
        }
        long sum = 0;
        int st = 0, ed = 0; // avg = sum / (ed - st)
        for (int i = 0; i <= n - k; ++i) {
            for (int j = i + k; j <= n; ++j) {
                long tmpSum = preSum[j] - preSum[i];
                if (sum * (j - i) < tmpSum * (ed - st)  // sum/(ed-st) < tmpSum/(j-i)
                    || sum * (j - i) == tmpSum * (ed - st) && (j - i) > (ed - st)) {
                    sum = tmpSum;
                    ed = j;
                    st = i;
                }
            }
        }
        System.out.println(st + " " + (ed - 1));
    }
}

2题灯管的变化数。只能通过45%，哪里错了没有查出来。。快查自闭了。应该是超时了，时间复杂度写成了O(n^3)，其实可以优化成O(n^2)。我想着n比较小，最大100，三次方也就百万级别，1s内可以运行出来。携程使坏，卡了时间。下面分别是没优化和优化的代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int[][] changeCount = {
                {0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
                {4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
                {3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
                {3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
                {4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
                {3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
                {2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
                {3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
                {1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
                {2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
                {6, 2, 5, 5, 4, 5, 6, 3, 7, 6},
        };
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder cache = new StringBuilder();
        for (int d = 1; d <= s.length(); ++d) { // 宽度
            cache.append(work(s, d, changeCount)).append(" ");
        }
        if (cache.length() > 0) {
            cache.deleteCharAt(cache.length() - 1);
        }
        System.out.println(cache);
    }


    private static int work(String s, int d, int[][] changeCount) {
        int count = 0;
        for (int i = 0; i < d; ++i) {
            count += changeCount[10][s.charAt(i) - '0'];
        }
        for (int i = 0; i < s.length() - d; ++i) {  // 第i天 变化数
            for (int j = i + 1; j <= i + d; ++j) {
                count += changeCount[s.charAt(j-1) - '0'][s.charAt(j) - '0'];
            }
        }
        return count;
    }
}
/*
说明：
所有测试数据正确率为 45%！
可以尝试再次完善代码，并调试，争取全部AC通过

温馨提示：有时候，申请大的全局数组会导致超时，如果有此类情况，请检查您的全局数组是否超过题目要求的内存大小。
排除这个错误后，再检查别的情况引起的超时错误：例如死循环、循环结束条件错误等，或者需要更好的算法！
 */

打表代码

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        init();
        for (int i = 0; i < changeCount.length; ++i) {
            System.out.println(Arrays.toString(changeCount[i]));
        }
    }

    static int[][] ligths = new int[][]{
            // 0  1  2  3  4  5  6
            {1, 1, 1, 1, 1, 1, 0},  // 0
            {0, 0, 0, 0, 1, 1, 0},  // 1
            {1, 0, 1, 1, 0, 1, 1},  // 2
            {1, 0, 0, 1, 1, 1, 1},  // 3
            {0, 1, 0, 0, 1, 1, 1},  // 4
            {1, 1, 0, 1, 1, 0, 1},  // 5
            {1, 1, 1, 1, 1, 0, 1},  // 6
            {1, 0, 0, 0, 1, 1, 0},  // 7
            {1, 1, 1, 1, 1, 1, 1},  // 8
            {1, 1, 0, 1, 1, 1, 1},  // 9
    };

    static final int[][] changeCount = new int[11][10];;
    static void init() {
        for (int i = 0; i <= 9; ++i) {
            for (int j = i + 1; j <= 9; ++j) {
                changeCount[i][j] = changeCount[j][i] = calc(i, j);
            }
        }
        changeCount[10] = new int[]{6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    }
    private static int calc(int num1, int num2) {
        int count = 0;
        for (int i = 0; i < 7; ++i) {
            count += ligths[num1][i] ^ ligths[num2][i];
        }
        return count;
    }

}

优化后，时间复杂度O(n^2)。主要修改了代码中的work方法，将计算每次LED灯管变化数从O(n)，降到了平均O(1)。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int[][] changeCount = {
                {0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
                {4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
                {3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
                {3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
                {4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
                {3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
                {2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
                {3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
                {1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
                {2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
                {6, 2, 5, 5, 4, 5, 6, 3, 7, 6},
        };
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder cache = new StringBuilder();
        for (int d = 1; d <= s.length(); ++d) { // 宽度
            cache.append(work(s, d, changeCount)).append(" ");
        }
        if (cache.length() > 0) {
            cache.deleteCharAt(cache.length() - 1);
        }
        System.out.println(cache);
    }


    private static int work(String s, int d, int[][] changeCount) {
        int totalCount = 0;
        for (int i = 0; i < d; ++i) {
            totalCount += changeCount[10][s.charAt(i) - '0'];
        }
        if (d == s.length()) {
            return totalCount;
        }
        int count = 0;
        for (int j = 1; j <= d; ++j) {
            count += changeCount[s.charAt(j - 1) - '0'][s.charAt(j) - '0'];
        }
        totalCount += count;
        for (int j = 2; j < s.length() - d; ++j) {
            count += - changeCount[s.charAt(j-1) - '0'][s.charAt(j) - '0'] + changeCount[s.charAt(j+d-1) - '0'][s.charAt(j+d) - '0'];
            totalCount += count;
        }
        return totalCount;
    }
}

3 题时间复杂度得O(nlogn)，哎

#携程笔试##笔试题目##携程#