有趣的算法(九) ——蛇形数组

有趣的算法(九)——蛇形数组

(原创内容,转载请注明来源,谢谢)

一、问题阐述

给定一个数字,需要返回的内容如下图所示:

输入5,得到结果:

输入10,得到结果:

输入一个数字i,输出结果的矩阵是i行i列的。矩阵从右上角开始,从1开始往下,每增加1行加1。到第i行后,再往左,每左一列加1。到头后再往上、往右、再往下....,其中已经填上的数字不能覆盖,直接转向。因为其生成的过程类似盘旋的蛇,故称为蛇形数组。

现要求输入任意元素i,返回矩阵内容。

二、问题分析

初看问题,看似很简单,用几个循环就可以解决问题。但是,当真正开始写循环的时候,就容易卡住。

对于此问题,用循环解决,需要考虑边界条件,以及如何进行循环。

1)如何进行循环

根据蛇形数组的生成过程,由左上方开始循环。共需要四类的循环,从左上到下、从下右到左、从左下到上、从上左到右,其中的上下左右都是相对的位置。

2)边界问题

循环何时退出,主要有两点:1是不能超过边界,输入的是i,则元素不能超出i;2是不能覆盖原有的内容,所以可以在对每个元素进行赋值的时候进行判断,如果已经有内容,则直接转向。

当触及边界问题,则按照第一点提到的四种循环,按顺序执行。

3)循环结束条件

上述的四个循环,只能完成一次的矩阵内容填充,故还需要一个总的循环。考虑到输入i,结果数组的元素个数是i*i,故循环结束的条件就是当值大于i*i,则结束循环。

三、实现

PHP实现过程如下:

function snakenumber($level){
   $max = $level * $level;//最大数量
   $count = 1;//初始值为1
   //初始从左上方开始
   $row = 0;
   $column = $level - 1;
   $res[$row][$column] = $count;
   while($max > $count)
    {
       while($level > $row+1 && !isset($res[$row+1][$column]))$res[++$row][$column] = ++$count;//从右往下
       while(0 <= $column-1 && !isset($res[$row][$column-1]))$res[$row][--$column] = ++$count;//从下往左
       while(0 <= $row-1 && !isset($res[$row-1][$column]))$res[--$row][$column] = ++$count;//从左往上
       while($level > $column+1 && !isset($res[$row][$column+1]))$res[$row][++$column] = ++$count;//从上往左
}
}

结果如问题阐述中的图示。其中的核心就是四重的循环,并且以结果不能大于 $level * $level作为边界控制条件。

PHP的实现相对来说简易,如果要用Java等强类型语言来实现的时候,需要先初始化整个二维数组。初始化的时候,给每个元素赋值为0,然后php中判断元素是否赋值的代码段!isset($res[$row+1][$column]),换成相应的$res[$row+1][$column]==0,即可作为判断。其余代码类似,不再赘述。

另外,近期个人事务较多,故文章发布较少,预计元旦开始会逐步恢复正常的内容发布。

——written by linhxx 2017.10.31

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏哈雷彗星撞地球

算法之路(一)----求最大子序列

对于IT行业者来说,刚参加工作,还能找点借口,说自己不擅长算法。可是工作三年以上的IT开发者,还说自己不会算法,不会设计模式就说不过去了。所以最近开始撸算法和设...

683
来自专栏数据分析

char varchar nchar nvarcharar到底有多大区别

首先说明下,ASP.NET MVC系列还在龟速翻译中。 工作好多年,基础知识甚是薄弱,决定以后在coding(cv操作)的时候尽量多google下,然后总结下来...

2686
来自专栏玄魂工作室

如何学Python 第十三课 列表进阶-切片,列表推导式

第十三课 列表进阶-切片,列表推导式 欢迎回来。在上一节课,我们学习了逻辑运算符和成员运算符。按照惯例,这节课我们讲点其他的东西,换换脑筋。 本节课我们来介绍一...

3505
来自专栏Python攻城狮

正则表达式1.正则表达式概述2.re模块操作3.表示字符4.re模块的高级用法5.贪婪和非贪婪

在Python中需要通过正则表达式对字符串进行匹配的时候,可以使用一个模块,名字为re

892
来自专栏听雨堂

Python学习笔记(1):列表元组结构

Python的列表元组功能强大,令人印象深刻。一是非常灵活,二是便于集体操作。特别是以元组作为列表项的结构,和数据访问的结果能够对应起来,和习惯的二维表理解上也...

1966
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3408
来自专栏用户2442861的专栏

阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

872
来自专栏数据结构与算法

P1338 末日的传说

题目描述 只要是参加jsoi活动的同学一定都听说过Hanoi塔的传说:三根柱子上的金片每天被移动一次,当所有的金片都被移完之后,世界末日也就随之降临了。 在古老...

2749
来自专栏小樱的经验随笔

洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数...

2815
来自专栏java思维导图

经典面试问题: Top K 之 -- 海量数据找出现次数最多或,不重复的

林冠宏 / 指尖下的幽灵 仅列举一些解决方法,事实的解决方案是非常多的。 这些问题都是面临着有如下的考虑: 内存不足以放下所有的数。 机器CPU的核数不够。 ...

3587

扫码关注云+社区