矩阵

请你判断一个 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;
	}
};
上一篇:用Python判断密码强度,返回bool值。大写1 小写1 数字3 其他字符3,总长12。


下一篇:欧拉习题40