当前位置： 首页 > 编程日记 > 正文

1105 Spiral Matrix 给定数组向螺旋矩阵中填入数据

编程日记 2024-09-06 09:00:00

两个测试用例超时，可直接跳转到

目录

超时点1

超时点2

​​​​​​​

要做的事情是，将数组按照非升序/降序，顺时针从外围到内部一圈一圈地把数据填到矩阵中，并打印出来。也就是将数组排好序后，将矩阵的坐标和数组的下标对应起来。

所以用一个这样的数组存放矩阵相应位置上元素的数组下标。

int mp[200][200] = {0};

起先，我这样填充每一圈(注意交点的分配)

当然，从外到内，这个圈一定是在减小的， 减小多少，我用z来控制，程序如下，4个for循环分别代表4条直线上的元素

	int idx = n-1,i,j,z=1;int sw = false;//stop while循环 	 for(z=1;;z++){i = z;if(sw)break;for(j=z;j<=col-z;j++){mp[i][j] = idx--;
//			printf("mp[%d][%d]=%d\n",i,j,idx+1);if(idx<0){sw = 1;break;}}j = col+1-z;if(sw)break;for(i=z;i<=row-z;i++){mp[i][j] = idx--;
//			printf("mp[%d][%d]=%d\n",i,j,idx+1);if(idx<0){sw = 1;break;}}i = row+1-z;if(sw)break;for(j=col-z+1;j>=z+1;j--){mp[i][j] = idx--;
//			printf("mp[%d][%d]=%d\n",i,j,idx+1);if(idx<0){sw = 1;break;}}j = z;if(sw)break;for(i=row-z+1;i>=z+1;i--){mp[i][j] = idx--;
//			printf("mp[%d][%d]=%d\n",i,j,idx+1);if(idx<0){sw = 1;break;}}}

至于i和j的起止到底是多少，我也不能一下子想出，但我知道肯定有对称性，于是试了出来(通过被注释掉的打印)

特别说明一下变量sw，是stop while的缩写，用于跳出while循环，且每次进入for循环之前都要判断一下sw是否为true。idx<0说明矩阵已填满。

1）每次idx--之后都判断一下idx是否<0，但是此时break,只能跳出内层for循环，要跳出外层循环还要借助sw变量。

2）何时判断sw呢？我们希望达到的效果是idx<0一旦成立，就不再填充，如果只是在刚进入while循环的时候判断一下，可能出现的情况是，在第三个for循环中断后，又进入第四个for循环，所以每次进入循环前都要判断一下sw。

但是这样做，有两个测试用例是运行超时的。我迫切地翻开参考书，想看看自己究竟哪里代码不优雅了。

1）那个sw的判断希望下次不要再看到了。直接把idx>=0放在while和for的括号里不香吗？理论上while可以不放，但是这样光标一直闪，程序会出问题。改进后如下

    int idx = n-1,i,j,z=1;for(z=1;idx>=0;z++){i = z;for(j=z;j<=col-z&&idx>=0;j++){mp[i][j] = idx--;}j = col+1-z;for(i=z;i<=row-z&&idx>=0;i++){mp[i][j] = idx--;}i = row+1-z;for(j=col-z+1;j>=z+1&&idx>=0;j--){mp[i][j] = idx--;}j = z;for(i=row-z+1;i>=z+1&&idx>=0;i--){mp[i][j] = idx--;}}

代码清爽了很多，但是超时的问题仍毫无进展。

超时点1

2）我听参考书的话，加入了如下特判

if(n==1){printf("%d",a[0]);return 0;}

于是从21变成了22分，有一个测试用例通过了。还剩一个超时，并且我注意到，刚才的两个超时，显示的时间都是-，也许是陷入了某种死循环。

3）我尝试提取i和j的边界中的公因子，引入

int r = col-z;
int d = row-z;

矩阵填充代码变成如下

    int idx = n-1,i,j,z=1;for(z=1;idx>=0;z++){i = z;int r = col-z;int d = row-z;for(j=z;j<=r&&idx>=0;j++){mp[i][j] = idx--;}j = r+1;for(i=z;i<=d&&idx>=0;i++){mp[i][j] = idx--;}i = d+1;for(j=r+1;j>=z+1&&idx>=0;j--){mp[i][j] = idx--;}j = z;for(i=d+1;i>=z+1&&idx>=0;i--){mp[i][j] = idx--;}}

很遗憾，那个测试用例还是没过

4）最后，我又找出自己的代码和参考书代码的一个区别，那就是我在填充过程中填充的是数组下标，而参考书直接填充的内容，这样输出的时候就不必先映射到下标再输出，于是我照做。

将所有的

mp[i][j] = idx--;

改成了

mp[i][j] = a[idx--];

于是输出时候的

int idx = mp[i][j];
printf("%d",a[idx]);

也就自然变成了

printf("%d",mp[i][j]);

还是超时。。

超时点2

5）最后，我又发现，程序对最内层只有一个数字的情况进行了特判，也就是在4个for循环后加入了如下代码

i++;
j++;
if(idx==0)mp[i][j] = a[idx--];

好了，AC。

完整代码如下

#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<stdlib.h>using namespace std;const int maxn = 10010;int mp[200][200] = {0};int main(){int n;int a[maxn];scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}if(n==1){printf("%d",a[0]);return 0;}int col,row;for(int i=(int)sqrt(n);i>=1;i--){if(n%i==0){col = i;break;}}row = n/col;//row>=col//a按照升序排好 sort(a,a+n);int idx = n-1,i,j,z;for(z=1;idx>=0;z++){int r = col-z;int d = row-z;for(i=z,j=z;j<=r&&idx>=0;j++){mp[i][j] = a[idx--];}for(i=z,j=r+1;i<=d&&idx>=0;i++){mp[i][j] = a[idx--];}for(i=d+1,j=r+1;j>=z+1&&idx>=0;j--){mp[i][j] = a[idx--];}for(i=d+1,j=z;i>=z+1&&idx>=0;i--){mp[i][j] = a[idx--];}i++;j++;if(idx==0)mp[i][j] = a[idx--];}for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){printf("%d",mp[i][j]);if(j!=col)printf(" ");}printf("\n"); } return 0;
}


https://www.dkcj.cn/info/17515.html

相关文章：

一晚上就能让你小腹变小的方法 - 健康程序员，至尚生活！

仅一晚上针对小腹的锻炼就会让它明显收紧&#xff0c;很不可思议吧&#xff1f;但它确实发生了。形体教练向我们推荐&#xff1a;做30次转身运动(双手抱在脑后站立&#xff0c;迅速分别向左右两侧依次扭转上肢&#xff0c;注意不要以膝盖为轴&#xff0c;使运动轴心保持在骨盆以…

编程日记2024/09/06 08:50:00

Alpha 冲刺 （2/10）

前言 队名&#xff1a;拖鞋旅游队组长博客&#xff1a;https://www.cnblogs.com/Sulumer/p/9960487.html作业博客&#xff1a;https://edu.cnblogs.com/campus/fzu/Grade2016SE/homework/2365组内情况 燃尽图任务分布github签入记录苏路明&#xff08;组长&#xff09;过去两天…

编程日记2024/09/06 08:40:00

互联网对erp行业到底有什么影响

1 财务管理的影响 总账、 应收应付、资金计划&#xff0c;支付管理。 生产计划的影响。 重大的疑惑。 转载于:https://www.cnblogs.com/sdgxbooy/p/8892655.html

编程日记2024/09/06 08:30:00

PAT甲级排队问题合集 (持续更新中)

已加入的习题 A1014,A1017 问题1和2共性 1. 都是排队问题 2. 都有一条黄线 3. 都需要找到最先离开人的队伍 4. 都有着服务时间段限制(迟于某个时间点来不予受理) 问题1&#xff1a;1014 Waiting in Line 问题链接&#xff1a;1014 Waiting in Line 这一题&#xff0c;…

编程日记2024/09/06 08:20:00

第三章：创建用户界面组件--可视化组件(一)

1.可视化组件 1.1关于可视化组件 可视化组件的特征包括&#xff1a;size(大小&#xff09;、事件、样式、皮肤、行为。 行为&#xff1a;当组件被触发时&#xff0c;视觉&#xff0c;音乐效果的变化。 1.1 .1Spark and Halo 组件 Spark是flex 4中新加的组件。halo仍旧继承了以…

编程日记2024/09/06 08:10:00

Rust 1.30带来更多元编程支持，并改进了模块系统

Rust的最新版本1.30扩展了过程宏&#xff0c;允许它们定义新的属性和类似于函数的宏。此外&#xff0c;它简化了Rust模块系统&#xff0c;使其更加一致、直观。 Rust 1.30引入了两种新类型的过程宏&#xff0c;“类属性的过程宏”和“类函数的过程宏”。过程宏是Rust元编程的基…

编程日记2024/09/06 08:00:00

两种最大堆建堆方式

都是用完全二叉树的静态存储方式&#xff0c;下标从1开始。 No.1 先按照数组的次序填入完全二叉树&#xff0c;再从倒数第一个非叶子节点开始&#xff0c;一个个地看是不是要向下调整&#xff0c;一直下调到不能再调。 void downAdjust(int low,int high){int i low;int j …

编程日记2024/09/06 07:50:00

汉字验证码和算式验证码

大家知道简单数字或者字母验证码很容易被破解&#xff0c;但是算式验证码或者中文汉字验证码不容易被破解&#xff0c; 所以建议大家在使用验证码的时候&#xff0c;尽量用算式验证码或者中文汉字验证码。 下面是我写的两种验证码代码&#xff0c;有用到的朋友可以参考下&#…

编程日记2024/09/06 07:40:00

自定义Linq的Distinct

代码 1 usingSystem;2 usingSystem.Collections.Generic;3 usingSystem.ComponentModel;4 usingSystem.Data;5 usingSystem.Drawing;6 usingSystem.Linq;7 usingSystem.Text;8 usingSystem.Windows.Forms;9 10 namespaceLinqTest11 {12 publicpartialclassForm1 : Form13 {14 p…

编程日记2024/09/06 07:30:00

Python itertools 实现全组合

>>> import itertools >>> data itertools.product([A, B], [1, 2, 3]) >>> list(data) [(A, 1), (A, 2), (A, 3), (B, 1), (B, 2), (B, 3)] 转载于:https://www.cnblogs.com/xiecl/p/9961825.html

编程日记2024/09/06 07:20:00

PAT（甲级）2021年春季考试 7-3 Structure of Max-Heap

考察&#xff1a;建堆&#xff0c;字符串的处理 建堆上&#xff0c;跳了坑&#xff0c;才发现自己之前的方法过于笨拙&#xff0c;详情见两种最大堆建堆方式 字符串处理上&#xff0c;走的弯路更大&#xff0c;但是也因此牢记了两个技巧 1. cin>>str可以用getline(cin…

编程日记2024/09/06 07:10:00

[linux内核][linux中断]——软中断机制

点击打开链接 一&#xff0c;linux软中断的概念软中断&#xff08;softirq&#xff09;常常表示可延迟函数的所有种类&#xff0c;目前linux上使用的软中断个数是有限的&#xff0c;linux最多注册32个&#xff0c;目前使用了10个&#xff0c;在interrupt.h中定义&#xff0c;中…

编程日记2024/09/06 07:00:00

JS中8个常见的陷阱

译者按: 漫漫编程路&#xff0c;总有一些坑让你泪流满面。 原文: Who said javascript was easy ? 译者: Fundebug为了保证可读性&#xff0c;本文采用意译而非直译。另外&#xff0c;本文版权归原作者所有&#xff0c;翻译仅用于学习。 这里我们针对JavaScript初学者给出一些…

编程日记2024/09/06 06:50:00

支持支付宝（Alipay）付款的三个美国主机商

这段时间买国外主机的筒子们越来越多&#xff0c;而付款就是首先摆在大家眼前的一道障碍&#xff0c;大部分美国主机商只能通过信用卡购买&#xff0c;付款不方便。因为这个原因&#xff0c;很多人的美国主机都是从国内的公司或者个人买的&#xff0c;无法享受美国主机的优质服…

编程日记2024/09/06 06:40:00

(C++)string 的两种输入方式和输出方式

注&#xff1a;头文件如下 #include<string> #include<cstdio> #include<iostream>using namespace std; 注&#xff1a;第一种输入方式遇到回车停止读入&#xff0c;第二种输入方式遇到空格停止读入。 两种读入方式也都可以用来读字符数组。 int main()…

编程日记2024/09/06 06:30:00

ob_get_contents();basename;file_get_contents用法

ob_get_contents(); ob_end_clean(); ob_start()使用ob_start()把输出那同输出到缓冲区&#xff0c;而不是到浏览器。然后用ob_get_contents得到缓冲区的数据。 ob_start()在服务器打开一个缓冲区来保存所有的输出。所以在任何时候使用echo &#xff0c;输出都将被加入缓冲区中…

编程日记2024/09/06 06:20:00

零基础学汇编 --小甲鱼

来自http://www.51xue8.com/diannao/wangluobiancheng/2013-11-06/6584.html#fillback0100307b617b7b7b303232303266313839397b677b7b240000&anchortestanchor转载于:https://www.cnblogs.com/I-L-o-v-e-z-h-o-u/p/4235340.html

编程日记2024/09/06 06:10:00

数据标准化_1

from sklearn.datasets import load_irisirisload_iris()#Z-score 数据标准化from sklearn.preprocessing import StandardScalerdata_standardStandardScaler().fit_transform(iris.data)# print(data_standard,data_standard)#Min-Maxfrom sklearn.preprocessing import MinM…

编程日记2024/09/06 06:00:00

PAT（甲级）2021年春季考试 7-1 Arithmetic Progression of Primes

思路&#xff1a;用筛除法打素数表(与之相对的是枚举加逐个判断)是降低时间复杂度的第一个点&#xff0c;第二个点是运用上数学技巧&#xff0c;给定了等差数列的范围(2-MAX)&#xff0c;给定了个数&#xff0c;那么最大的等差是可以求出的。循环的第一层从最大等差开始&#x…

编程日记2024/09/06 05:50:00

hadoop中HBase子项目入门讲解

HBase 是Hadoop的一个子项目,HBase采用了Google BigTable的稀疏的,面向列的数据库实现方式的理论,建立在hadoop的hdfs上,一方面里用了hdfs的高可靠性和可伸缩行,另外一方面里用 了BigTable的高效数据组织形式.可以说HBase为海量数据的real-time相应提供了很好的一个开源解决方案…

编程日记2024/09/06 05:40:00

C++/C union使用记一下锅

//首先&#xff0c;学习编程一定要记得加几个群或者加几个讨论组&#xff0c;因为这样你才能不断地进步还有吵架/滑稽 记一下 关于使用union结构体时遇到的一些坑 To zero-initialize an object of type T means: — if T is a scalar type (3.9), the object is set to the va…

编程日记2024/09/06 05:30:00

推荐60+ Flex开发参考网站

推荐60 Flex开发参考网站 下面是一些好的Flex开发的网站或者Flex资源&#xff0c;如果你使用Flex开发&#xff0c;可以参考一下。 网上找的&#xff0c;可以参考参考&#xff01;呵呵 新手入门参考: Adobe Flex 3 - adobe.comAdobe Flex Sample Applications - adobe.comVideo …

编程日记2024/09/06 05:20:00

PAT（甲级）2020年秋季考试 7-4 Professional Ability Test

解题思路&#xff1a; 1.用拓扑排序判断给定的图是否是有向无环图(DAG) 在这个过程当中&#xff0c;对于入度为0的结点&#xff0c;在布尔数组中标记是初始结点 通过入队的结点个数是否等于总个数判断是不是DAG 注意&#xff1a;虽然有队列&#xff0c;但是不需要inq[]数组…

编程日记2024/09/06 05:10:00

TestNG:org.openqa.selenium.os.UnixProcess$SeleniumWatchDog错误

在TestNG运行自动化测试用例的时候&#xff0c;浏览器FireFox正确打开&#xff0c;可是在测试用例运行完成后&#xff0c;我调用的是webdriver.quit()关闭程序的&#xff0c;结果却报以下错误&#xff1a; Sep 25, 2014 4:19:32 PM org.openqa.selenium.os.UnixProcess$Seleniu…

编程日记2024/09/06 05:00:00

项目经理修炼手册 2.1.2 项目经理的基本功

具备以上素质的人&#xff0c;大体上可以算是具有基本的程序员素质了&#xff0c;但是想从程序员成为项目经理&#xff0c;必然还需要有一点进步&#xff0c;那额外的这些素质都有哪些呢&#xff1f; 曾经有人力资源的朋友问我要人&#xff0c;我介绍了几个技术上很不错的人&am…

编程日记2024/09/06 04:50:00

CSS3动画过渡的jquery动态弹出框插件

版权声明&#xff1a;本文为博主原创文章&#xff0c;未经博主允许不得转载。 https://blog.csdn.net/w178191520/article/details/84111711 在线演示 本地下载

编程日记2024/09/06 04:40:00

PAT（甲级）2021年春季考试 7-4 Recycling of Shared Bicycles

解题思路&#xff1a; 先用Floyd算法求出全员最短路径矩阵。 然后使用DFS进行遍历&#xff0c;遍历的原则是就近贪心&#xff0c;对于每一个点先遍历离他最近的未访问点。 记录访问点的个数&#xff0c;同时用数组存放已访问点&#xff0c;如果访问点的个数不等于输入点数1(…

编程日记2024/09/06 04:30:00

JAVA抽象类和接口的区别【附经典分析用例Door】

这篇文章对抽象类和接口说的很详细&#xff0c;希望对大家有所帮助.　　abstract class和interface是Java语言中对于抽象类定义进行支持的两种机制&#xff0c;正是由于这两种机制的存在&#xff0c;才赋予了Java强大的面向对象能力。abstract class和interface之间在对于抽象类…

编程日记2024/09/06 04:20:00

sql 2005提示未能加载包Microsoft SQL Management Studio Package

被360隔离了&#xff0c;请到360恢复区恢复。转载于:https://www.cnblogs.com/janealer/p/4238743.html

编程日记2024/09/06 04:10:00

puppeteer爬虫的奇妙之旅

(爬虫)[puppeteer|] 爬虫又称网络机器人。每天或许你都会使用搜索引擎&#xff0c;爬虫便是搜索引擎重要的组成部分&#xff0c;爬取内容做索引。现如今大数据&#xff0c;数据分析很火&#xff0c;那数据哪里来呢&#xff0c;可以通过网络爬虫爬取啊。那我萌就来探讨一下网络爬…

编程日记2024/09/06 04:00:00