金山办公的服务端开发工程师-25届春招笔试编程题
1.作弊
溪染：六王毕，四海一；蜀山兀，阿房出。覆压三百余里，隔离天日。骊山北构而西折，直走咸阳。二川溶溶，流入宫墙。五步一楼，十步一阁；廊腰缦回，檐牙高啄；各抱地势，钩心斗角……
叁秋：还在背《阿房宫赋》啊。
溪染：（停下背书）明天就要测试了，难道不背？
叁秋：什么？明天要测试？我现在抱佛脚还来得及嘛？
溪染：也就十来篇文言文而已。哦，你比较笨，那估计来不及了
叁秋：（沉默几秒）救救孩子吧！
溪染：我想想办法，我把文言文先换成拼音，然后在考场用动作语言传给你怎么样？
叁秋：什么动作语言？
溪染：我们先规定一个规则好了，我用‘点头’和‘摇头’向你传递信息。
叁秋：然后呢?
溪染：比如用‘点头-摇头’代表‘a’，用‘点头-点头’代表‘b’。
叁秋：我知道了！‘c’就用‘点头-点头-点头’表示
溪染：没救了，你是真的傻！如果这样，那我‘点头-点头-点头-点头-点头-点头’表示什么？
叁秋：‘bbb’可以，‘cc’也行！！
溪染：对的，这样的规则就有歧义了，所以我们定义的任意2个规则，一个规则都不能是另一个的前缀，更不能相同！
叁秋：那这还不简单！我‘a’用‘点头-摇头’表示，‘b’用‘点头-点头-摇头’表示，‘c’用‘点头-点头-点头-摇头’表示，以此类推！
溪染：用你这个规则，我脖子可能就不在了！
溪染：我们应该找到一个规则，让我‘点头’and‘摇头’的次数和最少，这样的话即可以快速传递信息，被监考老师发现的几率也小—些。
叁秋：那我们改怎么规定规则呢？
溪染：现在我们把文言文转为拼音先
（过了一会儿）
溪染：我们已经知道到时候我该给你传递的信息了，我们稍加计算一下，就可以找到最好的规则了
叁秋：那怎么计算呢?
溪染：我都为你付出这么多了，怎么找到最好的规则就靠你自己了
（又过了一会儿）
叁秋实在不知道怎么计算，于是找到了你
输入描述
一行字符串S，(1≤|S|≤5×10^6)，表示需要传达的信息，有可能是文言文拼音，S中仅包含小写英文字母。
输出描述
仅一行一个正整数表示问题的答案ans，表示传达信息所需最少的‘点头’and‘摇头’的次数之和。
示例1
输入
aaaaaa
输出
6
说明
‘a’用‘点头’代表即可
示例2
输入
abcabc
输出
10
说明
‘a’用‘点头’代表 ‘b’用‘摇头-点头’代表 ‘c’用‘摇头-摇头’代表
示例3
输入
havefuninthegame
输出
54
说明
解释那么长，这点地方够吗？
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();int[] freq = new int[26]; // 统计每个小写字母的频率// 计算每个字符的出现频率for (char c : s.toCharArray()) {freq[c - 'a']++;}// 收集所有非零频率List<Integer> frequencies = new ArrayList<>();for (int count : freq) {if (count > 0) {frequencies.add(count);}}// 特殊情况：只有一种字符if (frequencies.size() == 1) {System.out.println(frequencies.get(0));return;}// 使用优先队列（最小堆）构建哈夫曼树PriorityQueue<Integer> minHeap = new PriorityQueue<>(frequencies);int totalActions = 0;// 合并节点直到堆中只剩一个节点while (minHeap.size() > 1) {int first = minHeap.poll();int second = minHeap.poll();int sum = first + second;totalActions += sum;minHeap.add(sum);}System.out.println(totalActions);}
}2.牛牛的数组匹配
牛牛刚学会数组不久，他拿到两个数组a和b，询问b的哪一段连续子数组之和与数组a之和最接近。如果有多个子数组之和同样接近，输出起始点最靠左的数组。
输入描述
第一行输入两个正整数n和m，表示数组a和b的长度。第二第三行输入n个和m个正整数，表示数组中a和b的值。
输出描述
输出子数组之和最接近a的子数组。
示例1
输入
2 6
30 39
15 29 42 1 44 1
输出
29 42
示例 2
输入
6 1
50 47 24 19 46 47
2
输出
2
import java.util.*;public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取数组a和b的长度int n = scanner.nextInt();int m = scanner.nextInt();// 读取数组a并计算其总和int[] a = new int[n];int sumA = 0;for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();sumA += a[i];}// 读取数组b并计算前缀和int[] b = new int[m];for (int i = 0; i < m; i++) {b[i] = scanner.nextInt();}// 计算前缀和，prefixSum[0] = 0, prefixSum[1] = b[0], prefixSum[2] = b[0]+b[1], etc.long[] prefixSum = new long[m + 1];for (int i = 0; i < m; i++) {prefixSum[i + 1] = prefixSum[i] + b[i];}int bestStart = 0;int bestEnd = 0;long minDiff = Long.MAX_VALUE;// 遍历所有可能的起始位置for (int i = 0; i < m; i++) {// 目标值：sumA + prefixSum[i]long target = sumA + prefixSum[i];// 二分查找最接近目标值的结束位置int left = i + 1;int right = m;int j = i + 1; // 默认结束位置while (left <= right) {int mid = left + (right - left) / 2;if (prefixSum[mid] == target) {j = mid;break;} else if (prefixSum[mid] < target) {j = mid;left = mid + 1;} else {right = mid - 1;}}// 检查j和j+1两个位置，找到更接近目标值的int candidates[] = {j, j + 1};for (int k : candidates) {if (k > m) continue;long currentSum = prefixSum[k] - prefixSum[i];long currentDiff = Math.abs(currentSum - sumA);// 更新最佳子数组if (currentDiff < minDiff ||(currentDiff == minDiff && i < bestStart)) {minDiff = currentDiff;bestStart = i;bestEnd = k - 1; // 转换为数组b的索引}}}// 输出最佳子数组for (int i = bestStart; i <= bestEnd; i++) {System.out.print(b[i]);if (i < bestEnd) {System.out.print(" ");}}System.out.println();}
}3.牛牛的四叶玫瑰数
牛牛最近学了水仙花数，但是他并不喜欢水仙花，因此他准备算出[l,r]区间内的四叶玫瑰数。
四叶玫瑰数：一个数的四个位置的数字的四次方加起来等于这个四位数本身的数。
输入描述
第一行输入两个正整数l，r，表示闭区间的两头r<=10000
输出描述
输出区间内的四叶玫瑰数，保证至少有一个
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取区间范围int l = scanner.nextInt();int r = scanner.nextInt();scanner.close();// 遍历区间内的每个数，检查是否为四叶玫瑰数for (int num = l; num <= r; num++) {// 四叶玫瑰数一定是四位数if (num < 1000 || num > 9999) {continue;}// 分解数字的四个位int thousands = num / 1000;int hundreds = (num % 1000) / 100;int tens = (num % 100) / 10;int units = num % 10;// 计算四个位的四次方之和int sum = (int)(Math.pow(thousands, 4) + Math.pow(hundreds, 4) +Math.pow(tens, 4) + Math.pow(units, 4));// 检查是否等于原数if (sum == num) {System.out.println(num);}}}
}