携程笔试-0905

#软件开发笔面经#

第一题 贪心：
public static void Q1(int n, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i < k - 1) {
                sb.append(i + 1);
            } else {
                sb.append(n + k - i - 1);
            }
            if (i != n) {
                sb.append(&quot; &quot;);
            }
        }
        System.out.println(sb.toString());
}

第二题： 暴力超时，改成dp，记录以每个i为结尾的奇偶个字符串的奇偶次变化的数目
public static void Q2(int n, String str) {
        int rs = 0;
        int[][][] dp = new int[n][2][2];
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[i][1][1] = 0;
                dp[i][1][0] = 1;
                continue;
            }
            if (str.charAt(i) != str.charAt(i - 1)) {
                dp[i][1][1] = dp[i - 1][0][0];
                dp[i][1][0] = dp[i - 1][0][1] + 1;
                dp[i][0][1] = dp[i - 1][1][0];
                dp[i][0][0] = dp[i - 1][1][1];
            } else {
                dp[i][1][1] = dp[i - 1][0][1];
                dp[i][1][0] = dp[i - 1][0][0] + 1;
                dp[i][0][1] = dp[i - 1][1][1];
                dp[i][0][0] = dp[i - 1][1][0];
            }
        }
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == '1') {
                rs += dp[i][1][1];
            } else {
                rs += dp[i][1][0];
            }
        }
        System.out.println(rs);
    }

第三题：极限最后两分钟做完，一直在模拟各种情况，纯纯屎山，自己都看不懂了
public static long Q3(long m, long n, long k) {
        if (m == 1) {
            return n > k ? n - k : 0;
        }
        long rs = n * Q3(m - 1, n);
        String kStr = String.valueOf(k);
        if (kStr.length() < m) {
            return rs;
        }
        if (kStr.length() > m) {
            return 0;
        }

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            long count = 0;
            boolean con = true;
            for (int j = 0; j <= n; j++) {
                if (j == 0 &amp;&amp; i == 0) {
                    continue;
                }
                if (set.contains(j)) {
                    continue;
                }
                if (j >= (kStr.charAt(i) - '0')) {
                    set.add(j);
                    con = false;
                    if (j != (kStr.charAt(i) - '0')) {
                        rs -= count * Q3(m - i - 1, n - i);
                        return rs;
                    }
                    if(m == i + 1){
                        count++;
                    }
                    break;
                } else {
                    count++;
                }
            }
            rs -= count * Q3(m - i - 1, n - i);
            if(con){
                break;
            }
        }

        return rs;
    }

    public static long Q3(long m, long n) {
        if(m == 0){
            return 1;
        }
        long rs = 1;
        while (m > 0) {
            rs = rs * n;
            n--;
            m--;
        }
        return rs;
    }

第四题 贪心从最右边开始减：
public static long Q4(int n, int k, long sum, long[] a) {
        long rs = 0;
        long tmp = 0;
        for (int i = 0; i < k - 1; i++) {
            tmp += a[i];
        }
        for (int i = k - 1; i < n; i++) {
            if (i != k - 1) {
                tmp -= a[i - k];
            }
            tmp += a[i];
            int j = i;
            while (tmp > sum) {
                long minus = Math.min(a[j], tmp - sum);
                rs += minus;
                tmp -= minus;
                a[j] -= minus;
                j--;
            }
        }
        return rs;
    }