首页Coding

# 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 = <!--swig0-->;
    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×n)O(m \times n)，其中，mm 和 nn 分别为网格的行数和列数

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

# Method 2: 深度优先搜索

# 算法思路

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

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

# 代码实现

vector<vector<int>> dir = <!--swig1-->;
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×n)O(m \times n)，其中，mm 和 nn 分别为网格的行数和列数


空间复杂度：O(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≤1 \le  n  ≤20\le 20
    • 

  • −1000≤-1000 \le  matrix[i][j]  ≤1000\le 1000
    • 



# Method 1: 原地旋转


经过观察，可以发现：


    

  • 

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

    • 

  • 

    原矩阵中的位置 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−i−1][n−j−1]matrix[n - i - 1][n - j - 1] ，旋转后的目标位置为 matrix[n−j−1][i]matrix[n - j - 1][i]
    

    • 

  • 

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

    • 



即，对于 matrix[i][j]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] 而言，每一项旋转后的位置就是下一项所在的位置


因此，可以引入一个临时变量  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;
那么，我们应该枚举哪些 ii 和 jj 呢？


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


    

  • 

    当 nn 为偶数时，此时需要枚举 n2/4=(n/2)×(n/2)n^2 / 4 = (n / 2) \times (n / 2) 个位置。因此，ii 和 jj 分别遍历 n/2n / 2 个位置，以 4×44 \times 4 矩阵为例
    

    

    • 

  • 

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

    

    • 



因此，无论 nn 是奇数还是偶数，均可按照 “ ii 遍历 n/2n / 2 个位置、jj 遍历 (n+1)/2(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(n2)O(n^2)


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


# Method 2: 翻转


算法思路：


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


理论推导：


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


matrix[i][j]⟷matrix[n−i−1][j]matrix[i][j] \longleftrightarrow matrix[n - i - 1][j]



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


matrix[i][j]⟷matrix[j][i]matrix[i][j] \longleftrightarrow matrix[j][i]



联立以上两式可得


matrix[i][j]⟶matrix[n−i−1][j]⟶matrix[j][n−i−1]matrix[i][j] \longrightarrow matrix[n - i - 1][j] \longrightarrow matrix[j][n - i - 1]



即，实现了将 matrix[i][j]matrix[i][j] 旋转 90 度、放到 matrix[j][n−i−1]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(n2)O(n^2)


空间复杂度：O(1)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≤1 \le  n  ≤20\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(n2)O(n^2)，需要填充 n2n^2 个元素


空间复杂度：O(n2)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≤1 \le  task.length  ≤104\le 10^4
    • 

  • tasks[i]  是大写英文字母
    • 

  • n  的取值范围为 [0,100][0, 100]
    • 



# Method: 桶思想


# 算法思路


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


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


    

  • 

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

      

    • 示例 1： 
      • 

    • 示例 3： 
      • 

    

    • 

  • 

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

      

      • 

    

    • 



因此，需要的最少时间为 max⁡(∣tasks∣,(maxn−1)×(n+1)+cnt)\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+∣Σ∣)O(n + \vert \Sigma \vert)，其中，nn 为数组 tasks 的长度，∣Σ∣\vert \Sigma \vert 为数组 tasks 中可能出现的任务种类数


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


参考：