【算法 C】Leetcode 36. Valid Sudoku 有效的数独
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法 C】Leetcode 36. Valid Sudoku 有效的数独，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5103字，纯文字阅读大概需要8分钟。
内容图文
其实算法并没有太难，无论是3次遍历还是1次遍历，都不会超时，我在做的时候，如何使用测试数据反而困扰了我很久。
读取测试数据
将测试数据放在文件中读取，这里将文件指针改为stdin应该也是一样的效果。
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int boardSize = 9;
int boardColSize = 9;
char** board = (char **) malloc(sizeof(char *) * boardSize);
// 打开文件
FILE *fp = fopen("sudoku1.txt", "r");
if (fp == NULL)
{
fprintf(stderr, "读取文件出错");
exit(-1);
}
// 输出文件内容
printf("文件内容为：\n");
int ch;
while ((ch = fgetc(fp)) != EOF)
{
putchar(ch);
}
printf("\n");
// 读取数组
rewind(fp);
for (int i = 0; i < boardSize; i++)
{
board[i] = (char *) malloc(sizeof(char) * boardSize); // 每行分配内存
for (int j = 0; j < boardColSize; j++)
{
while ((ch = fgetc(fp)) != EOF && ch != ‘\"‘);
board[i][j] = fgetc(fp);
fgetc(fp);
}
}
fclose(fp);
// 输出查看数组
printf("读取到数组为: \n");
for (int i = 0; i < boardSize; i++)
{
for (int j = 0; j < boardColSize; j++)
{
printf("%c ", board[i][j]);
}
printf("\n");
}
// solve
bool validate = isValidSudoku(board, boardSize, &boardColSize);
puts(validate ? "true": "false");
// 释放内存
for (int i = 0; i < boardSize; i++)
{
free(board[i]);
}
free((void *) board);
return 0;
}
3次遍历
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
bool isValidSudoku(char** board, int boardSize, int* boardColSize)
{
int nums[10] = {0};
int tmp;
// 检查行
for(int i = 0; i < boardSize; i++)
{
memset(nums, 0, sizeof(int) * 10);
for(int j = 0; j < *boardColSize; j++)
{
tmp = board[i][j];
if (tmp <= ‘9‘ && tmp > ‘0‘)
{
tmp = board[i][j] - ‘0‘;
nums[tmp] += 1;
if (nums[tmp] > 1)
{
// printf("false原因(行): [%d, %d]", i, j);
return false;
}
}
}
}
// 检查列
for(int j = 0; j < *boardColSize; j++)
{
memset(nums, 0, sizeof(int) * 10);
for(int i = 0; i < boardSize; i++)
{
tmp = board[i][j];
if (tmp <= ‘9‘ && tmp > ‘0‘)
{
tmp = board[i][j] - ‘0‘;
nums[tmp] += 1;
if (nums[tmp] > 1)
{
// printf("false原因(列): [%d, %d]", i, j);
return false;
}
}
}
}
// 检查九宫格
for (int i = 0; i < boardSize / 3; i++)
{
for (int j = 0; j < *boardColSize / 3; j++)
{
memset(nums, 0, sizeof(int) * 10);
for (int k = 0; k < 3; k++)
{
for (int l = 0; l < 3; l++)
{
tmp = board[i * 3 + k][j * 3 + l];
if (tmp <= ‘9‘ && tmp > ‘0‘)
{
tmp = tmp - ‘0‘;
nums[tmp] += 1;
if (nums[tmp] > 1)
{
// printf("false原因9: [%d, %d]", i * 3 + k, j * 3 + l);
return false;
}
}
}
}
}
}
return true;
}
int main()
{
int boardSize = 9;
int boardColSize = 9;
char** board = (char **) malloc(sizeof(char *) * boardSize);
// 打开文件
FILE *fp = fopen("sudoku1.txt", "r");
if (fp == NULL)
{
fprintf(stderr, "读取文件出错");
exit(-1);
}
// 输出文件内容
printf("文件内容为：\n");
int ch;
while ((ch = fgetc(fp)) != EOF)
{
putchar(ch);
}
printf("\n");
// 读取数组
rewind(fp);
for (int i = 0; i < boardSize; i++)
{
board[i] = (char *) malloc(sizeof(char) * boardSize); // 每行分配内存
for (int j = 0; j < boardColSize; j++)
{
while ((ch = fgetc(fp)) != EOF && ch != ‘\"‘);
board[i][j] = fgetc(fp);
fgetc(fp);
}
}
fclose(fp);
// 输出查看数组
printf("读取到数组为: \n");
for (int i = 0; i < boardSize; i++)
{
for (int j = 0; j < boardColSize; j++)
{
printf("%c ", board[i][j]);
}
printf("\n");
}
// solve
bool validate = isValidSudoku(board, boardSize, &boardColSize);
puts(validate ? "true": "false");
// 释放内存
for (int i = 0; i < boardSize; i++)
{
free(board[i]);
}
free((void *) board);
return 0;
}
一次遍历
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
bool isValidSudoku(char** board, int boardSize, int* boardColSize)
{
/* 一次遍历 */
int row[9][9] = {0};
int col[9][9] = {0};
int box[9][9] = {0};
int boxIndex;
int tmp;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
tmp = board[i][j];
if (tmp >=‘1‘ && tmp <= ‘9‘)
{
tmp -= ‘1‘;
boxIndex = (i / 3) * 3 + j / 3;
row[i][tmp] += 1;
col[j][tmp] += 1;
box[boxIndex][tmp] += 1;
if (row[i][tmp] > 1 || col[j][tmp] > 1 || box[boxIndex][tmp] > 1)
{
return false;
}
}
}
}
return true;
}
int main()
{
int boardSize = 9;
int boardColSize = 9;
char** board = (char **) malloc(sizeof(char *) * boardSize);
// 打开文件
FILE *fp = fopen("sudoku1.txt", "r");
if (fp == NULL)
{
fprintf(stderr, "读取文件出错");
exit(-1);
}
// 输出文件内容
printf("文件内容为：\n");
int ch;
while ((ch = fgetc(fp)) != EOF)
{
putchar(ch);
}
printf("\n");
// 读取数组
rewind(fp);
for (int i = 0; i < boardSize; i++)
{
board[i] = (char *) malloc(sizeof(char) * boardSize); // 每行分配内存
for (int j = 0; j < boardColSize; j++)
{
while ((ch = fgetc(fp)) != EOF && ch != ‘\"‘);
board[i][j] = fgetc(fp);
fgetc(fp);
}
}
fclose(fp);
// 输出查看数组
printf("读取到数组为: \n");
for (int i = 0; i < boardSize; i++)
{
for (int j = 0; j < boardColSize; j++)
{
printf("%c ", board[i][j]);
}
printf("\n");
}
// solve
bool validate = isValidSudoku(board, boardSize, &boardColSize);
puts(validate ? "true": "false");
// 释放内存
for (int i = 0; i < boardSize; i++)
{
free(board[i]);
}
free((void *) board);
return 0;
}
原文：https://www.cnblogs.com/XD00/p/13205482.html
内容总结
以上是互联网集市为您收集整理的【算法 C】Leetcode 36. Valid Sudoku 有效的数独全部内容，希望文章能够帮你解决【算法 C】Leetcode 36. Valid Sudoku 有效的数独所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】