跳转至

笔试练习

技巧汇总

C++板子

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main () {

    return 0;
}

笔试题目

linux 哪个命令会强制杀死进程 1000,而不会优雅的关闭

在Linux中，要强制杀死一个进程而不尝试优雅关闭，可以使用kill命令配合SIGKILL信号。SIGKILL是一个强制终止进程的信号，进程不能捕获或忽略该信号，这意味着它不会有机会进行任何清理操作就被立即终止。

命令格式如下：

kill -SIGKILL 1000

或者，你可以使用信号的数值，SIGKILL的值通常是9：

kill -9 1000

这里，1000是你想要强制杀死的进程ID。使用-9选项可以确保进程被立即终止，不进行任何清理操作。

linux 哪个命令会优雅的关闭进程1000

在Linux中，要优雅地关闭进程，通常使用kill命令发送SIGTERM信号。SIGTERM（信号值为15）是一个软终止信号，允许进程在终止之前释放资源和进行清理工作。这是终止进程的推荐方式，因为它给了进程一个适当关闭自身的机会。

命令格式如下：

kill -SIGTERM 1000

或者，由于SIGTERM是kill命令的默认信号，你可以省略信号名称：

kill 1000

单一责任制的好处（Single Responsibility Principle, SRP）

单一责任原则（Single Responsibility Principle, SRP）是面向对象设计原则中的一个概念，它指的是一个类应该仅有一个引起它变化的原因。这个原则强调将功能明确、相关性强的行为封装在同一个类中，而不是将多种不同的行为堆砌在一起。单一责任原则的好处包括：

1. 提高系统的可维护性

当一个类只负责一个功能或业务逻辑时，对该功能的修改只会影响到这个类，不会对系统中的其他部分产生副作用。这使得维护和更新特定功能变得更加简单直接。

2. 提高代码的可读性

遵循单一责任原则的代码通常更加清晰和易于理解。每个类的职责都很明确，开发人员可以快速定位相关的业务逻辑，降低了学习和理解代码的难度。

3. 促进代码的复用

当每个类都只关注于完成一个具体的任务时，这样的类更容易在其他系统或模块中被复用。因为它们不会与特定的业务逻辑过于耦合，可以在不同的上下文中发挥作用。

4. 降低修改带来的风险

修改一个多责任的类时，可能会影响到与这些责任相关的所有功能。但如果遵循单一责任原则，修改一个类的行为只会影响到该类所负责的那部分功能，从而降低了引入错误的风险。

5. 简化单元测试

单一责任的类通常更容易被测试。因为它们只负责一个功能，所以写测试用例时只需要关注这一点。这使得测试更加直接、高效，也使得测试能够更全面地覆盖到类的行为。

总结

单一责任原则通过限制类的职责范围，提高了软件设计的清晰度和系统的健壯性。它有助于创建易于维护、扩展和测试的代码，是构建高质量软件系统的关键原则之一。尽管在实践中严格遵循这一原则可能会导致类的数量增加，但通过合理的设计和组织，可以最大化地发挥其带来的好处。

在这四个选项中，不是结构型设计模式的是“工厂”。

在这四个选项中，不是结构型设计模式的是“工厂”。

解释如下：

  • 工厂（Factory）: 属于创建型设计模式，其目的是创建对象，而不是直接通过new关键字实例化对象。这样可以提高系统的灵活性，因为创建对象的具体类别可以在运行时刻决定。
  • 适配器（Adapter）: 属于结构型设计模式，它允许不兼容的接口之间进行交互。适配器模式通过包装一个已存在的类，提供一个期望的接口。
  • 修饰器（Decorator）: 也是结构型设计模式，它允许向一个现有的对象添加新的功能，同时又不改变其结构。这种类型的设计模式作为现有类的一个包装。
  • 单例（Singleton）: 属于创建型设计模式，确保一个类只有一个实例，并提供一个全局访问点来获取该实例。

总结，工厂模式是创建型设计模式，而适配器和修饰器是结构型设计模式，单例模式是创建型设计模式。

观察者模式是一种行为型设计模式。它定义了对象之间的一对多依赖关系，使得当一个对象改变状态时，所有依赖于它的对象都会得到通知并自动更新。观察者模式主要用于实现分布式系统中的事件处理系统、在桌面应用中实现MVC模型，以及各种发布-订阅（Pub/Sub）系统中。

题目：假设有一个子网 192.168.1.0/24，以下哪个IP地址不能够正常在这个子网下通信？

A) 192.168.1.25 B) 192.168.1.255 C) 192.168.2.1 D) 192.168.1.0

答案解析：

首先，我们需要理解题目给出的子网信息。这里的子网是192.168.1.0/24，表示使用子网掩码255.255.255.0，这意味着这个子网的IP地址范围是192.168.1.0到192.168.1.255。

  • A) 192.168.1.25在这个范围内，因此可以正常通信。
  • B) 192.168.1.255是这个子网的广播地址，虽然在技术上是这个子网的一部分，但它是用来广播到所有这个子网内的设备，而不是分配给单个设备的，因此它可以“通信”，但其实用途不是分配给单个设备。
  • C) 192.168.2.1不在192.168.1.0到192.168.1.255的范围内，因此它不能在192.168.1.0/24子网下正常通信。
  • D) 192.168.1.0是这个子网的网络地址，它标识的是整个网络而非一个可分配的主机地址，因此它自身不用于设备通信。

因此，正确答案是C) 192.168.2.1，它不能在192.168.1.0/24子网下正常通信

为什么“这里的子网是192.168.1.0/24，表示使用子网掩码255.255.255.0”

“这里的子网是192.168.1.0/24，表示使用子网掩码255.255.255.0”这句话的意思是基于子网掩码和CIDR（无类别域间路由）表示法的概念。这里，192.168.1.0/24是一个网络地址，其中“/24”是CIDR表示法，用来指示网络地址中有24位是网络前缀，剩余的位（在这个例子中是8位）用于主机地址。让我们分解这个概念以便更好地理解它：

子网掩码（Subnet Mask）

子网掩码用来区分一个IP地址中的网络部分和主机部分。在IPv4中，一个IP地址由32位组成，分为四个字节，每个字节由8位组成，用点分十进制表示，如255.255.255.0。

CIDR表示法

CIDR表示法（例如/24）提供了一种方式来表示子网掩码的长度。在/24的例子中，前24位被用作网络地址，这意味着最后8位用于主机地址。这种表示方法提供了一种更灵活的划分网络和主机的方式，比传统的A类、B类和C类地址更加细粒度。

解释为什么“/24表示使用子网掩码255.255.255.0”

当我们说/24时，我们指的是前24位是网络部分，剩下的是主机部分。在二进制中，这表示前24位都是1，剩下的位都是0：

11111111.11111111.11111111.00000000

转换为点分十进制，就是255.255.255.0。这意味着在这个子网中，只有最后的8位可以用来分配给主机，提供了256个可能的地址（包括网络地址和广播地址在内）。实际可用于主机的地址是这个范围减去网络地址（192.168.1.0）和广播地址（192.168.1.255），因此提供了254个可用地址（192.168.1.1到192.168.1.254）。

通过使用/24CIDR表示法和对应的255.255.255.0子网掩码，可以清晰地划分网络地址和可用于分配给设备的主机地址。这种方式在设计和管理网络时提供了显著的灵活性和准确性。

用数据库存代码的好处

将代码存储在数据库中而不是文件系统或版本控制系统（如Git）中可以在特定场景下带来一些好处，尽管这种做法并不常见，且需要谨慎使用。下面是一些可能的好处：

1. 集中管理

  • 将代码存储在数据库中可以实现代码的集中管理。对于一些动态生成或频繁更改的代码，例如动态SQL语句、配置脚本或业务逻辑，集中存储可以简化管理。

2. 安全性

  • 数据库可以提供细粒度的访问控制和审计功能，帮助保护代码不被未授权访问或修改。这对于存储敏感逻辑或数据处理脚本尤其重要。

3. 版本控制

  • 虽然文件系统基的版本控制系统（如Git）对代码的版本管理非常有效，但数据库也可以实现版本控制，通过记录数据变更的历史来管理代码版本。这可以确保代码变更的追踪和回滚。

4. 易于部署和迁移

  • 将代码存储在数据库中，可以简化代码部署和迁移的过程。在多环境（开发、测试、生产）部署中，可以通过数据库迁移脚本来统一管理和迁移代码，无需额外的文件同步操作。

5. 动态执行

  • 对于需要根据不同条件动态执行不同逻辑的应用程序，将代码存储在数据库中可以实现更灵活的动态执行。应用程序可以根据需要查询数据库，获取并执行相应的代码片段。

6. 与数据紧密相关的操作

  • 对于一些与数据紧密相关的操作，如数据库触发器、存储过程等，将这些代码存储在数据库中可以提高执行效率和便捷性。

在给定的一个整数(有正有负)类型数组中, 求最小子序列和

典型的动态规划问题

f[i] 标识的就是以i为结尾的所有子串序列和中的最小值

一种是和前面的组成序列，一种是单独自己

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int findMinSubArraySum(const vector<int>& nums) {
    if (nums.empty()) return 0;
    int currMin = nums[0];
    int globalMin = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        currMin = min(nums[i], nums[i] + currMin);
        globalMin = min(globalMin, currMin);
    }
    return globalMin;
}

int main () {
    vector<int> nums = {2, 1, -2, -3};
    cout << findMinSubArraySum(nums) << endl;

    return 0;
}

最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 一共是两种情况在根节点的两侧
        // 本身是p/q，另一个在另外一侧
        if (!root) return nullptr;
        if (root == p) return root;
        if (root == q) return root;

        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        else if (left) return left;
        else if (right) return right;
        else return nullptr;

    }
};

无向图1024顶点，2023条边用邻接矩阵存储，邻接矩阵的大小

在无向图中，邻接矩阵是一个二维数组，其大小为顶点数的平方。对于一个有1024个顶点的无向图，邻接矩阵的大小（即数组的大小）将是1024 x 1024。

left join, right join, inner join, join的区别和以及具体的用法

INNER JOIN (内连接)

当你只写JOIN时，默认是进行内连接（INNER JOIN）

  • 定义：只返回两个表中匹配的记录。
  • 用法: 假设我们有两个表，一个是employees（员工），另一个是departments（部门），我们想找出所有员工及其所属部门的信息。
SELECT employees.name, departments.department_name
FROM employees
INNER JOIN departments
ON employees.department_id = departments.id;
LEFT JOIN（左连接）
  • 定义：返回左表（table1）的所有记录和右表（table2）中匹配的记录。如果左表的某条记录在右表中没有匹配，则结果中这条记录的右表部分为NULL。
  • 用法：如果我们想找出所有员工的信息，即使他们没有归属的部门。
SELECT employees.name, departments.department_name
FROM employees
LEFT JOIN departments
ON employees.department_id = departments.id;
RIGHT JOIN（右连接）
  • 定义：返回右表（table2）的所有记录和左表（table1）中匹配的记录。如果右表的某条记录在左表中没有匹配，则结果中这条记录的左表部分为NULL。
  • 用法：如果我们想列出所有部门，即使它们没有员工。
SELECT employees.name, departments.department_name
FROM employees
RIGHT JOIN departments
ON employees.department_id = departments.id;

202.100.2.16IP 和255.255.255.192子网掩码，IP还能怎么表示，应该是202.100.2.16/26?

当你有一个IP地址202.100.2.16和子网掩码255.255.255.192时，这个地址可以使用CIDR（无类别域间路由）表示法表示为202.100.2.16/26。

这里的“/26”表示子网掩码的前26位是网络部分，这是因为子网掩码255.255.255.192在二进制中表示为11111111.11111111.11111111.11000000。这里，前26位是1，意味着网络部分占了26位。剩下的6位用于主机，允许在子网内分配的IP地址数量。

具体到这个例子中，子网掩码255.255.255.192将IP地址空间分成了4个子网，每个子网有64个地址（包括网络地址和广播地址）。因此，这个特定的IP地址202.100.2.16属于其所在的64地址范围内的一个地址，使用CIDR表示法就是202.100.2.16/26。

共享临界区每次允许3个进程进入，一共15个进程，信号量的变化范围是多少？

  • 最大值为3：当没有进程在临界区或者刚好有一个进程离开临界区，使得信号量增加到最大容量时。
  • 最小值：理论上，如果所有15个进程都试图进入已满的临界区，则信号量的值可以达到3 - 15 = -12。实际上，这个最小值取决于系统对信号量的实现和使用方式，以及是否允许所有进程几乎同时请求进入临界区。

10.0.17.0/24等长子网划分，掩码255.255.255.240,最大子网个数和最大分配地址

对于给定的网络10.0.17.0/24，当你使用子网掩码255.255.255.240进行等长子网划分时，意味着你将原始的/24网络进一步划分。子网掩码255.255.255.240在CIDR表示法中为/28。这意味着每个子网有232−28232−28个地址，即每个子网有16个地址。

计算最大子网个数

要计算在/24网络中可以划分出多少个/28子网，可以使用公式2(子网掩码长度−原网络掩码长度)2(子网掩码长度−原网络掩码长度)。在这个例子中，这将是2(28−24)=242(28−24)=24。

2(28−24)=24=162(28−24)=24=16

因此，你可以从一个/24网络中划分出16个/28子网。

计算最大分配地址

每个/28子网可以有16个地址，包括网络地址和广播地址。因为网络地址和广播地址不能分配给主机，所以每个子网实际上可以分配的地址数为16 - 2 = 14个。

总结

  • 最大子网个数：16个子网
  • 每个子网的最大分配地址数：14个地址

这意味着对于10.0.17.0/24网络，使用子网掩码255.255.255.240进行等长子网划分时，你可以得到16个子网，每个子网中有14个可分配给设备的IP地址。

非抢占调度中引起进程调度的原因

1. 进程终止

当进程完成其执行并终止时，操作系统需要选择另一个进程来执行。这是最直接的引起进程调度的原因。

2. 进程阻塞

当进程执行过程中进行了某种等待操作，如等待I/O操作完成、等待文件系统操作或等待同步对象（例如信号量、锁等）时，该进程会进入阻塞状态。由于它不能继续执行，操作系统将选择另一个进程来使用CPU。

3. 系统调用

即使在非抢占式调度策略中，进程也可能因为执行系统调用而暂时“让出”CPU。如果这个系统调用涉及到等待操作（如读取磁盘文件），那么在等待期间，其他进程可以被调度执行。

4. 用户交互

在某些基于事件的或用户交互的应用程序中，进程可能在等待用户输入时自愿放弃CPU。这允许其他进程在用户做出响应之前执行。

5. 协作式让出

在一些操作系统或运行时环境中，进程或线程可以显式调用特定的函数来让出其CPU的使用权。这通常出现在设计良好的协作式多任务处理系统中，其中每个进程都会定期让出控制权，以允许其他进程运行。

注意

非抢占式调度要求进程良好的协作。如果一个进程长时间占用CPU而不释放（例如，进入无限循环），它可能会导致系统变得不响应，因为其他进程无法得到执行的机会。因此，在设计这样的系统时，开发者需要格外注意确保每个进程都会在合理的时间内让出CPU。

异步传输和同步传输的区别

异步传输和同步传输是计算机网络和数据通讯中的两种基本传输机制，它们在数据发送和接收的方式上有本质的区别。

异步传输（Asynchronous Transmission）

  • 特点：
  • 数据以独立的单位传输，每个单位通常以起始位开始，以停止位结束。这意味着发送的数据之间不是连续的，每个数据单元（如一个字节）之间可能存在间隔时间。
  • 每个数据单元的传输是独立的，接收方根据起始位和停止位来识别数据单元的开始和结束。
  • 不需要发送方和接收方之间的时钟同步。每个数据单元都有自己的起始和停止位，这使得接收方可以根据这些位来重新同步。
  • 用途：
  • 常用于计算机串行通讯，如RS-232接口，以及某些低速度的网络通讯。

同步传输（Synchronous Transmission）

  • 特点：
  • 数据以连续的流形式传输，不在数据单元之间插入起始位和停止位。这意味着发送的数据是连续的，没有明显的间隔。
  • 需要发送方和接收方之间有严格的时钟同步，以确保接收方正确地识别出发送的数据单元。
  • 数据以块的形式发送，通常需要在数据块的开始和结束添加特殊的同步字符，以帮助接收方确定数据块的边界。
  • 用途：
  • 常用于更高速度的网络通讯，如以太网、光纤通道等，以及内部总线通讯协议。

区别总结

  • 时钟同步：同步传输需要发送方和接收方之间的时钟同步，而异步传输不需要。
  • 数据单元边界：异步传输的数据单元之间有明确的起始和停止位作为边界，而同步传输通过连续发送数据，并使用特殊同步字符标识数据块的开始和结束。
  • 适用场景：异步传输适用于低速或中速通讯，常用于串行通讯。同步传输适用于高速通讯，常用于网络通讯和内部总线协议。
  • 效率：同步传输由于不需要在每个字符之间添加额外的起始和停止位，因此在高速通讯中更为高效。然而，它需要更复杂的硬件和软件来维持时钟同步。

根据应用的具体需求和环境，选择适合的传输机制是非常重要的。

异步传输和同步传输的例子

异步传输的例子

  1. HTTP（Hypertext Transfer Protocol）:
  2. 通常被视为异步传输，特别是在现代的web应用中，客户端（如浏览器）发送请求后不需要一直等待响应，可以继续其他任务，服务器响应准备好后再处理。
  3. SMTP（Simple Mail Transfer Protocol）:
  4. 用于电子邮件的传输，邮件发送后，传输过程和邮件到达可以异步进行，发送者不需要等待整个过程完成。
  5. MQTT（Message Queuing Telemetry Transport）:
  6. 一个轻量级的消息协议，用于设备间异步通信，允许设备发布消息到主题，而其他设备订阅这些主题，不需要实时等待。

同步传输的例子

  1. TCP（Transmission Control Protocol）:
  2. TCP提供一种面向连接的、可靠的字节流服务。在TCP连接中，数据的发送和接收需要按照严格的顺序进行，接收方必须确认每个发送的数据包，这可以被视为一种同步传输方式。
  3. FTP（File Transfer Protocol）:
  4. 用于文件传输，通常在客户端和服务器之间建立TCP连接进行同步数据传输，数据和命令传输严格遵循请求-响应模式。
  5. Telnet:
  6. 一种网络协议，用于在远程计算机上执行命令，它通过同步传输模式进行交互，用户输入命令后必须等待并接收到响应。

C++万能头文件

#include <bits/stdc++.h>

比较三个数的最小值

min({a, b, c});

直接使用哈希表的key和value

for (auto& [charKey, charNumber] : charCount) {}

忽略结尾的换行符

cin.ignore();

字符串中出现次数

int cnt = count(s.begin(), s.end(), 'M') + count(s.begin(), s.end(), 'T');

处理矩阵输入

用string输入，然后一个一个填

输入：

1010 0101 1100 0011

for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++) {
            matrix[i][j] = row[j] - '0';
        }
    }

可以模拟的时候不要犹豫，直接最直接的模拟即可，不用找数学规律了

vector<int> slimePos(n, 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int t = 0; t < n; t++) {
        vector<int> newSlimePos(n, 0);
        int emptyCells = 0;
        for (int i = 0; i < n; i++) {
            if (slimePos[i] == 1) {
                if (a[t] == 0 && i > 0) {
                    newSlimePos[i - 1] = 1;
                }
                else if (a[t] == 1 && i < n - 1) {
                    newSlimePos[i + 1] = 1;
                }
            }
        }
        slimePos = newSlimePos;

关于set的使用

在 C++ 的 set 容器中，元素是自动排序并且唯一的。由于 set 是基于红黑树实现的，它不提供直接修改元素的能力，因为这可能会破坏集合的内部排序规则。但是，你可以访问 set 的首元素，并且如果需要修改首元素，你必须先移除它，然后插入一个新的元素。需要注意的是，这种操作可能会改变原本的队首元素。

以下是如何访问和修改 set 中队首元素的步骤：

访问队首元素

你可以使用 begin() 方法获取到 set 的迭代器，指向第一个（即最小的）元素，然后通过解引用该迭代器来访问该元素。

std::set<int> mySet = {5, 1, 4};  // 1, 4, 5
auto firstElement = *mySet.begin();  // 访问第一个元素，此处为 1

修改队首元素

由于 set 中的元素是常量，不能直接被修改。如果你想要修改队首元素，你需要先删除它，然后插入一个新的元素。但是，这种操作会影响 set 的排序，新插入的元素可能不会成为新的队首元素。

// 删除队首元素
mySet.erase(mySet.begin());

// 插入新元素
mySet.insert(newElement);

这种方法在操作上是有效的，但请记住，由于 set 的排序特性，新插入的元素可能不会放置在原来队首元素的位置。

24-03-13 携程后端岗笔试

1. you子串

题目描述 小盖拿到了一个字符串，她想重排这个字符串后，使得该字符串包含尽可能多的"you"连续子串。你能帮帮她吗?

输入描述 一个仅包含小写字母的字符串，长度不超过10^5

输出描述 重排后的字符串。有多解时输出任意即可。

样例 输入 yyoouuuu 输出 uyouyouu

#include <bits/stdc++.h>
using namespace std;
int main () {
    string s;
    cin >> s;
    string answer;
    int n = s.size();
    unordered_map<char, int> charCount;
    for (int i = 0; i < n; i++) {
        charCount[s[i]]++;
    }
    int minCount = min({charCount['y'], charCount['o'], charCount['u']});

    for (int i = 0; i < minCount; i++) {
        answer += "you";
        charCount['y']--, charCount['o']--, charCount['u']--;
    }


    // 直接从哈希映射中构建字符串
    for (auto& [charKey, charNumber] : charCount) {
        while (charNumber-- > 0) {
            answer += charKey;
        }
    }
    cout << answer << endl;
}

2. 数组推平

题目描述 小盖拿到了一个数组，她每次操作可以任选一个元素加 1或者减 1。小盖想知道，将所有元素都变成和ai相等需要操作最少多少次?你需要回答i[1,n]的结果。

输入描述 第一行输入一个正整数n，代表数组的大小。第二行输入n个正整数ai，代表数组的元素。1<=n<=10^5 1<=ai<=10^9

输出描述 输出n行，分别代表i[1,n]的结果。 样例 输入 3 2 1 4

输出

3

4

5

使用前后缀分解，加上哈希表来存储结果每个数字对应的结果

==>前后缀分解是因为，数组中会有比ai大的数，也会有比ai小的数，所以小的和大的有分类讨论

==>而前缀和又可以轻松知道每个数左右的数的和，所以使用前后缀分解

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

int main () {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    vector<int> sortedNums(nums);
    sort(sortedNums.begin(), sortedNums.end());

    vector<int> left(n, 0);
    int sumLeft = 0;
    for (int i = 0; i < n; i++) {
        sumLeft += sortedNums[i];
        left[i] = sumLeft;
    }

    vector<int> right(n, 0);
    int sumRight = 0;
    for (int i = n - 1; i >= 0; i--) {
        sumRight += sortedNums[i];
        right[i] = sumRight;
    }
    // for (int i = 0; i < n; i++) cout << left[i] << " " << right[i] << endl;
    unordered_map<int, int> opsMap;
    for (int i = 0; i < n; i++) {
        if (opsMap.count(sortedNums[i])) {
            continue;
        }
        // 自己本身的操作步数肯定是0，所以不用考虑
        int leftOps = (i > 0) ? i * sortedNums[i] - left[i - 1] : 0;
        int rightOps = (i < n - 1) ? right[i + 1] - (n - i - 1) * sortedNums[i] : 0;
        // cout << sortedNums[i] << " " << leftOps << " " << rightOps << endl;
        opsMap[sortedNums[i]] = leftOps + rightOps;
    }

    for (int i = 0; i < n; i++) {
        cout << opsMap[nums[i]] << endl;
    }
}

24-03-09 美团后端岗笔试

1. MT

题目描述 MT 是开水的缩写，因此小盖很喜欢这两个字母。 现在小盖拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小盖想知道，操作结束后最多共有多少个'M'和T'字符?

输入描述 第一行输入两个正整数，代表字符串长度n和操作次数k。第二行输入一个长度为k的、仅由大写字母组成的字符串。1<=k<=n<=10^5

输出描述 输出操作结束后最多共有多少个'M'和T'字符

样例 输入 5 2 MTUAN

输出 4

样例说明 修改第三个和第五个字符，形成的字符串为MTTAM，这样共有 4 个'M'和T’。

我的答案
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main () {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'M' || s[i] == 'T') {
            sum++;
        }
    }
    int ans = (sum + k > n) ? n : sum + k;
    cout << ans << endl;
    return 0;
}
techguide答案
// 注意count使用
// 注意cin.ignore()使用
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main () {
    int n, k;
    cin >> n >> k;
    cin.ignore();
    string s;
    getline(cin, s);
    int cnt = count(s.begin(), s.end(), 'M') + count(s.begin(), s.end(), 'T');
    cout << cnt + min(n - cnt, k) << endl;
    return 0;
}

2. 数组询问

题目描述 小盖拿到了一个由正整数组成的数组，但其中有一些元素是末知的(用0来表示)。 现在小盖想知道，如果那些未知的元素在区间[l, r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少? 共有q次询问。

输入描述 第一行输入两个正整数n,q，代表数组大小和询问次数。 第二行输入n个整数ai，其中如果输入ai的为0，那么说明ai是未知的。 接下来的q行，每行输入两个正整数r，代表一次询问。

输出描述 输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

样例 输入 3 2 1 0 3 1 2 4 4 输出 5 6 8 8 样例说明 只有第二个元素是未知的。 第一次询问，数组最小的和是 1+1=3=5最大的和是 1+2+3=6 第二次询问，显然数组的元素和必然为 8.

我的答案
#include <iostream>
using namespace std;
int main () {
    int n, q;
    cin >> n >> q;
    int sum = 0, number = 0;
    for (int i = 0; i < n; i++) {
        int j;
        cin >> j;
        if (j == 0) {
            number++;
        }
        else {
            sum += j;
        }
    }
    int l, r;
    while (q--) {
        cin >> l >> r;
        cout << sum + number * l << ' ' << sum + number * r << endl;
    }
    return 0
}
techguide答案
#include <bits/stdc++.h>
using namespace std;
int countZeros(const vector<int> & array) {
    int zeros = 0;
    for (int num : array) {
        if (num == 0) {
            zeros++;
        }
    }
    return zeros;
}

int sumArray(const vector<int>& array) {
    int sum = 0;
    for (int num : array) {
        sum += num;
    }
    return sum;
}


int main () {
    int n, q;
    cin >> n >> q;
    vector<int> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];

    int zeros = countZeros(A);
    int sum = sumArray(A);
    // cout << "----" <<endl;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << (sum + zeros * l) << " " << sum + zeros * r << endl;
    }
    return 0;
}

3. 平衡矩阵

题目描述 小盖拿到了一个n*n 的矩阵，其中每个元素是 0或者 1。 小盖认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于1的数量。 现在，小盖希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述 第一行输入一个正整数n，代表矩阵大小。接下来的n行，每行输入一个长度为n的01串，用来表示矩阵。

输出描述 输出n行，第i行输出的i * i完美矩形区域的数量。

样例

输入 4 1010 0101 1100 0011

输出 0 7 0 1

自己答案
// 区域内0的数量和1的数量相等，相当于n个数的区域和为n / 2
#include <iostream>
#include <vector>
using namespace std;

int main () {
    int n;
    cin >> n;
    vector<vector<int>> array(n + 1, vector<int>(n + 1));
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         cin >> array[i][j];
    //     }
    // }

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            array[i][j] = s[j - 1] - '0';
        }
    }

    // cout << "111111111111" << endl;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         cout << array[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << "2222222222222" << endl;

    vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + array[i][j];
        }
    }

    // cout << "111111111111" << endl;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         cout << pre[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << "2222222222222" << endl;

    vector<int> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; i + k - 1<= n; k++) {
                // (i, j) (i + k - 1, j + k - 1)
                int c = i + k - 1, d = j + k - 1;
                int sum = pre[c][d] - pre[c][j - 1] - pre[i - 1][d] + pre[i - 1][j - 1];
                if (sum * 2 == k * k) {
                    ans[k]++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
techguide
#include <iostream>
#include <vector>

using namespace std;

int getSubMatrix(vector<vector<int>>& pre, int x1, int y1, int x2, int y2) {
    return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++) {
            matrix[i][j] = row[j] - '0';
        }
    }

    vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }

    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (i + k >= n || j + k >= n) break;

                int subMatrix = getSubMatrix(pre, i, j, i + k, j + k);
                if (subMatrix * 2 == (k + 1) * (k + 1)) {
                    ans[k]++;
                }
            }
        }
    }

    for (int a : ans) {
        cout << a << endl;
    }

    return 0;
}

4. 区间删除

题目描述 小盖拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小盖想知道，一共有多少种不同的删除方案?

输入描述 第一行输入两个正整数n，k。第二行输入n个正整数ai，代表小盖拿到的数组。

输出描述 一个整数，代表删除的方案数。

样例 输入 5 2 2 5 3 4 20

输出 4

样例说明 第一个方案，删除[3]。 第二个方案，删除[4]。 第三个方案，删除[3,4]。 第四个方案，删除[2]。

我的答案（使用最简单的方法，但是时间复杂度高 O(n^2)，说明性质分析错误）
// 分析性质：
// k个0代表multiplication % (pow(10, k)) = 0

// 区间那么就滑动窗口，创造区间
// 如果到1个数，不能成立的时候，那么他的后面的数字都不能成立
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
typedef long long LL;
using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    LL mul = 1;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mul *= a[i];
    }
    int div = pow(10, k);
    for (int i = 0; i < n; i++) {
        int temp = mul;
        for (int j = i; j < n; j++) {
            temp /= a[j];
            if (temp % div == 0) ans++;
            else break;
        }
    }
    cout << ans << endl;
    return 0;
}
我的答案2需要修改！！！
// 末尾至少有k个0
// 就相当于所有的因数中至少有k个2和k个5

#include <iostream>
#include <vector>
using namespace std;

int getFactor2 (int n) {
    int f2 = 0;
    while (n % 2 == 0) {
        n /= 2;
        f2++;
    }
    return f2;
}

int getFactor5(int n) {
    int f5 = 0;
    while (n % 5 == 0) {
        n /= 5;
        f5++;
    }
    return f5;
}

int binarySearch(vector<int>& pres, int target) {
    int l = 0, r = pres.size() - 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        int x = pres[mid];
        if (x > target) {
            r = mid - 1;
        }
        else l = mid;
    }
    return l;
} 

int main () {
    int n, k;
    cin >> n >> k;
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    vector<int> pres2(n + 1);
    vector<int> pres5(n + 1);

    // cout << getFactor2(200) << getFactor5(200) << endl;
    int all2 = 0, all5 = 0;
    for (int i = 1; i <= n; i++) {
        int f2 = getFactor2(A[i]);
        pres2[i] = pres2[i - 1] + f2;
        all2 += f2;
        int f5 = getFactor5(A[i]);
        pres5[i] = pres5[i - 1] + f5;
        all5 += f5;
    }

    // cout << all2 << all5 << endl;
    // for (int i = 1; i <= n; i++) {
    //     cout << pres2[i] << ' ' << pres5[i] << endl;
    // }

    // 需要找到的是小于等于这个值的位置
    int ans = 0;
    for (int i = 1; i <= n; i++) {

        int p2 = binarySearch(pres2, all2 + pres2[i] - k);
        // cout << "i = " << i << ' ' << "p2 = " << p2 << endl;
        int p5 = binarySearch(pres5, all5 + pres5[i] - k);
        // cout << "i = " << i << ' ' << "p5 = " << p5 << endl;
        cout << "i = " << i << min(p2, p5) << endl;
        ans += min(p2, p5) - i + 1;
    }
    cout << ans <<endl;

    return 0;
}

5. 朋友关系

题目描述 小盖认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。 现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小盖想知道某一时刻中，某两人是否可以通过朋友介绍互相认识? 事件共有 2 种 1 u v:代表编号u的人和编号v的人淡忘了他们的朋友关系 2 u v:代表小盖查询编号u的人和编号 v的人是否能通过朋友介绍互相认识。 注:介绍可以有多层，比如 2号把1号介绍给3号，然后3号再把1号介绍给4号，这样1号和 4号就认识了。

输入描述 第一行输入三个正整数n,m，q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数uv，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数p,u,V，含义如题目描述所述。## 输出描述一个整数，代表删除的方案数。

输入描述 对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号u的人和编号v的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"NO”。

样例 输入 5 3 5 1 2 2 3 4 5 1 1 5 2 1 3 2 1 4 1 1 2 2 1 3

输出 Yes No No

样例说明 第一次事件，1号和5号本来就不是朋友所以无事发生。 第二次事件是询问，1号和3号可以通过 2号的介绍认识。 第三次事件是询问，显然1号和 4号无法互相认识。 第四次事件，1号和2 号淡忘了。第五次事件，此时1号无法再经过 2号和 3号互相认识了。

23-08-19 美团后端岗笔试

1. 外卖订单编号

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        int div = b % a;
        if (div == 0) {
            cout << a << endl;
        }
        else cout << div << endl;
    }
    return 0;
}

2. 加法

// 将一个加法改成乘法之后: a + b --> a * b
// 那么后面和前面的差值是a * b - a + b
// 只要差值最大，就是最后所得到的和最大
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main () {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }


    int maxDiff = 0;
    int c = 0, d = 1;
    for (int i = 0; i < n - 1; i++) {
        int j = i + 1;
        int diff = a[i] * a[j] - (a[i] + a[j]);
        if (diff > maxDiff) {
            maxDiff = diff;
            c = i;
            d = j;
        }
    }
    cout << sum - a[c] - a[d] + a[c] * a[d] << endl;
    return 0;
}

3. 01串翻转

题目描述 小盖定义一个 01 串的权值为:每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。 例如，"10001"的权值是 1，因为只需要修改一次:对第三个字符取反即可。 现在小盖拿到了一个 01串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗?

输入描述 一个仅包含'0'和'1'的字符串，长度不超过 2000。

输出描述 所有非空子串的权值和。

样例 输入 10001

输出 8

样例说明 长度为 2 的子串中，有2个"00"的权值是1。 长度为 3 的 3个子串权值都是 1。 长度为 4的 2 个子串权值都是 1。长度为 5 的1个子串权值是 1。总权值之和为 2+3+2+1=8

23-03-18 美团后端岗笔试

1. 捕获

题目描述 小美在玩一项游戏。请该游戏的目标是尽可能抓获敌人。 敌人的位置将被一个二维坐标(x,y)所描述。 小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。 捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。 现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述 第一行三个整数N,A,B，表示共有N个敌人，小美的全屏技能的参数A和参数B。 接下来N行，每行两个数字xy，描述一个敌人所在的坐标。 1≤N≤500，1≤A,B≤1000，1≤x,y≤1000。

3 1 1 1 1 1 2 1 3

输出描述 一行，一个整数表示小美使用技能单次所可以捕获的最多数量。 2

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n, a, b;
    cin >> n >> a >> b;
    vector<pair<int, int>> enemies(n);
    for (int i = 0; i < n; i++) {
        cin >> enemies[i].first;
        cin >> enemies[i].second;
    }
    // 对敌人的坐标进行排序
    // 对第一个字段进行升序排序
    sort(enemies.begin(), enemies.end());

    int maxSize = 0;
    // 使用滑动窗口寻找最大的符合条件的敌人集合
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // 检查当前窗口内的敌人是否满足条件
            if (abs(enemies[j].first - enemies[i].first) <= a && 
                abs(enemies[j].second - enemies[i].second) <= b) {
                maxSize = max(maxSize, j - i + 1);
            }
            else break;
        }
    }
    cout << maxSize << endl;
    return 0;
}

2. 彩带

题目描述 小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。 因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。 显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。 你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

输入描述 第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。 接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。 1≤N,K≤5000，彩带上的颜色数字介于[1,2000]之间。

8 3 1 2 3 2 1 4 5 1 输出描述 一行，一个整数，表示选取的彩带的最大长度。 5

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 0, r = 0;
    vector<int> b(n);
    int type = 0;
    // 以r为结尾的区间
    // r一位一位地移动，然后l作为调整
    int cnt = 0;
    int res = 0;
    while (r < n) {
        int n = a[r];
        b[n]++;
        if (b[n] == 1) {
            cnt++;
        }
        while (cnt > k) {
            int lNum = a[l];
            b[l]--;
            if (b[l] == 0) {
                cnt--;
            }
            l++;
        }
        res = max(res, r - l + 1);
        r++;
    }
    cout << res << endl;
    return 0;
}

3. 回文串

题目描述 现在小美获得了一个字符串。小美想要使得这个字符串是回文串。 小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符'a'-'z' 你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。 数据保证能在题目限制下形成回文字符串。 注:回文字符串:即一个字符串从前向后和从后向前是完全一致的字符串。 例如字符串abcba,aaaa,acca都是回文字符串。字符串abcd,acea都不是回文字符串，

输入描述 一行，一个字符串。字符串中仅由小写英文字符构成。 保证字符串不会是空字符串。 字符串长度介于[1,100000]之间。

acca

输出描述 一行，一个在题目条件限制下所可以获得的一行,字典序最小的回文字符串。 aaaa

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string str;
    cin >> str;
    vector<char> s(str.begin(), str.end());
    int l = 0;
    int r = s.size() - 1;
    int res = 2;
    vector<vector<int>> tmp;
    while (l < r) {
        if (s[l] != s[r]) {
            tmp.push_back({l,r});
        }
        l++;
        r--;
    }
    if (tmp.size() == 2) {
        s[tmp[0][0]] = min(s[tmp[0][0]],s[tmp[0][1]]);
        s[tmp[0][1]] = min(s[tmp[0][0]],s[tmp[0][1]]);
        s[tmp[1][0]] = min(s[tmp[1][0]],s[tmp[1][1]]);
        s[tmp[1][1]] = min(s[tmp[1][0]],s[tmp[1][1]]);
    } else if (tmp.size() == 1) {
        char c = min(s[tmp[0][0]],s[tmp[0][1]]);
        if (c != 'a') {
            s[tmp[0][0]] = 'a';
            s[tmp[0][1]] = 'a';
        } else {
            s[tmp[0][0]] = 'a';
            s[tmp[0][1]] = 'a';
            if (s.size() % 2 == 1) {
                s[s.size() / 2] = 'a';
            }
        }
    } else {
        l = 0;
        r = s.size() - 1;
        int cnt = 2;
        while (cnt > 0 && l <= r) {
            if (s[l] != 'a') {
                s[l] = 'a';
                s[r] = 'a';
                cnt -= 2;
            }
            l++;
            r--;
        }
    }
    for (auto ch : s) {
        cout << ch;
    }
    return 0;
}

4. 商店

题目描述 现在商店里有N个物品，每个物品有原价和折扣价。 小美想要购买商品。小美拥有X元，一共Y张折扣券。 小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入描述 第一行三个整数，以空格分开，分别表示N,X,Y. 接下来N行，每行两个整数，以空格分开表示一个的原价和折扣价。 1≤N≤100,1≤X≤5000,1≤Y<50，每个商品原价和折扣价均介于[1,50]之间。

3 5 1

4 3

3 1

6 5

输出描述 一行，两个整数，以空格分开。第一个数字表示最多买几个商品，第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。 2 5

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n, x, y;
    cin >> n >> x >> y;
    vector<pair<int, int>> products(n);
    for (int i = 0; i < n; i++) {
        cin >> products[i].first >> products[i].second;
    }


    // dp[i][j][k]表示在考虑前i个商品，j张购物券，总共花费k元的情况下，购买的商品数量
    sort(products.begin(), products.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return (a.first - a.second) > (b.first - b.second);
    });
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<pair<int, int>> products(N);
    for (int i = 0; i < N; ++i) {
        cin >> products[i].first >> products[i].second; // first是原价，second是折扣价
    }

    // 商品按原价与折扣价的差额排序
    sort(products.begin(), products.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return (a.first - a.second) > (b.first - b.second);
    });

    // 初始化DP数组
    vector<vector<vector<int>>> dp(N+1, vector<vector<int>>(Y+1, vector<int>(X+1, -1)));
    dp[0][0][0] = 0;

    for (int i = 1; i <= N; ++i) {
        int cost = products[i-1].first; // 原价
        int discountCost = products[i-1].second; // 折扣价
        for (int j = 0; j <= Y; ++j) {
            for (int k = 0; k <= X; ++k) {
                // 不购买当前商品
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                // 购买当前商品，不使用折扣券
                if (k >= cost) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-cost] + 1);
                // 购买当前商品，使用折扣券
                if (j > 0 && k >= discountCost) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-discountCost] + 1);
            }
        }
    }

    int maxItems = 0, minCost = X;
    for (int j = 0; j <= Y; ++j) {
        for (int k = 0; k <= X; ++k) {
            if (dp[N][j][k] > maxItems || (dp[N][j][k] == maxItems && k < minCost)) {
                maxItems = dp[N][j][k];
                minCost = k;
            }
        }
    }

    cout << maxItems << " " << minCost << endl;

    return 0;
}

5. 能量塔

题目描述 现在有若干节点。每个节点上有能量塔。所有节点构成一棵树。 某个节点u可以为和u距离不超过给定值的节点各提供一点能量。此处距离的定义为两个节点之间经过的边的数量。特别的，节点u到本身的距离为零。 现在给出每个节点上的能量塔可以为多远的距离内的点提供能量。 小美想要探究每个节点上的能量值具体是多少。 你的任务是帮助小美计算得到，并依次输出。

输入描述 第一行一个整数N，表示节点的数量。

接下来一行N个以空格分开的整数，依次表示节点1，节点2，…节点N的能量塔所能提供能量的最远距离。

接下来N-1行，每行两个整数，表示两个点之间有一条边。 1≤N<500，节点上能量塔所能到达的最远距离距离不会大于 500。 3 1 1 1 1 2 2 3 输出描述 2 3 2

1 2 3

24-03-10 米哈游后端岗笔试题

1. 蹦蹦史莱姆

题目描述 地图上有n个格子排成一排，最左边的格子为1，最右边的格子为n。 第0 秒时，每个格子都有一只史莱姆。 第i 只史莱姆的跳跃方向用数组a 表示。 ai=0 表示史莱姆跳跃的方向是往左。若第i秒史莱姆位于格子 x，那么第i+1秒史莱姆会跳到格子x-1。如果当前史莱姆在格子1则下一秒史莱姆将跳出地图。 ai=1 表示史莱姆跳跃的方向是往右。若第秒史莱姆位于格子x，那么第 i+1秒史莱姆会跳到格子x+1。如果当前史莱姆在格子n，则下一秒史莱姆将跳出地图。 米小游想知道第 1-n 秒，地图上有多少个格子没有史莱姆。

输入描述 第一行包含一个整数n，n[1,3000]，表示地图上的格子数量。

第二行包含n 个整数ai，ai[0,1]，表示每只史莱姆的跳跃方向。

输出描述 输出包含一行n 个整数，用空格隔开，第i个数表示第i 秒没有史莱姆的格子数量。

样例 输入 3 1 0 1

输出 1 2 3 样例说明 史莱姆1-3 的跳跃方向分别为，往右，往左，往右。 第1秒，5史莱姆1跳到格子 2，史莱姆2 跳到格子1，史莱姆3 跳出地图，格子3没有史莱姆。 第2秒，史莱姆1跳到格子3，史莱姆2跳出地图，格子 1,2 没有史莱姆。 第 3 秒，史莱姆1跳出地图，格子1,2,3 没有史莱姆。

// 直接进行模拟来确定史莱姆的格子数量
#include <bits/stdc++.h>
using namespace std;

int main () {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> slimePos(n, 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int t = 0; t < n; t++) {
        vector<int> newSlimePos(n, 0);
        int emptyCells = 0;
        for (int i = 0; i < n; i++) {
            if (slimePos[i] == 1) {
                if (a[t] == 0 && i > 0) {
                    newSlimePos[i - 1] = 1;
                }
                else if (a[t] == 1 && i < n - 1) {
                    newSlimePos[i + 1] = 1;
                }
            }
        }
        slimePos = newSlimePos;
        for (int i = 0; i < n; i++) {
            if (slimePos[i] == 0) {
                emptyCells++;
            }
        }
        cout << emptyCells << " ";
    }
    cout << endl;
    return 0;
}

2. 一番赏

题目描述 本题目由抽崩坏三茶歇时刻一番赏真实事件改(乱)编! -番赏初始有 n个抽赏，大家需要排队购买，只有在队列最前面的人可以选择购买或者不购买，所有人随时都可以离开队列，离开队列后也可以随时加入队列。 小盖陪着她的好朋友莫娜来买一番赏，她时不时会看一眼队列中有多少人。也就是说，共有 4 种事件: 1s:名字为s的人加入队列的结尾(保证不在队列中)。 2s:名字为s的人离开队列(保证s在队列中，但不一定在队列最前面) 3x:队列最前面的人购买了x个抽赏(保证在抽赏个数大于0时，当前至少有x个抽赏) 4:小盖查看队列人数。

还有一个特殊规则:当抽赏个数小于等于m时，处于队列最前面的人一定会把剩余的所有抽赏全部买走。当抽赏全部被买走后，队列会立即清空，后续的所有事件都将失效。 小盖想知道，她每次查看队列人数时，队列中有多少人。以及最后抽赏全部卖完或者所有事件结束后，每个参与过排队的人各买了多少个抽赏?(按名字字典序升序输出)

输入描述 第一行输入三个整数 n,m(1<=m<=n<=10^9)，q(1<=q<=2*10 ^5 表示抽赏个数、特殊规则限制、事件个数。接下来q 行，首先输入一个整数 op(1<=op<=4)表示事件类型 若事件类型为1或2，则再输入一个长度不超过 10 的只由大小写字母组成的字符串9表示名字 若事件类型为 3，则再输入一个整数x表示购买的抽赏个数， 若事件类型为 4，则不再输入。

输出描述 对于每一个类型为 4 的事件，输出一行，包含一个整数表示队列中的人数。最后每一行按字典序升序输出每一个参与过排队的人的名字和购买的抽赏个数(用一个空格隔开)

样例 输入 70 20 8 1 Mona 1 Kaveh 4 2 Mona 1 Mona 2 Kaveh 4 1 Kaveh

输出 2 1 Kaveh 0 Mona 0

样例说明

初始时队列为空。 第1个事件:Mona加入队列，队列为:[“Mo na"]。 第2个事件:Kaveh加入队列，队列为:[“Mona""Kaveh"。 第3个事件:查看队列人数，队列为:[“Mona""Kaveh”]，共有2人。 第4个事件:Mona离开队列，队列为:[“Kaveh"]。 第5个事件:Mona加入队列，队列为:[“Kaveh""Mona"1. 第6个事件:Kaveh离开队列，队列为:[“Mona"。 第7个事件:查看队列人数，队列为:[“Mona”]，共有1人。 第8个事件:Kaveh加入队列，队列为:[“Mona""Kaveh"]。 Kaveh共购买了0个抽赏

#include <bits/stdc++.h>
using namespace std;
int main () {
    int n, m, q;
    cin >> n >> m >> q;
    // 需要什么数据结构来存储
    // 因为有出队和入队可以想到，queue和set的数据结构都能存储队列
    // 但是发现有可能队伍中的人也会出队，那么queue就做不到了，只能使用set
    // 为了让set按照入队顺序排序，那么就需要在set中存储pair{time, name}

    // 为了最后能输出每个人买了多少，那么需要记录每个购买量使用哈希表记录unordered_map<name, int>
    // 因为最后需要按照名字字典序输出，而unordered_map是没有顺序，使用map会自动按照名字的第一个字母排序

    // 最后还需要以O(1)时间查询名字到入队时间映射，那么采用unordered_map<name, int>
    set<pair<int, string>> queue;// 队列，以入队时间和名字作为键，用入队时间进行
    map<string, int> purchases; // 购买记录，按名字字典序存储
    unordered_map<string, int> nameToTime;// 名字到入队时间的映射


    for (int i = 0; i < q; i++) {
        int op;
        string name;
        cin >> op;
        switch (op) {
            case 1:{
                cin >> name;
                queue.insert({i, name});
                // 确保在购买记录中，因为需要输出所有人的购买记录
                purchases[name] = 0;
                nameToTime[name] = i;
                // case千万不要忘记break!!!!!!!!!!!
                break;
            }
            case 2: {
                cin >> name;
                int time = nameToTime[name];
                queue.erase({time, name});
                // 将不存在的人的入队时间抹除
                nameToTime.erase(name);
                break;
            }
            case 3: {
                int x;
                cin >> x;
                auto p = *queue.begin();
                queue.erase(queue.begin());
                nameToTime.erase(p.second);
                purchases[p.second] += x;
                n -= x;
                if (n <= m) {
                    purchases[p.second] += n;
                    n = 0;
                    // 清空队列
                    queue.clear();
                }
                break;
            }
            case 4:{
                cout << queue.size() << endl;
                break;
            }
            default: {
                cout << "Something went wrong!" << endl;
            } 
        }
        if (n == 0) break;  // 如果所有抽赏都被购买了，结束事件处理
    }

    for (const auto& p : purchases) {
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}

3. 建木

题目描述 仙舟罗浮上有一棵建木，据说服下建木生成的神实就可以得到“无尽形寿”的身体,蜕变为长生种。小盖是短生种，因此她很想找到神实.建木是一棵有 n个节点的有根树，节点编号为1-n ，根节点为x。对于编号为i 的节点fi 表示以i 为根的子树中，节点编号是i 的因子的节点个数。建木上神实的总数就是 zf门，小盖想知道建木上神实的总数是多少。

输入描述 第一行包含两个整数 n,x(1<=x<=n<=5*10^5)，表示树的节点个数，根节点编号。 接下来n-1 行，每行两个整数 u, v(1<=u,v<=n)，表示一条u 到v 的树边。 数据保证一定是一棵树。

输出描述 输出包含一个整数，表示建木上神实的总数。 样例 输入 4 4 1 2 4 3 2 4 输出 7

样例说明

以节点4 为根的子树的节点有[1,2,3,4] 其中[1,2,4]是4的因子f[4]=3。 以节点 2 为根的子树的节点有[1,2]，其中[1,2]是2的因子f[2]=2。 以节点1 为根的子树的节点有[1]，其中[1]是1的因子，f[1]=1。 以节点3 为根的子树的节点有[3]，其中[3]是3的因子f[3]=1。 3+2+1+1=7

// gpt答案
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> graph;
vector<int> factors;
unordered_map<int, int> subtree_factors;

void dfs(int node, int parent) {
    factors[node] = 1;
    for (int child : graph[node]) {
        if (child != parent) {
            dfs(child, node);
            factors[node] += factors[child];
        }
    }
    subtree_factors[node] = factors[node];
}

int main() {
    int n, x;
    cin >> n >> x;

    graph.resize(n + 1);
    factors.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(x, 0);

    long long total = 0;
    for (auto& entry : subtree_factors) {
        total += entry.second;
    }

    cout << total << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

unordered_map<int, vector<int>> graph;
int ans = 0;

vector<int> getDivisors(int n) {
    vector<int> res;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) {
                res.push_back(n / i);
            }
        }
    }
    return res;
}

void dfs(int node, int parent, unordered_map<int, int>& counts) {
    vector<int> divisors = getDivisors(node);
    for (int div : divisors) {
        counts[div]++;
    }
    ans += counts[node];

    for (int next : graph[node]) {
        if (next != parent) {
            dfs(next, node, counts);
        }
    }

    for (int div : divisors) {
        counts[div]--;
    }
}

int main() {
    int n, x;
    cin >> n >> x;

    for (int i = 1; i <= n; i++) {
        graph[i] = vector<int>();
    }

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    unordered_map<int, int> counts;
    dfs(x, -1, counts);
    cout << ans << endl;

    return 0;
}

23-03-17 米哈游后端笔试题

#include <iostream>
#include <string>
using namespace std;

void solve(int number[][100], int i, int j, int n, int m, int color);

int main() {
    int n, m;
    cin >> n >> m;
    cin.ignore();
    string str;
    getline(cin, str);
    int number[n][100];
    int numberF[n][100];
    int nn = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char temp = str[nn];
            if (temp == 'R'){
                number[i][j] = 1;
                numberF[i][j] = 1;
            } else if (temp == 'G'){
                number[i][j] = 2;
                numberF[i][j] = 2;
            } else {
                number[i][j] = 3;
                numberF[i][j] = 2;
            }
            nn++;
        }
    }
    int truth= 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (number[i][j] == 0){
                continue;
            } else {
                truth++;
                solve(number, i, j, n, m, number[i][j]);
            }
        }
    }
    int fake = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (numberF[i][j] == 0){
                continue;
            } else {
                fake++;
                solve(numberF, i, j, n, m, numberF[i][j]);
            }
        }
    }
    cout << truth - fake << endl;
    return 0;
}

void solve(int number[][100], int i, int j, int n, int m, int color){
    number[i][j] = 0;
    //上
    if (i - 1 >= 0){
        if (number[i - 1][j] == color){
            solve(number, i - 1, j, n, m, color);
        }
    }
    //下
    if (i + 1 < n){
        if (number[i + 1][j] == color){
            solve(number, i + 1, j, n, m, color);
        }
    }
    //左
    if (j - 1 >= 0){
        if (number[i][j - 1] == color){
            solve(number, i, j - 1, n, m, color);
        }
    }
    //右
    if (j + 1 < m){
        if (number[i][j + 1] == color){
            solve(number, i, j + 1, n, m, color);
        }
    }
    return;
}

23-04-10 华为后端笔试真题

1. 云服务计费

编写一个程序为某云服务计算客户话单，输入为某云服务的计费日志和各种计费因子的计费单价的列表，计费日志内容包含时间戳、客户标识、计费因子、计费时长4个字段。日志中如果同一客户同一计费因子在相同时间戳上报多次话单只能计费一次，选先上报的日志计费。计算每个客户的话单总费用。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB,其他语言: 512MB

输入

第1行表示计费日志的条数n，是一个正整数，范围是1<=n<=1000

第2到n+1行表示云服务的计费日志，共4列，第1列表示时间戳(是一个数字字符串，长度为10) 、第2列表示客户标识(是一个字符串，长度为1-16)，第3列表示计费因子 (是一个字符串，长度为1-16，计费因子查不到时认为计费因子单价是0），第四列表示计费时长时长（范围为0-100，当计费时长不在范围内要认为是计费日志有问题，当成计费为0处理)，这4个字段使用逗号分隔

第n+2行表示计费因子的数量m，m是一个正整数，范围是1<=m<=100

第n+3到n+3+m行表示各种计费因子的计费单价的列表，该表有2列,第1列表示计费因子 (是一个字符串，长度为1-16)，第2列表示单价(是一个正整数，范围为1~100)，这2个字段使用逗号分

输出

每个客户的话单总费用,共2列，第1列表示客户名，第2列表示话单费用，2列用逗号分割，输出按客户标识字典序升序排序

样例

输入

5
1627845600,client1,factorA,10
1627845605,client2,factorB,15
1627845610,client1,factorA,5
1627845610,client1,factorB,8
1627845620,client2,factorB,20
2
factorA,5
factorB,7

输出

client1,131
client2,245

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
string s[N];                      // 存储输入的n个字符串
unordered_map<string, int> value; // 不同节点对应的单价
unordered_map<string, int> info;  // 时间戳+名字+节点（这边可以用set）
unordered_map<string, int> cost;  // 不同用户对应的消费
vector<string> nameall;           // 所有用户的名字
int main()
{
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string str, str1, str2;
        cin >> str;
        int len = str.length();
        // 存储不同节点对应的单价
        for (int j = 0; j < len; j++)
        {
            if (str[j] == ',')
            {
                str1 = str.substr(0, j);           // 节点
                str2 = str.substr(j + 1, len - j); // 单价
                // cout<<str1<<" "<<str2<<endl;
                int t = stoi(str2);
                value[str1] = t;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        int len = s[i].length();
        int cnt = 0;    // 逗号的个数
        int d1, d2, d3; // 第1、2、3个逗号的下标
        for (int j = 0; j < len; j++)
        {
            if (s[i][j] == ',')
            {
                if (cnt == 0)
                    d1 = j;
                else if (cnt == 1)
                    d2 = j;
                else if (cnt == 2)
                    d3 = j;
                cnt++;
            }
        }
        // cout<<"d1="<<d1<<"d2="<<d2<<"d3="<<d3<<endl;
        string name = s[i].substr(d1 + 1, d2 - d1 - 1);
        bool sign = false;
        for (auto t : nameall)
        {
            if (t == name)
                sign = true;
        }
        if (!sign)
            nameall.push_back(name);
        string ti = s[i].substr(0, d1);
        string factor = s[i].substr(d2 + 1, d3 - d2 - 1);
        string hhour = s[i].substr(d3 + 1, len - d3 - 1);
        int hour = stoi(hhour);
        if (hour < 0 || hour > 100)
            hour = 0; // 题目要求不在范围按0算
        string inf = ti + name + factor;
        if (info[inf] == 0) // 题目要求，如果有同一时间同一用户同一节点重复信息，只算第一个
        {
            cost[name] = cost[name] + value[factor] * hour;
            info[inf] = 1;
        }
        // cout<<"name="<<name<<"facotr="<<factor<<"hour="<<hour<<endl;
    }
    sort(nameall.begin(), nameall.end());
    for (auto name : nameall)
    {
        cout << name << "," << cost[name] << endl;
    }
    return 0;
}

2. 相似图片分类

小明想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类:

1)相似度>0表示两张图片相似，

2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度

3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0.给定一个大小为NxN的矩阵M存储任意两张图片的相似度，M[i][j]即为第i个图片和第j个图片的相似度，请按照"从大到小”的顺序返回每个相似类中所有图片的相似度之和。

输入

第一行一个数N，代表矩阵M中有N个图片，下面跟着N行，每行有N列数据，空格分隔(为了显示整弃，空格可能为多个) 代表N个图片之间的相似度。

约束：1.0<N<=900
0<=M[i][j]<=100,输入保证M[i][i] =0,M[i][j]=M[j][i]

输出

每个相似类的相似度之和。格式为:一行数字，分隔符为1个空格。

样例

输入

5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0

输出

65 25

考试代码忘记保存了，下面是考完后复盘再写的。

#include<bits/stdc++.h>
using namespace std;
const int N = 910;
int idx = 0;         // 目前算到第几个集合
int g[N][N];         // 存图
vector<int>v[N];     // 邻接矩阵
vector<int>res;      // 每个集合对应的相似值之和
vector<int>jihe[N];  // 每个集合的点
bool st[N];          // 是否结束访问
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> g[i][j];
            if (g[i][j])
                v[i].push_back(j);
        }
    }

    for (int i = 0; i < n; i++)
    {
        // 如果邻接矩阵为空说明没有相似的图，自成一派
        if (v[i].size() == 0)
        {
            //cout<<"i="<<i<<",idx="<<idx<<endl;
            st[i]=true;
            jihe[idx++].push_back(i); // 一开始没加进去，只能过32%数据点
            continue;
        }
        if (st[i])
            continue;
        //cout<<"i="<<i<<",idx="<<idx<<endl;
        queue<int> q;
        q.push(i);
        st[i]=true;
        jihe[idx].push_back(i);
        // bfs展开
        while (q.size())
        {
            int t = q.front();
            q.pop();
            st[t] = true;
            for (auto x : v[t])
            {
                if (!st[x])
                {
                    q.push(x);
                    jihe[idx].push_back(x);
                }
            }
        }
        idx++;

    }
    // 计算每一个集合的相似值之和
    for (int i = 0; i < idx; i++)
    {
        int t = 0, len = jihe[i].size();
        for (int j = 0; j < len; j++)
        {
            for (int k = j + 1; k < len; k++)
            {
                int x = jihe[i][j], y = jihe[i][k];
                t += g[x][y];
            }
        }
        res.push_back(t);
    }
    /*debug检查每个集合是否正确
    for (int i = 0; i < idx; i++)
    {
        cout << "jihe[" << i << "]:";
        for (auto x : jihe[i])
            cout << x;
        cout << endl;
    }
    cout << "idx=" << idx << endl;
    */
    // 降序且输出
    sort(res.begin(), res.end(), cmp);
    int len = res.size();
    for (int i = 0; i < len - 1; i++)
        cout << res[i] << " ";
    cout << res[len - 1];
    return 0;
}

3. 网络保卫战

公有云的某个region内，N个网络节点组网情况可以使用一个n* n的矩阵matrix表示，在这个组网图中，matrix[i][j] = p 时，表示用户在编号为 i的节点访问编号为j的节点时，必须在 i节点上具有>=p 的权限等级(p=0时表示无法通过第i节点访问j节点)，如果用户成功访问了j节点，那么它在j节点上的权限等级调整为 P。

exposed 为一个整数数组，表示暴露在公网上的网络节点的编号列表。某天扫描发现这批暴需在公网的节点存在被外部恶意攻击风险且该攻击会影响到可访问的其他节点，并可以持续传递进行攻击，被恶意攻击的节点从公网访问时，攻击者获得了ROOT 权限(权限等级为10，即最大值)。

小李是一名网络安全工程师，为了在有限的时间内尽可能的减少故障带来的损失，需要立即将某个节点从公网"下线"。

假设攻击结束时，被攻击过的节点数量为R，请帮小李计算出将哪个节点下线能使R尽可能小，如果答案有多个节点，返回索引最小的那个节点。

请注意：从公网“下线”的节点，不会受到来自公网的攻击，但仍然可能被“可访问”的其他节点传递攻击。

解答要求

时间限制: C/C++ 5000ms,其他语言: 10000ms内存限制: C/C++ 128MB，其他语言: 256MB

输入

输入的第一行是网络节点数量N后续的N行，每行N个数字v，以空格分割，形成一个N*N的矩阵，表示网络节点组网的矩阵。最后一行，输入 exposed 数组，表示暴露在公网上的网络节点的编号列表，数组元素不会重复。输入范围说明：
2<=n<=24
0<=v<=10
0<=exposed[i]<=n-1

输出

输出在 exposed 数组中，计划"下线”的那个节点的编号。

样例1

输入

4
1 0 0 0
0 1 2 0
0 1 1 4
0 0 3 1
1 3

输出

3

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

int simulateAttack(int n, const vector<vector<int>>& matrix, const vector<int>& exposed, int offlineNode) {
    vector<bool> attacked(n, false);
    queue<int> q;
    // 初始化攻击，排除下线的节点
    for (int node : exposed) {
        if (node != offlineNode) {
            q.push(node);
            attacked[node] = true;
        }
    }
    // 广度优先搜索模拟攻击过程
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < n; ++i) {
            if (!attacked[i] && matrix[current][i] > 0 && matrix[current][i] <= 10) {
                attacked[i] = true;
                q.push(i);
            }
        }
    }
    // 计算被攻击的节点数量
    int count = 0;
    for (bool status : attacked) {
        if (status) ++count;
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }
    int e;
    cin >> e;
    vector<int> exposed(e);
    for (int i = 0; i < e; ++i) {
        cin >> exposed[i];
    }

    int minAttacked = numeric_limits<int>::max();
    int nodeToOffline = -1;
    for (int node : exposed) {
        int attacked = simulateAttack(n, matrix, exposed, node);
        if (attacked < minAttacked) {
            minAttacked = attacked;
            nodeToOffline = node;
        }
    }

    cout << nodeToOffline << endl;

    return 0;
}