Monday, August 31, 2015

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;
    }
};

Saturday, August 29, 2015

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;
    }

Thursday, February 5, 2015

【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();
  
};

Tuesday, December 30, 2014

两个我喜欢的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

Sunday, February 16, 2014

知道fibonacci怎么写吗

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

Friday, September 13, 2013

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!