Chinaunix

标题: ignore~ this is only for me [打印本页]

---

作者: 楼外青楼山外山    时间: 2013-06-17 20:27
标题: 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;
};

---

作者: 楼外青楼山外山    时间: 2013-06-18 13:35
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-18 16:47


delete
ignore

---

作者: 楼外青楼山外山    时间: 2013-06-18 20:12
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-18 21:12
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-19 13:03


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

---

作者: 楼外青楼山外山    时间: 2013-06-19 14:29
//  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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-19 15:01
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-19 16:14
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-19 16:55
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-20 11:46
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-20 13:00
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-20 16:28
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-20 19:52
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-21 11:55
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-21 16:57
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-24 11:52
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-24 15:14
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-24 17:43
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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-25 13:01
// 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;
}

---

作者: 楼外青楼山外山    时间: 2013-06-25 17:13
// Swap Nodes in Pairs:


#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* swapPairs(ListNode* head)
        {
                if (head == 0 || head->next == 0) return head;
               
                ListNode* pswap = head->next;
                head->next = swapPairs(pswap->next);
                pswap->next = head;
                head = pswap;

                return head;
        }         

};

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

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


        Solution solve;
        ListNode* ret = solve.swapPairs(head);

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-06-26 17:28
//Regular Expression Matching:


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

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        bool isMatch(const char* s, const char* p)
        {
                if (*s == '\0') return true;
                if (isEqual(s, p) && *(p+1) != '*') return isMatch(s+1, p+1);

                if (*(p+1) == '*') {
                        const char* ptr = s;
                        for (; isEqual(ptr, p); ++ptr) {
                                if (isMatch(ptr+1, p+2)) return true;
                        }
                }

                return isMatch(s+1, p+2);
        }         

        bool isEqual(const char* c1, const char* c2)
        {
                return (*c1 == *c2) || (*c1 != '\0' && *c2 == '.');
        }
};

int main()
{
        std::string str1("aaxb");
        std::string str2("c*a*.abb");

        Solution solve;
        bool ret = solve.isMatch(str1.c_str(), str2.c_str());

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-06-27 17:19
// Search Insert Position:


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

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        int searchInsert(const int A[], int n, int target)
        {
                if (A[0] > target) return 0;
                if (A[n-1] < target) return n;
                int l = 0;
                int r = n-1;
                while (l <= r) {
                        int mid = (l + r)/2;
                        if (A[mid] == target) return mid;
                        else if (A[mid] < target) {
                                if (A[mid+1] >= target) return mid+1;
                                l = mid+1;
                        } else {
                                if (mid-1 >= 0 && A[mid-1] < target) return mid;
                                r = mid-1;
                        }
                }
        }         
       
};

int main()
{
        int A[] = {1,3,5,6};

        Solution solve;
        int ret = solve.searchInsert(A, sizeof(A)/sizeof(A[0]), 2);

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-06-27 20:57
#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;
typedef unsigned int uint;

class Solution {
public:
        bool solveSudoku(vector<vector<char>>& board)
        {
                if (board.empty()) return false;
                total = 0;

                return this->solveSudoku_impl(board, 0);
        }         

        int solveSudoku_impl(vector<vector<char>>& board, int id)
        {
                while (id < 81 && board[id/9][id%9] != '.') ++id;
                if (id >= 81) {
                        ++total;


                        for (int i = 0; i < 9; ++i) {
                                for (int j = 0; j < 9; ++i) {
                                        std::cout <<board[i][j] <<'\n'
                                }
                        }

                        return total;
                }

                for (int i = 1; i < 9; ++i) {
                        if (validSudoku(board, id/9, id%9, '0'+i)) {
                                board[id/9][id%9] = '0' + i;
                                if (solveSudoku_impl(board, id+1)) return true;
                        }
                }

                board[id/9][id%9] = '.';
        }
       
        bool validSudoku(vector<vector<char>>& board, int row, int col, char cc)
        {
                for (int i = 0; i < 9; ++i) {
                        if (board[row][i] == cc) return false;
                }

                for (int j = 0; j < 9; ++j) {
                        if (board[j][col] == cc) return false;
                }

                for (int i = 0; i < 3; ++i) {
                        for (int j = 0; j < 3; ++j) {
                                if (board[(row/3)*3 + i][(col/3)*3 + j] == cc) return false;
                        }
                }
        }

private:
        int total;
};

int main()
{
        char puzzle[][9] = {\
        {'.','.','.','5','.','.','.','.','.'}, \
        {'.','1','.','.','.','8','.','.','9'}, \
        {'.','.','4','.','.','.','6','.','.'}, \
        {'.','.','.','8','7','.','.','5','.'}, \
        {'4','.','.','.','.','.','.','.','8'}, \
        {'.','.','.','9','.','1','.','.','3'}, \
        {'.','6','.','.','9','.','2','4','.'}, \
        {'.','.','.','.','.','.','.','7','.'}, \
        {'5','4','2','.','.','.','.','3','.'}  \
    };

        vector<vector<char> > board(9, vector<char> (9, '.'));
        /***
        board.resize(9);
        for (int i = 0; i < 9; ++i)
                for (int j = 0; j < 9; ++j) {
                        board[i].push_back(puzzle[i][j]);
                }
        ***/


        Solution solve;
        int ret = solve.solveSudoku(board);

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-07-15 16:26

1. class Solution {
   
2. public:
   
3.     enum Direction {LEFT, DOWN, RIGHT, UP};
   
4. 
   
5.         std::vector<std::vector<int>> generateMatrix(int n)
   
6.         {
   
7.                 if (n < 0) return matrix_;
   
8. 
   
9.                 matrix_ = std::vector<std::vector<int>> (n, std::vector<int>(n, -1));
   
10.                 isUsed_ = std::vector<std::vector<bool>> (n, std::vector<bool>(n, false));
    
11.                 dfs(0, 0, Direction::RIGHT, 1, n*n);
    
12.                 return matrix_;
    
13.         }
    
14. 
    
15.         void dfs(int row, int col, Direction direction, int val, int sum)
    
16.         {
    
17.                 if (!ValidPlace(row, col)) return;
    
18. 
    
19.                 matrix_[row][col] = val;
    
20.                 isUsed_[row][col] = true;
    
21.                 if (val == sum) return;
    
22. 
    
23.                 ++val;
    
24.                 if (direction == Direction::RIGHT) {
    
25.                         if (ValidPlace(row, col+1) && !isUsed_[row][col+1]) {
    
26.                                 dfs(row, col+1, direction, val, sum);
    
27.                         } else if (ValidPlace(row+1, col) && !isUsed_[row+1][col]) {
    
28.                                 dfs(row+1, col, Direction::DOWN, val, sum);
    
29.                         }
    
30. 
    
31.                 } else if (direction == Direction::DOWN) {
    
32.                         if (ValidPlace(row+1, col) && !isUsed_[row+1][col]) {
    
33.                                 dfs(row+1, col, direction, val, sum);
    
34.                         } else if (ValidPlace(row, col-1) && !isUsed_[row][col-1]) {
    
35.                                 dfs(row, col-1, Direction::LEFT, val, sum);
    
36.                         }
    
37. 
    
38.                 } else if (direction == Direction::LEFT) {
    
39.                         if (ValidPlace(row, col-1) && !isUsed_[row][col-1]) {
    
40.                                 dfs(row, col-1, direction, val, sum);
    
41.                         } else if (ValidPlace(row-1, col) && !isUsed_[row-1][col]) {
    
42.                                 dfs(row-1, col, Direction::UP, val, sum);
    
43.                         }
    
44. 
    
45.                 } else if (direction == Direction::UP) {
    
46.                         if (ValidPlace(row-1, col) && !isUsed_[row-1][col]) {
    
47.                                 dfs(row-1, col, direction, val, sum);
    
48.                         } else if (ValidPlace(row, col+1) && !isUsed_[row][col+1]) {
    
49.                                 dfs(row, col+1, Direction::RIGHT, val, sum);
    
50.                         }
    
51. 
    
52.                 }
    
53.         }
    
54. 
    
55.         bool ValidPlace(int row, int col)
    
56.         {
    
57.                 if (row < 0 || row >= matrix_.size()) return false;
    
58.                 if (col < 0 || col >= matrix_[0].size()) return false;
    
59. 
    
60.                 return true;
    
61.         }
    
62. 
    
63. private:
    
64.         std::vector<std::vector<int>> matrix_;
    
65.         std::vector<std::vector<bool>> isUsed_;
    
66. };

复制代码

---

作者: 楼外青楼山外山    时间: 2013-07-16 00:17

1. #include <vector>
   
2. #include <string>
   
3. #include <stack>
   
4. #include <queue>
   
5. #include <set>
   
6. #include <algorithm>
   
7. #include <unordered_set>
   
8. #include <unordered_map>
   
9. 
   
10. using namespace std;
    
11. typedef unsigned int uint;
    
12. 
    
13. 
    
14. class Solution {
    
15.         typedef std::vector<std::vector<std::string>> RetVec;
    
16.         typedef std::pair<std::string, int> Pair;
    
17.         typedef std::unordered_map<std::string, std::unordered_set<std::string>> AdiacencyMap;
    
18. public:
    
19.          RetVec findLadders(std::string& start, std::string& end, std::unordered_set<std::string>& dict)
    
20.         {
    
21.                 if (dict.count(start) == 0) dict.insert(start);
    
22.                 if (dict.count(end) == 0) dict.insert(end);
    
23. 
    
24.                 AdiacencyMap adjacency;
    
25.                 buildAdjacency(dict, adjacency);
    
26. 
    
27.                 backtrace_.clear();
    
28.                 visited_.clear();
    
29.                 visited_.insert(start);
    
30.                 std::queue<std::string> bsfQue;
    
31.                 bsfQue.push(start);
    
32.                 int levelCnt = 1;
    
33.                 int levels = 0;
    
34.                 bool finished = false;
    
35.                 while (!bsfQue.empty() && !finished) {
    
36.                         int loopCnt = levelCnt;
    
37.                         levelCnt = 0;
    
38.                         ++levels;
    
39.                         for (int i = 0; i < loopCnt; ++i) {
    
40.                                 std::string elem = bsfQue.front();
    
41.                                 bsfQue.pop();
    
42.                                 if (valid(elem, end)) {
    
43.                                         backtrace_[end].insert(Pair(elem, levels));
    
44.                                         finished = true;
    
45.                                         continue;
    
46.                                 }
    
47. 
    
48.                                 auto iter = adjacency.find(elem);
    
49.                                 if (iter == adjacency.end()) continue;
    
50. 
    
51.                                 for (auto iterSet = iter->second.begin();
    
52.                                                         iterSet != iter->second.end(); ++iterSet)
    
53.                                 {
    
54.                                         if (visited_.find(*iterSet) == visited_.end()) {
    
55.                                                 visited_.insert(*iterSet);
    
56.                                                 bsfQue.push(*iterSet);
    
57.                                                 ++levelCnt;
    
58.                                         }
    
59. 
    
60.                                         backtrace_[*iterSet].insert(Pair(elem, levels));
    
61.                                 }
    
62.                         }
    
63.                 }
    
64. 
    
65.                 RetVec ret;
    
66.                 std::list<std::string> oneSolution;
    
67.                 buildPath(ret, oneSolution, start, end, levels);
    
68. 
    
69.                 return ret;
    
70.         }
    
71. 
    
72.         void buildPath(RetVec& ret, std::list<std::string>& oneSolution,
    
73.                                         const std::string& start, const std::string& end, int levels)
    
74.         {
    
75.                 if (start == end) {
    
76.                         std::vector<std::string> tmpSolution(oneSolution.begin(), oneSolution.end());
    
77.                         ret.push_back(tmpSolution);
    
78.                         return;
    
79.                 }
    
80. 
    
81.                 --levels;
    
82.                 for (auto iter = backtrace_[end].begin(); iter != backtrace_[end].end(); ++iter) {
    
83.                         if (iter->second == levels) {
    
84.                                 oneSolution.push_front(iter->first);
    
85.                                 buildPath(ret, oneSolution, start, iter->first, iter->second);
    
86.                                 oneSolution.pop_front();
    
87.                         }
    
88.                 }
    
89.         }
    
90. 
    
91.         void buildAdjacency(std::unordered_set<std::string>& dict, AdiacencyMap& adjacency)
    
92.         {
    
93.                 for (auto iter = dict.begin(); iter != dict.end(); ++iter) {
    
94.                         std::string elem = *iter;
    
95.                         for (uint i = 0; i < elem.size(); ++i) {
    
96.                                 for (char cc = 'a'; cc <= 'z'; ++cc) {
    
97.                                         if (elem[i] != cc) {
    
98.                                                 std::string tmpElem(elem);
    
99.                                                 tmpElem[i] = cc;
    
100.                                                 if (dict.count(tmpElem)) adjacency[elem].insert(tmpElem);
     
101.                                         }
     
102.                                 }
     
103.                         }
     
104.                 }
     
105.         }
     
106. 
     
107.         bool valid(const string& start, const string& end)
     
108.         {
     
109.                 if (start.size() != end.size()) return false;
     
110. 
     
111.                 int diff = 0;
     
112.                 for (int i = 0; i < start.size(); ++i) {
     
113.                         if (start[i] != end[i]) ++diff;
     
114.                         if (diff > 1) return false;
     
115.                 }
     
116. 
     
117.                 return diff == 1;
     
118.         }
     
119. 
     
120. private:
     
121.         std::unordered_set<string> visited_;
     
122.         std::unordered_map<std::string, std::unordered_set<Pair>> backtrace_;
     
123. };
     
124. 
     
125. int main()
     
126. {
     
127.         std::unordered_set<std::string> dict;
     
128.         dict.insert("hot");
     
129.         dict.insert("dot");
     
130.         dict.insert("dog");
     
131.         dict.insert("lot");
     
132.         dict.insert("hot");
     
133.         dict.insert("log");
     
134. 
     
135.         Solution solve;
     
136.         string start("hit");
     
137.         string end("cog");
     
138.         std::vector<std::vector<std::string>> ret =
     
139.                 solve.findLadders(start, end, dict);
     
140. 
     
141.         getchar();
     
142.         return 0;
     
143. }
     
144. 
     
145. 
     
146. 
     

复制代码

---

作者: 楼外青楼山外山    时间: 2013-07-16 00:17
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef unsigned int uint;


class Solution {
        typedef std::vector<std::vector<std::string>> RetVec;
        typedef std::pair<std::string, int> Pair;
        typedef std::unordered_map<std::string, std::unordered_set<std::string>> AdiacencyMap;
public:
         RetVec findLadders(std::string& start, std::string& end, std::unordered_set<std::string>& dict)
        {
                if (dict.count(start) == 0) dict.insert(start);
                if (dict.count(end) == 0) dict.insert(end);

                AdiacencyMap adjacency;
                buildAdjacency(dict, adjacency);

                backtrace_.clear();
                visited_.clear();
                visited_.insert(start);
                std::queue<std::string> bsfQue;
                bsfQue.push(start);
                int levelCnt = 1;
                int levels = 0;
                bool finished = false;
                while (!bsfQue.empty() && !finished) {
                        int loopCnt = levelCnt;
                        levelCnt = 0;
                        ++levels;
                        for (int i = 0; i < loopCnt; ++i) {
                                std::string elem = bsfQue.front();
                                bsfQue.pop();
                                if (valid(elem, end)) {
                                        backtrace_[end].insert(Pair(elem, levels));
                                        finished = true;
                                        continue;
                                }

                                auto iter = adjacency.find(elem);
                                if (iter == adjacency.end()) continue;

                                for (auto iterSet = iter->second.begin();
                                                        iterSet != iter->second.end(); ++iterSet)
                                {
                                        if (visited_.find(*iterSet) == visited_.end()) {
                                                visited_.insert(*iterSet);
                                                bsfQue.push(*iterSet);
                                                ++levelCnt;
                                        }

                                        backtrace_[*iterSet].insert(Pair(elem, levels));
                                }
                        }
                }

                RetVec ret;
                std::list<std::string> oneSolution;
                buildPath(ret, oneSolution, start, end, levels);

                return ret;
        }

        void buildPath(RetVec& ret, std::list<std::string>& oneSolution,
                                        const std::string& start, const std::string& end, int levels)
        {
                if (start == end) {
                        std::vector<std::string> tmpSolution(oneSolution.begin(), oneSolution.end());
                        ret.push_back(tmpSolution);
                        return;
                }

                --levels;
                for (auto iter = backtrace_[end].begin(); iter != backtrace_[end].end(); ++iter) {
                        if (iter->second == levels) {
                                oneSolution.push_front(iter->first);
                                buildPath(ret, oneSolution, start, iter->first, iter->second);
                                oneSolution.pop_front();
                        }
                }
        }

        void buildAdjacency(std::unordered_set<std::string>& dict, AdiacencyMap& adjacency)
        {
                for (auto iter = dict.begin(); iter != dict.end(); ++iter) {
                        std::string elem = *iter;
                        for (uint i = 0; i < elem.size(); ++i) {
                                for (char cc = 'a'; cc <= 'z'; ++cc) {
                                        if (elem[i] != cc) {
                                                std::string tmpElem(elem);
                                                tmpElem[i] = cc;
                                                if (dict.count(tmpElem)) adjacency[elem].insert(tmpElem);
                                        }
                                }
                        }
                }
        }

        bool valid(const string& start, const string& end)
        {
                if (start.size() != end.size()) return false;

                int diff = 0;
                for (int i = 0; i < start.size(); ++i) {
                        if (start[i] != end[i]) ++diff;
                        if (diff > 1) return false;
                }

                return diff == 1;
        }

private:
        std::unordered_set<string> visited_;
        std::unordered_map<std::string, std::unordered_set<Pair>> backtrace_;
};

int main()
{
        std::unordered_set<std::string> dict;
        dict.insert("hot");
        dict.insert("dot");
        dict.insert("dog");
        dict.insert("lot");
        dict.insert("hot");
        dict.insert("log");

        Solution solve;
        string start("hit");
        string end("cog");
        std::vector<std::vector<std::string>> ret =
                solve.findLadders(start, end, dict);

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-07-16 18:51
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef unsigned int uint;


class Solution {
        typedef std::vector<std::vector<std::string>> RetVec;
        typedef std::pair<std::string, int> Pair;
        typedef std::unordered_map<std::string, std::unordered_set<std::string>> AdiacencyMap;
public:
         RetVec findLadders(std::string& start, std::string& end, std::unordered_set<std::string>& dict)
        {
                if (dict.count(start) == 0) dict.insert(start);
                if (dict.count(end) == 0) dict.insert(end);

                AdiacencyMap adjacency;
                buildAdjacency(dict, adjacency);

                backtrace_.clear();
                visited_.clear();
                visited_.insert(start);
                std::queue<std::string> bsfQue;
                bsfQue.push(start);
                int levelCnt = 1;
                int levels = 0;
                bool finished = false;
                while (!bsfQue.empty() && !finished) {
                        int loopCnt = levelCnt;
                        levelCnt = 0;
                        ++levels;
                        for (int i = 0; i < loopCnt; ++i) {
                                std::string elem = bsfQue.front();
                                bsfQue.pop();
                                if (valid(elem, end)) {
                                        backtrace_[end].insert(Pair(elem, levels));
                                        finished = true;
                                        continue;
                                }

                                auto iter = adjacency.find(elem);
                                if (iter == adjacency.end()) continue;

                                for (auto iterSet = iter->second.begin();
                                                        iterSet != iter->second.end(); ++iterSet)
                                {
                                        if (visited_.find(*iterSet) == visited_.end()) {
                                                visited_.insert(*iterSet);
                                                bsfQue.push(*iterSet);
                                                ++levelCnt;
                                        }

                                        backtrace_[*iterSet].insert(Pair(elem, levels));
                                }
                        }
                }

                                ++levels;
                RetVec ret;
                std::list<std::string> oneSolution;
                                oneSolution.push_front(end);
                buildPath(ret, oneSolution, start, end, levels);

                return ret;
        }

        void buildPath(RetVec& ret, std::list<std::string>& oneSolution,
                                        const std::string& start, const std::string& end, int levels)
        {
                if (start == end) {
                        std::vector<std::string> tmpSolution(oneSolution.begin(), oneSolution.end());
                        ret.push_back(tmpSolution);
                        return;
                }

                --levels;
                                if (levels < 0) return;
                for (auto iter = backtrace_[end].begin(); iter != backtrace_[end].end(); ++iter) {
                        if (iter->second == levels) {
                                oneSolution.push_front(iter->first);
                                buildPath(ret, oneSolution, start, iter->first, iter->second);
                                oneSolution.pop_front();
                        }
                }
        }

        void buildAdjacency(std::unordered_set<std::string>& dict, AdiacencyMap& adjacency)
        {
                for (auto iter = dict.begin(); iter != dict.end(); ++iter) {
                        std::string elem = *iter;
                        for (uint i = 0; i < elem.size(); ++i) {
                                for (char cc = 'a'; cc <= 'z'; ++cc) {
                                        if (elem[i] != cc) {
                                                std::string tmpElem(elem);
                                                tmpElem[i] = cc;
                                                if (dict.count(tmpElem)) adjacency[elem].insert(tmpElem);
                                        }
                                }
                        }
                }
        }

        bool valid(const string& start, const string& end)
        {
                if (start.size() != end.size()) return false;

                int diff = 0;
                for (int i = 0; i < start.size(); ++i) {
                        if (start[i] != end[i]) ++diff;
                        if (diff > 1) return false;
                }

                return diff == 1;
        }

                struct hashValue {
                        size_t operator() (const Pair& pair) const {
                                size_t seed = 0;
                                std::hash<std::string> hasher;
                                seed ^= hasher(pair.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
                                // seed = std::hash<std::string>()(pair.first);
                                return seed;                       
                        }
                };

                struct keyEqual {
                        bool operator() (const Pair& lhs, const Pair& rhs) const {
                                return lhs.first == rhs.first;
                        }
                };

private:
        std::unordered_set<string> visited_;
                std::unordered_map<std::string, std::unordered_set<Pair, hashValue, keyEqual>> backtrace_;
};

int main()
{
        std::unordered_set<std::string> dict;
        dict.insert("hot");
        dict.insert("dot");
        dict.insert("dog");
        dict.insert("lot");
        dict.insert("hot");
        dict.insert("log");

        Solution solve;
        string start("hit");
        string end("cog");
        std::vector<std::vector<std::string>> ret =
                solve.findLadders(start, end, dict);

        getchar();
        return 0;
}

---

作者: 楼外青楼山外山    时间: 2013-09-06 10:33
class Solution {
public:
        vector<vector<int>> subsets(vector<int>& sub)
        {
                if (sub.empty()) {
                        return vector<vector<int>> ();
                }

                vector<int> result;
                subsetsWithDup_impl(sub, 0, result);
                return subs;
        }

        void subsetsWithDup_impl(vector<int>& sub, int pos,
                vector<int>& result, bool backtrace = false)
        {
                if (pos >= sub.size()) {
                        subs.push_back(result);
                        return;
                }

                subsetsWithDup_impl(sub, pos+1, result);
                result.push_back(sub[pos]);
                subsetsWithDup_impl(sub, pos+1, result);
                result.pop_back();
        }

        vector<vector<int>> subs;
};

---

作者: 楼外青楼山外山    时间: 2013-09-06 10:56
Given a collection of integers that might contain duplicates, S, return all possible subsets.


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

                std::sort(sub.begin(), sub.end());

                vector<int> result;
                subsetsWithDup_impl(sub, 0, result);
                return subs;
        }

        void subsetsWithDup_impl(vector<int>& sub, int pos,
                vector<int>& result)
        {
                if (pos >= sub.size()) {
                        subs.push_back(result);
                        return;
                }

                result.push_back(sub[pos]);
                subsetsWithDup_impl(sub, pos+1, result);
                result.pop_back();

                for (++pos; pos < sub.size() && sub[pos] == sub[pos-1]; ++pos);
                subsetsWithDup_impl(sub, pos, result);
               
        }

        vector<vector<int>> subs;
};

---

作者: 楼外青楼山外山    时间: 2013-09-09 14:11

Remove Duplicates from Sorted Array
int removeDuplicates(int A[], int n)
        {
                int index = -1;
                for (uint i = 1; i < n; ++i) {
                        if (A[i] == A[i-1]) {
                                if (index == -1) index = i;

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

                return index==-1? n: index;
        }

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2