http://blog.csdn.net/v_JULY_v一个算法的博客
几个算法题目
1.
实现过程中参考了网上别人的博客，主要思想是利用一个辅助栈记录 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 *先统计所有查询的次数，所有查询有 300 万个，255 * 300 * 10000B = 765 MB，可以存入内存。这里使用 STL 中的 map。所得时间复杂度为 O(NlogM)，N 为所有的查询，包括重复的，M 为不重复的查询。更好的方法是用散列。
4 *
5 *然后遍历 map，维护一个大小为 10 的集合，在遍历 map 时，比较当前查询的出现次数与集合中出现次数最小的查询的出现此时比较，如果大于，将当前查询替换到集合中。
6 *这里的集合还是用的 map，时间复杂度为 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 阅读(77)
评论(0) 编辑 收藏 引用