ignore~ this is only for me

楼外青楼山外山

// Longest Valid Parentheses:
class Solution {
public:
        int longestValidParentheses(const string& str)
        {
                std::stack<int> token;
                int max = 0;
                int succesiveNum = 0;
                for (int i = 0; i < str.size(); ++i) {
                        if (str[i] == '(') {
                                token.push(str[i]);
                        } else if (str[i] == ')') {
                                if (token.empty()) {
                                        if (succesiveNum) {
                                                max = std::max(max, succesiveNum);
                                                succesiveNum = 0;
                                        }

                                        continue;
                                }

                                token.pop();
                                ++succesiveNum;
                        }
                }

                return std::max(max, succesiveNum) * 2;
        }
       
};

int main()
{
        //std::string str("))(((())))()())()()((()()(");
        std::string str("))((((()()()()()))");
        Solution solve;
        int ret = solve.longestValidParentheses(str);

        getchar();
        return 0;
}

楼外青楼山外山

Reverse Integer:
class Solution {
public:
        int reverse(int x)
        {
                int flag = 1;
                if (x < 0) {
                        x = -x;
                        flag = -1;
                }

                int num = 0;
                while (x) {
                        num = num*10 + x%10;
                        x /= 10;
                }

                return num * flag;
        }
       
};

int main()
{
        Solution solve;
        int ret = solve.reverse(-12300);

        getchar();
        return 0;
}

楼外青楼山外山

Add Two Numbers:

struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        ListNode* addTwoNumbers2(const ListNode* a, const ListNode* b)
        {
                ListNode* pLink = 0;
                ListNode* head = 0;
                int carry = 0;
                while (a && b) {
                        int node = a->val + b->val + carry;
                        ListNode* ptmp = new ListNode(node%10);
                        carry = (node > 9? 1: 0);
                       
                        !pLink? (pLink = ptmp, head = pLink): (pLink->next = ptmp, pLink = ptmp);
                        a = a->next;
                        b = b->next;
                }

                const ListNode* ptr = a? a: b;

                while (ptr) {
                        int node = ptr->val + carry;
                        ListNode* ptmp = new ListNode(node%10);
                        carry = (node > 9? 1: 0);
                        !pLink? (pLink = ptmp, head = pLink): (pLink->next = ptmp, pLink = ptmp);
                        ptr = ptr->next;
                }

                if (carry) {
                        ListNode* ptmp = new ListNode(carry);
                        pLink->next = ptmp;
                }

                return head;
        }
       
        ListNode* addTwoNumbers(const ListNode* a, const ListNode* b)
        {
                return this->addTwoNumbers_Recursive(a, b, 0);
        }

        ListNode* addTwoNumbers_Recursive(const ListNode* a, const ListNode* b,
                                                                        int carry = 0)
        {
                if (!a && !b) {
                        if (!carry) return 0;

                        ListNode* pNode = new ListNode(carry);
                        return pNode;
                }

                carry += a? a->val: 0;
                carry += b? b->val: 0;
                ListNode* pNode = new ListNode(carry % 10);
                ListNode* plast = addTwoNumbers_Recursive(a? a->next: 0, b? b->next: 0, carry/10);
                pNode->next = plast;

                return pNode;
        }

};

int main()
{
        ListNode* a1 = new ListNode(1);
        ListNode* a2 = new ListNode(4);
        a1->next = a2;

        ListNode* b1 = new ListNode(1);
        ListNode* b2 = new ListNode(6);
        ListNode* b3 = new ListNode(5);
        b1->next = b2;
        b2->next = b3;

        Solution solve;
        ListNode* ret = solve.addTwoNumbers(a1, b1);

        getchar();
        return 0;
}

楼外青楼山外山

Two Sum://
bool cmp(std::pair<int, int> lop, std::pair<int, int> rop)
{
        return lop <= rop? true: false;
}

class Solution {
public:
        vector<int> twoSum(vector<int>& numbers, int target)
                {
                        vector<std::pair<int, int>> nums;
                        nums.reserve(numbers.size());
                        for (int i = 0; i < numbers.size(); ++i) {
                                nums.push_back(std::pair<int, int> (numbers[i], i+1));
                        }

                        vector<int> result;
                        std::sort(nums.begin(), nums.end(), cmp);
                        uint i = 0;
                        uint j = nums.size()-1;
                        while (i < j) {
                                if (nums[i].first + nums[j].first < target) ++i;
                                else if (nums[i].first + nums[j].first > target) --j;
                                else {
                                        int min = std::min(nums[i].second, nums[j].second);
                                        int max = std::max(nums[i].second, nums[j].second);
                                        result.push_back(min);
                                        result.push_back(max);

                                        return result;
                                }
                        }
        }        

};

int main()
{
        std::vector<int> num;
        num.push_back(2);
        num.push_back(9);
        num.push_back(1);
        num.push_back(;
        num.push_back(7);
        num.push_back(10);

        Solution solve;
        vector<int> ret = solve.twoSum(num, 16);

        getchar();
        return 0;
}

楼外青楼山外山

// longestValidParentheses::


class Solution {
public:
        int longestValidParentheses(const string& str)
        {
                std::vector<int> dp(str.size(), 0);
                int max = 0;
                for (int i = 1; i < str.size(); ++i) {
                        if (str[i] == '(') dp[i] = 0;
                        else if (str[i] == ')') {
                                if (str[i-1] == '(' && i-1 > 0) dp[i] = dp[i-2] + 1;
                                else if (str[i-1] == '(' && i-1 <= 0) dp[i] = 1;
                                else if (str[i-1] == ')' && dp[i-1]) {
                                        dp[i] = i-1-dp[i-1]*2 >=0? (str[i-1-dp[i-1]*2] != str[i]? dp[i-1]+1: 0): 0;
                                }
                       
                                max = std::max(max, dp[i]);
                        }
                }

                return max*2;
        }
};

int main()
{
        std::string str("))(((())))()())()()((()()(");
    // std::string str("()()((");

        Solution solve;
        int ret = solve.longestValidParentheses(str);

        getchar();
        return 0;
}

楼外青楼山外山

Longest Palindromic Substring：

#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        std::string longestPalindrome(const string& str)
        {
                int max = 0;
                int max_s = 0;
                for (int i = 1; i < str.size(); ++i) {
                        int len = 0;
                        int pos = countPalindrome(str, i-1, i, len);
                        if (max < len) {
                                max = len;
                                max_s = pos+1;
                        }

                        pos = countPalindrome(str, i-1, i+1, len);
                        if (max < len) {
                                max = len;
                                max_s = pos+1;
                        }

                }

                return str.substr(max_s, max);
        }

        int countPalindrome(const string& str, int s, int e, int& len)
        {
                while (s >= 0 && e < str.size()) {
                        if (str[s] == str[e]) {
                                --s;
                                ++e;
                                continue;
                        }

                        len = e-s-1;
                        return s;
                }

                len = e-s-1;
                return s;
        }
};

int main()
{
        std::string str("abcfcba123414321111111123414321abcfcba");
    // std::string str("()()((");

        Solution solve;
        string ret = solve.longestPalindrome(str);

        getchar();
        return 0;
}

楼外青楼山外山

// Longest Common Prefix


#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        string longestCommonPrefix(vector<string>& strs)
        {
                if (strs.empty()) return "";

                uint maxLen = strs[0].size();
                for (uint i = 1; i < strs.size(); ++i) {
                        maxLen = std::min(maxLen, strs[i].size());
                }

                for (uint i = 1; i < strs.size(); ++i) {
                        maxLen = std::min(maxLen, compare(strs[i-1], strs[i], maxLen));
                }

                return strs[0].substr(0, maxLen);
        }

        uint compare(const string& s1, const string& s2, int maxLen)
        {
                for (uint i = 0; i < maxLen; ++i) {
                        if (s1[i] != s2[i]) return i;
                }

                return maxLen;
        }

};

int main()
{
        vector<string> vec;
        vec.push_back("abcdxwde");
        vec.push_back("abcdxwdf");
        vec.push_back("abcdxwda");
        vec.push_back("abcdewda");
        vec.push_back("abcdvmooo");


        Solution solve;
        string ret = solve.longestCommonPrefix(vec);

        getchar();
        return 0;
}

楼外青楼山外山

Letter Combinations of a Phone Number: //


#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        vector<string> letterCombinations(string& digits)
        {
                string tmpStr;
                this->letterCombinations_impl(digits, 0, tmpStr);

                return letterVec;
        }

        void letterCombinations_impl(string& digits, int pos, string letter)
        {
                if (pos >= digits.size()) {
                        letterVec.push_back(letter);

                        return ;
                }

                char cc = digits[pos];
                if (cc == '0') {
                        letterVec.push_back(letter);
                } else if (cc == '2') {
                        letterCombinations_impl(digits, pos+1, letter+'a');
                        letterCombinations_impl(digits, pos+1, letter+'b');
                        letterCombinations_impl(digits, pos+1, letter+'c');
                } else if (cc == '3') {
                        letterCombinations_impl(digits, pos+1, letter+'d');
                        letterCombinations_impl(digits, pos+1, letter+'e');
                        letterCombinations_impl(digits, pos+1, letter+'f');
                } else if (cc == '4') {
                        letterCombinations_impl(digits, pos+1, letter+'g');
                        letterCombinations_impl(digits, pos+1, letter+'h');
                        letterCombinations_impl(digits, pos+1, letter+'i');
                } else if (cc == '5') {
                        letterCombinations_impl(digits, pos+1, letter+'j');
                        letterCombinations_impl(digits, pos+1, letter+'k');
                        letterCombinations_impl(digits, pos+1, letter+'l');
                } else if (cc == '6') {
                        letterCombinations_impl(digits, pos+1, letter+'m');
                        letterCombinations_impl(digits, pos+1, letter+'n');
                        letterCombinations_impl(digits, pos+1, letter+'o');
                } else if (cc == '7') {
                        letterCombinations_impl(digits, pos+1, letter+'p');
                        letterCombinations_impl(digits, pos+1, letter+'q');
                        letterCombinations_impl(digits, pos+1, letter+'r');
                        letterCombinations_impl(digits, pos+1, letter+'s');
                } else if (cc == '8') {
                        letterCombinations_impl(digits, pos+1, letter+'t');
                        letterCombinations_impl(digits, pos+1, letter+'u');
                        letterCombinations_impl(digits, pos+1, letter+'v');
                } else if (cc == '9') {
                        letterCombinations_impl(digits, pos+1, letter+'w');
                        letterCombinations_impl(digits, pos+1, letter+'x');
                        letterCombinations_impl(digits, pos+1, letter+'y');
                        letterCombinations_impl(digits, pos+1, letter+'z');
                } else {
                        return;
                }
        }

private:
        vector<string> letterVec;
};

int main()
{
        string str("2");

        Solution solve;
        vector<string> ret = solve.letterCombinations(str);

        getchar();
        return 0;
}

楼外青楼山外山

Remove Nth Node From End of List ://


#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;
typedef unsigned int uint;

struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        ListNode* removeNthFromEnd(ListNode* head, int n)
        {
                ListNode* pNode = head;
                for (int i = 1; i < n && pNode; ++i, pNode = pNode->next);
                if (pNode == 0) return 0;

                ListNode* pre = head;
                ListNode* parent = 0;
                while (pNode->next) {
                        pNode = pNode->next;
                        parent = pre;
                        pre = pre->next;
                }

                if (parent) parent->next = pre->next;
                else head = pre->next;

                return head;
        }

};

int main()
{
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(3);
        ListNode* node4 = new ListNode(4);
        ListNode* node5 = new ListNode(5);
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;

        Solution solve;
        ListNode* ret = solve.removeNthFromEnd(node1, 2);

        getchar();
        return 0;
}

楼外青楼山外山

// Merge k Sorted Lists:

struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        ListNode* mergeKLists(const vector<ListNode*>& lists)
        {
                return mergeKLists_impl(lists, 0, lists.size()-1);
        }         

        ListNode* mergeKLists_impl(const vector<ListNode *>& lists, int l, int r)
        {
                if (l >= r) return lists[l];

                int mid = (l+r)/2;
                ListNode* left = mergeKLists_impl(lists, l, mid);
                ListNode* right = mergeKLists_impl(lists, mid+1, r);

                return merge(left, right);
        }

        ListNode* merge(ListNode* left, ListNode* right)
        {
                ListNode* head = 0;
                ListNode* pre = head;
                while (left && right) {
                        ListNode*& ptmp = (left->val <= right->val)? left: right;
                        if (head == 0) {
                                head = ptmp, pre = head;
                        } else {
                                pre->next = ptmp;
                                pre = ptmp;
                        }
                       
                        ptmp = ptmp->next;
                }

                ListNode*& ptmp = left? left: right;
                while (ptmp) {
                        pre->next = ptmp;
                        ptmp = ptmp->next;
                }

                return head;
        }

};

int main()
{
        ListNode* head1 = new ListNode(1);
        ListNode* node11 = new ListNode(5);
        ListNode* node12 = new ListNode(7);
        head1->next = node11;
        node11->next = node12;

        ListNode* head2 = new ListNode(2);
        ListNode* node21 = new ListNode(6);
        ListNode* node22 = new ListNode(9);
        head2->next = node21;
        //node21->next = node22;

        ListNode* head3 = new ListNode(3);
        ListNode* node31 = new ListNode(4);
        ListNode* node32 = new ListNode(11);
        head3->next = node31;
        node31->next = node32;

        vector<ListNode *> lists;
        lists.push_back(head1);
        lists.push_back(head2);
        lists.push_back(head3);

        Solution solve;
        ListNode* ret = solve.mergeKLists(lists);

        getchar();
        return 0;
}