Posts

Showing posts from August, 2013

Swap a Number with 0

/*** Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”. Example: src={1,0,3,2}; tgt={0,1,2,3}; 1230 0123 IDEA: src[i] = 0; int target = tgt[i]; find target in src and swap with 0; if zero is at ideal position, find the next wrong position and swap if all number is at the ideal position, finish ***/ #include <iostream> using namespace std; void swap( int * a , int * b ) {        int t = * a ;        * a = * b ;        * b = t; } int check( int * src , int * tgt , int sz ) {        for ( int i=0; i< sz ; i++) {           ...

Word Break

/*** Word Break Problem ***/ #include <iostream> #include <string> #include <vector> using namespace std; #define MAX_LEN 8 bool dictionaryContains( string word ) {        string dictionary[] = { "mobile" , "samsung" , "sam" , "sung" , "man" , "mango" ,               "icecream" , "and" , "go" , "i" , "like" , "ice" , "cream" };        int size = sizeof (dictionary)/ sizeof (dictionary[0]);        for ( int i = 0; i < size; i++)               if (dictionary[i].compare( word ) == 0)                      return true ;        return false ; } void split_word( string...

selection sort

/*** selection sort: O(n2) find the min on the right part and exchange ***/ #include <iostream> using namespace std; class selectionSort { public :        selectionSort( int *a, int sz);        ~selectionSort() { }        void sort();        void print(); private :        int *as;        int size;        void exchange( int *a1, int *b1);        int getmin( int begin, int end); }; selectionSort::selectionSort( int *a, int sz):as(a), size(sz) { } void selectionSort::sort() {        int pos;        for ( int i = 0; i < size; i++) {               pos...