在學(xué)習(xí)設(shè)計模式期間，用 C++ 程序語言將 24 個設(shè)計模式實(shí)現(xiàn)了一遍，中間有些錯誤，留待以后改正。
參考文獻(xiàn)有：
《大話設(shè)計模式》
《設(shè)計模式：可復(fù)用面向?qū)ο筌浖幕A(chǔ)》
Wikipedia
下載地址：
http://download.csdn.net/source/3308757
posted @
2011-05-24 17:28 unixfy 閱讀(124) |
評論 (0) |
編輯 收藏
這里沒有什么，只是想補(bǔ)充完整。
MVC 模式（Model-View-Controller）
軟件工程中的一種軟件架構(gòu)模式，把軟件系統(tǒng)分為三個基本部分：
·模型（Model）
·視圖（View）
·控制器（Controller）
控制器：負(fù)責(zé)轉(zhuǎn)發(fā)請求，對請求進(jìn)行處理。
視 圖：界面設(shè)計人員進(jìn)行圖形界面設(shè)計。
模 型：程序員編寫程序應(yīng)用的功能（實(shí)現(xiàn)算法等）、數(shù)據(jù)庫專家進(jìn)行數(shù)據(jù)管理和數(shù)據(jù)庫設(shè)計（可以實(shí)現(xiàn)具體的功能）。
實(shí)現(xiàn)：
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 閱讀(233) |
評論 (0) |
編輯 收藏
摘要: 實(shí)現(xiàn)一個雙索引容器基于雙索引實(shí)現(xiàn)一個具有插入、查找、刪除的容器，一個索引是 int 類型的，一個索引是自定義結(jié)構(gòu)體類型的。這個問題來自于網(wǎng)宿筆試的一個題目。這里的功能已基本實(shí)現(xiàn)，支持雙索引，自定義結(jié)構(gòu)體類型是有兩個 int 型元素的結(jié)構(gòu)體。支持迭代器，但是不支持模板。實(shí)現(xiàn)如下：
Code highlighting produced by Actipro CodeHighlighter (free...
閱讀全文
posted @
2011-05-23 23:48 unixfy 閱讀(497) |
評論 (0) |
編輯 收藏
利用后綴數(shù)組求解該問題。
首先用后綴數(shù)組拆分字符串，然后對后綴數(shù)組排序，在對后綴數(shù)組一次遍歷，計算相鄰的兩個字符串，從頭開始的最大公共子串。
實(shí)現(xiàn)：
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 閱讀(591) |
評論 (0) |
編輯 收藏
int 中連續(xù) 1 的個數(shù)，并且求左右邊界。
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 閱讀(148) |
評論 (0) |
編輯 收藏
求出現(xiàn)次數(shù)大于一半的數(shù)
在網(wǎng)上查了一下，這個題目大概有這幾種做法：
一，用 map 計數(shù)，但是沒有利用次數(shù)大于一半的特點(diǎn)，時間復(fù)雜度其實(shí)不是 O(N)，因?yàn)?map 也要計算，時間復(fù)雜度應(yīng)該是 O(N^logN)。
二，遍歷數(shù)組，元素兩兩比較，如果兩個數(shù)相同，則刪除一個，如果兩個數(shù)不同，則都刪除。這種方法的正確性我還沒有證明。但是有一點(diǎn)是如果不存在次數(shù)大于一半的數(shù)，找到的結(jié)果肯定是錯誤的。這種方法是時間復(fù)雜度是 O(N)
三，還是遍歷數(shù)組，這里用兩個遍歷 A 和 B 做記錄工作。B 初始化 0，掃描整個數(shù)組，當(dāng) B == 0 時，A 等于當(dāng)前數(shù)；如果當(dāng)前數(shù)與 A 相同，則 ++B，如果與 A 不同，則 --A。遍歷結(jié)束時，A 就是結(jié)果。時間復(fù)雜度是 O(N)。但是當(dāng)數(shù)組中不存在次數(shù)大于一半的數(shù)時，這種方法找到的數(shù)還是不是正確的。
不過綜合起來看，如果默認(rèn)一定存在出現(xiàn)次數(shù)大于一半的數(shù)，那么第三種方法是最好的，思路清晰，實(shí)現(xiàn)簡單。
下面是對第三種方法的實(shí)現(xià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 閱讀(222) |
評論 (0) |
編輯 收藏
連續(xù)遞增最長子串，其做法與最大連續(xù)子串差不多。逐個掃描，記錄最長子串的長度和邊界。
這里的遞增有兩種方式，一是只要后一個元素比前一個元素大于或等于即可。
第二種方式是，后一個元素必須比前一個元素大于 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 閱讀(436) |
評論 (0) |
編輯 收藏
下午網(wǎng)宿的一個面試題目，當(dāng)時沒有答好。先分析如下：
刪除 vector 中大于 n 的數(shù)，注意 vector 中并不一定存在 n + 1
最簡單的做法是循環(huán)，逐個掃描，到檢查到有大于 n 的元素時，移動后面的元素。這里有另種掃描方式，分別是從左到右和從右到左。
從右到左的方式效率更高，因?yàn)楸苊饬艘苿悠渌笥?n 的元素。但是兩種方式的時間復(fù)雜度都是 O(N ^ 2)。
可以通過先排序然后找到第一個大于 n 的元素的迭代器，然后刪除該迭代器到最后一個元素之間的元素。
但是這種方法改變原來小于等于 n 的元素之間的相對順序。
查找第一個大于 n 的元素的迭代器是先要排序，然后查找。
查找的方法有，直接循環(huán)遍歷查找。也可以傳一個函數(shù)，用 find_if。也可以用函數(shù)對象，函數(shù)對象的函數(shù)時你可以自己設(shè)定想要的參數(shù)，還是用 find_if 查找。
這種方法的時間復(fù)雜度是 O(NlogN)。
第三種方法是利用 remove_if 函數(shù)，但是 remove_if 函數(shù)不會真的刪除元素，需要借助于 erase 函數(shù)。但是 remove_if 操作的效率和第一種是一樣的，時間復(fù)雜度還是 O(N^2)。
實(shí)現(xiàn)：
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 閱讀(1276) |
評論 (0) |
編輯 收藏
一般面試中會有這個題目，交換兩個變量的值，不需要其他變量。
首先是最常見的交換變量的方法是
void swap(int& a, int& b)
{
int t = a;
a = b;
b = a;
}
這里借助了輔助變量 t。
另一種方法是利用算數(shù)運(yùn)算
void swap(int& a, int &b)
{
a += b;
b = a - b;
a = a - b;
}
但是這種方法要考慮越界的可能，a + b 有可能越界，如果發(fā)生這種情況，這種方法就不行了。
第三種方法是利用異或運(yùn)算
異或運(yùn)算的原理就是 0 保持，1 取反。
void swap(int& a, int& b)
{
a ^= b;
b ^= a;
a ^= b;
}
這種方法直接進(jìn)行為運(yùn)算，不用考慮是否越界的問題。但是要考慮 a 和 b 是否是同一個變量，如果是同一個變量，則最終的結(jié)果是 a = b = 0。
這就達(dá)不到我們想要的交換操作了。所以這種方法應(yīng)該加一個檢測。
void swap(int& a, int& b)
{
if (&a == &b)
{
return;
}
a ^= b;
b ^= a;
a ^= b;
}
另外，只要 a 和 b 不是同一個變量即可實(shí)現(xiàn)交換，a = b 也不例外。
除此之外，如果 a 和 b 的字節(jié)數(shù)不一致，則只會交換第字節(jié)位的數(shù)值，高字節(jié)位的數(shù)值保持不變。
posted @
2011-05-19 14:43 unixfy 閱讀(195) |
評論 (0) |
編輯 收藏將一個 int 型的數(shù)按位輸出。進(jìn)行循環(huán)移位，檢測最左邊的位是否非零，然后輸出 1 或 0 即可。
對 int 型的數(shù)中的位進(jìn)行逆序?？紤]逆序的特征，可以利用棧進(jìn)行逆序，從左往右進(jìn)行壓棧，彈出的時候 ret = 2 * ret + s.top();
如果從右往左壓棧，在彈出棧的時候，有個記錄項(xiàng) m = 0；ret = ret + pow(2, m++)。
也可以采用另一種方式在原地逆序，循環(huán)這個位。對左右兩邊的對稱位進(jìn)行檢測，設(shè)置各自的掩碼。如果左右兩邊的位不一致，則相互設(shè)置相反。
為的逆序來自一思科面試題。
實(shí)現(xiàn)：
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4
5 // 輸入一個 int 數(shù)的二進(jìn)制位
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 // 這里使用一個棧來實(shí)現(xiàn)逆序
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 // 第二種實(shí)現(xiàn)方式
52 // 直接在原地交換，設(shè)置掩碼
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 閱讀(586) |
評論 (0) |
編輯 收藏