C++ 算法之螺旋矩阵生成

2024-08-10

本文作者原创，首发在本博客；CSDN 上的同名文章已标注为转载并回链到本页：https://blog.csdn.net/qq_30220519/article/details/141098405

代码

#include <fmt/core.h>

#include "io.h"
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < starty + n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < startx + n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 2;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

int main() {
    Solution solution;
    auto rets = solution.generateMatrix(6);
    // 打印二维数组
    for (int i = 0; i < rets.size(); ++i) {
        for (int j = 0; j < rets[i].size(); ++j) {
            fmt::print("{:02d} ",  rets[i][j]);
        }
        fmt::print("\n");
    }
}

输出

01 02 03 04 05 06 
20 21 22 23 24 07 
19 32 33 34 25 08 
18 31 36 35 26 09 
17 30 29 28 27 10 
16 15 14 13 12 11

效果

优化

#include <fmt/core.h>


/*
 * 获取圈数
 */
int getScrewNums(int r, int c) {
    auto shortV = std::min(r, c);
    return  shortV / 2 + shortV % 2;
}

/*
 * 获取列
 */
int getsubCSize(int c, int n) {
    return (c - n*2);
}

/*
 * 获取行
 */
int getSubRSize(int r, int n) {
    return (r - n*2);
}

void printMatrix(int* matrix, int r, int c) {
    // 打印二维数组
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            fmt::print("{:02d} ", matrix[i * c + j]);
        }
        fmt::print("\n");
    }
}

/*
 * 获取每个圈元素个数
 */
int getElementNums(int r, int c, int n) {
    int times = 2;
    auto rowNums = getSubRSize(r, n);
    auto colNums = getsubCSize(c, n);   
    if(0 == rowNums || 0 == colNums)
        times = 1;
    return (rowNums + colNums) * times;
}

/*
 * 创建螺旋矩阵单圈
 */
void createScrewMatrix(int* matrix, int r, int c, int n, int& val) {
    auto startR = n;
    if(startR > (r/2 + r%2))
        startR = (r/2 + r%2);
    auto startC = n;
    if(startC > (c/2 + c%2))
        startC = (c/2 + c%2);        
    int* subMatrix = &matrix[startR* c + startC];
    auto subRSize = r - n*2;
    auto subCSize = c - n*2;
    //fmt::print("R{:02d} C{:02d}\n", subRSize, subCSize);
    //fmt::print("startR{:02d} startC{:02d} \n",startR, startC);
    if(0 == subRSize && 0 == subCSize)
        return;
    if(0 == subRSize)
        subRSize = 1;
    if(0 == subCSize)
        subCSize = 1;        
    // 单个
    if(1 == subRSize && 1 == subCSize) {
        subMatrix[0] = val++;
    } else if (1 == subRSize){ // 单行
        for(int i = 0; i < subCSize; ++i) {
            subMatrix[i] = val++;
        }
    } else if(1 == subCSize) { // 单列
        for(int i = 0; i < subRSize; ++i) {
            //fmt::print("Index{:02d}\n", (startR + i)* c + startC);
            matrix[(startR + i)* c + startC] = val++;
        }
    } else {   // 多行多列
        // 顶部
        for(int i = 0; i < subCSize - 1; ++i) {
            subMatrix[i] = val++;
        }

        // 右侧
        for(int i = 0; i < subRSize - 1; ++i) {
            matrix[(startR + i)* c + startC + subCSize - 1] = val++;
        }

        // 底部
        for(int i = subCSize - 1; i > 0; --i) {
            matrix[(startR + subRSize - 1)* c + startC + i] = val++;
        } 

        // 左侧
        for(int i = subRSize - 1; i > 0; --i) {
            matrix[(startR + i)* c + startC] = val++;
        }
    }

}


/*
 * 创建一个螺旋矩阵
 */
int main() {
    int r = 10;
    int c = 10;
    int maxNum = 0;
    auto matrix = new int[r*c];
    auto screwNums = getScrewNums(r, c);
    fmt::print("screwNums{:02d}\n",screwNums);    
    for(int i = 0; i < screwNums; ++i) {
        createScrewMatrix(matrix, r, c, i, maxNum);
        printMatrix(matrix, r, c);
    }
    delete[] matrix;
    return 0;
}

过程推导

00 01 02 03 04        00 01 02 03 04 00 01 02 03 04

15 00 00 00 05        15 16 17 18 05 15 16 17 18 05

14 00 00 00 06        14 23 00 19 06 14 23 24 19 06

13 00 00 00 07        13 22 21 20 07 13 22 21 20 07

12 11 10 09 08        12 11 10 09 08 12 11 10 09 08

00 01 02 03 04 05        00 01 02 03 04 05

13 00 00 00 00 06        13 14 15 16 17 06

12 11 10 09 08 07        12 11 10 09 08 07

00 01 02 03 04 05 06 07 08 09                        00 01 02 03 04 05 06 07 08 09

35 00 00 00 00 00 00 00 00 10                        35 36 37 38 39 40 41 42 43 10

34 00 00 00 00 00 00 00 00 11                        34 63 64 65 66 67 68 69 44 11

33 00 00 00 00 00 00 00 00 12                        33 62 83 84 85 86 87 70 45 12

32 00 00 00 00 00 00 00 00 13                        32 61 82 95 96 97 88 71 46 13

31 00 00 00 00 00 00 00 00 14 ……   31 60 81 94 99 98 89 72 47 14

30 00 00 00 00 00 00 00 00 15   30 59 80 93 92 91 90 73 48 15

29 00 00 00 00 00 00 00 00 16                        29 58 79 78 77 76 75 74 49 16

28 00 00 00 00 00 00 00 00 17 28 57 56 55 54 53 52 51 50 17

27 26 25 24 23 22 21 20 19 18                        27 26 25 24 23 22 21 20 19 18

参考

https://github.com/youngyangyang04/leetcode-master

代码

输出

效果

优化

过程推导

参考

创作不易，小小的支持一下吧！