8月19日：美团笔试第3 4 5题

第3题：01子串，二维 dp

三维 dp：dp[i][j][0] 表示 s.charAt(j) 变为 0 的操作次数，dp[i][j][1] 表示 s.charAt(j) 变为 1 的操作次数。画个图就知道了。

遍历 ij 时，j 的变换不依赖 i，因此存储可以优化为二维 dp[n][2]。

因为要遍历每个子串，因此，res += Math.min(dp[j][0], dp[j][1])

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String s = cin.next();
        int n = s.length();
        int[][] dp = new int[n][2]; // 优化前：dp[n][n][2]
        int res = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[j][0] = s.charAt(i) == '0' ? 0 : 1;
                    dp[j][1] = s.charAt(i) == '1' ? 0 : 1;
                } else {
                    dp[j][0] = s.charAt(j) == '0' ? dp[j - 1][1] : dp[j - 1][1] + 1;
                    dp[j][1] = s.charAt(j) == '1' ? dp[j - 1][0] : dp[j - 1][0] + 1;
                    res += Math.min(dp[j][0], dp[j][1]);
                }
            }
        }
        System.out.println(res);
    }
}

第4题：和相等的数组个数，二维 dp

回溯超时，但是可以作为验证，因此两种方案都给出。

二维 dp

dp[i][j]：下标为 [0, i] 的子数组 sub 中和为 j 的个数，k 表示子数组 sub 的下标 i 的值，依次遍历，注意剔除 nums[i] == k。

例如：nums = [1, 2, 4]。dp[1][5] = 表示下标为 [0, 1] 的子数组中和为 5 的个数，包括 [2, 3], [4, 1]。[1, 4] 和 [3, 2] 都不满足要求

注意，i == n - 1 时，只需计算最后一个值 dp[n - 1][sum]，即是最终答案。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = cin.nextInt();
            sum += nums[i];
        }

        int MOD = (int) 1e9 + 7;
        long[][] dp = new long[n][sum + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < sum; j++) {
                if (i == 0) {
                    if (nums[i] != j) {
                        dp[i][j] = 1;
                    }
                    continue;
                }
                if (i == n - 1) {
                    j = sum;
                }
                for (int k = 1; k <= j; k++) {
                    if (nums[i] == k) {
                        continue;
                    }
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                }
            }
        }
        // 打印 dp
//        for (int j = 1; j <= sum; j++) {
//            System.out.print(j + " ");
//        }
//        System.out.println();
//        for (int i = 0; i < n; i++) {
//            for (int j = 1; j <= sum; j++) {
//                System.out.print(dp[i][j] + " ");
//            }
//            System.out.println();
//        }
        System.out.println(dp[n - 1][sum]);
    }
}

回溯（超时，可打印具体数组验证）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {

    public static int MOD = (int) 1e9 + 7;
    public static int res = 0;
    public static List<List<Integer>> ans = new ArrayList<>();

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = cin.nextInt();
            sum += nums[i];
        }
        backtrack(new ArrayList<>(), nums, 0, sum, nums.length);
        System.out.println(ans);
        System.out.println(res);
    }

    public static void backtrack(List<Integer> list, int[] nums, int i, int rest, int n) {
        if (i == n || rest == 0) {
            if (i == n && rest == 0) {
                res = (res + 1) % MOD;
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        for (int num = 1; num <= rest; num++) {
            if (num == nums[i]) {
                continue;
            }
            list.add(num);
            backtrack(list, nums, i + 1, rest - num, n);
            list.remove(list.size() - 1);
        }
    }
}

第5题：讲真，有点东西

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int n;
    public static int[] nums;
    public static long sum;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        nums = new int[n];
        sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = cin.nextInt();
            sum += nums[i];
        }
        Arrays.sort(nums);

        long avg = sum / n;
        if (avg * n == sum) {
            long res = 0;
            for (int num : nums) {
                res += Math.abs(num - avg);
            }
            System.out.println(res >> 1);
        } else {
            System.out.println(Math.min(
                    Math.min(cal(true, true, sum - nums[n - 1]), cal(true, false, sum - nums[n - 1])),
                    Math.min(cal(false, true, sum - nums[0]), cal(false, false, sum - nums[0]))
            ));
        }
    }

    public static long cal(boolean isLeft, boolean isFloor, long sum) {
        double a = 1.0 * sum / (n - 1);
        long avg = (long) (isFloor ? Math.floor(a) : Math.ceil(a));
        long diff = Math.abs(sum - avg * (n - 1));
        long res = 0;

        if (isLeft) {
            nums[n - 2] -= isFloor ? diff : 0;
            nums[0] += isFloor ? 0 : diff;
            for (int i = 0; i < n - 1; i++) {
                res += Math.abs(nums[i] - avg);
            }
            nums[n - 2] += isFloor ? diff : 0;
            nums[0] -= isFloor ? 0 : diff;
        } else {
            nums[n - 1] -= isFloor ? diff : 0;
            nums[1] += isFloor ? 0 : diff;
            for (int i = 1; i < n; i++) {
                res += Math.abs(nums[i] - avg);
            }
            nums[n - 1] += isFloor ? diff : 0;
            nums[1] -= isFloor ? 0 : diff;
        }
        return diff + res / 2;
    }
}