3月23日-游酷盛世-后端-26暑期实习笔试
📍笔试公司
游酷盛世科技（北京）有限公司
👜笔试岗位
后端开发工程师（平台）- 26暑期实习
📖笔试问题
题型
10个单选题，10个不单项选择题（错选0分，少选1/3分），3道算法题。限时好像是2小时还是1小时50分钟（没怎么注意😂），用的是牛客网的系统，双机位，手机摄像头也需开启，建议考前充满电或考试时插上充电器。
内容
一、选择题
有两三题线性代数的题，求矩阵的秩、特征值什么的。有一两题排序算法相关的，时空复杂度和排序稳定性之类的。有一两题数据库的，考的是索引失效和查询语句相关的。其他的记不太清了。
二、算法题
1. 小红的01串
这题在牛客网上找到了原题，链接：小红的01串。题目如下：
今天用DeepSeek做了下，测试了是正确的，用的是动态规划。代码如下：
import java.util.Scanner;
public class Main {
// 主函数：处理输入输出
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next(); // 读取输入的01字符串
System.out.println(minOperations(s)); // 输出转换为好串的最小操作次数
}
// 核心方法：计算将字符串转换为好串所需的最小操作次数
private static int minOperations(String s) {
int n = s.length();
// 若字符串长度不足3，无法形成非法子串，直接返回0
if (n < 3) {
return 0;
}
// 初始化动态规划状态数组：prevDp[a][b]表示处理完前两个字符后，前两个字符分别为a和b的最小操作次数
int[][] prevDp = new int[2][2];
for (int a = 0; a < 2; a++) { // 遍历第一个字符的可能值（0或1）
for (int b = 0; b < 2; b++) { // 遍历第二个字符的可能值（0或1）
// 计算将第一个字符改为a的代价：原字符等于a对应的字符则代价为0，否则为1
int costA = (s.charAt(0) == (a == 0 ? '0' : '1')) ? 0 : 1;
// 计算将第二个字符改为b的代价
int costB = (s.charAt(1) == (b == 0 ? '0' : '1')) ? 0 : 1;
prevDp[a][b] = costA + costB; // 记录前两个字符状态的总代价
}
}
// 从第三个字符开始逐字符处理（动态规划主循环）
for (int i = 2; i < n; i++) {
// currDp[b][c]：处理到当前字符时，前两个字符为b和c的最小操作次数
int[][] currDp = new int[2][2];
// 初始化currDp为不可达状态（无限大）
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
currDp[a][b] = Integer.MAX_VALUE;
}
}
char currentChar = s.charAt(i); // 当前处理的字符的原始值
// 遍历前两个字符的当前状态组合（a和b）
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
if (prevDp[a][b] == Integer.MAX_VALUE) {
continue; // 若之前状态无效，跳过（无法转移到新状态）
}
// 枚举当前字符的修改值c（0或1）
for (int c = 0; c < 2; c++) {
// 检查三元组（a,b,c）是否形成非法子串"010"或"101"
if ((a == 0 && b == 1 && c == 0) || (a == 1 && b == 0 && c == 1)) {
continue; // 若非法，跳过此状态
}
// 计算将当前字符改为c的代价（原字符等于目标字符时代价为0，否则为1）
int cost = (currentChar == (c == 0 ? '0' : '1')) ? 0 : 1;
// 当前总代价 = 累积的代价 + 当前字符修改的代价
int totalCost = prevDp[a][b] + cost;
// 如果新状态（b,c）的总代价更优，则更新currDp
if (totalCost < currDp[b][c]) {
currDp[b][c] = totalCost;
}
}
}
}
prevDp = currDp; // 状态转移：currDp成为下一轮的prevDp
}
// 遍历最终所有可能的状态，找出最小操作次数
int min = Integer.MAX_VALUE;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
if (prevDp[a][b] < min) {
min = prevDp[a][b];
}
}
}
return min; // 返回全局最小代价
}
}
2. 小红拼图
这题在牛客网上没找到原题（可能是删了😓），用AI找了下，结果通义的知识库里刚好有这题。题目大致如下：
让通义做了一下，它是暴力做的，代码如下（由于没有测试用例，正确性未知）：
import java.util.HashMap;
import java.util.Scanner;
public class Main {
private static final HashMap<Character, int[]> DIRECTIONS;
static {
DIRECTIONS = new HashMap<>();
// 定义每个字符的四个方向凸凹状态（上、右、下、左）
// 1表示凸，0表示凹
DIRECTIONS.put('W', new int[]{1, 1, 0, 1});
DIRECTIONS.put('D', new int[]{1, 1, 1, 0});
DIRECTIONS.put('S', new int[]{0, 1, 1, 1});
DIRECTIONS.put('A', new int[]{1, 0, 1, 1});
DIRECTIONS.put('*', new int[]{0, 0, 0, 0}); // 空格不参与判断
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int i = 0; i < t; i++) {
int n = in.nextInt();
int m = in.nextInt();
char[][] grid = new char[n][m];
for (int row = 0; row < n; row++) {
String line = in.next();
grid[row] = line.toCharArray();
}
System.out.println(isValid(grid, n, m) ? "Yes" : "No");
}
}
private static boolean isValid(char[][] grid, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char current = grid[i][j];
if (current == '*') continue;
// 检查右侧相邻
if (j + 1 < m) {
char right = grid[i][j + 1];
if (right != '*') {
// 当前格子的右边凸凹 vs 右侧格子的左边凸凹
int currentRight = DIRECTIONS.get(current)[1]; // 右边方向
int rightLeft = DIRECTIONS.get(right)[3]; // 左边方向
if (currentRight == rightLeft) return false;
}
}
// 检查下方相邻
if (i + 1 < n) {
char down = grid[i + 1][j];
if (down != '*') {
// 当前格子的下边凸凹 vs 下方格子的上边凸凹
int currentDown = DIRECTIONS.get(current)[2]; // 下边方向
int downUp = DIRECTIONS.get(down)[0]; // 上边方向
if (currentDown == downUp) return false;
}
}
}
}
return true;
}
}
3. 两点最小路径
这题没时间做了，大致看了下题目，应该是跟图相关的，求两点间的最小路径。不过个人感觉输入有点不好处理。
#笔试##软件开发笔面经#
投递太古地产等公司6个岗位 >
查看3道真题和解析