请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
点击查看代码
class Solution {
public boolean isValidSudoku(char[][] board) {
//定义数字行内出现的次数
int[][] row = new int[9][9];
//定义数字列内出现的次数
int[][] column = new int[9][9];
//定义数字九宫格内出现的次数最大为9次
int[][][] jiugongge = new int[3][3][9];
//遍历数组
for (int i =0;i <9;i++){
for(int j = 0;j<9;j++){
char c = board[i][j];
//只要存在数字
if (c !='.'){
//把数字-1化成索引下标,c是字符串要减去字符串，-1会报错。
int index = c-'1';
//这个时候++意思是第i行这个c值次数+1，默认row第二位就是{1-9}-1；每一行都有可能是1-9
//例如现在是第一行第一列是9，就在row[1][8]号位置+1
row[i][index]++;
//列同理
column[j][index]++;
//并且九宫格内次数也要+1,例如也是第1行第一列，i/3 j/3会自动定位到所在的小宫格
jiugongge[i/3][j/3][index]++;
//次数大于1就不成立一个数独
if (row[i][index]>1||column[j][index]>1||jiugongge[i/3][j/3][index]>1) return false;
}
}
}
return true;
}
}点击查看代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rol[9][9];
int col[9][9];
int jiugongge[3][3][9];
memset(rol,0,sizeof(rol));
memset(col,0,sizeof(col));
memset(jiugongge,0,sizeof(jiugongge));
for (int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
char c=board[i][j];
if(c!='.')
{
int index=c-'1';
rol[i][index]++;
col[j][index]++;
jiugongge[i/3][j/3][index]++;
if(rol[i][index]>1||col[j][index]>1||jiugongge[i/3][j/3][index]>1)
return false;
}
}
}
return true;
}
};
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
点击查看代码
class Solution {
private:
//
bool line[9][9];
bool column[9][9];
bool block[3][3][9];
//
bool valid;
//空格
vector<pair<int, int>> spaces;
public:
void dfs(vector<vector<char>>& board, int pos) {
//结束
if (pos == spaces.size()) {
valid = true;
return;
}
//
auto [i, j] = spaces[pos];
for (int digit = 0; digit < 9 && !valid; ++digit) {
if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
board[i][j] = digit + '0' + 1;
dfs(board, pos + 1);
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
}
}
}
void solveSudoku(vector<vector<char>>& board) {
memset(line, false, sizeof(line));
memset(column, false, sizeof(column));
memset(block, false, sizeof(block));
valid = false;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.emplace_back(i, j);
}
else {
int digit = board[i][j] - '0' - 1;
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
}
}
}
dfs(board, 0);
}
};
点击查看代码
class Solution {
private:
int row[9][9];
int col[9][9];
int jiugongge[3][3][9];
bool valid;
vector<pair<int,int>>spaces;
public:
void bfs(vector<vector<char>>&board,int pos)
{
if(pos==spaces.size())
{
valid=true;
return;
}
auto[i,j]=spaces[pos];
for(int digit=0;digit<9&&!valid;++digit)
{
if(!row[i][digit]&&!col[j][digit]&&!jiugongge[i/3][j/3][digit])
{
row[i][digit]=col[j][digit]=jiugongge[i/3][j/3][digit]=true;
board[i][j]=digit+'1';
bfs(board,pos+1);
row[i][digit]=col[j][digit]=jiugongge[i/3][j/3][digit]=false;
}
}
}
void solveSudoku(vector<vector<char>>& board) {
memset(row,false,sizeof(row));
memset(col,false,sizeof(col));
memset(jiugongge,false,sizeof(jiugongge));
valid=false;
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)
{
if(board[i][j]=='.')
{
spaces.emplace_back(i,j);
}
else{
int digit=board[i][j]-'1';
row[i][digit]=col[j][digit]=jiugongge[i/3][j/3][digit]=true;
}
}
}
bfs(board,0);
}
};
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n/2;++i)
{
for(int j=0;j<(n+1)/2;++j)
{
int temp=matrix[i][j];
matrix[i][j]=matrix[n-j-1][i];
matrix[n-j-1][i]=matrix[n-i-1][n-j-1];
matrix[n-i-1][n-j-1]=matrix[j][n-i-1];
matrix[j][n-i-1]=temp;
}
}
}
};二进制求和，满二进一
首先让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引。
然后从后到前遍历所有的位数，同位相加，这里有一个点，用的是字符相加，利用 ASCII 码，字符在内部都用数字表示，我们不需要知道具体数值，但可知 ‘0’-‘0’ = 0， ‘0’+1=‘1’，以此类推 。字符的加减，大小比较，实际上都是内部数字的加减，大小比较
判断相加后的字符，若大于等于字符 ‘2’‘2’，下一位需要进一
第 00 位数的相加在这里是单独处理的，因为它可能涉及到字符的插入（即是否需要在最前面加一位数 ‘1’‘1’
点击查看代码
class Solution {
public:
string addBinary(string a, string b)
{
int asize = a.size(), bsize = b.size();
while (asize > bsize)//补齐
{
b = '0' + b;
bsize++;
}
while (asize < bsize)
{
a = '0' + a;
asize++;
}
int carry = 0; //进位
for (int i = asize - 1; i >= 0; i--)
{
int sum = a[i] - '0' + b[i] - '0' + carry;
a[i] = (sum) % 2+'0';//本位数值
carry = sum / 2;//进位更新
}
if (carry > 0)//有溢出
a = '1' + a;
return a;
}
};