新凯来笔试

微信用户_5412

9.29 新凯来笔试记
单机位，需要开摄像头，需要上传身份证，有屏幕监控限时2个小时，总分600分      
三道编程题，语言可选，acm模式，不能复制粘贴
第一题：200分，前缀和，完全通过
第二题：300分，单调栈，部分通过
第三题：100分，暴力的，完全通过

微信用户_5412

考试不是双机位，只需要使用电脑摄像头 + 共享屏幕，整体流程还是比较方便的，整场一共 3道代码大题，总分600分(100+200+300)
第一题主要是连通网络的最小成本问题，涉及图、连通性、成本优化思路。
第二题是数组的拼接问题。
第三题主要是最少任务时间问题，相比前两题综合性和难度都会更高一些，需要自己分析怎么优化

微信用户_5412

真题1：最长无重复子字符串的长度
题目描述：给定一个字符串（如"1230*5215494*5412163598"），求最长无重复数字的子字符串的长度。
难度：⭐⭐ 中等
答案：使用滑动窗口+哈希集合。维护窗口[left,right]，右指针扩展时检查字符是否已存在，若重复则左指针收缩。时间复杂度O(n)。关键代码：while right在集合中，移除left对应字符并left++，然后添加right对应字符并right++，更新最大长度。
📌 真题2：编辑距离
题目描述：给出两个字符串，每次操作可以替换、插入或删除一个字符，问经过几次操作后能把第二个字符串变为与第一个一致。
难度：⭐⭐⭐ 较难
答案：经典Levenshtein距离。定义dp[i][j]为str1前i个字符转为str2前j个字符的最少操作数。若当前字符相同则dp[i][j]=dp[i-1][j-1]，否则取替换、插入、删除三种操作中的较小值+1。时间O(mn)，空间可优化到O(min(m,n))。
📌 真题3：出现次数最少的字符的首个索引
题目描述：输入一个非空字符串，输出出现次数最少的字符的首个索引值。如果多个字符出现次数相同且最少，输出索引值最小的那个。
难度：⭐⭐ 中等
答案：先用哈希表统计每个字符的出现频率，找到最小频率值，然后从左到右遍历字符串，返回第一个频率等于最小频率的字符的索引。时间复杂度O(n)，空间O(k)。注意：是找"出现最少的字符"而非"不重复的字符"，两个概念容易混淆

微信用户_5412

新凯来秋招三道编程题解析
🔹T1字符串压缩
双指针遍历统计连续字符，拼接压缩结果。
压缩后的字符串如果更短则输出压缩版，否则输出原串。
🔹T2网格最小路径和
二维DP，只能向右向下走。
先初始化第一行、第一列；其余格子取上方、左边的最小值，叠加当前格子的值，右下角即为答案。
🔹T3括号多选模式匹配（压轴难题）
普通暴力DFS容易翻车，正确方案：NFA状态机 + DFS记忆化DP。
1. 栈预处理括号配对，分割括号内逗号分隔的各个候选选项。
​
2. 构造NFA，括号位置生成ε分支，支持多选试探。
​
3. 记忆化DFS同时走原串和自动机状态，普通字符直接比对；括号位置遍历全部候选分支。
​
4. 不仅要判断匹配与否，还要记录匹配片段，成功就给匹配片段套中括号；匹配失败输出Mismatch。