Skip to content

Instantly share code, notes, and snippets.

@songron

songron/3sum_closest.cpp

Last active December 29, 2015 07:49
Show Gist options
  • Save songron/7638718 to your computer and use it in GitHub Desktop.
Save songron/7638718 to your computer and use it in GitHub Desktop.
Download ZIP
LeetCode OnlineJudge. http://oj.leetcode.com/problems/
Raw
3sum_closest.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
void show(int idx[])
{
for (int i=0; i<3; i++)
cout << idx[i] << ' ';
cout << endl;
}
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int c=0, r=0, x=-1, h=0;
int n = num.size();
int idx[3], i=0, k=0;
while (1) {
if (i==3) {
if (c == target)
return c;
else if (c > target && (x==-1 || c-target<x)) {
r = c;
x = c - target;
}
else if (c < target && (x==-1 || target-c<x)) {
r = c;
x = target - c;
}
i--;
c -= num[idx[i]];
}
else {
if (k == n) {
if (i == 0) {
break;
}
i--;
k = idx[i] + 1;
c -= num[idx[i]];
}
else {
idx[i++] = k;
c += num[k++];
}
}
}
return r;
}
};
int main()
{
vector<int> num;
num.push_back(-1);
num.push_back(2);
num.push_back(2);
num.push_back(1);
num.push_back(2);
int t=4;
Solution so;
int r = so.threeSumClosest(num, t);
cout << r << endl;
return 0;
}
Raw
add_binary.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
string addBinary(string a, string b) {
string r;
int n=a.length(), m=b.length();
int x, ac=0;
int i, j;
for (i=n-1, j=m-1; i>=0 || j>=0; i--, j--) {
x = ac;
if (i >= 0)
x += a[i] - '0';
if (j >= 0)
x += b[j] - '0';
r.insert(0, 1, x%2+'0');
ac = x / 2;
}
if (ac == 1)
r.insert(0, 1, '1');
return r;
}
};
int main()
{
string a, b;
cin >> a >> b;
Solution so;
string r = so.addBinary(a, b);
cout << r << endl;
return 0;
}
Raw
add_two_numbsers.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *p1, *p2, *p, *q, *r, *head=NULL;
p1 = l1;
p2 = l2;
int a=0, x=0;
while (p1 || p2) {
x = a;
if (p1) {
x += p1->val;
p1 = p1->next;
}
if (p2) {
x += p2->val;
p2 = p2->next;
}
q = new ListNode(x % 10);
a = x / 10;
if (!head) {
head = p = q;
}
else {
p->next = q;
p = q;
}
}
if (a > 0) {
q = new ListNode(a);
p->next = q;
}
return head;
}
};
void show(ListNode *p)
{
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *l1, *l2;
l1 = new ListNode(2);
l1->next = new ListNode(4);
l1->next->next = new ListNode(3);
show(l1);
l2 = new ListNode(5);
l2->next = new ListNode(6);
l2->next->next = new ListNode(4);
show(l2);
Solution so;
ListNode *r = so.addTwoNumbers(l1, l2);
show(r);
return 0;
}
Raw
anagrams.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <tr1/unordered_map>
#include <algorithm>
using namespace std;
class Solution {
private:
struct Anag {
string s;
string a;
Anag (string s1, string s2) : s(s1), a(s2) {};
} ;
public:
static bool cmp(Anag *an1, Anag *an2) {
return (an1->a) < (an2->a);
}
vector<string> anagrams(vector<string> &strs) {
vector<string> res;
int n=strs.size();
if (n <= 1)
return res;
vector<Anag*> anags;
Anag *p = NULL;
for (int i=0; i<n; i++) {
string a = strs[i];
sort(a.begin(), a.end());
p = new Anag(strs[i], a);
anags.push_back(p);
}
sort(anags.begin(), anags.end(), cmp);
for (int i=0; i<n; i++) {
if ((i<n-1 && anags[i]->a==anags[i+1]->a) || (i>0 && anags[i]->a==anags[i-1]->a))
res.push_back(anags[i]->s);
}
return res;
}
};
int main()
{
Solution so;
return 0;
}
Raw
backward.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
#include <vector>
using namespace std;
/*
* 一个回溯算法的例子：
* 一共m 行，每行n 个数，要求从每行选择一个数组成一个m 个元素的数组；
* 问有几种选法。
* 输出： 对于每种选法，输出所选数字的下标集合.
*/
void show(vector<int> vec)
{
for (int i=0; i<vec.size(); i++)
cout << vec[i] << ' ';
cout << endl;
}
void backward(int m, int n)
{
vector<int> vec(m, 0);
int i, k;
i = k = 0;
while (1) {
if (k == m) { // 得到一个结果
show(vec);
// 开始回溯
do {
k--;
i = vec[k] + 1;
} while (i >= n && k > 0);
if (i >= n)
break;
}
vec[k++] = i;
i=0;
}
}
int main()
{
int m, n;
cin >> m >> n;
backward(m, n);
return 0;
}
Raw
balanced_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 还可以提高效率吗？
class Solution {
public:
int bal(TreeNode *left, TreeNode *right, int h) {
if (!left && !right) {
return h;
}
int h1, h2;
h1 = h2 = h;
if (left) {
h1 = bal(left->left, left->right, h+1);
if (h1 == -1)
return -1;
}
if (right) {
h2 = bal(right->left, right->right, h+1);
if (h2 == -1)
return -1;
}
int r;
r = h1 > h2? h1 : h2;
if (r - h1 > 1 || r - h2 > 1)
return -1;
return r;
}
bool isBalanced(TreeNode *root) {
if (!root)
return true;
int r = bal(root->left, root->right, 0);
if (r == -1)
return false;
return true;
}
};
int main()
{
TreeNode *root;
root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
root->right->left = new TreeNode(3);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(2);
root->left->left->right = new TreeNode(2);
Solution so;
bool r = so.isBalanced(root);
cout << r << endl;
return 0;
}
Raw
basic.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
};
int main()
{
Solution so;
return 0;
}
Raw
binary_tree_maximum_path_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {};
};
// 贪心：类似于最大连续子段和的题目
// 求以每个结点为"转轴" 的路径的最大和
// 取其中最大的一个
// 注意："转轴"最多只能有一个 !
class Solution {
private:
int max_sum;
int nodeSum(TreeNode *node) {
if (!node) return 0;
int sum = node->val;
int left = nodeSum(node->left);
int right = nodeSum(node->right);
if (left > 0)
sum += left;
if (right > 0)
sum += right;
max_sum = sum > max_sum ? sum : max_sum;
int part_sum = node->val;
if (left > 0 || right > 0)
part_sum += left > right ? left : right;
return part_sum;
}
public:
int maxPathSum(TreeNode *root) {
max_sum = INT_MIN;
nodeSum(root);
return max_sum;
}
};
int main()
{
Solution so;
return 0;
}
Raw
buy_stock.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.begin() == prices.end())
return 0;
int maxp=0, p, sell, buy;
buy = *(prices.begin());
for(vector<int>::iterator it=prices.begin()+1; it!=prices.end(); ++it) {
p = *it - buy;
if (p > maxp)
maxp = p;
if (*it < buy)
buy = *it;
}
return maxp;
}
};
void show(vector<int> vec)
{
for (vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
vector<int> prices;
srand(time(0));
int val;
for (int i=0; i<10; i++) {
val = rand() % 100 + 1;
prices.push_back(val);
}
show(prices);
Solution so;
int r = so.maxProfit(prices);
cout << r << endl;
return 0;
}
Raw
buy_stock2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n=prices.size();
if (n < 2)
return 0;
int p=0, i=0, j=0;
int buy=prices[0], sell;
for (int i=1; i<n; i++) {
if (prices[i] < prices[i-1]) {
p += prices[i-1] - buy;
buy = prices[i];
}
}
if (prices[n-1] > buy)
p += prices[n-1] - buy;
return p;
}
};
void show(vector<int> vec)
{
for (vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
return 0;
}
Raw
buy_stock3.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n=prices.size();
if (n < 2)
return 0;
int r=0, p=0, ma=0, mi=0;
vector<int> pros(n, 0);
ma = prices[n-1];
for (int i=n-2; i>=0; i--) {
if (prices[i] > ma) {
ma = prices[i];
pros[i] = pros[i+1];
}
else {
p = ma - prices[i];
if (p > pros[i+1])
pros[i] = p;
else
pros[i] = pros[i+1];
}
}
r = pros[0];
mi = prices[0];
for (int i=1; i<n-1; i++) {
if (prices[i] < mi)
mi = prices[i];
else {
p = prices[i] - mi + pros[i+1];
if (p > r)
r = p;
}
}
return r;
}
};
void show(vector<int> vec)
{
for (vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
return 0;
}
Raw
candy.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int candy(vector<int> &ratings) {
int n=ratings.size();
vector<int> cans(n);
for (int i=1; i<n; i++) {
if (ratings[i] > ratings[i-1])
cans[i] = cans[i-1]+1;
}
for (int i=n-1; i>0; i--) {
if (ratings[i] < ratings[i-1])
cans[i-1] = max(cans[i-1], cans[i]+1);
}
int res=n;
for (int i=0; i<n; i++)
res += cans[i];
return res;
}
};
int main()
{
Solution so;
vector<int> rates;
int x;
for (int i=0; i<5; i++) {
cin >> x;
rates.push_back(x);
}
x = so.candy(rates);
cout << x << endl;
return 0;
}
Raw
climb_stairs.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 这个方法太丑陋，见solution2
class Solution {
public:
int select(int m, int n) {
int up=1, down=1;
if (n > m/2)
n = m-n;
int facs[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51};
for (; n>=1; n--, m--) {
up *= m;
down *= n;
if (up > 100000) {
for (int i=0; i<17; i++) {
// 防止溢出
while (up%facs[i]==0 && down%facs[i]==0) {
up /= facs[i];
down /= facs[i];
}
}
}
}
return up / down;
}
int climbStairs(int n) {
int r = 0, one, two;
two = n/2;
one = n - two * 2;
while (two >= 0) {
r += select(one+two, one);
two -= 1;
one += 2;
}
return r;
}
};
/*
* 对于n 级台阶 foo(n) 的第一步:
* 可能爬一个， 剩余的为 foo(n-1);
* 也可能爬2个, 剩余的为 foo(n-2);
* 所以foo(n) = foo(n-1) + foo(n-2); 这也就是斐波那契数列
*/
class Solution2 {
public:
// 递归方法太慢，会超时
/*
int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
return climbStairs(n-1) + climbStairs(n-2);
}
*/
int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
int r, lr, llr;
llr = 1;
lr = 2;
for (int i=3; i<=n; i++) {
r = lr + llr;
llr = lr;
lr = r;
}
return r;
}
};
// 斐波那契数列的更高效算法
// 将斐波那契数列化解为数幂的形式
// 复杂度降为： C*log(n), C 是常数
// 即 pow(m, n) 的复杂度为 log(n)
class Solution3 {
public:
vector<int> multi(vector<int> x, vector<int> y) {
vector<int> r(4, 0);
r[0] = x[0]*y[0] + x[1]*y[2];
r[1] = x[0]*y[1] + x[1]*y[3];
r[2] = x[2]*y[0] + x[3]*y[2];
r[3] = x[2]*y[1] + x[3]*y[3];
return r;
}
int climbStairs(int n) {
vector<int> mat(4, 1);
mat[0] = 0; // mat: 0, 1, 1, 1
vector<int> r(4, 1);
r[1] = r[2] = 0; // r: 1, 0, 0, 1
// pow(mat, n);
while (n) {
if (n%2 == 1)
r = multi(r, mat);
mat = multi(mat, mat);
n /= 2;
}
return r[3];
}
};
int main()
{
int n;
cin >> n;
Solution3 so;
int r = so.climbStairs(n);
cout << r << endl;
return 0;
}
Raw
clone_graph.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
#include <vector>
#include <tr1/unordered_map>
using namespace std;
struct UndirectedGraphNode {
int label;
vector<UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {};
};
// 深度优先搜索，递归实现
class Solution {
private:
// map cloned: 将原图结点与新图结点对应起来
tr1::unordered_map<const UndirectedGraphNode*, UndirectedGraphNode*> cloned;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node)
return NULL;
if (cloned.find(node) != cloned.end())
return cloned[node];
UndirectedGraphNode *nd;
nd = new UndirectedGraphNode(node->label);
cloned[node] = nd;
for (int i=0; i<node->neighbors.size(); i++) {
nd->neighbors.push_back(cloneGraph(node->neighbors[i]));
}
return nd;
}
};
int main()
{
Solution so;
return 0 ;
}
Raw
combination_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> get_values(vector<int> &candidates, vector<int> now) {
vector<int> value;
for (vector<int>::const_iterator it=now.begin(); it!=now.end(); ++it)
value.push_back(candidates[*it]);
return value;
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int> > res;
vector<int> now;
sort(candidates.begin(), candidates.end());
int n=candidates.size();
int cur=0, i=0;
while (i < n || !now.empty()) {
if (i >= n) {
i = *(now.end()-1) + 1;
cur -= candidates[*(now.end()-1)];
now.pop_back();
}
else if (cur == target) {
vector<int> value = get_values(candidates, now);
res.push_back(value);
if (now.size() < 2)
break;
cur -= *(value.end()-1) + *(value.end()-2);
i = *(now.end()-2) + 1;
now.pop_back();
now.pop_back();
}
else if (cur + candidates[i] > target) {
if (now.empty())
break;
else {
i = *(now.end()-1) + 1;
cur -= candidates[*(now.end()-1)];
now.pop_back();
}
}
else {
cur += candidates[i];
now.push_back(i);
}
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> cans;
cans.push_back(1);
cans.push_back(2);
int target = 4;
Solution so;
vector<vector<int> > res = so.combinationSum(cans, target);
show(res);
return 0;
}
Raw
combination_sum2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 回溯,搜索
class Solution {
public:
vector<int> get_values(vector<int> &num, vector<int> now) {
vector<int> value;
for (vector<int>::const_iterator it=now.begin(); it!=now.end(); ++it)
value.push_back(num[*it]);
return value;
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int> > res;
vector<int> now;
sort(num.begin(), num.end());
int n=num.size();
int cur=0, i=0;
while (i < n || !now.empty()) {
if (cur == target) {
vector<int> value = get_values(num, now);
res.push_back(value);
}
if (i >= n || cur + num[i] > target) {
if (now.empty()) break;
int j = *(now.end()-1);
cur -= num[j];
now.pop_back();
i = j + 1;
while (i < n && num[i] == num[j])
i++;
}
else {
cur += num[i];
now.push_back(i);
++i;
}
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> cans;
cans.push_back(8);
int target = 8;
Solution so;
vector<vector<int> > res = so.combinationSum2(cans, target);
show(res);
return 0;
}
Raw
combinations.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > res;
int i=0, j=1;
vector<int> idx;
while (1) {
if (idx.size() == k) {
res.push_back(idx);
idx.pop_back();
}
else {
if (j == n+1) {
if (idx.empty())
break;
j = *(idx.end()-1) + 1;
idx.pop_back();
}
else
idx.push_back(j++);
}
}
return res;
}
};
int main()
{
Solution so;
return 0;
}
Raw
commit.cpp
class Solution {
private:
vector<vector<string> > genRes(unordered_map<string, vector<string> > &parents, \
string start, string end)
{
vector<vector<string> > res;
unordered_map<string, vector<string> >::const_iterator it = parents.find(end);
if (end == start) {
res.push_back(vector<string>(1, start));
return res;
}
for (int i=0; i < parents[end].size(); ++i) {
vector<vector<string> > tmp;
tmp = genRes(parents, start, parents[end][i]);
for (int j=0; j<tmp.size(); j++) {
tmp[j].push_back(end);
res.push_back(tmp[j]);
}
}
return res;
}
public:
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
vector<vector<string> > res;
queue<string> q;
q.push(start);
bool found = false;
// 保存某一个单词是由哪个词变换而来的
// 用于生成最终结果
unordered_map<string, vector<string> > parents;
dict.erase(start);
while (!q.empty()) {
queue<string> nextq;
unordered_set<string> added;
while (!q.empty()) { // here !!
string s=q.front(); q.pop();
for (int i=0; i<s.length(); i++) {
for (char c='a'; c<='z'; c++) {
if (c == s[i]) continue;
string t = s; t[i] = c;
// 此时不可能再得到最短的
if (found && t != end) continue ;
if (t == end) {
found = true;
parents[end].push_back(s);
break ;
}
unordered_set<string>::const_iterator it = dict.find(t);
if (it != dict.end()) {
if (added.find(t) == added.end()) {
nextq.push(t); added.insert(t);
}
parents[t].push_back(s);
}
}
// 如果是由 "t == end" 跳转而来的，则break ;
if (found && s == *(parents[end].end()-1)) break;
}
}
if (found) break;
q = nextq;
// 出现在当前层的词不可能再在后续层出现
while (!nextq.empty()) {
dict.erase(nextq.front());
nextq.pop();
}
}
res = genRes(parents, start, end);
return res;
}
};
Raw
construct_BT_from_post_in_order.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode *halfTree(vector<int> &posto, vector<int> &ino, int ip, int ii, int n) {
TreeNode *root;
root = new TreeNode(posto[ip+n-1]);
int i, m, m2;
for (i=ii; i<ii+n; i++)
if (ino[i] == posto[ip+n-1])
break;
m = i - ii;
if (m > 0)
root->left = halfTree(posto, ino, ip, ii, m);
m2 = n - m - 1;
if (m2 > 0)
root->right = halfTree(posto, ino, ip+m, i+1, m2);
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
int n=postorder.size();
if (n == 0)
return NULL;
TreeNode *root;
root = halfTree(postorder, inorder, 0, 0, n);
return root;
}
};
void recursive(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive(root->left);
recursive(root->right);
}
int main()
{
vector<int> posto, ino;
posto.push_back(4);
posto.push_back(2);
posto.push_back(3);
posto.push_back(1);
ino.push_back(2);
ino.push_back(4);
ino.push_back(1);
ino.push_back(3);
Solution so;
TreeNode *root = so.buildTree(ino, posto);
recursive(root);
cout << endl;
return 0;
}
Raw
construct_BT_from_pre_in_order.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode *halfTree(vector<int> &preo, vector<int> &ino, int ip, int ii, int n) {
TreeNode *root;
root = new TreeNode(preo[ip]);
int i, m, m2;
for (i=ii; i<ii+n; i++)
if (ino[i] == preo[ip])
break;
m = i - ii;
if (m > 0)
root->left = halfTree(preo, ino, ip+1, ii, m);
m2 = n - m - 1;
if (m2 > 0)
root->right = halfTree(preo, ino, ip+m+1, i+1, m2);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int n=preorder.size();
if (n == 0)
return NULL;
TreeNode *root;
root = halfTree(preorder, inorder, 0, 0, n);
return root;
}
};
void recursive(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive(root->left);
recursive(root->right);
}
int main()
{
vector<int> preo, ino;
preo.push_back(1);
preo.push_back(2);
preo.push_back(4);
preo.push_back(100);
ino.push_back(2);
ino.push_back(4);
ino.push_back(1);
ino.push_back(100);
Solution so;
TreeNode *root = so.buildTree(preo, ino);
recursive(root);
cout << endl;
return 0;
}
Raw
convert_binary_search_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode *bst(vector<int> &num, int i, int j) {
TreeNode *p, *l, *r;
int m = (i + j) / 2;
p = new TreeNode(num[m]);
if (m-1 >= i)
p->left = bst(num, i, m-1);
if (m+1 <= j)
p->right = bst(num, m+1, j);
return p;
}
TreeNode *sortedArrayToBST(vector<int> &num) {
TreeNode *root = NULL;
int n;
n = num.size();
if (n == 0)
return root;
root = bst(num, 0, n-1);
return root;
}
};
void show(TreeNode *root)
{
if (!root)
return ;
cout << root->val << ' ';
show(root->left);
show(root->right);
}
int main()
{
TreeNode *root;
vector<int> num;
for (int i=0; i<10; i++)
num.push_back(i+1);
cout << num.size() << endl;
Solution so;
root = so.sortedArrayToBST(num);
show(root);
cout << endl;
return 0;
}
Raw
convert_list_to_binary_search_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode *bst(ListNode *head, int n) {
ListNode *mid = head;
for (int i=0; i<n/2; i++)
mid = mid->next;
TreeNode *root = new TreeNode(mid->val);
if (n/2 > 0)
root->left = bst(head, n/2);
if (n - n/2 - 1 > 0)
root->right = bst(mid->next, n-n/2-1);
return root;
}
TreeNode *sortedListToBST(ListNode *head) {
TreeNode *root = NULL;
if (!head)
return root;
ListNode *h;
int n=0;
h = head;
while (h) {
n++;
h = h->next;
}
root = bst(head, n);
return root;
}
};
void show(TreeNode *root)
{
if (!root)
return ;
cout << root->val << ' ';
show(root->left);
show(root->right);
}
int main()
{
TreeNode *root = NULL;
ListNode *head = NULL;
Solution so;
root = so.sortedListToBST(head);
return 0;
}
Raw
copy_list_with_random_pointer.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
#include <string>
struct RandomListNode {
int label;
RandomListNode *next, *random;
RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};
// 把新链表交叉地插入旧链表，然后再拆分
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head)
return NULL;
RandomListNode *p, *q;
for (RandomListNode *cur=head; cur!=NULL; ) {
q = new RandomListNode(cur->label);
q->next = cur->next;
cur->next = q;
cur = q->next;
}
for (RandomListNode *cur=head; cur!=NULL; ) {
if (cur->random)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
p = head;
q = head->next;
RandomListNode *res = q;
while (p) {
p->next = q->next;
p = p->next;
if (p) {
q->next = p->next;
q = q->next;
}
else
break;
}
return res;
}
};
int main()
{
RandomListNode *head=NULL, *p, *q, *r;
Solution so;
r = so.copyRandomList(head);
return 0;
}
Raw
count_and_say.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
string mystr(int n) {
string s;
if (n < 10)
s.append(1, n+'0');
else {
s = mystr(n/10);
s.append(1, n%10+'0');
}
return s;
}
string countAndSay(int n) {
string s, r;
r = "1";
for (int i=1; i<n; i++) {
s = r;
r = "";
int c = 1, sn=s.length();
for (int j=1; j<sn; j++) {
if (s[j] == s[j-1])
c++;
else {
r.append(mystr(c));
r.append(1, s[j-1]);
c = 1;
}
}
r.append(mystr(c));
r.append(1, s[sn-1]);
}
return r;
}
};
int main()
{
int n;
cin >> n;
Solution so;
string r = so.countAndSay(n);
cout << r << endl;
return 0;
}
Raw
decode_ways.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
// 参数s 有可能是非法的，即不可以被decode;
// 动态规划：标技术组D[n] ;
// D[i] 表示 s[0..i] 有多少种decode 方式;
class Solution {
public:
int numDecodings(string s) {
int n=s.size();
if (n == 0)
return 0;
if (s[0] == '0')
return 0;
int D[n];
memset(D, 0, n*4); // 1 int = 4 bytes
D[0] = 1;
for (int i=1; i<n; i++) {
if (s[i] == '0' && s[i-1] == '0')
return 0;
if (s[i] != '0')
D[i] += D[i-1];
if (s[i-1] != '0' && 10*(s[i-1]-'0')+s[i]-'0' <= 26) {
if (i == 1)
D[i] += 1;
else
D[i] += D[i-2];
}
}
return D[n-1];
}
};
int main()
{
string s;
cin >> s;
Solution so;
cout << so.numDecodings(s) << endl;
return 0;
}
Raw
distinct_subsequences.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/distinct-subsequences/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// TIME LIMIT EXCEEDED
// Seee Solution2
class Solution {
public:
int numDistinct(string S, string T) {
int i=0, k=0, r=0;
int m=S.length(), n=T.length();
vector<int> idx(n, 0);
while (1) {
if (i == n) {
r += 1;
i -= 1;
}
while (k<m && S[k]!=T[i])
k++;
if (k == m) {
if (i > 0) {
i -= 1;
k = idx[i] + 1;
}
else
break;
}
else
idx[i++] = k++;
}
return r;
}
};
class Solution2 {
public:
int numDistinct(string S, string T) {
int m=S.size(), n=T.size();
if (n == 0 || m < n)
return 0;
int R[m][n];
/*
* R[i][j] 记录S[0..i] 包含多少个T[0..j]
* 当S[i] == T[j]时，可以分为 S[i] 和 T[j] 对齐和不对齐两种情况。
* 所以 R[i][j]=R[i-1][j-1] + R[i-1][j]
* 注意边界情况的判定。
*/
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
R[i][j] = 0;
if (i >= j) {
if (S[i] == T[j]) {
if (i > 0 && j > 0)
R[i][j] = R[i-1][j-1] + R[i-1][j];
else if (i > 0)
R[i][j] = R[i-1][j] + 1;
else // i == j == 0
R[i][j] = 1;
}
else {
if (i > 0)
R[i][j] = R[i-1][j];
else
R[i][j] = 0;
}
}
}
}
return R[m-1][n-1];
}
};
int main()
{
string s, t;
cin >> s >> t;
Solution2 so;
int r = so.numDistinct(s, t);
cout << r << endl;
return 0;
}
Raw
divide_two_integers.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
// 特别注意溢出问题，正负数问题
int divide(int dividend, int divisor) {
const int MIN = -2147483648;
const int HALF = 1073741823;
int flag = 1;
bool isMin=false;
if (dividend < 0) {
if (dividend == MIN) {
if (divisor == 1)
return MIN;
isMin=true;
dividend += 1;
}
flag *= -1;
dividend = -dividend;
}
if (divisor < 0) {
if (divisor == MIN) {
if (isMin)
return 1;
return 0;
}
flag *= -1;
divisor = -divisor;
}
if (divisor == 1)
return flag * dividend;
if (dividend < divisor)
return 0;
int r=0, m=1, i=0;
int dds[32], rs[32];
if (isMin && dividend >= divisor) {
dividend -= (divisor - 1);
r = 1;
}
while (dividend >= divisor) {
dds[i] = divisor;
rs[i++] = m;
if (divisor > HALF)
break;
divisor += divisor;
m += m;
}
for (--i; i>=0 && dividend >= dds[0]; i--) {
if (dds[i] <= dividend) {
dividend -= dds[i];
r += rs[i];
}
}
return r * flag;
}
};
int main()
{
int d1, d2;
cin >> d1 >> d2;
Solution so;
int r=so.divide(d1, d2);
cout << r << endl;
return 0;
}
Raw
edit_distance.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int minDistance(string word1, string word2) {
int n1=word1.length(), n2=word2.length();
vector<vector<int> > R;
vector<int> vec;
for (int i=0; i<=n2; i++)
vec.push_back(0);
for (int i=0; i<=n1; i++)
R.push_back(vec);
for (int i=0; i<=n1; i++)
R[i][0] = i;
for (int i=0; i<=n2; i++)
R[0][i] = i;
for (int i=1; i<=n1; i++) {
for (int j=1; j<=n2; j++) {
if (word1[i-1] == word2[j-1]) {
R[i][j] = R[i-1][j-1];
continue;
}
R[i][j] = R[i-1][j] + 1;
if (R[i][j-1] < R[i-1][j])
R[i][j] = R[i][j-1] + 1;
if (R[i-1][j-1]+1 < R[i][j])
R[i][j] = R[i-1][j-1] + 1;
}
}
return R[n1][n2];
}
};
int main()
{
string s1, s2;
cin >> s1 >> s2;
Solution so;
int r = so.minDistance(s1, s2);
cout << r << endl;
return 0;
}
Raw
eval_reverse_polish_notation.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int evalRPN(vector<string> &tokens) {
int r=0, n=tokens.size();
stack<int> nums;
int n1, n2, len;
for (int i=0; i<n; i++) {
len = tokens[i].length();
if (len>1 || (tokens[i][0] >= '0' && tokens[i][0] <= '9')) {
int m=0, j=0, flag=1;
if (tokens[i][0] == '-') {
flag = -1;
j = 1;
}
else if (tokens[i][0] == '+')
j = 1;
for (; j<len; j++) {
m = m * 10 + tokens[i][j] - '0';
}
m *= flag;
nums.push(m);
}
else {
n2 = nums.top();
nums.pop();
n1 = nums.top();
nums.pop();
if (tokens[i][0] == '+') {
nums.push(n1+n2);
}
else if (tokens[i][0] == '-') {
nums.push(n1-n2);
}
else if (tokens[i][0] == '*') {
nums.push(n1*n2);
}
else if (tokens[i][0] == '/') {
nums.push(n1/n2);
}
}
}
r = nums.top();
nums.pop();
return r;
}
};
int main()
{
vector<string> vec;
vec.push_back("4");
vec.push_back("13");
vec.push_back("5");
vec.push_back("/");
vec.push_back("+");
Solution so;
int r = so.evalRPN(vec);
cout << r << endl;
return 0;
}
Raw
first_missing_positive.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
class Solution {
public:
int firstMissingPositive(int A[], int n) {
tr1::unordered_map<int, bool> used;
for (int i=0; i<n; i++)
used[A[i]] = false;
for (int i=0; i<n; i++) {
if (used.find(i+1) == used.end())
return i+1;
}
return n+1;
}
};
int main()
{
Solution so;
return 0;
}
Raw
flatten_binaty_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void flatten(TreeNode *root) {
TreeNode *p, *q=NULL;
stack<TreeNode*> bstack;
p = root;
while (p != NULL) {
if (!q)
q = p;
else {
q->right = p;
q = p;
}
if (p->right != NULL)
bstack.push(p->right);
if (p->left != NULL) {
p = p->left;
q->left = NULL;
}
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
}
}
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
void show(TreeNode *root)
{
while (root) {
cout << root->val << ' ';
root = root->right;
}
cout << endl;
}
int main()
{
TreeNode *root;
root = new TreeNode(10);
root->left = NULL;
root->right = new TreeNode(20);
Solution so;
so.flatten(root);
show(root);
cout << endl;
recursive_so(root);
cout << endl;
return 0;
}
Raw
four_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
using namespace std;
// TIME LIMIT EXCEED
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > res;
const int n=num.size();
if (n < 4) return res;
sort(num.begin(), num.end());
vector<int> vec(4);
vector<int> idx(4, 0);
int i=0, k=0, sum=0;
while (k > 0 || i < n) {
if (k == 4) {
if (sum == target) {
vec[0]=num[idx[0]]; vec[1]=num[idx[1]]; vec[2]=num[idx[2]]; vec[3]=num[idx[3]];
res.push_back(vec);
}
}
if (k == 4 || i >= n || sum + num[i] > target) {
if (k == 0) break;
int j = idx[--k];
sum -= num[j];
i = j + 1;
while (i < n && num[i] == num[j]) i++;
}
else {
sum += num[i];
idx[k++] = i++;
}
}
return res;
}
};
// 复杂度：O(n^3)
class Solution2 {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > res;
const int n=num.size();
if (n < 4) return res;
sort(num.begin(), num.end());
vector<int> vec(4);
int r=0;
for (int i=0; i<n-3; i++) {
if (i > 0 && num[i] == num[i-1]) continue;
for (int j=i+1; j<n-2; j++) {
if (j > i+1 && num[j] == num[j-1]) continue;
r = target - num[i] - num[j];
for (int k=j+1, l=n-1; k<l; ) {
if (k > j+1 && num[k] == num[k-1]) { k++; continue; }
if (l < n-1 && num[l] == num[l+1]) { l--; continue; }
if (num[k] + num[l] < r)
k++;
else if (num[k] + num[l] > r)
l--;
else {
vec[0]=num[i];
vec[1]=num[j];
vec[2]=num[k];
vec[3]=num[l];
res.push_back(vec);
k++;
l--;
}
}
}
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
int target, x;
vector<int> num;
cin >> target;
while (cin >> x)
num.push_back(x);
Solution2 so;
vector<vector<int> > res = so.fourSum(num, target);
show(res);
return 0;
}
Raw
gas_station.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int n;
n = gas.size();
if (n == 0)
return -1;
int tank=0, start=0, i=0, j;
// time: O(n)
do {
tank += gas[i] - cost[i];
if (tank < 0) { // wrong start, go back
j = (n + start - 1) % n;
while (j != i) {
tank += gas[j] - cost[j];
if (tank >= 0) { // find a better start
start = j;
break;
}
j = (n + j - 1) % n;
}
if (j == i) // we cannot find a solution; make sure T=O(n)
return -1;
}
i = (i + 1) % n;
} while (i != start);
return start;
}
};
int main()
{
vector<int> gas, cost;
for (int i=0; i<10; i++) {
cost.push_back(10-i);
gas.push_back(i+1);
}
Solution so;
int r = so.canCompleteCircuit(gas, cost);
cout << r << endl;
return 0;
}
Raw
generate_parentheses.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
string gen(vector<int> notes, int n) {
string s;
int k=0;
for (int i=0; i<n-1; i++) {
s.append(1, '(');
for (int j=0; j<notes[i]; j++, k++)
s.append(1, ')');
}
s.append(1, '(');
while (k < n) {
s.append(1, ')');
k++;
}
return s;
}
vector<string> generateParenthesis(int n) {
vector<string> res;
if (n == 1) {
res.push_back("()");
return res;
}
vector<int> notes(n-1, 0);
string s;
int i, k, m;
i = k = m = 0;
while (1) {
if (i == n-1) {
s = (gen(notes, n));
res.push_back(s);
do {
i--;
m -= notes[i];
k = notes[i] + 1;
} while (m+k > i+1 && i>0);
if (m+k > i+1)
break;
}
notes[i++] = k;
m += k;
k = 0;
}
return res;
}
};
int main()
{
int n;
cin >> n;
Solution so;
so.generateParenthesis(n);
return 0;
}
Raw
gray_code.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<int> __grayCode(int n) {
vector<int> r, ws;
r.push_back(0);
if (n == 0)
return r;
ws.push_back(1);
for (int i=1, w=1; i<n; i++) {
w *= 2;
ws.push_back(w);
}
int i=0, g=0, c=1;
while (c < ws[n-1] * 2) {
if (!(g & ws[i])) {
g += ws[i];
}
else {
if (i>0 && g&ws[i-1])
g -= ws[i-1];
else {
i = (i + 1) % n;
g += ws[i];
}
}
r.push_back(g);
c++;
}
return r;
}
// beautiful, clear, simple codes
vector<int> grayCode(int n) {
vector<int> r;
r.push_back(0);
for (int i=0, w=1; i<n; i++) {
for (int j=r.size()-1; j>=0; j--) {
r.push_back(r[j] + w);
}
w *= 2;
}
return r;
}
};
void show(vector<int> r)
{
for (vector<int>::iterator it=r.begin(); it!=r.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
int n;
cin >> n;
Solution so;
vector<int> r = so.grayCode(n);
show(r);
return 0;
}
Raw
inorder_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
vector<int> res;
p = root;
while (p != NULL) {
bstack.push(p);
if (p->left) {
p = p->left;
}
else {
do {
p = bstack.top();
bstack.pop();
res.push_back(p->val);
p = p->right;
} while (!p && !bstack.empty());
}
}
return res;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
recursive_so(root->left);
cout << root->val << ' ';
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root, *p, *left, *right, *q;
for (int i=0; i<10; i++) {
if (i==0) {
p = new TreeNode(i+1);
root = p;
}
left = new TreeNode((i+1) * 10);
right = new TreeNode((i+1) * 15);
p->left = left;
p->right = right;
if (i % 3 == 0)
p = p->left;
else
p = p->right;
}
vector<int> res;
Solution so;
res = so.inorderTraversal(root);
show(res);
recursive_so(root);
cout << endl;
return 0;
}
Raw
insert_interval.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/merge-intervals/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
void show(vector<Interval> vec)
{
int n=vec.size();
for (int i=0; i<n; i++)
cout << vec[i].start << ' ' << vec[i].end << endl;
}
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
int n=intervals.size();
if (n == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, st=newInterval.start, en=newInterval.end;
while (i<n && st >= intervals[i].start)
i++;
// 直接插入一个新区间，不需其他处理
if (en < intervals[0].start ||
st > intervals[n-1].end ||
(i>0 && st > intervals[i-1].end && en < intervals[i].start)
) {
intervals.insert(intervals.begin()+i, newInterval);
return intervals;
}
int j;
j = i > 0 ? i-1 : 0;
while (j<n && en >= intervals[j].end)
j++;
// 已经包含在某个现有集合内
if (j < i)
return intervals;
// 确定左边界位置及大小
if (i>0 && st <= intervals[i-1].end) // 左边界在区间i-1 的左边界
i--;
else // 左边界在区间i 的新左边界，是st
intervals[i].start = st;
// 确定右边界位置及大小
if (j == n || en < intervals[j].start) { // 右边界在区间j-1 的新右边界
j--;
intervals[j].end = en;
}
else ; // 右边界在区间j 的右边界, 什么都不做
intervals[i].end = intervals[j].end;
intervals.erase(intervals.begin()+i+1, intervals.begin()+j+1);
return intervals;
}
};
int main()
{
vector<Interval> input;
Interval i1(1,5), i2(2, 3);
input.push_back(i1);
Solution so;
so.insert(input, i2);
return 0;
}
Raw
insert_sort.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode *p = NULL, *pl = NULL, *q = NULL, *ql = NULL;
p = head;
while (p != NULL) {
q = head;
while (1) {
if (q == p) {
pl = p;
p = p->next;
break;
}
if (q->val > p->val) {
if (q==head) {
head = p;
}
else {
ql->next = p;
}
pl->next = p->next;
p->next = q;
p = pl->next;
break;
}
ql = q;
q = q->next;
}
}
return head;
}
};
void show(ListNode *head)
{
ListNode *p = head;
while (p != NULL) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *head, *p, *q;
int val;
srand(time(0));
for (int i=0; i<10; i++) {
val = rand() % 100 + 1;
q = new ListNode(val);
if (i == 0) {
head = q;
p = q;
}
else {
p->next = q;
p = q;
}
}
show(head);
Solution so;
head = so.insertionSortList(head);
show(head);
return 0;
}
Raw
integer2roman.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
* I - 1
* V - 5
* X - 10
* L - 50
* C - 100
* D - 500
* M - 1000
*/
class Solution {
public:
string intToRoman(int num) {
int W[] = {1000, 500, 100, 50, 10, 5, 1};
char R[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
string s;
for (int i=0; i<7 && num>0; i++) {
while (num >= W[i]) {
num -= W[i];
s.append(1, R[i]);
}
if (R[i] == 'M' || R[i] == 'D') {
if (num >= W[i] - 100) {
num -= W[i] - 100;
s.append(1, 'C');
s.append(1, R[i]);
}
}
else if (R[i] == 'C' || R[i] == 'L') {
if (num >= W[i] - 10) {
num -= W[i] - 10;
s.append(1, 'X');
s.append(1, R[i]);
}
}
else if (R[i] == 'X' || R[i] == 'V') {
if (num >= W[i] - 1) {
num -= W[i] - 1;
s.append(1, 'I');
s.append(1, R[i]);
}
}
}
return s;
}
};
int main()
{
int n;
cin >> n;
Solution so;
string r = so.intToRoman(n);
cout << r << endl;
return 0;
}
Raw
interleaving_string.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
/*
* 动态规划：
* R[i][j] 表示s1[0..i-1] 和 s2[0..j-1] 能否构成 s3[0..i+j-1]
*/
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1=s1.length(), n2=s2.length(), n3=s3.length();
if (n1 + n2 != n3) return false;
if (n1 == 0) return s2 == s3;
if (n2 == 0) return s1 == s3;
bool R[n1+1][n2+1];
memset(R, 0, (n1+1)*(n2+1));
R[0][0] = true;
for (int i=1; i<=n2; i++)
R[0][i] = s2.substr(0, i) == s3.substr(0, i);
for (int i=1; i<=n1; i++)
R[i][0] = s1.substr(0, i) == s3.substr(0, i);
for (int i=1; i<=n1; i++) {
for (int j=1; j<=n2; j++) {
if (R[i-1][j] && s1[i-1] == s3[i+j-1])
R[i][j] = true;
else if (R[i][j-1] && s2[j-1] == s3[i+j-1])
R[i][j] = true;
else
R[i][j] = false;
}
}
return R[n1][n2];
}
};
int main()
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
Solution so;
cout << so.isInterleave(s1, s2, s3) << endl;
return 0;
}
Raw
jump_game2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
// 贪心法
// 从初始位置开始向前跳；
// 跳到的下一个位置是：该位置可以延伸到最远, 即 max{i + A[i]}, i为可以达到的下一个位置;·
class Solution {
public:
int jump(int A[], int n) {
int ju=0, k=0;
for (int i=0; i<n-1; ) {
++ju;
if (i + A[i] >= n-1)
return ju;
int j=k+1, m=0; // j = k + 1: 避免无谓的探视
k = i + A[i];
for (; j<=k; j++) {
if (j + A[j] >= n-1)
return ju + 1;
if (j + A[j] > m) {
m = j + A[j];
i = j;
}
}
}
return ju;
}
};
int main()
{
int A[100], n;
cin >> n;
for (int i=0; i<n; i++)
cin >> A[i];
Solution so;
cout << so.jump(A, n) << endl;
return 0;
}
Raw
largest_rectangle_in_histogram.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int res=0, w=0, n=height.size();
int lefts[n], rights[n];
stack<int> st;
lefts[0] = 0;
rights[n-1] = n-1;
st.push(0);
for (int i=1; i<n; i++) {
int j=st.top();
if (height[j] < height[i])
lefts[i] = i;
else {
st.pop();
while (!st.empty()) {
j = st.top();
if (height[j] >= height[i])
st.pop();
else
break;
}
if (st.empty())
lefts[i] = 0;
else
lefts[i] = j+1;
}
st.push(i);
}
while (!st.empty()) st.pop();
st.push(n-1);
for (int i=n-2; i>=0; i--) {
int j=st.top();
if (height[j] < height[i])
rights[i] = i;
else {
st.pop();
while (!st.empty()) {
j = st.top();
if (height[j] >= height[i])
st.pop();
else
break;
}
if (st.empty())
rights[i] = n-1;
else
rights[i] = j-1;
}
st.push(i);
}
res = 0;
for (int i=0; i<n; i++)
if (height[i] * (rights[i] - lefts[i] + 1) > res)
res = height[i] * (rights[i] - lefts[i] + 1);
return res;
}
};
int main()
{
Solution so;
return 0;
}
Raw
LeetCode
http://oj.leetcode.com/problems/
Learning algorithms.
C++ codes.
Raw
length_of_last_word.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int lengthOfLastWord(const char *s) {
int i=0, len=0;
while (s[i] != '\0') {
if (s[i] == ' ') {
while (s[++i] == ' ') ;
if (s[i] != '\0') {
len = 1;
i++;
}
}
else {
len++;
i++;
}
}
return len;
}
};
int main()
{
string ss;
char *s = new char[100];
getline(cin, ss);
for (int i=0; i<ss.length(); i++)
s[i]=ss[i];
Solution so;
int r = so.lengthOfLastWord(s);
cout << r << endl;
return 0;
}
Raw
letter_combinations_of_phone_number.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
string reps[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int lens[] = {3, 3, 3, 3, 3, 4, 3, 4};
vector<string> res;
int n=digits.length();
if (n == 0) {
res.push_back("");
return res;
}
string rep;
rep.append(n, '0');
int i=0, j=0, k=0;
int idx[n];
while (1) {
j = digits[i] - '0' - 2;
if (i == n) {
res.push_back(rep);
}
if (i == n || k==lens[j]) {
if (i == 0)
break;
i--;
k = idx[i] + 1;
}
else {
idx[i] = k;
rep[i] = reps[j][k];
k = 0;
i++;
}
}
return res;
}
};
int main()
{
Solution so;
vector<string> res = so.letterCombinations("23");
cout << res.size() << endl;
return 0;
}
Raw
level_order_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
// vector<int> preorderTraversal(TreeNode *root) {
vector<vector<int> > levelOrder(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> high;
vector<vector<int> > res;
int h=0, ri=-1;
p = root;
while (p != NULL) {
if (ri < h) {
res.push_back(vector<int> (1,p->val));
ri++;
}
else {
res[h].push_back(p->val);
}
if (p->right != NULL) {
bstack.push(p->right);
high.push(h+1);
}
if (p->left != NULL) {
p = p->left;
h++;
}
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
h = high.top();
high.pop();
}
}
return res;
}
};
int main()
{
return 0;
}
Raw
level_order_binary_tree2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
// just reverse levelOrderTop
vector<vector<int> > levelOrderBottom(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> high;
vector<vector<int> > res;
int h=0, ri=-1;
p = root;
while (p != NULL) {
if (ri < h) {
res.push_back(vector<int> (1,p->val));
ri++;
}
else {
res[h].push_back(p->val);
}
if (p->right != NULL) {
bstack.push(p->right);
high.push(h+1);
}
if (p->left != NULL) {
p = p->left;
h++;
}
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
h = high.top();
high.pop();
}
}
vector<int> vec;
for (int i=0, j=ri; i<j; i++, j--) {
vec = res[i];
res[i] = res[j];
res[j] = vec;
}
return res;
}
};
int main()
{
return 0;
}
Raw
linked_cycle.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *p, *q;
if (head == NULL)
return false;
p = head;
q = p->next;
while (p && q) {
if (p == q)
return true;
p = p->next;
if (!q->next) return false;
q = q->next->next;
}
return false;
}
};
int main()
{
ListNode *head, *p, *q;
for (int i=0; i<10; i++) {
q = new ListNode(i+1);
if (i == 0) {
head = q;
}
else {
p->next = q;
}
p = q;
}
p->next = head->next->next;
Solution so;
bool r = so.hasCycle(head);
cout << r << endl;
return 0;
}
Raw
linked_cycle2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *p, *q;
if (head == NULL)
return NULL;
p = head;
q = p->next;
while (p && q) {
if (p == q) {
ListNode *r = head;
while (1) {
do {
if (q == r)
return r;
q = q->next;
} while (q != p);
r = r->next;
}
}
p = p->next;
if (!q->next) return NULL;
q = q->next->next;
}
return NULL;
}
};
int main()
{
ListNode *head, *p, *q;
for (int i=0; i<10; i++) {
q = new ListNode(i+1);
if (i == 0) {
head = q;
}
else {
p->next = q;
}
p = q;
}
p->next = head;
Solution so;
ListNode *r = so.detectCycle(head);
cout << r->val << endl;
return 0;
}
Raw
longest_common_prefix.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
string s;
int n = strs.size(), m=0, l;
vector<int> lens;
for (int i=0; i<n; i++) {
l = strs[i].size();
if (i==0 || l < m)
m = l;
}
for (int i=0; i<m; i++) {
char c = strs[0][i];
int j;
for (j=1; j<n; j++)
if (strs[j][i] != c)
break;
if (j == n)
s.append(1, c);
else
break;
}
return s;
}
};
int main()
{
vector<string> strs;
strs.push_back("abcd");
// strs.push_back("abd");
Solution so;
string s = so.longestCommonPrefix(strs);
cout << s << endl;
return 0;
}
Raw
longest_consecutive_sequence.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
class Solution {
public:
int longestConsecutive(vector<int> &num) {
tr1::unordered_map<int, bool> used;
int n=num.size();
for (int i=0; i<n; i++)
used[num[i]] = false;
int longest=0;
int len=1;
for (int i=0; i<n; i++) {
if (used[num[i]]) continue;
len=1;
for (int right=num[i]+1; used.find(right)!=used.end(); ++right) {
used[right] = true;
++len;
}
for (int left=num[i]-1; used.find(left)!=used.end(); --left) {
used[left] = true;
++len;
}
longest = longest > len? longest: len;
}
return longest;
}
};
int main()
{
Solution so;
return 0;
}
Raw
longest_palindromic_substring.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
if (n <= 1)
return s;
// convert s to ms
// string s not contains '#' or '$'
string ms = "$#";
for (int i=0; i<n; i++){
ms.append(1, s[i]);
ms.append(1, '#');
}
// both sides of ms[i] contain a '#'
// m: length of ms
int m = n * 2 + 2;
// pa[i] recoreds i-centered palindromic substring's right-length
vector<int> pa(m, 0);
// maxi: ms[maxi] is the center point of the longest palindromic substring
// id: ms[id] is the center point of the rightmost palindromic substring
int maxi=0, id=0, mi=id+pa[id];
for (int i=1; i<m; i++) {
if (i >= mi) // ms[i] is outside id-substring
pa[i] = 0;
else { // ms[i] is inside of id-substring
if (pa[2*id-i] == pa[id]+id-i) { // pa[i] == pa[j]
pa[i] = pa[2*id-i];
}
else if (pa[2*id-i] < pa[id]+id-i) { // pa[i] == pa[id]+id-i
pa[i] = pa[2*id-i] < pa[id]+id-i ? pa[2*id-i] : pa[id]+id-i;
continue;
}
}
while (ms[i-pa[i]-1] == ms[i+pa[i]+1])
pa[i]++;
if (i+pa[i] > mi) { // i-substring becomes the rightmost
id = i;
mi = id + pa[id];
}
if (pa[i] > pa[maxi]) { // i-substring becomes the longest
maxi = i;
}
}
string r;
// get the leftmost/rightmost point of maxi-substring
int left = maxi - pa[maxi], right=maxi + pa[maxi];
// get the longest palindromic substring
for (int i=left; i<=right; i++)
if (ms[i] != '$' && ms[i] != '#')
r.append(1, ms[i]);
return r;
}
};
int main()
{
string s;
cin >> s;
Solution so;
string r = so.longestPalindrome(s);
cout << r << endl;
return 0;
}
Raw
longest_parentheses.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/longest-valid-parentheses/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
int res=0, c;
int n = s.length();
int *counter = new int [n];
stack<int> idx;
int i=-1, j=-1;
for (int k=0; k<n; k++) {
if (s[k] == '(') {
idx.push(k);
}
else {
if (!idx.empty()) {
i = idx.top();
idx.pop();
c = 1;
if (i>0 && s[i-1]==')')
c += counter[i-1];
if (s[k-1] == ')')
c += counter[k-1];
counter[i] = counter[k] = c;
if (c > res)
res = c;
}
else {
counter[k] = 0;
}
}
}
delete [] counter;
return res * 2;
}
};
int main()
{
string s;
cin >> s;
Solution so;
int r = so.longestValidParentheses(s);
cout << r << endl;
return 0;
}
Raw
longest_substring_no_repeat.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n;
n = s.length();
if (n == 0 || n == 1)
return n;
int repeat[n];
repeat[n-1] = 0;
for (int i=0; i<n-1; i++) {
repeat[i] = 0;
int j=i+1;
for (; j<n; j++) {
if (s[j] == s[i]) {
repeat[i] = j;
break;
}
}
if (j == n)
repeat[i] = 0;
}
int starts[n], r=1, k;
starts[n-1] = 1;
for (int i=n-2; i>=0; i--) {
if (repeat[i] == 0) {
starts[i] = starts[i+1] + 1;
}
else {
starts[i] = starts[i+1] + 1;
if (repeat[i] - i < starts[i])
starts[i] = repeat[i] - i;
}
if (starts[i] > r)
r = starts[i];
}
return r;
}
};
int main()
{
string s;
cin >> s;
Solution so;
cout << s << endl;
int r = so.lengthOfLongestSubstring(s);
cout << r << endl;
return 0;
}
Raw
lru_cache.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
class LRUCache {
private:
int capacity;
int size;
struct Node {
int key;
int value;
Node *last;
Node *next;
Node (int k, int v) : key(k), value(v), last(NULL), next(NULL) {};
};
tr1::unordered_map<int, Node*> index;
Node *head, *tail;
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = tail = NULL;
size = 0;
}
void push(Node *p) {
if (p != tail) { // p->next != NULL
if (p->last) { // p != head
p->last->next = p->next;
}
else {// p == head
head = p->next;
}
p->next->last = p->last;
tail->next = p;
p->last = tail;
p->next = NULL;
tail = p;
}
}
int get(int key) {
if (index.find(key) == index.end())
return -1;
Node *p = index[key];
push(p);
return p->value;
}
void set(int key, int value) {
if (index.find(key) != index.end()) {
Node *p = index[key];
p->value = value; // update value of "key"
push(p);
}
else {
if (size == capacity) {
index.erase(head->key); // delete the head (the oldest)
index[key] = head;
head->key = key;
head->value = value;
push(head);
}
else {
Node *p = new Node(key, value);
index[key] = p;
if (size == 0)
head = tail = p;
else {
p->last = tail;
tail->next = p;
tail = p;
}
++size;
}
}
}
void show() {
Node *p = head;
cout << " -- : ";
while (p) {
cout << p->key << ' ';
p = p->next;
}
cout << endl;
}
};
int main()
{
LRUCache lru(3);
string s;
int key, value;
while (1) {
cin >> s;
if (s[0] == 's') {
cin >> key >> value;
lru.set(key, value);
}
else if (s[0] == 'g') {
cin >> key;
cout << lru.get(key) << endl;
}
lru.show();
}
return 0;
}
Raw
max_palindrome.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int max_palindrome(string s) {
int n = s.length();
if (n==0)
return 0;
// 假设源字符串s 中没有字符 '$' '#'
string ms = "$#";
// 首先更改原字符串，将奇偶字符串都改为奇数串
// 首字符'$' 是为了简化处理边界情况
for (int i=0; i<n; i++){
ms.append(1, s[i]);
ms.append(1, '#');
}
int m = n * 2 + 2;
// pa[i] 记录以i 为中心点的回文串向右延伸多少个字符(不包含i 本身)
vector<int> pa(m, 0);
// id 记录边界最靠右的回文串的中心点位置；mi 记录id 右边界位置(内边界)
// 即：mi = id + pa[id]
// 注意id 标识的回文串不一定是最长的，而是最靠右的
int id=0, mi=0, maxp=0;
// 依次求解以每个点为中心的最大回文串长度
for (int i=1; i<m; i++) {
if (i >= mi) // i 不在id回文串的边界内部；
pa[i] = 0;
else { // i 在id回文串的边界内部
if (pa[2*id-i] < pa[id]+id-i) { // 与i对称(关于id对称)的点的回文串包含于id回文串内
// 这种情况了，i的回文串与其对称点的回文串关于id 对称，都包含在id 回文串内部
pa[i] = pa[2*id-i];
continue;
}
else { // 与i 对称的点的回文串边界超出了id回文串边界
pa[i] = pa[id]+id-i;
}
}
while (ms[i-pa[i]-1] == ms[i+pa[i]+1])
pa[i]++;
// 得到了更靠右的回文串
if (i + pa[i] > mi) {
id = i;
mi = id + pa[id];
}
// 记录目前最长的回文串长度
if (pa[i] > maxp)
maxp = pa[i];
}
return maxp;
}
};
int main()
{
string s;
cin >> s;
Solution so;
int r = so.max_palindrome(s);
cout << r << endl;
return 0;
}
Raw
max_points_on_a_line.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
#define unordered_map tr1::unordered_map
struct Point {
int x;
int y;
Point(): x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.empty()) return 0;
int m=0;
for (int i=0; i<points.size(); ++i) {
unordered_map<long long, int> lines;
int vertical = 0, same = 0, local = 0;
long long k;
// check the max points on a line which passed points[i]
for (int j=0; j<points.size(); ++j) {
// same points as points[i], every lines passed points[i] passing points[j]
if (points[i].x == points[j].x && points[i].y == points[j].y)
++same;
// the vertical line passed points[i]
else if (points[i].x == points[j].x)
++vertical;
else {
k = 1000000 * (points[i].y-points[j].y) / (points[i].x-points[j].x);
++lines[k];
local = max(lines[k], local);
}
}
local = max(local, vertical);
local += same;
m = max(m, local);
}
return m;
}
};
int main()
{
vector<Point> points;
points.push_back(Point(0, 0));
points.push_back(Point(1, 1));
points.push_back(Point(1, -1));
Solution so;
int r = so.maxPoints(points);
cout << r << endl;
return 0;
}
Raw
maximal_rectangle.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.empty())
return 0;
const int m=matrix.size(), n=matrix[0].size();
vector<int> H(n, 0), L(n, 0), R(n, n-1);
int left, right;
int res = 0;
for (int i=0; i<m; i++) {
left = 0;
right = n-1;
for (int j=0; j<n; j++) {
if (matrix[i][j] == '1') {
++H[j];
L[j] = max(L[j], left);
}
else {
H[j] = 0; L[j] = 0; R[j] = n-1;
left = j + 1;
}
}
for (int j=n-1; j>=0; j--) {
if (matrix[i][j] == '1') {
R[j] = min(right, R[j]);
res = max(res, H[j] * (R[j] - L[j] + 1));
}
else
right = j - 1;
}
}
return res;
}
};
int main()
{
Solution so;
return 0;
}
Raw
maximum_depth.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxDepth(TreeNode *root) {
if (!root)
return 0;
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> high;
int res=0, h=0;
p = root;
while (p != NULL) {
if (h > res)
res = h;
if (p->right != NULL) {
bstack.push(p->right);
high.push(h+1);
}
if (p->left != NULL) {
p = p->left;
h++;
}
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
h = high.top();
high.pop();
}
}
return res+1;
}
};
int main()
{
return 0;
}
Raw
maximum_subarray.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 贪心
class Solution {
public:
int maxSubArray(int A[], int n) {
int last, r;
last = r = A[0];
for (int i=1; i<n; i++) {
if (last > 0)
last = last + A[i];
else
last = A[i];
if (last > r)
r = last;
}
return r;
}
};
int main()
{
Solution so;
return 0;
}
Raw
maxpoints_on_a_line.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <tr1/unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point {
int x;
int y;
Point(): x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
class Solution {
public:
int maxPoints(vector<Point> &points) {
int n=points.size();
if (n <= 2)
return n;
tr1::unordered_map<long long, int> lines;
int maxp=0, ver=0;
long long k;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (points[i].x == points[j].x)
ver += 1;
else {
k = 1000000 * (points[i].y - points[j].y) / (points[i].x - points[j].x);
if (lines.find(k) != lines.end())
lines[k] = lines[k] + 1;
else
lines[k] = 1;
maxp = maxp > lines[k] ? maxp : lines[k];
}
}
}
maxp = maxp > ver ? maxp : ver;
int r = int(sqrt(2*maxp+1.0) + 0.5);
return r;
}
};
int main()
{
Solution so;
return 0;
}
Raw
median_of_two_sorted_arrays.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
double findKth(int A[], int m, int B[], int n, int k) {
if (m > n)
return findKth(B, n, A, m, k);
if (m == 0)
return B[k-1];
if (k == 1)
return A[0] < B[0] ? A[0] : B[0];
int x = k/2 < m ? k/2 : m;
if (A[x-1] == B[x-1]) {
if (k == x * 2)
return A[x-1];
return findKth(A+x, m-x, B+x, n-x, k-x*2);
}
if (A[x-1] < B[x-1])
return findKth(A+x, m-x, B, n, k-x);
if (A[x-1] > B[x-1])
return findKth(A, m, B+x, n-x, k-x);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m + n) % 2)
return findKth(A, m, B, n, (m+n+1)/2);
return (findKth(A, m, B, n, (m+n)/2) + findKth(A, m, B, n, (m+n)/2+1)) / 2.0;
}
};
int main()
{
int A[10];
int B[10];
for (int i=0; i<10; i++) {
A[i] = i;
B[i] = (i+1) * 10;
cout << A[i] << ' ' << B[i] << endl;
}
cout << endl;
Solution so;
double r = so.findMedianSortedArrays(A, 10, B, 10);
cout << r << endl;
return 0;
}
Raw
merge_intervals.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/merge-intervals/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
void show(vector<Interval> vec)
{
int n=vec.size();
for (int i=0; i<n; i++)
cout << vec[i].start << ' ' << vec[i].end << endl;
}
class Solution {
public:
// must be static
static bool cmp(Interval i1, Interval i2) {
return (i1.start < i2.start);
}
vector<Interval> merge(vector<Interval> &intervals) {
int n=intervals.size();
if (n == 0)
return intervals;
sort(intervals.begin(), intervals.end(), cmp);
vector<Interval>::iterator it;
int i=0, j=1;
for (; j<n; j++) {
if (intervals[j].start > intervals[i].end) {
i++;
if (i != j)
intervals[i] = intervals[j];
}
else if (intervals[j].end > intervals[i].end)
intervals[i].end = intervals[j].end;
}
for (j=i+1; j<n; j++)
intervals.pop_back();
return intervals;
}
};
int main()
{
Solution so;
return 0;
}
Raw
merge_k_lists.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/merge-k-sorted-lists/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
int n=lists.size(), k;
ListNode *p=NULL, *q=NULL, *head=NULL;
for (int i=0, j=n-1; j>=i; i++) {
if (!lists[i]) {
n--;
while (j > i && !lists[j]) {
j--;
n--;
}
if (j == i)
break;
lists[i] = lists[j];
j--;
}
}
if (n == 0)
return NULL;
while (n > 1) {
k = 0;
// 这里可以用小顶堆提速
for (int i=1; i<n; i++) {
if (lists[i]->val < lists[k]->val)
k = i;
}
p = lists[k];
lists[k] = p->next;
if (!lists[k]) {
n--;
lists[k] = lists[n];
}
if (!head)
q = head = p;
else {
q->next = p;
q = p;
}
}
if (!head)
head = lists[0];
else
q->next = lists[0];
return head;
}
};
int main()
{
Solution so;
return 0;
}
Raw
merge_sorted_array.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int *tmp = new int[m];
for (int i=0; i<m; i++)
tmp[i] = A[i];
int i, j, k;
i = j = k = 0;
while (i < m && j < n) {
if (tmp[i] <= B[j]) {
A[k++] = tmp[i];
i++;
}
else {
A[k++] = B[j];
j++;
}
}
while (i < m)
A[k++] = tmp[i++];
while (j < n)
A[k++] = B[j++];
delete [] tmp;
}
};
int main()
{
Solution so;
return 0;
}
Raw
merge_two_lists.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *p1=l1,*p2=l2, *q=NULL, *r=NULL, *head=NULL;
while (p1 && p2) {
if (p1->val <= p2->val) {
r = p1;
p1 = p1->next;
}
else{
r = p2;
p2 = p2->next;
}
if (!head)
q = head = r;
else {
q->next = r;
q = r;
}
}
if (!head)
head = p1 ? p1 : p2;
else
q->next = p1 ? p1 : p2;
return head;
}
};
int main()
{
Solution so;
return 0;
}
Raw
minimum_depth.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int minDepth(TreeNode *root) {
if (!root)
return 0;
queue<TreeNode*> qu; // keep current level !
int c_in, c_out, depth=0;
TreeNode *p;
qu.push(root);
depth = 1;
c_out = 1;
c_in = 0;
while (1) {
while (c_out--) {
p = qu.front();
qu.pop();
if (p->left) {
qu.push(p->left);
c_in++;
if (p->right) {
qu.push(p->right);
c_in++;
}
}
else if (p->right) {
qu.push(p->right);
c_in++;
}
else
return depth;
}
c_out = c_in;
c_in = 0;
depth++;
}
return depth;
}
};
int main()
{
TreeNode *root, *p;
root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->right = new TreeNode(4);
Solution so;
int r = so.minDepth(root);
cout << r << endl;
return 0;
}
Raw
minimum_path_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
int m = grid.size();
if (m == 0)
return 0;
int n = grid[0].size();
vector<vector<int> > psum;
vector<int> row;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (i>0 && j==0) {
row.push_back(grid[i][j] + psum[i-1][j]);
}
else if (j>0 && i==0) {
row.push_back(grid[i][j] + row[j-1]);
}
else
row.push_back(grid[i][j]);
}
psum.push_back(row);
row.clear();
}
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
psum[i][j] += (psum[i-1][j] <= psum[i][j-1] ? psum[i-1][j] : psum[i][j-1]);
}
}
return psum[m-1][n-1];
}
};
int main()
{
Solution so;
return 0;
}
Raw
minimum_window_substring.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <tr1/unordered_map>
#include <cstring>
using namespace std;
class Solution {
public:
string minWindow(string S, string T) {
int m=S.size(), n=T.size();
int count_char[256], show_char[256];
// 初始化数组是，memset 的第三个参数表示数组的大小（字节数），一定要准确。
memset(count_char, 0, 256*4);
memset(show_char, 0, 256*4);
for (int i=0; i<n; i++)
count_char[T[i]]++;
int len=m+1, size=0, head=0;
string r;
for (int i=0; i<m; i++) {
if (count_char[S[i]] > 0) { // S[i] appears in T
if (show_char[S[i]] < count_char[S[i]])
size++;
show_char[S[i]]++;
}
if (size == n) {
while (count_char[S[head]]==0 || show_char[S[head]]>count_char[S[head]]) {
--show_char[S[head]];
++head;
}
if (i - head + 1 < len) {
len = i - head + 1;
r = S.substr(head, len);
}
show_char[S[head]]--;
++head;
size--;
}
}
return r;
}
};
int main()
{
string s, t;
cin >> s >> t;
Solution so;
cout << so.minWindow(s, t) << endl;
return 0;
}
Raw
most_water.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
/* Container With Most Water
* http://oj.leetcode.com/problems/container-with-most-water/
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int> &height) {
int area, dist, maxa=0;
for (vector<int>::iterator it=height.begin(); it!=height.end(); ++it) {
if (*it == 0)
continue;
dist = maxa / *it;
if ((height.end()-it-1) < dist) // pruning first
continue;
for (vector<int>::iterator i2=it+dist; i2!=height.end(); ++i2) {
area = min(*it, *i2) * (i2 - it);
if (area > maxa)
maxa = area;
}
}
return maxa;
}
};
int main()
{
int nums[] = {0, 2}; // test case
vector<int> height (nums, nums+2);
Solution so;
cout << so.maxArea(height) << endl;
return 0;
}
Raw
multiply_strings.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
string add(string num1, string num2) {
string s;
int m=num1.length(), n=num2.length();
int x, a=0;
for (int i=m-1, j=n-1; i>=0 || j>=0; i--, j--) {
x = a;
if (i >= 0)
x += num1[i] - '0';
if (j >= 0)
x += num2[j] - '0';
s.insert(0, 1, x % 10 + '0');
a = x / 10;
}
if (a > 0)
s.insert(0, 1, a + '0');
return s;
}
string multiply(string num1, string num2) {
int m=num1.length(), n=num2.length();
int x, y, a=0;
string s, r;
for (int i=n-1; i>=0; i--) {
s.insert(0, n-i-1, '0');
y = num2[i] - '0';
a = 0;
for (int j=m-1; j>=0; j--) {
x = a + y * (num1[j] - '0');
s.insert(0, 1, x%10 + '0');
a = x / 10;
}
if (a > 0)
s.insert(0, 1, a + '0');
r = add(r, s);
cout << r << ' ' << s << endl;
s.clear();
}
while (!r.empty() && r[0]=='0')
r.erase(r.begin());
if (r.empty())
r.push_back('0');
return r;
}
};
int main()
{
string s1, s2;
cin >> s1 >> s2;
Solution so;
string r = so.multiply(s1, s2);
cout << r << endl;
return 0;
}
Raw
n_queen.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/n-queens/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
void show(vector<string> vec)
{
int n=vec.size();
for (int i=0; i<n; i++)
cout << vec[i] << endl;
cout << endl;
}
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > res;
vector<string> board;
string s;
s.append(n, '.');
// v 记录哪些列被占了，ld记录哪些左偏对角线被占了，rd记录哪些右偏对角线被占了
unsigned v=0, ld=0, rd=0;
int i=0, j=0, k=0;
int idx[n];
while (1) {
if (i == n) {
res.push_back(board);
}
if (i == n || j == n) {
if (i == 0)
break;
i--;
board.pop_back();
j = idx[i];
v ^= 1 << j;
ld ^= 1 << (i+j);
rd ^= 1 << (i-j+n-1);
j++;
}
for (; j<n; j++) {
if (!(v&(1<<j) || ld&(1<<(i+j)) || rd&(1<<(i-j+n-1)))) {
s[j] = 'Q';
board.push_back(s);
s[j] = '.';
v |= 1 << j;
ld |= 1 << (i+j);
rd |= 1 << (i-j+n-1);
idx[i++] = j;
j = 0;
break;
}
}
}
return res;
}
};
int main()
{
int n;
cin >> n;
Solution so;
vector<vector<string> > res = so.solveNQueens(n);
cout << res.size() << endl;
return 0;
}
Raw
n_queen2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/n-queens-ii/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
void show(vector<string> vec)
{
int n=vec.size();
for (int i=0; i<n; i++)
cout << vec[i] << endl;
cout << endl;
}
class Solution {
public:
// 只计数，是不是应该有更好的方法？？
int totalNQueens(int n) {
// fac 控制每次找到结果加1还是加2；由于棋盘对称性，有一半的计算可以省略
int res=0, fac=2;
// v 记录哪些列被占了，ld记录哪些左偏对角线被占了，rd记录哪些右偏对角线被占了
unsigned v=0, ld=0, rd=0;
int i=0, j=0, k=0;
int idx[n];
while (1) {
if (i == n) {
res += fac;
}
if (i == n || j == n) {
if (i == 0)
break;
i--;
j = idx[i];
v ^= 1 << j;
ld ^= 1 << (i+j);
rd ^= 1 << (i-j+n-1);
j++;
}
for (; j<n; j++) {
if (i==0) {
if (n%2 && j==n/2)
fac = 1;
else if (j >= n/2)
break ;
}
if (!(v&(1<<j) || ld&(1<<(i+j)) || rd&(1<<(i-j+n-1)))) {
v |= 1 << j;
ld |= 1 << (i+j);
rd |= 1 << (i-j+n-1);
idx[i++] = j;
j = 0;
break;
}
}
if (i == 0 && j>=n/2)
break;
}
return res;
}
};
int main()
{
int n;
cin >> n;
Solution so;
int res = so.totalNQueens(n);
cout << res << endl;
return 0;
}
Raw
next_permutation.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void nextPermutation(vector<int> &num) {
int k, n=num.size();
if (n <= 1)
return ;
for (k=n-1; k>0; k--) {
if (num[k] > num[k-1])
break;
}
int t;
for (int i=k, j=n-1; i<j; i++, j--) {
t = num[i];
num[i] = num[j];
num[j] = t;
}
if (k > 0) {
int i=k;
while (num[i] <= num[k-1]) i++;
t=num[i];
num[i] = num[k-1];
num[k-1] = t;
}
}
};
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
vector<int> num;
num.push_back(4);
num.push_back(0);
Solution so;
show(num);
so.nextPermutation(num);
show(num);
return 0;
}
Raw
next_right_pointers.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
class Solution {
public:
void connect(TreeLinkNode *root) {
stack<TreeLinkNode*> st;
TreeLinkNode *p, *q, *down;
if (!root)
return ;
p = root;
p->next = NULL;
down = p->left;
while (down) {
p->left->next = p->right;
if (p->next) {
p->right->next = p->next->left;
p = p->next;
}
else {
p->right->next = NULL;
p = down;
down = down->left;
}
}
}
};
void show(TreeLinkNode *root)
{
TreeLinkNode *p, *down;
down = root;
while (down) {
p = down;
down = down->left;
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
}
void recursive_so(TreeLinkNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
int build_tree(TreeLinkNode *root, int high, int val)
{
if (high == 5)
return val;
root->left = new TreeLinkNode(val++);
root->right = new TreeLinkNode(val++);
high++;
val = build_tree(root->left, high, val);
val = build_tree(root->right, high, val);
}
int main()
{
TreeLinkNode *root = NULL;
root = new TreeLinkNode(0);
build_tree(root, 1, 1);
recursive_so(root);
cout << endl;
Solution so;
so.connect(root);
show(root);
return 0;
}
Raw
next_right_pointers2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
using namespace std;
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root)
return ;
TreeLinkNode *p=NULL, *last=NULL, *down=NULL;
p = root;
p->next = NULL;
down = p->left? p->left : p->right;
while (down) {
if (p->left) {
if (last)
last->next = p->left;
last = p->left;
if (p->right) {
last->next = p->right;
last = p->right;
}
}
else if (p->right) {
if (last)
last->next = p->right;
last = p->right;
}
// find next node p
if (p->next)
p = p->next;
else { // this level has met the end, move to next level
if (last)
last->next = NULL;
last = NULL; // at the beginning of a new level, last is NULL
p = down;
down = NULL;
// now begin to find new "down"
while (p && !down) {
if (p->left) {
down = p->left;
}
else if (p->right) {
down = p->right;
}
else {
p = p->next;
}
}
}
}
}
};
void show(TreeLinkNode *root)
{
TreeLinkNode *p, *down;
down = root;
while (down) {
p = down;
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
p = down;
while (p) {
if (p->left) {
down = p->left;
break;
}
else if (p->right) {
down = p->right;
break;
}
else {
p = p->next;
down = NULL;
}
}
}
}
int main()
{
TreeLinkNode *root = NULL;
root = new TreeLinkNode(1);
root->left = new TreeLinkNode(2);
root->right = new TreeLinkNode(3);
Solution so;
so.connect(root);
show(root);
return 0;
}
Raw
palindrome_number.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
using namespace std;
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) // Negative number is NOT palindrome;
return false;
int e=1, f=10;
while (x / e >= 10)
e *= 10;
while (x >= 10) {
if (x/e != x%f)
return false;
x %= e;
x /= f;
e /= 100;
}
return true;
}
};
int main()
{
int n;
cin >> n;
Solution so;
int r = so.isPalindrome(n);
cout << r << endl;
return 0;
}
Raw
palindrome_partition.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void show(vector<vector<string> > res)
{
for (vector<vector<string> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<string>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
class Solution {
public:
vector<vector<string> > sub_partition(string s, int start, int n) {
vector<vector<string> > res, vv;
string subs;
int i, j, k;
for (i=start; i<n; i++) {
subs.append(1, s[i]);
for (j=start, k=i; j<k; j++, k--) {
if (s[j] != s[k])
break;
}
if (j >= k) {
if (i == n-1) {
vector <string> vec;
vec.push_back(subs);
res.push_back(vec);
}
else {
vv = sub_partition(s, i+1, n);
int vn = vv.size();
for (int h=0; h<vn; h++) {
vv[h].insert(vv[h].begin(), subs);
res.push_back(vv[h]);
}
}
}
}
return res;
}
vector<vector<string> > partition(string s) {
vector<vector<string> > res;
int n = s.length();
res = sub_partition(s, 0, n);
return res;
}
};
int main()
{
string s;
cin >> s;
vector<vector<string> > res;
Solution so;
res = so.partition(s);
show(res);
return 0;
}
Raw
palindrome_partition2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void show(vector<int> res)
{
int n = res.size();
for(int i=0; i<n; i++)
cout << res[i] << ' ';
cout << endl;
}
// too slow !!
class Solution {
public:
vector<string> sub_partition(string s, int start, int n) {
vector<string> res, vec;
string subs;
int i, j, k;
for (i=start; i<n; i++) {
subs.append(1, s[i]);
for (j=start, k=i; j<k; j++, k--) {
if (s[j] != s[k])
break;
}
if (j >= k) {
if (i == n-1) {
res.clear();
res.push_back(subs);
return res;
}
else {
vec = sub_partition(s, i+1, n);
vec.insert(vec.begin(), subs);
if (res.size() == 0 || vec.size() < res.size())
res = vec;
}
}
}
return res;
}
int minCut(string s) {
vector<string> vec;
int n = s.length();
vec = sub_partition(s, 0, n);
return vec.size();
}
};
class Solution2 {
public:
int palindromeLength(string s) {
int n = s.length();
// convert s to ms
// string s not contains '#' or '$'
string ms = "$#";
for (int i=0; i<n; i++){
ms.append(1, s[i]);
ms.append(1, '#');
}
// both sides of ms[i] contain a '#'
// m: length of ms
int m = n * 2 + 2;
// pa[i] recoreds i-centered palindromic substring's right-length
vector<int> pa(m, 0);
// maxi: ms[maxi] is the center point of the longest palindromic substring
// id: ms[id] is the center point of the rightmost palindromic substring
int maxi=0, id=0, mi=id+pa[id];
for (int i=1; i<m; i++) {
if (i >= mi) // ms[i] is outside id-substring
pa[i] = 0;
else { // ms[i] is inside of id-substring
if (pa[2*id-i] == pa[id]+id-i) { // pa[i] == pa[j]
pa[i] = pa[2*id-i];
}
else if (pa[2*id-i] < pa[id]+id-i) { // pa[i] == pa[id]+id-i
pa[i] = pa[2*id-i] < pa[id]+id-i ? pa[2*id-i] : pa[id]+id-i;
continue;
}
}
while (ms[i-pa[i]-1] == ms[i+pa[i]+1])
pa[i]++;
if (i+pa[i] > mi) { // i-substring becomes the rightmost
id = i;
mi = id + pa[id];
}
if (pa[i] > pa[maxi]) { // i-substring becomes the longest
maxi = i;
}
}
vector<int> cut(m, 0);
for (int i=1; i<m; i++) {
for (int j=i-pa[i]+1, k=i+pa[i]-1; j<=i; j+=2, k-=2) {
if (j == 2)
cut[j] = cut[k] = 1;
else {
if (cut[j] == 0 || cut[j] > cut[j-2] + 1)
cut[j] = cut[j-2] + 1;
if (cut[k] == 0 || cut[k] > cut[j-2] + 1)
cut[k] = cut[j-2] + 1;
}
}
}
return cut[m-2] - 1;
}
int minCut(string s) {
int n = s.size();
if (n <= 1)
return 0;
return palindromeLength(s);
}
};
int main()
{
string s;
cin >> s;
Solution2 so;
int r = so.minCut(s);
cout << r << endl;
return 0;
}
Raw
partition_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *p, *q, *r, *h2=NULL, *p2=NULL;
p = head;
while (p) {
if (p->val >= x) {
if (!h2)
h2 = p;
else
p2->next = p;
p2 = p;
if (p == head) {
p = p->next;
head = p;
}
else {
q->next = p->next;
p = p->next;
}
}
else {
q = p;
p = p->next;
}
}
if (p2)
p2->next = NULL;
if (!head)
return h2;
q->next = h2;
return head;
}
};
void show(ListNode *p)
{
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *head=NULL, *p, *q;
for (int i=0; i<10; i++) {
q = new ListNode(10-i);
if (!head)
head = q;
else
p->next = q;
p = q;
}
show(head);
Solution so;
head = so.partition(head, 4);
show(head);
return 0;
}
Raw
pascal_triangel.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > res;
vector<int> line;
for (int i=0; i<numRows; i++) {
for (int j=0; j<=i; j++) {
if (j==0 || j==i)
line.push_back(1);
else
line.push_back(res[i-1][j-1] + res[i-1][j]);
}
res.push_back(line);
line.clear();
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
int n;
cin >> n;
Solution so;
vector<vector<int> > res;
res = so.generate(n);
show(res);
return 0;
}
Raw
pascal_triangel2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res;
const int FACTOR[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 0};
int n = 1, m, r;
res.push_back(1);
for (int i=1; i<=rowIndex; i++) {
if (i > rowIndex/2)
res.push_back(res[rowIndex-i]);
else {
m = rowIndex - i + 1;
int _i = i;
for (int j=0; FACTOR[j]!=0; j++) {
r = FACTOR[j];
if (r > _i)
break;
while (n % r == 0 && _i % r == 0) {
n /= r;
_i /= r;
}
while (m % r == 0 && _i % r == 0) {
m /= r;
_i /= r;
}
}
n = n * m / _i;
res.push_back(n);
}
}
return res;
}
};
void show(vector<int> res)
{
for (vector<int>::iterator it=res.begin(); it!=res.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
int n;
cin >> n;
Solution so;
vector<int> res;
res = so.getRow(n);
show(res);
return 0;
}
Raw
path_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
int r=0, t;
stack<TreeNode*> st;
stack<int> tag;
TreeNode *p=root, *q;
while (p) {
r += p->val;
if (p->left) {
st.push(p);
tag.push(0);
p = p->left;
}
else {
if (!p->right) {
if (r == sum)
return true;
r -= p->val;
while (!p->right && !st.empty()) {
t = tag.top();
tag.pop();
if (t == 0) {
p = st.top();
tag.push(1);
}
else {
r -= st.top()->val;
st.pop();
}
}
}
else {
st.push(p);
tag.push(1);
}
p = p->right;
}
}
return false;
}
};
int build_tree(TreeNode *root, int high, int val)
{
if (high == 3)
return val;
root->left = new TreeNode(val++);
root->right = new TreeNode(val++);
high++;
val = build_tree(root->left, high, val);
val = build_tree(root->right, high, val);
}
int main()
{
TreeNode *root;
root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
Solution so;
bool r = so.hasPathSum(root, 101);
cout << r << endl;
return 0;
}
Raw
path_sum2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
int r=0, t;
vector<vector<int> > res;
vector<int> vec;
stack<TreeNode*> st;
stack<int> tag;
TreeNode *p=root, *q;
while (p) {
r += p->val;
vec.push_back(p->val);
if (p->left) {
st.push(p);
tag.push(0);
p = p->left;
}
else {
if (!p->right) {
if (r == sum)
res.push_back(vec);
r -= p->val;
vec.pop_back();
while (!p->right && !st.empty()) {
t = tag.top();
tag.pop();
if (t == 0) {
p = st.top();
tag.push(1);
}
else {
r -= st.top()->val;
vec.pop_back();
st.pop();
}
}
}
else {
st.push(p);
tag.push(1);
}
p = p->right;
}
}
return res;
}
};
int build_tree(TreeNode *root, int high, int val)
{
if (high == 3)
return val;
root->left = new TreeNode(val++);
root->right = new TreeNode(val++);
high++;
val = build_tree(root->left, high, val);
val = build_tree(root->right, high, val);
}
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
TreeNode *root;
root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
root->left->left = new TreeNode(2);
Solution so;
vector<vector<int> > res = so.pathSum(root, 5);
show(res);
return 0;
}
Raw
permulations.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
void show_one(vector<int> &num)
{
for (vector<int>::iterator it=num.begin(); it!=num.end(); ++it)
cout << *it << ' ';
cout << endl;
}
class Solution {
public:
void prep(vector<int> &num, int i, int j) {
int t;
if (i < j) {
t = num[j];
for (int k=j; k>i; k--)
num[k] = num[k-1];
num[i] = t;
}
else if (i > j) {
t = num[j];
for (int k=j; k<i; k++)
num[k] = num[k+1];
num[i] = t;
}
}
void permute_recur(vector<vector<int> > &res, vector<int> &num, int b, int e) {
if (b == e) {
res.push_back(num);
return ;
}
// 针对第一个位置元素处理, 避免移动原数组过多
// 选择好第一个元素后，对其余元素全排列；
for (int i=b; i<=e; i++) {
if (i == b) {
permute_recur(res, num, b+1, e);
continue;
}
// 为了保持最后结果序列的顺序，本题不要求。
prep(num, b, i);
permute_recur(res, num, b+1, e);
// 一定要复原！ 否则顺序混乱，出现重复结果
prep(num, i, b);
}
}
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
int n = num.size();
permute_recur(res, num, 0, n-1);
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> nums;
for (int i=0; i<5; i++) {
nums.push_back(i+1);
}
Solution so;
vector<vector<int> > r = so.permute(nums);
cout << endl;
show(r);
// cout << r.size() << endl;
return 0;
}
Raw
permulations2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void show_one(vector<int> &num)
{
for (vector<int>::iterator it=num.begin(); it!=num.end(); ++it)
cout << *it << ' ';
cout << endl;
}
class Solution {
public:
void prep(vector<int> &num, int i, int j) {
int t;
if (i < j) {
t = num[j];
for (int k=j; k>i; k--)
num[k] = num[k-1];
num[i] = t;
}
else if (i > j) {
t = num[j];
for (int k=j; k<i; k++)
num[k] = num[k+1];
num[i] = t;
}
}
void permute_recur(vector<vector<int> > &res, vector<int> &num, int b, int e) {
if (b == e) {
res.push_back(num);
return ;
}
for (int i=b; i<=e; i++) {
if (i>b && num[i]==num[i-1])
continue;
// 对于本题，保持有序很重要！！
prep(num, b, i);
permute_recur(res, num, b+1, e);
prep(num, i, b);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
int n = num.size();
sort(num.begin(), num.end());
permute_recur(res, num, 0, n-1);
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> nums;
for (int i=0; i<3; i++) {
nums.push_back(i+1);
}
nums.push_back(1);
nums.push_back(1);
Solution so;
vector<vector<int> > r = so.permuteUnique(nums);
cout << endl;
show(r);
cout << r.size() << endl;
return 0;
}
Raw
permutation_sequence.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/permutation-sequence/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
string getPermutation(int n, int k) {
int *digits = new int[n+1];
for (int i=0; i<=n; i++)
digits[i] = i;
string s;
int m=1, i, start=1, r;
while (k > 0) {
for (i=1; i<=n && m<k; i++)
m *= (i + 1);
// k 恰好为i 阶乘值
if (m == k) {
for (int j=start; j <= n-i; j++)
s.append(1, digits[j]+'0');
for (int j=n; j > n - i; j--)
s.append(1, digits[j]+'0');
break ;
}
else { // (i-1)! < m < i!
m /= i;
r = (k-1) / m;
k -= r * m;
for (int j=start; j <= n-i; j++)
s.append(1, digits[j]+'0');
s.append(1, digits[n-i+1+r]+'0');
for (int j=n-i+1+r; j>n-i+1; j--)
digits[j] = digits[j-1];
digits[n-i+2] = digits[n-i+1];
start = n-i+2;
m = 1;
}
}
return s;
}
};
int main()
{
int n, k;
cin >> n >> k;
Solution so;
so.getPermutation(n, k);
return 0;
}
Raw
plus_one.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int n=digits.size();
int a=0, x;
for (int i=n-1; i>=0; i--) {
if (i == n-1)
x = digits[i] + 1;
else
x = digits[i] + a;
digits[i] = x % 10;
a = x / 10;
}
if (a > 0)
digits.insert(digits.begin(), a);
return digits;
}
};
void show(vector<int> digs)
{
int n = digs.size();
for (int i=0; i<n; i++)
cout << digs[i];
cout << endl;
}
int main()
{
vector<int> digs;
for (int i=0; i<9; i++) {
digs.push_back(9-i);
break;
}
show(digs);
Solution so;
vector<int> r = so.plusOne(digs);
show(digs);
return 0;
}
Raw
postorder_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> vstack;
vector<int> res;
p = root;
while (p != NULL) {
vstack.push(p->val);
if (p->left)
bstack.push(p->left);
if (p->right)
p = p->right;
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
}
}
while (!vstack.empty()) {
res.push_back(vstack.top());
vstack.pop();
}
return res;
}
};
class Solution2 {
public:
vector<int> postorderTraversal(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> tag;
int t=0;
vector<int> res;
p = root;
while (p) {
bstack.push(p);
tag.push(0);
if (p->left)
p = p->left;
else {
do {
t = tag.top();
tag.pop();
if (t == 0) {
p = bstack.top()->right;
tag.push(1);
}
else {
res.push_back(bstack.top()->val);
bstack.pop();
}
} while (!p && !bstack.empty());
}
}
return res;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
recursive_so(root->left);
recursive_so(root->right);
cout << root->val << ' ';
}
void recursive_rso(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_rso(root->right);
recursive_rso(root->left);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root, *p, *left, *right, *q;
for (int i=0; i<10; i++) {
if (i==0) {
p = new TreeNode(i+1);
root = p;
}
left = new TreeNode((i+1) * 10);
right = new TreeNode((i+1) * 15);
p->left = left;
p->right = right;
if (i % 3 == 0)
p = p->left;
else
p = p->right;
}
vector<int> res;
Solution so;
res = so.postorderTraversal(root);
show(res);
vector<int> res2;
Solution2 so2;
res2 = so2.postorderTraversal(root);
show(res2);
recursive_so(root);
cout << endl;
// recursive_rso(root);
// cout << endl;
return 0;
}
Raw
pow.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
double pow(double x, int n) {
if (n == 0)
return 1;
double r=1.0;
if (n % 2 == 0)
r = pow(x*x, n/2);
else
r = x * pow(x*x, n/2);
return r;
}
};
class Solution2 {
public:
double pow(double x, int n) {
bool negative=false;
if (n < 0) {
n = -n;
negative = true;
}
double r=1.0;
while (n) {
if (n % 2)
r *= x;
x *= x;
n /= 2;
}
if (negative)
return 1 / r;
return r;
}
};
int main()
{
double x;
int n;
cin >> x >> n;
Solution so;
double r = so.pow(x, n);
cout << r << endl;
Solution2 so2;
double r2 = so2.pow(x, n);
cout << r2 << endl;
return 0;
}
Raw
preorder_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
vector<int> res;
p = root;
while (p != NULL) {
res.push_back(p->val);
if (p->right != NULL)
bstack.push(p->right);
if (p->left != NULL)
p = p->left;
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
}
}
return res;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root, *p, *left, *right, *q;
for (int i=0; i<10; i++) {
if (i==0) {
p = new TreeNode(i+1);
root = p;
}
left = new TreeNode((i+1) * 10);
right = new TreeNode((i+1) * 15);
p->left = left;
p->right = right;
if (i % 3 == 0)
p = p->left;
else
p = p->right;
}
vector<int> res;
Solution so;
res = so.preorderTraversal(root);
show(res);
recursive_so(root);
cout << endl;
return 0;
}
Raw
recover_bst.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/validate-binary-search-tree/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 利用中序遍历
class Solution {
public:
void _swap(TreeNode *p, TreeNode *q) {
int t = p->val;
p->val = q->val;
q->val = t;
}
void recoverTree(TreeNode *root) {
TreeNode *p, *q, *r, *last=NULL, *key=NULL;
stack<TreeNode*> bstack;
p = root;
while (p) {
bstack.push(p);
if (p->left) {
p = p->left;
}
else {
do {
p = bstack.top();
bstack.pop();
if (key) {
if (p->val < last->val) {
_swap(key, p);
return ;
}
else if (p->val > key->val) {
_swap(key, last);
return ;
}
}
else if (last && p->val < last->val) {
key = last;
}
last = p;
p = p->right;
} while (!p && !bstack.empty());
}
}
if (key)
_swap(key, last);
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
recursive_so(root->left);
cout << root->val << ' ';
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root;
root = new TreeNode(9);
root->left = new TreeNode(8);
root->right = new TreeNode(10);
root->right->left = new TreeNode(12);
recursive_so(root);
cout << endl;
Solution so;
so.recoverTree(root);
recursive_so(root);
cout << endl;
return 0;
}
Raw
regular_expression_matching.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0')
return *s == '\0';
if (*(p+1) == '*') {
if (isMatch(s, p+2))
return true;
if (*s == *p || (*s!='\0' && *p=='.'))
if (isMatch(s+1, p))
return true;
return false;
}
else {
if (*s == *p || (*s!='\0' && *p=='.'))
return isMatch(s+1, p+1);
return false;
}
}
};
int main()
{
Solution so;
return 0;
}
Raw
remove_duplicates_sorted_array.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
#include <iostream>
using namespace std;
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n == 0)
return 0;
int k=1;
for (int i=1; i<n; i++) {
if (A[i] != A[k-1]) {
A[k++] = A[i];
}
}
return k;
}
};
int main()
{
return 0;
}
Raw
remove_duplicates_sorted_array2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
#include <iostream>
using namespace std;
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n <= 2)
return n;
int k=2;
for (int i=2; i<n; i++) {
if (A[i] != A[k-2]) {
A[k++] = A[i];
}
}
return k;
}
};
int main()
{
return 0;
}
Raw
remove_duplicates_sorted_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode *p, *q, *r;
p = head;
while (p) {
if (p == head) {
q = p;
}
else {
if (p->val == q->val)
q->next = p->next;
else
q = p;
}
p = p->next;
}
return head;
}
};
int main()
{
Solution so;
return 0;
}
Raw
remove_duplicates_sorted_list2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode *p, *q, *r=NULL;
q = head;
while (q && q->next) {
p = q->next;
if (p->val == q->val) {
while (p && p->val == q->val) {
p = p->next;
}
if (q == head)
head = q = p;
else {
q = p;
r->next = p;
}
}
else {
r = q;
q = p;
p = p->next;
}
}
return head;
}
};
void show(ListNode *p)
{
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *p;
p = new ListNode(1);
p->next = new ListNode(1);
p->next->next = new ListNode(2);
p->next->next->next = new ListNode(2);
p->next->next->next->next = new ListNode(3);
Solution so;
p = so.deleteDuplicates(p);
show(p);
return 0;
}
Raw
remove_element.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int removeElement(int A[], int n, int elem) {
int len=n, j=n-1, t;
for (int i=0; i<=j; i++) {
if (A[i] == elem) {
len--;
while (j>i && A[j]==elem) {
j--;
len--;
}
if (j == i)
break;
A[i] = A[j];
j--;
}
}
return len;
}
};
int main()
{
Solution so;
return 0;
}
Raw
remove_nth_node.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *p, *q, *r;
p = q = head;
for (int i=0; i<n; i++)
p = p->next;
while (p) {
p = p->next;
r = q;
q = q->next;
}
if (q == head)
head = q->next;
else
r->next = q->next;
return head;
}
};
void show(ListNode *head)
{
ListNode *p = head;
while (p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *head, *p, *q;
for (int i=0; i<5; i++) {
q = new ListNode(i+1);
if (i==0) {
p = head = q;
}
else {
p->next = q;
p = q;
}
}
show(head);
cout << endl;
Solution so;
int n;
cin >> n;
head = so.removeNthFromEnd(head, n);
show(head);
return 0;
}
Raw
reorder_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void show(ListNode *head) {
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << endl;
}
class Solution {
public:
void reorderList(ListNode *head) {
if (!head || !head->next)
return ;
int n=0;
ListNode *p, *q, *r, *start;
p = head;
while (p) {
n++;
p = p->next;
}
start = head;
for (int i=0; i<n/2-1; i++)
start = start->next;
p = start->next;
start->next = NULL;
q = p->next;
p->next = NULL;
while (p && q) {
r = q->next;
q->next = p;
p = q;
q = r;
}
r = head;
q = head->next;
while (q && p) {
r->next = p;
p = p->next;
r->next->next = q;
r = q;
q = q->next;
}
if (q)
r->next = q;
if (p)
r->next = p;
return ;
}
};
int main()
{
ListNode *head, *p, *q;
for (int i=0; i<11; i++) {
q = new ListNode(i+1);
if (i==0)
head = q;
else
p->next = q;
p = q;
}
show(head);
Solution so;
so.reorderList(head);
show(head);
return 0;
}
Raw
restore_ip_addr.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool isValid(string s, int i, int j) {
// 不能有多余前导零
if (s[i] == '0') {
if (j - i == 1)
return true;
else
return false;
}
int r = 0;
for (int k=i; k<j; k++) {
r = r*10 + s[k]-'0';
}
if (r <= 255)
return true;
return false;
}
string combine(string s, int idx[]) {
string r;
int k=0;
for (int i=0; i<4; i++) {
for (int j=0; j<idx[i]; j++) {
r.append(1, s[k]);
k++;
}
if (i < 3)
r.append(1, '.');
}
return r;
}
vector<string> restoreIpAddresses(string s) {
vector<string> res;
int n = s.length();
if (n < 4 || n > 12)
return res;
int idx[] = {0, 0, 0, 0};
string ip;
int i, j, k;
i = 1;
j = k = 0;
while (1) {
if (k == 4) {
if (idx[0] + idx[1] + idx[2] + idx[3] == n) {
ip = combine(s, idx);
res.push_back(ip);
}
do {
k--;
i = idx[k] + 1;
j -= idx[k];
} while(!isValid(s, j, j+i) && k > 0);
if (!isValid(s, j, j+i))
break;
}
j += i;
idx[k++] = i;
i = 1;
}
return res;
}
};
class Solution2 {
public:
bool isValid(string s, int idx[], int k, int j) {
int i;
if (k == 0)
i = 0;
else
i = idx[k-1];
// 不能有多余前导零
if (s[i] == '0' && j-i>1)
return false;
// 不能提前用尽所有字符
int n = s.length();
if (j > n+k-3)
return false;
int r = 0;
for (; i<j; i++) {
r = r*10 + s[i]-'0';
}
if (r <= 255)
return true;
return false;
}
string combine(string s, int idx[]) {
string r;
int j=0;
for (int i=0; i<3; i++) {
for (; j<idx[i]; j++)
r.append(1, s[j]);
r.append(1, '.');
}
for ( ; j<s.length(); j++)
r.append(1, s[j]);
return r;
}
vector<string> restoreIpAddresses(string s) {
vector<string> res;
int n = s.length();
if (n < 4 || n > 12)
return res;
string ip;
int idx[] = {0, 0, 0};
// idx 记录ip 地址第二、三、四部分在串s 的起始位置 (第一部分起始部分一定是0，省略)
// j 记录在串s 中的起始位置
// i 记录从j 开始， 占据多少个字符
// k 指示idx 的下标
int j, k;
j = 1;
k = 0;
while (1) {
if (k == 3) {
if (isValid(s, idx, k, n)) {
ip = combine(s, idx);
cout << ip << endl;
res.push_back(ip);
}
do {
k--;
j = idx[k] + 1;
} while(!isValid(s, idx, k, j) && k > 0);
if (!isValid(s, idx, k, j))
break;
}
idx[k++] = j;
j += 1;
}
return res;
}
};
int main()
{
string s;
cin >> s;
Solution2 so;
so.restoreIpAddresses(s);
return 0;
}
Raw
reverse_integer.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//Reverse Integer
//http://oj.leetcode.com/problems/reverse-integer/
#include <iostream>
using namespace std;
class Solution {
public:
int reverse(int x) {
int r = 0, flag = 1;
if (x < 0) {
flag = -1;
x = -x;
}
while (x) {
r = r * 10 + x % 10;
x /= 10;
}
return (flag * r);
}
};
int main()
{
int x;
cin >> x;
Solution so;
cout << so.reverse(x) << endl;
return 0;
}
Raw
reverse_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
if (m == n)
return head;
ListNode *parent, *start, *p, *q, *r;
if (m == 1) {
parent = NULL;
start = head;
}
else {
parent = head;
for (int i=1; i<m-1; i++) {
parent = parent->next;
}
start = parent->next;
}
p = start;
q = p->next;
for (int i=m; i<n; i++) {
r = q->next;
q->next = p;
p = q;
q = r;
}
if (parent)
parent->next = p;
else
head = p;
start->next = q;
return head;
}
};
void show(ListNode *head)
{
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << endl;
}
int main()
{
ListNode *head=NULL, *p, *q;
for (int i=1; i<=10; i++) {
p = new ListNode(i);
if (!head)
head = p;
else
q->next = p;
q = p;
}
show(head);
Solution so;
head = so.reverseBetween(head, 6, 10);
show(head);
return 0;
}
Raw
reverse_nodes_in_k_group.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/reverse-nodes-in-k-group/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (k <= 1 || !head || !head->next)
return head;
ListNode *parent, *start, *p, *q, *r;
parent = NULL;
start = head;
int i=0;
while (1) {
p = start;
for (i=0; p && i<k; i++)
p = p->next;
if (i < k)
return head;
p = start;
q = p->next;
for (i=1; i<k; i++) {
r = q->next;
q->next = p;
p = q;
q = r;
}
if (parent)
parent->next = p;
else
head = p;
parent = start;
start = q;
parent->next = start;
}
return head;
}
};
void show(ListNode *head)
{
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << endl;
}
int main()
{
ListNode *head=NULL, *p, *q;
for (int i=1; i<=10; i++) {
p = new ListNode(i);
if (!head)
head = p;
else
q->next = p;
q = p;
}
show(head);
Solution so;
head = so.reverseKGroup(head, 10);
show(head);
return 0;
}
Raw
roman2integer.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
using namespace std;
/*
* I - 1
* V - 5
* X - 10
* L - 50
* C - 100
* D - 500
* M - 1000
*/
// About romain integer :
// http://baike.baidu.com/link?url=dE_dQLNKHz4eCF7Omjiak6V8T0adHF9Iw7EQqKsCvKvgH31pbfTshPI3AU_Tfik-
class Solution {
public:
int getWeight(char c) {
switch (c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}
int romanToInt(string s) {
int r=0, n=s.length();
if (n == 0)
return 0;
int w1, w2;
w1 = getWeight(s[0]);
for (int i=1; i<n; i++) {
w2 = getWeight(s[i]);
if (w2 <= w1)
r += w1;
else
r -= w1;
w1 = w2;
}
r += w1;
return r;
}
};
int main()
{
string s;
cin >> s;
Solution so;
int r = so.romanToInt(s);
cout << r << endl;
return 0;
}
Raw
root_to_leaf.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void show(vector<TreeNode*> vec)
{
for (vector<TreeNode*>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << (*it)->val << ' ';
cout << endl;
}
class Solution {
public:
int sumNumbers(TreeNode *root) {
int r = 0;
vector<TreeNode*> vec;
TreeNode *p = root, *q;
while (p) {
vec.push_back(p);
if (!p->left && !p->right) {
int path = 0;
for(vector<TreeNode*>::iterator it=vec.begin(); it!=vec.end(); ++it) {
path = path*10 + (*it)->val;
}
r += path;
vec.pop_back();
vector<TreeNode*>::iterator it=vec.end();
for (;it!=vec.begin(); --it) {
q = *(it-1);
if (q->left == p) {
if (q->right) {
p = q->right;
break;
}
}
vec.pop_back();
p = q;
}
if (it == vec.begin())
break;
}
else {
if (p->left)
p = p->left;
else
p = p->right;
}
}
return r;
}
};
int build_tree(TreeNode *root, int high, int val)
{
if (high == 3)
return val;
root->left = new TreeNode(val++);
root->right = new TreeNode(val++);
high++;
val = build_tree(root->left, high, val);
val = build_tree(root->right, high, val);
}
int main()
{
TreeNode *root;
root = new TreeNode(1);
build_tree(root, 1, 2);
Solution so;
so.sumNumbers(root);
return 0;
}
Raw
rotate_image.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
int m = matrix.size();
if (m == 0)
return ;
int n = matrix[0].size();
int k, t;
k = 0;
while (k < n/2) {
for (int i=k; i<n-k-1; i++) {
t = matrix[k][i];
matrix[k][i] = matrix[m-1-i][k];
matrix[m-1-i][k] = matrix[m-1-k][m-1-i];
matrix[m-1-k][m-1-i] = matrix[i][m-1-k];
matrix[i][m-1-k] = t;
}
k++;
}
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<vector<int> > m;
vector<int> v;
int k=1;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++)
v.push_back(k++);
m.push_back(v);
v.clear();
}
show(m);
Solution so;
so.rotate(m);
show(m);
return 0;
}
Raw
rotate_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/rotate-list/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (k == 0 || !head)
return head;
ListNode *p, *q, *r;
p = head;
int i=0;
while (p) {
p = p->next;
i++;
}
k = k % i;
p = head;
for (i=0; i<k && p; i++)
p = p->next;
if (!p)
return head;
q = head;
while (p->next) {
p = p->next;
q = q->next;
}
p->next = head;
head = q->next;
q->next = NULL;
return head;
}
};
void show(ListNode *head)
{
ListNode *p;
p = head;
while(p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *head=NULL, *p=NULL, *q=NULL;
for (int i=0; i<2; i++) {
if (i == 0) {
p = new ListNode(i+1);
head = p;
}
else {
q = new ListNode(i+1);
p->next = q;
p = q;
}
}
show(head);
Solution so;
head = so.rotateRight(head, 3);
show(head);
return 0;
}
Raw
rotated_array.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int search(int A[], int n, int target) {
if (n == 0)
return -1;
int i, j, k, m, x;
for (i=1; i<n; i++) {
if (A[i] < A[i-1])
break;
}
k = i == n? 0 : i;
i = 0;
j = n - 1;
while (i <= j) {
m = (i + j) / 2;
x = (m + k) % n;
if (A[x] == target)
return x;
if (A[x] > target)
j = m - 1;
else
i = m + 1;
}
return -1;
}
};
int main()
{
int A[] = {4, 5, 6, 7, 0, 1, 2, 3};
Solution so;
int r = so.search(A, 8, 9);
cout << r << endl;
return 0;
}
Raw
rotated_array2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// Allow duplicates
class Solution {
public:
bool search(int A[], int n, int target) {
if (n == 0)
return -1;
int i, j, k, m, x;
for (i=1; i<n; i++) {
if (A[i] < A[i-1])
break;
}
k = i == n? 0 : i;
i = 0;
j = n - 1;
while (i <= j) {
m = (i + j) / 2;
x = (m + k) % n;
if (A[x] == target)
return true;
if (A[x] > target)
j = m - 1;
else
i = m + 1;
}
return false;
}
};
int main()
{
int A[] = {4, 5, 6, 6, 6, 7, 0, 1, 2, 3};
Solution so;
bool r = so.search(A, 10, 7);
cout << r << endl;
return 0;
}
Raw
same_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
TreeNode *pr, *qr;
stack<TreeNode*> stp, stq;
while (p && q) {
if (p->val != q->val)
return false;
if (p->right && q->right) {
stp.push(p->right);
stq.push(q->right);
}
else if (p->right || q->right)
return false;
if (p->left && q->left) {
p = p->left;
q = q->left;
}
else if (p->left || q->left)
return false;
else {
if (stp.empty() && stq.empty())
return true;
p = stp.top();
stp.pop();
q = stq.top();
stq.pop();
}
}
if (!p && !q)
return true;
return false;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root, *p, *left, *right, *q;
for (int i=0; i<10; i++) {
if (i==0) {
p = new TreeNode(i+1);
root = p;
}
left = new TreeNode((i+1) * 10);
right = new TreeNode((i+1) * 15);
p->left = left;
p->right = right;
if (i % 3 == 0)
p = p->left;
else
p = p->right;
}
Solution so;
bool r = so.isSameTree(root, root);
cout << r << endl;
return 0;
}
Raw
scramble_string.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
// 递归超时 ！！
// 动归见 Solution2
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s1.length();
if (n <= 1)
return s1 == s2;
for (int i=1; i<n; i++) {
if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i, n-i), s2.substr(i, n-i)))
return true;
if (isScramble(s1.substr(0, i), s2.substr(n-i, i)) &&
isScramble(s1.substr(i, n-i), s2.substr(0, n-i)))
return true;
}
return false;
}
};
// 动态规划：标记数据（三维）R[n+1][n][n];
// R[i][j][k]表示：长度为i, s1中以s1[j]起始 和 s2中以s2[k]起始的两个子串是否为 scramble
class Solution2 {
public:
bool isScramble(string s1, string s2) {
int n = s1.length();
if (n <= 1)
return s1 == s2;
bool R[n+1][n][n];
memset(R, 0, (n+1)*n*n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
R[0][i][j] = true;
}
}
for (int i=1; i<=n; i++) {
for (int j=0; j<=n-i; j++) {
for (int k=0; k<=n-i; k++) {
if (i == 1) {
R[i][j][k] = s1[j] == s2[k];
continue;
}
for (int l=1; l<i; l++) {
if ((R[l][j][k] && R[i-l][j+l][k+l]) ||
(R[l][j][k+i-l] && R[i-l][j+l][k])) {
R[i][j][k] = true;
break;
}
}
}
}
}
return R[n][0][0];
}
};
int main()
{
string s1, s2;
cin >> s1 >> s2;
Solution2 so;
cout << so.isScramble(s1, s2) << endl;
return 0;
}
Raw
search_2d_matrix.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// binary search
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int m, n;
m = matrix.size();
if (m == 0)
return false;
n = matrix[0].size();
int i=0, j=0, k1=0, k2=n*m-1, idx=0;
while (k1 <= k2) {
idx = (k1 + k2) / 2;
i = idx / n;
j = idx % n;
if (matrix[i][j] == target)
return true;
if (matrix[i][j] < target)
k1 = idx + 1;
else
k2 = idx - 1;
}
return false;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<vector<int> > matrix;
vector<int> row;
for (int i=0; i<10; i++) {
for (int j=0; j<15; j++) {
row.push_back(i*100 + j*2);
}
matrix.push_back(row);
row.clear();
}
show(matrix);
int t;
cin >> t;
Solution so;
bool r = so.searchMatrix(matrix, t);
cout << "Result: " << r << endl;
return 0;
}
Raw
search_for_range.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int> res(2, -1);
int i=0, j=n-1, m;
while (i <= j) {
m = (i + j) / 2;
if (A[m] == target) {
break;
}
else if (A[m] > target)
j = m-1;
else
i = m+1;
}
if (i > j)
return res;
int x, y, k;
res[0] = res[1] = m;
if (m > 0) {
x = i; y = m-1;
while (x < y && A[y]==target) {
k = (x + y) / 2;
if (A[k] == target) {
y = k - 1;
}
else
x = k + 1;
}
if (A[y] == target)
res[0] = y;
else
res[0]= y+1;
}
if (m < n-1) {
x = m+1; y = j;
while (x < y && A[x] == target) {
k = (x + y) / 2;
if (A[k] == target)
x = k + 1;
else
y = k - 1;
}
if (A[x] == target)
res[1] = x;
else
res[1] = x - 1;
}
return res;
}
};
int main()
{
int A[] = {1, 2, 3, 7, 8, 8, 8, 9};
Solution so;
vector<int> res = so.searchRange(A, 8, 6);
cout << res[0] << ' ' << res[1] << endl;
return 0;
}
Raw
search_insert_position.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 二分查找
class Solution {
public:
int searchInsert(int A[], int n, int target){
int i=0, j=n-1, k;
while (i <= j) {
k = (i + j) / 2;
if (A[k] == target)
return k;
if (target < A[k])
j = k-1;
else
i = k+1;
}
return i;
}
};
int main()
{
Solution so;
return 0;
}
Raw
set_matrix_zeroes.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class Solution {
public:
// not using extra space !!
void setZeroes(vector<vector<int> > &matrix) {
int m, n;
m = matrix.size();
if (m == 0)
return;
n = matrix[0].size();
int col1 = 1;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
if (j == 0)
col1 = 0;
else
matrix[0][j] = 0;
}
}
}
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
if (matrix[0][0] == 0)
for (int i=0; i<n; i++)
matrix[0][i] = 0;
if (col1 == 0)
for (int i=0; i<m; i++)
matrix[i][0] = 0;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<vector<int> > matrix;
vector<int> row;
srand(time(0));
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
if(rand() % 7 == 0)
row.push_back(0);
else
row.push_back(1);
}
matrix.push_back(row);
row.clear();
}
show(matrix);
cout << endl;
Solution so;
so.setZeroes(matrix);
show(matrix);
return 0;
}
Raw
single_number.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
using namespace std;
class Solution {
public:
int singleNumber(int A[], int n) {
int res=0;
for (int i=0; i<n; i++)
res = res ^ A[i];
return res;
}
};
int main()
{
Solution so;
return 0;
}
Raw
single_number2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
using namespace std;
void show(int x)
{
int r, c=0;
while (x) {
r = x % 2;
cout << r;
x /= 2;
c++;
}
while (c < 3) {
cout << '0';
c++;
}
cout << endl;
}
// fuck!! wast a lot of time !!!
class Solution {
public:
int singleNumber(int A[], int n) {
unsigned int res=0, flag=0, r=0;
for (int i=0; i<n; i++) {
r = (res ^ A[i]) | flag;
// be careful with flag !! waste a lot of time here !!
flag |= (~res & A[i]);
flag &= (~(res & A[i]));
res = r;
}
return res;
}
};
int main()
{
int A[] = {1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5};
Solution so;
int r = so.singleNumber(A, 14);
cout << r << endl;
return 0;
}
Raw
sort_colors.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void myswap(int &a, int &b)
{
int t;
t = a;
a = b;
b = t;
}
void sortColors(int A[], int n){
int i, j, k=0;
int i1, j1;;
i = i1 = 0;
j = j1 = n-1;
do {
while (i < n && A[i] == 0)
i++;
while (j >= 0 && A[j] == 2)
j--;
if (i > k)
k = i;
if (k > j)
break;
if (A[k] == 2) {
myswap(A[k], A[j]);
j--;
}
if (A[k] == 0) {
myswap(A[i], A[k]);
i++;
}
if (A[k] == 1) {
k++;
}
} while (k <= j);
}
};
void show(int A[], int n){
for (int i=0; i<n; i++)
cout << A[i] << ' ';
cout << endl;
}
int main()
{
int n = 10;
int A[] = {0, 0, 1, 2, 2, 0, 0, 1, 2, 2};
show(A, n);
Solution so;
so.sortColors(A, n);
show(A, n);
return 0;
}
Raw
sort_list.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// merge sort
class Solution {
public:
ListNode *halfSortList(ListNode *head, int n) {
if (n <= 1)
return head;
ListNode *p, *q, *r;
p = head;
for (int i=0; i<n/2-1; i++)
p = p->next;
q = p->next;
p->next = NULL;
ListNode *left, *right, *res=NULL;
left = halfSortList(head, n/2);
right = halfSortList(q, n-n/2);
while (left && right) {
if (left->val <= right->val) {
q = left;
left = left->next;
}
else {
q = right;
right = right->next;
}
if (!res) {
res = p = q;
}
else {
p->next = q;
p = q;
}
}
if (left)
p->next = left;
if (right)
p->next = right;
return res;
}
ListNode *sortList(ListNode *head) {
if (!head || !head->next)
return head;
ListNode *p = head;
int n = 0;
while (p) {
n++;
p = p->next;
}
//cout << n << endl;
p = halfSortList(head, n);
return p;
}
};
void show(ListNode *head)
{
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << endl;
}
int main()
{
ListNode *head;
head = new ListNode(10);
head->next = new ListNode(7);
head->next->next = new ListNode(10);
show(head);
Solution so;
head = so.sortList(head);
show(head);
return 0;
}
Raw
spiral_matrix.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int> > &matrix) {
vector<int> res;
int m=matrix.size();
if (m==0)
return res;
int n = matrix[0].size();
int i=0, j=0, k=0;
while (n-2*k>1 && m-2*k>1) {
i = j = k;
for ( ; j<n-1-k; j++)
res.push_back(matrix[i][j]);
for ( ; i<m-1-k; i++)
res.push_back(matrix[i][j]);
for ( ; j>k; j--)
res.push_back(matrix[i][j]);
for ( ; i>k; i--)
res.push_back(matrix[i][j]);
k++;
}
if (m-2*k == 1 && n - 2*k == 1)
res.push_back(matrix[k][k]);
else if (n-2*k > 1 && m-2*k == 1) {
for (i=j=k; j<n-k; j++)
res.push_back(matrix[i][j]);
}
else if (m-2*k > 1 && n-2*k == 1) {
for (i=j=k; i<m-k; i++)
res.push_back(matrix[i][j]);
}
return res;
}
};
void show(vector<int> r)
{
int n = r.size();
for (int i=0; i<n; i++)
cout << r[i] << ' ';
cout << endl;
}
int main()
{
vector<vector<int> > m;
vector<int> v;
int k=1;
for (int i=0; i<4; i++) {
for (int j=0; j<4; j++)
v.push_back(k++);
m.push_back(v);
v.clear();
}
Solution so;
vector<int> r = so.spiralOrder(m);
show(r);
return 0;
}
Raw
spiral_matrix2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
// vector<int> spiralOrder(vector<vector<int> > &matrix) {
vector<vector<int> > generateMatrix(int n) {
vector<vector<int> > res;
vector<int> vec(n);
for (int i=0; i<n; i++)
res.push_back(vec);
int i=0, j=0, k=0, v=0;
while (k < n/2) {
i = j = k;
for ( ; j<n-1-k; j++)
res[i][j] = ++v;
for ( ; i<n-1-k; i++)
res[i][j] = ++v;
for ( ; j>k; j--)
res[i][j] = ++v;
for ( ; i>k; i--)
res[i][j] = ++v;
k++;
}
if (n % 2)
res[n/2][n/2] = ++v;
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
int n;
cin >> n;
Solution so;
vector<vector<int> > r = so.generateMatrix(n);
show(r);
return 0;
}
Raw
sqrt.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
// http://oj.leetcode.com/problems/sqrtx/
// 利用二分查找减少尝试次数
// 当整数平方根不存在时，向下取整。 如： sqrt(5) = 2;
class Solution {
public:
int sqrt(int x) {
if (x == 0 || x == 1) return x;
const int MAX_SQRT = 46340; // 46341*46341 > 2147483648
int i=1, j=x/2, m, mr;
if (j > MAX_SQRT) j = MAX_SQRT;
while (i <= j) {
m = (i + j) / 2;
mr = m * m;
if (mr == x) return m;
if (mr < x)
i = m + 1;
else
j = m - 1;
}
return j;
}
};
int main()
{
int n;
cin >> n;
Solution so;
int r = so.sqrt(n);
cout << r << endl;
return 0;
}
Raw
str_str.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/implement-strstr/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> preprocess(char *needle) {
vector<int> next(1, 0);
for (int i=1, j=0; needle[i]!='\0'; ) {
while (needle[i] == needle[j]) {
next.push_back(++j);
i++;
}
if (j == 0) {
next.push_back(0);
i++;
}
else
j = next[j-1];
}
return next;
}
char *strStr(char *haystack, char *needle) {
if (*needle == '\0')
return haystack;
vector<int> next = preprocess(needle);
int n=0;
while (needle[n] != '\0')
n++;
int i=0, j=0;
while (haystack[i] != '\0') {
while (haystack[i]!='\0' && needle[j]!='\0' && haystack[i] == needle[j]) {
i++;
j++;
}
if (needle[j] == '\0')
return (haystack + i - n);
else if (j==0)
i++;
else
j = next[j-1];
}
return NULL;
}
};
int main()
{
char *p=new char[20], *q=new char[10];
cin >> p >> q;
Solution so;
char *r = so.strStr(p, q);
cout << r << endl;
return 0;
}
Raw
string_to_integer.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int atoi(const char *str) {
const int MAX = 2147483647;
const int MIN = -2147483648;
const int T = 214748364;
int r = 0, i=0, flag=1;
while (str[i]==' ' || str[i]=='\t' || str[i]=='\n')
i++;
if (str[i] == '-' || str[i] == '+') {
if (str[i] == '-')
flag = -1;
i++;
}
while (str[i] == '0')
i++;
int k=0;
while (str[i] >= '0' && str[i] <= '9') {
if (k == 10 || (k == 9 && r > T)) {
if (flag == -1)
return MIN;
return MAX;
}
if (k == 9 && r == T) {
if (flag == -1 && str[i] == '9')
return MIN;
if (flag == 1 && (str[i] == '8' || str[i] == '9'))
return MAX;
}
r = r * 10 + (str[i] - '0');
i++;
k++;
}
return flag * r;
}
};
int main()
{
char *s = new char[100];
cin >> s;
Solution so;
int r = so.atoi(s);
cout << r << endl;
return 0;
}
Raw
subsets.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void show_one(vector<int> &num)
{
for (vector<int>::iterator it=num.begin(); it!=num.end(); ++it)
cout << *it << ' ';
cout << endl;
}
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res;
vector<int> vec;
int n = S.size(), m=1;
res.push_back(vec);
sort(S.begin(), S.end()); // 原数组不一定有序
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
vec = res[j];
vec.push_back(S[i]);
res.push_back(vec);
}
m = res.size();
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> nums;
for (int i=0; i<3; i++) {
nums.push_back(3-i);
}
Solution so;
vector<vector<int> > r = so.subsets(nums);
cout << endl;
show(r);
// cout << r.size() << endl;
return 0;
}
Raw
subsets2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void show_one(vector<int> &num)
{
for (vector<int>::iterator it=num.begin(); it!=num.end(); ++it)
cout << *it << ' ';
cout << endl;
}
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > res;
vector<int> vec;
int n = S.size(), m=1, lastm=0;
res.push_back(vec);
sort(S.begin(), S.end()); // 原数组不一定有序
int i, j;
for (i=0; i<n; i++) {
if (i>0 && S[i] == S[i-1])
j = lastm;
else
j = 0;
for (; j<m; j++) {
vec = res[j];
vec.push_back(S[i]);
res.push_back(vec);
}
lastm = m;
m = res.size();
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> nums;
for (int i=0; i<2; i++) {
nums.push_back(2-i);
}
nums.push_back(2);
Solution so;
vector<vector<int> > r = so.subsetsWithDup(nums);
show(r);
// cout << r.size() << endl;
return 0;
}
Raw
substrings_with_concatenation_of_all_words.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
// sort ??
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> res;
if (L.size() == 0) return res;
int wl = L[0].size();
int len = wl * L.size();
tr1::unordered_map<string, int> stats;
for (int i=0; i<L.size(); i++)
++stats[L[i]];
int n=S.size();
for (int i=0; i<=n-len; i++) {
tr1::unordered_map<string, int> used(stats);
for (int j=i; j<i+len; j+=wl) {
cout << j << ' ' << wl << endl;
tr1::unordered_map<string, int>::iterator it = used.find(S.substr(j,wl));
if (it == used.end()) break;
if (--(it->second) == 0) used.erase(it);
}
if (used.empty())
res.push_back(i);
}
return res;
}
};
// time limit; 还是采用unordered_map 要快得多 ！
class Solution2 {
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> res;
if (L.size() == 0) return res;
int wl = L[0].size();
int len = wl * L.size();
sort(L.begin(), L.end()); // O(mlogm)
string sl;
int n=S.size(), m=L.size();
for (int i=0; i<m; i++)
sl += L[i];
vector<string> temps;
for (int i=0; i<=n-len; i++) {
for (int j=i; j<i+len; j+=wl) {
temps.push_back(S.substr(j, wl));
}
sort(temps.begin(), temps.end()); // O(mlogm)
string s;
for (int j=0; j<m; j++)
s += temps[j];
if (s == sl) { // O(wl*m)
res.push_back(i);
}
temps.clear();
}
return res;
}
};
int main()
{
string S = "barfoothefoobarman";
vector<string> L;
L.push_back("foo");
L.push_back("bar");
Solution2 so;
vector<int> res = so.findSubstring(S, L);
for (int i=0; i<res.size(); i++)
cout << res[i] << endl;
return 0;
}
Raw
sudoku_solver.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
// http://blog.csdn.net/a83610312/article/details/11845149
// This is my Beautiful Solution !!
// 回溯搜索 + 标记数组
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
const int m = board.size();
if (m != 9) return;
const int n = board[0].size();
if (n != 9) return;
unsigned int row[9], col[9], sq[9];
memset(row, 0, 4*9);
memset(col, 0, 4*9);
memset(sq, 0, 4*9);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j] == '.')
continue;
else if (board[i][j] >= '1' && board[i][j] <= '9') {
unsigned int offset = 1 << (board[i][j]-'1');
int isq = (i/3) * 3 + (j/3);
if (row[i] & offset || col[j] & offset || sq[isq] & offset)
return ;
row[i] |= offset;
col[j] |= offset;
sq[isq] |= offset;
}
else
return ;
}
}
stack<pair<int, int> > filled;
int i=0, j=0, k=1;
while (i < 9) {
if (board[i][j] == '.') { // need to be filled
for (; k<=9; k++) {
unsigned int offset = 1 << (k-1);
int isq = (i/3) * 3 + (j/3);
if (row[i] & offset || col[j] & offset || sq[isq] & offset)
continue;
row[i] |= offset;
col[j] |= offset;
sq[isq] |= offset;
filled.push(pair<int, int>(i*9+j, k));
board[i][j] = '0' + k;
break;
}
}
if (k > 9) {
if (filled.empty()) return ;
pair<int, int> p = filled.top(); filled.pop();
i = p.first / 9; j = p.first % 9;
unsigned int mask = ~(1 << (p.second - 1));
int isq = (i/3) * 3 + (j/3);
row[i] &= mask;
col[j] &= mask;
sq[isq] &= mask;
board[i][j] = '.';
k = p.second + 1;
}
else { // filled sucessfully, or no need to be filled
k = 1;
j++;
if (j == 9) {
j = 0;
i++;
}
}
}
return ;
}
};
void show_sudoku(vector<vector<char> > &board)
{
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++)
cout << board[i][j];
cout << endl;
}
}
int main()
{
vector<char> row(9, '.');
vector<vector<char> > board(9, row);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++)
cin >> board[i][j];
}
show_sudoku(board);
cout << endl;
Solution so;
so.solveSudoku(board);
show_sudoku(board);
return 0;
}
Raw
surrounded_regions.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
// 可能由于递归深度太大，出现问题！！
// 采用广度优先，不需要递归
class Solution {
private:
void spread(vector<vector<char> > &board, int i, int j) {
const int m=board.size(), n=board[0].size();
if (i < 0 || i > m-1 || j < 0 || j > n-1)
return ;
if (board[i][j] == 'X' || board[i][j] == 'Y')
return ;
board[i][j] = 'Y';
spread(board, i, j-1);
spread(board, i-1, j);
spread(board, i, j+1);
spread(board, i+1, j);
}
public:
void solve(vector<vector<char> > &board) {
if (board.empty()) return ;
const int m=board.size(), n=board[0].size();
if (m == 1 || n == 1) return ;
for (int i=0; i<n-1; i++)
spread(board, 0, i);
for (int i=0; i<m-1; i++)
spread(board, i, n-1);
for (int i=n-1; i>0; i--)
spread(board, m-1, i);
for (int i=m-1; i>0; i--)
spread(board, i, 0);
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (board[i][j] == 'Y')
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}
}
};
// 广度优先搜索
class Solution2 {
private:
queue<int> q;
void spread(vector<vector<char> > &board, int i, int j) {
visit(board, i, j);
while (!q.empty()) {
int cur = q.front(); q.pop();
i = cur / board[0].size();
j = cur % board[0].size();
visit(board, i, j-1);
visit(board, i-1, j);
visit(board, i, j+1);
visit(board, i+1, j);
}
}
void visit(vector<vector<char> > &board, int i, int j) {
const int m=board.size(), n=board[0].size();
if (i < 0 || i > m-1 || j < 0 || j > n-1)
return ;
if (board[i][j] == 'X' || board[i][j] == 'Y')
return ;
board[i][j] = 'Y';
q.push(i*n+j);
}
public:
void solve(vector<vector<char> > &board) {
if (board.empty()) return ;
const int m=board.size(), n=board[0].size();
if (m == 1 || n == 1) return ;
for (int i=0; i<n-1; i++)
spread(board, 0, i);
for (int i=0; i<m-1; i++)
spread(board, i, n-1);
for (int i=n-1; i>0; i--)
spread(board, m-1, i);
for (int i=m-1; i>0; i--)
spread(board, i, 0);
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (board[i][j] == 'Y')
board[i][j] = 'O';
else if (board[i][j] == 'O')
board[i][j] = 'X';
}
}
}
};
int main()
{
vector<vector<char> > board;
string s;
while (cin >> s) {
vector<char> row;
for (int i=0; i<s.length(); i++)
row.push_back(s[i]);
board.push_back(row);
}
Solution2 so;
so.solve(board);
return 0;
}
Raw
swap_nodes.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// Swap Nodes in Pairs
// http://oj.leetcode.com/problems/swap-nodes-in-pairs/
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
ListNode *p, *q, *r;
if (head == NULL)
return head;
p = head;
while (p != NULL && p->next != NULL) {
q = p->next;
p->next = q->next;
q->next = p;
if (p == head)
head = q;
else
r->next = q;
r = p;
p = p->next;
}
return head;
}
};
void show(ListNode *head)
{
ListNode *p;
p = head;
while(p) {
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
int main()
{
ListNode *head=NULL, *p=NULL, *q=NULL;
for (int i=0; i<9; i++) {
if (i == 0) {
p = new ListNode(i+1);
head = p;
}
else {
q = new ListNode(i+1);
p->next = q;
p = q;
}
}
show(head);
Solution so;
head = so.swapPairs(head);
show(head);
return 0;
}
Raw
symmetric_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
// bool isSameTree(TreeNode *p, TreeNode *q) {
bool isSymmetric(TreeNode *root) {
if (!root)
return true;
TreeNode *p, *q;
p = root->left;
q = root->right;
stack<TreeNode*> stp, stq;
while (p && q) {
if (p->val != q->val)
return false;
if (p->right && q->left) {
stp.push(p->right);
stq.push(q->left);
}
else if (p->right || q->left)
return false;
if (p->left && q->right) {
p = p->left;
q = q->right;
}
else if (p->left || q->right)
return false;
else {
if (stp.empty() && stq.empty())
return true;
p = stp.top();
stp.pop();
q = stq.top();
stq.pop();
}
}
if (!p && !q)
return true;
return false;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root, *p, *left, *right, *q;
for (int i=0; i<10; i++) {
if (i==0) {
p = new TreeNode(i+1);
root = p;
}
left = new TreeNode((i+1) * 10);
right = new TreeNode((i+1) * 15);
p->left = left;
p->right = right;
if (i % 3 == 0)
p = p->left;
else
p = p->right;
}
Solution so;
bool r = so.isSameTree(root, root);
cout << r << endl;
return 0;
}
Raw
t.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <tr1/unordered_set>
using namespace std;
void foo(vector<int> &vec)
{
vec.push_back(10);
vec.push_back(10);
vec.push_back(10);
}
void show(vector<int> vec)
{
int n=vec.size();
for (int i=0; i<n; i++)
cout << vec[i] << ' ';
cout << endl;
}
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
bool cmp(Interval i1, Interval i2) {
return (i1.start < i2.start);
}
void test_set() {
tr1::unordered_set<string> uns;
string s;
while (cin >> s)
uns.insert(s);
for (int i=0; i<uns.size(); i++)
cout << uns[i] << endl;
}
int main()
{
string s("xyz");
test_set();
return 0;
}
Raw
text_justified.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 没啥难度，注意细节和边界条件
class Solution {
public:
vector<string> fullJustify(vector<string> &words, int L) {
vector<string> res;
int len=0, start=0;
bool enough = false;
string s;
for (int i=0; i<words.size(); i++) {
if (len == 0)
len = words[i].length();
else if (len + words[i].length() + 1 <= L)
len += words[i].length() + 1;
else
enough = true;
if (enough || i == words.size() - 1) {
int n = i - start, remain = L - len;
if (!enough)
n += 1;
s = words[start];
if (n == 1 || !enough) {
for (int j=1; j<n; j++)
s += " " + words[start+j];
s += string(remain, ' ');
}
else {
int extra_space = remain%(n-1);
string gap_space = string(remain/(n-1)+1, ' ');
// s = words[start];
for (int j=1; j<n; j++) {
s += gap_space;
if (j <= extra_space)
s += ' ';
s += words[start+j];
}
}
res.push_back(s);
s.clear();
len = 0;
start = i;
if (enough) // words[i] 没用上
--i;
enough = false;
}
}
return res;
}
};
void show(vector<string> &vs) {
for (int i=0; i<vs.size(); i++)
cout << vs[i] << endl;
}
int main()
{
vector<string> words;
words.push_back("This");
words.push_back("is");
words.push_back("an");
words.push_back("example");
words.push_back("of");
words.push_back("text");
words.push_back("justification.");
int L = 16;
Solution so;
vector<string> res = so.fullJustify(words, L);
show(res);
return 0;
}
Raw
three_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > res;
vector<int> vec(3, 0);
int n = num.size();
if (n < 3)
return res;
sort(num.begin(), num.end());
for (int i=0; i<n-2; i++) {
if (num[i] > 0)
break;
if (i>0 && num[i] == num[i-1])
continue;
vec[0] = num[i];
for (int j=i+1, k=n-1; j<k; ) {
if (j>i+1 && num[j] == num[j-1]) {
j++;
continue;
}
if (k<n-1 && num[k] == num[k+1]) {
k--;
continue;
}
int sm = num[i] + num[j] + num[k];
if (sm == 0) {
vec[1] = num[j];
vec[2] = num[k];
res.push_back(vec);
j++;
k--;
}
else if (sm < 0) {
j++;
}
else {
k--;
}
}
}
return res;
}
};
void show(vector<vector<int> > res)
{
for (vector<vector<int> >::iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
vector<int> num;
num.push_back(-1);
num.push_back(0);
num.push_back(1);
num.push_back(2);
num.push_back(-1);
num.push_back(-4);
num.push_back(1);
num.push_back(0);
Solution so;
vector<vector<int> > res = so.threeSum(num);
show(res);
return 0;
}
Raw
trapping_rain_water.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int trap(int A[], int n) {
int r = 0;
int tail=-1;
for (int i=0; i<n; i++) {
if (tail == -1) {
if (A[i] > 0)
tail = i;
}
else {
if (A[i] >= A[i-1] && i-1==tail)
tail = i;
else if (A[i] > A[i-1]) {
int j, h, b;
j = i-1;
b = A[i-1];
while (A[i] > b && j > tail) {
for (; A[j]<=b; j--)
;
if (A[i] <= A[j])
h = A[i] - b;
else
h = A[j] - b;
r += (i-1-j) * h;
b += h;
}
if (A[i] >= A[tail])
tail = i;
}
}
}
return r;
}
};
int main()
{
int A[] = {0,1,0,2,1,0,1,3,2,1,2,1};
Solution so;
int r = so.trap(A, 12);
cout << r << endl;
return 0;
}
Raw
triangle.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
void show(vector<int> vec, int n)
{
for (int i=0; i<=n; i++)
cout << vec[i] << ' ';
cout << endl;
}
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int n=triangle.size();
if (n == 0)
return 0;
vector<int> scores;
for (int i=n-1; i>=0; i--) {
for (int j=0; j<=i; j++) {
if (i == n-1)
scores.push_back(triangle[i][j]);
else
scores[j] = triangle[i][j] + (scores[j] < scores[j+1]? scores[j] : scores[j+1]);
}
}
return scores[0];
}
};
vector<vector<int> > init() {
srand(time(0));
vector<vector<int> > tri;
vector<int> nums;
int v;
for (int i=1; i<4; i++) {
for (int j=0; j<i; j++) {
// nums.push_back(rand() % 11 + 1);
cin >> v;
nums.push_back(v);
}
tri.push_back(nums);
nums.clear();
}
for (vector<vector<int> >::iterator it=tri.begin(); it!=tri.end(); ++it) {
for (vector<int>::iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
cout << endl;
return tri;
}
int main()
{
vector<vector<int> > tri;
tri = init();
Solution so;
int r = so.minimumTotal(tri);
cout << endl << r << endl;
return 0;
}
Raw
two_sum.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// n2 复杂度的算法居然接受了，考虑高效算法
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
int n = numbers.size(), m;
vector<int> res(2, 0);
for (int i=0; i<n-1; i++) {
res[0] = i+1;
m = target - numbers[i];
for (int j=i+1; j<n; j++) {
if (m == numbers[j]) {
res[1] = j+1;
return res;
}
}
}
}
};
int main()
{
Solution so;
return 0;
}
Raw
unique_bst.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int numTrees(int n) {
if (n == 0 || n == 1)
return 1;
int r = 0;
for (int i=1; i<=n; i++) {
r += numTrees(i-1) * numTrees(n-i);
}
return r;
}
};
int main()
{
int n;
cin >> n;
Solution so;
int r = so.numTrees(n);
cout << r << endl;
return 0;
}
Raw
unique_bst2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int numTrees(int n) {
if (n == 0 || n == 1)
return 1;
int r = 0;
for (int i=1; i<=n; i++) {
r += numTrees(i-1) * numTrees(n-i);
}
return r;
}
vector<TreeNode *> genTrees(int n1, int n2) {
vector<TreeNode *> res;
if (n1 > n2) {
res.push_back(NULL);
return res;
}
vector<TreeNode *> lefts, rights;
TreeNode *root;
for (int i=n1; i<=n2; i++) {
lefts = genTrees(n1, i-1);
rights = genTrees(i+1, n2);
for (int j=0; j<lefts.size(); j++) {
for (int k=0; k<rights.size(); k++) {
root = new TreeNode(i);
root->left = lefts[j];
root->right = rights[k];
res.push_back(root);
}
}
}
return res;
}
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> res;
res = genTrees(1, n);
return res;
}
};
int main()
{
int n;
cin >> n;
Solution so;
int x = so.numTrees(n);
cout << x << endl;
vector<TreeNode *> r = so.generateTrees(n);
cout << r.size() << endl;
return 0;
}
Raw
unique_paths.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
int select(int m, int n) {
int up=1, down=1;
if (n > m/2)
n = m-n;
int facs[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51};
for (; n>=1; n--, m--) {
up *= m;
down *= n;
if (up > 100000) {
for (int i=0; i<17; i++) {
// 防止溢出
while (up%facs[i]==0 && down%facs[i]==0) {
up /= facs[i];
down /= facs[i];
}
}
}
}
return up / down;
}
int uniquePaths(int m, int n) {
int len, r=1;
len = m + n - 2;
return select(len, m-1);
}
};
int main()
{
int m, n;
cin >> m >> n;
Solution so;
int r = so.uniquePaths(m, n);
cout << r << endl;
return 0;
}
Raw
unique_paths2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// Time limit exceeded !
// See Solution2
class Solution {
public:
int uniquePaths(vector<vector<int> > &obstacleGrid, int m, int n, int i, int j) {
if (i == m-1 || j == n-1)
return 1;
int r=0;
if (obstacleGrid[i+1][j] == 0)
r += uniquePaths(obstacleGrid, m, n, i+1, j);
if (obstacleGrid[i][j+1] == 0)
r += uniquePaths(obstacleGrid, m, n, i, j+1);
return r;
}
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
if (m == 0)
return 0;
int n = obstacleGrid[0].size();
if (n == 0)
return 0;
int r = uniquePaths(obstacleGrid, m, n, 0, 0);
return r;
}
};
// 最近老是马马虎虎犯错误，浪费调试时间；注意注意。
class Solution2 {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
if (m == 0)
return 0;
int n = obstacleGrid[0].size();
if (n == 0)
return 0;
vector<vector<int> > notes;
vector<int> vec;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (obstacleGrid[i][j] == 1)
vec.push_back(0);
else if (i == 0 && j == 0)
vec.push_back(1);
else if (i == 0)
vec.push_back(vec[j-1]);
else if (j == 0)
vec.push_back(notes[i-1][j]);
else
vec.push_back(vec[j-1] + notes[i-1][j]);
}
notes.push_back(vec);
vec.clear();
}
return notes[m-1][n-1];
}
};
int main()
{
int m, n;
cin >> m >> n;
Solution so;
// int r = so.uniquePaths(m, n);
//cout << r << endl;
return 0;
}
Raw
valid_numbers.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// Valid Number
// http://oj.leetcode.com/problems/valid-number/
/* Test cases:
* Valid: .10, 10., 1e10, -1e10, -1e-10, 0.1, -0.1, +10, -1e+10
* Invalid: ., e, 10e, 10e6.5, 1.3.3, 1e10e3, 10-4, e10
* spaces only exist at two sides
*/
#include <iostream>
using namespace std;
class Solution {
public:
bool isNumber(const char *s) {
bool e = false, point = false, isn = false;
char last = ' ';
while (*s == ' ' || *s == '\t')
s++;
while(*s != '\0') {
if (*s >= '0' && *s <= '9')
isn = true;
else if (*s == '-' || *s == '+') {
if (last != ' ' && last != 'e') {
return false;
}
isn = false;
}
else if (*s == 'e') {
if (e || !isn)
return false;
e = true;
isn = false;
}
else if (*s == '.') {
if (point || e)
return false;
point = true;
}
else if (*s == ' ' || *s == '\t') {
while (*s == ' ' || *s == '\t')
s++;
if (*s != '\0')
return false;
else
break;
}
else
return false;
last = *s;
s++;
}
return isn;
}
};
int main()
{
char *s = new char[20];
char c;
int i = 0;
while ((c = cin.get()) != '\n') {
s[i++] = c;
}
cout << s << endl;
Solution so;
cout << so.isNumber(s) << endl;
return 0;
}
Raw
valid_palindrome.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
bool isPalindrome(string s) {
int n, i, j;
n = s.length();
i =0;
j=n-1;
char c1, c2;
while (1) {
while (i<n && !isalnum(s[i]))
i++;
while (j>=0 && !isalnum(s[j]))
j--;
if (i >= j)
break;
c1 = s[i];
c2 = s[j];
if (s[i] <= 'Z' && s[i] >= 'A')
c1 = s[i] - 'A' + 'a';
if (s[j] <= 'Z' && s[j] >= 'A')
c2 = s[j] - 'A' + 'a';
if (c1 != c2)
return false;
i++;
j--;
}
return true;
}
};
int main()
{
string s;
getline(cin, s);
Solution so;
bool r = so.isPalindrome(s);
cout << r << endl;
return 0;
}
Raw
valid_parentheses.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool isValid(string s) {
stack<char> pas;
int n = s.length();
for (int i=0; i<n; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
pas.push(s[i]);
else if (s[i] == ')') {
if (!pas.empty() && pas.top() == '(')
pas.pop();
else
return false;
}
else if (s[i] == ']') {
if (!pas.empty() && pas.top() == '[')
pas.pop();
else
return false;
}
else if (s[i] == '}') {
if (!pas.empty() && pas.top() == '{')
pas.pop();
else
return false;
}
}
if (pas.empty())
return true;
return false;
}
};
int main()
{
string s;
cin >> s;
Solution so;
bool r = so.isValid(s);
cout << r << endl;
return 0;
}
Raw
valid_sudoku.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
// http://blog.csdn.net/a83610312/article/details/11845149
// This is my Beautiful Solution !!
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
const int m = board.size();
if (m != 9) return false;
const int n = board[0].size();
if (n != 9) return false;
unsigned int row[9], col[9], sq[9];
memset(row, 0, 4*9);
memset(col, 0, 4*9);
memset(sq, 0, 4*9);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j] == '.')
continue;
else if (board[i][j] >= '1' && board[i][j] <= '9') {
unsigned int offset = 1 << (board[i][j]-'1');
int isq = (i/3) * 3 + (j/3);
if (row[i] & offset || col[j] & offset || sq[isq] & offset)
return false;
row[i] |= offset;
col[j] |= offset;
sq[isq] |= offset;
}
else
return false;
}
}
return true;
}
};
int main()
{
Solution so;
return 0;
}
Raw
validate_bst.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
// http://oj.leetcode.com/problems/validate-binary-search-tree/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> validBST(TreeNode *root) {
vector<int> r;
// r[0]标识该树是否合法；r[1]标识该树的最小值； r[2]标识该树的最大值；
r.push_back(1);
r.push_back(root->val);
r.push_back(root->val);
if (root->left) {
vector<int> left = validBST(root->left);
// 如果左子树非法，或者左子树的最大值大于等于父节点的值， 则父树非法；
if (!left[0] || left[2] >= root->val) {
r[0] = 0;
return r;
}
r[1] = left[1];
}
if (root->right) {
vector<int> right = validBST(root->right);
// 同理，若右子树非法，或者右子树的最小值小于等于父节点的值，则父树非法；
if (!right[0] || right[1] <= root->val) {
r[0] = 0;
return r;
}
r[2] = right[2];
}
return r;
}
bool isValidBST(TreeNode *root) {
if (!root)
return true;
vector<int> res = validBST(root);
if (res[0])
return true;
return false;
}
};
// 利用中序遍历，更简洁的算法
// 对于BST, 中序遍历得到的应该是一个单调有序数列
class Solution2 {
public:
bool isValidBST(TreeNode *root) {
if (!root)
return true;
TreeNode *p;
stack<TreeNode*> bstack;
int maxn;
bool thefirst=true;
p = root;
while (p) {
bstack.push(p);
if (p->left) {
p = p->left;
}
else {
do {
p = bstack.top();
bstack.pop();
if (thefirst) {
maxn = p->val;
thefirst = false;
}
else {
if (p->val > maxn)
maxn = p->val;
else
return false;
}
p = p->right;
} while (!p && !bstack.empty());
}
}
return true;
}
};
void recursive_so(TreeNode *root)
{
if (root == NULL)
return;
cout << root->val << ' ';
recursive_so(root->left);
recursive_so(root->right);
}
void show(vector<int> vec)
{
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout << *it << ' ';
cout << endl;
}
int main()
{
TreeNode *root;
root = new TreeNode(9);
root->left = new TreeNode(8);
root->right = new TreeNode(12);
root->right->left = new TreeNode(6);
Solution so;
bool r = so.isValidBST(root);
cout << r << endl;
Solution2 so2;
bool r2 = so2.isValidBST(root);
cout << r2 << endl;
return 0;
}
Raw
wildcard_matching.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
// 采用二维标记数组会出现 memory limit
// 重点考虑* 号的匹配：* 可以匹配任意长度的任意字符串
// 对于模式串 p = xxx*yyy*xxx, 当两星号之间的子串"yyy" 在s 中有多重匹配方案时，
// 任意采取其中一种即可(只要保证第一个星号之前的子串已经成功匹配)
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
const char *pstar=NULL, *sp;
for (; *s != '\0'; ) {
if (*p == '?' || *p == *s) {
++p; ++s;
}
else if (*p == '*') {
while (*p == '*') ++p;
pstar = p - 1;
sp = s;
}
else {
if (!pstar) return false;
p = pstar + 1;
s = ++sp;
}
}
while (*p == '*') ++p;
return *p == '\0';
}
};
int main()
{
Solution so;
char s[100], p[100];
cin >> s >> p;
cout << so.isMatch(s, p) << endl;
return 0;
}
Raw
word_break.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <tr1/unordered_set>
using namespace std;
/*
* 动态规划：
* R[i] 记录 s[0,i] 是否可分； s[0,i] = s[0]s[1]...s[i-1] , s[0,0] 表示空字符串;
* R[i] = true 当且仅当存在 j < i; R[j] == true && s[j,i+1] 包含在字典dict 中；
*/
class Solution {
public:
bool wordBreak(string s, tr1::unordered_set<string> &dict) {
int n=s.size();
vector<bool> R(n+1, false);
R[0] = true;
for (int i=1; i<=n; i++) {
for (int j=i-1; j>=0; j--) {
if (R[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
R[i] = true;
break;
}
}
}
return R[n];
}
};
int main()
{
Solution so;
return 0;
}
Raw
word_break2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <tr1/unordered_set>
using namespace std;
/*
* 动态规划：
* R[i] 记录 s[0,i] 是否可分； s[0,i] = s[0]s[1]...s[i-1] , s[0,0] 表示空字符串;
* R[i] = true 当且仅当存在 j < i; R[j] == true && s[j,i+1] 包含在字典dict 中；
*/
class Solution {
public:
vector<string> genResult(vector<vector<int> > &X, int n, string &s) {
vector<string> res;
for (int i=0; i<X[n].size(); i++) {
if (X[n][i] == 0) {
res.push_back(s.substr(X[n][i], n-X[n][i]));
continue;
}
vector<string> temps = genResult(X, X[n][i], s);
for (int j=0; j<temps.size(); j++)
res.push_back(temps[j] + " " + s.substr(X[n][i], n-X[n][i]));
}
return res;
}
vector<string> wordBreak(string s, tr1::unordered_set<string> &dict) {
int n=s.size();
vector<vector<int> > X(n+1);
for (int i=1; i<=n; i++) {
for (int j=i-1; j>=0; j--) {
if ((j==0 || X[j].size() > 0) && dict.find(s.substr(j, i-j)) != dict.end())
X[i].push_back(j);
}
}
vector<string> res;
if (X[n].size() > 0)
res = genResult(X, n, s);
return res;
}
};
// Solution2 is tow slow !!
class Solution2 {
public:
vector<string> wordBreak(string s, tr1::unordered_set<string> &dict) {
int n=s.size();
vector<string> res;
for (int i=1; i<=n; i++) {
if (dict.find(s.substr(0, i)) != dict.end()) {
if (i == n) {
res.push_back(s);
continue ;
}
vector<string> temps = wordBreak(s.substr(i, n-i), dict);
for (int j=0; j<temps.size(); j++) {
res.push_back(s.substr(0, i) + " " + temps[j]);
}
}
}
return res;
}
};
void show(vector<string> vs)
{
for (vector<string>::const_iterator it=vs.begin(); it != vs.end(); ++it) {
cout << *it << endl;
}
}
int main()
{
string s="catsanddog";
tr1::unordered_set<string> ss;
ss.insert("cat");
ss.insert("cats");
ss.insert("and");
ss.insert("sand");
ss.insert("dog");
Solution2 so;
vector<string> res = so.wordBreak(s, ss);
show(res);
return 0;
}
Raw
word_ladder.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <tr1/unordered_set>
using namespace std;
// 广度优先搜索
// 如果不利用unordered_map 的快速查找性质，直接遍历dict 会超时
class Solution {
private:
bool compare_pair(string s, string p) {
int diff = 0;
for (int i=0; i<s.length(); i++)
if (s[i] != p[i]) ++diff;
return diff == 1;
}
public:
int ladderLength(string start, string end, tr1::unordered_set<string> &dict) {
vector<string> current(1, start);
vector<string> next(dict.begin(), dict.end());
int deep=0;
while (!current.empty()) {
for (vector<string>::const_iterator it=current.begin(); it!=current.end(); ++it)
if (compare_pair(*it, end)) return deep+2;
vector<string> t, nt;
for (int i=0; i<next.size(); i++) {
string s=next[i];
vector<string>::const_iterator it=current.begin();
for (; it!=current.end(); ++it) {
if (compare_pair(*it, s)) {
t.push_back(s);
break ;
}
}
if (it == current.end()) nt.push_back(s);
}
current=t; next=nt;
++deep;
}
return 0;
}
};
/* dict 可能非常大，而26个字母和单词长度有限，
* 所以通过对"当前"每位单词变换字母，并在dict 中查找新单词的方法更有效率。
* dict 是unordered_map, 查找很快。
* */
class Solution2 {
public:
int ladderLength(string start, string end, tr1::unordered_set<string> &dict) {
queue<string> q;
q.push(start);
int deep=0;
while (!q.empty()) {
queue<string> nextq;
while (!q.empty()) {
string s=q.front(); q.pop();
for (int i=0; i<s.length(); i++) {
for (char c='a'; c<='z'; c++) {
if (c == s[i]) continue;
swap(s[i], c);
if (s == end) return deep+2;
tr1::unordered_set<string>::const_iterator it = dict.find(s);
if (it != dict.end()) {
nextq.push(*it);
dict.erase(it);
}
swap(s[i], c);
}
}
}
q = nextq;
++deep;
}
return 0;
}
};
int main()
{
string start, end;
cin >> start >> end;
tr1::unordered_set<string> dict;
string s;
while (cin >> s) dict.insert(s);
Solution so;
// cout << so.ladderLength(start, end, dict) << endl;
Solution2 so2;
cout << so2.ladderLength(start, end, dict) << endl;
return 0;
}
Raw
word_ladder2.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <tr1/unordered_set>
#include <tr1/unordered_map>
using namespace std;
// 真不容易啊！细节处理！！
class Solution {
private:
vector<vector<string> > genRes(tr1::unordered_map<string, vector<string> > &parents, \
string start, string end)
{
vector<vector<string> > res;
tr1::unordered_map<string, vector<string> >::const_iterator it = parents.find(end);
if (end == start) {
res.push_back(vector<string>(1, start));
return res;
}
for (int i=0; i < parents[end].size(); ++i) {
vector<vector<string> > tmp;
tmp = genRes(parents, start, parents[end][i]);
for (int j=0; j<tmp.size(); j++) {
tmp[j].push_back(end);
res.push_back(tmp[j]);
}
}
return res;
}
public:
vector<vector<string> > findLadders(string start, string end, tr1::unordered_set<string> &dict) {
vector<vector<string> > res;
queue<string> q;
q.push(start);
bool found = false;
// 保存某一个单词是由哪个词变换而来的
// 用于生成最终结果
tr1::unordered_map<string, vector<string> > parents;
dict.erase(start);
while (!q.empty()) {
queue<string> nextq;
tr1::unordered_set<string> added;
while (!q.empty()) { // here !!
string s=q.front(); q.pop();
for (int i=0; i<s.length(); i++) {
for (char c='a'; c<='z'; c++) {
if (c == s[i]) continue;
string t = s; t[i] = c;
// 此时不可能再得到最短的
if (found && t != end) continue ;
if (t == end) {
found = true;
parents[end].push_back(s);
break ;
}
tr1::unordered_set<string>::const_iterator it = dict.find(t);
if (it != dict.end()) {
if (added.find(t) == added.end()) {
nextq.push(t); added.insert(t);
}
parents[t].push_back(s);
}
}
// 如果是由 "t == end" 跳转而来的，则break ;
if (found && s == *(parents[end].end()-1)) break;
}
}
if (found) break;
q = nextq;
// 出现在当前层的词不可能再在后续层出现
while (!nextq.empty()) {
dict.erase(nextq.front());
nextq.pop();
}
}
res = genRes(parents, start, end);
return res;
}
};
void show(vector<vector<string> > res)
{
for (vector<vector<string> >::const_iterator it=res.begin(); it!=res.end(); ++it) {
for (vector<string>::const_iterator it2=(*it).begin(); it2!=(*it).end(); ++it2)
cout << *it2 << ' ';
cout << endl;
}
}
int main()
{
string start, end;
cin >> start >> end;
tr1::unordered_set<string> dict;
string s;
while (cin >> s) dict.insert(s);
Solution so;
vector<vector<string> > res = so.findLadders(start, end, dict);
cout << res.size() << endl;
show(res);
return 0;
}
Raw
word_search.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool detect(vector<vector<char> > &board, int m, int n, int i, int j, string word, int l, int k, vector<vector<int> > &W) {
if (k == l)
return true;
if (i>0 && W[i-1][j]==0 && board[i-1][j]==word[k]) {
W[i-1][j] = 1;
if (detect(board, m, n, i-1, j, word, l, k+1, W))
return true;
W[i-1][j] = 0;
}
if (j>0 && W[i][j-1]==0 && board[i][j-1]==word[k]) {
W[i][j-1] = 1;
if (detect(board, m, n, i, j-1, word, l, k+1, W))
return true;
W[i][j-1] = 0;
}
if (i<m-1 && W[i+1][j]==0 && board[i+1][j]==word[k]) {
W[i+1][j] = 1;
if (detect(board, m, n, i+1, j, word, l, k+1, W))
return true;
W[i+1][j] = 0;
}
if (j<n-1 && W[i][j+1]==0 && board[i][j+1]==word[k]) {
W[i][j+1] = 1;
if (detect(board, m, n, i, j+1, word, l, k+1, W))
return true;
W[i][j+1] = 0;
}
return false;
}
bool exist(vector<vector<char> > &board, string word) {
int l=word.length();
if (l == 0) return true;
int m=board.size();
if (m == 0) return false;
int n=board[0].size();
if (n == 0) return false;
vector<int> row(n, 0);
vector<vector<int> > W;
for (int i=0; i<m; i++)
W.push_back(row);
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (board[i][j] == word[0]) {
W[i][j] = 1;
if (detect(board, m, n, i, j, word, l, 1, W))
return true;
W[i][j] = 0;
}
}
}
return false;
}
};
int main()
{
vector<vector<char> > board;
vector<char> row;
int m, n;
char c;
cin >> m >> n;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
cin >> c;
row.push_back(c);
}
board.push_back(row);
row.clear();
}
string word = "AAB";
Solution so;
bool r = so.exist(board, word);
cout << r << endl;
return 0;
}
Raw
zigzag_conversion.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
string convert(string s, int nRows) {
if (nRows == 1)
return s;
string r;
int n = s.length();
vector<string> strs;
for (int i=0; i<nRows; i++)
strs.push_back("");
int k=0, flag=1;
for (int i=0; i<n; i++) {
strs[k].append(1, s[i]);
k += flag;
if (k == nRows) {
flag = -1;
k = nRows-2;
}
else if (k == -1) {
flag = 1;
k = 1;
}
}
for (int i=0; i<nRows; i++)
r += strs[i];
return r;
}
};
int main()
{
string s;
int n;
cin >> s >> n;
Solution so;
string r = so.convert(s, n);
cout << r << endl;
return 0;
}
Raw
zigzag_level_order_binary_tree.cpp
// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong (rongxiaosong@gmail.com)
//
// LeetCode template for coding and testing
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
TreeNode *p;
stack<TreeNode*> bstack;
stack<int> high;
vector<vector<int> > res;
int h=0, ri=-1;
p = root;
while (p != NULL) {
if (ri < h) {
res.push_back(vector<int> (1,p->val));
ri++;
}
else {
if (h % 2 == 0)
res[h].push_back(p->val);
else
res[h].insert(res[h].begin(), p->val);
}
if (p->right != NULL) {
bstack.push(p->right);
high.push(h+1);
}
if (p->left != NULL) {
p = p->left;
h++;
}
else {
if (bstack.empty())
break;
p = bstack.top();
bstack.pop();
h = high.top();
high.pop();
}
}
return res;
}
};
int main()
{
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment