Skip to content

Commit fac3887

Browse files
daiwbdaiwb
committed
LeetCode 05/30/2014
1 parent 0270d54 commit fac3887

File tree

3 files changed

+249
-0
lines changed

3 files changed

+249
-0
lines changed

‎LeetCode/isNumber.cpp‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
class Solution {
31+
public:
32+
bool isok2(string str) {
33+
if (str.length() == 0) return false;
34+
REP(i,str.length()) {
35+
if (!(str[i] >= '0' && str[i] <= '9')) return false;
36+
}
37+
return true;
38+
}
39+
bool isok(string str) {
40+
int idx = -1;
41+
REP(i,str.length()) {
42+
if (str[i] == '.') {
43+
if (idx == -1) idx = i;
44+
else idx = -2;
45+
}
46+
}
47+
if (idx == -2) return false;
48+
if (idx == -1) return isok2(str);
49+
if (str.length() == 1) return false;
50+
return (idx == 0 || isok2(str.substr(0, idx))) && (idx == str.length() - 1 || isok2(str.substr(idx + 1)));
51+
}
52+
bool isNumber(const char *s) {
53+
string str = string(s);
54+
while (str.length() > 0 && str[0] == ' ') str.erase(str.begin(), str.begin() + 1);
55+
while (str.length() > 0 && str[str.length() - 1] == ' ') str.erase(str.end() - 1);
56+
if (str.length() > 0 && (str[0] == '-' || str[0] == '+')) str.erase(str.begin(), str.begin() + 1);
57+
int idx = -1;
58+
REP(i,str.length()) {
59+
if (str[i] == 'e' || str[i] == 'E') {
60+
if (idx == -1) idx = i;
61+
else idx = -2;
62+
}
63+
}
64+
if (idx == -2) return false;
65+
if (idx == -1) return isok(str);
66+
FOR(i,idx+1,str.length()-1) {
67+
if (str[i] == '.') return false;
68+
}
69+
if (idx + 1 < str.length() && (str[idx + 1] == '+' || str[idx + 1] == '-')) str.erase(str.begin() + idx + 1, str.begin() + idx + 2);
70+
return isok(str.substr(0, idx)) && isok(str.substr(idx + 1));
71+
}
72+
};
73+
74+
int main() {
75+
Solution s = Solution();
76+
cout << s.isNumber("0") << endl;
77+
cout << s.isNumber(" 0.1 ") << endl;
78+
cout << s.isNumber("abc") << endl;
79+
cout << s.isNumber("1 a") << endl;
80+
cout << s.isNumber("2e10") << endl;
81+
cout << s.isNumber(".1") << endl;
82+
cout << s.isNumber("3.") << endl;
83+
cout << s.isNumber(".") << endl;
84+
cout << s.isNumber("+.8") << endl;
85+
cout << s.isNumber("6e6.5") << endl;
86+
cout << s.isNumber(" 005047e+6") << endl;
87+
return 0;
88+
}

‎LeetCode/minWindow.cpp‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
class Solution {
31+
public:
32+
string minWindow(string S, string T) {
33+
map<char, int> mp, tp;
34+
REP(i,T.length()) {
35+
if (mp.find(T[i]) == mp.end()) mp[T[i]] = 1;
36+
else ++mp[T[i]];
37+
}
38+
int cnt = 0, rt = -1;
39+
REP(i,S.length()) {
40+
char ch = S[i];
41+
if (mp.find(ch) == mp.end()) continue;
42+
if (tp.find(ch) == tp.end()) tp[ch] = 1;
43+
else ++tp[ch];
44+
if (tp[ch] == mp[ch]) {
45+
++cnt;
46+
if (cnt == mp.size()) {
47+
rt = i;
48+
break;
49+
}
50+
}
51+
}
52+
if (rt == -1) return "";
53+
int lt = 0;
54+
string res = S.substr(0, rt + 1);
55+
while (true) {
56+
while (true) {
57+
if (mp.find(S[lt]) == mp.end()) {
58+
++lt;
59+
continue;
60+
}
61+
if (tp[S[lt]] > mp[S[lt]]) {
62+
--tp[S[lt]];
63+
++lt;
64+
continue;
65+
}
66+
break;
67+
}
68+
if (rt + 1 - lt < res.length()) res = S.substr(lt, rt + 1 - lt);
69+
++rt;
70+
if (rt >= S.length()) break;
71+
char ch = S[rt];
72+
if (mp.find(ch) == mp.end()) continue;
73+
++tp[ch];
74+
}
75+
return res;
76+
}
77+
};
78+
79+
int main() {
80+
Solution s = Solution();
81+
cout << s.minWindow("ADOBECODEBANC", "ABC") << endl;
82+
cout << s.minWindow("ab", "b") << endl;
83+
return 0;
84+
}

‎LeetCode/simplifyPath.cpp‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
vector<string> split( const string& s, const string& delim =" " ) {
31+
vector<string> res;
32+
string t;
33+
for ( int i = 0 ; i != s.size() ; i++ ) {
34+
if ( delim.find( s[i] ) != string::npos ) {
35+
if ( !t.empty() ) {
36+
res.push_back( t );
37+
t = "";
38+
}
39+
} else {
40+
t += s[i];
41+
}
42+
}
43+
if ( !t.empty() ) {
44+
res.push_back(t);
45+
}
46+
return res;
47+
}
48+
49+
class Solution {
50+
public:
51+
string simplifyPath(string path) {
52+
VS a = split(path, string("/"));
53+
VS mm;
54+
REP(i,a.size()) {
55+
if (a[i] == ".") {
56+
} else if (a[i] == "..") {
57+
if (!mm.empty()) mm.pop_back();
58+
} else {
59+
mm.push_back(a[i]);
60+
}
61+
}
62+
if (mm.empty()) return "/";
63+
string res = "";
64+
REP(i,mm.size()) res += "/" + mm[i];
65+
return res;
66+
}
67+
};
68+
69+
int main() {
70+
Solution s = Solution();
71+
cout << s.simplifyPath("/home/") << endl;
72+
cout << s.simplifyPath("/a/./b/../../c/") << endl;
73+
cout << s.simplifyPath("/...") << endl;
74+
cout << s.simplifyPath("/.") << endl;
75+
cout << s.simplifyPath("/..") << endl;
76+
return 0;
77+
}

0 commit comments

Comments
 (0)