Skip to content

Commit 1958e83

Browse files
daiwbdaiwb
committed
LeetCode 06/02/2014
1 parent 8e9962e commit 1958e83

File tree

10 files changed

+408
-0
lines changed

10 files changed

+408
-0
lines changed

‎LeetCode/cloneGraph.cpp‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
* Definition for undirected graph.
3+
* struct UndirectedGraphNode {
4+
* int label;
5+
* vector<UndirectedGraphNode *> neighbors;
6+
* UndirectedGraphNode(int x) : label(x) {};
7+
* };
8+
*/
9+
class Solution {
10+
public:
11+
map<int, UndirectedGraphNode*> vv;
12+
UndirectedGraphNode* doit(UndirectedGraphNode *v) {
13+
UndirectedGraphNode *res = new UndirectedGraphNode(v->label);
14+
vv[v->label] = res;
15+
for (int i = 0; i < v->neighbors.size(); ++i) {
16+
if (!vv[v->neighbors[i]->label]) res->neighbors.push_back(doit(v->neighbors[i]));
17+
else res->neighbors.push_back(vv[v->neighbors[i]->label]);
18+
}
19+
return res;
20+
}
21+
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
22+
if (node == NULL) return NULL;
23+
vv.clear();
24+
return doit(node);
25+
}
26+
};

‎LeetCode/copyRandomList.cpp‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* Definition for singly-linked list with a random pointer.
3+
* struct RandomListNode {
4+
* int label;
5+
* RandomListNode *next, *random;
6+
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
7+
* };
8+
*/
9+
class Solution {
10+
public:
11+
RandomListNode *copyRandomList(RandomListNode *head) {
12+
if (head == NULL) return head;
13+
map<RandomListNode*, RandomListNode*> mp;
14+
RandomListNode* res = new RandomListNode(0);
15+
RandomListNode* p = head;
16+
RandomListNode* q = res;
17+
while (p) {
18+
RandomListNode* t = new RandomListNode(p->label);
19+
q->next = t;
20+
mp[p] = t;
21+
p = p->next;
22+
q = q->next;
23+
}
24+
p = head;
25+
q = res->next;
26+
while (p) {
27+
if (p->random == NULL) q->random = NULL;
28+
else q->random = mp[p->random];
29+
p = p->next;
30+
q = q->next;
31+
}
32+
return res->next;
33+
}
34+
};

‎LeetCode/evalRPN.cpp‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
int s2i(string s) {
2+
stringstream ss;
3+
ss << s;
4+
int res;
5+
ss >> res;
6+
return res;
7+
}
8+
9+
string i2s(int n) {
10+
stringstream ss;
11+
ss << n;
12+
string res;
13+
ss >> res;
14+
return res;
15+
}
16+
17+
class Solution {
18+
public:
19+
bool isop(string str) {
20+
return str == "+" || str == "-" || str == "*" || str == "/";
21+
}
22+
int evalRPN(vector<string> &tokens) {
23+
vector<string> mm = tokens;
24+
while (mm.size() > 1) {
25+
for (int i = 0; i < mm.size(); ++i) {
26+
if (isop(mm[i])) {
27+
int v1 = s2i(mm[i - 2]);
28+
int v2 = s2i(mm[i - 1]);
29+
int v3;
30+
if (mm[i] == "+") v3 = v1 + v2;
31+
else if (mm[i] == "-") v3 = v1 - v2;
32+
else if (mm[i] == "*") v3 = v1 * v2;
33+
else if (mm[i] == "/") v3 = v1 / v2;
34+
mm[i] = i2s(v3);
35+
mm.erase(mm.begin() + i - 2, mm.begin() + i);
36+
break;
37+
}
38+
}
39+
}
40+
return s2i(mm[0]);
41+
}
42+
};

‎LeetCode/insertionSortList.cpp‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* struct ListNode {
4+
* int val;
5+
* ListNode *next;
6+
* ListNode(int x) : val(x), next(NULL) {}
7+
* };
8+
*/
9+
class Solution {
10+
public:
11+
ListNode *insertionSortList(ListNode *head) {
12+
if (head == NULL) return head;
13+
ListNode *cur = head->next, *last = head;
14+
while (cur != NULL) {
15+
ListNode *next = cur->next;
16+
if (cur->val <= head->val) {
17+
cur->next = head;
18+
head = cur;
19+
} else if (cur->val >= last->val) {
20+
last = cur;
21+
} else {
22+
ListNode *t = head;
23+
while (true) {
24+
if (cur->val > t->val && cur->val <= t->next->val) {
25+
cur->next = t->next;
26+
t->next = cur;
27+
break;
28+
}
29+
t = t->next;
30+
}
31+
}
32+
last->next = next;
33+
cur = next;
34+
}
35+
return head;
36+
}
37+
};

‎LeetCode/ladderLength.cpp‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#define REP(i,n) for(int i=0;i<(n);++i)
2+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
3+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
4+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
5+
#define CLR(x) memset((x),0,sizeof((x)))
6+
#define MP make_pair
7+
#define MPI make_pair<int, int>
8+
#define PB push_back
9+
typedef long long LL;
10+
typedef vector<int> VI;
11+
typedef vector<string> VS;
12+
typedef pair<int, int> PI;
13+
14+
class Solution {
15+
public:
16+
int ladderLength(string start, string end, unordered_set<string> &dict) {
17+
if (start == end) return 0;
18+
dict.erase(start);
19+
int len = start.length();
20+
deque<pair<string, int> > que;
21+
que.push_back(make_pair(start, 1));
22+
while (!que.empty()) {
23+
pair<string, int> item = que.front();
24+
que.pop_front();
25+
string s = item.first;
26+
int c = item.second;
27+
REP(i,len) {
28+
char bak = s[i];
29+
for (char ch = 'a'; ch <= 'z'; ++ch) {
30+
s[i] = ch;
31+
if (s == end) return c + 1;
32+
if (dict.find(s) != dict.end()) {
33+
que.push_back(make_pair(s, c + 1));
34+
dict.erase(s);
35+
}
36+
}
37+
s[i] = bak;
38+
}
39+
}
40+
return 0;
41+
}
42+
};

‎LeetCode/longestConsecutive.cpp‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
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+
#include <unordered_map>
16+
using namespace std;
17+
18+
#define REP(i,n) for(int i=0;i<(n);++i)
19+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
20+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
21+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
22+
#define CLR(x) memset((x),0,sizeof((x)))
23+
#define MP make_pair
24+
#define MPI make_pair<int, int>
25+
#define PB push_back
26+
typedef long long LL;
27+
typedef vector<int> VI;
28+
typedef vector<string> VS;
29+
typedef pair<int, int> PI;
30+
31+
class Solution {
32+
public:
33+
int longestConsecutive(vector<int> &num) {
34+
unordered_map<int, bool> mp;
35+
REP(i,num.size()) mp[num[i]] = true;
36+
int res = 0;
37+
REP(i,num.size()) {
38+
int cur = num[i];
39+
if (mp.find(cur) == mp.end()) continue;
40+
int cnt = 1;
41+
mp.erase(cur);
42+
while (mp.find(cur + 1) != mp.end()) {
43+
++cnt;
44+
mp.erase(cur++);
45+
}
46+
cur = num[i];
47+
while (mp.find(cur - 1) != mp.end()) {
48+
++cnt;
49+
mp.erase(cur--);
50+
}
51+
res = max(res, cnt);
52+
}
53+
return res;
54+
}
55+
};
56+
57+
int main() {
58+
Solution s = Solution();
59+
return 0;
60+
}

‎LeetCode/minCut.cpp‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
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 s;
33+
int len;
34+
vector<int> mm;
35+
vector<vector<int> > vv;
36+
bool isok(int st, int ed) {
37+
return vv[st][ed] == 1;
38+
}
39+
int doit(int idx) {
40+
int& res = mm[idx];
41+
if (res != -1) return res;
42+
if (idx >= len) return res = 0;
43+
if (isok(idx, len - 1)) return res = 0;
44+
res = 1 + doit(idx + 1);
45+
for (int i = idx + 1; i < len; ++i) {
46+
if (!isok(idx, i)) continue;
47+
res = min(res, 1 + doit(i + 1));
48+
}
49+
return res;
50+
}
51+
int minCut(string _s) {
52+
s = _s;
53+
len = s.length();
54+
if (len <= 1) return 0;
55+
vv.assign(len, vector<int>(len, 0));
56+
for (int i = 0; i < len; ++i) vv[i][i] = 1;
57+
for (int i = 0; i < len - 1; ++i) vv[i][i + 1] = (s[i] == s[i + 1]);
58+
for (int sz = 2; sz < len; ++sz) {
59+
for (int i = 0; i < len - sz; ++i) {
60+
if (s[i] == s[i + sz] && vv[i + 1][i + sz - 1] == 1) vv[i][i + sz] = 1;
61+
}
62+
}
63+
mm.assign(len + 5, -1);
64+
return doit(0);
65+
}
66+
};
67+
68+
int main() {
69+
Solution s = Solution();
70+
cout << s.minCut("dde") << endl;
71+
return 0;
72+
}

‎LeetCode/palindromePartition.cpp‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
class Solution {
2+
public:
3+
string s;
4+
vector<string> t;
5+
vector<vector<string> > res;
6+
bool isok(int st, int ed) {
7+
while (st < ed) {
8+
if (s[st] != s[ed]) return false;
9+
++st;
10+
--ed;
11+
}
12+
return true;
13+
}
14+
void doit(int now) {
15+
if (now >= s.length()) {
16+
res.push_back(t);
17+
return;
18+
}
19+
20+
for (int i = now; i < s.length(); ++i) {
21+
if (isok(now, i)) {
22+
t.push_back(s.substr(now, i - now + 1));
23+
doit(i + 1);
24+
t.pop_back();
25+
}
26+
}
27+
}
28+
vector<vector<string>> partition(string _s) {
29+
s = _s;
30+
res.clear();
31+
t.clear();
32+
doit(0);
33+
return res;
34+
}
35+
};

‎LeetCode/wordBreak.cpp‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
bool wordBreak(string s, unordered_set<string> &dict) {
4+
if (s.empty()) return false;
5+
int len = s.length();
6+
vector<vector<bool> > mm(len, vector<bool>(len, false));
7+
for (int i = 0; i < len; ++i) {
8+
for (int j = i; j < len; ++j) {
9+
if (dict.find(s.substr(i, j - i + 1)) != dict.end()) mm[i][j] = true;
10+
}
11+
}
12+
for (int i = 0; i < len; ++i) {
13+
for (int j = i; j < len; ++j) {
14+
for (int k = i; k < j; ++k) {
15+
if (mm[i][k] && mm[k + 1][j]) mm[i][j] = true;
16+
}
17+
}
18+
}
19+
return mm[0][len - 1];
20+
}
21+
};

0 commit comments

Comments
 (0)