记录一个面试算法题

- 日理万妓 2022-02-23 01:50 256阅读 0赞

*这周在QQ群里看到一位朋友问了一个算法题，好像是他面试时遇到的，当时比较忙，大致看了下这个题目，一下子还没有想出来该怎么做，不过我觉得这个题目还是挺有意思的，把题目保存起来了，今天放假上午在图书馆学习时记起了这个题目，就思考了一会，有了思路。下午又有事耽搁去了，没有来将它做完，只得晚上这会稍微闲暇一点，就把上午的思路转换为代码来将它实现吧。*

## **题目：** ##

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70][]**

**在命令行输入一个自然数N，实现如下面实例：**

**N=3时：**

**123**

**894**

**765**

**N=6时：**

01  02  03  04  05  06   
 20  21  22  23  24  07   
 19  32  33  34  25  08   
 18  31  36  35  26  09   
 17  30  29  28  27  10   
 16  15  14  13  12  11

## 解题思路： ##

我在画图软件里简单画了下，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70 1][]

即一个数组的某个点可以走的路径为：右->下->左->上

然后按着这个顺序一直循环，直到所有数字都填入到数组中

public class JavaTest {
        /**
         * 长度大小
         */
        private static int LENGTH = 6;
    
        public static void main(String[] args) {
    
            int max = LENGTH * LENGTH;
            int maxNumberWeiShu = (max + "").length();
            System.out.println("最大数的位数为：" + maxNumberWeiShu);
            String formatStr = " %0" + maxNumberWeiShu + "d ";
    
            int[][] array = new int[LENGTH][LENGTH];
    
            int index = 1;
            int i = 0, j = 0;
            while (index < max) {
                while (j + 1 < LENGTH && array[i][j + 1] == 0) {
                    array[i][++j] = index++;
                    System.out.println("next  右");
                }
                while (i + 1 < LENGTH && array[i + 1][j] == 0) {
                    array[++i][j] = index++;
                    System.out.println("next  下");
                }
                while (j - 1 >= 0 && array[i][j - 1] == 0) {
                    array[i][--j] = index++;
                    System.out.println("next  左");
                }
                while (i - 1 > 0 && array[i - 1][j] == 0) {
                    array[--i][j] = index++;
                    System.out.println("next  上");
                }
    
            }
    
            for (int row = 0; row < LENGTH; row++) {
                for (int col = 0; col < LENGTH; col++) {
    
                    System.out.printf(formatStr, array[row][col] + 1);
                }
                System.out.println();
            }
        }
    }

当输入为7时，上面代码的输出为：

最大数的位数为：2
    next  右
    next  右
    next  右
    next  右
    next  右
    next  右
    next  下
    next  下
    next  下
    next  下
    next  下
    next  下
    next  左
    next  左
    next  左
    next  左
    next  左
    next  左
    next  上
    next  上
    next  上
    next  上
    next  上
    next  右
    next  右
    next  右
    next  右
    next  右
    next  下
    next  下
    next  下
    next  下
    next  左
    next  左
    next  左
    next  左
    next  上
    next  上
    next  上
    next  右
    next  右
    next  右
    next  下
    next  下
    next  左
    next  左
    next  上
    next  右
     01  02  03  04  05  06  07 
     24  25  26  27  28  29  08 
     23  40  41  42  43  30  09 
     22  39  48  49  44  31  10 
     21  38  47  46  45  32  11 
     20  37  36  35  34  33  12 
     19  18  17  16  15  14  13

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70]: /images/20220223/d1bbdba6735e4b9287fb730a83321c79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70 1]: /images/20220223/1491af962f704230922283cdf9fb7572.png