PTA C 1050 螺旋矩阵(思路与优化)

本题要求将给定的 N 个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第 1 个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列,满足条件:m×n 等于 N;m≥n;且 m−n 取所有可能值中的最小值。

输入格式:

输入在第 1 行中给出一个正整数 N,第 2 行给出 N 个待填充的正整数。所有数字不超过 104,相邻数字以空格分隔。

输出格式:

输出螺旋矩阵。每行 n 个数字,共 m 行。相邻数字以 1 个空格分隔,行末不得有多余空格。

输入样例:

12
37 76 20 98 76 42 53 95 60 81 58 93

输出样例:

98 95 93
42 37 81
53 20 76
58 60 76

 问题总结:

1.没什么特别的,就是一个找规律的题,和机器人的那一道题有些类似:机器人控制。但是需要解决几个问题。

2.寻找 m * n = N 的两个数,且有 m>n & min(m-n) 比较笨的方法。

void get_m_n(int N, int &m,int &n)
{
    int min = N ;
    for(int i = 1; i <= N; i++)
    {
        for (int j = i; j <= N; j++)
        {
           if(i*j == N)
           {
                if(min > (j-i))
                {
                    min = (j-i);
                    m = j;
                    n = i;
                }
           }
           if(i*j > N)
           {
            break;
           }
        }
    }
}

 3.简单的选择排序

void sort(int *nums,int size)
{
    int t;
    for(int i=0;i<size;i++)
    {
        for(int j = i+1; j<size; j++)
        {
            if(nums[i]<nums[j])
            {
                t = nums[i];
                nums[i] = nums[j];
                nums[j] =t;
            }
        }
    }
}

4.数据范围,m和n的取值决定了程序能不能通过测试点,因此二维数组不能开太大,当然可以用一维数组来优化。开辟 m * n =N的一维数组,将二维矩阵按行顺序存储,通过计算还原元素在二维数组位置的下标,即:一维元素 index = i * n + j;i和j代表二维中的下标,n代表列col数量。

优化前的内存

优化后的内存

 

5.总体实现:未优化

#include <iostream>
#include<cstring>
using namespace std;
void get_m_n(int N, int &m,int &n)
{
    int min = N ;
    for(int i = 1; i <= N; i++)
    {
        for (int j = i; j <= N; j++)
        {
           if(i*j == N)
           {
                if(min > (j-i))
                {
                    min = (j-i);
                    m = j;
                    n = i;
                }
           }
           if(i*j > N)
           {
            break;
           }
        }
    }
}
void sort(int *nums,int size)
{
    int t;
    for(int i=0;i<size;i++)
    {
        for(int j = i+1; j<size; j++)
        {
            if(nums[i]<nums[j])
            {
                t = nums[i];
                nums[i] = nums[j];
                nums[j] =t;
            }
        }
    }
}
int main(int argc, char const *argv[])
{
    bool r = true,d = false,l = false,u=false;
    int N;
    cin>>N;
    int *nums = new int[N];
    memset(nums, 0, sizeof(int)*N);
    for(int i = 0; i <N; i++)
    {
        cin>>nums[i];
    }
    sort(nums,N);
    int m=0,n=0;
    get_m_n(N,m,n);
    int ans[10000][100] = {0};
    int i=0,j=-1;
    int heng = n,shu = m -1;
    for(int index = 0; index < N; )
    {
        if(r)
        {
            for(int step = 0; step < heng; step++)
            {
                ans[i][++j] = nums[index++];
                r = false;
                l = false;
                u = false;
                d = true;

            }
            heng--;
        }
        if(d)
        {
            for(int step=0; step < shu;step++)
            {
                ans[++i][j] = nums[index++];
                d = false;
                u = false;
                r = false;
                l = true;

            }
            shu--;
        }
        if(l)
        {
            for(int step = 0; step < heng; step++)
            {
                ans[i][--j] = nums[index++];
                l = false;
                r = false;
                d = false;
                u = true;

            }
            heng--;
        }
        if(u)
        {
            for(int step=0; step < shu; step++)
            {
                ans[--i][j] = nums[index++];
                u = false;
                l = false;
                d = false;
                r = true;

            }
            shu--;
        }
    }
    for(int row = 0; row < m; row++)
    {
        for (int col = 0; col < n; col++)
        {
            if(col<n-1)
            {
                cout<<ans[row][col]<<" ";
            }
            else
            {
                cout<<ans[row][col];
            }
        }
        cout<<endl;
    }
    return 0;
}

6.优化方案

#include <iostream>
#include<cstring>
using namespace std;
void get_m_n(int N, int &m,int &n)
{
    int min = N ;
    for(int i = 1; i <= N; i++)
    {
        for (int j = i; j <= N; j++)
        {
           if(i*j == N)
           {
                if(min > (j-i))
                {
                    min = (j-i);
                    m = j;
                    n = i;
                }
           }
           if(i*j > N)
           {
            break;
           }
        }
    }
}
void sort(int *nums,int size)
{
    int t;
    for(int i=0;i<size;i++)
    {
        for(int j = i+1; j<size; j++)
        {
            if(nums[i]<nums[j])
            {
                t = nums[i];
                nums[i] = nums[j];
                nums[j] =t;
            }
        }
    }
}
int convert_i_j(int i, int j, int n)
{
    return i*n+j;
}
int main(int argc, char const *argv[])
{
    bool r = true,d = false,l = false,u=false;
    int N;
    cin>>N;
    int *nums = new int[N];
    memset(nums, 0, sizeof(int)*N);
    for(int i = 0; i <N; i++)
    {
        cin>>nums[i];
    }
    sort(nums,N);
    int m=0,n=0;
    get_m_n(N,m,n);
    int *answer= new int[m*n];
    int i=0,j=-1;
    int heng = n,shu = m -1;
    for(int index = 0; index < N; )
    {
        if(r)
        {
            for(int step = 0; step < heng; step++)
            {
                j++;
                int value = nums[index++];
                int index_m_n = convert_i_j(i,j,n);
                answer[index_m_n] = value;
                r = false;
                l = false;
                u = false;
                d = true;
            }
            heng--;
        }
        if(d)
        {
            for(int step=0; step < shu;step++)
            {
                i++;
                int value = nums[index++];
                int index_m_n = convert_i_j(i,j,n);
                answer[index_m_n] = value;
                d = false;
                u = false;
                r = false;
                l = true;
            }
            shu--;
        }
        if(l)
        {
            for(int step = 0; step < heng; step++)
            {
                j--;
                int value = nums[index++];
                int index_m_n = convert_i_j(i,j,n);
                answer[index_m_n] = value;
                l = false;
                r = false;
                d = false;
                u = true;
            }
            heng--;
        }
        if(u)
        {
            for(int step=0; step < shu; step++)
            {
                i--;
                int value = nums[index++];
                int index_m_n = convert_i_j(i,j,n);
                answer[index_m_n] = value;
                u = false;
                l = false;
                d = false;
                r = true;
            }
            shu--;
        }
    }

    for(int row = 0; row < m; row++)
    {
        for (int col = 0; col < n; col++)
        {
            if(col<n-1)
            {
                cout<<answer[row*n+col]<<" ";
            }
            else
            {
                 cout<<answer[row*n+col];
            }
        }
        cout<<endl;
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520744.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

160.相交链表

题目描述 解题思路 ————看评论区大神的思路———— 设「第一个公共节点」为 node &#xff0c;「链表 headA」的节点数量为 aaa &#xff0c;「链表 headB」的节点数量为 bbb &#xff0c;「两链表的公共尾部」的节点数量为 ccc &#xff0c;则有&#xff1a; 头节点 …

CSS设置字体样式

目录 前言&#xff1a; 1.font-family&#xff1a; 2.font-style&#xff1a; 3.font-weight&#xff1a; 4.font-size&#xff1a; 5.font-variant&#xff1a; 6.font&#xff1a; 前言&#xff1a; 在网页中字体是重要的组成部分&#xff0c;使用好字体可以让网页更…

第一次在msf控制台中运行search命令提示Module database cache not built yet问题解决

0x00 问题描述 在新装的kali虚拟机中使用msfconsole执行search命令时提示Module database cache not built yet问题&#xff0c;显然&#xff0c;是我们相关的数据库缓存存在问题。 故障现象&#xff1a; 0x01 启动数据库服务 msf中的search功能是基于postgresql来实现的&am…

python学习25:python中的元组(tuple)

python中的元组(tuple) 1.什么是元组&#xff1f; 元组也是容器数据类型的一种&#xff0c;同列表几乎是一样的&#xff0c;都是可以在里面封装多个&#xff0c;不同类型的元素在内&#xff1b;与列表最大的不同就是&#xff1a; 元组一旦被定义&#xff0c;就不能修改 2.元组…

物理层习题及其相关知识(谁看谁不迷糊呢)

1. 对于带宽为50k Hz的信道&#xff0c;若有4种不同的物理状态来表示数据&#xff0c;信噪比为20dB 。&#xff08;1&#xff09; 按奈奎斯特定理&#xff0c;信道的最大传输数据速率是多少&#xff1f;&#xff08;2&#xff09; 按香农定理&#xff0c;信道的最大传输数据速度…

Java设计模式—享元(FlyWeight)模式

享元模式&#xff08;Flyweight&#xff09;&#xff0c;运用共享技术有效地支持大量细粒度的对象 public abstract class Piece {protected PieceColor m_color;protected PiecePos m_pos;public Piece(PieceColor color ,PiecePos pos){m_color color;m_pos pos;}public ab…

Java笔试总结

. 操作系统中关于竞争和死锁的关系下面描述正确的是&#xff1f; A 竞争一定会导致死锁 B 死锁一定由竞争引起 C 竞争可能引起死锁 D 预防死锁可以防止竞争 答案: C 进程的控制信息和描述信息存放在()。 A JCB B PCB C AFT D SFT 答案: B 当系统发生抖动&#xff08;thrash…

元宇宙虚拟空间的场景的渲染(五)

前言 该文章主要讲元宇宙虚拟空间的场景的渲染&#xff0c;基本核心技术点&#xff0c;不多说&#xff0c;直接引入正题。 场景的渲染 下面第二个图中的代码是一个循环渲染逻辑&#xff0c;首先getDelta 获取2次时间的时间间隔&#xff0c;requestAnimationFrame请求我们的一…

Qt Creator 界面

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、认识 Qt Creator 界面 1、总览 2、左边栏 3、代码编辑区 4、UI设计界面 5、构建区 一、认识 …

99%的人不知道,Oracle resetlogs强制开库需要推进SCN?

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…

算法---分治(归并排序)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享分治算法关于归并排序的专题 对于归并排序在我个人主页专栏 <排序> 有详细的介绍 如果有不足的或者错误的请您指出! 1.归并排序 题目: 排序数组 1.1解析 关于归并排序…

STM32使用HAL库获取GPS模块HT1818Z3G5L信息(方法1)

1、写在最前 先了解一下GPRMC的格式 格 式&#xff1a; GPRMC,024813.640,A,3158.4608,N,11848.3737,E,10.05,324.27,150706,A*50 说 明&#xff1a; 字段 0&#xff1a;$GPRMC&#xff0c;语句ID&#xff0c;表明该语句为Recommended Minimum Specific GPS/TRANSIT Data&…

Open CASCADE学习|在给定的TopoDS_Shape中查找与特定顶点 V 对应的TopoDS_Edge编号

enum TopAbs_ShapeEnum{TopAbs_COMPOUND,TopAbs_COMPSOLID,TopAbs_SOLID,TopAbs_SHELL,TopAbs_FACE,TopAbs_WIRE,TopAbs_EDGE,TopAbs_VERTEX,TopAbs_SHAPE}; 这段代码定义了一个名为 TopAbs_ShapeEnum 的枚举类型&#xff0c;它包含了表示不同几何形状类型的常量。这些常量通常…

通过学习mayfly-go,我学会了前端如何优雅设计字典值

shigen坚持更新文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 个人IP&#xff1a;shigen shigen在假期的最后一天早晨起来&#xff0c;翻看了一下博客&#xff0c;一个ma…

spring注解驱动系列--声明式事务

一、环境搭建 一、导入依赖 <!-- 数据源、数据库驱动、spring-jdbc模块--> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-jdbc</artifactId> <version>4.3.12.RE…

Dockerfile详解构建镜像

Dockerfile构建企业级镜像 在服务器上可以通过源码或rpm方式部署Nginx服务&#xff0c;但不利于大规模的部署。为提高效率&#xff0c;可以通过Dockerfile的方式将Nginx服务封装到镜像中&#xff0c;然后Docker基于镜像快速启动容器&#xff0c;实现服务的快速部署。 Dockerf…

统一网关 Gateway(黑马程序员)

网关的技术实现 在 SpringCloud 中网关的实现包括两种&#xff1a; gatewayzuul Zuul 是基于 Servlet 的实现&#xff0c;属于阻塞式编程。而 SpringCloudGateway 则是基于 Spring5 中提供的 WebFlux &#xff0c; 属于响应式编程的实现&#xff0c;具备更好的性能。 网关的作…

火柴排队(c++实现)

题目 涵涵有两盒火柴&#xff0c;每盒装有 n 根火柴&#xff0c;每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列&#xff0c;同一列火柴的高度互不相同&#xff0c;两列火柴之间的距离定义为&#xff1a; 其中 ai 表示第一列火柴中第 i 个火柴的高度&#xf…

【OneAPI】贴纸生成API

OneAPI新接口发布&#xff1a;贴纸生成 生成一个10241024像素的贴纸。 API地址&#xff1a;POST https://oneapi.coderbox.cn/openapi/api/stickers 请求参数&#xff08;body&#xff09; 参数名类型必填含义说明prompt提示词是提示词示例&#xff1a;一只可爱的小狗 响应…

网络网络层之(1)IPv4地址

网络网络层之(1)IPv4地址 Author: Once Day Date: 2024年4月1日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…