复试辅导

复试流程

周六上午报道,交一些表之类的东西,然后抽签确定面试顺序和机试位置

周六下午机试,时间是三个小时,大多数人都提前离场了

,电脑非常的垃圾,vs2010,连int main这种都得一个字一个字敲出来,没有自动补全,没有智能提示,没有代码片段,没有快捷键,甚至连复制粘贴都不行,只能在记事本里写好代码再复制到vs里

上机包括了30个选择题和2个编程题

选择题一上来就是人工智能的一些基础概念,反而准备的一些数据库跟软件工程的东西比较少,然后操作系统因为是408的缘故其实自己凭感觉能搞出来,但是也考了一个linux的安全模块啥的

我个人的感觉当时选择题有十几个拿不稳的都是2选1,当时一边做一边很崩溃,但是还是慢慢熬下来到编程题

编程题第一个一般是送分题,第二个就比较难,贪心算法呀,动态规划这些东西得熟练掌握,不仅仅是能看懂,要能够自己凭空手搓出来

面试的流程是这样的,先在一个大教室里面集合,然后等志愿者一个一个来叫到面试的教室里面

进去差不多有六个老师和一个教务老师,上来直接会让你坐下然后问:请介绍一下你的大学生涯,有什么亮点吗?这个时候就要把自己大学期间的经历总结一下,比如说参加过什么比赛,做过什么项目,实习过什么公司,这些都是可以说的,如果没有什么说的一定要编一点,把自己编成一个适合当牛马的人,其实这些东西都是在一张简历上面,也就是你去华科复试之前就需要交一张简历表,然后老师手上都有你的简历,所以你说的东西他们都是知道的,所以准备简历就变得非常重要了,你需要把自己大学期间的一些重要的事情写出来,学术和生活都要写一些,如果你实在没有什么竞赛经验,你就说大学里面跟某老师的硕博团队参加了一些计算机项目的开发,比如你学习到了什么技术,这里面就是面试老师会感兴趣的地方,当然不排除有些逆天老师就喜欢问你软件工程,我去年就有一个,我说了我本科是学数学的,然后他问我软件工程的架构设计,我根据复试资料随便回答了一点

我当时的自我介绍大概花了20分钟,基本上每个人都是20分钟

一、 完整机试真题：黑洞数（卡布列克常数 6174）】

题目描述： 给定任意一个各位数字不全相同的四位正整数。将该数字的四个数位重新排列，组成一个最大的数和一个最小的数，然后相减，得到一个新的四位数。 对新的数字重复上述操作，最多经过 7 次，最终一定会得到 6174，并且陷入 7641 - 1467 = 6174 的死循环。

输入格式： 一个四位正整数 N（保证各位数字不全相同。如有前导零也视作四位数，如输入 67，视为 0067）。

输出格式： 打印每次操作的过程，严格遵循格式：大数 - 小数 = 差值。 注意：如果输入就是 6174，也必须走一次流程，输出 7641 - 1467 = 6174。

---

【二、 实战破题思路：怎么写最稳？】

在机试的高压环境下，千万别用除法（/10）和取余（%10）去提取数字！一旦减出来的差值是三位数（比如 918），用数学方法极容易漏掉前导零，导致后续排序全部错乱。

最稳妥的策略是“字符串格式化”：

1. 强制补零：无论拿到什么数字，第一步先格式化为长度为 4 的字符串。不足 4 位就在前面补 0。
2. 字符排序：直接利用自带的排序函数，降序得到大数，升序得到小数。
3. 转回整数相减：把排好序的字符串转回整数，计算差值，然后进入下一轮。

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
    int n;
    
    // 模拟终端交互提示
    cout << "【华科软院机试模拟】" << endl;
    cout << "请输入一个不全相同的四位整数 (输入 Ctrl+C 或非数字退出): ";
    
    // 持续监听终端输入，方便你随机测试多个数字
    while (cin >> n) {
        int diff = n;
        cout << "------------------------" << endl;
        cout << "推导过程如下：" << endl;
        
        // 核心逻辑：do-while 保证至少执行并打印一次过程
        do {
            // 1. 转为字符串并强制补齐4位
            string s = to_string(diff);
            while (s.length() < 4) {
                s = "0" + s;
            }

            // 2. 构造大数和小数
            string max_str = s;
            string min_str = s;
            sort(max_str.begin(), max_str.end(), greater<char>()); // 降序
            sort(min_str.begin(), min_str.end());                  // 升序

            // 3. 转换回整数计算差值
            int max_val = stoi(max_str);
            int min_val = stoi(min_str);
            diff = max_val - min_val;

            // 4. 终端自动打印当前步骤的执行结果！
            cout << setfill('0') << setw(4) << max_val << " - "
                 << setfill('0') << setw(4) << min_val << " = "
                 << setfill('0') << setw(4) << diff << endl;

        } while (diff != 6174 && diff != 0); // 遇到 6174 或 0 (如输入1111) 时停止打印
        
        cout << "------------------------" << endl;
        cout << "\n请输入下一个测试数字: ";
    }
    
    return 0;
}

【华科软院机试模拟】  
请输入一个不全相同的四位整数 (输入 Ctrl+C 或非数字退出): 1234  
------------------------  
推导过程如下：  
4321 - 1234 = 3087  
8730 - 0378 = 8352  
8532 - 2358 = 6174  
------------------------  

请输入下一个测试数字: 67  
------------------------  
推导过程如下：  
7600 - 0067 = 7533  
7533 - 3357 = 4176  
7641 - 1467 = 6174  
------------------------

1. 题目核心逻辑：贪心策略

这道题的目标是通过消除 "ab" 和 "ba" 来赚取最高分。由于消除动作会改变剩余字符串的结构（例如从 aabbaa 中抽走中间的 ba，左右两边会拼合成新的 ab），所以消除的顺序决定了最终得分。

这里必须使用贪心策略（Greedy Algorithm）：

• 谁分高，先消谁。
• 假设 "ab" 得分比 "ba" 高，我们就应该不管三七二十一，先把字符串里所有的 "ab" 甚至因为消除而新生成的 "ab" 榨干。
• 等彻底没有 "ab" 可以消除时，我们再去剩下的残局里，寻找有没有 "ba" 可以捡漏。

因此，解题的大框架分为两步：第一轮遍历消除高分目标 → 截取剩余字符串 → 第二轮遍历消除低分目标。

---

2. 双指针解法：原地“吃掉”目标

在知道要分两轮消除后，最大的挑战是：如何高效地在字符串中进行消除和拼接？

如果直接用内置函数（如 erase）在原字符串上删减，后面的字符每次都要向前移动，时间复杂度会飙升到 O(n2)。这就是为什么要引入双指针法。

双指针法的精髓在于**“覆盖”**而不是“删除”。我们把原字符串当作一个空数组，用两个指针来重新书写它：

• 读指针 (read)： 像扫描仪一样，从左到右依次读取原字符串的每一个字符。
• 写指针 (write)： 像一支笔，记录当前“保留下来”的有效字符应该写在哪个位置。它同时也代表了当前有效字符串的长度。

双指针运作的三条规则：

1. 无脑写入： 每次 read 读到一个字符，就把它写到 write 所在的位置，然后 write 向前走一步（准备写下一个）。
2. 回头检查： 每次写完后，回头看一眼刚刚写下的最后两个字符，是否凑成了我们这轮要消除的目标（比如 "ab"）。
3. 触发消除（回退）： 如果凑成了目标，说明这两个字符不该保留。我们只需要把 write 指针往回退两步。这在逻辑上相当于把这两个字符“抹掉”了，下次再写入时，会直接覆盖它们。

---

3. 慢镜头回放：双指针实战推演

假设当前轮次我们要消除目标 "ab"。 原字符串为：s = "a b b a"。

初始状态：read = 0, write = 0。

步骤	读指针 read 动作	写指针 write 动作	当前底层字符串形态	逻辑说明
1	读取 s[0] (‘a’)	写入 ‘a’，write 进1，变为 1	a b b a	只有一个字符，无法凑成 “ab”，继续。
2	读取 s[1] (‘b’)	写入 ‘b’，write 进1，变为 2	a b b a	回头看：最后两个字符是 "ab"！触发消除，得分。write 回退2步，变为 0。
3	读取 s[2] (‘b’)	写入 ‘b’，write 进1，变为 1	b b b a	注意：此时写入的 ‘b’ 覆盖了原本位置上的 ‘a’。无法凑成 “ab”，继续。
4	读取 s[3] (‘a’)	写入 ‘a’，write 进1，变为 2	b a b a	最后两个字符是 "ba"。但本轮目标是 "ab"，所以不触发消除。

导出到 Google 表格

第一轮结束： 此时 write = 2。有效保留下来的字符串就是从下标 0 到下标 1 的部分，即 "ba"。 我们可以直接把原字符串截断到 write 的长度，拿着这个干净的 "ba"，去进入下一轮低分目标的消除。

---

4. 总结与优势

这种双指针技巧，本质上是用数组下标模拟了一个栈（Stack）的入栈和出栈操作：

• write 前进就是入栈。
• write 后退就是出栈。

它的绝对优势在于：

1. 极致的内存效率： 全程在原字符串上就地（In-place）修改，不需要开辟任何新的内存空间，空间复杂度为 O(1)。
2. 线性的速度： 每个字符只会被读指针读取一次，被写指针写入一次，时间复杂度为严格的 O(n)。