算法题-矩阵

一、矩阵1. 二维数组坐标定义模板 A逐格双层遍历判重、状态统计类题目适用有效数独、矩阵置零、生命游戏int m matrix.length; // m 总行数i行下标上下 int n matrix[0].length; // n 总列数j列下标左右 matrix[i][j]; // i先行j后列 // 从上到下遍历每一行 for(int i 0; i m; i){ // 从左到右遍历一行内每一列 for(int j 0; j n; j){ // 操作 matrix[i][j] } }2.矩阵置零// 矩阵置零示范思路 boolean[] rowFlag new boolean[m]; boolean[] colFlag new boolean[n]; // 第一轮只标记不改原矩阵 for(i,j){ if(matrix[i][j]0){ rowFlag[i]true; colFlag[j]true; } } // 第二轮依据标记统一修改 for(i,j){ if(rowFlag[i] || colFlag[j]) matrix[i][j]0; }3. 36有效的数独核心用数组 / Set 充当哈希表记录「行、列、指定区域」出现过哪些数字 套路双层循环遍历每个格子遇到有效数字先判断是否已经存在不存在就打上标记存在直接返回结果 推荐最优模板boolean 数组法boolean[][] rowHas new boolean[9][9]; boolean[][] colHas new boolean[9][9]; boolean[][][] boxHas new boolean[3][3][9]; for(int i0;i9;i){ for(int j0;j9;j){ char c board[i][j]; if(c .) continue; int x c - 1; // i/3 j/3 定位3×3小九宫 if(rowHas[i][x] || colHas[j][x] || boxHas[i/3][j/3][x]){ return false; } rowHas[i][x] colHas[j][x] boxHas[i/3][j/3][x] true; } }