第一题乒乓球筐哈希表/计数 题目描述Nowcoder有两盒A、B乒乓球有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类并且每种球的数量不少于B盒中的数量。输入描述输入有多组数据。每组数据包含两个字符串A、B代表A盒与B盒中的乒乓球每个乒乓球用一个大写字母表示即相同类型的乒乓球为相同的大写字母。字符串长度不大于10000。输出描述每一组输入对应一行输出如果B盒中所有球的类型在A中都有并且每种球的数量都不大于A则输出“Yes”否则输出“No”。 解题思路这是一道典型的哈希表计数数组应用题。因为题目明确说明乒乓球种类由大写字母表示A-Z所以我们可以用一个长度为26的整型数组充当哈希表。遍历字符串A统计每种大写字母出现的次数。遍历字符串B每遇到一个字符就将哈希表中对应字母的计数减1。如果在减的过程中某个字母的计数小于0说明A盒中该类型的球数量少于B盒直接输出“No”并跳出。如果遍历完B都没有出现负数则输出“Yes”。 JAVA代码实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); while(in.hasNext()) { char[] s1 in.next().toCharArray(); char[] s2 in.next().toCharArray(); int[] hash new int[26]; // 统计A盒中每种球的个数 for(int i 0; i s1.length; i) { hash[s1[i] - A]; } boolean ans true; // 遍历B盒消耗A盒的数量 for(int i 0; i s2.length; i) { hash[s2[i] - A]--; if(hash[s2[i] - A] 0) { System.out.println(No); ans false; break; } } if(ans) System.out.println(Yes); } } }第二题组队竞赛排序 贪心 题目描述牛牛举办了一次编程比赛参加比赛的有 3∗n3∗n 个选手每个选手都有一个水平值 aiai​。现在要将这些选手进行组队一共组成n个队伍即每个队伍3人。牛牛发现队伍的水平值等于该队伍队员中第二高水平值。为了让比赛更有看点牛牛想安排队伍使所有队伍的水平值总和最大。输入描述输入的第一行为一个正整数n (1≤n≤1051≤n≤105)。第二行包括 3∗n3∗n 个整数 aiai​ (1≤ai≤1091≤ai​≤109)表示每个参赛选手的水平值。输出描述输出一个整数表示所有队伍的水平值总和最大值。 解题思路这是一道经典的贪心算法题。为了使所有队伍的“第二高水平值”之和最大我们需要合理分配每组的三个人。假设我们将数组从小到大排序。对于每个队伍如果要让第二大的值尽可能大我们应该选一个最小的值作为队伍的“拖油瓶”第一水平。选一个最大的值作为队伍的“天花板”第三水平。选一个尽可能大的值作为“第二水平”。具体策略将数组升序排序。从数组倒数第二个元素开始即最大的值不能被选为第二水平它只能作为每组的最大值被牺牲掉每次向前隔一个取一个值一共取n个。例如排序后[1, 2, 5, 5, 5, 8]。分组为[1, 5, 8]和[2, 5, 5]。第二水平值分别是5和5总和为10。代码实现上排序后定义指针pos 3*n - 2每次pos - 2累加n次即可。注意结果需要用long防止溢出。 JAVA代码实现import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int[] arr new int[n * 3]; for(int i 0; i n * 3; i) { arr[i] in.nextInt(); } Arrays.sort(arr); int pos n * 3 - 2, count 1; long ret 0; // 贪心累加每组的第二水平值 while(count n) { ret arr[pos]; pos - 2; } System.out.println(ret); } }第三题删除相邻数字的最大分数动态规划 题目描述给定一个长度为n的仅包含正整数的数组另外有一些操作每次操作你可以选择数组中的任意一个元素 aiai​同时数组中所有等于 ai−1ai​−1 和 ai1ai​1 的元素会被全部移除同时你可以得到 aiai​ 分直到所有的元素都被选择或者删除。请你计算最多能得到多少分。数据范围数组长度满足 1≤n≤1051≤n≤105数组中的元素大小都满足 1≤ai≤1041≤ai​≤104。 解题思路这道题是经典的动态规划问题类似于力扣上的“打家劫舍”或者“删除并获得点数”。虽然题目描述是“删除相邻数字”但我们可以转换思路由于元素值域在 1∼1041∼104我们可以开一个数组sum[]sum[x]表示原数组中所有值为x的元素之和。这样问题就转化为在1 ~ 10000这些数字中如果选择了数字i就能获得sum[i]的分数但数字i-1和i1就不能选了。定义状态f[i]表示选择数字i时能获得的最大分数。g[i]表示不选择数字i时能获得的最大分数。状态转移方程如果选了i那么i-1一定不能选所以f[i] g[i-1] sum[i]。如果不选i那么i-1选或不选都可以取最大值所以g[i] Math.max(f[i-1], g[i-1])。最终答案就是Math.max(f[N-1], g[N-1])。 JAVA代码实现import java.util.*; public class Main { static int N (int)1e4 10; static int[] sum new int[N]; // 记录每个数字的总和 static int[] f new int[N]; // 选当前数字的最大分数 static int[] g new int[N]; // 不选当前数字的最大分数 public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int x 0; // 预处理将相同数字的分数合并 for(int i 0; i n; i) { x in.nextInt(); sum[x] x; } // 动态规划过程 for(int i 1; i N; i) { f[i] g[i - 1] sum[i]; g[i] Math.max(f[i - 1], g[i - 1]); } System.out.println(Math.max(f[N - 1], g[N - 1])); } }