woxujiazhe
BAN USER// if there must be one island and it must be surrounded by 1
boolean map[][];
int directions[4][2] = {
{ 0, 1},
{ 0,-1},
{ 1, 0},
{-1, 0},
};
bool isBoundaryPosition(int i, int j)
{
if( i == 0 || j == 0 || i == n-1 || j == m-1 )
return true;
return false;
}
pair<int, int> go(pair<int, int> p, int direction[]){
return make_pair<int, int> (p.first+direction[0], p.second+direction[1] );
}
bool breath_search_surround_island(int i, int j)
{
queue< pair<int,int> > que;
map[i][j] = 1;
if ( isBoundaryPosition(i,j) ){
return false;
}
que.push( make_pair<int,int>(i,j) );
while( !que.empty() ){
pair<int, int> p = que.pop();
for(size_t di = 0; di<4; di++){
var pgo = go(p, directions[di]);
if( map[pgo.first][pgo.second] )
continue;
if( isBoundaryPosition(pgo) )
return false;
map[pgo.first][pgo.second] = true;
que.push( pgo );
}
}
return true;
}
is0surrounded = true; //whether is all 0 surrounded by 1
zero_island_count = 0; //how many islands; if not all 0 is surrounded, this number is not accurate.
for(size_t i = 0; i<n && !is0surrounded; i++){
for(size_t j = 0; j<m && !is0surrounded; j++){
if(map[i][j] == 0){
if( breath_search_surround_island(i, j) )
zero_island_count++;
else
is0surrounded = false;
}
}
}
if( is0surrounded && zero_island_count==0)// there is no islands
is0surrounded = false;
trap problem
// if we don't care how many island in the matrix
// if there's no 0 on the matrix's border, it would be OK
is0surrounded = true;
for(size_t i = 0;i<n;i++){
if( map[i][0] || map[i][m-1] ){
is0surrounded = true;
break;
}
}
for(size_t j = 0;j<m;j++){
if(map[0][j] || map[n-1][j]){
is0surrounded = true;
break;
}
}
class TNode
{
public:
enum type;// text node , tag node<>, another tag node</tag> or special tag node <br />
string content;
string originalString;
};
// <html> <body> <div> <span> TEXT1 </span> <br/> </div> </body> </html>
//parse the string, and push every node in domtree
stack<TNode> domtree;
/* you could use another stack algorithm to verify the tree
stack<TNode> domtree2;
foreach(var node in domtree){
if(node.type == NodeType.tag){
domtree2.push(node);
}
else if(node.type == NodeType.atag){
TNode pair_node = domtree2.pop();
if( pair_node.content == node.content )
; // verify failed
}
}
*/
class TreeNode{
public:
TreeNode* parent;
enum type;
string content; //tagName or text
vector<TreeNode*> children;
};
typedof TreeNode *PTreeNode;
PTreeNode rootp = new TreeNode();
PTreeNode cursor = rootp;
while( !domtree.empty() )
{
TNode cur = domtree.pop();
if( cur.type == NodeType.atag ){
// create node, append it to cursor node's children, move the cursor to that node
PTreeNode newNode = new TreeNode();
cursor->children.push(newNode);
cursor = cursor->children[ cursor->children.size()-1 ];
}
else if( cur.type == NodeType.tag ){
cursor->children.reverse();
cursor = cursor->parent;
assert( cur.content == cursor->content );//don't need it if after verified
}
else{
//create text node append text;
PTreeNode newNode = new TreeNode();
cursor->children.push(newNode);
}
}
PTreeNode tree_root = rootp->children[0];
kidding code boy
- woxujiazhe November 29, 2013static int Pre = INT_MIN;
bool IsValidBST(root)
{
Pre = INT_MIN;
return IsValidBST(root)
}
bool Verify(TreeNode* root)
{
if( !root ) return true;
if( !Verify(root->left) ) return false;
if( root->data < Pre ) return false;
Pre = root->data;
if( !Verify(root->left) ) return false;
return true;
}
- woxujiazhe November 29, 2013you can think like this.
the faster step is x. and the slower is y. when the come into the loop. their distance is d(y ahead x, it's a circle).
so if we want they meet, we should make this formula stands.
(a(x-y))%n = d
am%n = d
0 < d < n; a is a variable.
so how can it always stands?
m and n is must be relatively prime.
1 will be always relatively-prime with any positive number. so (x=2,y=1) would be a not bad choice
- woxujiazhe January 06, 2015