- 题目链接：https://www.nowcoder.com/exam/company?currentTab=recommand&jobId=100&selectStatus=0&tagIds=179
2.小美的数组操作 #
考虑以下几点:
- 众数个数最多是多少？
sum%n==0?n:n-1
题目要求优先求众数个数最多的情况，然后再求其最小的操作数。分以下两种情况考虑，
- 当
sum%n==0时,也就是全部的n个数都能通过有限次变换变成平均值sum/n，那么众数最大个数就是n，此时只要求其操作次数即可; - 当
sum%n!=0时，此时我们需要选出一个数用来平衡其余n-1个数，使得其剩余的和是n-1的整数倍，基于贪心的局部最优策略我们能想到选择其中的最大值或最小值来充当这个角色
- 达到众数最多个数所需要的最少操作次数
对于第一种情况可以直接计算;
对于第二种情况，用v[n]数组存所有的数，maxx、minn分别表示最大值、最小值，sum表示所有元素的总和。
分别考虑去除最大值和最小值之后计算剩余n-1个数全部转换为平均值所需要的次数，以去除最大值为例，去除最大值maxx之后，由于可能不是整除所以我们考虑其余数k=(sum-maxx)%(n-1)，为了使得剩余n-1个数总和刚好是n-1的整数倍，我们可以选择将总和中余出的k删掉，此时平均值为ever=(sum-maxx)/(n-1);或者再补上一个n-1-k,此时平均值为p=(sum-maxx)/(n-1)+1。
- 怎么计算操作的次数？
实际上我们只需要知道平均值是多少就行了，然后遍历一遍v[n]数组，求其中所有大于平均值的数转换为平均数所需要减去数的总和就是我们要的操作次数（同样也可以计算小于平均数的数），代码中定义了函数solve(取大于平均数计算)，该函数的作用就是给定平均值ever，计算操作次数
注意：如果是减去k那么这个操作可以由solve的操作一并算出，如果是加上n-1-k那么就要将solve计算的操作次数加上n-1-k。根据你solve函数中选择计算的方式决定，如果是选择大于平均数的数来计算就按上面的规则，如果选择小于平均数的数来计算那么上面的加减情况则反过来
import java.util.*;
import java.lang.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
long[] a = new long[n];
long sum = 0;
long maxx = Integer.MIN_VALUE;
long minn = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
sum += a[i];
maxx = Math.max(maxx, a[i]);
minn = Math.min(minn, a[i]);
}
long ans = 0;
if (sum % n == 0) {
ans = solve(a, sum / n, -1);
} else {
long k = (sum - minn) % (n - 1);
ans = solve(a, (sum - minn) / (n - 1), minn);
ans = Math.min(ans, solve(a, (sum - minn) / (n - 1) + 1, minn) + n - 1 - k);
k = (sum - maxx) % (n - 1);
ans = Math.min(ans, solve(a, (sum - maxx) / (n - 1), maxx));
ans = Math.min(ans, solve(a, (sum - maxx) / (n - 1) + 1, maxx) + n - 1 - k);
}
System.out.println(ans);
}
}
public static long solve(long[] a, long ever, long num) {
int n = a.length;
long ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] == num) continue;
if (a[i] > ever) {
ans += (a[i] - ever);
}
}
return ans;
}
}
3.小美的01串翻转 #
首先按照题目意思写了一遍，超时
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String str = in.nextLine();
char[] s = str.toCharArray();
int n = s.length;
int ans = 0;
for (int i = 2; i <= n; i++) {
int temp = solve(s, i);
ans += temp;
}
System.out.print(ans);
}
public static int solve(char[] s, int len) {
int n = s.length;
int ans = 0;
for (int i = 0 ; i <= n - len; i++) {
int t0 = 0, t1 = 0;
int temp = 0;
for (int j = i; j < i + len; j++) {
if ((temp % 2 + '0') != s[j]) {
t0++;
}
if (((temp + 1) % 2 + '0') != s[j]) {
t1++;
}
temp = (temp + 1) % 2;
}
ans += Math.min(t0, t1);
}
return ans;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
int ret = 0;
for (int i = 0; i < str.length(); i++) {
int c0 = 0;
int c1 = 0;
for (int j = i; j < str.length(); j++) {
if ((str.charAt(j) == '0' && (j - i) % 2 == 0) || (str.charAt(j) == '1' && (j - i) % 2 == 1)) {
c0++;
} else {
c1++;
}
ret += Math.min(c0, c1);
}
}
System.out.println(ret);
scanner.close();
}
}
6.小美的数组构造 #
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int MOD = 1000000007;
int s = 0;
for (int num : a) {
s += num;
}
int[][] dp = new int[n + 1][s + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
for (int k = 1; k <= j; k++) {
if (k != a[i - 1]) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
}
}
}
}
System.out.println(dp[n][s]);
scanner.close();
}
}
7.美团商家注册系统 #
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
HashMap<String, String> info = new HashMap<>();
int length = in.nextInt();
in.nextLine();
for (int i = 0; i < length; i++) {
String[] line = in.nextLine().split(" ");
if (Character.isLowerCase(line[0].charAt(0))) {
if (!info.containsKey(line[0])) {
info.put(line[0], line[1] + " " + 0);
} else {
String[] values = info.get(line[0]).split(" ");
//System.out.print(values[0] + " " + line[1] + " ");
boolean flag = false;
for (int j = 0; j < values.length - 1; j++) {
if (values[j].equals(line[1])) {
flag = true;
break;
}
}
if (flag == false) {
int count = Integer.valueOf(values[values.length - 1]) + 1;
String str = "";
for (int k = 0; k < values.length - 1; k++) {
str += values[k] + " ";
}
info.put(line[0], str + line[1] + " " + count);
}
}
}
}
List<String> keys = new ArrayList<>(info.keySet());
// 对键列表按字典序升序排序
Collections.sort(keys);
// 遍历排序后的键列表，输出键值对
for (String key : keys) {
String value = info.get(key);
String[] values = info.get(key).split(" ");
System.out.println(key + " " + values[0] + " " + values[values.length - 1]);
}
}
}