2014
04-04

Sudoku

The puzzle game of Sudoku is played on a board of N^2 × N^2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N^2.

The Sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct positions; fill all empty cells so that the final position is still correct. (We call the final position is a solution to the starting position).

This problem is not about to solve a specific Sudoku puzzle, but ask you to find all correct positions that have a unique solution when N = 2.

There’s no input for this problem.

There’s no input for this problem.

HintThe Sudoku description is quoted from problem "Sudoku Checker", Northeastern Europe 2005

// File Name: hdu3746.cpp
// Author: bo_jwolf
// Created Time: 2013年05月04日 星期六 19:54:29

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>

using namespace std;
const int maxn = 100010 ;
char str[ maxn ] ;
int next[ maxn ] ;
void getnext( char *p )
{
int j  , k ;
j = 0 , k = -1 ;
int len = strlen( p ) ;
next[ 0 ] = -1 ;
while( j < len )
{
if( k == -1 || p[ j ] == p[ k ] )
{
j++ ;
k++ ;
next[ j ] = k ;
}
else
k = next[ k ] ;
}
}

int main()
{
int Case ;
scanf( "%d" , &Case ) ;
while( Case-- )
{
scanf( "%s" , str ) ;
getnext( str );
int len = strlen( str ) ;

if( next[ len ] == 0 )
{
printf( "%d\n" , len ) ;
continue ;
}
int t = len - next[ len ] ;
if( len % t == 0 )
printf( "0\n" );
else
printf( "%d\n" , t - len % t ) ;
}
return 0;
}

1. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

2. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

3. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

4. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

5. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

6. 小学五年级的时候=-=我们语文老师跑回家生孩子了，学校调来一个很老的老师教我们语文。然而我们惊讶的发现，他是我们一年级的体育老师=-=从此之后，我可以骄傲的所有人，我的语文是体育老师教的！！！！！！！！！！！！！！！

7. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

8. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

9. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。