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

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

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

一、问题阐述

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

输入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 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

python的迭代器和生成器

迭代是数据处理的基础,迭代可以理解为是一种惰性求值。在python里迭代器和生成器是一回事,使用的是yield关键字。

451
来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

3578
来自专栏枕边书

空间索引 - 四叉树

前言 作为程序员,应该都对二叉树都不陌生,我们都知道二叉树的变体二叉查找树,非常适合用来进行对一维数列的存储和查找,可以达到 O(logn) 的效率;我们在用二...

23510
来自专栏爱撒谎的男孩

跳跃链表

1593
来自专栏大数据文摘

视觉直观感受 7 种常用排序算法

1775
来自专栏阿凯的Excel

Vlookup最高阶应用的全网唯一解决方案

古有烟笼寒水月笼沙的缥缈朦胧,今有查询函数的假模糊匹配的终极应用!今天分享的内容是全网唯一哦~ 为啥是假模糊匹配呢?一会和你说! 嗯嗯,Vlookup函数应该...

2665
来自专栏趣学算法

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

503
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

3669
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3068
来自专栏Python专栏

浅尝Python快速排序

944

扫描关注云+社区