二分查找的變形
傳統的二分查找
數組時有序的，要么升序要么降序，這里不考慮重復元素出現的情況。
int foo(int a[], int n, int item)
{
int left = 0, right = n - 1;
int middle = 0;
while (left <= right)
{
middle = (left + right) / 2;
if (item > a[middle])
{
left = middle + 1;
}
else if (item < a[middle])
{
right = middle - 1;
}
else
{
return middle;
}
}
return -1;
}
二分查找的變形
給定一個數組 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
如果對該數組調整為
{6, 7, 8, 9, 10, 1, 2, 3, 4, 5}
調整后即是兩個連續有序序列，只不過整體不有序
還是用二分策略，但是具體細節需要改進
整體結構還是一樣的
具體補充的是當待查找元素與中間元素不相等時，
如果小于，還要檢測 item 與 a[left] 的大小關系
如果大于，還要檢測 item 與 a[right] 的大小關系
int bar(int a[], int n, int item)
{
int left = 0, right = n - 1;
int middle = 0;
while (left <= right)
{
middle = (left + right) / 2;
if (item < a[middle])
{
if (a[left] < item)
{
right = middle - 1;
}
else if (a[left] > item)
{
left = middle + 1;
}
else
{
return left;
}
// right = middle - 1;
}
else if (item > a[middle])
{
if (a[right] > item)
{
left = middle + 1;
}
else if (a[right] < item)
{
right = middle - 1;
}
else
{
return right;
}
}
else
{
return middle;
}
}
return -1;
}
1 #include <iostream>
2 using namespace std;
3
4 int foo(int a[], int n, int item)
5 {
6 int left = 0, right = n - 1;
7 int middle = 0;
8 while (left <= right)
9 {
10 middle = (left + right) / 2;
11 if (item > a[middle])
12 {
13 left = middle + 1;
14 }
15 else if (item < a[middle])
16 {
17 right = middle - 1;
18 }
19 else
20 {
21 return middle;
22
23 }
24 }
25 return -1;
26 }
27
28 int bar(int a[], int n, int item)
29 {
30 int left = 0, right = n - 1;
31 int middle = 0;
32 while (left <= right)
33 {
34 middle = (left + right) / 2;
35 if (item < a[middle])
36 {
37 if (a[left] < item)
38 {
39 right = middle - 1;
40 }
41 else if (a[left] > item)
42 {
43 left = middle + 1;
44 }
45 else
46 {
47 return left;
48 }
49 // right = middle - 1;
50 }
51 else if (item > a[middle])
52 {
53 if (a[right] > item)
54 {
55 left = middle + 1;
56 }
57 else if (a[right] < item)
58 {
59 right = middle - 1;
60 }
61 else
62 {
63 return right;
64 }
65 }
66 else
67 {
68 return middle;
69 }
70 }
71 return -1;
72 }
73
74 int main()
75 {
76 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
77 cout << foo(a, sizeof (a) / sizeof (*a), 3) << endl;
78 int b[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5};
79 cout << bar(b, sizeof (b) / sizeof (*b), 5) << endl;
80 return 0;
81 }
實現：
posted @
2011-10-29 00:04 unixfy 閱讀(189) |
評論 (0) |
編輯 收藏不同組的組合
有 N 個組，每個組中有不定個元素，從每個組中選擇一個元素，例如：
第一組 1 2
第二組 3 4
第三組 5
結果為：
1 3 5
1 4 5
2 3 5
2 4 5
http://topic.csdn.net/u/20100313/23/51e49d61-8a36-47f5-8e3b-20477dafde55.html
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 using namespace std;
5
6 void foo(vector<vector<string> >& result, vector<string>& temp, const vector<vector<string> >& vvs, size_t m)
7 {
8 if (temp.size() >= vvs.size())
9 {
10 result.push_back(temp);
11 for (size_t i = 0; i != temp.size(); ++i)
12 {
13 cout << temp[i] << ' ';
14 }
15 cout << endl;
16 }
17 else
18 {
19 for (size_t i = 0; i != vvs[m].size(); ++i)
20 {
21 temp.push_back(vvs[m][i]);
22 foo(result, temp, vvs, m + 1);
23 temp.pop_back();
24 }
25 }
26 }
27
28 void bar(vector<vector<string> >& result, const vector<vector<string> >& vvs)
29 {
30 vector<string> temp;
31 foo(result, temp, vvs, 0);
32 }
33
34 int main()
35 {
36 vector<vector<string> > vvs;
37 vector<string> vs;
38 vs.push_back("A1");
39 vs.push_back("A2");
40 vvs.push_back(vs);
41 vs.clear();
42 vs.push_back("B1");
43 vs.push_back("B2");
44 vvs.push_back(vs);
45 vs.clear();
46 vs.push_back("C1");
47 vs.push_back("C2");
48 vs.push_back("C3");
49 vvs.push_back(vs);
50 vs.clear();
51 for (size_t i = 0; i != vvs.size(); ++i)
52 {
53 for (size_t j = 0; j != vvs[i].size(); ++j)
54 {
55 cout << vvs[i][j] << ' ';
56 }
57 cout << endl;
58 }
59 cout << endl;
60 vector<vector<string> > result;
61 bar(result, vvs);
62 cout << endl;
63 for (size_t i = 0; i != result.size(); ++i)
64 {
65 for (size_t j = 0; j != result[i].size(); ++j)
66 {
67 cout << result[i][j] << ' ';
68 }
69 cout << endl;
70 }
71 return 0;
72 }
posted @
2011-10-06 13:23 unixfy 閱讀(179) |
評論 (0) |
編輯 收藏從 n 個數種選出 m 個數，隨機
思路來源于《編程珠璣》和 TAOCP
問題來源：http://topic.csdn.net/u/20110920/20/94c9eba8-ccdf-44eb-b9bc-f2707ca78c99.html
http://hi.baidu.com/unixfy/blog/item/f064063266f1cdc9a3cc2b81.html
解法：
for (int i = 0; i != n; ++i)
{
if (rand() % (n - i) < m)
{
printf("%d ", a[i]);
--m;
}
}
重點在于該循環。
遍歷整個 n 個元素的數組，隨機生成一個數，這個數為 0 - (n - i) 之間，判斷其是否小于 m
i 每次循環自加，所以說對于最大的數只有 m / n 幾率被選中，如果前面 n - m 次都沒有選中元素，那么在 n - m + 1 次就必須選中一個元素，幾率是 100% 的，后面的也是 100%。
選中一個元素則 m 自減，對剩下的 n - i 個元素還有 m - j 個元素需要選擇。每個元素被選中的概率是一樣的即 m / n, 不被選中的概率也是一樣的，即 (n - m) / n 。
一個循環 O(N) 的時間復雜度。
1 #include <stdio.h>
2 #include <time.h>
3 #include <stdlib.h>
4
5 void foo(int a[], int n, int m)
6 {
7 srand(time(0));
8 for (int i = 0; i != n; ++i)
9 {
10 if (rand() % (n - i) < m)
11 {
12 printf("%d ", a[i]);
13 --m;
14 }
15 }
16 printf("\n");
17 }
18
19 int main()
20 {
21 int a[35];
22 for (int i = 0; i != 35; ++i)
23 {
24 a[i] = i;
25 }
26 foo(a, 35, 8);
27 return 0;
28 }
posted @
2011-09-22 23:48 unixfy 閱讀(1517) |
評論 (1) |
編輯 收藏排列與組合
問題描述：
對一個字符串，求出其所有的全排列情況和所有的組合情況。
例如字符串 abc
其所有的全排列是 abc, acb, bac, bca, cab, cba
其所有的組合是：a, b, c, ab, ac, bc, abc
全排列：
固定前面的元素，對后面的進行遞歸求解，求解后，恢復之前的狀態，并將后面的元素與前面的進行交換。
代碼描述：
void Permutation(char* pStr, char* pBegin);
void Permutation(char* pStr)
{
Permutation(pStr, pStr);
}
void Permutation(char* pStr, char* pBegin)
{
if(!pStr || !pBegin)
return;
if(*pBegin == '\0')
{
printf("%s\n", pStr);
}
else
{
for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
{
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
組合：
對于組合，也是從頭掃描字符串的第一個元素，按照數學上的公式，對于第一個元素有兩種選擇，一是取該元素，然后再剩下來的 n - 1 個元素中取 m - 1 個；而是不去該元素，然后在 n - 1 個元素中取 m 個元素。
C(m, n) = C(m - 1, n - 1) + C(m, n - 1)
這兩種選擇都可以進一步遞歸求解。
代碼描述：
void Combination(char* string)
{
if(string == NULL)
return;
int length = strlen(string);
vector<char> result;
for(int i = 1; i <= length; ++ i)
{
Combination(string, i, result);
}
}
void Combination(char* string, int number, vector<char>& result)
{
if(number == 0)
{
vector<char>::iterator iter = result.begin();
for(; iter < result.end(); ++ iter)
printf("%c", *iter);
printf("\n");
return;
}
if(*string == '\0')
return;
result.push_back(*string);
Combination(string + 1, number - 1, result);
result.pop_back();
Combination(string + 1, number, result);
}
參考：
字符串的排列
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
字符串的組合
http://zhedahht.blog.163.com/blog/static/2541117420114172812217/
posted @
2011-09-17 09:54 unixfy 閱讀(123) |
評論 (0) |
編輯 收藏程序員面試題精選
全部內容來自
浙大何海濤老師的博客 http://zhedahht.blog.163.com/
主要內容是數據結構、算法、C++、C#
程序員面試精選-何海濤-PDF
http://download.csdn.net/detail/goonyangxiaofang/3576580
posted @
2011-09-14 13:15 unixfy 閱讀(152) |
評論 (0) |
編輯 收藏單鏈表的訪問改進
我們知道單鏈表的插入和刪除的時間復雜度是 O(1)
但是其訪問的時間復雜度是 O(N)，不能實現隨機訪問。
而順序表是隨機訪問的，插入和刪除的時間復雜度是 O(N)
針對單鏈表的訪問弊端，如何改進單鏈表數據結構，使得訪問的效率有所提升？
每種數據結構都有各自的優劣以及適用情況。
這里有幾種方案，其實不能算在方案吧，而是采用其他數據結構替換的策略。
第一種方案
采用平衡二叉樹，插入、刪除、訪問的復雜度都是 O(logN)
或者紅黑樹，插入、刪除、訪問的時間復雜度都是 O(logN)
STL 中的 set、map 可以完成該功能。
第二種方案
采用分段的策略
針對每個節點的值，根據值進行分段，段數視具體情況而定。
插入和刪除的時間復雜度保持不變，還是 O(1)
訪問的時間復雜度變為 O(N / 段的數目)
這種方式訪問的時間復雜度得到一定的改進，但是是常數級的。
這種策略實質上是哈希。
哈希函數為除法函數。
例如有 0 1 2 3 4 5 6 7 8 9 十個數，可以分為兩段，0 - 4 為第一段，5 - 9 為第二段。
訪問一個數時，首先計算其所在的段，m / 5，得到所在段的首地址，然后去遍歷訪問。
第三種方案
采用線索二叉樹
線索二叉樹將二叉樹線索化，二叉樹可以想鏈表那樣操作。插入和刪除的時間復雜度都是 O(1)。
訪問按照二叉樹的方式，這時二叉樹是平衡二叉樹，訪問的時間復雜度是 O(logN)。
幾種方案的比較
插入和刪除 訪問
單鏈表 O(1) O(N)
平衡二叉樹 O(logN) O(logN)
分段 O(1) O(N / 段的數目)
線索二叉樹 O(1) O(logN)
總結
這幾種方案，與其說是改進，不如說是更換另一種數據結構。
另外哈希方式，最好在存在大量數據的情況下使用，否則會浪費空間，因為哈希表很大。
針對單鏈表訪問效率的改進，另一個角度是采用輔助性數據結構，記錄一些信息，以方便快速地訪問。
posted @
2011-09-13 20:54 unixfy 閱讀(755) |
評論 (0) |
編輯 收藏最長重復子串
問題描述
給定一個字符串，求出其最長重復子串
例如 abcdabcd
最長重復子串是 abcd
最長重復子串可以重疊
例如
abcdabcda
這時最長重復子串是 abcda
中間的 a 是被重疊的。
直觀的解法是，首先檢測長度為 n - 1 的字符串情況，如果不存在重復則檢測 n - 2, 一直遞減下去，直到 1 。
這種方法的時間復雜度是 O(N * N * N)，其中包括三部分，長度緯度、根據長度檢測的字符串數目、字符串檢測。
改進的方法是利用后綴數組
后綴數組是一種數據結構，對一個字符串生成相應的后綴數組后，然后再排序，排完序依次檢測相鄰的兩個字符串的開頭公共部分。
這樣的時間復雜度為：
生成后綴數組 O(N)
排序 O(NlogN*N) 最后面的 N 是因為字符串比較也是 O(N)
依次檢測相鄰的兩個字符串 O(N * N)
總的時間復雜度是 O(N^2*logN), 由于第一種方法的 O(N^3)
后綴數組的實現：
代碼摘自 CSDN 論壇
http://topic.csdn.net/u/20071002/22/896b1597-fc39-466e-85d3-5bef6f7442f6.html
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define MAXCHAR 5000 //最長處理5000個字符
6
7 char c[MAXCHAR], *a[MAXCHAR];
8
9 int comlen( char *p, char *q ){
10 int i = 0;
11 while( *p && (*p++ == *q++) )
12 ++i;
13 return i;
14 }
15
16 int pstrcmp( const void *p1, const void *p2 ){
17 return strcmp( *(char* const *)p1, *(char* const*)p2 );
18 }
19
20 int main( ){
21 char ch;
22 int n=0;
23 int i, temp;
24 int maxlen=0, maxi=0;
25 printf("Please input your string:\n");
26 while( (ch=getchar())!='\n' ){
27 a[n]=&c[n];
28 c[n++]=ch;
29 }
30 c[n]='\0';
31 qsort( a, n, sizeof(char*), pstrcmp );
32 for(i=0; i<n-1; ++i ){
33 temp=comlen( a[i], a[i+1] );
34 if( temp>maxlen ){
35 maxlen=temp;
36 maxi=i;
37 }
38 }
39 printf("%.*s\n",maxlen, a[maxi]);
40 system("PAUSE");
41 return 0;
42 }
參考：
http://topic.csdn.net/u/20071002/22/896b1597-fc39-466e-85d3-5bef6f7442f6.htmlhttp://blog.csdn.net/kongming_acm/article/details/6232439http://blog.sina.com.cn/s/blog_5133d4dd0100a4qd.htmlhttp://www.programbbs.com/bbs/view35-20014-1.htmhttp://hi.baidu.com/fangm/blog/item/58fd1a4c20a5eafdd72afcd0.htmlhttp://www.cnblogs.com/dyh333/articles/1801714.htmlhttp://www.byvoid.com/blog/tag/%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E4%B8%B2/http://www.shnenglu.com/Joe/archive/2011/08/19/153851.html
posted @
2011-09-13 16:01 unixfy 閱讀(7832) |
評論 (0) |
編輯 收藏兩個指針的作用
兩個指針一般用在一個序列中。
在一個序列中處理問題時，如果只使用一個指針，可能會造成雙重循環的問題，結果時間復雜度會是 O(N) 。
如果采用兩個指針可以很好地解決問題，時間復雜度也可以得到改進。
采用兩個指針的例子很多，這里舉幾個：
1.
自動文摘中，如果采用循環查找的方法，時間復雜度是冪次方。采用兩個指針，分別指向文摘的開始處和結束處可以在 O(N) 的時間復雜度內找到文摘。
2.
求連續數字之和等于一給定數，例如給定數是 15 ，則結果有 1 2 3 4 5、4 5 6、7 8 三種結果。
如果采用循環的方法事件復雜度是 O(N^2)
可以采用兩個指針，分別指向 small 和 big 。當 sum(small ... big) 大于給定數時，small 指針右移，當 sum 小于給定數時，big 指針右移。直到 small 是給定數的一半時。
3.
調整數組，是前半部分是某種類型的數，后半部分是某種類型的數。
比如前半部分是奇數，后半部分是偶數
前半部分是負數，后半部分是非負數
采用兩個指針，分別從左右兩端進行掃描，檢測，如果符合條件則交換兩數，直到兩個指針交叉為止。
4.
求一個數組中兩個數的和等于一定數。
先對數組排序
然后從數組兩端用兩個指針掃描，檢測，直到兩個指針交叉為止。
當一個指針無法很好解決問題時，應該再增添一個指針，多一個幫手。
posted @
2011-09-13 13:12 unixfy 閱讀(206) |
評論 (0) |
編輯 收藏全排列
遞歸實現
·與第一個交換
·遞歸
*pch 與 *begin 之間的交換與復原
for (char* pch = pbegin; *pch != '\0'; ++pch)
{
char temp = *pch;
*pch = *pbegin;
*pbegin = temp;
permutation(pstr, pbegin + 1);
temp = *pch;
*pch = *pbegin;
*pbegin = temp;
}
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
1 #include <iostream>
2 using namespace std;
3
4 void permutation(char* pstr, char* pbegin)
5 {
6 if (pstr == 0 || pbegin == 0)
7 {
8 return;
9 }
10 if (*pbegin == '\0')
11 {
12 cout << pstr << endl;
13 }
14 else
15 {
16 for (char* pch = pbegin; *pch != '\0'; ++pch)
17 {
18 char temp = *pch;
19 *pch = *pbegin;
20 *pbegin = temp;
21
22 permutation(pstr, pbegin + 1);
23
24 temp = *pch;
25 *pch = *pbegin;
26 *pbegin = temp;
27 }
28 }
29 }
30
31 void perm(char* str)
32 {
33 permutation(str, str);
34 }
35
36 int main()
37 {
38 char s[4] = "abc";
39 perm(s);
40 }
posted @
2011-09-13 13:00 unixfy 閱讀(93) |
評論 (0) |
編輯 收藏二叉樹的深度
二叉樹的遞歸簡歷
二叉樹的遞歸前序遍歷
二叉樹的遞歸深度求解
示例：
10
6
4
0
0
0
14
12
0
0
16
0
0
10 6 4 14 12 16
3
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int value;
7 node* left;
8 node* right;
9 };
10
11 void create(node*& btree)
12 {
13 int n;
14 cin >> n;
15 if (n == 0)
16 {
17 btree = 0;
18 }
19 else
20 {
21 btree = new node;
22 btree->value = n;
23 create(btree->left);
24 create(btree->right);
25 }
26 }
27
28 void preOrder(node* btree)
29 {
30 if (btree != 0)
31 {
32 cout << btree->value << ' ';
33 preOrder(btree->left);
34 preOrder(btree->right);
35 }
36 }
37
38 int depth(node* btree)
39 {
40 if (btree == 0)
41 {
42 return 0;
43 }
44 else
45 {
46 int left = depth(btree->left);
47 int right = depth(btree->right);
48 return left > right ? left + 1 : right + 1;
49 }
50 }
51
52 int main()
53 {
54 node* btree;
55 create(btree);
56 preOrder(btree);
57 cout << endl;
58 cout << depth(btree) << endl;
59 }
posted @
2011-09-13 12:41 unixfy 閱讀(176) |
評論 (0) |
編輯 收藏