逆序數的計算
常規的做法
時間：O(N^2)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int foo(const vector<int>& array)
6 {
7 int ret = 0;
8 for (vector<int>::size_type i = 0; i != array.size() - 1; ++i)
9 {
10 for (vector<int>::size_type j = i + 1; j != array.size(); ++j)
11 {
12 if (array[i] > array[j])
13 {
14 ++ret;
15 }
16 }
17 }
18 return ret;
19 }
20
21 int main()
22 {
23 vector<int> array;
24
25 for (int i = 10; i > 0; --i)
26 {
27 array.push_back(i);
28 }
29 cout << foo(array) << endl;
30 return 0;
31 }
改進的做法
利用分治法，借助歸并排序求解逆序數。
時間復雜度：O(NlogN)
在歸并排序的基礎做一個修改即可：
不是算右邊的相對左邊的逆序數，這樣太過于繁雜
而是算左邊相當于右邊的逆序數，這樣可以就在這一個地方做統一處理
即當檢測到左邊大于右邊的時候，則所有剩下的左邊的數都相對于當前右邊的數大，所以逆序數都要加 1 。
count += (end1 - begin1 + 1);
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 int count = 0;
7
8 void merge(int array[], int low, int mid, int high)
9 {
10 int i, k;
11 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
12 int begin1 = low;
13 int end1 = mid;
14 int begin2 = mid + 1;
15 int end2 = high;
16
17 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
18 if(array[begin1]<=array[begin2])
19 {
20 temp[k] = array[begin1++];
21
22 }
23 else
24 {
25 //++count;
26
27 // 不是算右邊的相對左邊的逆序數，這樣太過于繁雜
28 // 而是算左邊相當于右邊的逆序數，這樣可以就在這一個地方做統一處理
29 count += (end1 - begin1 + 1);
30 temp[k] = array[begin2++];
31 }
32 if(begin1 <= end1) //若第一個序列有剩余，直接拷貝出來粘到合并序列尾
33 {
34 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
35 //count += (end1 - begin1 + 1) * (high - mid);
36 }
37 if(begin2 <= end2) //若第二個序列有剩余，直接拷貝出來粘到合并序列尾
38 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
39 memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
40 free(temp);
41 }
42
43 int merge_sort(int array[], unsigned int first, unsigned int last)
44 {
45 int mid = 0;
46 if(first<last)
47 {
48 mid = (first+last)/2;
49 merge_sort(array, first, mid);
50 merge_sort(array, mid+1,last);
51 merge(array,first,mid,last);
52 }
53 return count;
54 }
55
56
57 int foo(int array[], int n)
58 {
59 return merge_sort(array, 0, n - 1);
60 }
61
62 int main()
63 {
64 int array[] = {9, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0};
65 // int array[] = {1, 3, 2, 4, 3};
66 // int array[] = {1, 3, 2};
67 cout << foo(array, sizeof (array) / sizeof (*array)) << endl;
68 return 0;
69 }
http://www.cnblogs.com/dskit/archive/2009/12/16/1625942.html
http://hi.baidu.com/xiaohanhoho/blog/item/277a09392a0e4722b8998fdc.html
http://www.shnenglu.com/asp/articles/14261.html
http://www.cublog.cn/u2/62093/showart_484338.html
http://blog.csdn.net/guzhilei1986/archive/2008/04/10/2276782.aspx
posted @
2011-06-22 01:11 unixfy 閱讀(552) |
評論 (0) |
編輯 收藏歸并排序是穩定的
時間復雜度：O(NlogN)
空間復雜度：O(N)
合并 + 遞歸
http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
http://baike.baidu.com/view/90797.htm
http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.5.1.html
http://www.zjhyzx.net/Article/ShowArticle.asp?ArticleID=924
http://learn.akae.cn/media/ch11s04.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 void merge(int array[], int low, int mid, int high)
7 {
8 int i, k;
9 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
10 int begin1 = low;
11 int end1 = mid;
12 int begin2 = mid + 1;
13 int end2 = high;
14
15 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
16 if(array[begin1]<=array[begin2])
17 temp[k] = array[begin1++];
18 else
19 temp[k] = array[begin2++];
20 if(begin1 <= end1) //若第一個序列有剩余，直接拷貝出來粘到合并序列尾
21 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
22 if(begin2 <= end2) //若第二個序列有剩余，直接拷貝出來粘到合并序列尾
23 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
24 memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
25 free(temp);
26 }
27
28 void merge_sort(int array[], unsigned int first, unsigned int last)
29 {
30 int mid = 0;
31 if(first<last)
32 {
33 mid = (first+last)/2;
34 merge_sort(array, first, mid);
35 merge_sort(array, mid+1,last);
36 merge(array,first,mid,last);
37 }
38 }
39
40 int main()
41 {
42 int a[8] = {4, 7, 5, 3, 2, 8, 6, 1};
43 for (int i = 0; i != 8; ++i)
44 {
45 cout << a[i] << ' ';
46 }
47 cout << endl;
48 merge_sort(a, 0, 7);
49 for (int i = 0; i != 8; ++i)
50 {
51 cout << a[i] << ' ';
52 }
53 cout << endl;
54 }
posted @
2011-06-22 00:13 unixfy 閱讀(113) |
評論 (0) |
編輯 收藏基數排序、桶排序
這里介紹一下非比較排序
頭緒比較亂
編程珠璣 I 第一節中就講到一種排序方法：大批量的數排序，內存有限，利用 bitmap 可以很好的解決。時間為 O(N) 。
對于不重復出現的數的集合，也就是說對于某個數最多只出現一次。可以利用 bitmap 來解決。因為一個 bit 只有兩個狀態： 0 和 1 。
1.
對于重復出現的數，可以利用一般類型數組來解決。對于每個數，以每個數為索引，記錄以該索引的元素自加 1 。處理完后，掃描這個輔助數組，將記錄的信息，也就是索引的次數，把索引以次數存入原來數組中。
2.
這種直接以待排序的數為索引，需要很大的輔助數組。所以可以利用針對待排序的數的每位來處理，每個位的范圍也就是 0 - 9 十的大小。對于多維的待排序數處理方式有兩種。即從左到右和從右到左。
從左到右：左面的排完序后，整體次序不變了，只是調整的次位的相對順序。
從右到左：右面的排完序后，整體的次序還會有變化的，只不過是隨著從右到左，依次調整的次數越來越少了。
3.
桶排序，對于一系列待排序數，可以先按照各個數的屬性將所有數分配到各個桶里。這樣后，對于每個桶里的數可以使用插入排序進行各個桶的排序。
1 #include <iostream>
2 #include <vector>
3 #include <cstring>
4 using namespace std;
5
6 void sort(vector<int>& array)
7 {
8 int temp[1000];
9 memset(temp, 0, sizeof (int) * 1000);
10 for (vector<int>::size_type i = 0; i != array.size(); ++i)
11 {
12 ++temp[array[i]];
13 }
14 array.clear();
15 for (int i = 0; i < 1000; ++i)
16 {
17 while (temp[i]-- != 0)
18 {
19 array.push_back(i);
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> array;
27 for (int i = 0; i < 10; ++i)
28 {
29 array.push_back(i);
30 }
31 for (int i = 10; i >= 0; --i)
32 {
33 array.push_back(i);
34 }
35 sort(array);
36 for (vector<int>::size_type i = 0; i < array.size(); ++i)
37 {
38 cout << array[i] << ' ';
39 }
40 cout << endl;
41 return 0;
42 }
posted @
2011-06-21 22:45 unixfy 閱讀(376) |
評論 (0) |
編輯 收藏排序的作用
幾個問題
·刪除數組中大于一定數的所有數
·查找少量數中重復出現的數
·在數組中找到兩個等于一給定數的二元組
如何解決這些問題？
·排序，二分查找，刪除
·排序，遍歷
·排序，左右遍歷檢測，如果小向右走，如果大向左走
排序是基本的算法，到處都會用到。
解決問題的關鍵在于對處理對象進行調整。也就是做預處理工作。
posted @
2011-06-21 21:19 unixfy 閱讀(220) |
評論 (0) |
編輯 收藏
之前讀過間斷讀過兩遍。
迫于找工作壓力，現再次翻閱。
1. 讓 CPU 占用率聽你指揮
刷新周期
int main()
{
for (; ; )
{
for (int i = 0; i < 960000; ++i)
{
sleep(10);
}
}
}
while ((GetTickCount() - startTime) <= busyTime);
2. 中國象棋將帥問題
struct
{
unsigned char a : 4;
unsigned char b : 4;
} i;
i.a, i.b;
3. 一摞烙餅的排序
排序問題
每次找到最大的
4. 買書問題
貪心算法的反例
5. 快速找到出故障機器
ID
哈希表
<異或>
·0 保持
·1 取反
·A ^ A = 0
兩個出問題，如果是不同的兩個，可以解決，即是根據異或原理，把所有 ID 分成兩部分，以某一位是 0 還是 1 分開。在分開的兩部分中每個部分，采用異或的方法進行解決。
利用不變量進行解決
·加法不變量
·乘法不變量
·平方和不變量
6. 飲料供貨
7. 光影切割問題
問題轉換
逆序的分治計算方法
8. 小飛的電梯調度算法
直觀暴力解法
N1, N2, N3
逐層遍歷
9. 高效率地安排見面會
10. 雙線程高效下載
·下載
·寫入磁盤
11. NIM(1) 一排石頭的排序
posted @
2011-06-20 16:23 unixfy 閱讀(103) |
評論 (0) |
編輯 收藏字符串旋轉問題
需要 O(N) 的時間，O(1) 的空間
借助字符串翻轉
ABCEFG
((ABC)'(EFG)')'
=(CBAGFE)'
=EFGABC
對一個字符串，進行給定位置的逆轉。
1 #include <iostream>
2 using namespace std;
3
4 void swap(char& a, char& b)
5 {
6 a ^= b;
7 b ^= a;
8 a ^= b;
9 }
10
11 void reverse(char* s, int l, int h)
12 {
13 while (l < h)
14 {
15 swap(s[l++], s[h--]);
16 }
17 }
18
19 int getLen(char* s)
20 {
21 int ret = 0;
22 while (*s++ != '\0')
23 {
24 ++ret;
25 }
26 return ret;
27 }
28
29 char* rotate(char* s, int pos)
30 {
31 int t = getLen(s) - 1;
32 reverse(s, 0, pos - 1);
33 reverse(s, pos, t);
34 reverse(s, 0, t);
35 return s;
36 }
37
38 int main()
39 {
40 char s[100];
41 int pos;
42 while (cin >> s >> pos)
43 {
44 cout << rotate(s, pos) << endl;
45 }
46 return 0;
47 }
http://www.shnenglu.com/jake1036/archive/2011/03/05/141163.html
posted @
2011-06-17 22:58 unixfy 閱讀(122) |
評論 (0) |
編輯 收藏
連續內存，溢出
1 #include <iostream>
2 using namespace std;
3
4 template <typename T>
5 class DoulStack
6 {
7 private:
8 T* data_;
9 int top1_;
10 int top2_;
11 unsigned size_;
12 public:
13 DoulStack(unsigned size = 1000) : data_(new T[size]), top1_(0), top2_(size - 1), size_(size)
14 {
15 if (data_ == 0)
16 {
17 exit(1);
18 }
19 }
20 DoulStack(const DoulStack& ds) : data_(new T[ds.size_]), top1_(ds.top1_), top2_(ds.top2_), size_(ds.size_)
21 {
22 if (data_ == 0)
23 {
24 exit(1);
25 }
26 memcpy(data_, ds.data_, sizeof (T) * ds.size_);
27 }
28 DoulStack& operator = (const DoulStack& ds)
29 {
30 if (this != &ds)
31 {
32 delete [] data_;
33 data_ = new T[ds.size_];
34 if (data_ == 0)
35 {
36 exit(1);
37 }
38 top1_ = ds.top1_;
39 top2_ = ds.top2_;
40 size_ = ds.size_;
41 memcpy(data_, ds.data_, sizeof (T) * ds.size_);
42 }
43 return *this;
44 }
45 ~DoulStack()
46 {
47 delete [] data_;
48 }
49 bool empty()
50 {
51 return empty1() && empty2();
52 }
53 bool full()
54 {
55 return top1_ - 1 == top2_;
56 }
57 bool resize(unsigned size)
58 {
59 T* temp = new T[size];
60 if (temp == 0)
61 {
62 exit(1);
63 }
64 for (int i = 0; i != top1_; ++i)
65 {
66 temp[i] = data_[i];
67 }
68 for (int i = size - 1, j = size_ - 1; j != top2_; --i, --j)
69 {
70 temp[i] = data_[j];
71 }
72 size_ = size;
73 delete [] data_;
74 data_ = temp;
75 }
76 void push1(const T& t)
77 {
78 if (full())
79 {
80 resize(size_ * 2);
81 }
82 data_[top1_++] = t;
83 }
84 void push2(const T& t)
85 {
86 if (full())
87 {
88 resize(size_ * 2);
89 }
90 data_[top2_--] = t;
91 }
92 void pop1()
93 {
94 --top1_;
95 }
96 void pop2()
97 {
98 ++top2_;
99 }
100 T top1()
101 {
102 return data_[top1_ - 1];
103 }
104 T top2()
105 {
106 return data_[top2_ + 1];
107 }
108 bool empty1()
109 {
110 return top1_ == 0;
111 }
112 bool empty2()
113 {
114 return top2_ == size_ - 1;
115 }
116 };
117
118 int main()
119 {
120 DoulStack<int> ds;
121 for (int i = 0; i < 10; ++i)
122 {
123 ds.push1(i);
124 ds.push2(9 - i);
125 }
126 while (!ds.empty1())
127 {
128 cout << ds.top1() << endl;
129 ds.pop1();
130 }
131 while (!ds.empty2())
132 {
133 cout << ds.top2() << endl;
134 ds.pop2();
135 }
136 cout << ds.empty() << endl;
137 }
posted @
2011-06-17 15:30 unixfy 閱讀(147) |
評論 (0) |
編輯 收藏
摘要: 前綴匹配
網絡層的數據報網絡，在路由器轉發功能實現中會用到前綴匹配，即是對 IP 地址與路由表中的目的地址范圍的公共部分進行前綴匹配。由于有的前綴存在包含的問題，對有些 IP 地址會造成多重匹配，短的匹配會造成 IP 的轉發錯誤。所以可以遵循 最長前綴匹配原則 進行匹配。
首先做一個 ip 轉換的實現從 unsigned int 32 位整型數到 ip 字符串的轉換從 ip 字符串到 unsi...
閱讀全文
posted @
2011-06-17 14:36 unixfy 閱讀(796) |
評論 (0) |
編輯 收藏
來自于《高質量程序設計指南——C++/C 語言》
實現類似 copy 的功能
1 #include <cstdio>
2 using namespace std;
3
4 int main(int argCount, char* argValue[])
5 {
6 FILE* srcFile = 0, *destFile = 0;
7 int ch = 0;
8 if (argCount != 3)
9 {
10 printf("Usage: %s src-file-name dest-file-name\n", argValue[0]);
11 }
12 else
13 {
14 if ((srcFile = fopen(argValue[1], "r")) == 0)
15 {
16 printf("Can not open source file \"%s\"!", argValue[1]);
17 }
18 else
19 {
20 if ((destFile = fopen(argValue[2], "w")) == 0)
21 {
22 printf("Can not open destination file \"%s\"!", argValue[2]);
23 fclose(srcFile);
24 }
25 else
26 {
27 while ((ch = fgetc(srcFile)) != EOF)
28 {
29 fputc(ch, destFile);
30 }
31 printf("Successful to copy a file!\n");
32 fclose(srcFile);
33 fclose(destFile);
34 return 0;
35 }
36 }
37 }
38 return 1;
39 }
posted @
2011-06-16 21:48 unixfy 閱讀(116) |
評論 (0) |
編輯 收藏
找到 50 億個 32 位整型數中出現重復的數。
可行的方法是利用位圖。32 位數的范圍是 0~2^32 - 1
開辟一個 2^32 個 bit 的空間，大小約為 512 MB。
一次掃描每一個數，檢測以該數為索引的那個 bit 是否為 0 ，若為 0 ，則說明過去不存在，將其置為 1，如果為 1 則說明以前出現過，則說明該數是重復出現的。
這個問題解決的關鍵在于用待檢測數去做索引，利用隨即存取的特點，可以做到 O(1) 的效率。用數本身做索引是一種高效的方法。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 void foo(const vector<int>& arr)
8 {
9 bitset<1024> bs;
10
11 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
12 {
13 if (bs[arr[i]] == 0)
14 {
15 bs[arr[i]].flip();
16 }
17 else
18 {
19 cout << arr[i] << endl;
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> arr;
27 for (int i = 0; i < 100; ++i)
28 {
29 arr.push_back(i);
30 }
31 arr.push_back(5);
32 arr.push_back(25);
33
34 foo(arr);
35 return 0;
36 }
關鍵在于這個位圖如何實現。STL 中有個 bitset 就好可以做這個工作。
但是如果需要仔細實現一個該如何辦？也就是說自己實現一個 bitset
實現一個類似的 bitset
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset-source.html
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset.html
http://blog.sina.com.cn/s/blog_4d3a41f40100kxnw.html
http://blog.sina.com.cn/s/articlelist_1295663604_0_1.html
更進一步學習 bitset ，《STL 源碼剖析》中應該有所介紹
關鍵是對 bit 的讀寫如何操作。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 template <unsigned NUM>
8 class MyBitset
9 {
10 private:
11 char* data_;
12 unsigned numbits;
13 unsigned numchars;
14 public:
15 MyBitset() : numbits(NUM), numchars(NUM / 8 + 1)
16 {
17 data_ = new char[numchars];
18 if (data_ == 0)
19 {
20 exit(1);
21 }
22 memset(data_, 0, numchars);
23 }
24 unsigned operator [] (unsigned pos)
25 {
26 char c = data_[pos / 8];
27 unsigned t = pos - pos / 8 * 8;
28 while (t > 0)
29 {
30 c <<= 1;
31 --t;
32 }
33 if (c & 128)
34 {
35 return 1;
36 }
37 else
38 {
39 return 0;
40 }
41 }
42 void set(unsigned pos)
43 {
44 char* p = data_ + pos / 8;
45 unsigned t = pos - pos / 8 * 8;
46 char temp = pow(2.0, 8.0 - t);
47 *p |= temp;
48 }
49 };
50
51 void foo(const vector<int>& arr)
52 {
53 // bitset<1024> bs;
54 MyBitset<1024> bs;
55
56 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
57 {
58 if (bs[arr[i]] == 0)
59 {
60 // bs[arr[i]].flip();
61 bs.set(arr[i]);
62 }
63 else
64 {
65 cout << arr[i] << endl;
66 }
67 }
68 }
69
70 int main()
71 {
72 vector<int> arr;
73 for (int i = 0; i < 100; ++i)
74 {
75 arr.push_back(i);
76 }
77 arr.push_back(5);
78 arr.push_back(25);
79
80 foo(arr);
81 return 0;
82 }
posted @
2011-06-16 17:17 unixfy 閱讀(497) |
評論 (2) |
編輯 收藏