在学习设计模式期间，用 C++ 程序语言将 24 个设计模式实现了一遍，中间有些错误，留待以后改正。
参考文献有：
《大话设计模式》
《设计模式：可复用面向对象软件的基础》
Wikipedia
下载地址：
http://download.csdn.net/source/3308757
posted @
2011-05-24 17:28 unixfy 阅读(102) |
评论 (0) |
编辑 收藏
这里没有什么，只是想补充完整。
MVC 模式（Model-View-Controller）
软件工程中的一种软件架构模式，把软件系统分为三个基本部分：
·模型（Model）
·视图（View）
·控制器（Controller）
控制器：负责转发请求，对请求进行处理。
视 图：界面设计人员进行图形界面设计。
模 型：程序员编写程序应用的功能（实现算法等）、数据库专家进行数据管理和数据库设计（可以实现具体的功能）。
实现：
MFC
Java J2EE
.NET
http://zh.wikipedia.org/wiki/MVC
http://baike.baidu.com/view/31.htm
http://zh.wikipedia.org/wiki/Category:%E8%BD%AF%E4%BB%B6%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F
posted @
2011-05-24 16:48 unixfy 阅读(203) |
评论 (0) |
编辑 收藏
摘要: 实现一个双索引容器基于双索引实现一个具有插入、查找、删除的容器，一个索引是 int 类型的，一个索引是自定义结构体类型的。这个问题来自于网宿笔试的一个题目。这里的功能已基本实现，支持双索引，自定义结构体类型是有两个 int 型元素的结构体。支持迭代器，但是不支持模板。实现如下：
Code highlighting produced by Actipro CodeHighlighter (free...
阅读全文
posted @
2011-05-23 23:48 unixfy 阅读(440) |
评论 (0) |
编辑 收藏
利用后缀数组求解该问题。
首先用后缀数组拆分字符串，然后对后缀数组排序，在对后缀数组一次遍历，计算相邻的两个字符串，从头开始的最大公共子串。
实现：
1 #include <iostream>
2 using namespace std;
3
4 const int MAXN = 1000;
5
6 int mycmp(const void* p1, const void* p2)
7 {
8 return strcmp(*(char* const*)p1, *(char* const*)p2);
9 }
10
11 int getLen(char* p, char* q)
12 {
13 int ret = 0;
14 while (*p && *p++ == *q++)
15 {
16 ++ret;
17 }
18 return ret;
19 }
20
21 char* foo(char result[], char s[])
22 {
23 int len = strlen(s);
24 char** suffix = new char*[len];
25 for (int i = 0; i < len; ++i)
26 {
27 suffix[i] = s + i;
28 }
29 qsort(suffix, len, sizeof (char*), mycmp);
30 //for (int i = 0; i < len; ++i)
31 //{
32 // cout << suffix[i] << endl;
33 //}
34 int maxlen = 0, maxi = 0, maxj = 0, temp = 0;
35 for (int i = 0; i < len - 1; ++i)
36 {
37 temp = getLen(suffix[i], suffix[i + 1]);
38 if (temp > maxlen)
39 {
40 maxlen = temp;
41 maxi = i;
42 maxj = i + 1;
43 }
44 }
45 //cout << maxlen << endl;
46 //cout << suffix[maxi] << endl;
47 //cout << suffix[maxj] << endl;
48 //printf("%.*s\n", maxlen, suffix[maxi]);
49 for (int i = 0; i < maxlen; ++i)
50 {
51 result[i] = suffix[maxi][i];
52 }
53 result[maxlen] = '\0';
54 return result;
55 }
56
57 int main()
58 {
59 char s[MAXN];
60 char result[MAXN];
61 while (cin >> s)
62 {
63 cout << foo(result, s) << endl;
64 }
65 return 0;
66 }
http://hi.baidu.com/prettydidy/blog/item/84bf6a37afd3ef1c90ef399f.htmlhttp://blog.csdn.net/baiwen1979/archive/2008/03/24/2212147.aspxhttp://ds.fzu.edu.cn/fine/resources/http://ds.fzu.edu.cn/fine/acm/index.asp
posted @
2011-05-23 18:27 unixfy 阅读(555) |
评论 (0) |
编辑 收藏
int 中连续 1 的个数，并且求左右边界。
1 #include <iostream>
2 using namespace std;
3
4 int foo(int n, int& l, int& r)
5 {
6 int ret = 0, now = 0;
7 int l2, r2;
8 r2 = 0;
9 l2 = -1;
10 l = r = l2;
11 int idx = 0;
12 while (n != 0)
13 {
14 if (n % 2 != 0)
15 {
16 ++now;
17 l2 = idx;
18 if (now == 1)
19 {
20 r2 = idx;
21 }
22 }
23 else
24 {
25 now = 0;
26 }
27 if (now > ret)
28 {
29 ret = now;
30 l = l2;
31 r = r2;
32 }
33 ++idx;
34 n /= 2;
35 }
36 return ret;
37 }
38
39 int main()
40 {
41 int n;
42 while (cin >> n)
43 {
44 int ret, l, r;
45 ret = foo(n, l, r);
46 cout << ret << ' ' << r << ' ' << l << endl;
47 }
48 return 0;
49 }
posted @
2011-05-21 11:30 unixfy 阅读(132) |
评论 (0) |
编辑 收藏
求出现次数大于一半的数
在网上查了一下，这个题目大概有这几种做法：
一，用 map 计数，但是没有利用次数大于一半的特点，时间复杂度其实不是 O(N)，因为 map 也要计算，时间复杂度应该是 O(N^logN)。
二，遍历数组，元素两两比较，如果两个数相同，则删除一个，如果两个数不同，则都删除。这种方法的正确性我还没有证明。但是有一点是如果不存在次数大于一半的数，找到的结果肯定是错误的。这种方法是时间复杂度是 O(N)
三，还是遍历数组，这里用两个遍历 A 和 B 做记录工作。B 初始化 0，扫描整个数组，当 B == 0 时，A 等于当前数；如果当前数与 A 相同，则 ++B，如果与 A 不同，则 --A。遍历结束时，A 就是结果。时间复杂度是 O(N)。但是当数组中不存在次数大于一半的数时，这种方法找到的数还是不是正确的。
不过综合起来看，如果默认一定存在出现次数大于一半的数，那么第三种方法是最好的，思路清晰，实现简单。
下面是对第三种方法的实现：
1 #include <vector>
2 #include <iostream>
3 using namespace std;
4
5 int foo(const vector<int>& data)
6 {
7 int A, B = 0;
8 for (size_t i = 0; i != data.size(); ++i)
9 {
10 if (B == 0)
11 {
12 A = data[i];
13 }
14 if (A == data[i])
15 {
16 ++B;
17 }
18 else
19 {
20 --B;
21 }
22 }
23 return A;
24 }
25
26 int main()
27 {
28 vector<int> data;
29 for (int i = 0; i < 10; ++i)
30 {
31 data.push_back(5);
32 }
33 for (int i = 0; i < 10; ++i)
34 {
35 data.push_back(7);
36 }
37 data.push_back(7);
38 cout << foo(data) << endl;
39 return 0;
40 }
http://hi.baidu.com/mianshiti/blog/item/ac88ddeef9e29c4479f0556c.htmlhttp://blog.csdn.net/cynhafa/archive/2011/04/26/6364604.aspxhttp://blog.csdn.net/kannju/archive/2010/12/21/6090423.aspx
posted @
2011-05-21 11:06 unixfy 阅读(197) |
评论 (0) |
编辑 收藏
连续递增最长子串，其做法与最大连续子串差不多。逐个扫描，记录最长子串的长度和边界。
这里的递增有两种方式，一是只要后一个元素比前一个元素大于或等于即可。
第二种方式是，后一个元素必须比前一个元素大于 1。
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 // 后一个元素大于或等于前一个元素
6 int foo(const string& s, size_t& l, size_t& r)
7 {
8 int ret = 1, now = 1;
9 size_t l2, r2;
10 l2 = r2 = 0;
11 l = r = l2;
12 for (size_t i = 1; i < s.size(); ++i)
13 {
14 if (s[i] >= s[i - 1])
15 {
16 ++now;
17 ++r2;
18 }
19 else
20 {
21 now = 1;
22 l2 = r2 = i;
23 }
24 if (now > ret)
25 {
26 ret = now;
27 l = l2;
28 r = r2;
29 }
30 }
31 return ret;
32 }
33
34 // 后一个元素必须比前一个元素大于 1
35 int bar(const string& s, size_t& l, size_t& r)
36 {
37 int ret = 1, now = 1;
38 size_t l2, r2;
39 l2 = r2 = 0;
40 l = r = l2;
41 for (size_t i = 1; i < s.size(); ++i)
42 {
43 if (s[i] - s[i - 1] == 1)
44 {
45 ++now;
46 ++r2;
47 }
48 else
49 {
50 now = 1;
51 l2 = r2 = i;
52 }
53 if (now > ret)
54 {
55 ret = now;
56 l = l2;
57 r = r2;
58 }
59 }
60 return ret;
61 }
62
63 int main()
64 {
65 string s;
66 while (cin >> s)
67 {
68 size_t l, u;
69 int len = foo(s, l, u);
70 cout << len << endl;
71 while (l <= u)
72 {
73 cout << s[l++] << ' ';
74 }
75 cout << endl;
76
77 len = bar(s, l, u);
78 cout << len << endl;
79 while (l <= u)
80 {
81 cout << s[l++] << ' ';
82 }
83 cout << endl;
84 }
85 return 0;
86 }
posted @
2011-05-21 10:35 unixfy 阅读(420) |
评论 (0) |
编辑 收藏
下午网宿的一个面试题目，当时没有答好。先分析如下：
删除 vector 中大于 n 的数，注意 vector 中并不一定存在 n + 1
最简单的做法是循环，逐个扫描，到检查到有大于 n 的元素时，移动后面的元素。这里有另种扫描方式，分别是从左到右和从右到左。
从右到左的方式效率更高，因为避免了移动其他大于 n 的元素。但是两种方式的时间复杂度都是 O(N ^ 2)。
可以通过先排序然后找到第一个大于 n 的元素的迭代器，然后删除该迭代器到最后一个元素之间的元素。
但是这种方法改变原来小于等于 n 的元素之间的相对顺序。
查找第一个大于 n 的元素的迭代器是先要排序，然后查找。
查找的方法有，直接循环遍历查找。也可以传一个函数，用 find_if。也可以用函数对象，函数对象的函数时你可以自己设定想要的参数，还是用 find_if 查找。
这种方法的时间复杂度是 O(NlogN)。
第三种方法是利用 remove_if 函数，但是 remove_if 函数不会真的删除元素，需要借助于 erase 函数。但是 remove_if 操作的效率和第一种是一样的，时间复杂度还是 O(N^2)。
实现：
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 // 从左向右扫描删除移动
7 void delLeftToRight(vector<int>& data, int n)
8 {
9 for (size_t i = 0; i < data.size(); ++i)
10 {
11 if (data[i] > n)
12 {
13 for (size_t j = i + 1; j < data.size(); ++j)
14 {
15 data[j - 1] = data[j];
16 }
17 data.pop_back();
18 --i;
19 }
20 }
21 }
22
23 // 从右向左扫描删除移动
24 void delRightToLeft(vector<int>& data, int n)
25 {
26 for (size_t i = data.size(); i > 0; --i)
27 {
28 if (data[i - 1] > n)
29 {
30 for (size_t j = i; j < data.size(); ++j)
31 {
32 data[j - 1] = data[j];
33 }
34 data.pop_back();
35 }
36 }
37 }
38
39 // 排序，顺序遍历查找，删除
40 void delSort(vector<int>& data, int n)
41 {
42 sort(data.begin(), data.end());
43 vector<int>::const_iterator cit = data.begin();
44 for (; cit != data.end(); ++cit)
45 {
46 if (*cit > n)
47 {
48 break;
49 }
50 }
51 data.erase(cit, data.end());
52 }
53
54 class biggerN
55 {
56 int m;
57 public:
58 biggerN(int i) : m(i) {}
59 bool operator ()(int n)
60 {
61 return n > m;
62 }
63 };
64
65 bool bigger(int n)
66 {
67 return n > 10;
68 }
69
70 // 排序，查找，删除
71 void delSortFind(vector<int>& data, int n)
72 {
73 sort(data.begin(), data.end());
74 vector<int>::const_iterator cit;
75 cit = find_if(data.begin(), data.end(), biggerN(n));
76 // cit = find_if(data.begin(), data.end(), bigger);
77 data.erase(cit, data.end());
78 }
79
80 // 移动，删除
81 void delRemove(vector<int>& data, int n)
82 {
83 data.erase(remove_if(data.begin(), data.end(), biggerN(n)), data.end());
84 // data.erase(remove(data.begin(), data.end(), 20), data.end());
85 }
86
87 void display(const vector<int>& data)
88 {
89 for (size_t i = 0; i < data.size(); ++i)
90 {
91 cout << data[i] << ' ';
92 }
93 cout << endl;
94 }
95
96 int main()
97 {
98 vector<int> data;
99 for (int i = 20; i > 0; --i)
100 {
101 data.push_back(i);
102 }
103 // data.push_back(20);
104 display(data);
105 // delLeftToRight(data, 10);
106 // delRightToLeft(data, 10);
107 // delSort(data, 10);
108 // delSortFind(data, 10);
109 delRemove(data, 10);
110 display(data);
111 }
posted @
2011-05-21 00:18 unixfy 阅读(1219) |
评论 (0) |
编辑 收藏
一般面试中会有这个题目，交换两个变量的值，不需要其他变量。
首先是最常见的交换变量的方法是
void swap(int& a, int& b)
{
int t = a;
a = b;
b = a;
}
这里借助了辅助变量 t。
另一种方法是利用算数运算
void swap(int& a, int &b)
{
a += b;
b = a - b;
a = a - b;
}
但是这种方法要考虑越界的可能，a + b 有可能越界，如果发生这种情况，这种方法就不行了。
第三种方法是利用异或运算
异或运算的原理就是 0 保持，1 取反。
void swap(int& a, int& b)
{
a ^= b;
b ^= a;
a ^= b;
}
这种方法直接进行为运算，不用考虑是否越界的问题。但是要考虑 a 和 b 是否是同一个变量，如果是同一个变量，则最终的结果是 a = b = 0。
这就达不到我们想要的交换操作了。所以这种方法应该加一个检测。
void swap(int& a, int& b)
{
if (&a == &b)
{
return;
}
a ^= b;
b ^= a;
a ^= b;
}
另外，只要 a 和 b 不是同一个变量即可实现交换，a = b 也不例外。
除此之外，如果 a 和 b 的字节数不一致，则只会交换第字节位的数值，高字节位的数值保持不变。
posted @
2011-05-19 14:43 unixfy 阅读(162) |
评论 (0) |
编辑 收藏将一个 int 型的数按位输出。进行循环移位，检测最左边的位是否非零，然后输出 1 或 0 即可。
对 int 型的数中的位进行逆序。考虑逆序的特征，可以利用栈进行逆序，从左往右进行压栈，弹出的时候 ret = 2 * ret + s.top();
如果从右往左压栈，在弹出栈的时候，有个记录项 m = 0；ret = ret + pow(2, m++)。
也可以采用另一种方式在原地逆序，循环这个位。对左右两边的对称位进行检测，设置各自的掩码。如果左右两边的位不一致，则相互设置相反。
为的逆序来自一思科面试题。
实现：
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4
5 // 输入一个 int 数的二进制位
6 void foo(int n)
7 {
8 static int t = 1 << (sizeof (int) * 8 - 1);
9 for (int i = 0; i < sizeof (n) * 8; ++i)
10 {
11 if ((n & t) == 0)
12 {
13 cout << 0;
14 }
15 else
16 {
17 cout << 1;
18 }
19 n <<= 1;
20 }
21 cout << endl;
22 }
23
24 // 将 int 中的各位逆序
25 // 这里使用一个栈来实现逆序
26 int bar(int* a, int b)
27 {
28 static int t = 1 << (sizeof (int) * 8 - 1);
29 *a = 0;
30 stack<int> s;
31 for (int i = 0; i < sizeof (int) * 8 - 1; ++i)
32 {
33 if ((b & t) == 0)
34 {
35 s.push(0);
36 }
37 else
38 {
39 s.push(1);
40 }
41 b <<= 1;
42 }
43 while (!s.empty())
44 {
45 *a = 2 * (*a) + s.top();
46 s.pop();
47 }
48 return *a;
49 }
50
51 // 第二种实现方式
52 // 直接在原地交换，设置掩码
53 int reverse(int n)
54 {
55 int len = sizeof (int) * 8;
56 int a, b;
57 int t1, t2;
58 // int t = -1;
59 int t = 0;
60 t = (1 << (len - 1)) - 1 + (1 << (len - 1));
61 for (int i = 0; i < len / 2; ++i)
62 {
63 t1 = 1 << (len - i - 1);
64 t2 = 1 << i;
65 a = t1 & n;
66 b = t2 & n;
67 cout << "test" << endl;
68 foo(t1);
69 foo(t2);
70 foo(a);
71 foo(b);
72 foo(t);
73 if (a == 0 && b != 0)
74 {
75 n &= (t - t2);
76 n |= t1;
77 }
78 else if (a != 0 && b == 0)
79 {
80 n &= (t - t1);
81 n |= t2;
82 }
83 foo(n);
84 }
85 return n;
86 }
87
88 int main()
89 {
90 int n = 2; // 2;
91 cout << (n << 1) << endl;
92 cout << (n >> 1) << endl;
93
94 foo(n);
95 foo(-2);
96 foo(1 << (sizeof (int) * 8 - 1));
97
98 n = 2;
99 int m;
100 m = bar(&m, n);
101 foo(n);
102 foo(m);
103
104 n = 7;
105 m = reverse(n);
106 foo(n);
107 foo(m);
108 return 0;
109 }
posted @
2011-05-19 14:14 unixfy 阅读(530) |
评论 (0) |
编辑 收藏