1. AI技术聚合首页
  2. IT

【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【模拟/递归】2023C-螺旋数字矩阵【欧弟算法】全网注释最详细分类最全的华为OD真题题解

心中带点小风骚 • • IT • 阅读 25

文章目录

  • 题目描述与示例
    • 题目描述
    • 输入描述
    • 输出描述
    • 示例
      • 输入
      • 输出
  • 解题思路
  • 代码
    • Python
    • Java
    • C++
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述

疫情期间，小明隔离在家，百无聊赖，在纸上写数字玩。

他发明了一种写法：给出数字个数n和行数m (0 < n < 999，0 < m < 999)，从左上角的1开始，按照顺时针螺旋向内写方式，依次写出2, 3, ..., n，最终形成一个m行矩阵。

小明对这个矩阵有些要求：

  1. 每行数字的个数一样多
  2. 列的数量尽可能少
  3. 填充数字时优先填充外部
  4. 数字不够时，使用单个*号占位

输入描述

两个整数，空格隔开，依次表示n、m

输出描述

符合要求的唯一短阵

示例

输入

9 4

输出

1 2 3
* * 4
9 * 5
8 7 6

解题思路

注意，本题和LeetCode54、螺旋矩阵非常类似。

本题既可以用迭代方法也可以用递归方法完成。本题解主要介绍递归方法。

题目要求矩阵列数尽可能少，很容易算出来最小的列数为c = ceil(n / m)。

注意到每次填充都优先填充矩阵的最外圈，比如对于5*5的矩阵，初始化均用*填充

* * * * *
* * * * *
* * * * *
* * * * *
* * * * *

假设需要填充21个数，那么第一圈会螺旋式地填充如下

1 2 3 4 5
16 * * * 6
15 * * * 7
14 * * * 8
13 12 11 10 9

中间剩余一个(5-2)*(5-2) = 3*3的未填充矩阵，那么可以从17开始继续螺旋式地填充第二层矩阵，直到到达21，即

1 2 3 4 5
16 17 18 19 6
15 * * 20 7
14 * * 21 8
13 12 11 10 9

显然每一次填充，都是从未填充矩阵的左上角开始填充其外层，直到填充完毕或到达规定数字。因此可以使用递归来完成上述过程。

代码

Python

# 题目：【模拟】2023C-螺旋矩阵
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟/递归
# 代码看不懂的地方，请直接在群上提问


from math import ceil

# 递归函数
# ans为答案螺旋矩阵
# start_i, end_i, start_j, end_j分别为子矩阵的起始、终止的i和j下标
# cur_num为未填充子矩阵左上角的第一个数
# n为终止数字
def help(ans, start_i, end_i, start_j, end_j, cur_num, n):
    # 如果不存在遍历区间，则不会进入下面四个for循环中的任意一个
    # 会持续进行递归，导致编译栈溢出
    # 这种情况就是当n为某个奇数的平方且c = m = sqrt(n)的时候会出现
    # 譬如填充5*5的矩阵且n = 25，最中间那个数字会出现的情况
    # 额外判断这种条件，将最中间的数字填充上并退出递归即可
    if start_i == end_i and start_j == end_j:
        ans[start_i][start_j] = cur_num
        return
    # 未填充矩阵的上边界：从左往右，固定start_i，正序遍历j
    for j in range(start_j, end_j):
        ans[start_i][j] = str(cur_num)
        cur_num += 1
        if cur_num > n: return
    # 未填充矩阵的右边界：从上往下，固定end_j，正序遍历i
    for i in range(start_i, end_i):
        ans[i][end_j] = str(cur_num)
        cur_num += 1
        if cur_num > n: return
    # 未填充矩阵的下边界：从右往左，固定end_i，逆序遍历j
    for j in range(end_j, start_j, -1):
        ans[end_i][j] = str(cur_num)
        cur_num += 1
        if cur_num > n: return
    # 未填充矩阵的做边界：从下往上，固定start_j，逆序遍历j
    for i in range(end_i, start_i, -1):
        ans[i][start_j] = str(cur_num)
        cur_num += 1
        if cur_num > n: return
    # 对未填充数组进行递归
    # start_i, end_i, start_j, end_j需要修改
    help(ans, start_i+1, end_i-1, start_j+1, end_j-1, cur_num, n)

# 输入数字n，行数m
n, m = map(int, input().split())
# 计算列数c，n除以m后向上取整
c = ceil(n / m)

# 初始化答案螺旋数组，先用"*"填充
ans = [["*"] * c for _ in range(m)]

# 递归入口：start_i, end_i, start_j, end_j
# 分别传入0, m-1, 0, c-1
help(ans, 0, m-1, 0, c-1, 1, n)
# 逐行输出螺旋矩阵
for row in ans:
    print(*row)

Java

import java.util.Scanner;

public class Main {
    // 递归函数
    // ans为答案螺旋矩阵
    // start_i, end_i, start_j, end_j分别为子矩阵的起始、终止的i和j下标
    // cur_num为未填充子矩阵左上角的第一个数
    // n为终止数字
    static void help(String[][] ans, int start_i, int end_i, int start_j, int end_j, int cur_num, int n) {
        // 如果不存在遍历区间，则不会进入下面四个for循环中的任意一个
        // 会持续进行递归，导致编译栈溢出
        // 这种情况就是当n为某个奇数的平方且c = m = sqrt(n)的时候会出现
        // 譬如填充5*5的矩阵且n = 25，最中间那个数字会出现的情况
        // 额外判断这种条件，将最中间的数字填充上并退出递归即可
        if (start_i == end_i && start_j == end_j) {
            ans[start_i][start_j] = String.valueOf(cur_num);
            return;
        }
        // 未填充矩阵的上边界：从左往右，固定start_i，正序遍历j
        for (int j = start_j; j <= end_j; j++) {
            ans[start_i][j] = String.valueOf(cur_num++);
            if (cur_num > n) return;
        }
        // 未填充矩阵的右边界：从上往下，固定end_j，正序遍历i
        for (int i = start_i + 1; i <= end_i; i++) {
            ans[i][end_j] = String.valueOf(cur_num++);
            if (cur_num > n) return;
        }
        // 未填充矩阵的下边界：从右往左，固定end_i，逆序遍历j
        for (int j = end_j - 1; j >= start_j; j--) {
            ans[end_i][j] = String.valueOf(cur_num++);
            if (cur_num > n) return;
        }
        // 未填充矩阵的左边界：从下往上，固定start_j，逆序遍历i
        for (int i = end_i - 1; i > start_i; i--) {
            ans[i][start_j] = String.valueOf(cur_num++);
            if (cur_num > n) return;
        }
        // 对未填充数组进行递归
        // start_i, end_i, start_j, end_j需要修改
        help(ans, start_i + 1, end_i - 1, start_j + 1, end_j - 1, cur_num, n);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入数字n，行数m
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        // 计算列数c，n除以m后向上取整
        int c = (int) Math.ceil((double) n / m);

        // 初始化答案螺旋数组，先用"*"填充
        String[][] ans = new String[m][c];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < c; j++) {
                ans[i][j] = "*";
            }
        }

        // 递归入口：start_i, end_i, start_j, end_j
        // 分别传入0, m-1, 0, c-1
        help(ans, 0, m - 1, 0, c - 1, 1, n);
        // 逐行输出螺旋矩阵
        for (String[] row : ans) {
            System.out.println(String.join(" ", row));
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 递归函数
// ans为答案螺旋矩阵
// start_i, end_i, start_j, end_j分别为子矩阵的起始、终止的i和j下标
// cur_num为未填充子矩阵左上角的第一个数
// n为终止数字
void help(vector<vector<string>>& ans, int start_i, int end_i, int start_j, int end_j, int& cur_num, int n) {
    // 如果不存在遍历区间，则不会进入下面四个for循环中的任意一个
    // 会持续进行递归，导致编译栈溢出
    // 这种情况就是当n为某个奇数的平方且c = m = sqrt(n)的时候会出现
    // 譬如填充5*5的矩阵且n = 25，最中间那个数字会出现的情况
    // 额外判断这种条件，将最中间的数字填充上并退出递归即可
    if (start_i == end_i && start_j == end_j) {
        ans[start_i][start_j] = to_string(cur_num);
        return;
    }
    // 未填充矩阵的上边界：从左往右，固定start_i，正序遍历j
    for (int j = start_j; j <= end_j; j++) {
        ans[start_i][j] = to_string(cur_num++);
        if (cur_num > n) return;
    }
    // 未填充矩阵的右边界：从上往下，固定end_j，正序遍历i
    for (int i = start_i + 1; i <= end_i; i++) {
        ans[i][end_j] = to_string(cur_num++);
        if (cur_num > n) return;
    }
    // 未填充矩阵的下边界：从右往左，固定end_i，逆序遍历j
    for (int j = end_j - 1; j >= start_j; j--) {
        ans[end_i][j] = to_string(cur_num++);
        if (cur_num > n) return;
    }
    // 未填充矩阵的左边界：从下往上，固定start_j，逆序遍历i
    for (int i = end_i - 1; i > start_i; i--) {
        ans[i][start_j] = to_string(cur_num++);
        if (cur_num > n) return;
    }
    // 对未填充数组进行递归
    // start_i, end_i, start_j, end_j需要修改
    help(ans, start_i + 1, end_i - 1, start_j + 1, end_j - 1, cur_num, n);
}

int main() {
    // 输入数字n，行数m
    int n, m;
    cin >> n >> m;
    // 计算列数c，n除以m后向上取整
    int c = ceil(static_cast<double>(n) / m);

    // 初始化答案螺旋数组，先用"*"填充
    vector<vector<string>> ans(m, vector<string>(c, "*"));

    int cur_num = 1;
    // 递归入口：start_i, end_i, start_j, end_j
    // 分别传入0, m-1, 0, c-1
    help(ans, 0, m - 1, 0, c - 1, cur_num, n);
    // 逐行输出螺旋矩阵
    for (const auto& row : ans) {
        for (const auto& elem : row) {
            cout << elem << " ";
        }
        cout << endl;
    }

    return 0;
}

时空复杂度

时间复杂度：O(N)。

空间复杂度：O(MC)。

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

  • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

版权声明：本文为博主作者：闭着眼睛学算法原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_48157259/article/details/135630855

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐