博客

题目展示

(问答题) 编程输出以下格式的数据。

when i=1:

1

4 5 2

3

when i=2:

1 2

8 9 10 3

7 12 11 4

6 5

拿到这道题后首先要找出输出数据的规律，不难发现，这些输出以顺时针螺旋的方式排列，且i取多少，第一行和最后一行就有几个数，中间 i 行是标准的螺旋矩阵。因此想要准确实现此题，首先需要熟悉最基本的螺旋矩阵的实现过程。

那么接下来就先整理一波螺旋矩阵的实现。

思路说明

螺旋矩阵是一个呈螺旋状的矩阵，它的数值向右->向下->向左->向上依次变大，不断循环。由于螺旋矩阵是一个循环迭代的过程，因此需要导入python模块itertools

我们用(x, y)坐标来表示螺旋矩阵的位置,顺时针方向：


右(1,0)

->【x加一格】，


下(0, 1)

->【y加一格】，


左(-1, 0)

->【x减一格】，


上(0, -1)

->【y减一格】。

坐标从(0, 0)开始，不断更新，当超过范围或者遇到障碍时改变方向。

螺旋矩阵的打印首先应该对n*n的数组进行赋值（初始化）。

代码实现

# 导入迭代器模块itertools
import itertools
# 定义spiral()函数实现螺旋矩阵
def spiral(n, m):
    # 四个状态,右-下-左-上
    _status = itertools.cycle(['right', 'down', 'left', 'up' ])
    # 每个状态所对应的坐标变化情况
    _movemap = {'right': (1, 0), 'down': (0, 1), 'left': (-1, 0), 'up': (0, -1)}
    # 初始化二维数组
    pos_map = dict.fromkeys([(x, y) for x in range(n) for y in range(m)])
    # 初始化开始位置
    _pos = (0, 0)
    # 转到下一状态
    _st = next(_status)
    for i in range(1, n*m+1):
        _oldpos = _pos  
        # 更新位置
        _pos = tuple(map(sum, zip(_pos, _movemap[_st])))    

        # 当超出维度或者遇到障碍时，改变状态
        if (_pos not in pos_map) or (pos_map[_pos]):
            _st = next(_status)
            _pos = tuple(map(sum, zip(_oldpos, _movemap[_st]))) 

        pos_map[_oldpos] = i
    return pos_map

def display_spiral(n, m):
    pos_map = spiral(n, m)
    for i in range(m):
        for j in range(n):
            print pos_map[j, i], "\t\t",
        print "\n"

display_spiral(6, 6)

明白上述过程之后，题解也就到了进阶阶段。我们结合以上，先构建中心螺旋部分，再找规律构建边缘数字。下面分别在python3和python2下对该题目进行具体的实现。

python3

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Name: demo22.py
# Author: zhuzhuzhu   time:2018/5/12
# Connect: 1406380550@qq.com
# Desc: 螺旋矩阵进阶python3

import itertools


def spiral(init):
    status = itertools.cycle(['right', 'down', 'left', 'up'])
    # 用于状态周期性的切换    
    movemap = {'right': (1, 0), 'down': (0, 1), 'left': (-1, 0), 'up': (0, -1), }
    #  初始化二维数组    
    position_map = dict.fromkeys([(x, y) for x in range(init) for y in range(init)])
    # 初始化当前位置以及当前方向    
    position = (0, 0)
    new_status = next(status)
    for i in range(4*init+1, init * (init+4) + 1):
        old_position = position
        # 根据状态进行移动        
        position = tuple(map(sum, zip(position, movemap[new_status])))
    # 如果超过范围或者碰到已经有值的位置则切换方向        
        if (position not in position_map) or (position_map[position]):
            new_status = next(status)
            position = tuple(map(sum, zip(old_position, movemap[new_status])))
        position_map[old_position] = i
    # 构造输出信息    
    print("When:init = {}".format(init))

    # 打印第一行    
    for i in range(1, init+1):
        if i < init:
            print("{}".format(i), end='\t')
        else:
            print("{}".format(i))
            # 构造中心螺旋结构    
            for i in range(init):
                print("{}".format(4 * init - i), end='\t\t')
                for j in range(init):
                    print((str(position_map[(j, i)])), end='\t\t')
                print("{}".format(i + init + 1))
            # 添加最后一行    
            for i in range(init*3, init*2, -1):
                print("{}".format(i), end='\t')
                if i == init:
                    print("{}".format(i))


if __name__ == "__main__":
    spiral(3)

python2

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Name: demo23.py
# Author: zhuzhuzhu   time:2018/5/16
# Connect: 1406380550@qq.com
# Desc: 螺旋矩阵进阶python2
import itertools
# 定义参数为init的函数


def spiral(init):
    # 四个状态
    _status = itertools.cycle(['right', 'down', 'left', 'up'])
    movemap = {"right": (1, 0), "down": (0, 1), "left": (-1, 0), "up": (0, -1), }
    # 初始化二维数组
    posmap = dict.fromkeys([(x, y) for x in range(init) for y in range(init)])
    # 初始化开始位置
    _pos = (0, 0)
    # 变换位置
    _st = next(_status)
    for i in range(4 * init + 1, init * (4 + init) + 1):
        _oldpos = _pos
        _pos = tuple(map(sum, zip(_pos, movemap[_st])))
        # 如超出维度或者遇到障碍，则改变位置
        if (_pos not in posmap) or (posmap[_pos]):
            _st = next(_status)
            _pos = tuple(map(sum, zip(_oldpos, movemap[_st])))
        posmap[_oldpos] = i
    print "When:init = %d" % init
    # 打印第一行
    for i in range(1, init+1):
        if i < init:
            print "\t%d" % i,
        else:
            print "\t%d" % i

    # 打印中间螺旋部分
    for i in range(init):
        print "\t%d" % (4 * init - i),
        for j in range(init):
            print "\t%s" % (str(posmap[j, i])),
        print "\t%d" % (i + init + 1)

    # 打印最后一行
    for i in range(3*init, 2*init, -1):
        print "\t%d" % i,
        if i == init:
            print "\t%d" % i,


if __name__ == "__main__":
    spiral(4)

题目变换

(问答题) 编程输出以下格式的数据。

When i=0

1

When i=1

7 8 9

6 1 2

5 4 3

When i=2

21 22 23 24 25

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

观察以上输出数据，不难发现，本题目是顺时针从内圈向外圈打印数据。而前面我们所提到的题目均是顺时针由外圈向内圈打印数据。因此，我们可以考虑将此题转化为逆时针从外圈向内圈打印数据的问题。

对上例代码稍作改动：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Name: demo24.py
# Author: zhuzhuzhu   time:2018/5/17
# Connect: 1406380550@qq.com
# Desc: 螺旋矩阵再进阶(逆时针)
import itertools


def spiral(init):
    # 行数
    raw = 2*init + 1
    # 逆时针遵循左-下-右-上
    status = itertools.cycle(["left", "down", "right", "up"])
    movemap = {"left": (-1, 0), "down": (0, 1), "right": (1, 0), "up": (0, -1), }
    posmap = dict.fromkeys([(x, y) for x in range(raw) for y in range(raw)])
    # 初始位置
    _pos = (raw - 1, 0)
    # 改变状态
    _st = next(status)
    # 从右上角的数开始遍历
    for i in range(raw*raw, 0, -1):
        oldpos = _pos
        _pos = tuple(map(sum, zip(_pos, movemap[_st])))
        # 超出维度或者遇到障碍
        if (_pos not in posmap) or (posmap[_pos]):
            _st = next(status)
            _pos = tuple(map(sum, zip(oldpos, movemap[_st])))
        posmap[oldpos] = i
    print "When init = %d" % init

    for i in range(raw):
        for j in range(raw):
            print "\t%s\t" % str(posmap[(j, i)]),
        print "\n"


if __name__ == "__main__":
    spiral(2)

到这里，这道题也就圆满解决啦~

总结与感想

然而，伴随着这道题的结束，真正理解的路其实才刚刚开始，要想下次遇到此类题从容不迫，还需要多下功夫多钻研，吃透母题，举一反三才是王道嘻嘻（装不下去了，我像高中班主任…