逆序數(shù)的計(jì)算
常規(guī)的做法
時(shí)間：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 }
改進(jìn)的做法
利用分治法，借助歸并排序求解逆序數(shù)。
時(shí)間復(fù)雜度：O(NlogN)
在歸并排序的基礎(chǔ)做一個(gè)修改即可：
不是算右邊的相對(duì)左邊的逆序數(shù)，這樣太過(guò)于繁雜
而是算左邊相當(dāng)于右邊的逆序數(shù)，這樣可以就在這一個(gè)地方做統(tǒng)一處理
即當(dāng)檢測(cè)到左邊大于右邊的時(shí)候，則所有剩下的左邊的數(shù)都相對(duì)于當(dāng)前右邊的數(shù)大，所以逆序數(shù)都要加 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)); //申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
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) //比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
18 if(array[begin1]<=array[begin2])
19 {
20 temp[k] = array[begin1++];
21
22 }
23 else
24 {
25 //++count;
26
27 // 不是算右邊的相對(duì)左邊的逆序數(shù)，這樣太過(guò)于繁雜
28 // 而是算左邊相當(dāng)于右邊的逆序數(shù)，這樣可以就在這一個(gè)地方做統(tǒng)一處理
29 count += (end1 - begin1 + 1);
30 temp[k] = array[begin2++];
31 }
32 if(begin1 <= end1) //若第一個(gè)序列有剩余，直接拷貝出來(lái)粘到合并序列尾
33 {
34 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
35 //count += (end1 - begin1 + 1) * (high - mid);
36 }
37 if(begin2 <= end2) //若第二個(gè)序列有剩余，直接拷貝出來(lái)粘到合并序列尾
38 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
39 memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回?cái)?shù)組中
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://m.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
歸并排序是穩(wěn)定的
時(shí)間復(fù)雜度：O(NlogN)
空間復(fù)雜度：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)); //申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
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) //比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
16 if(array[begin1]<=array[begin2])
17 temp[k] = array[begin1++];
18 else
19 temp[k] = array[begin2++];
20 if(begin1 <= end1) //若第一個(gè)序列有剩余，直接拷貝出來(lái)粘到合并序列尾
21 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
22 if(begin2 <= end2) //若第二個(gè)序列有剩余，直接拷貝出來(lái)粘到合并序列尾
23 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
24 memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回?cái)?shù)組中
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 }
基數(shù)排序、桶排序
這里介紹一下非比較排序
頭緒比較亂
編程珠璣 I 第一節(jié)中就講到一種排序方法：大批量的數(shù)排序，內(nèi)存有限，利用 bitmap 可以很好的解決。時(shí)間為 O(N) 。
對(duì)于不重復(fù)出現(xiàn)的數(shù)的集合，也就是說(shuō)對(duì)于某個(gè)數(shù)最多只出現(xiàn)一次。可以利用 bitmap 來(lái)解決。因?yàn)橐粋€(gè) bit 只有兩個(gè)狀態(tài)： 0 和 1 。
1.
對(duì)于重復(fù)出現(xiàn)的數(shù)，可以利用一般類型數(shù)組來(lái)解決。對(duì)于每個(gè)數(shù)，以每個(gè)數(shù)為索引，記錄以該索引的元素自加 1 。處理完后，掃描這個(gè)輔助數(shù)組，將記錄的信息，也就是索引的次數(shù)，把索引以次數(shù)存入原來(lái)數(shù)組中。
2.
這種直接以待排序的數(shù)為索引，需要很大的輔助數(shù)組。所以可以利用針對(duì)待排序的數(shù)的每位來(lái)處理，每個(gè)位的范圍也就是 0 - 9 十的大小。對(duì)于多維的待排序數(shù)處理方式有兩種。即從左到右和從右到左。
從左到右：左面的排完序后，整體次序不變了，只是調(diào)整的次位的相對(duì)順序。
從右到左：右面的排完序后，整體的次序還會(huì)有變化的，只不過(guò)是隨著從右到左，依次調(diào)整的次數(shù)越來(lái)越少了。
3.
桶排序，對(duì)于一系列待排序數(shù)，可以先按照各個(gè)數(shù)的屬性將所有數(shù)分配到各個(gè)桶里。這樣后，對(duì)于每個(gè)桶里的數(shù)可以使用插入排序進(jìn)行各個(gè)桶的排序。
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 }
排序的作用
幾個(gè)問(wèn)題
·刪除數(shù)組中大于一定數(shù)的所有數(shù)
·查找少量數(shù)中重復(fù)出現(xiàn)的數(shù)
·在數(shù)組中找到兩個(gè)等于一給定數(shù)的二元組
如何解決這些問(wèn)題？
·排序，二分查找，刪除
·排序，遍歷
·排序，左右遍歷檢測(cè)，如果小向右走，如果大向左走
排序是基本的算法，到處都會(huì)用到。
解決問(wèn)題的關(guān)鍵在于對(duì)處理對(duì)象進(jìn)行調(diào)整。也就是做預(yù)處理工作。
之前讀過(guò)間斷讀過(guò)兩遍。
迫于找工作壓力，現(xiàn)再次翻閱。
1. 讓 CPU 占用率聽(tīng)你指揮
刷新周期
int main()
{
for (; ; )
{
for (int i = 0; i < 960000; ++i)
{
sleep(10);
}
}
}
while ((GetTickCount() - startTime) <= busyTime);
2. 中國(guó)象棋將帥問(wèn)題
struct
{
unsigned char a : 4;
unsigned char b : 4;
} i;
i.a, i.b;
3. 一摞烙餅的排序
排序問(wèn)題
每次找到最大的
4. 買書(shū)問(wèn)題
貪心算法的反例
5. 快速找到出故障機(jī)器
ID
哈希表
<異或>
·0 保持
·1 取反
·A ^ A = 0
兩個(gè)出問(wèn)題，如果是不同的兩個(gè)，可以解決，即是根據(jù)異或原理，把所有 ID 分成兩部分，以某一位是 0 還是 1 分開(kāi)。在分開(kāi)的兩部分中每個(gè)部分，采用異或的方法進(jìn)行解決。
利用不變量進(jìn)行解決
·加法不變量
·乘法不變量
·平方和不變量
6. 飲料供貨
7. 光影切割問(wèn)題
問(wèn)題轉(zhuǎn)換
逆序的分治計(jì)算方法
8. 小飛的電梯調(diào)度算法
直觀暴力解法
N1, N2, N3
逐層遍歷
9. 高效率地安排見(jiàn)面會(huì)
10. 雙線程高效下載
·下載
·寫(xiě)入磁盤(pán)
11. NIM(1) 一排石頭的排序
字符串旋轉(zhuǎn)問(wèn)題
需要 O(N) 的時(shí)間，O(1) 的空間
借助字符串翻轉(zhuǎn)
ABCEFG
((ABC)'(EFG)')'
=(CBAGFE)'
=EFGABC
對(duì)一個(gè)字符串，進(jìn)行給定位置的逆轉(zhuǎn)。
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://m.shnenglu.com/jake1036/archive/2011/03/05/141163.html
連續(xù)內(nèi)存，溢出
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 }
摘要: 前綴匹配
網(wǎng)絡(luò)層的數(shù)據(jù)報(bào)網(wǎng)絡(luò)，在路由器轉(zhuǎn)發(fā)功能實(shí)現(xiàn)中會(huì)用到前綴匹配，即是對(duì) IP 地址與路由表中的目的地址范圍的公共部分進(jìn)行前綴匹配。由于有的前綴存在包含的問(wèn)題，對(duì)有些 IP 地址會(huì)造成多重匹配，短的匹配會(huì)造成 IP 的轉(zhuǎn)發(fā)錯(cuò)誤。所以可以遵循 最長(zhǎng)前綴匹配原則 進(jìn)行匹配。
首先做一個(gè) ip 轉(zhuǎn)換的實(shí)現(xiàn)從 unsigned int 32 位整型數(shù)到 ip 字符串的轉(zhuǎn)換從 ip 字符串到 unsi...
閱讀全文
來(lái)自于《高質(zhì)量程序設(shè)計(jì)指南——C++/C 語(yǔ)言》
實(shí)現(xiàn)類似 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 }
找到 50 億個(gè) 32 位整型數(shù)中出現(xiàn)重復(fù)的數(shù)。
可行的方法是利用位圖。32 位數(shù)的范圍是 0~2^32 - 1
開(kāi)辟一個(gè) 2^32 個(gè) bit 的空間，大小約為 512 MB。
一次掃描每一個(gè)數(shù)，檢測(cè)以該數(shù)為索引的那個(gè) bit 是否為 0 ，若為 0 ，則說(shuō)明過(guò)去不存在，將其置為 1，如果為 1 則說(shuō)明以前出現(xiàn)過(guò)，則說(shuō)明該數(shù)是重復(fù)出現(xiàn)的。
這個(gè)問(wèn)題解決的關(guān)鍵在于用待檢測(cè)數(shù)去做索引，利用隨即存取的特點(diǎn)，可以做到 O(1) 的效率。用數(shù)本身做索引是一種高效的方法。
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 }
關(guān)鍵在于這個(gè)位圖如何實(shí)現(xiàn)。STL 中有個(gè) bitset 就好可以做這個(gè)工作。
但是如果需要仔細(xì)實(shí)現(xiàn)一個(gè)該如何辦？也就是說(shuō)自己實(shí)現(xiàn)一個(gè) bitset
實(shí)現(xiàn)一個(gè)類似的 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
更進(jìn)一步學(xué)習(xí) bitset ，《STL 源碼剖析》中應(yīng)該有所介紹
關(guān)鍵是對(duì) bit 的讀寫(xiě)如何操作。
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 }