中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
在表達(dá)式計(jì)算中，第一要做的就是講中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
所采用的方式是，掃描中綴表達(dá)式，檢測(cè)每個(gè)中綴表達(dá)式的元素
如果是操作數(shù)，則將其加入到輸出的后綴表達(dá)式中
如果是操作符，需要對(duì)其分析，設(shè)定一個(gè)操作符棧，
·如果一開始操作符棧為空，則將該操作符壓棧
·這里涉及左括號(hào)的兩個(gè)優(yōu)先級(jí)，即棧外優(yōu)先級(jí)和棧內(nèi)優(yōu)先級(jí)，如果左括號(hào)在棧外，則其優(yōu)先級(jí)最高，直接將其壓入到操作符棧中，如果左括號(hào)在棧內(nèi)，則其優(yōu)先級(jí)很低，只有在碰到右括號(hào)的時(shí)候才會(huì)彈棧，遇到其他運(yùn)算符時(shí)，直接當(dāng)其他運(yùn)算符壓棧。
·這里涉及操作符優(yōu)先級(jí)問題，+ - * / % 這里的優(yōu)先級(jí)相對(duì)于壓操作符棧的優(yōu)先級(jí)。即檢測(cè)當(dāng)前操作符與棧頂?shù)牟僮鞣麅?yōu)先級(jí)，如果當(dāng)前操作符優(yōu)先級(jí)高于棧頂操作符優(yōu)先級(jí)，需要將當(dāng)前操作符壓棧，如果當(dāng)前操作符優(yōu)先級(jí)小于或等于棧頂操作符優(yōu)先級(jí)，則將棧頂操作符出棧，然后再次檢測(cè)下一個(gè)棧頂操作符的優(yōu)先級(jí)與當(dāng)前操作符優(yōu)先級(jí)關(guān)系。
·對(duì)于有左括號(hào)和右括號(hào)的情況，需要對(duì)其做特殊分析。左括號(hào)會(huì)被壓入棧中，右括號(hào)不會(huì)。如果當(dāng)前元素時(shí)左括號(hào)，由于其棧外優(yōu)先級(jí)最高，可以直接將其壓入棧中，如果棧頂優(yōu)先級(jí)是左括號(hào)，并且當(dāng)前操作符是一般操作符，則直接將當(dāng)前操作符壓入棧中，如果當(dāng)前操作符是右括號(hào)，則直接將棧頂?shù)淖罄ㄌ?hào)出棧。
·中綴表達(dá)式和后綴表達(dá)式的不同是操作符的相對(duì)位置存在變化，當(dāng)然后綴表達(dá)式不會(huì)出現(xiàn)括號(hào)，也就是后綴表達(dá)式中隱式包含了操作符的優(yōu)先級(jí)。另外中綴和后綴表達(dá)式中的操作數(shù)相對(duì)順序是一致的，在轉(zhuǎn)換的過程中，當(dāng)當(dāng)前中綴表達(dá)式中的元素時(shí)操作數(shù)時(shí)，直接將其添加到輸出后綴表達(dá)式中就可以。
這里利用的棧是操作符棧
在計(jì)算后綴表達(dá)式的過程中，利用的棧是操作數(shù)棧
從中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式也是一遍掃描中綴表達(dá)式即可，當(dāng)然中間涉及對(duì)操作符棧的操作。
修正：( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2 ， ( ( ( 1 + 2 + 3 ) ) ) 的情形。要時(shí)刻考慮到括號(hào)的特殊性，左括號(hào)的棧內(nèi)優(yōu)先級(jí)和棧外優(yōu)先級(jí)的區(qū)別。對(duì)于左括號(hào)和右括號(hào)的主動(dòng)入棧和出棧以及其他操作符的相對(duì)于其入棧和出棧決策要考慮清楚。
實(shí)現(xiàn)：
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <stack>
5 #include <map>
6 using namespace std;
7
8 map<string, int> operatorPriors;
9
10 void getInfix(vector<string>& infix)
11 {
12 infix.clear();
13 string tmp;
14 while (cin >> tmp)
15 {
16 infix.push_back(tmp);
17 }
18 }
19
20 void init()
21 {
22 operatorPriors["+"] = 10;
23 operatorPriors["-"] = 10;
24 operatorPriors["*"] = 20;
25 operatorPriors["/"] = 20;
26 operatorPriors["%"] = 20;
27 operatorPriors["("] = 30;
28 operatorPriors[")"] = 0;
29 }
30
31 bool prior(const string& op1, const string& op2)
32 {
33 return operatorPriors[op1] > operatorPriors[op2];
34 }
35
36 bool isOperator(const string& s)
37 {
38 return operatorPriors.find(s) != operatorPriors.end();
39 }
40
41 void print(stack<string> operators)
42 {
43 while (!operators.empty())
44 {
45 cout << operators.top() << ' ';
46 operators.pop();
47 }
48 cout << endl;
49 }
50
51 const vector<string>& infixToPostfix(vector<string>& postfix, const vector<string>& infix)
52 {
53 postfix.clear();
54 stack<string> operators;
55 for (vector<string>::size_type i = 0; i != infix.size(); ++i)
56 {
57 if (isOperator(infix[i]))
58 {
59 if (operators.empty())
60 {
61 operators.push(infix[i]);
62 }
63 else if (operators.top() == "(" && infix[i] != ")" || prior(infix[i], operators.top()))
64 {
65 operators.push(infix[i]);
66 }
67 else
68 {
69 if (infix[i] == ")")
70 {
71 while (operators.top() != "(")
72 {
73 postfix.push_back(operators.top());
74 operators.pop();
75 }
76 operators.pop();
77 }
78 else
79 {
80 postfix.push_back(operators.top());
81 operators.pop();
82 while (!operators.empty() && !prior(infix[i], operators.top()) && operators.top() != "(")
83 {
84 postfix.push_back(operators.top());
85 operators.pop();
86 }
87
88 operators.push(infix[i]);
89 }
90 }
91 }
92 else
93 {
94 postfix.push_back(infix[i]);
95 }
96 }
97 while (!operators.empty())
98 {
99 postfix.push_back(operators.top());
100 operators.pop();
101 }
102 return postfix;
103 }
104
105 int main()
106 {
107 init();
108 vector<string> infix;
109 vector<string> postfix;
110 getInfix(infix);
111 infixToPostfix(postfix, infix);
112 for (vector<string>::size_type i = 0; i != postfix.size(); ++i)
113 {
114 cout << postfix[i] << ' ';
115 }
116 cout << endl;
117 return 0;
118 }
后綴表達(dá)式的計(jì)算
表達(dá)式運(yùn)算過程中，需要先做中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換。
這里現(xiàn)對(duì)后綴表達(dá)式求值進(jìn)行解答。
對(duì)后綴表達(dá)式進(jìn)行掃描，遇到操作數(shù)將操作數(shù)壓棧，遇到運(yùn)算符將操作數(shù)出棧，進(jìn)行運(yùn)算，將運(yùn)算的結(jié)果壓入到操作數(shù)棧中。
注意，對(duì)于雙目運(yùn)算符，在堆操作數(shù)棧出棧的時(shí)候要注意，后彈出的操作符為左邊的操作符，不要弄反了。
之前的做法是錯(cuò)誤的，把后綴表達(dá)式存在一個(gè)棧中，只對(duì)棧頂操作，對(duì)于 a b c + * 這種情況不成立。
實(shí)現(xiàn)如下：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <stack>
5 #include <sstream>
6 #include <cstdlib>
7 using namespace std;
8
9 void getPost(vector<string>& post)
10 {
11 post.clear();
12 string tmp;
13 while (cin >> tmp)
14 {
15 post.push_back(tmp);
16 }
17 }
18
19 double stringToDouble(const string& s)
20 {
21 return (atof(s.c_str()));
22 }
23
24 double evalPost(const vector<string>& post)
25 {
26 stack<double> operands;
27 int a, b;
28 for (vector<string>::size_type i = 0; i != post.size(); ++i)
29 {
30 if (post[i] == "+")
31 {
32 b = operands.top();
33 operands.pop();
34 a = operands.top();
35 operands.pop();
36 operands.push(a + b);
37 }
38 else if (post[i] == "-")
39 {
40 b = operands.top();
41 operands.pop();
42 a = operands.top();
43 operands.pop();
44 operands.push(a - b);
45 }
46 else if (post[i] == "*")
47 {
48 b = operands.top();
49 operands.pop();
50 a = operands.top();
51 operands.pop();
52 operands.push(a * b);
53 }
54 else if (post[i] == "/")
55 {
56 b = operands.top();
57 operands.pop();
58 a = operands.top();
59 operands.pop();
60 operands.push(a / b);
61 }
62 else if (post[i] == "%")
63 {
64 b = operands.top();
65 operands.pop();
66 a =operands.top();
67 operands.pop();
68 operands.push(a - b);
69 }
70 else
71 {
72 // stringstream ss;
73 // ss << post[i];
74 // ss >> a;
75 operands.push(stringToDouble(post[i]));
76 }
77 }
78 return operands.top();
79 }
80
81 int main()
82 {
83 vector<string> post;
84 getPost(post);
85 cout << evalPost(post) << endl;
86 return 0;
87 }
繼承層次中的輸入輸出運(yùn)算符重載
class A
{
};
class B : public A
{
};
方案一
可對(duì) A 進(jìn)行重載輸入輸出運(yùn)算符，然后也對(duì) B 重載相應(yīng)版本的輸入輸出運(yùn)算符
方案二
只對(duì) A 進(jìn)行重載輸入輸出運(yùn)算符，對(duì) A 定義一個(gè) virtual print 函數(shù)，在 B 中也對(duì)該 virtual 函數(shù) override
在重載的輸入輸出運(yùn)算符中調(diào)用 virtual print 函數(shù)
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 class Complex
6 {
7 protected:
8 // private:
9 int nR;
10 int nI;
11 public:
12 Complex(int tmpR = -100, int tmpI = -100);
13 virtual void display();
14 virtual ostream& print(ostream& os) const;
15 friend ostream& operator << (ostream&, const Complex&);
16 };
17
18 class NameComplex : public Complex
19 {
20 private:
21 string strName;
22 public:
23 NameComplex(const string& = "abc", int = -100, int = -100);
24 virtual void display();
25 virtual ostream& print(ostream& os) const;
26 // friend ostream& operator << (ostream&, const NameComplex&);
27 };
28
29 Complex::Complex(int tmpR, int tmpI) : nR(tmpR), nI(tmpI) {}
30
31 void Complex::display()
32 {
33 cout << nR << endl;
34 cout << nI << endl;
35 }
36
37 ostream& Complex::print(ostream& os) const
38 {
39 os << nR << ' ' << nI;
40 return os;
41 }
42
43 /*
44 ostream& operator << (ostream& os, const Complex& rhs)
45 {
46 os << rhs.nR << ' ' << rhs.nI;
47 return os;
48 }
49 */
50
51 ostream& operator << (ostream& os, const Complex& rhs)
52 {
53 return rhs.print(os);
54 }
55
56 NameComplex::NameComplex(const string& str, int nR, int nI) : Complex(nR, nI), strName(str) {}
57
58 void NameComplex::display()
59 {
60 cout << strName << endl;
61 Complex::display();
62 }
63
64 /*
65 ostream& operator << (ostream& os, const NameComplex& rhs)
66 {
67 os << rhs.strName << ' ';
68 operator << (os, static_cast<Complex>(rhs));
69 return os;
70 }
71 */
72
73 ostream& NameComplex::print(ostream& os) const
74 {
75 os << strName << ' ';
76 return Complex::print(os);
77 }
78
79 int main()
80 {
81 Complex a;
82 cout << a << endl;
83
84 NameComplex b;
85 cout << b << endl;
86 }
http://topic.csdn.net/u/20110627/22/c4c0b809-13f4-482d-aa26-5faf5c1fc0f0.html?54375
還是利用字符 ASCII 定義一個(gè)表，即
static char x[256];
memset(x, 0, sizeof (x));
這樣一遍掃描即可，在掃描的過程中，首先檢測(cè)當(dāng)前字符是否出現(xiàn)，如果沒出現(xiàn)，將對(duì)應(yīng) x 的元素置為出現(xiàn)狀態(tài)，并且將該字符加入到輸出字符串中，如果已經(jīng)出現(xiàn)過，則忽略
實(shí)現(xiàn)如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 void changestr(const char* pIn, char* pOut)
6 {
7 static char x[256];
8 int i = 0, j = 0;
9 memset(x, 0, sizeof (x));
10 for (i = 0, j = 0; i < strlen(pIn); ++i)
11 {
12 if (x[pIn[i]] == 0)
13 {
14 x[pIn[i]] = 1;
15 pOut[j] = pIn[i];
16 ++j;
17 }
18 }
19 pOut[j] = '\0';
20 }
21
22 int main()
23 {
24 char pIn[100], pOut[100];
25 while (scanf("%s", pIn) != EOF)
26 {
27 changestr(pIn, pOut);
28 printf("%s\n", pOut);
29 }
30 return 0;
31 }
一個(gè)字符串由 a - z 26 個(gè)字符組成，其中只有一個(gè)字符出現(xiàn)的次數(shù)為奇數(shù)次，其他 25 個(gè)字符出現(xiàn)次數(shù)都是偶數(shù)次。
找出這個(gè)出現(xiàn)奇數(shù)次的字符。
這個(gè)問題，最直觀的解法就是遍歷一下，記錄每個(gè)字符的出現(xiàn)次數(shù) int x[26] = {0};
然后掃描 x 檢測(cè)即可。
但是回過頭來想一下這樣做有必要嗎，看看我們這樣做的后果是什么，我們得到了所有字符出現(xiàn)的次數(shù)，然后檢測(cè)以得到出現(xiàn)次數(shù)為奇數(shù)的字符，這種方法是可以的，但是沒有必要得到每個(gè)字符的出現(xiàn)次數(shù)，也就是說我們得到了大量的冗余信息，這種冗余信息是需要代價(jià)的。這也就導(dǎo)致了我們的這種方法效率不高。
把問題認(rèn)識(shí)清楚很重要，最重要。我們只需要找到出現(xiàn)次數(shù)為奇數(shù)的字符，不需要得到每個(gè)字符的具體出現(xiàn)次數(shù)。我們可以利用位運(yùn)算中的異或。
異或的運(yùn)算性質(zhì)是：
a ^ a = 0
a ^ a ^ a = a
偶數(shù)個(gè)本身異或運(yùn)算為 0
奇數(shù)個(gè)本身異或運(yùn)算為其本身
也就是說，我們可以對(duì)字符串中的每個(gè)字符，一遍掃描，做異或運(yùn)算，由于 25 個(gè)字符出現(xiàn)偶數(shù)次，1 個(gè)字符出現(xiàn)奇數(shù)次，一遍掃描異或運(yùn)算得到的結(jié)果即是出現(xiàn)次數(shù)為奇數(shù)的那個(gè)字符。
總結(jié)：
一個(gè)問題的解決，要從認(rèn)清問題開始。求解問題的好的方法是觀察我們的解決過程，看看是不是中間得到了冗余的信息，如果存在這種冗余信息，說明我們的解法做了不必要的計(jì)算，有更大的改進(jìn)空間。
異或運(yùn)算很巧妙。關(guān)于它的巧妙運(yùn)用很多地方都有提到。其中《編程之美》中有關(guān)于異或運(yùn)算的運(yùn)用。
找出字符串中最大的子串
子串：當(dāng)重復(fù)出現(xiàn)某個(gè)字符時(shí)，這個(gè)字符串就是子串
例如：
字符串 abcd13agbf
子串為：abcd13a, bcd13agb
求解 1
兩重遍歷字符串，檢測(cè)左右兩個(gè)端點(diǎn)的字符是否一樣，如果相等，則是子串
這種方法直觀，時(shí)間復(fù)雜度為 O(N ^ 2)。
求解 2
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。
針對(duì)字符，我們知道其 ASCII 范圍是 0 - 255 ，我們這設(shè)計(jì)一個(gè)二維數(shù)組
int x[256][100];
x 存儲(chǔ)每個(gè)字符所在的位置
用 int n[256]; 記錄每個(gè)字符出現(xiàn)的次數(shù)
掃描一遍字符串，即可得到我們想要的信息并存儲(chǔ)于 x 和 n 中
然后對(duì) x 進(jìn)行掃描，即可得到最大的子串
第一次掃描字符串時(shí)間復(fù)雜度是 O(N)
第二次掃描 x ，時(shí)間復(fù)雜度也是 O(N)
總的時(shí)間復(fù)雜度為 O(N)
實(shí)現(xiàn)：
1 #include <iostream>
2 using namespace std;
3
4 char* maxSubStr(char* s, const char* str)
5 {
6 int left = 0, right = 0;
7 int max = 0;
8 for (int i = 0; i < strlen(str); ++i)
9 {
10 int temp = 1;
11 for (int j = i + 1; j < strlen(str); ++j)
12 {
13 if (str[i] == str[j])
14 {
15 ++temp;
16 if (temp > max)
17 {
18 max = temp;
19 left = i;
20 right = j;
21 }
22 }
23 else
24 {
25 ++temp;
26 }
27 }
28 }
29 int j = 0;
30 for (int i = left; i <= right; ++i, ++j)
31 {
32 s[j] = str[i];
33 }
34 s[j] = '\0';
35 return s;
36 }
37
38 char* maxSubStrX(char* s, const char* str)
39 {
40 static int x[256][100];
41 static int n[256];
42 memset(x, -1, sizeof (x));
43 memset(n, 0, sizeof (n));
44 for (int i = 0; i < strlen(str); ++i)
45 {
46 x[ str[i] ][ n[ str[i] ] ] = i;
47 ++n[str[i]];
48 }
49 int left = 0, right = 0;
50 int max = 0;
51 for (int i = 0; i < 256; ++i)
52 {
53 for (int j = 0; j < n[i] - 1; ++i)
54 {
55 if (x[i][j + 1] - x[i][j] > max)
56 {
57 max = x[i][j + 1] - x[i][j];
58 left = x[i][j];
59 right = x[i][j + 1];
60 }
61 }
62 }
63 int j = 0;
64 for (int i = left; i <= right; ++i, ++j)
65 {
66 s[j] = str[i];
67 }
68 s[j] = '\0';
69 return s;
70 }
71
72 int main()
73 {
74 char str[100], s[100];
75 while (cin >> str)
76 {
77 cout << maxSubStr(s, str) << endl;
78 cout << maxSubStrX(s, str) << endl;
79 }
80 return 0;
81 }
利用棧存儲(chǔ)中綴表達(dá)式的各個(gè)元素
例如：
1 2 + 3 *
3 3 *
9
1 // 后綴表達(dá)式求解結(jié)果
2
3 #include <iostream>
4 #include <stack>
5 #include <string>
6 #include <sstream>
7 #include <algorithm>
8 using namespace std;
9
10 void printPost(const stack<string>& post)
11 {
12 stack<string> temp(post);
13 while (!temp.empty())
14 {
15 cout << temp.top() << ' ';
16 temp.pop();
17 }
18 cout << endl;
19 }
20
21 void clearPost(stack<string>& post)
22 {
23 while (!post.empty())
24 {
25 post.pop();
26 }
27 }
28
29 void getPost(stack<string>& post)
30 {
31 clearPost(post);
32 string t;
33 stack<string> temp;
34 while (cin >> t)
35 {
36 temp.push(t);
37 }
38 while (!temp.empty())
39 {
40 post.push(temp.top());
41 temp.pop();
42 }
43 }
44
45 double computePost(const stack<string>& rhs)
46 {
47 stack<string> post(rhs);
48 double d1, d2;
49 double dd;
50 string optor;
51 string temp;
52 while (post.size() >= 3)
53 {
54 d1 = atof(post.top().c_str());
55 post.pop();
56 d2 = atof(post.top().c_str());
57 post.pop();
58 optor = post.top();
59 post.pop();
60 switch (optor[0])
61 {
62 case '+':
63 dd = d1 + d2;
64 break;
65 case '-':
66 dd = d1 - d2;
67 break;
68 case '*':
69 dd = d1 * d2;
70 break;
71 case '/':
72 dd = d1 / d2;
73 break;
74 default:
75 break;
76 }
77 if (post.empty())
78 {
79 break;
80 }
81 stringstream ss;
82 ss << dd;
83 ss >> temp;
84 post.push(temp);
85 printPost(post);
86 }
87 return dd;
88 }
89
90 int main()
91 {
92 stack<string> post;
93 cout << "Input:" << endl;
94 getPost(post);
95 printPost(post);
96 cout << computePost(post) << endl;
97 return 0;
98 }
字符轉(zhuǎn)換函數(shù)的實(shí)現(xiàn)
第一種方法，利用 ASCII 碼大小計(jì)算
1 char mytoupper(char c)
2 {
3 if (c >= 'a' && c <= 'z')
4 {
5 c += ('A' - 'a');
6 }
7 return c;
8 }
9
10 char mytolower(char c)
11 {
12 if (c >= 'A' && c <= 'Z')
13 {
14 c += ('a' - 'A');
15 }
16 return c;
17 }
第二種方法，利用位運(yùn)算
'a' - 'z': 97 - 122
'A' - 'Z': 65 - 90
'a' 與 'A' 正好相差 32 ，即 20x ，0010 0000
大寫字母的范圍是 0100 0001 - 0101 1010
小些字母的范圍是 0110 0001 - 0111 1010
對(duì)于大寫字母第 5 位都為 0
對(duì)于小些字母第 5 為都為 1
可以利用位運(yùn)算的方法，即對(duì)大寫字母的第 5 位進(jìn)行操作，但要保持其他位不變
即利用 MASK = 0010 0000
大寫 -> 小寫
'a' = 'A' | (0010 0000);
小寫 -> 大寫
'A' = 'a' & (1101 1111);
這樣做也不需要檢測(cè)，如果本來就是小寫，在做 或 操作時(shí)，第 5 位不變，維持 1
如果本來就是大寫，在做 與操作時(shí)，第 5 位還是不變，維持 0
1 char mytoupper(char c)
2 {
3 return c & (0xDF);
4 }
5
6 char mytolower(char c)
7 {
8 return c | (0x20);
9 }
http://m.shnenglu.com/qinqing1984/archive/2011/06/25/149427.html
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 }
除以 1000 ， 對(duì)余數(shù)進(jìn)行處理
1 #include <iostream>
2 using namespace std;
3
4 char* reverse(char* s, int low, int high)
5 {
6 while (low < high)
7 {
8 s[low] ^= s[high];
9 s[high] ^= s[low];
10 s[low] ^= s[high];
11 ++low;
12 --high;
13 }
14 return s;
15 }
16
17 char* format_thousands_separator(char a[], unsigned long val)
18 {
19 char* ret = a;
20 char temp[4];
21 int t;
22 int n = 0;
23 while (val > 1000)
24 {
25 t = val % 1000;
26 if (t >= 100)
27 {
28 itoa(t, temp, 10);
29 reverse(temp, 0, 2);
30 //cout << temp << endl;
31 strcat(ret, temp);
32 //cout<< "test" << ret << endl;
33 }
34 else if (t >= 10)
35 {
36 itoa(t, temp, 10);
37 reverse(temp, 0, 1);
38 strcat(ret, temp);
39 strcat(ret, "0");
40 }
41 else
42 {
43 itoa(t, temp, 10);
44 strcat(ret, temp);
45 strcat(ret, "00");
46 }
47 strcat(ret, ",");
48 n += 4;
49 val /= 1000;
50 ret[n] = '\0';
51 cout << ret << endl;
52 }
53 if (val >= 100)
54 {
55 itoa(val, temp, 10);
56 reverse(temp, 0, 2);
57 strcat(ret, temp);
58 n += 3;
59 }
60 else if (val >= 10)
61 {
62 itoa(val, temp, 10);
63 reverse(temp, 0, 1);
64 strcat(ret, temp);
65 n += 2;
66 }
67 else
68 {
69 itoa(val, temp, 10);
70 strcat(ret, temp);
71 ++n;
72 }
73 reverse(ret, 0, n - 1);
74 ret[n] = '\0';
75 return ret;
76 };
77
78 int main()
79 {
80 unsigned long ul;
81 char sul[20] = {0};
82 while (cin >> ul)
83 {
84 cout << format_thousands_separator(sul, ul) << endl;
85 }
86 return 0;
87 }
先轉(zhuǎn)換成一個(gè) 字符串 ，然后從右掃描，加逗號(hào)，然后反轉(zhuǎn)
1 #include <iostream>
2 #include <sstream>
3 #include <string>
4 #include <algorithm>
5 using namespace std;
6
7 const string& format_thousands_separator(string& s, unsigned long val)
8 {
9 s.clear();
10 char t[20];
11 string temp(ltoa(val, t, 10));
12
13 int n = 0;
14 for (string::const_reverse_iterator cit = temp.rbegin(); cit != temp.rend(); ++cit)
15 {
16 ++n;
17 s += *cit;
18 if (n == 3)
19 {
20 s += ',';
21 n = 0;
22 }
23 }
24 reverse(s.begin(), s.end());
25 return s;
26 }
27
28 int main()
29 {
30 unsigned long ul;
31 string sul;
32 while (cin >> ul)
33 {
34 cout << format_thousands_separator(sul, ul) << endl;
35 }
36 return 0;
37 }
http://m.shnenglu.com/qinqing1984/archive/2011/06/24/149366.html