118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
AC代码
#include<bits/stdc++.h> using namespace std; //暴力法 //如果是第一列/i==j则 值为0 ,否则就是上一行该列和前一列的数之和. vector<vector<int>> generate(int numRows) { //定义ans并初始化. vector<vector<int>> ans(numRows); for(int i = 0;i < numRows;i++){ vector<int> V(i+1); ans[i] = V; for(int j = 0;j<=i;j++){ if(j==0||i==j){ ans[i][j] = 1; }else{ ans[i][j] = ans[i-1][j-1]+ans[i-1][j]; } } } return ans; } int main() { int numRows = 30; vector<vector<int>> ans = generate(numRows); for(int i = 0;i < ans.size();i++){ for(int j = 0;j < ans[i].size();j++){ cout<<ans[i][j]<<" "; } cout<<endl; } return 0; }
36. 有效的数独
请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 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 存在, 因此这个数独是无效的。
思路分析:
由于board中的整数限定在1到9的范围内，因此可以分别建立哈希表来存储任一个数在相应维度上是否出现过。维度有3个：所在的行，所在的列，所在的box，注意box的下标也是从左往右、从上往下的。
遍历到每个数的时候，例如boar[i][j]，我们判断其是否满足三个条件：
在第 i 个行中是否出现过
在第 j 个列中是否出现过
在第 j/3 + (i/3)*3个box中是否出现过.
关于从数组下标到box序号的变换
重述一遍问题：给定i和j，如何判定board[i][j]在第几个box呢？
显然属于第几个box由i和j的组合唯一确定，例如board[2][2]一定是第0个box，board[4][7]一定是第5个box，可以画出来看一下，但是规律在哪里呢？
我们可以考虑一种简单的情况： 一个3x9的矩阵，被分成3个3x3的box，如图：
显然每个数属于哪个box就只取决于纵坐标，纵坐标为0/1/2的都属于box[0],纵坐标为3/4/5的都属于box[1],纵坐标为6/7/8的都属于box[2].也就是j/3.
而对于9x9的矩阵，我们光根据j/3得到0/1/2还是不够的，可能加上一个3的倍数，例如加0x3,表示本行的box，加1x3，表示在下一行的box，加2x3，表示在下两行的box， 这里的0/1/2怎么来的？和j/3差不多同理，也就是i/3。
AC代码
#include<bits/stdc++.h> using namespace std; bool isValidSudoku(vector<vector<char>>& board) { int row[9][10] = {0};//行 int col[9][10] = {0};//列 int box[9][10] = {0};//盒子 for(int i = 0; i <9; i++) { for(int j = 0; j<9; j++) { if(board[i][j]=='.') { continue; } //判断行是否重复 int temp = board[i][j] - '0'; if(row[i][temp]) { return false; } row[i][temp] = 1; if(col[j][temp]) { return false; } col[j][temp] = 1; if(box[(i/3)*3+j/3][temp]) { return false; } box[(i/3)*3+j/3][temp] = 1; } } return true; } int main() { vector<vector<char>> 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'}}; cout<<isValidSudoku(board)<<endl; return 0; }
