split tree(C++)

这个代码没测试过。 
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
    int data;
    list<Node *> nodes;
};
------------------------
思路：每个node记录左子树和右子树的node的个数。随便找种顺序遍历树，对每个node的子树，是偶数就砍掉，是奇数就留着。递归做被砍掉的树。

void findnumber(Node *root, map<Node *,int> &num){
  if(!root) {num[root] = 0; return;}
  num[root] = 1;
  list<Node *>::iterator it = root->nodes.begin();
 while( it++ != root->nodes.end() ){
   findnumber(it,num);
   num[root] += num[it];
 }
}

void dfscut(Node *root, map<Node *, int> num, vector<Node *> &res){
   list<Node *>::iterator it = root->nodes.begin();
   while( it != root->nodes.end() ){
      if(num[it] & 1 == 1) { it++;}
      else {
        dfscut(it, num, res);
        it = root->nodes.erase(it);
       num[root] -= num[it];
      }
  }

res.push_back(root);
}


vector<Node *> cutTree(Node *root){
  map<Node *, int> num;
  vector<Node *> res;
  findnumber(root, num);
  if(num[root] & 1 == 1) return NULL;
  dfscut(root, num, res);

return res;
}

find next node of a tree(C++)

写的啥啊看不懂。。重新写一个。。
------06/17/13 rewrite-----------
假设不是最大的节点 ，假设是BST
1, node has  a parent field.
node *nextNode(node *root,  int val){
    if(!root) return NULL;
   while(root && root->val != val){
       if(root->val > val) root = root->left;
       else root = root->right;
   }
   if(!root->right) return root->parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}

2, node doesn't have a parent field.

node *nextNode(node *root,  int val){
   if(!root) return NULL;
   node dummy(0);
   dummy.next = root;
   node *parent = &dummy;
   // find node with value = val
   while(root && root->val != val){
       parent = root;
       if(root->val > val) root = root->left;
       else root = root->right;
   } 
   // find next node
   if(!root->right) return parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}


------------------old post---------------------------
add a successor pointer for each node in a tree

findsuc(node *root){
  node *parent = NULL;
  node *first,last;
  inorder(root,  first, last);
}

void inorder(node *root,  node *first, node *last){
  if(!root->left) first = root;
  if(!root->right) last = root;
  if(root->left){
   inorder(root->left, first, last);
   last->successor = root;
  }
  if(root->right) {
   inorder(root->right,first,last);
   root->sucessor = first;
   last->successor = NULL;
  }
}
---------------
void solve(Node * r) {
    while (r && r->left) r=r->left;
    Helper(NULL, r);
}

// return the last node of inorder travsal
Node * Helper(Node * prev, Node * r) {
    if (!r) return NULL;
    Node * prev_in_left = Helper(prev, r->left);

    if (prev_in_left) prev = prev_in_left;
    if (prev) prev->successor = r;

    return r->right?Helper(r, r->right):r;
}

quadtree (C++)

问题1 : 为这个 quadtree里面的 node 设计 data structure

然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的 
image 是两个相同的 area
比如 都是 [0 1] x [0 1] 这个相同的二维区域的image.

问题二: 写一个函数，返回两个 quadtree的intersection,

这个intersection的规则是: 如果一个区域在 第一个quadtree 里面是
白的，这个相同的区域在 第二个 quadtree里面是黑的，那么intersection
就是白的，简单的说白是 0, 黑是 1, intersection就是两个bit 的 AND
-------------------
//color: 0 means white, 1 means black, 2 means mixed.
struct Qnode{
private:
  int color; 
  Qnode *children;
public:
  Qnode(int c){color = c;};
} 



Qnode *intersection(Qnode *first, Qnode *second){
   if(first == NULL && second == NULL)
 // if both nodes are mixed
  if(first->color == 2 && second->color == 2){
    Qnode *root = new Qnode(2);
    Qnode *newchildren = new Qnode[4];
    int count = 0;
    for(i = 0; i < 4; i++){
    newchildren[i] = intersection(first->children[i], second->children[i]); 
    if(newchildren[i]->color == 0) count++;  
    }
   if(count == 4){
     root->color = 0;
     delete[] newchildren;
   }  
 } 

//if at least one is while
else if(first->color == 0 || second->color == 0)  
  Qnode *root = new Qnode(0);
  root->children = NULL;
} 

//if one black one mixed or two blacks
else if(first->color == 1) Qnode *root =clone(second);
else (second->color == 1) Qnode *root = clone(first);

return root;
 }

Qnode *clone(Qnode *quad){
  if(quad == NULL) return Null;
  Qnode *root = new Qnode(quad->color);
  if(!quad->children) root->children == NULL; 
  else 
for(int i = 0; i < 4; i++){
 root->children[i] = clone(quad->children[i]);
}

return root;
}

Python for data analysis(study notes): chapter 2

Assume dataframe has rows 1,2,3...,n, columns A,B,C,...Z (so it has n records with 26 fields)
Example1:
a,  find 10 most common values in A
   pandas: value_counts()
b, find 10 most common values in A with sub-info of B
   numpy: where(B.str.contains('keyword'), 'keyword', 'no keyword')
   pandas: groupby, size(), unstack()
               .sum(1), aggsort(),take
 other funcs: dropna(), fillna(0),notnull()

Example2:
a, find A, mean of B group by A,C
  pandas: pivot_table(B,rows = A, cols = C, aggfunc = 'mean')
--------------to be continue---------------
 

Python: override hash key

list, dict等object不能直接当hashkey用，但是python里的tuple是可以的，如果要override自己定义的类，添加两个函数

__hash__(self),

__eq__(self, other)

即可。

例如：

class myclass:

  def __init__(self, str1,int2,var3):

     self.var1 = str1

     self.var2 = int2

     self.var3 = var3

  def __hash__(self):

     return hash((self.var1,self.var2))

  def __eq__(self,other):

     return (self.var1,self.var2) == (other.var1,other.var2)  

还有一种方法是用现成module: colletions.namedtuple()，这里就不写了。

参考来源：

http://stackoverflow.com/questions/4901815/object-as-a-dictionary-key

singleton double-checked locking pattern

为什么要用double check呢？因为当已经有instance存在，每次想新建instance时，我们就不需要先启用lock machnism,直接通过判定条件拒绝就行了。

class Singleton{

static Singleton *pInstance;

public:

static Singleton *instance();

 ...

}

Singleton* Singleton::instance() {

if(pInstance == 0) {

// 1st test

  Lock lock;

  if(pInstance == 0) {

  // 2nd test

    pInstance = new Singleton;

  }

}

return pInstance;

}

大数相乘string multiplication C

面试题给的是C string,那就写C吧。基本上就是模拟实际的乘法，因为数值很大存不了int,很自然要用string来存了。考虑进位的需要，结果应该是最多m+n位，再加上末位的'\0'字符，应该给结果分配m+n+1 byte的空间。此外还要考虑负数，不过我char array不熟，折腾了很久，就懒得再加这个case了。。
从写这个code，学到了char[]和char *的区别，最大的不同就是如果char *指向的是string literal, 内容不可更改，所以这里传入参数应该是由char[]定义的。

0. //assume that no negative integers are involved.  
1. //reverse a c string  
2. void reverse(char *c, int start, int end){  
3.     
4.   while(start < end){  
5.   
6.      char tmp = c[start];  
7.   
8.      c[start++] = c[end];  
9.   
10.      c[end--] = tmp;      
11.   
12.  }   
13. }  
14.   
15. char* MultiplyString(char *a,char *b){  
16.   
17.    int m = strlen(a), n = strlen(b);  
18.    //one extra position for carry, another one extra position for '\0'  
19.    char *c = new char[m+n+1];  
20.    memset(c, '0', m+n);  
21.    reverse(a,0,m-1);  
22.    reverse(b,0,n-1);  
23.    int carry;  
24.    //for each position in b, do the multiplication of b[i]*a,update corresponding positions in result c.  
25.    for(int i = 0; i < n; i++){  
26.   
27.      carry = 0;  
28.       
29.      for(int j = 0; j < m; j++){  
30.   
31.        int prod = (b[i] - '0')*(a[j] - '0') + carry + (c[i+j] - '0');  
32.    
33.        carry = prod/10;  
34.   
35.        c[i+j] = prod%10 + '0';  
36.      }  
37.    }  
38.    //deal with the highest position's carry  
39.    if(carry != 0) {   
40.       c[m+n-1] = '0' + carry;   
41.       reverse(c,0,m+n-1);  
42.     }  
43.   
44.    else {  
45.       c[m+n-1] = '\0';  
46.       reverse(c,0,m+n-2);  
47.    }  
48.   
49.    return c;   
50. }  

此外无意间发现一个有趣的swap方法，利用a^a ^b=b，可以不用额外tmp存中间值的：

swap(a,b):
  a = a^b
  b = b^a
  a = a^b

几个storage class keyword(C++)

auto, static, register and extern are  storage class specifiers, we can only use one of these four in a declaration.

Register: The variable is to be stored in a machine register, instead of memory (for example, instead of the stack) . This is useful if we want to use the variable very frequently. Practically, the compiler will do its own optimization and the keyword will probably have no effect.

Static: The variable will be in file scope, so it is accessible within the compilation unit (Compare:  a global variable can be accessed from any compilation with external linkage, and a local variable can be accessed only within block).

Extern:  when used with a string("C"/"C++"), extern specifies that the linkage conventions of another language are being used for the declarator(s). When modifying a variable, extern specifies that the variable has static duration.

Auto: The variable will be in local block-scope, since this is by default any way, auto is
basically not necessary to use. However, in  C++11, auto has new meaning:  the definition of a 

variable with an explicit initialization can use the auto keyword. 

Example: 

std::list<int> a; 

// fill in a 

for (auto it =a.begin(); it!= a.end(); ++it) { 

// Do stuff here 

} 

  

First non duplicate character in string C++

Find out the first non duplicate character in a string.
eg: "nasa" output: 'n' 
Require to scan the string only once.

思路：要求只能扫一遍string，既然时间严格限制，那只好多用空间了。一个map用来计数，一个double linkedlist用来存character candidates.最后总时间是O(n).
注：本代码未测试，懒得自己写double linked node的定义了。。

0. //assume that s is nonempty  
1. char firstnondup(string s){  
2.   
3.    unordered_map<char, ListNode*>  visited;  
4.   
5.    ListNode *tail = new ListNode(s[0]);  
6.   
7.    ListNode dummy(0);  
8.   
9.    dummy.next = tail;  
10.   
11.    tail->prev = dummy;  
12.   
13.    visited[s[0]] = tail;  
14.   
15.    for(int i = 1; i < s.length(); i++){  
16.    
17.       //if first occured  
18.       if(visited.find(s[i]) == visited.end()){  
19.   
20.         ListNode *cur = new ListNode(s[i]);  
21.   
22.         visited[s[i]] = cur;  
23.   
24.         tail->next = cur;  
25.   
26.         cur->prev = tail;  
27.   
28.         tail = cur;  
29.   
30.       }  
31.   
32.      else{  
33.   
34.        //if second occured, delete node  
35.        if(visited[s[i]] != NULL) {  
36.   
37.             ListNode *tmp = visited[s[i]]->prev;  
38.   
39.             tmp->next = visited[s[i]]->next;  
40.   
41.             visited[s[i]]->next->prev = tmp;  
42.   
43.             if(visited[s[i]] == tail) tail = tmp;  
44.   
45.             delete visited[s[i]];  
46.       }  
47.   
48.       //if more than secondly occured, just continue  
49.     }  
50.   }  
51.   
52. return dummy.next.val;  
53.   
54. }  
55.   
56.    

Remove space from string C++

Write a function that removes extra spaces from a string and leaves only one correct space.

0. void removespace(string &s){  
1.   
2.   int count = 0;   
3.   
4.   string buffer;  
5.   
6.   for(int i = 0; i < s.length(); i++){  
7.   
8.     if(s[i] != ' ') {  
9.   
10.          count = 0;  
11.   
12.          buffer.push_back(s[i]);  
13.     }  
14.     else{  
15.   
16.        if(count == 0) {  
17.   
18.           count++;  
19.   
20.           buffer.push_back(' ');  
21.        }  
22.    }  
23.   }   
24.  s = buffer;  
25. }   

Convert string to palindrome C++

Find minimum number of characters that need to be inserted into a string (anywhere in the string) to make it a palindrome
ex. abb->abba, dabbde->edabbade
思路：一道DP题，设A[i][j]表示把s从位置i到位置j变成palindrome,则有：如果两头相等s[i] = s[j]，那么A[i][j] = A[i+1][j-1]。如果两头不等，那么A[i][j] = min(A[i][j-1], A[i+1][j]) +1。
最后返回A[0][n-1]就行了。

0. int makepalindrome(string s){  
1.    if(s.empty()) return 0;  
2.    int n = s.length();  
3.   
4.    //define A[i][j] as the min number needed to make palindrome from pos i to pos j.  
5.    vector<vector<int> > A(n,vector<int>(n,n));  
6.   
7.    //initialize substr with 1 and 2 chars.  
8.    for(int i = 0; i < n; i++){  
9.   
10.      A[i][i] = 0;  
11.   
12.      if(i < n-1) {  
13.   
14.         if(s[i] == s[i+1]) A[i][i+1] = 0;  
15.   
16.         else A[i][i+1] =  1;  
17.      }    
18.    }  
19.   
20.    //calculate substr from i to j with more than 2 chars.  
21.    for(int j = 2; j < n; j++){  
22.   
23.       for(int i = j-2; i >= 0; i--){  
24.   
25.          if(s[i] == s[j]) A[i][j] = A[i+1][j-1];  
26.   
27.          else A[i][j] = min(A[i][j-1], A[i+1][j]) + 1;  
28.      }  
29.   }  
30.   
31.   return A[0][n-1];  
32. }     

Six digit number with equal sum C++

Write an algorithm to find the number of six digit numbers where the sum of the first three digits is equal to the sum of the last three digits.

思路：找总数太简单了，写个找所有满足条件的数的code吧。
3位数的数字之和最多27,0不用考虑，所以建一个size为27的bucket,遍历所有的三位数组合，按数字和分类放入bucket里面，这样要得到要求的6位数，只要前三位和后三位在同一个bucket就可以了。复杂度就是n^3+27*n^2~1000+2700~O(n^3), n=10. 这里用string来存每个整数，一个是节省空间，还有就是输出的code写起来方便，如果要把结果存入变量，只要append两个三位数的string就行了。

0. void findall(){  
1.   //set up an array, each element stores strings with sum = index of the element  
2.   vector<string> digit3[27];   
3.   
4.   string str;  
5.   //group 3-digit integers with equal sum into each array element  
6.   for(int i = 0; i < 10; i++){  
7.             
8.     for(int j = 0; j < 10; j++){  
9.   
10.        for(int k = 0; k < 10; k++){  
11.   
12.           int sum = i + j + k;  
13.   
14.           if(sum > 0) {  
15.             str.clear();  
16.             str.push_back(i+'0');   
17.             str.push_back(j+'0');  
18.             str.push_back(k+'0');   
19.   
20.             digit3[sum-1].push_back(str);  
21.          }  
22.       }    
23.     }  
24.   }  
25.   
26.  //print out all 6-digit numbers  
27.  for(int i = 0; i < 27; i++){  
28.    //len is the number of 3-digit integers with sum = i  
29.    int len = digit3[i].size();    
30.   
31.    for(int j =0; j < len; j++){  
32.              
33.       for(int k = 0; k < len; k++){  
34.   
35.            string str1 = digit3[i][j];  
36.   
37.            string str2 = digit3[i][k];  
38.             
39.            if(str1[0] != '0') cout<<str1<<str2<<endl;  
40.   
41.       }  
42.    }  
43. }  
44. }  

Maximum subsequence sum C++

Find the maximum subsequence sum of an array of integers which contains both positive and negative numbers and return the starting and ending indices within the array.

For example:

int array[] = {1, -2, -3, 4, 5, 7, -6}

The max subsquence sum is 4+5+7= 16 and start index is at 3 and end index is at 5.

思路：DP，用一个int maxsofar记录当前最大和，对每个元素记录包含此元素的最大和cursum，同时更新maxsofar,这样做一遍就行了。

0. //assume n>0  
1.   
2. int maxsubsum(int A[], int n){  
3.   
4.   int maxsofar = A[0], cursum = A[0];  
5.   
6.   for(int i = 1; i < n; i++){  
7.   
8.     cursum = A[i] + max(cursum, 0);  
9.   
10.     maxsofar = max(maxsofar, cursum);  
11.   
12.  }  
13.   
14.  return maxsofar;  
15.   
16. }  

Print linked list in reverse order C++

Print a linked list recursively in a reverse manner without changing the actual list

思路：可以用stack或者vector做buffer, stack的default implementation是deque,对于本题来说有些浪费，只要用array-based vector然后倒着读就行了。如果不让用额外空间，那只能O(n^2)递归了。

0. void printlist(ListNode *head){  
1.   
2.  vector<int> v;  
3.   
4.  while(head){  
5.   
6.       v.push_back(val);  
7.   
8.       head = head->next;  
9.   
10.  }  
11.   
12.  for(int i = v.size() - 1; i >=0; i--){  
13.   
14.   cout<<v[i]<<" ";  
15.   
16. }  
17. }   

递归：

0. void printlist(ListNode *head){  
1.   if(!head) return;  
2.   printlist(head->next);  
3.   cout<<" "<<head->val;  
4. }   

Move zeros to end C++

Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])

思路：用个index记录当前需要填充的位置，扫一遍就行了，跟quicksort思路一致。复杂度O(n)

0. void pushzeros(int A[], int n){  
1.   
2.   int index = 0;  
3.   
4.   for(int i = 0; i < n; i++){  
5.   
6.     if(A[i] != 0){  
7.          int tmp = A[index];  
8.   
9.          A[index++] = A[i];  
10.   
11.          A[i] = tmp;  
12.   
13.     }  
14.      
15.   }     
16.   
17. }   

Surrounded regions(C++ code)

Leetcode Surrounded Regions, Feb 22
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

思路：这道题的要求是边界相连的O不动，被围在里面的O变为X。这里有个trick，就是先把边界相连的O变为另一个符号#，然后遍历矩阵，把#变回O，同时把O变为X，就可以了。找所有的边界O需要用到dfs，只对所有边界元素遍历，这里的特殊之处在于遇到X或者#都直接返回，只有遇到O才加以处理并继续DFS，因此不需要另外使用map判定条件了。

0. #depth-first-search and change boundary O's to #'s.  
1. void dfs(vector<vector<char>> &board, int i, int j){  
2.   
3.   if(board[i][j] == 'X' || board[i][j] == '#') return;  
4.   
5.   board[i][j] = '#';   
6.   
7.   if(i > 0) dfs(board,i-1,j);  
8.   
9.   if(i < board.size()-1) dfs(board,i+1,j);  
10.   
11.   if(j > 0) dfs(board,i,j-1);  
12.   
13.   if(j < board[0].size() - 1) dfs(board,i,j+1);  
14.   
15. }   
16.   
17.    
18.   
19. void solve(vector<vector<char>> &board) {  
20.   
21.         if(board.empty()) return;  
22.  
23.         #r is row number, c is column numer  
24.         int r = board.size(), c = board[0].size();  
25.  
26.         #do dfs on the boundary lines  
27.         for(int i = 0; i < c; i++){  
28.   
29.           dfs(board,0,i);  
30.   
31.           dfs(board,r-1,i);   
32.   
33.         }   
34.   
35.         for(int j = 1; j < r-1; j++){  
36.   
37.           dfs(board,j,0);  
38.   
39.           dfs(board,j,c-1);   
40.   
41.         }   
42.        
43.         #change #'s back to O's, change O's to X's  
44.         for(int i = 0; i < r; i++){  
45.   
46.            for(int j = 0; j < c; j++){  
47.   
48.              if(board[i][j] == '#') board[i][j] = 'O';  
49.   
50.              else if(board[i][j] == 'O') board[i][j] = 'X';   
51.            }  
52.         }  
53. }  

Rotate list(C++ code)

LeetCode Rotate List, Mar 28 '12
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

思路：新头在倒数第k个，需要把新头前面的node指向null,把链表尾巴指向旧头。要处理k大于表长度的情况。

0. ListNode *rotateRight(ListNode *head, int k) {  
1.   
2.      if(!head) return NULL;  
3.      if(k == 0) return head;  
4.        
5.      ListNode *tail = head, *prev = head;  
6.   
7.      int i = k;  
8.   
9.      //find last k+1-th elem and last elem.  
10.   
11.      while(k>0 &&tail->next != NULL){  
12.   
13.          tail = tail->next;   
14.          k--;  
15.   
16.      }  
17.   
18.      //list length is i-k+1  
19.   
20.      if(tail->next == NULL) {  
21.   
22.         int listlen = i - k + 1;  
23.   
24.         k =listlen -  i%listlen-1;          
25.   
26.         while(k>0){prev = prev->next; k--;}  
27.   
28.     }  
29.   
30.      while(tail->next != NULL){  
31.   
32.           prev = prev->next;  
33.   
34.           tail = tail->next;  
35.   
36.      }  
37.   
38.      tail->next = head;  
39.   
40.      head = prev->next;  
41.   
42.      prev->next = NULL;  
43.   
44.      return head;           
45.       
46.  }  

Valid Palindrome (C++ code)

LeetCode Valid Palindrome ,Jan 13

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

思路：继续捏软柿子。。这题唯一要注意的是跳过非字母数字的字符的时候，别忘了同时满足边界条件。

0. bool isPalindrome(string s) {  
1.   
2.        if(s.empty()) return true;  
3.        int start = 0, end = s.length() - 1;  
4.        while(start < end){  
5.   
6.           if(!isalnum(s[start])) {start++; continue;}  
7.   
8.           if(!isalnum(s[end])) {end--; continue;}  
9.   
10.           if(abs(s[start] - s[end]) != 0 && abs(s[start] - s[end]) != 32)  
11.   
12.             return false;  
13.   
14.          else{  
15.   
16.             start++; end--;  
17.   
18.          }  
19.   
20.        }  
21.   
22.     return true;  
23.   
24. }   

Validate binary search tree(C++ code)

LeetCode Validate Binary Search Tree, Aug 31 '12
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

思路：这题简单，一次bug free。。。最近都在科普python,sql ，为了避免C++手生，决定每天练一道leetcode，恩，发现C还是很重要的，把C搞懂了，学其他的才会事半功倍~

0. #helper function  
1. bool isValidBST(TreeNode *root, int lower, int upper){  
2.   
3.  if (!root) return true;  
4.   
5.  if(root->val <= lower || root->val >= upper) return false;  
6.   
7.  bool left = isValidBST(root->left, lower, root->val);  
8.   
9.  bool right = isValidBST(root->right, root->val, upper);  
10.   
11.    
12.   
13.  return left && right;  
14.   
15. }  
16.   
17. bool isValidBST(TreeNode *root) {  
18.         isValidBST(root, INT_MIN, INT_MAX);  
19.          
20.     }   

Reverse Linked List II(C++)

LeetCode Reverse Linked List II, Jun 27 '121352 / 4252
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 <= m <= n <= length of list.
思路：也没什么特别的，就是要注意考虑边界情况。

0. ListNode *reverseBetween(ListNode *head, int m, int n) {  
1.     if(!head) return NULL;  
2.     if(m == n) return head;  
3.     ListNode dummy(0);  
4.     dummy.next = head;  
5.     ListNode *prev = &dummy;  
6.     ListNode *first = head;  
7.     #first's index will be from m to n-1  
8.     int k = 0;  
9.     while(k++ < m-1) prev = prev->next;  
10.     first = prev->next;  
11.     ListNode *front = first, *back = first->next;  
12.     for(k = 0; k < n - m; k++){  
13.        ListNode *temp = back->next;  
14.        back->next = front;  
15.        front = back;  
16.        back = temp;  
17.     }  
18.     prev->next = front;  
19.     first->next = back;  
20.       
21.     return dummy.next;  
22.       
23.       
24. }  

minimum depth of binary tree(c++ code)

LeetCode Minimum Depth of Binary Tree, Oct 10 '121893 / 4635

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
思路：递归

1. int minDepth(TreeNode *root) {  
2.        if(!root) return 0;  
3.        if(!root->left && !root->right) return 1;  
4.        int leftmin = INT_MAX, rightmin = INT_MAX;  
5.        if(root->left){  
6.           leftmin = minDepth(root->left);  
7.        }  
8.        if(root->right){  
9.            rightmin = minDepth(root->right);  
10.        }  
11.        return min(leftmin, rightmin) + 1;  
12.          
13.    }  

sort colors(c++)

Leetcode Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0′s, 1′s, and 2′s, then overwrite array with total number of 0′s, then 1′s and followed by 2′s.
Could you come up with an one-pass algorithm using only constant space?
思路：就是quicksort的思路了。

1.   void swap(int &i, int &j){  
2.    int temp = i;  
3.    i = j;  
4.    j = temp;  
5. }  
6.   
7. void sortColors(int A[], int n) {  
8.   int rindex = 0,bindex = n-1;  
9.   int i = 0;  
10.   while(i <= bindex){  
11.     if(A[i] == 0) {  
12.       swap(A[i],A[rindex]);rindex++;  
13.     }  
14.     if(A[i] == 2) {  
15.       swap(A[i],A[bindex]); bindex--;  
16.     }  
17.     else i++;  
18.   }   
19. }  

merge sorted array(C++ code)

leetcode Merge Sorted ArrayMay 20 '12
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

0. void merge(int A[], int m, int B[], int n) {  
1.   
2.        if(n == 0) return;  
3.   
4.        int i = m+n-1;  
5.   
6.       while(m > 0 && n > 0){  
7.   
8.            if(A[m-1] > B[n-1]) {A[i--] = A[m-- -1]; }  
9.   
10.            else{  
11.   
12.               A[i--] = B[n-- -1];   
13.   
14.            }  
15.   
16.       }   
17.   
18.      while(m > 0) {A[i--] = A[m-- -1]; }      
19.   
20.      while(n > 0) {A[i--] = B[n-- -1]; }   
21.   
22.        }  

encode string C++

给一个string, 让把里面连续的超过3个的相同char替换成char#个数。少于3个的不变。
比如：AAABCCDDDDEEF
变成：A#3BCCD#4EEF
---------
挺简单的。。

0. string encode(string &input){  
1.   string output;  
2.   if(input.empty()) return output;  
3.   int count = 1;  
4.   int i;  
5.   for(i = 0; i < input.length() - 1; i++){  
6.     if(input[i] != input[i+1]){  
7.           if(count < 3){  
8.               while(count-- > 0)  
9.               output.push_back(input[i]);               
10.          }  
11.          else{  
12.              output.push_back(input[i]);  
13.              output.push_back('#');  
14.              output.push_back(to_string(count));  
15.          }  
16.         count = 1;  
17.     }  
18.   else count++;  
19.  }  
20.   
21. output.push_back(input[i]);  
22. if(count > 1){  
23.   output.push_back('#');  
24.   output.push_back(to_string(count));  
25. }  
26. if(count == 2) output.push_back(input[i]);  
27.   
28. return output;  
29. }  

git新手指南

在网上搜来搜去，最后发现还是下面这个最有用，简洁明了，对于新手来说零失败（总结翻译见后）：
https://help.github.com/articles/set-up-git

这个git virtual reference 也很棒：
http://marklodato.github.io/visual-git-guide/index-en.html


然后就是入门宝典：http://git-scm.com/book/en/Git-Basics-Getting-a-Git-Repository

常用命令：
http://gitref.org/creating/

read bookmark:

http://git-scm.com/book/en/Git-Basics-Recording-Changes-to-the-Repository 

-----------------新手指南--------------------

第一步： 下载并安装git

第二步： 打开git bash, 设置用户名和电子邮件地址，命令如下:

$git config --global user.name "yumei165"

$git config --global user.email "yumei165@example.com" 

注： 如果不同的项目想使用不同的用户信息，比如有一个项目personal_repo，先设置工作目录到personal_repo,

然后重新设置（注意这里不使用global关键字）

$cd personal_repo path
$git config user.name "other name"
$git config user.email "differentemail@email.com" 

第三步： 新建自己的项目

 1， 在本地电脑新建项目(不用下面的命令直接操作也可以)：

 $mkdir Hello-World
 $cd Hello-World 

 2, 变为GIT项目，新建一个文档README

 $git init
 $touch README 

 3, 把本地项目和github链接起来

  3i, 在github网站上登入账户，新建项目

  3ii, 在本地bash输入以下命令，这样本地git项目对应到github中的Hello-world项目，并取名为origin

      （也可以是别的名字，origin是默认名）

  $git remote add origin https://github.com/username/Hello-World.git 

 4, 把本地项目内容存到github上对应项目中，三部曲： stage-commit-push

  $git add README anotherFile

  $git commit -m 'my first commit'

  $git push origin master

  --------other useful commands-------

  $git status -s (s for short)

  $git add . (files in current and all sub-directories)

  $git add * (files in current directory) 

 注： master是origin的主干默认名，如果需要可以建立分支，并在分支中存储本地项目的修改内容  

 5, 在分支中工作

 $git branch mybranch
 $git checkout mybranch 

 或者

 $git checkout -b mybranch

 #switch between branches

 $git checkout master 

 合并分支到master并删掉分支：
 $git checkout master
 $git merge mybranch 

 $git branch -d mybranch

第四步： 在别人的项目上工作

 1， 在目标项目上点击fork，之后项目就会被复制到自己的github目录中

 2, 现在从自己的github里把项目复制到本地电脑中：

 $git clone https://github.com/myUserName/Spoon-Knife.git 

 3, clone来的本地项目和自己github上fork来的项目是通过origin对应链接的，如果想和别人的源项目接，

    用如下命令，这样源项目的命名为upstream，最后一行命令用来同步更新

 
 $cd Spoon-Knife
 $git remote add upstream https://github.com/originalUserName/Spoon-Knife.git

 4， 本地项目和origin之间的联系和第三步相同。如果需要和源项目upstream联系，用如下命令：

  4i, 同步更新

  $git fetch upstream
  $git merge upstream/master

  or

  $ git pull upstream

  注：如果正在修改某个文件，为了避免冲突应该选择第一种方法 

  4ii, 把自己的更新送到源项目upstream:

    pull request

    基本都在网上完成，这里就不写了

第五步： 删除项目

  github repository->settings->Delete this repository

------------------------------------------

常用命令：

ls -a: all files including hidden