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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Bayes-RF,基于贝叶斯Bayes优化算法优化随机森林RF分类预测(二分类及多分类皆可)-附代码

Bayesian Optimization&#xff08;贝叶斯优化&#xff09;是一种用于超参数调优的技术&#xff0c;对于类似随机森林&#xff08;Random Forest&#xff0c;简称RF&#xff09;的机器学习算法非常重要。随机森林是一种集成学习方法&#xff0c;它在训练过程中构建多个决策树&a…

漂亮国的无人餐厅的机器人骚操作

导语 大家好&#xff0c;我是智能仓储物流技术研习社的社长&#xff0c;你的老朋友&#xff0c;老K。行业群 新书《智能物流系统构成与技术实践》 知名企业 读者福利&#xff1a; &#x1f449;抄底-仓储机器人-即买即用-免调试 智能制造-话题精读 1、西门子、ABB、汇川&#x…

详解 Redis 在 Centos 系统上的安装

文章目录 详解 Redis 在 Centos 系统上的安装1. 使用 yum 安装 Redis 52. 创建符号链接3. 修改配置文件4. 启动和停止 Redis 详解 Redis 在 Centos 系统上的安装 1. 使用 yum 安装 Redis 5 如果是Centos8&#xff0c;yum 仓库中默认的 redis 版本就是5&#xff0c;直接 yum i…

Premiere Pro 2024:赋予创意翅膀,让你的视频飞翔 mac/win版

Premiere Pro 2024&#xff0c;作为Adobe旗下的旗舰视频编辑软件&#xff0c;自推出以来&#xff0c;一直在视频制作领域占据着重要的地位。随着技术的不断进步和创新&#xff0c;Premiere Pro 2024为用户带来了前所未有的编辑体验&#xff0c;重新定义了视频制作的标准。 Pre…

Unity类银河恶魔城学习记录12-3 p125 Limit Inventory Slots源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Inventory.cs using Newtonsoft.Json.Linq; using System.Collections; us…

深入go泛型特性之comparable「附案例」

写作背景 如果你经常遇到一些操作&#xff0c;比如将 map 转换为 slice&#xff0c;判断一个字符串是否出现在 map 中&#xff0c;slice 中是否有重复元素等等&#xff0c;那你对下面这个库肯定不陌生。 github.com/samber/lo最近抽业余时间在看了源码&#xff0c;底层用了范…

云计算的安全需求

目录 一、概述 二、云安全服务基本能力要求 三、信息安全服务&#xff08;云计算安全类&#xff09;资质要求 3.1 概述 3.2 资质要求内容 3.2.1 组织与管理要求 3.2.2 技术能力要求 四、云安全主要合规要求 4.1 安全管理机构部门的建立 4.2 安全管理规范计划的编制 4…

【Flutter】Getx设计模式及Provider、Repository、Controller、View等

本文基于Getx 4,x 本本 1、引入 再次接触到Flutter项目&#xff0c;社区俨然很完善和活跃。pubs.dev 寻找状态管理的时候看到很熟悉的Getx时间&#xff0c;俨然发现Getx的版本已到是4.x版本&#xff0c;看到Getx的功能已经非常强大了&#xff0c;庞大的API俨然成为一种开发框架…

Windows Server 2008添加Web服务器(IIS)、WebDAV服务、网络负载均衡

一、Windows Server 2008添加Web服务器&#xff08;IIS&#xff09; &#xff08;1&#xff09;添加角色&#xff0c;搭建web服务器&#xff08;IIS&#xff09; &#xff08;2&#xff09;添加网站&#xff0c;关闭默认网页&#xff0c;添加默认文档 在客户端浏览器输入服务器…

蓝桥杯 十一届C++A组 字符排序 21分(运行超时)

思路&#xff1a; 1. 此题考查的冒泡排序中的交换次数&#xff0c;其实就是考察当前数与后面的逆序对个数问题。而为了最大利用位数&#xff0c;应当使每一位都不小于后面的字符&#xff0c;否则会造成一次逆序对的浪费&#xff08;贪心&#xff0c;为了使总位数最少&#xff…

每日OJ题_优先级队列_堆③_力扣692. 前K个高频单词

目录 力扣692. 前K个高频单词 解析代码 力扣692. 前K个高频单词 692. 前K个高频单词 难度 中等 给定一个单词列表 words 和一个整数 k &#xff0c;返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率&#xff0c…

《QT实用小工具·三》偏3D风格的异型窗体

1、概述 源码放在文章末尾 可以在窗体中点击鼠标左键进行图片切换&#xff0c;项目提供了一些图片素材&#xff0c;整体风格偏向于3D类型&#xff0c;也可以根据需求自己放置不同的图片。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; 头文件部分&#xff…

基于SSM+Vue的服装商城系统

绪论 项目研究的背景 困扰管理层的许多问题当中,服装定制将是广大用户们不可忽视的一块。但是管理好服装定制又面临很多麻烦需要解决,例如,如何在工作琐碎,记录繁多的情况下将服装定制的当前情况反应给相关管理人员决策,等等。在此情况下开发一款服装定制系统&#xff0c;于是…

DataLoader的使用

DataLoader的使用 测试DataLoader&#xff0c;batch_size大小为4 import torchvision.datasets from torch.utils.data import DataLoadertest_data torchvision.datasets.CIFAR10("./dataset", trainFalse, transformtorchvision.transforms.ToTensor()) test_loa…

215 基于matlab的快速跟踪算法

基于matlab的快速跟踪算法&#xff0c;提出一种简单又快速、 鲁棒性的算法&#xff0c;基于贝叶斯框架下&#xff0c;该模型 &#xff08;即图像强度和从目标位置&#xff09; 的低级功能及周边地区的统计相关性的时空关系。跟踪问题是通过计算信心地图&#xff0c;并将以最大限…

闪站侠洗护管理系统,洗衣洗鞋小程序软件定制,干洗连锁店软件系统搭建;

闪站侠洗护管理系统&#xff0c;洗衣洗鞋小程序软件定制&#xff0c;干洗连锁店软件系统搭建&#xff1b; 为了让每一个洗衣洗鞋工厂与门店的连接更加高效便捷&#xff0c;送洗流程更加简单轻松&#xff0c;拽牛科技倾心打造洗衣洗鞋管理软件。我们的目标是通过高效和优质的服务…

Navicat Premium工具安装教程(超详细讲解)

Navicat Premium是一款功能强大并可支持多连接的数据库管理工具&#xff0c;它允许在单一程序中同时连接多达7种数据库&#xff0c;包括MySQL、MariaDB、MongoDB、SQL server、SQLite、Oracle和PostgreSQl数据库&#xff0c;让管理不同类型的数据库更加快速便捷。 安装Navicat…

隐私计算实训营学习九:隐语多方安全计算在安全核对的行业实践

文章目录 一、业务背景&#xff1a;安全核对产生的土壤二、产品方案&#xff1a;从试点到规模化的路三、技术共建&#xff1a;与隐语的共同成长 一、业务背景&#xff1a;安全核对产生的土壤 业务背景&#xff1a;很多粗放使用数据的方式被新出台的法律法规所规范&#xff0c;…

Redis的I/O多路复用

Redis是单线程的&#xff0c;为什么还那么快&#xff1f; 1.redis是基于内存的 2.redis使用I/O多路复用模型 关于I/O多路复用&#xff1a; 多路&#xff1a;多个客户端连接复用&#xff1a;使用单线程就能够实现同时处理多个客户端的连接 单线程去监控多个Socket&#xff…

数据库的简单查询

一、检索一列或多列1.检索单独一列 select 列名 from 表名; select order_num from orders; 2.检索多列数据 select 列 1&#xff0c;列 2... from 表名; select order_num,order_date from orders; select order_date,order_num from orders; 3.查询所有字段 select * from…