ignore~ this is only for me

楼外青楼山外山

class Solution {
public:
        vector<vector<int> > func(vector<int>& num)
        {
                if (num.empty()) {
                        return vector<vector<int> > ();
                }

                vector<int> result;
                func_impl(num, 0, result);
                return subsets;
        }

        void func_impl(vector<int>& num, int pos,
                        vector<int>& result, bool bt = false)
        {
                if (pos >= num.size()) return;
                if (bt != true) {
                        subsets.push_back(result);
                }

                result.push_back(num[pos]);
                func_impl(num, pos+1, result);
                if (pos+1 == num.size()) {
                        subsets.push_back(result);
                }

                for (++pos; pos < num.size() && num[pos] == num[pos-1]; ++pos);
                result.pop_back();
                func_impl(num, pos, result, true);
        }

        vector<vector<int> > subsets;
};

楼外青楼山外山

Decode Ways：

#include <vector>
#include <string>
#include <iostream>

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        int numDecodings(const string& str)
        {
                if (str.empty()) return 0;               

                vector<int> dp(str.size(), 0);
                if (str[0] != '0') {
                        dp[0] = 1;
                }

                for (uint i = 1; i < str.size(); ++i) {
                        int total = 0;
                        if (valid(str, i-1)) {
                                total += i>1? dp[i-2]: 1;
                                dp[i] = total;
                        }

                        if (str[i] == '0') continue;

                        total += dp[i-1];
                        dp[i] = total;
                }

                return dp[str.size()-1];
        }

        bool valid(const std::string& str, int pos)
        {
                if (pos >= str.size()) return false;
                if (pos == str.size()-1) return false;
                if (str[pos] == '0') return false;
               
                int num = 0;
                int loop = 0;
                while (loop < 2 && pos < str.size()) {
                        num = num * 10 + str[pos] - '0';
                        ++pos;
                        ++loop;
                }
       
                if (num > 26 || num < 1) return false;
                        return true;
        }
       
};

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

        getchar();
        return 0;
}

楼外青楼山外山

delete
ignore

楼外青楼山外山

class Solution {
public:
        void merge(int A[], int m, int B[], int n)
        {
                int i = m-1;
                int j = n-1;
                int k = m+n-1;
                while (i >= 0 && j >= 0) {
                        A[k--] = A[i]<B[j]? B[j--]: A[i--];
                }

                while (j >= 0) A[k--] = B[j--];
        }
       
};

int main()
{
        int A[] = {1, 3, 5, 6, 8, 0, 0, 0, 0, 0};
        int B[] = {2, 4, 7, 9, 11};
        Solution solve;
        solve.merge(A, 5, B, 5);

        getchar();
        return 0;
}

楼外青楼山外山

Partition List

#include <vector>
#include <string>
#include <iostream>

using namespace std;
typedef unsigned int uint;

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

class Solution {
public:
        ListNode* partition(ListNode* head, int val)
        {
                if (head == 0) return 0;

                ListNode* pre = 0;
                ListNode* pIndex = head;
                while (pIndex->val <= val) {
                        pre = pIndex;
                        pIndex = pIndex->next;
                }

                if (pIndex == 0) return head;
                pIndex = pIndex->next;
                if (pIndex == 0) return head;
                       
                while (pIndex) {
                        ListNode* preIndex = 0;
                        for (; pIndex->val >= val; preIndex = pIndex,
                                                                pIndex = pIndex->next);
                       
                        if (pIndex) {
                                ListNode* tmp = pIndex->next;
                                preIndex->next = tmp;
                                if (pre) {
                                        pIndex->next = pre->next;
                                        pre->next = pIndex;
                                } else {
                                        pIndex->next = head;
                                        head = pIndex;
                                }

                                pIndex = tmp;
                        }
                         
                }

                return head;
        }
       
};

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

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = node6;

        Solution solve;
        solve.partition(node1, 3);

        getchar();
        return 0;
}

楼外青楼山外山

gray code：
class Solution {
public:
        vector<int> grayCode(int n)
        {
                vector<int> codes;
                codes.push_back(0);
                for (int i = 0; i < n; ++i) {
                        for (int j = codes.size()-1; j >= 0; --j) {
                                codes.push_back(codes[j] + (1<<i));
                        }
                }

                return codes;
        }
       
};

int main()
{
        Solution solve;
        vector<int> ret = solve.grayCode(3);

        getchar();
        return 0;
}

楼外青楼山外山

//  Remove Duplicates from Sorted List

class Solution {
public:
        ListNode* deleteDuplicates(ListNode* head)
        {
                if (head == 0) return 0;

                ListNode* pre = head;
                ListNode* pNode = head->next? head->next: 0;
                if (pNode == 0) return head;

                while (pre) {
                        while (pNode && pre->val != pNode->val) {
                                pre = pNode;
                                pNode = pNode->next;
                        }

                        if (pNode == 0) return head;
                        for (; pNode->next && pNode->val == pNode->next->val; pNode = pNode->next);

                        pre->next = pNode->next;
                        delete pNode;
                        pNode = pre->next;
                }
        }
       
};

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

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        //node5->next = node6;
        node6->next = node7;

        Solution solve;
        solve.deleteDuplicates(node1);

        getchar();
        return 0;
}

楼外青楼山外山

Remove Duplicates from Sorted List II:
struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        ListNode* deleteDuplicates(ListNode* head)
        {
                if (head == 0) return 0;

                ListNode* pre = 0;
                ListNode* pNode = head;
                if (pNode == 0) return head;

                while (pNode) {
                        while (pNode && pNode->next && pNode->val != pNode->next->val) {
                                pre = pNode;
                                pNode = pNode->next;
                        }

                        if (pNode->next == 0) return head;
                        for (; pNode->next && pNode->val == pNode->next->val; pNode = pNode->next);

                        if (pre) {
                                pre->next = pNode->next;
                        } else {
                                pre = pNode->next;
                                head = pre;
                        }
                       
                        if (pre) pNode = pre->next;
                }
        }
       
};

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

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = node6;
        node6->next = node7;

        Solution solve;
        ListNode* ptr = solve.deleteDuplicates(node1);

        getchar();
        return 0;
}

楼外青楼山外山

// Remove Duplicates from Sorted Array
class Solution {
public:
        int removeDuplicates(int A[], int n)
        {
                int index = -1;
                for (int i = 1; i < n; ++i) {
                        if (A[i] != A[i-1]) {
                                if (index != -1) A[index++] = A[i];
                                continue;
                        }

                        if (index == -1) index = i;
                        for (++i; i < n && A[i] == A[i-1]; ++i);
                        if (i >= n) return index;
                        A[index++] = A[i];
                }

                return index;
        }
       
};

int main()
{
        int A[] = {1,1,2,2,3,4,5,6,7,7,7,7,8,9,9,9};
        Solution solve;
        int ret = solve.removeDuplicates(A, sizeof(A)/sizeof(A[0]));

        getchar();
        return 0;
}

楼外青楼山外山

// Remove Duplicates from Sorted Array II
class Solution {
public:
        int removeDuplicates(int A[], int n)
        {
                int index = -1;
                for (int i = 1; i < n; ++i) {
                        if (A[i] != A[i-1]) {
                                if (index != -1) A[index++] = A[i];
                                continue;
                        }

                        if (i < n-1 && A[i] == A[i+1]) {
                                if (index != -1) A[index++] = A[i];
                                if (index == -1) index = ++i;
                                for (++i; i < n && A[i] == A[i-1]; ++i);
                                if (i < n) A[index++] = A[i];
                                continue;
                        }

                        if (index != -1) A[index++] = A[i];
                }

                return index;
        }
       
};

int main()
{
        int A[] = {1,1,1,2,2,3};
        Solution solve;
        int ret = solve.removeDuplicates(A, sizeof(A)/sizeof(A[0]));
        A[ret] = 0;

        getchar();
        return 0;
}