时间过的很快，怎么就第七周了，忙不过来了。这周课堂限时作业被薄纱，很绝望。

实验课

week7-3-2 航班

题目描述

在未来的太空殖民地里，有 m 条星际航线，n 名乘客正准备登上穿梭飞船。 每位乘客都属于某一条固定的航线（相当于他们的“所属星区”）。

现在航站的登机口形成了一条队列，系统支持以下两种操作：

​push x​：乘客 x 到达登机口。

• 如果此时队列中已经有他所属航线的其他乘客，那么 x 会自动排在​该航线最后一位乘客的后面​； 否则，x 会直接站在​队列的末尾​。

​pop​：开始登机！

• 队列最前面的乘客登机离开，并输出他的编号。登机顺序与普通队列相同——先来的先走。

输入格式

• 第一行包含两个整数 n 和 ​m​，分别表示乘客数量和航线数量。

  （乘客编号为 0 ~ n-1，航线编号为 0 ~ m-1）

• 第二行包含 n 个整数 ​$A₀, A₁, …, Aₙ₋₁$​，其中 $Aᵢ$ 表示乘客 i 所属的航线编号。

• 第三行包含一个整数 ​T​，表示操作次数。

• 接下来 T 行，每行一个操作，形式为 push x 或 pop。

输出格式

对于每一个 pop 操作，输出一行，表示登机的乘客编号。

解答

这题目真的有意思，告诉了你航线个数，看似跟答案毫无关联，实际上是在给你提示。

本来是想开个双端队列强行模拟的，但是这样写起来效率极低，运行效率也很差。奈何我水平实在不够，考试时就往死里手搓，最终连编译都基本过不了（老实提示异常我也不知道怎么办）。哦对，考试时我还读错题意了，以为输入的是前面要push的乘客，原来那是后面要push的乘客的航班号。。。

思考一下不难发现，最后整个队列的长相就是所有相同航班都挨在一块儿，所以只需要记录队列顺序即可。原来这题这么简单，考试时脑子真是不好使。。。

思路如下：$_{默认using \space namespace \space std}$

由于告诉了你航线个数，干脆每个航线开一个队列，所以我们有vector<queue<int>> teamQueues(m + 1)。再创建一个队列用来记录队列里航线出现的顺序，queue<int> teamOrder，存放的时对应队列在teamQueues里对应的下标。

假设我们已经将输入读到teamOf数组里了，先实现void pushPassenger(int x)。学习一下Modern CPP写法。

auto pushPassenger = [&](int x) {
    int t = teamOf[x];
    if (teamQueues[t].empty()) {
        teamOrder.push(teamQueues[t]);
    }
    teamQueues[t].push(x);
}

然后是popPassenger()

auto popPassenger = [&]() {
    int t = teamOrder.front(); //队首的队
    int x = teamQueues[t].front(); // 队首的乘客，要被弹出，先记录待会返回。
    teamQueues[t].pop_front();
    if (teamQueues[t].empty()) {
        teamOrder.pop(); //这个航班的队列空了，丢掉。
    }
    return x;
}

剩下的操作就是过家家了。我也不知道为什么考试会在那死磕手搓带hash的双端队列，可能下次开始做题前还需多加思考，而非直接开敲。

力扣

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。）

解答

依旧是利用字符集有限的性质，我们记录s和p中所有字符出现的个数。其实不难发现，只要同样长度字串中字符个数对应的上，那么那个字串就是异位词。

int sLen = s.size(), pLen = p.size();

if (sLen < pLen) {
    return vector<int>();
}

vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for (int i = 0; i < pLen; ++i) {
    ++sCount[s[i] - 'a'];
    ++pCount[p[i] - 'a'];
}
// 如果刚记录玩就一样，那么说明整个总串就是一个巨大的异位词。
if (sCount == pCount) {
    ans.emplace_back(0);
}

然后开始滑动窗口，从左往右固定窗口长度搜索即可。

for (int i = 0; i < sLen - pLen; ++i) {
    --sCount[s[i] - 'a'];
    ++sCount[s[i + pLen] - 'a'];

    if (sCount == pCount) {
        ans.emplace_back(i + 1);
    }
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

解答

跟46. 全排列一样都是典型回溯题。思路差不多的，先对整个数组执行，然后一点一点剥掉，保证不要重复即可。

这题我们选择一点一点加数进去，所以我们先建立vector<<vector<int>> ans; vector<int> subans;回溯函数backtrack函数如下：

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& ans) { // start用于记录开始被插入的地方，避免重复插入数字
    ans.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, ans);
        path.pop_back();
    }
}

73 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

解答

纯纯模拟题根本不想写，主要就是第一次思路不太好想，毕竟要求原地算法。

我们用首行和首列来记录当前行或列是否需要被置零，可是首行和首列被修改了怎么办？那就多加两个变量记录首行首列是否需要置零。

至于置零的方式比较有意思，从左上角以行为基准遍历矩阵，检测行首或列首记录了需要置零，就把当前格置零即可。

for (int i = 1; i < col_length; i++) {
    for (int j = 1; j < row_length; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
            matrix[i][j] = 0;
        }
    }
}

最后再检查一下首行和首列是否需要置零即可。

杂谈

cpp中抽象类经验

这周完成实训课大作业，实现一个简陋emp系统，但是要求Employee类必须为抽象类，意味着不可以直接构造。我有四个类继承于它，可是我有张表是只记录Employee基类才有的基本数据的，读取的时候怎么办呢？顺带提一下，不让用数据库，所以我是在初始化程序时读入，将所有表中数据存进表对应的vector里的。所以我先读Employee类，这时是没有别的派生类成员变量的数据的。

好在，我基类里有存一个变量，间接指定了派生类的类型，所以我在创建时用了switch语句，来直接构建对应的派生类。

void addEmployee(std::shared_ptr<MODULE::Employee> employee) {
    employees.push_back(employee);
    switch (employee->getLevel()) {
        case 4:
            managers.push_back(std::dynamic_pointer_cast<MODULE::Manager>(employee));
            break;
        case 3:
            technicians.push_back(std::dynamic_pointer_cast<MODULE::Technician>(employee));
            break;
        case 1:
            salesmen.push_back(std::dynamic_pointer_cast<MODULE::Salesman>(employee));
            break;
        case 2:
            salesManagers.push_back(std::dynamic_pointer_cast<MODULE::SalesManager>(employee));
            break;
    }
}

这里还有一个值得注意的点，就是我创建的都是指针，这样对我日后修改十分的方便，也节省了内存。cpp智能指针是好东西，很好遵循了RAII原则，省去了管理内存不必要的麻烦。

顺带说一下项目思路吧。既然不让用数据库，我就在程序初始化时读入csv中数据，存进对应vector里，然后程序执行“数据库操作”时就修改对应vector（我知道时间复杂度是$O(n)$效率不好，我懒），最后程序退出时在析构函数里执行将vector中内容写回csv表的操作。总体架构还是模仿后端三层架构，重点实现了业务逻辑层（Service）和数据访问层（DAO）。