二分查找的变形
传统的二分查找
数组时有序的，要么升序要么降序，这里不考虑重复元素出现的情况。
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 阅读(175) |
评论 (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 阅读(165) |
评论 (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 阅读(1492) |
评论 (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 阅读(111) |
评论 (0) |
编辑 收藏程序员面试题精选
全部内容来自
浙大何海涛老师的博客 http://zhedahht.blog.163.com/
主要内容是数据结构、算法、C++、C#
程序员面试精选-何海涛-PDF
http://download.csdn.net/detail/goonyangxiaofang/3576580
posted @
2011-09-14 13:15 unixfy 阅读(136) |
评论 (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 阅读(737) |
评论 (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.cppblog.com/Joe/archive/2011/08/19/153851.html
posted @
2011-09-13 16:01 unixfy 阅读(7799) |
评论 (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 阅读(194) |
评论 (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 阅读(84) |
评论 (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 阅读(160) |
评论 (0) |
编辑 收藏