ignore~ this is only for me

楼外青楼山外山

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

楼外青楼山外山

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

楼外青楼山外山

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

楼外青楼山外山

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

楼外青楼山外山

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

复制代码

楼外青楼山外山

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. 
     

复制代码

楼外青楼山外山

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

楼外青楼山外山

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

楼外青楼山外山

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

楼外青楼山外山

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