拼多多 后端开发 2019.4.3笔试

第一题思路：
数组排序后，数组第i位和第n-1-i位配对，使得两两和趋于平均值。
代码：

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    int n = cin.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = cin.nextInt();
    }

    Arrays.sort(arr);

    int[] sum = new int[n/2];
    for (int i = 0; i < n / 2; i++) {
        sum[i] = arr[i] + arr[n - 1 - i];
    }

    Arrays.sort(sum);
    int min = sum[0];
    int max = sum[n/2 - 1];

    System.out.println(max - min);
}

第二题思路：
【参考 @TheGoneYou 思路，优先考虑0值，然后交叉分配最小待选值，优先给较短的数字】
代码：

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    int[] count = new int[10];
    for (int i = 0; i < 10; i++) {
        count[i] = cin.nextInt();
    }

    int aLen = cin.nextInt();
    int bLen = cin.nextInt();

    int longLen;
    int shortLen;

    if (aLen >= bLen) {
        longLen = aLen;
        shortLen = bLen;
    } else {
        longLen = bLen;
        shortLen = aLen;
    }

    StringBuilder shortNumber = new StringBuilder();
    StringBuilder longNumber = new StringBuilder();

    // 优先分配0
    if (count[0] >= shortLen) {
        // 0 * n = 0
        System.out.println(0);
        return;
    } else {
        shortLen -= count[0];
    }

    // 交叉分配AB
    while (shortLen > 0 && longLen > 0) {
        shortNumber.append(findMin(count));
        longNumber.append(findMin(count));
        shortLen--;
        longLen--;
    }

    while (shortLen > 0) {
        shortNumber.append(findMin(count));
        shortLen--;
    }

    while (longLen > 0) {
        longNumber.append(findMin(count));
        longLen--;
    }


    BigInteger bigLong = new BigInteger(longNumber.toString());
    BigInteger bigShort = new BigInteger(shortNumber.toString());

    BigInteger result = bigLong.multiply(bigShort);

    System.out.println(result);

}

private static int findMin(int[] count) {
    for (int i = 1; i < count.length; i++) {
        if (count[i] > 0) {
            count[i]--;
            return i;
        }
    }
    return -1;
}

第三题思路：
暴力穷举所有组合。
代码：

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    String sInput = cin.nextLine();
    int d = cin.nextInt();

    String[] sInput2 = sInput.substring(1, sInput.length() - 1).split(", ");
    int[] s = new int[sInput2.length];
    for (int i = 0; i < sInput2.length; i++) {
        s[i] = Integer.valueOf(sInput2[i]);
    }

    int sum = 0;
    int success = 0;
    for (int i = 0; i < s.length - 1; i++) {
        for (int j = i + 1; j < s.length; j++) {
            int cha = s[i] - s[j];
            if (cha < 0) {
                cha = -cha;
            }
            if (cha <= d) {
                success++;
            }
            sum++;
        }
    }

    System.out.println(String.format("%6f", ((double) success) / sum));
}

第四题思路：
动态规划问题，最短编辑距离，百度下有很多案例。
定义状态：dp[i][j]为长度i的A修改为长度为j的B所需最小步数。
状态转移方程：

dp[i][j] = dp[i-1][j-1] | (A[i-1] == B[i-1])
         = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1 | (A[i-1]!= B[i-1])

代码：

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    String word1 = cin.nextLine();
    String word2 = cin.nextLine();

    int len1 = word1.length();
    int len2 = word2.length();

    int[][] dp = new int[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }

    for (int i = 0; i <= len2; i++) {
        dp[0][i] = i;
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
            }
        }
    }

    System.out.println(dp[len1][len2]);
}