拼多多 后端开发 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]);
}
#拼多多##笔试题目##题解##Java工程师#