Skip to content

Commit a7fa395

Browse files
gatiemegatieme
authored
Merge pull request gatieme#9 from happerys/master
中缀表达式
2 parents 6dbdd43 + 7c89107 commit a7fa395

11 files changed

Lines changed: 682 additions & 295 deletions

File tree

‎022-栈的压入弹出序列/README.md‎

Lines changed: 10 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -90,50 +90,21 @@ using namespace std;
9090
class Solution
9191
{
9292
public:
93-
bool IsPopOrder(vector<int> pushV,vector<int> popV)
94-
{
95-
96-
if(pushV.size( ) == 0 || popV.size( ) == 0)
97-
{
93+
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
94+
if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
9895
return false;
99-
}
10096
stack<int> s;
101-
int push, pop;
102-
103-
s.push(pushV[0]);
104-
debug <<"push" <<pushV[0] <<endl;
105-
106-
for(push = 0, pop = 0;
107-
push < pushV.size() && pop < popV.size( );)
108-
{
109-
if(s.empty( ) != true && s.top( ) == popV[pop]) // 当前栈顶元素正好是出栈序列中的元素
110-
{
111-
debug <<"pop"<<popV[pop] <<endl;
112-
// 模拟出栈的过程
113-
s.pop( );
114-
pop++;
115-
}
116-
else
117-
{
118-
119-
// 模拟入栈的过程
120-
s.push(pushV[++push]);
121-
debug <<"push" <<pushV[push] <<endl;
122-
97+
int j=0;
98+
for(int i=0;i<pushV.size();++i){
99+
s.push(pushV[i]);
100+
while(!s.empty()&&s.top()==popV[j]){
101+
s.pop();
102+
++j;
123103
}
124104
}
125-
if(s.empty( ) == true)
126-
{
105+
if(s.empty())
127106
return true;
128-
}
129-
else
130-
{
131-
return false;
132-
}
133-
134-
135-
136-
107+
return false;
137108
}
138109
};
139110

‎028-字符串的排列/README.md‎

Lines changed: 70 additions & 85 deletions
Original file line numberDiff line numberDiff line change
@@ -143,92 +143,30 @@ public:
143143
3. 接着，固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换
144144
145145
```cpp
146-
#include <iostream>
147-
#include <algorithm>
148-
#include <vector>
149-
#include <string>
150-
151-
using namespace std;
152-
153-
// 调试开关
154-
#define __tmain main
155-
156-
#ifdef __tmain
157-
158-
#define debug cout
159-
160-
#else
161-
162-
#define debug 0 && cout
163-
164-
#endif // __tmain
165-
166-
167-
class Solution
168-
{
169-
protected:
170-
vector<string> m_res;
171-
172-
public:
173-
174-
vector<string> Permutation(string str)
175-
{
176-
m_res.clear( );
177-
178-
if(str.empty( ) == true)
179-
{
180-
return m_res;
181-
}
182-
PermutationRecursion(str, 0);
183-
184-
sort(m_res.begin( ), m_res.end( ));
185-
return m_res;
146+
vector<string> Permutation(string str) {
147+
vector<string> v1;
148+
if(str.size()<= 0 || str.size()>9 )//排除异常情况
149+
return v1;
150+
PermutationHelp(v1, 0, str);
151+
return v1;
186152
}
187-
188-
189-
void PermutationRecursion(string str, int begin)
190-
{
191-
if(str[begin] == '\0')
192-
{
193-
debug <<str <<endl;
194-
m_res.push_back(str);
195-
}
196-
else
197-
{
198-
for(int i = begin;
199-
str[i] != '\0';
200-
i++)
201-
{
202-
//debug <<str[i] <<str[begin] <<endl;
203-
if(!HasDuplicate(str, begin, i))
204-
{
205-
swap(str[i], str[begin]);
206-
debug <<"swap " <<str[i] <<"(" <<i <<")" <<" and " <<str[begin] <<"(" <<begin <<")" <<endl;
207-
PermutationRecursion(str, begin + 1);
208-
//copy(str.begin( ), str.degin( ) + i, ostream_iterator<char>(cout," "));
209-
swap(str[i], str[begin]);
210-
}
211-
}
212-
}
213-
}
214-
215-
private:
216-
//find duplicate of str[i] in str[k,i)
217-
bool HasDuplicate(string& str, int k, int i) const {
218-
for (int p = k; p < i; p++)
219-
if (str[p] == str[i]) return true;
220-
221-
return false;
222-
}
223-
};
224-
225-
int __tmain( )
226-
{
227-
Solution solu;
228-
solu.Permutation("abc");
229-
230-
return 0;
231-
}
153+
void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
154+
{
155+
if(k == (str.size() - 1))//单次递归终止条件
156+
ans.push_back(str);
157+
unordered_set<char> us;//保存字符串中字符的无序集合
158+
sort(str.begin() + k, str.end());
159+
for(int i = k; i < str.size(); i++)
160+
{
161+
if(us.find(str[i]) == us.end())
162+
{
163+
us.insert(str[i]);
164+
swap(str[i], str[k]);
165+
PermutationHelp(ans, k + 1, str);
166+
swap(str[i], str[k]);
167+
}
168+
}
169+
}
232170
```
233171

234172
#STL的next_permutation求全排列
@@ -263,4 +201,51 @@ public:
263201
}
264202
};
265203
```
204+
# 字符串的全组合
205+
```cpp
206+
#include<iostream>
207+
#include<vector>
208+
#include<cstring>
209+
#include<assert.h>
210+
using namespace std;
211+
212+
void Combination(char *string ,int number,vector<char> &result);
213+
214+
void Combination(char *string)
215+
{
216+
assert(string != NULL);
217+
vector<char> result;
218+
int i , length = strlen(string);
219+
for(i = 1 ; i <= length ; ++i)
220+
Combination(string , i ,result);
221+
}
266222

223+
void Combination(char *string ,int number , vector<char> &result)
224+
{
225+
assert(string != NULL);
226+
if(number == 0)
227+
{
228+
static int num = 1;
229+
printf("第%d个组合\t",num++);
230+
vector<char>::iterator iter = result.begin();
231+
for( ; iter != result.end() ; ++iter)
232+
printf("%c",*iter);
233+
printf("\n");
234+
return ;
235+
}
236+
if(*string == '\0')
237+
return ;
238+
result.push_back(*string);
239+
Combination(string + 1 , number - 1 , result);
240+
result.pop_back();
241+
Combination(string + 1 , number , result);
242+
}
243+
244+
int main(void)
245+
{
246+
char str[] = "abc";
247+
Combination(str);
248+
return 0;
249+
}
250+
251+
```

‎028-字符串的排列/字符串的全组合.cpp‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
void Combination(char *string ,int number,vector<char> &result);
2+
3+
void Combination(char *string)
4+
{
5+
assert(string != NULL);
6+
vector<char> result;
7+
int i , length = strlen(string);
8+
for(i = 1 ; i <= length ; ++i)
9+
Combination(string , i ,result);
10+
}
11+
12+
void Combination(char *string ,int number , vector<char> &result)
13+
{
14+
assert(string != NULL);
15+
if(number == 0)
16+
{
17+
static int num = 1;
18+
printf("第%d个组合\t",num++);
19+
20+
vector<char>::iterator iter = result.begin();
21+
for( ; iter != result.end() ; ++iter)
22+
printf("%c",*iter);
23+
printf("\n");
24+
return ;
25+
}
26+
if(*string == '\0')
27+
return ;
28+
result.push_back(*string);
29+
Combination(string + 1 , number - 1 , result);
30+
result.pop_back();
31+
Combination(string + 1 , number , result);
32+
}
33+
int main(void)
34+
{
35+
char str[] = "abc";
36+
Combination(str);
37+
return 0;
38+
}

‎031-连续子数组的最大和/README.md‎

Lines changed: 13 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -147,64 +147,22 @@ class Solution
147147
public:
148148
149149
int FindGreatestSumOfSubArray(vector<int> array)
150-
{
151-
152-
if(array.size( ) == 0)
153-
{
154-
return 0;
155-
}
156-
157-
158-
159-
#ifdef __tmain
160-
161-
int temp, start, end;
162-
163-
#endif // __tmain
164-
165-
int maxSum = INT_MIN;
166-
dp[0] = array[0];
167-
168-
for(unsigned int i = 1; i < array.size( ); i++)
150+
{
151+
if(array.size()<=0)
152+
return -1;
153+
int nsum_value = array[0]; //初始化f(i-1)
154+
int max_sum = -1;
155+
for(int i = 1; i < array.size(); i++)
169156
{
170-
171-
if(dp[i - 1] <= 0)
172-
{
173-
dp[i] = array[i];
174-
175-
#ifdef __tmain
176-
177-
temp = i;
178-
179-
#endif // __tmain
180-
181-
}
157+
if(nsum_value <= 0)
158+
nsum_value = array[i];
182159
else
183-
{
184-
dp[i] = array[i] + dp[i - 1];
185-
}
186-
187-
188-
if(dp[i] > maxSum)
189-
{
190-
maxSum = dp[i];
191-
192-
#ifdef __tmain
193-
194-
start = temp;
195-
end = i;
196-
197-
#endif // __tmain
198-
}
199-
160+
nsum_value += array[i];
161+
162+
if(nsum_value > max_sum)
163+
max_sum = nsum_value;
200164
}
201-
202-
debug <<"[" <<start <<", " <<end <<"] = " <<maxSum <<endl;
203-
204-
return maxSum;
205-
206-
207-
165+
return max_sum;
208166
}
209167
210168
};

0 commit comments

Comments
 (0)