【免费题库】华为OD机试 - 螺旋数字矩阵（Java & JS & Python & C & C++）

在编程面试和技术竞赛中，算法题目是一个重要的考察维度，其中“螺旋数字矩阵”是比较经典的题目之一。本文将通过该题目，深入探讨如何使用多种编程语言实现它，尤其是Java、JavaScript、Python、C以及C++。首先，我们需要明确什么是“螺旋数字矩阵”。

螺旋数字矩阵的定义

螺旋数字矩阵指的是按照“螺旋”的方向将数字从1到n填充到一个二维矩阵中。例如，对于给定的输入n=3，应该生成如下矩阵：

1  2  3
8  9  4
7  6  5

实现思路

1. 定义矩阵：首先，我们需要定义一个n x n的二维数组。
2. 边界控制：使用左、右、上、下四个边界来控制填充的范围，并在每次填充后逐步收缩边界。
3. 控制方向：我们需要定义填充的方向，初始为从左到右，然后顺时针依次为下、右、上。

接下来，我将为不同编程语言提供实现示例。

Java 实现

public class SpiralMatrix {
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int num = 1;

        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) matrix[top][i] = num++;
            top++;
            for (int i = top; i <= bottom; i++) matrix[i][right] = num++;
            right--;
            if (top <= bottom) {
                for (int i = right; i >= left; i--) matrix[bottom][i] = num++;
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) matrix[i][left] = num++;
                left++;
            }
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] result = generateMatrix(n);
        for (int[] row : result) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

Python 实现

def generate_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    left, right, top, bottom = 0, n - 1, 0, n - 1
    num = 1

    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1
        if top <= bottom:
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
    return matrix

# 示例
n = 3
result = generate_matrix(n)
for row in result:
    print(" ".join(map(str, row)))

C++ 实现

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

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n));
    int left = 0, right = n - 1, top = 0, bottom = n - 1;
    int num = 1;

    while (left <= right && top <= bottom) {
        for (int i = left; i <= right; i++) matrix[top][i] = num++;
        top++;
        for (int i = top; i <= bottom; i++) matrix[i][right] = num++;
        right--;
        if (top <= bottom) {
            for (int i = right; i >= left; i--) matrix[bottom][i] = num++;
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) matrix[i][left] = num++;
            left++;
        }
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> result = generateMatrix(n);
    for (const auto& row : result) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

总结

“螺旋数字矩阵”是一个经典的编程题，涉及到二维数组的填充以及控制两层循环的边界。在该问题中，充分掌握数组的索引操作和方向控制是关键。通过本文的实现示例，读者可以在不同的编程语言环境中灵活使用此算法，为解决其他类似问题打下良好的基础。希望通过这篇文章能够帮助大家更好地理解和掌握这个有趣的算法题。