文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-03 05:40

关注

大家好,我是TianTian。

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

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

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

输入:

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

输出:

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

思路

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

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

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

深度优先遍历

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

  1. const spiralOrder = function (matrix) { 
  2.     if (matrix.length === 0) return []; 
  3.     const result = [], 
  4.         dx = [0, 1, 0, -1], 
  5.         dy = [1, 0, -1, 0], 
  6.         col = matrix.length, 
  7.         row = matrix[0].length; 
  8.     // isCheckMatrix记录是否走过 
  9.     const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))  
  10.     const dfs = (x, y, directionIndex) => { 
  11.           // 逻辑代码 
  12.             // 通常这里做逻辑处理,边界处理 
  13.         } 
  14.     }; 
  15.     dfs(0, 0, 0); 
  16.     return result 
  17. }; 

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

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

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

  1. dx = [0, 1, 0, -1] 
  2. dy = [1, 0, -1, 0] 
  3. const nextX = x + dx[directionIndex] 
  4. const nextY = y + dy[directionIndex] 

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

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

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

代码:

  1. const spiralOrder = function (matrix) { 
  2.     if (matrix.length === 0) return []; 
  3.     const result = [], 
  4.         dx = [0, 1, 0, -1], 
  5.         dy = [1, 0, -1, 0], 
  6.         col = matrix.length, 
  7.         row = matrix[0].length; 
  8.     const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false))) 
  9.     const dfs = (x, y, directionIndex) => { 
  10.         result.push(matrix[x][y]) // 存答案 
  11.         isCheckMatrix[x][y] = true // 标记走过 
  12.         for (let i = 0; i < 3; i++) { 
  13.             const nextX = x + dx[directionIndex] 
  14.             const nextY = y + dy[directionIndex] 
  15.             // 判断边界 
  16.             if (nextX < col && nextX >= 0 && nextY < row && nextY >= 0 && !isCheckMatrix[nextX][nextY]) { 
  17.                 dfs(nextX, nextY, directionIndex) 
  18.             } 
  19.             // 方向取余数 
  20.             directionIndex = (directionIndex + 1) % 4; 
  21.         } 
  22.     }; 
  23.     dfs(0, 0, 0); 
  24.     return result 
  25. }; 

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

  1. directionIndex = (directionIndex + 1) % 4; 

优化

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

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

代码:

  1. const spiralOrder = function (matrix) { 
  2.     if (matrix.length === 0) return []; 
  3.     const result = [], 
  4.         dx = [0, 1, 0, -1], 
  5.         dy = [1, 0, -1, 0], 
  6.         col = matrix.length, 
  7.         row = matrix[0].length; 
  8.     const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false))) 
  9.     const dfs = (x, y, directionIndex) => { 
  10.         result.push(matrix[x][y]); 
  11.         isCheckMatrix[x][y] = true 
  12.         for (let i = 0; i < 3; i++) { 
  13.             const nextX = x + dx[directionIndex] 
  14.             const nextY = y + dy[directionIndex] 
  15.             if (nextX < col && nextX >= 0 && nextY < row && nextY >= 0 && !isCheckMatrix[nextX][nextY]) { 
  16.                 return dfs(nextX, nextY, directionIndex) 
  17.             } 
  18.             directionIndex = (directionIndex + 1) % 4; 
  19.         } 
  20.     }; 
  21.     dfs(0, 0, 0); 
  22.     return result 
  23. }; 

后记

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

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

 

来源: TianTianUp内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯