模拟

前言

模拟算法其实就是根据题目做，题目要求什么，就做什么。

一、数据结构

对于模拟题而言，最关键的其实是数据结构，看到一个问题，选择合适的数据结构，然后根据问题来实现对应的功能。模拟题的常见数据结构主要就是：数组、字符串、矩阵、链表 等等。

1、基于数组

利用数组的数据结构，根据题目要求，去实现算法，如：1920. 基于排列构建数组、1389. 按既定顺序创建目标数组、1603. 设计停车系统、2149. 按符号重排数组、2221. 数组的三角和

2、基于字符串

利用字符串的数据结构，根据题目要求，去实现算法，如：2011. 执行操作后的变量值、2744. 最大字符串配对数目、LCP 17. 速算机器人、537. 复数乘法

3、基于链表

利用链表的数据结构，根据题目要求，去实现算法，如：2181. 合并零之间的节点、1823. 找出游戏的获胜者

4、基于矩阵

利用矩阵的数据结构，根据题目要求，去实现算法，如：2120. 执行所有后缀指令、1252. 奇数值单元格的数目、832. 翻转图像、657. 机器人能否返回原点、289. 生命游戏、59. 螺旋矩阵 II、885. 螺旋矩阵 III

5、基于栈

利用栈的数据结构，如：1441. 用栈操作构建数组

6、基于队列

利用队列的数据结构，如：1700. 无法吃午餐的学生数量

二、算法技巧

模拟时一般会用到一些算法技巧，或者说混合算法，比如 排序、递归、迭代 等等。

1、排序

排序后，干一件事情，如：950. 按递增顺序显示卡牌

2、递归

需要借助递归来实现，如：1688. 比赛中的配对次数 、2169. 得到 0 的操作数、258. 各位相加

3、迭代

不断迭代求解，其实就是利用 while 循环来实现功能，如：1860. 增长的内存泄露、258. 各位相加

三、实例

  1. 1252. 奇数值单元格的数目 - 力扣（LeetCode）

题目

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

  1. ri 行上的所有单元格，加 1 。
  2. ci 列上的所有单元格，加 1 。

给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。

思路

按要求进行操作即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int oddCells(int m, int n, int** indices, int indicesSize, int* indicesColSize) {
    int i, j, r, c;
    int mat[110][110];
    int ans = 0;

    memset(mat, 0, sizeof(mat));

    for(i = 0; i < indicesSize; ++i) {
        r = indices[i][0];
        c = indices[i][1];
        for(j = 0;j < m; ++j) {
            mat[j][c]++;
        }
        for(j = 0; j < n; ++j) {
            mat[r][j]++;
        }
    }

    for(i = 0; i < m; ++i){
        for(j = 0; j < n; ++j) {
            if(mat[i][j] & 1) ans++;
        }
    }

    return ans;
}
  1. 537. 复数乘法 - 力扣（LeetCode）

题目

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

  • 实部 是一个整数，取值范围是 [-100, 100]
  • 虚部 也是一个整数，取值范围是 [-100, 100]
  • i2 == -1

给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

思路

由于直接从头到尾模拟将会耗费大量时间且毫无意义（实现读取实部和虚部的函数，实现字符串转数字的函数，还有他们的反函数等等），因此在这里采取格式化的措施。优点是简洁易读，缺点是效率不咋地。

代码

1
2
3
4
5
6
7
8
char* complexNumberMultiply(char* num1, char* num2) {
    int real1, imag1, real2, imag2;
    sscanf(num1, "%d+%di", &real1, &imag1);
    sscanf(num2, "%d+%di", &real2, &imag2);
    char *ans = (char *)malloc(sizeof(char) * 100);
    sprintf(ans, "%d+%di", real1 * real2 - imag1 * imag2, real1 * imag2 + real2 * imag1);
    return ans;
}