LeetCode OnlineJudge. http://oj.leetcode.com/problems/

3sum_closest.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

add_binary.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

add_two_numbsers.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

anagrams.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

backward.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

#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;
}

balanced_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

basic.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

binary_tree_maximum_path_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

buy_stock.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

buy_stock2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

buy_stock3.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

candy.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

climb_stairs.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

clone_graph.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

#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 ;
}

combination_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

combination_sum2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

combinations.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

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;
    }
};

construct_BT_from_post_in_order.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

construct_BT_from_pre_in_order.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

convert_binary_search_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

convert_list_to_binary_search_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

copy_list_with_random_pointer.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

#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;
}

count_and_say.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

decode_ways.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

distinct_subsequences.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

divide_two_integers.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

edit_distance.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

eval_reverse_polish_notation.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

first_missing_positive.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

flatten_binaty_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

four_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

gas_station.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

generate_parentheses.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

gray_code.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

inorder_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

insert_interval.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

insert_sort.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

integer2roman.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

interleaving_string.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

jump_game2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

largest_rectangle_in_histogram.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

LeetCode

http://oj.leetcode.com/problems/

Learning algorithms.
C++ codes.

length_of_last_word.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

letter_combinations_of_phone_number.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

level_order_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

level_order_binary_tree2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

linked_cycle.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])


#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;
}

linked_cycle2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])


#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;
}

longest_common_prefix.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

longest_consecutive_sequence.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

longest_palindromic_substring.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

#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;
}

longest_parentheses.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

longest_substring_no_repeat.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

lru_cache.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

max_palindrome.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

max_points_on_a_line.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

maximal_rectangle.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

maximum_depth.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

maximum_subarray.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

maxpoints_on_a_line.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

median_of_two_sorted_arrays.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

merge_intervals.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

merge_k_lists.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

merge_sorted_array.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

merge_two_lists.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

minimum_depth.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

minimum_path_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

minimum_window_substring.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

most_water.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
/*  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;
}

multiply_strings.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

n_queen.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

n_queen2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

next_permutation.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

next_right_pointers.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

next_right_pointers2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

palindrome_number.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

palindrome_partition.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

palindrome_partition2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

partition_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

pascal_triangel.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

pascal_triangel2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

path_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

path_sum2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

permulations.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

permulations2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

permutation_sequence.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

plus_one.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

postorder_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

pow.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

preorder_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

recover_bst.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

regular_expression_matching.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

remove_duplicates_sorted_array.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

remove_duplicates_sorted_array2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

remove_duplicates_sorted_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

remove_duplicates_sorted_list2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

remove_element.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

remove_nth_node.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

reorder_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

restore_ip_addr.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

reverse_integer.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

//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;
}

reverse_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

reverse_nodes_in_k_group.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

roman2integer.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

root_to_leaf.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

rotate_image.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

rotate_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

rotated_array.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

rotated_array2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

same_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

scramble_string.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

search_2d_matrix.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

search_for_range.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

search_insert_position.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

set_matrix_zeroes.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

single_number.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

single_number2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

sort_colors.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

sort_list.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

spiral_matrix.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

spiral_matrix2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

sqrt.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

str_str.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

string_to_integer.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

subsets.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

subsets2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

substrings_with_concatenation_of_all_words.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

sudoku_solver.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

surrounded_regions.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

swap_nodes.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
// 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;
}

symmetric_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

t.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

#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;
}

text_justified.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

three_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

trapping_rain_water.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

triangle.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

two_sum.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

unique_bst.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

unique_bst2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

unique_paths.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

unique_paths2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

valid_numbers.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
// 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;
}

valid_palindrome.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

valid_parentheses.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

valid_sudoku.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

validate_bst.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

wildcard_matching.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

word_break.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

word_break2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

word_ladder.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

word_ladder2.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])

// 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;
}

word_search.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

zigzag_conversion.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}

zigzag_level_order_binary_tree.cpp

// Copyright (c) 2013 Peking University.
// Author: Xiaosong Rong ([email protected])
//
// 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;
}