1. 华为OD机考双机位C卷实战解析最近刚参加完华为OD的机考抽到了C卷的敌情监控题目用Java实现了一套解决方案。作为过来人想分享下这道题的解题思路和实战经验给准备参加机考的朋友们参考。这道题主要考察对二维矩阵的处理能力和双指针技巧的运用。题目会给出一个N×N的矩阵模拟战场环境其中包含敌军、友军和平地区域要求编写监控程序快速统计特定区域的敌情。这类题型在华为OD机考中属于中等难度但非常考验代码的健壮性和边界处理能力。2. 题目需求与技术要点2.1 核心问题描述给定一个N×N的矩阵grid其中grid[i][j] 1 表示敌军单位grid[i][j] 2 表示友军单位grid[i][j] 0 表示空白区域需要实现以下功能统计任意矩形区域内的敌军数量确保统计时不会被友军单位阻挡视线处理多个区域查询请求2.2 关键技术难点这道题的主要难点在于如何高效处理大规模矩阵的区域查询视线阻挡的判断逻辑实现在双机位监考环境下保证代码一次通过3. 解决方案设计与实现3.1 预处理优化思路直接遍历查询区域虽然简单但在多次查询时效率太低。我采用了前缀和矩阵进行优化class EnemyMonitor { private int[][] prefixSum; public EnemyMonitor(int[][] grid) { int n grid.length; prefixSum new int[n1][n1]; for(int i1; in; i) { for(int j1; jn; j) { prefixSum[i][j] prefixSum[i-1][j] prefixSum[i][j-1] - prefixSum[i-1][j-1] (grid[i-1][j-1] 1 ? 1 : 0); } } } }3.2 视线阻挡处理算法友军单位会阻挡监控视线需要特殊处理。我使用动态规划的方法记录每个位置最近的友军private int[][] leftBlock; // 记录左侧最近的友军 private int[][] topBlock; // 记录上方最近的友军 private void preprocessBlocks(int[][] grid) { int n grid.length; leftBlock new int[n][n]; topBlock new int[n][n]; // 横向扫描处理左侧阻挡 for(int i0; in; i) { int lastBlock -1; for(int j0; jn; j) { if(grid[i][j] 2) lastBlock j; leftBlock[i][j] lastBlock; } } // 纵向扫描处理上方阻挡 for(int j0; jn; j) { int lastBlock -1; for(int i0; in; i) { if(grid[i][j] 2) lastBlock i; topBlock[i][j] lastBlock; } } }3.3 区域查询实现结合前缀和与阻挡信息实现高效查询public int query(int row1, int col1, int row2, int col2) { // 检查边界条件 if(row1 row2 || col1 col2) return 0; // 计算原始区域敌军数量 int total prefixSum[row21][col21] - prefixSum[row1][col21] - prefixSum[row21][col1] prefixSum[row1][col1]; // 减去被阻挡的敌军 for(int irow1; irow2; i) { for(int jcol1; jcol2; j) { if(prefixSum[i1][j1] - prefixSum[i][j1] - prefixSum[i1][j] prefixSum[i][j] 1) { if(leftBlock[i][j] col1 || topBlock[i][j] row1) { total--; } } } } return total; }4. 机考实战经验与优化技巧4.1 双机位环境下的编程要点代码规范华为机考对代码规范要求严格务必注意类名使用大驼峰方法名使用小驼峰适当添加注释但不需过度测试用例设计void testCase1() { int[][] grid {{1,0,0},{0,2,0},{0,0,1}}; EnemyMonitor monitor new EnemyMonitor(grid); assert monitor.query(0,0,2,2) 1; // 友军阻挡 assert monitor.query(0,0,0,0) 1; }4.2 性能优化技巧空间优化可以将前缀和矩阵与阻挡矩阵合并存储查询优化对密集查询可以使用Mos算法进一步优化并行处理对于超大矩阵可以考虑分块处理5. 常见问题与解决方案5.1 边界条件处理常见错误包括矩阵索引越界空矩阵处理不当查询区域超出矩阵范围解决方案// 在查询方法开始处添加边界检查 if(row1 0) row1 0; if(col1 0) col1 0; if(row2 n) row2 n-1; if(col2 n) col2 n-1;5.2 时间复杂度分析预处理阶段前缀和矩阵O(N²)阻挡矩阵O(N²)查询阶段基础查询O(1)阻挡检查最坏O(N²)平均O(1)6. 代码重构与质量保证6.1 重构建议使用工厂模式创建监控器添加输入验证实现日志记录功能优化后的类结构public class EnemyMonitorFactory { public static EnemyMonitor create(int[][] grid) { if(grid null || grid.length 0) { throw new IllegalArgumentException(Invalid grid input); } return new EnemyMonitor(grid); } }6.2 单元测试覆盖完整的测试用例应该包括空矩阵测试全敌军矩阵测试全友军矩阵测试随机矩阵测试边界查询测试示例测试方法Test public void testFullEnemyGrid() { int[][] grid new int[100][100]; Arrays.fill(grid, 1); EnemyMonitor monitor EnemyMonitorFactory.create(grid); assertEquals(10000, monitor.query(0, 0, 99, 99)); }7. 类似题型扩展训练7.1 推荐练习题目矩阵区域和检索 - 可变版本二维区间求和查询战场信息统计系统7.2 算法扩展应用这种前缀和动态规划的思路还可以应用于图像处理中的卷积运算游戏中的视野计算地理信息系统中的区域统计8. 华为OD机考备考建议重点准备领域数据结构数组、链表、树、图算法排序、搜索、动态规划设计模式单例、工厂、观察者时间管理技巧先完成所有题目基础功能留出20分钟检查边界条件最后优化性能代码风格提示使用有意义的变量名保持方法短小专注适当添加关键注释在华为OD机考中拿到高分的关键在于清晰的解题思路、严谨的代码实现、全面的测试考虑。这道敌情监控题目很好地考察了候选人的综合能力建议在备考时多练习类似题型。 
长河君 · 2026/10/24 5:28:34 · 阅读 1.2k 华为OD机考C卷敌情监控题解与双指针技巧
1. 华为OD机考双机位C卷实战解析最近刚参加完华为OD的机考抽到了C卷的敌情监控题目用Java实现了一套解决方案。作为过来人想分享下这道题的解题思路和实战经验给准备参加机考的朋友们参考。这道题主要考察对二维矩阵的处理能力和双指针技巧的运用。题目会给出一个N×N的矩阵模拟战场环境其中包含敌军、友军和平地区域要求编写监控程序快速统计特定区域的敌情。这类题型在华为OD机考中属于中等难度但非常考验代码的健壮性和边界处理能力。2. 题目需求与技术要点2.1 核心问题描述给定一个N×N的矩阵grid其中grid[i][j] 1 表示敌军单位grid[i][j] 2 表示友军单位grid[i][j] 0 表示空白区域需要实现以下功能统计任意矩形区域内的敌军数量确保统计时不会被友军单位阻挡视线处理多个区域查询请求2.2 关键技术难点这道题的主要难点在于如何高效处理大规模矩阵的区域查询视线阻挡的判断逻辑实现在双机位监考环境下保证代码一次通过3. 解决方案设计与实现3.1 预处理优化思路直接遍历查询区域虽然简单但在多次查询时效率太低。我采用了前缀和矩阵进行优化class EnemyMonitor { private int[][] prefixSum; public EnemyMonitor(int[][] grid) { int n grid.length; prefixSum new int[n1][n1]; for(int i1; in; i) { for(int j1; jn; j) { prefixSum[i][j] prefixSum[i-1][j] prefixSum[i][j-1] - prefixSum[i-1][j-1] (grid[i-1][j-1] 1 ? 1 : 0); } } } }3.2 视线阻挡处理算法友军单位会阻挡监控视线需要特殊处理。我使用动态规划的方法记录每个位置最近的友军private int[][] leftBlock; // 记录左侧最近的友军 private int[][] topBlock; // 记录上方最近的友军 private void preprocessBlocks(int[][] grid) { int n grid.length; leftBlock new int[n][n]; topBlock new int[n][n]; // 横向扫描处理左侧阻挡 for(int i0; in; i) { int lastBlock -1; for(int j0; jn; j) { if(grid[i][j] 2) lastBlock j; leftBlock[i][j] lastBlock; } } // 纵向扫描处理上方阻挡 for(int j0; jn; j) { int lastBlock -1; for(int i0; in; i) { if(grid[i][j] 2) lastBlock i; topBlock[i][j] lastBlock; } } }3.3 区域查询实现结合前缀和与阻挡信息实现高效查询public int query(int row1, int col1, int row2, int col2) { // 检查边界条件 if(row1 row2 || col1 col2) return 0; // 计算原始区域敌军数量 int total prefixSum[row21][col21] - prefixSum[row1][col21] - prefixSum[row21][col1] prefixSum[row1][col1]; // 减去被阻挡的敌军 for(int irow1; irow2; i) { for(int jcol1; jcol2; j) { if(prefixSum[i1][j1] - prefixSum[i][j1] - prefixSum[i1][j] prefixSum[i][j] 1) { if(leftBlock[i][j] col1 || topBlock[i][j] row1) { total--; } } } } return total; }4. 机考实战经验与优化技巧4.1 双机位环境下的编程要点代码规范华为机考对代码规范要求严格务必注意类名使用大驼峰方法名使用小驼峰适当添加注释但不需过度测试用例设计void testCase1() { int[][] grid {{1,0,0},{0,2,0},{0,0,1}}; EnemyMonitor monitor new EnemyMonitor(grid); assert monitor.query(0,0,2,2) 1; // 友军阻挡 assert monitor.query(0,0,0,0) 1; }4.2 性能优化技巧空间优化可以将前缀和矩阵与阻挡矩阵合并存储查询优化对密集查询可以使用Mos算法进一步优化并行处理对于超大矩阵可以考虑分块处理5. 常见问题与解决方案5.1 边界条件处理常见错误包括矩阵索引越界空矩阵处理不当查询区域超出矩阵范围解决方案// 在查询方法开始处添加边界检查 if(row1 0) row1 0; if(col1 0) col1 0; if(row2 n) row2 n-1; if(col2 n) col2 n-1;5.2 时间复杂度分析预处理阶段前缀和矩阵O(N²)阻挡矩阵O(N²)查询阶段基础查询O(1)阻挡检查最坏O(N²)平均O(1)6. 代码重构与质量保证6.1 重构建议使用工厂模式创建监控器添加输入验证实现日志记录功能优化后的类结构public class EnemyMonitorFactory { public static EnemyMonitor create(int[][] grid) { if(grid null || grid.length 0) { throw new IllegalArgumentException(Invalid grid input); } return new EnemyMonitor(grid); } }6.2 单元测试覆盖完整的测试用例应该包括空矩阵测试全敌军矩阵测试全友军矩阵测试随机矩阵测试边界查询测试示例测试方法Test public void testFullEnemyGrid() { int[][] grid new int[100][100]; Arrays.fill(grid, 1); EnemyMonitor monitor EnemyMonitorFactory.create(grid); assertEquals(10000, monitor.query(0, 0, 99, 99)); }7. 类似题型扩展训练7.1 推荐练习题目矩阵区域和检索 - 可变版本二维区间求和查询战场信息统计系统7.2 算法扩展应用这种前缀和动态规划的思路还可以应用于图像处理中的卷积运算游戏中的视野计算地理信息系统中的区域统计8. 华为OD机考备考建议重点准备领域数据结构数组、链表、树、图算法排序、搜索、动态规划设计模式单例、工厂、观察者时间管理技巧先完成所有题目基础功能留出20分钟检查边界条件最后优化性能代码风格提示使用有意义的变量名保持方法短小专注适当添加关键注释在华为OD机考中拿到高分的关键在于清晰的解题思路、严谨的代码实现、全面的测试考虑。这道敌情监控题目很好地考察了候选人的综合能力建议在备考时多练习类似题型。