2014年3月12日 星期三

STL 函數 "fill" 初始化靜態陣列

利用 fill 函式, 輕鬆初始化靜態陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;

int main( ){
    const int N = 10;
    int static_arr[N];
    for( int i = 0 ; i < N ; ++i )
        cout << static_arr[i] << " ";
    cout << endl;

    fill( static_arr, static_arr + N, 0);

    for( int i = 0 ; i < N ; ++i )
        cout << static_arr[i] << " ";
    cout << endl;

    return 0;
}


Output:
1
2
1074806772 1073829312 1074838040 1073829928 -1085147136 -16121856 -1085147192 134539877 134539728 0 
0 0 0 0 0 0 0 0 0 0

關於動態陣列初始化

2014年3月10日 星期一

Insert operation of map and set in C++ STL

single element (1)
pair<iterator,bool> insert (const value_type& val);
with hint (2)
iterator insert (iterator position, const value_type& val);

STL的 set 之 insert, 提供兩個可用的方式,

第一種傳入一個欲插入的值,
若已經出現在 set 中, 則插入失敗會回傳相同的key之位置的 iterator 及 false
否則會回傳插入後之位置的 iterator 及 true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <set>
#include <iostream>
using namespace std;

int main( ){
    set<int> s;

    s.insert( 1 );
    s.insert( 2 );

    {
        pair<set<int>::iterator,bool> ret = s.insert( 2 );
        cout << *(ret.first) << " " << ret.second;
    }
    cout << endl;
    {
        pair<set<int>::iterator,bool> ret = s.insert( 3 );
        cout << *(ret.first) << " " << ret.second;
    }
}

Output:
1
2
2 false
3 true



第二種傳入一個搜尋的起點當作 set 找出欲插入位置的 hint,
如果提供的資訊正確, 則可以達到 O(1) 的插入時間


以下比較 hint 之功用:

1
2
3
set<int> s;
for( int i = 0 ; i < 10000000; ++i )
    pair<set<int>::iterator,bool> ret = s.insert(i);
執行時間約11秒

1
2
3
set<int> s;
for( int i = 0 ; i < 10000000; ++i )
    set<int>::iterator ret = s.insert(s.end(), i);
執行時間約3秒






2014年3月7日 星期五

Finding the redundant number in an array with fixed range elements

假設輸入一個陣列具有101個數, 數字分布範圍是1到100, 找出重複的數
Solution: linear search, sum, ...  O(n)

假設傳入的陣列為sorted
Solution: Binary Search    O(log n)

e.g.
b      m         e
0  1  2  3  4  5
1  1  2  3  4  5
index值與element值相同, 往左找, b = b, e = m

b      m         e
0  1  2  3  4  5
1  2  3  4  4  5
index值與element值不相同, 往右找, b = m, e = e


終止條件: b與e的元素相同, 或是 e == b+1
e.g.
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10

pass1:
b                  m                  e
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10

pass2:
                    b      m           e
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10

pass3:
                            b  m        e
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10

pass4:
                                b  m    e
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10

pass4:
                                b  e
0  1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  9  10
return 9


#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

void shuffle( int *a, int n ){
    int pickedLoc;
    while( n != 0 ){
        // choose a location "pickedLoc" to exchange
        // the element on location n-1 with "pickedLoc"
        pickedLoc = rand( ) % n--;

        // swap
        int temp = a[n];
        a[n] = a[pickedLoc];
        a[pickedLoc] = temp;
    }
}

int find_redundant_linear( int *a, const int n ){
    if( !a || n < 2 ) return -1;
    bool *flag = new bool[n](); // flag[0] is unused

    for( int i = 0 ; i < n ; ++i )
        flag[a[i]] = !flag[a[i]];

    for( int i = 0 ; i < n ; ++i )
        if( !flag[a[i]] ){
            delete [] flag;
            return a[i];
        }
}

int find_redundant_binarySearch( int *a, const int n ){
    if( !a || n < 2 ) return -1;

    int begin = 0;
    int end = n-1;
    int middle;
    while( end != begin + 1 ){
        middle = (begin + end) / 2;
        if( a[middle] == middle )
            end = middle;
        else
            begin = middle;
    }
    return a[begin];
}

int main( ){

    // initialize an array with N numbers within [1, N-1]
    // and only one number is redundant in this array
    const int N = 101;
    int arr[N];
    int *p = arr;
    int *q = arr + sizeof(arr)/sizeof(arr[0]);
    int count = 1;
    while( p != q )
        *p++ = count++;

    // create a redundant number
    srand( time(NULL) );
    arr[N-1] = rand( ) % (N-1) + 1;
    cout << "The redundant number is " << arr[N-1] << endl;

    // shuffle them
    shuffle( arr, N );

    // find redundant
    int r = find_redundant_linear( arr, N );
    cout << "The found redundant number is " << r << endl;

    // sort the array
    p = arr;
    sort( p, q );
    r = find_redundant_binarySearch( arr, N );
    cout << "The found redundant number is " << r << endl;
}


遇到這個問題, 最麻煩的部分是, 知道如何iteration下去, 可是不知道boundary condition怎麼取

方法就是, 找一個很小的例子來觀察 (其實作法就跟數學歸納法的證明一樣), 考慮n小一點的case, 例如 1 個或 2 個inputs, 就是很 trivial 的 case

例如, 此問題就可以考慮當 input 只有 2 個時的case,
index      0  1
element  1  1
顯然終止是在 e == b+1時

只要假設且確保原問題的 input 數量是會 down 此case的 即可

Interview questions - C

1
2
3
4
5
char str[] = "ABCDE"; // sizeof(str): 6
char *p = str; // sizeof(p): 4
char q = *str; // sizeof(q): 1
int n = 10; // sizeof(n): 4
int *ptr = &n; // sizeof(ptr): 4 ; sizeof(*ptr): 4

char的pointer之size是4 (因為存的是位置)
char本身是1 (存的是資料)


========================================================================
1
2
3
4
5
6
7
8
int arr[] = {6, 7, 8, 9, 10};
int *ptr = arr;
*ptr++ += 123;
*++ptr += 123;
int *p = arr;
int *q = arr + sizeof(arr)/sizeof(*arr);
while( p != q )
    cout << *p++ << " "; //129 7 131 9 10
*ptr++
等價於
*(ptr++)

compound assignment operator:
將 right-hand operand 加到左邊, 再將結果存入 left-hand operand
(assignment是最後做!)

*ptr++ += 123;
左邊取值6 (位置仍在6), 將123 + 6 = 129 assign到 6 的位置, 完成後 ptr 前進到 7 的位置
*++ptr += 123;
左邊先前進到8的位置, 取值8, 將123 + 8 = 131 assign到 8 的位置

注意這兩個意義不一樣:
*ptr++ += 123;
*ptr++ = *ptr++ + 123;
後者是 Undefined behavior


========================================================================
1
2
3
4
5
6
7
int* arr1[8];
int (*arr2)[8];
int *(arr3[8]);

printf("size of arr1 = %d\n", sizeof(arr1)); // 32
printf("size of arr2 = %d\n", sizeof(arr2)); // 4
printf("size of arr3 = %d\n", sizeof(arr3)); // 32


========================================================================
1
2
3
4
5
6
7
union{
    int num;
    unsigned char n[4];
}q;
q.num = 10;
for( int i = 0 ; i< 4 ; i++)
    printf("%x ", q.n[i]); // a 0 0 0

此片段可用來判斷機器是little-endian
10 => 0 0 0 a 
n      ->a
n+1  ->0
n+2  ->0
n+3  ->0
(由尾端開始放入memory, 記得前題都是記憶體位置 低到高/小到大/index 0到n)


========================================================================
#include <iostream>
using namespace std;

class Animal{
public:
    Animal() { cout << "Animal" << endl; }
    ~Animal() { cout << "~Animal" << endl; }
    void move() { cout << "Animal move" << endl; }
    virtual void eat() { cout << "Animal eat" << endl; }
};

class Dog: public Animal{
public:
    Dog() { cout << "Dog" << endl; }
    ~Dog() { cout << "~Dog" << endl; }
    void move() { cout << "Dog move" << endl; }
    void eat() { cout << "Dog eat" << endl; }
};

int main( ){
    {
    Dog dog;                // Animal
                            // Dog
    Animal *pAnimal = &dog;
    Dog *pDog = &dog;

    pAnimal->eat();         // Dog eat
    pAnimal->move();        // Animal move
    pDog->eat();            // Dog eat
    pDog->move();           // Dog move
    }                       // ~Dog
                            // ~Animal
    {
    Dog *pDog = new Dog();  // Animal
                            // Dog
    Animal *pAnimal = pDog;

    pAnimal->eat();         // Dog eat
    pAnimal->move();        // Animal move
    pDog->eat();            // Dog eat
    pDog->move();           // Dog move
    delete pAnimal;         // ~Animal
    }
}


========================================================================
1
2
3
4
5
6
7
8
9
10
cout << sizeof(short int) << endl;              // 2
cout << sizeof(unsigned short int) << endl;     // 2
cout << sizeof(unsigned int) << endl;           // 4
cout << sizeof(int) << endl;                    // 4
cout << sizeof(long int) << endl;               // 4
cout << sizeof(signed char) << endl;            // 1
cout << sizeof(unsigned char) << endl;          // 1
cout << sizeof(float) << endl;                  // 4
cout << sizeof(double) << endl;                 // 8
cout << sizeof(long double) << endl;            // 12

short int = short
long int = long


2014年3月6日 星期四

Evaluation order is undefined - C

#include <iostream>
using namespace std;

class Add{
public:
    Add( int x = 0 ) : val( x ) {}
    int getVal() const {return val;}
    void setVal( int x ) {val = x;}

    Add& operator++();
private:
    int val;
};
Add& Add::operator++(){
    cout << "Increment " << val << endl;
    ++val;
    return *this;
}

Add operator +(const Add& lhs, const Add& rhs)
{
    cout << "Add " << lhs.getVal() << " and " << rhs.getVal() << "\n";
    int added = lhs.getVal();
    added = added + rhs.getVal();
    return Add(added);
}
int main( ){
    {
    Add x(10), y(20);
    ++x = ++x + ++y;
    cout << x.getVal() << endl;
    }
    cout << endl;
    {
    Add x(10), y(20);
    Add z;
    ++z = ++x + ++y;
    cout << z.getVal() << endl;
    }
    cout << endl;
    {
    Add x(10), y(20);
    ++x = ++y + ++x;
    cout << x.getVal() << endl;
    }
    return 0;
}


mingw32-g++ by Code::Blocks :
Increment 10
Increment 20
Increment 11
Add 12 and 21
33

Increment 0
Increment 20
Increment 10
Add 11 and 21
32

Increment 10
Increment 11
Increment 20
Add 21 and 12
33
1. 等號左邊 prefix increment
2. rhs increment
3. lhs increment
4. addition
5. assign

codepad output and Visual Studio 2012 ouput:
Increment 20
Increment 10
Add 11 and 21
Increment 11
32

Increment 20
Increment 10
Add 11 and 21
Increment 0
32

Increment 10
Increment 20
Add 21 and 11
Increment 11
32
1. 等號右邊 rhs increment
2. 等號右邊 lhs increment
3. addition
4. 等號左邊 prefix increment
5. assign


結論:
當一個expression中, 某一個 sub-expression 改變某另一個 sub-expression 必須用到的 operand 之值, 此種 expression 的行為是 undefined, 因為此語言未保證 left-to-right evaluation order




2014年3月5日 星期三

孫燕姿 - 克卜勒



克卜勒

作詞:hush!
作曲:hush!

Key: C
1--- 4--- b7--- 1---
等不到你 成為我最閃亮的星星
我依然願意借給你我的光

6m--- 27---  4 - 5 - 1---
投射給你 直到你那燦爛的光芒
輕輕地掛在遙遠的天上

1--- 4--- b7--- 1---
當你沉靜 天空那條冰冷的銀河
粼粼的波光夠不夠暖和你

6m--- 27--- 4--- 5---
當你想起 那道源自於我的光芒
我依然願意為你來歌唱


1--- 3m--- 2m--- 4m---
一閃一閃亮晶晶 好像你的身體
藏在眾多孤星之中 還是找得到你

1--- 3m--- b3--- 4- 5-
掛在天上放光明 反射我的孤寂
提醒我 我也只是一顆寂寞的星星
1--- b7--- 1--- 0---

1--- 4--- b7--- 1---
當你沉靜 天空那條冰冷的銀河
粼粼的波光夠不夠暖和你

6m--- 27---  4--- 5---
當你想起 那道源自於我的光芒
我依然願意為你來歌唱

1--- 3m--- 2m--- 4m-5-
一閃一閃亮晶晶 好像你的身體
藏在眾多孤星之中 還是找得到你

1--- 3m--- b3 /2 /1 /b7   4- 5--
掛在天上放光明 反射我的孤寂
提醒我 我也只是一顆寂寞的星星


(節奏變shuffle)
b7 6m 1
浩瀚的世界裡
更迭的人海裡
和你互相輝映


6m  /5  2/#4   5
讓我們延續
用盡所有思念
唱一首歌給你
給你
(過門: 高把位5 4 5 D 型)

1--- 3m/7--- 2m--- 4m-5-
一閃一閃亮晶晶 好像你的身體
藏在眾多孤星之中 還是找得到你

1--- 3m--- b3 /2 /1 /b7   4- 5--
掛在天上放光明 反射我的過去
提醒我 我不再是一顆寂寞的星星

1 16 1sus4 1add9

2014年2月26日 星期三

Rotate an square image by 90 degrees in place

Main idea:

  • There is a relation between the locations of exchanged

 1   2   3   4
 5   6   7   8
 9  10 11 12
13 14 15 16

after rotation

13  9  5 1
14 10 6 2
15 11 7 3
16 12 8 4

(i, j) -> (j, n-1-i) -> (n-1-i, n-1-j) -> (n-1-j, i) -> (i, j)

  • Swapping partial image is enough
  • Carefully handle the size of image
 1   2   3   4 
 5   6   7   8
 9  10 11 12
13 14 15 16

  1   2   3   4   5
  6   7   8   9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25


C++ code :

#include <iostream>
using namespace std;

class Mat{
public:
    Mat( const int *a, const int size );
    ~Mat();
    void showElement() const;
    void rotate( );
private:
    int **m_image;
    int m_size;
};

Mat::Mat( const int *a, const int size ) : m_image(NULL), m_size(size)
{
    if( m_size <= 0 )   return;
    m_image = new int*[m_size]( );
    for( int i = 0 ; i < m_size ; i++ )
        m_image[i] = new int[m_size]( );

    // assign array value to member variable
    for( int i = 0, p = 0 ; i < m_size ; i++ )
        for( int j = 0 ; j < m_size ; j++ )
            m_image[i][j] = a[p++];

}
Mat::~Mat(){
    if(m_image){
        for( int i = 0 ; i < m_size ; i++ )
            delete [] m_image[i];
        delete [] m_image;
    }
}

void Mat::showElement() const{
    for( int i = 0 ; i < m_size ; i++ ){
        for ( int j = 0 ; j < m_size ; j++ )
            cout << m_image[i][j] << " ";
        cout << endl;
    }
}

void Mat::rotate( ){
    const int final_row = (m_size - 1) / 2;
    const int final_col = (m_size % 2) ? (final_row - 1) : final_row;
    const int final_index = m_size - 1;

    // (i, j) -> (j, final_index-i) -> (final_index-i, final_index-j)
    //  -> (final_index-j, i) -> (i, j)

    for( int i = 0 ; i <= final_row ; i++ ){
        for( int j = 0 ; j <= final_col ; j++ )
        {
            int temp = m_image[final_index-j][i];
            m_image[final_index-j][i] = m_image[final_index-i][final_index-j];
            m_image[final_index-i][final_index-j] = m_image[j][final_index-i];
            m_image[j][final_index-i] = m_image[i][j];
            m_image[i][j] = temp;
        }
    }
}
int main( ){
    const int SIZE = 4;
    int image[SIZE * SIZE] = {1, 2, 3, 4,
                             5, 6, 7, 8,
                             9, 10,11,12,
                             13,14,15,16};
    Mat mat( image, SIZE );

    mat.showElement( );
    mat.rotate( );

    cout << endl;
    mat.showElement( );


    cout << endl;
    const int SIZE2 = 5;
    int image2[SIZE2 * SIZE2] = {1, 2, 3, 4, 5,
                             6, 7, 8, 9, 10,
                             11, 12, 13, 14, 15,
                             16, 17, 18, 19, 20,
                             21, 22, 23, 24, 25};
    Mat mat2( image2, SIZE2 );

    mat2.showElement( );
    mat2.rotate( );

    cout << endl;
    mat2.showElement( );

    return 0;
}