Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

class Solution {
public:
    void pushLefts(stack<TreeNode*>& s, TreeNode* root)
    {
        while(root != NULL)
        {
            s.push(root);
            root = root->left;
        }
    }
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> tmp;
        pushLefts(tmp, root);
        while (!tmp.empty())
        {
            TreeNode* cur = tmp.top();
            tmp.pop();
            if (k == 1)
            {
                return cur->val;
            }
            pushLefts(tmp, cur->right);
            k--;
        }
        return -1;
    }
};

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Runtime: 36 ms

int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> tmp;
        int maxN = 0;
        for (int i = 0; i != nums.size(); ++i)
        {
            int t = nums[i];
            if (tmp.find(t) != tmp.end())
            {
                continue;
            }
            else
            {
                tmp[t] = t;
                maxN = max(maxN, 1);
            }
            if (tmp.find(t - 1) != tmp.end() && tmp[t-1] < t)
            {
                maxN = max(maxN, t - tmp[t-1] + 1);
                tmp[t] = tmp[t - 1];
                tmp[tmp[t-1]] = t;
            }
            if (tmp.find(t + 1) != tmp.end() && tmp[t+1] > t)
            {
                maxN = max(maxN, tmp[t+1] - tmp[t] + 1);
                int lowerBound = tmp[t];
                tmp[lowerBound] = tmp[t+1];
                tmp[tmp[t+1]] = lowerBound;
            }
        }
        return maxN;
    }

【effective c++】Design and Declarations I

看一遍忘一遍，觉得还是写点NOTES比较好。就从第四章开始吧。

Item 1: make interfaces easy to use correctly and hard to use incorrectly.

1, creating new types

(*Bad Practise*)
class Date {
public:
  Date(int month, int day, int year);
  ...
};

(*Good practise*)
class Date {
public:
  Date(const Month& month, const Day& day, const Year& year);
  ...
};

2, restrict operations on types, contrain object values

(*Bad Practise*)
struct Month {
  explicit Month(int m):val(m){}
  int m;
};

(*Good practise*)
(*This implementation is better than using enum which is not type safe*)
class Month {
public:
  static Month Jan() {return Month(1);}
  static Month Feb() {return Month(2);}
  ...
private:
  explicit Month(int m):val(m){}
  int m;
};

3, eliminating client resource management responsibility

(*Bad Practise*)
Investment* createInvestment();

(*Good practise*)
(*This implementation is better than using enum which is not type safe*)
std::tr1::shared_ptr createInvestment();
  
};

两个我喜欢的bash设置

1, ls color 不同颜色显示不同类别（文件，文件夹，可执行文件。。）
step1: put below codes in ls_color.sh
#!/bin/bash
# colored ls function

echo -e "$(ls -CF $@ | nawk '{
         gsub(/[A-Za-z0-9\-\._]+\//, "\\e[1;34m&\\e[0m\b/", $0);
         gsub(/[A-Za-z0-9\-\._]+@/, "\\e[1;36m&\\e[0m\b@", $0);
         gsub(/[A-Za-z0-9\-\._]+\*/, "\\e[1;31m&\\e[0m\b*", $0);
         print $0 }')"
step2: make alias in .bashrc
alias ls='$HOME/bin/ls_color.sh'
2，smiley face for prompt，如果任务非正常结束，会显示:(
function prompt {
   PS1='\[\e[0;36m\]\u@\h $(smiley) \[\e[0;36m\]\w\[\e[0m\]\n\$ '
   smiley ()
   {
       if [ $? = 0 ]; then
            echo -e '\e[32m:)\e[0m';
            true;
             else
                  echo -e '\e[31m:(\e[0m';
                  return $?;
                   fi
                    }
   export PS1
}

prompt

分享一下我的gvim

整理一下我的gvim,现在我有a.vim, acp.vim, fuzzyfinder.vim,tagbar.vim, 等有空，是转EMACS呢，还是继续研究各种gvim tips呢，that's a question..
==================
" This configuration file was tested with
" /usr/local/bin/vim (7.0)
" /usr/local/bin/gvim (7.0)
"this line prevents copydotfiles from recopying: dot-vimrc_included
syntax on

"set for auto loading cpp.vim
filetype plugin indent on
set hidden
set switchbuf=usetab,newtab

set term=dtterm
set ru
set et
"set bs=indent,eol,start
set sw=4  "this is the level of autoindent, adjust to taste                
set cin
"set foldmethod=indent

" Only use 256 colors on Linux machines.
" torte is better in 256 colors or gui.
" darkblue is better in 8 colors
if match($TERM, "xterm-256color") == 0
    set t_Co=256
    colorscheme torte
else
    colorscheme darkblue
endif

" GUI options
if has("gui_running")
   colorscheme desert
   set gfn=Monospace\ 16
   set lines=40 columns=83
endif

"highlight after 80 columns
highlight OverLength ctermbg=red ctermfg=white guibg=#592929
match OverLength /\%80v.\+/

 " automatically rebalance windows on vim resize
autocmd VimResized * :wincmd =

 
" Behavior for backspace
set backspace=indent,eol,start

" Highlight search
set hlsearch

"increament search
set incsearch

"case smart search
set ignorecase
set smartcase

" CTRL-V is Paste
"map <C-V>    "+gP
"imap <C-V>    <C-R>+
"cmap <C-V>    <C-R>+

set directory=/bb/data/tmp
set ic
set ai
set number
set showmode
set autoindent
set noignorecase

set tag=/path/tags

cmap fb<Space> FuzzyFinderBuffer<CR>
cmap fd<Space> FuzzyFinderDir<CR>
cmap fr<Space> FuzzyFinderMruFile<CR>
cmap ff<Space> FuzzyFinderFile<CR>

" These are so that we do not have to use middle click
set clipboard=unnamed
vnoremap y "+y

"Tab Complete Commands
set wildmode=longest,list,full
set wildmenu

""set for ocaml
au BufRead,BufNewFile *.mf set filetype=ocaml
au BufRead,BufNewFile *.mfi set filetype=ocaml
au BufRead,BufNewFile *.mf set sw=2 et
au BufRead,BufNewFile *.mfi set sw=2 et
au BufRead,BufNewFile *.ml set sw=2 et
au BufRead,BufNewFile *.mli set sw=2 et
"
let g:ctrlp_map = '<c-p>'
"
"
function! Compile()
  if &filetype == 'ocaml'
    !/opt/swt/bin/ocamlbuild '%:t'
  else
    !/compilecmd '%:t:r'
  endif
endfunction

map <C-c> : call Compile()

"" Omnicomplete stuff
filetype plugin on
set omnifunc=syntaxcomplete#Complete
au BufNewFile,BufRead,BufEnter *.cpp,*.hpp set omnifunc=omni#cpp#complete#Main
" OmniCppComplete
let OmniCpp_NamespaceSearch = 1
let OmniCpp_GlobalScopeSearch = 1
let OmniCpp_ShowAccess = 1
let OmniCpp_ShowPrototypeInAbbr = 1 " show function parameters
let OmniCpp_MayCompleteDot = 1 " autocomplete after .
let OmniCpp_MayCompleteArrow = 1 " autocomplete after ->
let OmniCpp_MayCompleteScope = 1 " autocomplete after ::
let OmniCpp_DefaultNamespaces = ["std", "_GLIBCXX_STD"]
" automatically open and close the popup menu / preview window
au CursorMovedI,InsertLeave * if pumvisible() == 0|silent! pclose|endif
set completeopt=menuone,menu,longest,preview

set completeopt=longest,menuone
:inoremap <expr> <CR> pumvisible() ? "\<C-y>" : "\<C-g>u\<CR>"

"
function! InsertTabWrapper()
    let col = col('.') - 1
    if !col || getline('.')[col - 1] !~ '\k'
        return "\<tab>"
    else
        return "\<c-p>"
    endif
endfunction

inoremap <C-Space> <c-r>=InsertTabWrapper()<cr>

"autoindent for ocaml
autocmd FileType ocaml source /bbshr/ird/lexifi/tools/ocp-indent-master/tools/ocp-indent.vim

知道fibonacci怎么写吗

http://www.willa.me/2013/11/the-six-most-common-species-of-code.html

Ubuntu : firefox auto selectall in browser bar

最近新装了个Ubuntu 12.04, 发现firefox里的地址搜索框不会自动全选了，需要double click才可以。
网上搜了个解决方案：
step1: at address bar, input:
    about: config

step2: find the item
    browser.urlbar.doubleClickSelectAll
double click it to change value to false;

step3: find the item
   browser.urlbar.clickSelectAll
double click it to change value to true;

done!

Triangle (C++ code)

Leetcode Triangle Oct 30 '123620 / 9772
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.


好久没写code了，先练个暴力的：

void helper(vector<vector<int> > &triangle, int &res, int sum, int level, int pos){
  if(level == triangle.size()) {
        if(sum < res) res = sum;
        return;
  }
  helper(triangle, res, sum + triangle[level][pos], level + 1, pos);
  helper(triangle, res, sum + triangle[level][pos+1], level + 1, pos + 1);

}

int minimumTotal(vector<vector<int> > &triangle) {
        int  n = triangle.size();
        if(n == 0) return 0;
        int sum = triangle[0][0], res = INT_MAX;
        helper(triangle,res, sum, 1,0);

        return res;
    }

果然大集合没过，想了下，如果记录到达每个node的最短距离，可以省去很多重复计算，于是写了下面这个：
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
       map<pair<int,int>, int> record;
       int res = INT_MAX;
       record[make_pair(0,0)] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[make_pair(i,0)] = record[make_pair(i-1,0)] + triangle[i][0];
            record[make_pair(i,i)] = record[make_pair(i-1,i-1)] + triangle[i][i];
            for(int j = 1;  j < i; j++){
                 record[make_pair(i,j)] = min(record[make_pair(i-1,j)], record[make_pair(i-1, j-1)]) +  
                 triangle[i][j];
            }
      }     
      for(int i = 0; i < n; i++){
        if(record[make_pair(n-1,i)] < res) res = record[make_pair(n-1,i)];
      }
        return res;
    }

然后又follow了一下题目的hint, 只用一个长度为n的array来记录结果。注意每次新的一行更新要倒着来。
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
      vector<int> record(n, INT_MIN);
       int res = INT_MAX;
       record[0] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[i] = record[i-1] + triangle[i][i];
            for(int j = i-1;  j > 0; j--){
                 record[j] = min(record[j], record[j-1]) +  triangle[i][j];           
            }
            record[0] += triangle[i][0];
      }     
      for(int i = 0; i < n; i++){
        if(record[i] < res) res = record[i];
      }
        return res;
    }

cc150_2.3,2.4

2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

public static boolean deleteNode(LinkedListNode n){
 if(!n || !n->next) return false;
 n.data = n.next.data;
 n.next = n.next.next;
 return true;
}

2.4 Write code to partition a linked list around a value x, such that all nodes less than x
come before alt nodes greater than or equal to x.

public LinkedListNode partition(LinkedListNode node, int x){
  LinkedListNode index = node, cur = node;
  while(cur){
     if(cur.data < x){
            int temp = cur.data;
            cur.data = index.data;
            index.data = temp;
            index = index.next;
     }
    cur = cur.next;          
    }
 return node;
}

singleton pattern

deal with multithreading:
1, synchronization: if it's used rarely in the application
public class Singleton{
  private Singleton(){}
  private static Singleton  uniqueInstance;
  public static synchronized Singleton getInstance(){
    if(uniqueInstance == null){
        uniqueInstance = new Singleton();
    }
    return uniqueInstance;
  }
 // other methods
}

2， make an eagerly created instance

public class Singleton{
  private Singleton(){}
  private static Singleton  uniqueInstance = new Singleton();
  public static  Singleton getInstance(){
    return uniqueInstance;
  }
 // other methods
}

3, double check lock

public class Singleton{
  private Singleton(){}
  private static volatile Singleton  uniqueInstance;
  public static Singleton getInstance(){
    if(uniqueInstance == null){
      synchronized(Singleton.class){
        if(uniqueInstance == null) 
          uniqueInstance = new Singleton();
       } 
    }
    return uniqueInstance;
  }
 // other methods
}

cc150_2.2

Implement an algorithm to find the kth to last element of a singly linked list.

LinkedListNode  nthToLast(LinkedListNode head, int k) {
  if(k <= 0) return null;
  LinkedListNode prev = head;
  LinkedListNode cur = head;
  while(cur && k > 1){    
     cur = cur.next;
     k--;
  }
  if(!cur) return null;
  while(cur.next){
     cur = cur.next;
     prev = prev.next;
  }

 return prev;
}

cc150_2.1

Write code to remove duplicates from an unsorted linked list.

//method: hashtable
public static void deleteDups(LinkedListl\lode n) {
   Hashtable table = new Hashtable();
   LinkedListNode prev = null;
   while(n){
       if(table.containsKey(n.data)){
          prev.next = n.next;
      }
      else table.put(n.data, true);
      n = n.next;
   }

}

tips: Hashtable vs HashMap
There are several differences between HashMap and Hashtable in Java:

1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
3. One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

cc150_1.8

Assume you have a method isSubstring which checks if one word is a substring
of another. Given two strings, si and s2, write code to check Ifs2 is a rotation of si
using only onecalltoisSubstring (e.g., "waterbottLe" is a rotation of "erbottLewat").

public boolean isRotation(String si, String s2){
  if(s1.length() != s2.length() || s1.length() == 0) return false;
  return isSubstring(s1+s1, s2) ;
}

cc150_1.7

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column are set to 0.

public void setZeros(int[][] matrix) {
  boolean[] column = new boolean[matrix[0].length];
  for(int i = 0; i < matrix.length; i++){
     for(int j = 0; j < matrix[0].length; j++){
          if(column[j]) continue;
          if(matrix[i][j] == 0) {
           //set i-th row and j-th col zero
             for(int k = 0; k < matrix[0].length; k++){
                   matrix[i][k] = 0;
             }
             for(int k = 0; k < matrix.length; k++){
                   matrix[k][j] = 0;
             }
             //mark column and move to next row
             column[j] = true;
             break;
          }
    }
  }
}

cc150_1.6

Given an image represented by an NxN matrix, where each pixel in the image is
4 bytes, write a method to rotate the image by 90 degrees. Can you do this in
place?

public void rotate(int[][] matrix, int n){
  for(int i = 0; i < n/2; i++){
   for(int j = i; j < n-1-i; j++){
      int tmp = matrix[i][j];
      matrix[i][j] = matrix[j][n-i-1];
      matrix[j][n-i-1] = matrix[n-i-1][n-j-1];
      matrix[n-i-1][n-j-1] = matrix[n-j-1][i];
      matrix[n-j-1][i] = matrix[i][j];
    }
  }
}

cc150_1.5

Implement a method to perform basic string compression using the counts of
repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

//use StringBuffer to avoid useless copying
public String compressBad(String str){
   int  count = 1, n = str.length();   if(n == 0) return null;
   StringBuffer res =new StringBuffer(); 
   for(int i = 1; i < n; i++){
      if(str.charAt(i) == str.charAt(i-1)){
          count++;
      }
     else {
          res.append(str.charAt(i-1));
          res.append(count);
          count = 1;
   }
 res.append(str.charAt(n-1));
 res.append(count);
 String cp = res.toString();
 if(cp.length() < n) return cp;
 else return str.
}

//if don't use StringBuffer, first figure out the new size, then do backtracking to get desired string from a new char array.

cc150_1.4

Write a method to replace all spaces in a string with '%20'. You may assume that the
string has sufficient space at the end of the string to hold the additional characters,
and that you are given the "true" length of the string. (Note: if implementing in Java,
please use a character array so that you can perform this operation in place.)

public void replaceSpaces(char[] str, int length) {
  int spacecount = 0, newlength, index;
  for(int i = 0; i < length; i++){
     if(str[i] == ' ') spacecount++;
  }
  index = length + (spacecount<<1);
  str[index--] = '\0';
  for(int i = length - 1; i >= 0; i--){
       if(str[i] != ' ') str[index--] = str[i];
       else{
          str[index--] = '0';
          str[index--] = '2';
          str[index--] = '%';
      }
  }
}

cc150_1.3

Given two strings, write a method to decide if one is a permutation of the other.

//method 1: sort and compare
String sort(String s){
  char[] content = s.toCharArray();
  java.util.Arrays.sort(content);
  return new String(content);
}

public boolean permutation(String s, String t){
  if(s.length() != t.length()) return false;
  return sort(s).equals(sort(t));
}

//method 2: hash and compare
public boolean permutation(String s, String t) {
  if (s.length() != t.lengthQ)  return false;
  int[] count = new int[256];
  for(int i = 0; i < s.length(); i++){
     int ch = s.charAt(i);
     count[ch]++;
  }
 for(int i = 0; i < s.length(); i++){
     count[ch]--;
    if(count[ch] < 0) return false;
  }

  return true;

}

cc150_1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if
you cannot use additional data structures?
//if it's ASCII characters: 256 candidates
public boolean isUnique(String str){
  if(str.length() > 256) return false;
  boolean[] v = new boolean[256];
  for(int i = 0; i < str.length(); i++){
      int ch = str.charAt[i];
      if(v[ch]) return false;
      v[ch] = true;
  }
  return true;
}

//use bit to save space: assume that it's a~z characters: 26 candidates, so one int = 32 bits is enough.
public boolean isUnique(String str){
  int checker = 0;
  for(int i = 0; i < str.length(); i++){
    int ch = str.charAt[i] - 'a';
    if( (checker & (1<<ch)) ) return false;
    checker |= (1<<ch);
  }
  return true;
}

Scramble string (C++ code)

Leetcode Scramble String, Apr 30 '121887 / 5901
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
 思路： 直接递归做超时了，因此改用DP，恩，其实是个很典型的DP题了。

0. bool isScramble(string s1, string s2) {  
1.   int n = s1.size();  
2.   if(s2.size() != n) return false;  
3.   if(n == 0) return true;  
4.   bool A[n][n][n+1];  
5.   for(int i = 0; i < n; i++){  
6.    for(int j = 0; j < n; j++){  
7.       A[i][j][1] =(s1[i] == s2[j])? true : false;  
8.    }  
9.  }  
10. for(int k = 2; k < n+1; k++){  
11.   for(int i = 0; i <= n - k; i++){  
12.     for(int j = 0; j <= n - k; j++){  
13.       A[i][j][k] = false;  
14.       for(int m = 1; m < k; m++){  
15.        if(A[i][j][m] && A[i+m][j+m][k-m]) A[i][j][k] = true;       
16.        if(A[i][j+k-m][m] && A[i+m][j][k-m]) A[i][j][k] = true;  
17.       }    
18.     }   
19.   }  
20. }  
21.   
22. return A[0][0][n];  
23.   
24. }   

暴力解法：
bool isScramble(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        int n = s1.length();
        if(n == 0) return true;
        if(n == 1) return s1 == s2;

       for(int i = 1; i < n; i++){

         string s1left = s1.substr(0,i), s1right = s1.substr(i, n-i);
         string s2left = s2.substr(0, i), s2right = s2.substr(i, n-i);
         string s2left2 = s2.substr(0, n-i), s2right2 = s2.substr(n-i, i);

        if(isScramble(s1left, s2left) && isScramble(s1right, s2right)) return true;
        if(isScramble(s1left, s2right) && isScramble(s1right, s2left)) return true;
        if(isScramble(s1left, s2left2) && isScramble(s1right, s2right2)) return true;
        if(isScramble(s1left, s2right2) && isScramble(s1right, s2left2)) return true;

        }
        return false;                   
    }