25 horses problem

http://www.youtube.com/watch?v=oaePKvHhUEA

把BT 同一层的sibling 连起来，constant 内存

struct Node {
    int value;
    Node *left;
    Node *right;
    Node *sibling; 
};


//把BT 同一层的sibling 连起来，constant 内存.
//
//                  1  -->null
//               /     \
//              2   -->  3  -->null
//            /       /    \
//          7     --> 8   -> 4  -->null
//
//
//开始没要求constant, 用queue记录每层的结点 O(n)即可. 后来要求constant，在提示下才搞定。
//先让不知道答案的xdjm想想吧。回头贴我的做法。
void connect_sibling( Node *root ) {
    root->sibling = null;
    Node *cur, *dummy;
    dummy = new Node;

    while( root ) {  //dummy->slibling是指向上次下一层的最左节点。
        cur = dummy;  //这样保证dummy->slibling总指向最左节点
        while( root ) {   // 找上一层的最右边节点， 假设当前层sibling已连好。

            if( root->left ) {
                cur->sibling = root->left;
                cur = root->left;
            }

            if(root->right){
                cur->sibling = root->right;
                cur = root->right;
            }

            root = root->sibling; //上一层的下一个姐妹，直到最右边。
        } //end of while second loop
        //此时，下一层已串好。

        cur->sibling = null; //最右边下一层填空。
        root = dummy->sibling; //上层的右一个节点。
    }
    delete dummy;
}

TopCoder Tutorial

http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static

String permutation

// Stringpermutation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include 
#include 
#include 
using namespace std;


void swap(char* a, char* b) 
{
 if (*a == *b ) return;

 char temp;
 temp = *a;
 *a = *b;
 *b = temp;
}

void permutate( char* Str, int index )
{
    int i = 0;
    if( index == strlen(Str)-1 )
    { 
       // We get a permutation, print it
        printf("%s \n",Str);
        return;
    }

 permutate(Str, index+1);

    for( i = index+1; i < strlen(Str); i++ )
    {

        int j;
        for( j = index;j < i;j++ )
            if( Str[j] == Str[i] )
                     break;
        if(j==i) 
        {
          swap( Str+index, Str+i ); 
          permutate( Str, index + 1 );
          swap( Str+index, Str+i );
        };

    }
}


int _tmain(int argc, _TCHAR* argv[])
{
 char str[] = "Abc";
 permutate( str, 0 );
 system("pause");

 char str2[] = "aabc";
 permutate( str2, 0 );
 system("pause");

 
 char str3[] = "acadc";
 permutate( str3, 0 );
 system("pause");

 return 0;
}

First nonrepeated character in a string

//First nonrepeated character in a string
char first_unique_char_in_string(const string a)
{
  //suppose string is composed of alphabets only ( a~z).
    unsigned char count[26];
    for(int i=0; i<26; i++) count[i] = 0; //initialize
    for(int i=0; i        count[a[i]-'a']++;
    for(int i=0; i        if(count[a[i]-'a']==1)
            return a[i];

    return -1; //no unique char.

}

Movie tickets problem

/* You have two movie tickets and want to invite a friend to watch movie
together. You can invite several friends simultaneously. Each one of them
independently has probability p to accept your invitation. How many friends
should you invite to maximize the probability that exactly one friend
accepts your invitation?*/

Suppose we invite n persons.

P=n*(1-p)^(n-1)*p   //independently, sum

f(n)=ln(P)=ln(n)+(n-1)ln(1-p)+ln(p)   //log

df/dn=1/n + ln(1-p) = 0   //derivative to get local max,

n = -1/ln(1-p) = 1/p;  when x-->0,  -ln(1-x) = x+x^2/2 + x^3/3 + ...

function to reverse digits of an integer

//Write a function to reverse digits of an integer. E.g. 456 --> 654, -7800 --> -87.
int ReverseDigits (int n){
    int ret = 0;
    while (n){
        ret = ret * 10 + n % 10;  //mod 10.
        n /= 10;  //div
    }
    return ret;
}

Efficiently remove duplicate white space from a string

//输入一个字符串，把连续的空格合并成一个。
void remove_duplicate_space(char *p)
{
    char *r=p, *w=p; //r: read, w: write
    while (*r != '\0') {
      if (*r!=' ' || *(w-1) != ' ')
      { *w = *r; w++; r++;}
      else
        r++;
    }
    if (r!=w) *w = '\0';
}

Flood Fill

//http://www.mitbbs.com/article_t1/JobHunting/31909771_0_5.html
//白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序
//列），上坡时：如果
//有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
//知道过完为止。
int water(int * a, int n){
  stack > mystack;
  int water = 0;
  for(int i = 0; i    while(!mystack.empty() && mystack.top().second <= a[i]){ //上坡
      int bottom = mystack.top().second; //底
      mystack.pop();
      if( mystack.empty())  //堆栈中只有一个元素，不能形成底。
        break;
      int top = mystack.top().second < a[i]?  mystack.top().second:  a[i];  //找到顶（次大数）

      int length = i - mystack.top().first - 1;  //长度
      water = water + (top-bottom)* length;  //填充
    }  //当前上坡处理完。
    mystack.push(make_pair(i, a[i]));  //下坡，进堆栈。

    //上坡无底的话，是什么都不做的，因为上次进堆栈的元素直接出堆栈了，只是查了一下底（至少两元素在堆栈）。
  }
  return water;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int value[10] = {5,5,1,7,1,1,5,2,7,6};


    int result=0;

    cout << result;

    result = water(value, 10);
    cout << result;

    return 0;
}

lambda function in C++0x

Lambda function in C++0x

1. Simplify code. good for simple predicate (i.e. a condition check);
[](//input parameters){ //lambda function body}

2. Anonymous call, function to be defined at the point it is needed.

3. Lambda function can only use global variable and passed parameters, just as a math function, i.e.
sin, cos, pow etc.

4. No local variable in the containing scope, special capture operation has to be defined, if you want to
use the local variables, i.e. [=] by value, [&] by reference.

C++ const: why and how-- a really messy feature

I was even asked during a job interview, const keyword can be put in 5 places, make it 5 meanings, pls refer to: http://duramecho.com/ComputerInformation/WhyHowCppConst.html