华为OD机试真题 新系统 2026-09-16 PythonJS【矩阵螺旋遍历】

目录题目思路Code题目题目内容给定一个 M 行 N 列的矩阵矩阵中的每个元素都是非负整数。从左上角坐标 (0,0) 开始按照从外到内的顺时针螺旋顺序遍历矩阵。对遍历到的每个数字统计其二进制表示中 1 的个数如果这个数量是 3 的倍数则记录该数字的坐标。请按照遍历顺序输出所有满足条件的坐标。数字 0 的二进制表示中 1 的个数为 0因此也满足条件。1 ≤ M,N ≤ 100 ≤ matrix[i][j] ≤ 10^9。输入描述第一行输入两个整数 M 和 N分别表示矩阵的行数和列数。接下来 M 行每行输入 N 个以空格分隔的非负整数。输出描述按遍历顺序输出满足条件的坐标每个坐标格式为 (行索引,列索引)相邻坐标之间以一个空格分隔。如果没有满足条件的数字则输出空行。样例 1输入3 4 1 2 3 4 5 6 7 8 9 10 11 12输出(2,2) (1,2)说明螺旋遍历顺序为 1、2、3、4、8、12、11、10、9、5、6、7。数字 11 和 7 的二进制表示中都含有 3 个 1因此依次输出它们的坐标 (2,2) 和 (1,2)。思路整体思路用四个边界表示尚未遍历的矩形区域每轮依次扫描上边、右边、下边和左边。访问元素时同步统计二进制中 1 的个数满足条件就记录坐标。第一步初始化 top、bottom、left、right分别指向当前未遍历区域的上、下、左、右边界。第二步从左到右扫描上边再从上到下扫描右边每完成一条边就把对应边界向内收缩一格。第三步只有当收缩后仍存在未处理行时才从右到左扫描下边只有仍存在未处理列时才从下到上扫描左边。两个判断可以避免单行或单列矩阵中的元素被重复访问。第四步使用不断清除最低位 1 的方法统计二进制中 1 的个数。计数能被 3 整除时记录当前坐标0 不进入循环计数保持为 0因此自然满足条件。正确性说明四个方向按顺时针顺序覆盖当前矩形的四条边边界收缩后这些元素不会再次进入未处理区域。循环结束时每个矩阵元素恰好被访问一次满足条件的坐标也按螺旋访问顺序加入答案。边界处理单行和单列需要在扫描下边与左边前重新检查边界没有符合条件的元素时答案为空矩阵元素为 0 时必须记录。复杂度分析每个元素只访问一次每次位计数最多处理整数二进制中的 1时间复杂度为 O(MN log V)其中 V 是矩阵最大值除输出坐标外额外空间复杂度为 O(1)。Codeimport sys def qualifies(value: int) - bool: count 0 # 每次 value (value - 1) 都会清除最低位的一个 1循环次数正好等于二进制 1 的数量。 while value: value value - 1 count 1 # 初始输入为 0 时循环不会执行count 保持为 0符合题目中“0 也满足”的规则。 return count % 3 0 def solve(matrix: list[list[int]]) - list[tuple[int, int]]: rows len(matrix) cols len(matrix[0]) answer [] # 四个边界始终包围尚未访问的矩形区域边界外的元素都已经按螺旋顺序处理完毕。 top, bottom 0, rows - 1 left, right 0, cols - 1 while top bottom and left right: # 当前轮先从左到右走完上边随后收缩上边界保证这一行不再被访问。 for col in range(left, right 1): if qualifies(matrix[top][col]): answer.append((top, col)) top 1 # 再从上到下走右边起点使用更新后的 top不会重复右上角。 for row in range(top, bottom 1): if qualifies(matrix[row][right]): answer.append((row, right)) right - 1 # 收缩后可能已经没有剩余行先判断可避免单行矩阵的元素被反向再扫一次。 if top bottom: for col in range(right, left - 1, -1): if qualifies(matrix[bottom][col]): answer.append((bottom, col)) bottom - 1 # 同理只有仍有未处理列时才向上扫描左边避免单列矩阵重复。 if left right: for row in range(bottom, top - 1, -1): if qualifies(matrix[row][left]): answer.append((row, left)) left 1 return answer data list(map(int, sys.stdin.buffer.read().split())) rows, cols data[0], data[1] # 前两个整数是尺寸之后每连续 cols 个整数还原成矩阵的一行。 matrix [ data[2 row * cols:2 (row 1) * cols] for row in range(rows) ] answer solve(matrix) # join 同时处理坐标间单空格和空答案答案为空时只输出题目要求的空行。 print( .join(f({row},{col}) for row, col in answer))JSconst fs require(fs); function qualifies(value) { let count 0; // value (value - 1) 每次清除最低位的一个 1循环次数就是二进制 1 的数量。 while (value ! 0) { value value - 1; count; } // value 初始为 0 时 count 保持为 0按题意也应判为满足条件。 return count % 3 0; } function solve(matrix) { const rows matrix.length; const cols matrix[0].length; const answer []; // 四个边界始终表示尚未访问的矩形边界外元素均已按螺旋顺序处理。 let top 0; let bottom rows - 1; let left 0; let right cols - 1; while (top bottom left right) { // 从左到右扫描上边后上移 top使已访问行不再进入后续区域。 for (let col left; col right; col) { if (qualifies(matrix[top][col])) { answer.push([top, col]); } } top; // 从更新后的 top 开始向下扫描右边避免重复右上角。 for (let row top; row bottom; row) { if (qualifies(matrix[row][right])) { answer.push([row, right]); } } right--; // 单行区域在上边扫描后已经耗尽复核行边界可避免反向重复扫描。 if (top bottom) { for (let col right; col left; col--) { if (qualifies(matrix[bottom][col])) { answer.push([bottom, col]); } } bottom--; } // 单列区域在右边扫描后可能耗尽仍有列时才从下向上扫描左边。 if (left right) { for (let row bottom; row top; row--) { if (qualifies(matrix[row][left])) { answer.push([row, left]); } } left; } } return answer; } const data fs.readFileSync(0, utf8).trim().split(/\s/).map(Number); const rows data[0]; const cols data[1]; const matrix []; let index 2; // 前两个整数是尺寸后续数字每 cols 个切成矩阵的一行。 for (let row 0; row rows; row) { matrix.push(data.slice(index, index cols)); index cols; } const answer solve(matrix); // join 同时保证坐标间只有一个空格并让无答案场景输出空行。 console.log(answer.map(([row, col]) (${row},${col})).join( ));【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。