day5-数组

1、有效的数独

1. 描述

   请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。
   数字 1-9 在每一列只能出现一次。
   数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）注意：
   一个有效的数独（部分已被填充）不一定是可解的。
   只需要根据以上规则，验证已经填入的数字是否有效即可。
   空白格用 '.' 表示。示例 1：
   输入：board = 
   [["5","3",".",".","7",".",".",".","."]
   ,["6",".",".","1","9","5",".",".","."]
   ,[".","9","8",".",".",".",".","6","."]
   ,["8",".",".",".","6",".",".",".","3"]
   ,["4",".",".","8",".","3",".",".","1"]
   ,["7",".",".",".","2",".",".",".","6"]
   ,[".","6",".",".",".",".","2","8","."]
   ,[".",".",".","4","1","9",".",".","5"]
   ,[".",".",".",".","8",".",".","7","9"]]
   输出：true
   示例 2：输入：board = 
   [["8","3",".",".","7",".",".",".","."]
   ,["6",".",".","1","9","5",".",".","."]
   ,[".","9","8",".",".",".",".","6","."]
   ,["8",".",".",".","6",".",".",".","3"]
   ,["4",".",".","8",".","3",".",".","1"]
   ,["7",".",".",".","2",".",".",".","6"]
   ,[".","6",".",".",".",".","2","8","."]
   ,[".",".",".","4","1","9",".",".","5"]
   ,[".",".",".",".","8",".",".","7","9"]]
   输出：false
   解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
   

2. 思路

   按行/列/块读取，判断是否重复

3. 代码

   #include 
   using namespace std;
   #include class Solution {
   public:bool isValidSudoku(vector>& board) {vector tmp;vector block;for(int i = 0; i < 9; i++) {tmp.clear();for(int j = 0; j < 9; j++) {tmp.push_back(board[j][i]);}block.clear();for(int k = 0; k < 9; k++) {block.push_back(board[i/3*3 + k/3][i%3*3 + k%3]);}if(!hasOneNum(board[i]) || !hasOneNum(tmp) || !hasOneNum(block))    return false;}//blockreturn true;}bool hasOneNum(vector ls) {vector nums = vector(9,0);int tmp;for(int i = 0; i < 9; i++)printf("%c\t",ls[i]);printf("\n");for(int i = 0; i < 9; i++) {if(ls[i] - '.' == 0)    continue;tmp = ls[i] - '1';nums[tmp]++;if(nums[tmp] >= 2)    return false;}return true;}
   };
   int main() {vector> board;for(int i = 0; i < 9; i++) {board.push_back({'.','.','.','.','5','.','.','1','.'});board.push_back({'.','4','.','3','.','.','.','.','.'});board.push_back({'.','.','.','.','.','3','.','.','1'});board.push_back({'8','.','.','.','.','.','.','2','.'});board.push_back({'.','.','2','.','7','.','.','.','.'});board.push_back({'.','1','5','.','.','.','.','.','.'});board.push_back({'.','.','.','.','.','2','.','.','.'});board.push_back({'.','2','.','9','.','.','.','.','.'});board.push_back({'.','.','4','.','.','.','.','.','.'});}Solution sol;cout << sol.isValidSudoku(board);return 0;
   }
   

2、矩阵置零

1. 描述

   给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1：
   输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
   输出：[[1,0,1],[0,0,0],[1,0,1]]
   示例 2：
   输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
   输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示：
   m == matrix.length
   n == matrix[0].length
   1 <= m, n <= 200
   -231 <= matrix[i][j] <= 231 - 1进阶：
   一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
   一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
   你能想出一个仅使用常量空间的解决方案吗？
   

2. 思路

   获取所有0所在位置，行/列置零

3. 代码

   #include 
   using namespace std;
   #include class Solution {
   public:void setZeroes(vector>& matrix) {int m = matrix.size();int n = matrix[0].size();vector> index;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(matrix[i][j] == 0)index.push_back(pair(i,j));}}for(int i = 0; i < index.size(); i++) {printf("%d - %d\n",index[i].first,index[i].second);setZero(matrix,index[i].first,index[i].second);}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {printf("%d  ",matrix[i][j]);}printf("\n");}}void setZero(vector>& matrix,int row,int column) {matrix[row].assign(matrix[0].size(),0);for(int i = 0; i < matrix.size(); i++) {matrix[i][column] = 0;}}
   };
   int main() {vector> matrix;matrix.push_back({0,1,2,0});matrix.push_back({3,4,5,2});matrix.push_back({1,3,1,5});Solution sol;sol.setZeroes(matrix);return 0;
   }