# LeetCode 463. 岛屿的周长

LeetCode 463. Island Perimeter

给定一个 row x col 的二维网格地图 grid ，其中： grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域

网格中的格子 水平 和 垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）

岛屿中没有 “湖”（“湖” 是指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

输入：grid = [[1,0]]
输出：4

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 为 0 或 1

# Method 1: 模拟

# 算法思路

对于一个岛屿格子的每条边：如果这条边为网格的边界，或者这条边是岛屿与水域的分界线，则需将这条边计入岛屿的周长

因此，可以遍历每个岛屿格子，看其四个方向的边是否为网格边界或水域分界线，如果是，则计入岛屿周长

# 代码实现

int islandPerimeter(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 0) continue;
            for (int k = 0; k < 4; ++k) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                if (x == -1 || x == m || y == -1 || y == n) ++res; // 网格边界
                else if (grid[x][y] == 0) ++res;                   // 水域分界线
            }
        }
    }
    return res;
}

# 复杂度分析

时间复杂度：$O(m \times n)$，其中，$m$ 和 $n$ 分别为网格的行数和列数

空间复杂度：$O(1)$

# Method 2: 深度优先搜索

# 算法思路

可以将方法一改成深度优先搜索遍历的方式（该方式可以拓展至多个岛屿情形）

其中，为避免岛屿格子被重复遍历，需要将已经遍历过的岛屿格子标记。特别地，可以将已经遍历过的岛屿格子的值置为 -1 （不能置为 0，因为置 0 会形成新的 “水域边界线”，进而导致结果出错）

# 代码实现

vector<vector<int>> dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};

int dfs(vector<vector<int>>& grid, int x, int y) {
    int m = grid.size();
    int n = grid[0].size();
    if (x == -1 || x == m || y == -1 || y == n) return 1;
    if (grid[x][y] == 0) return 1;
    if (grid[x][y] == -1) return 0;
    grid[x][y] = -1;
    int count = 0;
    for (int k = 0; k < 4; ++k) {
        int newx = x + dir[k][0];
        int newy = y + dir[k][1];
        count += dfs(grid, newx, newy);
    }
    return count;
}

int islandPerimeter(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1)
                ans += dfs(grid, i, j);
        }
    }
    return ans;
}

# 复杂度分析

时间复杂度：$O(m \times n)$，其中，$m$ 和 $n$ 分别为网格的行数和列数

空间复杂度：$O(m \times n)$

参考：力扣官方题解

# LeetCode 48. 旋转图像

48. Rotate Image

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• $1 \le$ n $\le 20$
• $-1000 \le$ matrix[i][j] $\le 1000$

# Method 1: 原地旋转

经过观察，可以发现：

• 原矩阵中的位置 $matrix[i][j]$ ，旋转后的目标位置为 $matrix[j][n - i - 1]$

• 原矩阵中的位置 $matrix[j][n - i - 1]$ ，旋转后的目标位置为 $matrix[n - i - 1][n - j - 1]$

• 原矩阵中的位置 $matrix[n - i - 1][n - j - 1]$ ，旋转后的目标位置为 $matrix[n - j - 1][i]$

• 原矩阵中的位置 $matrix[n - j - 1][i]$ ，旋转后的目标位置为 $matrix[i][j]$

即，对于 $matrix[i][j]$ 、$matrix[j][n - i - 1]$ 、$matrix[n - i - 1][n - j - 1]$ 、$matrix[n - j - 1][i]$ 而言，每一项旋转后的位置就是下一项所在的位置

因此，可以引入一个临时变量 tmp ，完成这四项的原地交换

int tmp = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = matrix[i][j];
matrix[i][j] = tmp;

那么，我们应该枚举哪些 $i$ 和 $j$ 呢？

每一次可以交换四个位置的元素：

• 当 $n$ 为偶数时，此时需要枚举 $n^2 / 4 = (n / 2) \times (n / 2)$ 个位置。因此，$i$ 和 $j$ 分别遍历 $n / 2$ 个位置，以 $4 \times 4$ 矩阵为例

• 当 $n$ 为奇数时，由于中心位置始终不变，需要枚举 $(n^2 - 1) / 4 = ((n - 1) / 2) \times ((n + 1) / 2)$ 个位置。因此，i 遍历 $(n - 1) / 2$ 个位置、j 遍历 $(n + 1) / 2$ 个位置，以 $5 \times 5$ 矩阵为例

因此，无论 $n$ 是奇数还是偶数，均可按照 “ $i$ 遍历 $n / 2$ 个位置、$j$ 遍历 $(n + 1) / 2$ 个位置 ” 来处理，即， i 遍历 [0, n / 2) ， j 遍历 [0, (n + 1) / 2)

代码实现：

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < (n + 1) / 2; j++) {
            int tmp = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = matrix[i][j];
            matrix[i][j] = tmp;
        }
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

# Method 2: 翻转

算法思路：

首先进行上下翻转，然后进行对角线翻转（即，转置）

理论推导：

对于上下翻转：只需要枚举矩阵上半部分的元素，并将其与下半部分对应位置的元素进行交换，即

$$matrix[i][j] \longleftrightarrow matrix[n - i - 1][j]$$

对于对角线翻转：只需要枚举对角线左侧的元素，并将其与右侧对应位置的元素进行交换，即

$$matrix[i][j] \longleftrightarrow matrix[j][i]$$

联立以上两式可得

$$matrix[i][j] \longrightarrow matrix[n - i - 1][j] \longrightarrow matrix[j][n - i - 1]$$

即，实现了将 $matrix[i][j]$ 旋转 90 度、放到 $matrix[j][n - i - 1]$ 位置

代码实现：

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n / 2; i++) { // 上下翻转
        for (int j = 0; j < n; j++) {
            swap(matrix[i][j], matrix[n - i - 1][j]);
        }
    }
    for (int i = 0; i < n; i++) {     // 对角线翻转
        for (int j = 0; j < i; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

参考：leetcode-solution

# LeetCode 59. 螺旋矩阵 II

LeetCode 59. Spiral Matrix II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• $1 \le$ n $\le 20$

# Method: 模拟

思路：模拟 顺时针画矩阵的过程，即

• 填充上行从左到右

• 填充右列从上到下

• 填充下行从右到左

• 填充左列从下到上

由外向内一圈一圈这么画下去

注意：每画一条边都要坚持一致的 左闭右开 ，或者 左开又闭 的原则，这样这一圈才能按照统一的规则画下来

坚持 循环不变量 原则

下图以左闭右开原则为例：每一种颜色，代表一条边，注意每一个拐角处的处理规则，拐角处让给新的一条边来继续画（即，每条边都遵循左闭右开原则）

代码实现：

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    int num = 1;                        // 填充的数字
    for (int i = 0; i < n / 2; ++i) {   // 每次循环填充一圈
        int start = i;                  // 填充的起点
        int len = n - i * 2 - 1;        // 每个方向的填充长度
        for (int j = 0; j < len; ++j) { // 上面一行，从左往右填充
            matrix[start][start + j] = num++;
        }
        for (int j = 0; j < len; ++j) { // 右边一列，从上往下填充
            matrix[start + j][start + len] = num++;
        }
        for (int j = len; j >= 1; --j) { // 下面一行，从右往左填充
            matrix[start + len][start + j] = num++;
        }
        for (int j = len; j >= 1; --j) { // 左边一列，从下往上填充
            matrix[start + j][start] = num++;
        }
    }
    if (n % 2) matrix[n / 2][n / 2] = n * n; // n 为奇数，数组最中间的位置需要单独处理

    return matrix;
}

时间复杂度：$O(n^2)$，需要填充 $n^2$ 个元素

空间复杂度：$O(n^2)$

参考：代码随想录：螺旋矩阵 II

# LeetCode 621. 任务调度器

621. Task Scheduler

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算 完成所有任务所需要的最短时间 。

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：
A -> B -> idle -> A -> B -> idle -> A -> B

示例 2：

输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类

示例 3：

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• $1 \le$ task.length $\le 10^4$
• tasks[i] 是大写英文字母
• n 的取值范围为 $[0, 100]$

# Method: 桶思想

# 算法思路

使用一个宽为 $n + 1$ 的矩阵来展示任务执行方案，其中，任务按照逐行遍历的顺序执行，空白格子对应 CPU 的待命状态

于是，可以将具有最大数量的任务排布在矩阵的第一列，将其余任务依次排布成列。由于冷却时间为 $n$，上述排列方案可以保证满足题目要求，并且总时间最小

• 情况一：冷却时间长、任务种类和数量很少，假设所有任务种类中的最大数量为 $\textrm{maxn}$（即，矩阵的行数），具有最大数量的任务的种类数为 $\textrm{cnt}$（即，矩阵最后一行的任务数量），则执行任务所需的时间为 (\textrm{maxn} - 1) \times (n + 1) + \textrm

  • 示例 1：
  • 示例 3：

• 情况二：冷却时间短、任务种类或数量很多，可以拓展矩阵的列数，并将任务排布在拓展的列中。此时，每个任务之间都不存在待命时间，因此，执行任务所需的时间就是任务的数量，即 $\vert \textrm{tasks} \vert$

因此，需要的最少时间为 $\max{(\vert \textrm{tasks} \vert, (\textrm{maxn} - 1) \times (n + 1) + \textrm{cnt})}$

具体可参考 popopop

# 代码实现

int leastInterval(vector<char>& tasks, int n) {
    vector<int> rec(26, 0);
    for (auto c : tasks) // 记录每种任务的数量
        ++rec[c - 'A'];
    int maxn = 0;        // 任务的最大数量
    int cnt = 0;         // 具有最大数量的任务种类数
    for (int num : rec) {
        if (num > maxn) {
            maxn = num;
            cnt = 1;
        } else if (num == maxn) {
            ++cnt;
        }
    }
    return max((int)tasks.size(), (maxn - 1) * (n + 1) + cnt);
}

# 复杂度分析

时间复杂度：$O(n + \vert \Sigma \vert)$，其中，$n$ 为数组 tasks 的长度，$\vert \Sigma \vert$ 为数组 tasks 中可能出现的任务种类数

空间复杂度：$O(\vert \Sigma \vert)$

参考：

• popopop
• leetcode-solution