一道字节笔试题,没有想到考察的是....

脑洞前端

共 7456字,需浏览 15分钟

 ·

2021-06-03 15:05

点击上方关注 TianTianUp一起学习,天天进步

大家好,我是TianTian

分享的内容是字节的笔试题,字节的算法题。

考察的点,可以归纳于深度优先遍历,或者说是一道脑筋急转弯题。

题目

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

输入:

[

  [ 123 ],

  [ 456 ],

  [ 789 ]

]

输出:

 [1,2,3,6,9,8,7,4,5]

思路

基本上围绕的思路就是:一层层向里处理,按顺时针依次遍历:上、右、下、左。

其实很类似于迷宫的走法,走到格子后,判断下一个格子,还能不能走,也就是边界条件。遇到边界条件后,顺着上面的顺序: 上、右、下、左。

所以我们可以有几个约束条件:

  • 是不是在这个范围内,不能超过这些范围。
  • 这个格子是不是走过,存一下之前的状态。
  • 记录当前方向,抱着下一个方向是对的。

深度优先遍历

按照深度优先遍历思路来写,我们可以构造常见的dfs模版:

const spiralOrder = function (matrix{
    if (matrix.length === 0return [];
    const result = [],
        dx = [010-1],
        dy = [10-10],
        col = matrix.length,
        row = matrix[0].length;
    // isCheckMatrix记录是否走过
    const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false))) 
    const dfs = (x, y, directionIndex) => {
          // 逻辑代码
            // 通常这里做逻辑处理,边界处理
        }
    };
    dfs(000);
    return result
};

这应该就是基础的模版,唯一不同的是,我们看dfs的三个参数,x,y,directionIndex

x和y参数很好理解,这个directionIndex参数含义就是告诉我们当前前进的方向。

接下来,是写我们的逻辑部分。首先确定接下来走到哪一个格子:

dx = [010-1]
dy = [10-10]
const nextX = x + dx[directionIndex]
const nextY = y + dy[directionIndex]

根据当前的格子所在的位置x,y我们就知道接下来要走的位置,通过directionIndex的下标索引,知道我们下一个格子的坐标。

然后就是判断一下,边界的情况:

  • 不能出界
  • 判断能不能走

根据以上的信息,其实我们主要的逻辑部分就完成啦。

代码:

const spiralOrder = function (matrix{
    if (matrix.length === 0return [];
    const result = [],
        dx = [010-1],
        dy = [10-10],
        col = matrix.length,
        row = matrix[0].length;
    const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))
    const dfs = (x, y, directionIndex) => {
        result.push(matrix[x][y]) // 存答案
        isCheckMatrix[x][y] = true // 标记走过
        for (let i = 0; i < 3; i++) {
            const nextX = x + dx[directionIndex]
            const nextY = y + dy[directionIndex]
            // 判断边界
            if (nextX < col && nextX >= 0 && nextY < row && nextY >= 0 && !isCheckMatrix[nextX][nextY]) {
                dfs(nextX, nextY, directionIndex)
            }
            // 方向取余数
            directionIndex = (directionIndex + 1) % 4;
        }
    };
    dfs(000);
    return result
};

这里我们需要对方向做余数处理。在确只有四个方向的情况,并且在这个方向不能走的情况下,尝试下一个方向。

directionIndex = (directionIndex + 1) % 4;

优化

写完的时候,我在想能不能优化一下,做个减枝的处理,后面发现,当前这个位置可以走的话,是不是就不能判断其他方向了。

或者说我们可以提前走出这个循环,这里做的优化就是return 当前的处理。

代码:

const spiralOrder = function (matrix{
    if (matrix.length === 0return [];
    const result = [],
        dx = [010-1],
        dy = [10-10],
        col = matrix.length,
        row = matrix[0].length;
    const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))
    const dfs = (x, y, directionIndex) => {
        result.push(matrix[x][y]);
        isCheckMatrix[x][y] = true
        for (let i = 0; i < 3; i++) {
            const nextX = x + dx[directionIndex]
            const nextY = y + dy[directionIndex]
            if (nextX < col && nextX >= 0 && nextY < row && nextY >= 0 && !isCheckMatrix[nextX][nextY]) {
                return dfs(nextX, nextY, directionIndex)
            }
            directionIndex = (directionIndex + 1) % 4;
        }
    };
    dfs(000);
    return result
};

后记

后面发现这个是一道leetcode中等的题目,题目链接:

螺旋矩阵: https://leetcode-cn.com/problems/spiral-matrix/

可能写的过程有点简单,最优解应该不是我这个,leetcode评论区里面有很多解法,类似于脑筋急转弯,感兴趣的话可以看看。

最后

对于深度优先遍历算法入门的文章,可以看看我这篇文章:

「算法与数据结构」DFS和BFS算法之美

或者可以阅读原文,掘金阅读体验可能更加友好。

面试交流群持续开放,分享了 许多 个面经。 

加我微信: DayDay2021,备注面试,拉你进群。


我是 TianTian,我们下篇见~

爱心三连击

1.看到这里了就点个在看支持下吧,你的在看是我创作的动力。

2.关注公众号脑洞前端,获取更多前端硬核文章!加个星标,不错过每一条成长的机会。

3.如果你觉得本文的内容对你有帮助,就帮我转发一下吧。

浏览 21
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报