2014
11-18

LeetCode-Valid Sudoku[数组]

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

// LeetCode, Valid Sudoku
// 时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
bool isValidSudoku(const vector<vector<char>>& board) {
bool used[9];

for (int i = 0; i < 9; ++i) {
fill(used, used + 9, false);

for (int j = 0; j < 9; ++j) // 检查行
if (!check(board[i][j], used))
return false;

fill(used, used + 9, false);

for (int j = 0; j < 9; ++j) // 检查列
if (!check(board[j][i], used))
return false;
}

for (int r = 0; r < 3; ++r) // 检查 9 个子格子
for (int c = 0; c < 3; ++c) {
fill(used, used + 9, false);

for (int i = r * 3; i < r * 3 + 3; ++i)
for (int j = c * 3; j < c * 3 + 3; ++j)
if (!check(board[i][j], used))
return false;
}

return true;
}

bool check(char ch, bool used[9]) {
if (ch == '.') return true;

if (used[ch - '1']) return false;

return used[ch - '1'] = true;
}
};


1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢