2026 华为OD机试真题9月16日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定一个M行N列的矩阵，矩阵中每个元素是一个非负整数，从左上角(0,0)开始，按顺时针螺旋顺序遍历矩阵，对于遍历的每个数字，计算器二进制表示中1的个数，如果1的个数是3的倍数，则记录该数字的坐标。请按照顺序输出满足条件的数字的坐标列表。

2026 华为OD机试真题9月16日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

补充说明

螺旋遍历按照从外到内的顺序进行：从 (0,0) 出发，先向右走，遇到边界或已访问过的元素后转向，按右 → 下 → 左 → 上循环转向。

输入描述

参数 matrix 为一个 M 行 N 列的二维整数数组 (1≤M,N≤10)，每个元素 matrix[i][j] (0≤matrix[i][j]≤10^9) 为非负整数。

输出描述

返回一个二维整数数组，按遍历顺序依次记录满足条件的坐标，每个坐标写作 [行索引,列索引]。

如果没有满足条件的数字，返回空数组。数字 0 的二进制中 1 的个数为 0，按满足条件统计。

示例1

输入

[[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 的二进制为 1011，含 3 个 1，坐标为 (2,2)；7 的二进制为 111，含 3 个 1，坐标为 (1,2)。其余数字中 1 的个数为 1 或 2，都不满足条件。

按遍历顺序先记录 (2,2)，再记录 (1,2)。

示例2

输入

[[0,1],[2,4]]

输出

[[0,0]]

说明

螺旋遍历顺序为 0,1,4,2。

0 的二进制中 1 的个数为 0，是 3 的倍数，记录坐标 (0,0)；1,4,2 的二进制都只含 1 个 1，不满足条件。

示例3

输入

[[1,2]]

输出

[]

说明

1 与 2 的二进制都只含 1 个 1，没有满足条件的数字，返回空数组。

解题思路

核心思想

螺旋顺序本质上是不断处理当前未遍历区域的四条边。用 top、bottom、left、right 表示未处理矩形的四个边界，每完成一条边就收缩对应边界，因此不需要额外的 visited 矩阵。

判断一个数是否满足条件时，统计二进制中 1 的个数并判断是否能被 3 整除。0 的 1 的个数是 0，天然满足条件。不同语言分别使用内置位计数函数或 Brian Kernighan 方法实现这一判断。

算法步骤

1. 初始化四个边界，分别指向矩阵的首行、末行、首列和末列。
2. 从左到右扫描 top 行，检查每个元素并记录符合条件的坐标，然后上移 top。
3. 从上到下扫描 right 列，检查每个元素并记录符合条件的坐标，然后左移 right。
4. 如果仍存在未处理行，从右到左扫描 bottom 行，然后下移 bottom。
5. 如果仍存在未处理列，从下到上扫描 left 列，然后右移 left。
6. 重复以上过程直到四个边界交错，输出记录结果。

复杂度分析

设矩阵大小为 M×N，数值最大为 V。每个元素只访问一次，位计数最多处理 O(log V) 位，因此时间复杂度为 O(MN log V)，在题目给定范围内可视为 O(MN)。除结果数组外，边界变量只占用 O(1) 额