V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
imlink
V2EX  ›  问与答

一道编程题,可能是我想复杂了

  •  
  •   imlink · 2018-02-24 18:15:05 +08:00 · 2544 次点击
    这是一个创建于 2224 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    原矩阵 tmp_circleNo_array顺时针取值, tmp_circleNo_array
    得到新的结果数组tmp_result_array

    下面是我的思路过程,有可能开始就想复杂了,导致中间需要创建很多辅助矩阵

    思路

    创建一个辅助顺序矩阵(对应原矩阵的每个元素的最终顺序 ),

    顺序矩阵tmp_originNo_array 然后在遍历原矩阵的时候,对照对应位置的顺序矩阵结果数组赋值。

    步骤

    1. 得到顺序矩阵

      • 为了方面得到顺序矩阵,先产生一个圈数矩阵(对应原矩阵的每个元素所在的圈数)和一个顺序中间矩阵
        圈数矩阵tmp_originNo_array+顺序中间矩阵tmp_originNo_array=顺序矩阵tmp_originNo_array

      思路:上图顺序矩阵中的 17 其实对应的顺序中间矩阵中的第二个圈的第一个数字 1,1 如何变成 17,17=1+第一个圈的长度( 16 ),每一个圈的长度都有一定的规律,
      缩写下:     2*(currentColumnNum+currentLineNum)-4
      数字意义: 长+宽+长+宽-重复计算的部分
      这里第三圈的外圈长度等于第一圈长度+第二圈的长度,第四也是如此依次递推,所以需要一个递推函数,单独计算外圈的总长度
      outSideLength = countOutSideLength({lineLength,columnLength,currentCircleNo})

      • 得到圈数矩阵的过程
        根据原矩阵初始化一个矩阵
        tmp_originNo_ing1_array转换成tmp_originNo_ing1_array最后转换成圈数矩阵tmp_originNo_ing1_array

      • 得到顺序中间矩阵的过程
        用上面得到的圈数矩阵复制然后扩充得到一个新的矩阵 tmp_originNo_ing1_array遍历内圈判断每个元素位于圈的上,右,下,左用一定规律得到顺序中间矩阵tmp_originNo_array

      • 得到顺序矩阵
        遍历上面得到的顺序中间矩阵,每个元素加上外圈的总长度得到顺序矩阵(这部可以和上一步骤合并,在上一个的遍历内圈时同时加上外圈的总长度)

    2. 得到结果数组
      初始化结果数组为一个长度为原矩阵的长*宽的数组,遍历顺序矩阵tmp_originNo_array ,将对应的行和列的原矩阵 tmp_circleNo_array赋值给结果数组(比如顺序矩阵的第 4 行的第三列的对应的是 22,那么结果数组的( 22-1 )个元素为原矩阵的第 4 行的第三列对应的 13 )

    21 条回复    2018-02-24 20:35:10 +08:00
    steel1990
        1
    steel1990  
       2018-02-24 18:22:30 +08:00 via Android
    用一个标记记录当前遍历的方向,方向按顺时针变化就好了啊。
    moonmagian
        2
    moonmagian  
       2018-02-24 18:24:17 +08:00 via Android
    实际上只存在左至右,上至下,右至左,下至上四个按顺序遍历的过程,实际上在每一轮这样的遍历,进行遍历时都比上次遍历少得到两个数,那么可以使用一个记录当前位置的变量,直接一圈一圈地得到结果数组,应该也是一种思路
    imlink
        3
    imlink  
    OP
       2018-02-24 18:36:34 +08:00 via Android
    @moonmagian 应该是没一轮少 4,少了 4 个角。这确实是个方法。
    akira
        4
    akira  
       2018-02-24 18:37:14 +08:00
    1l 2l 的方法就可以了,只是具体实现的方法有好几个,随便一个都比你现在的要好
    ant2017
        5
    ant2017  
       2018-02-24 18:38:07 +08:00 via Android
    取第一行,旋转矩阵,取第一行,旋转矩阵…
    swulling
        6
    swulling  
       2018-02-24 18:49:51 +08:00 via iPad
    确实复杂了。
    abusizhishen
        7
    abusizhishen  
       2018-02-24 18:50:20 +08:00 via Android
    懵逼中
    akira
        8
    akira  
       2018-02-24 18:51:10 +08:00
    另外,这种题目感觉应该可以通过纯数学方式来解答的,可惜现在矩阵什么的 完全还给老师了。。
    imlink
        9
    imlink  
    OP
       2018-02-24 18:57:10 +08:00
    脑回路太复杂,其实一开始也是有想过 2 楼的方案,觉得遍历的时候的变量太多放弃了。最后选择了更复杂的方案。
    acros
        10
    acros  
       2018-02-24 19:06:10 +08:00 via iPhone
    按一楼的空间 n,时间 n,不是很方便吗,还有其他要求?
    awolfly9
        11
    awolfly9  
       2018-02-24 19:11:37 +08:00 via Android
    这个问题还是我司的面试题
    akira
        12
    akira  
       2018-02-24 19:13:58 +08:00
    已知以下数列
    1
    1 2 4 3
    1 2 3 6 9 8 7 4 5

    请尝试给出此数列的数学描述 @@
    imlink
        13
    imlink  
    OP
       2018-02-24 19:19:50 +08:00 via Android
    @awolfly9 哈哈 我大概知道了 不过我挂上来 就不会回邮件了
    liuhaotian
        14
    liuhaotian  
       2018-02-24 19:23:18 +08:00
    taifus
        15
    taifus  
       2018-02-24 19:55:16 +08:00 via Android   ❤️ 1
    蛇形数组 🤓
    vindurriel
        16
    vindurriel  
       2018-02-24 19:57:00 +08:00 via iPhone
    这不就是贪吃蛇么?往一个方向走 越界或者撞墙就右转
    mdluo
        17
    mdluo  
       2018-02-24 20:16:35 +08:00
    一个循环就能搞定,帮你用 JavaScript 写了个 11 行的函数:



    下面是在线版地址:

    https://repl.it/@mdluo/clockwise-array
    mdluo
        18
    mdluo  
       2018-02-24 20:25:28 +08:00
    @mdluo #17 上面这个代码处理边界条件有些问题,仅提供个思路,有时间你可以自己修复

    p 表示当前在处理第几条边
    nav 表示当前边( p%4 )的两个相邻元素之间的索引位置差值
    count 用来记录当前边( p%2 )的剩余元素个数
    sun1991
        19
    sun1991  
       2018-02-24 20:27:05 +08:00
    类似寻路算法, 撞墙或者撞到以前访问过的节点, 就右转 90 度不就行了嘛
    kaifeii
        20
    kaifeii  
       2018-02-24 20:31:19 +08:00
    对于 n,m 矩阵,直接建 n*m 的数组,然后遍历矩阵,对于第 i 行第 j 列:
    i>j : i,j-> (n+m-2(j+1))*2*(j+1)-(j-1-i)
    i=j : i,j-> (n+m-2j)*2*(j)+1
    i<j : i,j-> (n+m-2i)*2*i+j-i+1
    直接赋值
    kaifeii
        21
    kaifeii  
       2018-02-24 20:35:10 +08:00
    @kaifeii 细节可能有错,大体就这么个意思,对于左上半部分对角线上的点来说,算是一圈开头。在这之前已经转过的圈的总和是 (总行数+总列数-2*对角线点的列)*2*对角线点的列。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5342 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 08:24 · PVG 16:24 · LAX 01:24 · JFK 04:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.