http://blog.csdn.net/v_JULY_v一個(gè)算法的博客
幾個(gè)算法題目
1.
實(shí)現(xiàn)過程中參考了網(wǎng)上別人的博客，主要思想是利用一個(gè)輔助棧記錄 min 的索引。
1 #include <iostream>
2 #include <ctime>
3 #include <cassert>
4 using namespace std;
5
6 class MinStack
7 {
8 private:
9 int stack[100];
10 int p;
11 int minstack[100];
12 int q;
13 public:
14 MinStack() : p(0), q(0) {}
15 bool empty()
16 {
17 return p == 0;
18 }
19 bool minEmpty()
20 {
21 return q == 0;
22 }
23 void push(int i)
24 {
25 stack[p++] = i;
26 if (minEmpty())
27 {
28 minstack[q++] = p - 1;
29 }
30 else
31 {
32 if (i <= stack[minTop()])
33 {
34 minstack[q++] = p - 1;
35 }
36 }
37 }
38 void pop()
39 {
40 assert(!empty());
41 if (top() == stack[minTop()])
42 {
43 minPop();
44 }
45 --p;
46 }
47 int min()
48 {
49 assert(!empty());
50 return stack[minTop()];
51 }
52 void minPop()
53 {
54 assert(!minEmpty());
55 --q;
56 }
57 int top()
58 {
59 assert(!empty());
60 return stack[p - 1];
61 }
62 int minTop()
63 {
64 assert(!minEmpty());
65 return minstack[q - 1];
66 }
67 };
68
69 int main()
70 {
71 MinStack ms;
72 srand(time(0));
73 for (int i = 0; i < 10; ++i)
74 {
75 int n = rand() % 100;
76 ms.push(n);
77 }
78 while (!ms.empty())
79 {
80 cout << ms.top() << '\t' << ms.min() << endl;
81 ms.pop();
82 }
83 return 0;
84 }
2.
1 /*
2 *
3 *先統(tǒng)計(jì)所有查詢的次數(shù)，所有查詢有 300 萬個(gè)，255 * 300 * 10000B = 765 MB，可以存入內(nèi)存。這里使用 STL 中的 map。所得時(shí)間復(fù)雜度為 O(NlogM)，N 為所有的查詢，包括重復(fù)的，M 為不重復(fù)的查詢。更好的方法是用散列。
4 *
5 *然后遍歷 map，維護(hù)一個(gè)大小為 10 的集合，在遍歷 map 時(shí)，比較當(dāng)前查詢的出現(xiàn)次數(shù)與集合中出現(xiàn)次數(shù)最小的查詢的出現(xiàn)此時(shí)比較，如果大于，將當(dāng)前查詢替換到集合中。
6 *這里的集合還是用的 map，時(shí)間復(fù)雜度為 O（MlogK），這里 K = 10。
7 *
8 */
9
10 #include <iostream>
11 #include <fstream>
12 #include <map>
13 #include <string>
14 using namespace std;
15
16 void statistics(map<string, int>& data, const string& query)
17 {
18 ++data[query];
19 }
20
21 void findTopK(multimap<int, string>& topK, int k, const map<string, int>& data)
22 {
23 topK.clear();
24 for (map<string, int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
25 {
26 if (topK.size() < k)
27 {
28 topK.insert(make_pair(cit->second, cit->first));
29 }
30 else
31 {
32 if (cit->second > topK.begin()->first)
33 {
34 topK.erase(topK.begin());
35 topK.insert(make_pair(cit->second, cit->first));
36 }
37 }
38 }
39 }
40
41 int main()
42 {
43 ifstream fin("queryfile.txt");
44 map<string, int> data;
45 multimap<int, string> top10;
46 string query;
47 while (getline(fin, query))
48 {
49 statistics(data, query);
50 }
51 findTopK(top10, 10, data);
52 for (multimap<int, string>::const_reverse_iterator cit = top10.rbegin(); cit != top10.rend(); ++cit)
53 {
54 cout << cit->second << '\t' << cit->first << endl;
55 }
56
57 return 0;
58 }
3.
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 char solve(const string& s)
6 {
7 static int times[26] = {0};
8 memset(times, 0, sizeof (times));
9 for (size_t i = 0; i < s.size(); ++i)
10 {
11 ++times[s[i] - 'a'];
12 }
13 for (size_t i = 0; i < s.size(); ++i)
14 {
15 if (times[s[i] - 'a'] == 1)
16 {
17 return s[i];
18 }
19 }
20 return 0;
21 }
22
23 int main()
24 {
25 string s = "abaccdeff";
26 cout << solve(s) << endl;
27 return 0;
28 }
posted on 2011-06-25 16:44
unixfy 閱讀(90)
評(píng)論(0) 編輯 收藏 引用