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

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

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

一、问题阐述

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

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

相关文章

来自专栏大数据和云计算技术

算法基础9:散列表

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第9篇《散列表》,非常赞!希望对大家有帮助,大家会喜欢!

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

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2776
来自专栏风中追风

高效编程之hashmap你必须要懂的知识点

以前看Java的招聘要求:Java基础扎实,熟悉常用集合类,多线程,IO,网络编程,经常会疑惑,集合类不就ArrayList,HashMap会用,熟悉下API不...

3306
来自专栏Python小屋

Python编程一定要注意的那些“坑”(九):0与False

问题描述:在编程时,经常需要单独编写一个函数用来判断某个事件是否成立,如果成立就返回正常结果,否则返回False。在主调函数中根据被调函数的返回值决定下一步的操...

1003
来自专栏编程

C语言/C加加新手入门学习经验资料分享,基础知识大汇总!

C语言是面向过程的,而C++是面向对象的 相信这么努力的你 已经置顶了我 学习C语言始终要记住“曙光在前头”和“千金难买回头看”,“千金难买回头看”是学习知识的...

1849
来自专栏后端技术探索

从头到尾解析Hash 表算法

问题描述 百度面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记...

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

3285 转圈游戏 2013年NOIP全国联赛提高组

3285 转圈游戏 2013年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2608
来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

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

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2655
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer 第二章 【变量和基本类型】

正文之前 C++的数据类型包括 算术类型(int double等)和空类型(void),今天发生了一些很可怕的事情,详情请看正文之后!!我好害怕!! 正文 1、...

38111

扫码关注云+社区