本周题目难度'Medium'，所以还是用C来写，其实C和Python差不多，能用C写的，个人感觉用Python更好写，反正思路都是一样的，但C的效率真心比 Python快很多，所以'Medium'的还是用C来写
题目：给定一个数独，空白的用.来代替，让你来验证下是否合法，不需要求解。
思路：数独我还是很喜欢玩的，据说数独也有很多神奇的功效，但本宝宝只用它来打发时间而已，不懂数独的自行百度。关于数独的验证，无非也就三点。
- 每一个横排都是1-9的乱序排列。
- 每一个竖排都是1-9的乱序排列。
- 每个数独都有9个九宫格，每个九宫格都是1-9的乱序排列。
每点验证都差不多，只是范围有微小的变化，下面是代码，从isValidSudoku函数开始看：
//排序
void quickSort(char* nums,int first,int end){
int temp,l,r;
if(first>=end)return;
temp=nums[first];
l=first;r=end;
while(l<r){
while(l<r && nums[r]>=temp)r--;
if(l<r)nums[l]=nums[r];
while(l<r && nums[l]<=temp)l++;
if(l<r)nums[r]=nums[l];
}
nums[l]=temp;
quickSort(nums,first,l-1);
quickSort(nums,l+1,end);
}
//检查排序后的容器是否有重复的数字
bool checkArr(char *nums, int num) {
if (num > 1) {
quickSort(nums, 0, num-1);
for (int k = 0; k < num-1; k++) {
if (nums[k] == nums[k+1]) return 1;
}
return 0;
}else return 0;
}
//确定九宫格的九个数字
bool searchArr(char** board, int i0, int in, int j0, int jn) {
int num = 0;
char arr[9] = {'.', '.', '.', '.', '.', '.', '.', '.', '.'};
for (int i = i0; i < in; i++) {
for (int j = j0; j < jn; j++) {
if (board[i][j] != '.'){
arr[num] = board[i][j];
num++;
}
}
}
if (checkArr(arr, num)) return 1;
return 0;
}
//主函数，从这里开始看
bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
//先吐槽下参数，boardRowSize和boardColSize其实就没有必要给，因为两个一定都是9,出题人验证的数独全是规范的9*9的数独。
//定义一个容器，将思路中的1、2、3点分别放入容器中来验证（num是容器中的个数，arr为容器）
int num = 0;
char arr[9] = {'.', '.', '.', '.', '.', '.', '.', '.', '.'};
//判断第一点每行是否是1-9
for (int i = 0; i < boardRowSize; i++) {
num = 0;
for (int j = 0; j < boardColSize; j++) {
if (board[i][j] != '.'){
//将不为.的数放入容器中
arr[num] = board[i][j];
num++;
}
}
//检查是否有重复
if (checkArr(arr, num)) return 0;
}
//判断第二点每列是否是1-9（只是把行的i和j换了位置）
for (int j = 0; j < boardRowSize; j++) {
num = 0;
for (int i = 0; i < boardColSize; i++) {
if (board[i][j] != '.'){
arr[num] = board[i][j];
num++;
}
}
if (checkArr(arr, num)) return 0;
}
//判断第三点九宫格是否是1-9
int n = 0;
while (n <= boardRowSize - 3) {
int m = 0;
while (m <= boardColSize - 3) {
if (searchArr (board, n, n+3, m, m+3)) return 0;
m += 3;
}
n += 3;
}
//返回结果
return 1;
}
其实这道题C语言写起来蛮麻烦的，至少按我的思路是比较麻烦的，因为C中没有字典或者Set这样的容器，如果有这样可以去重的容器，直接比较容器内的个数和放入容器的个数即可知道是否有重复的，而C语言还要先排序，然后再找重复，当然，尽管实现的比较坎坷，依旧速度秒杀其他语言，效率中上。。。
