分享我的Lintcode题解，目前进度244/248

又被吞掉一题：Unique Binary Search Trees

审核的人干嘛去了？在跟公务员比效率吗？审核五天之内不给通过的话，审核员全家都是孙子。有种删我贴啊~
不让我贴代码，我躲得起。回自己博客去写不就得了。
来这儿是为了分享和互相学习编程经验，你审核能别处处碍事吗？真可恶。

1. print '审核员是我',
   
2. while True:
   
3.     print '儿子的',
   

复制代码

zhuli19901106 发表于 2015-7-23 17:26
审核的人干嘛去了？在跟公务员比效率吗？审核五天之内不给通过的话，审核员全家都是孙子。有种删我贴啊~
...

别上火，有可能是系统本身的问题。我在另外一个论坛（同样是powered by discuz!的论坛）做版主，结果有时自己发的帖子都会被提示“审核中”，但是我在后台又找不到自己发的待审核的帖。

stellari 发表于 2015-7-23 18:07
别上火，有可能是系统本身的问题。我在另外一个论坛（同样是powered by discuz!的论坛）做版主，结果有时 ...

“被审核”三个字真的非常打击积极性。好比我认真思考自己写过的代码，总结思路，查漏补缺。然后按下“回复”的一瞬间，帖子没了。不知道多少天后才能突然出现，也没准就被删了。

我本人对政治很反感，所以碰见网络审查时尤其火大~~哎

Unique Binary Search Trees II
题意：如果一棵BST的中序遍历恰好是1-N。求出这棵树的所有可能的形态。要求以数组的形式返回所有树的根节点。
解法：我还以为这题会定义成hard难度呢，因为我做的时候感觉这题挺复杂的。做法肯定是要递归，因为要求出所有可能的树，那么递归就从“选取根节点”来入手。每个位置都可以作为根节点，求出来的树也各不相同。处理左右子树时也要考虑周全，尤其是空子树。总的来说，这题对我是hard难度，写的代码也出了些bug，做得并不轻松。
对了，这题我还对搜索结果做了记忆化处理。用哈希表保存了子问题的解，这样可以避免重复计算。即使这样，这题的时空复杂度还是相当高的。所以，不进行优化必然要超时。
代码：

1. #include <unordered_map>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      * @paramn n: An integer
    
19.      * @return: A list of root
    
20.      */
    
21.     vector<TreeNode *> generateTrees(int n) {
    
22.         if (n == 0) {
    
23.             // Special case
    
24.             vector<TreeNode *> v;
    
25.             v.push_back(NULL);
    
26.             return v;
    
27.         }
    
28.         
    
29.         int i;
    
30.         this->n = n;
    
31.         id.resize(n);
    
32.         for (i = 0; i < n; ++i) {
    
33.             id[i] = i + 1;
    
34.         }
    
35.         this->um.clear();
    
36.         constructTree(0, n - 1);
    
37.         return um[n - 1];
    
38.     }
    
39. private:
    
40.     unordered_map<int, vector<TreeNode *> > um;
    
41.     vector<int> id;
    
42.     int n;
    
43.    
    
44.     void constructTree(int ll, int rr) {
    
45.         if (um.find(ll * n + rr) != um.end()) {
    
46.             return;
    
47.         }
    
48.         vector<TreeNode *> v;
    
49.         if (ll == rr) {
    
50.             v.push_back(new TreeNode(id[ll]));
    
51.             um[ll * n + rr] = v;
    
52.             return;
    
53.         }
    
54.         
    
55.         int i;
    
56.         TreeNode *p;
    
57.         vector<TreeNode *> *pl, *pr;
    
58.         
    
59.         constructTree(ll + 1, rr);
    
60.         pl = &(um[(ll + 1) * n + rr]);
    
61.         for (i = 0; i < pl->size(); ++i) {
    
62.             p = new TreeNode(id[ll]);
    
63.             p->right = (*pl)[i];
    
64.             v.push_back(p);
    
65.         }
    
66.         
    
67.         constructTree(ll, rr - 1);
    
68.         pl = &(um[ll * n + rr - 1]);
    
69.         for (i = 0; i < pl->size(); ++i) {
    
70.             p = new TreeNode(id[rr]);
    
71.             p->left = (*pl)[i];
    
72.             v.push_back(p);
    
73.         }
    
74.         
    
75.         int j, k;
    
76.         for (i = ll + 1; i < rr; ++i) {
    
77.             constructTree(ll, i - 1);
    
78.             constructTree(i + 1, rr);
    
79.             pl = &(um[ll * n + i - 1]);
    
80.             pr = &(um[(i + 1) * n + rr]);
    
81.             for (j = 0; j < pl->size(); ++j) {
    
82.                 for (k = 0; k < pr->size(); ++k) {
    
83.                     p = new TreeNode(id[i]);
    
84.                     p->left = (*pl)[j];
    
85.                     p->right = (*pr)[k];
    
86.                     v.push_back(p);
    
87.                 }
    
88.             }
    
89.         }
    
90.         um[ll * n + rr] = v;
    
91.     }
    
92. };

复制代码

复杂度：时间O(H(N))，空间一样。H(N)表示第N项Catalan数。

Merge Two Sorted Lists
题意：给定两个有序链表，归并成一条。
解法：基础题。既可以用一个额外的dummy node作为头节点，以便简化代码。也可以多写点代码，不用额外的节点。我一般是避免new和delete，所以选择后者。
代码：

1. /**
   
2. * Definition of ListNode
   
3. * class ListNode {
   
4. * public:
   
5. *     int val;
   
6. *     ListNode *next;
   
7. *     ListNode(int val) {
   
8. *         this->val = val;
   
9. *         this->next = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param ListNode l1 is the head of the linked list
    
17.      * @param ListNode l2 is the head of the linked list
    
18.      * @return: ListNode head of linked list
    
19.      */
    
20.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    
21.         if (l1 == NULL) {
    
22.             return l2;
    
23.         }
    
24.         if (l2 == NULL) {
    
25.             return l1;
    
26.         }
    
27.         
    
28.         ListNode *h = NULL;
    
29.         ListNode *p;
    
30.         
    
31.         if (l1->val < l2->val) {
    
32.             h = p = l1;
    
33.             l1 = l1->next;
    
34.         } else {
    
35.             h = p = l2;
    
36.             l2 = l2->next;
    
37.         }
    
38.         p->next = NULL;
    
39.         while (l1 != NULL && l2 != NULL) {
    
40.             if (l1->val < l2->val) {
    
41.                 p->next = l1;
    
42.                 l1 = l1->next;
    
43.             } else {
    
44.                 p->next = l2;
    
45.                 l2 = l2->next;
    
46.             }
    
47.             p = p->next;
    
48.             p->next = NULL;
    
49.         }
    
50.         if (l1 != NULL) {
    
51.             p->next = l1;
    
52.         }
    
53.         if (l2 != NULL) {
    
54.             p->next = l2;
    
55.         }
    
56.         return h;
    
57.     }
    
58. };

复制代码

复杂度：时间O(N + M)，空间O(1)。

Nth to Last Node in List
题意：给定一个单链表，找到倒数第N个节点。
解法：既可以先算长度，再遍历，也也可双指针。
代码：

1. /**
   
2. * Definition of ListNode
   
3. * class ListNode {
   
4. * public:
   
5. *     int val;
   
6. *     ListNode *next;
   
7. *     ListNode(int val) {
   
8. *         this->val = val;
   
9. *         this->next = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param head: The first node of linked list.
    
17.      * @param n: An integer.
    
18.      * @return: Nth to last node of a singly linked list.
    
19.      */
    
20.     ListNode *nthToLast(ListNode *head, int n) {
    
21.         ListNode *p1, *p2;
    
22.         
    
23.         p1 = head;
    
24.         int i;
    
25.         for (i = 0; i < n; ++i) {
    
26.             p1 = p1->next;
    
27.         }
    
28.         p2 = head;
    
29.         while (p1 != NULL) {
    
30.             p1 = p1->next;
    
31.             p2 = p2->next;
    
32.         }
    
33.         return p2;
    
34.     }
    
35. };

复制代码

复杂度：时间O(N)，空间O(1)。

Add Two Numbers
题意：给定两个以单链表形式表示的十进制数，求和。
解法：算法没有难度，但写代码要小心，考虑各种可能情况。
代码：

1. /**
   
2. * Definition for singly-linked list.
   
3. * struct ListNode {
   
4. *     int val;
   
5. *     ListNode *next;
   
6. *     ListNode(int x) : val(x), next(NULL) {}
   
7. * };
   
8. */
   
9. class Solution {
   
10. public:
    
11.     /**
    
12.      * @param l1: the first list
    
13.      * @param l2: the second list
    
14.      * @return: the sum list of l1 and l2
    
15.      */
    
16.     ListNode *addLists(ListNode *l1, ListNode *l2) {
    
17.                 if (l1 == NULL) {
    
18.                         return l2;
    
19.                 }
    
20.                 if (l2 == NULL) {
    
21.                         return l1;
    
22.                 }
    
23.                
    
24.                 ListNode *h;
    
25.                 ListNode *t;
    
26.                 int c;
    
27.                
    
28.                 h = t = new ListNode(l1->val + l2->val);
    
29.                 c = t->val / 10;
    
30.                 t->val %= 10;
    
31.                 l1 = l1->next;
    
32.                 l2 = l2->next;
    
33.                
    
34.                 while (l1 != NULL && l2 != NULL) {
    
35.                         t->next = new ListNode(l1->val + l2->val + c);
    
36.                         t = t->next;
    
37.                         c = t->val / 10;
    
38.                         t->val %= 10;
    
39.                         l1 = l1->next;
    
40.                         l2 = l2->next;
    
41.                 }
    
42.                 while (l1 != NULL) {
    
43.                         t->next = new ListNode(l1->val + c);
    
44.                         t = t->next;
    
45.                         c = t->val / 10;
    
46.                         t->val %= 10;
    
47.                         l1 = l1->next;
    
48.                 }
    
49.                 while (l2 != NULL) {
    
50.                         t->next = new ListNode(l2->val + c);
    
51.                         t = t->next;
    
52.                         c = t->val / 10;
    
53.                         t->val %= 10;
    
54.                         l2 = l2->next;
    
55.                 }
    
56.                 if (c) {
    
57.                         t->next = new ListNode(1);
    
58.                 }
    
59.                 return h;
    
60.     }
    
61. };

复制代码

复杂度：时间O(N + M)，空间O(1)。

Rotate List
题意：给定一个单链表，把它循环移位K位。
解法：注意K取不同值时的处理方式。对于需要移位的情况，只要找出应该截断的位置，然后从头部移到尾部就行了。
代码：

1. /**
   
2. * Definition for singly-linked list.
   
3. * struct ListNode {
   
4. *     int val;
   
5. *     ListNode *next;
   
6. *     ListNode(int x) : val(x), next(NULL) {}
   
7. * };
   
8. */
   
9. class Solution {
   
10. public:
    
11.     /**
    
12.      * @param head: the list
    
13.      * @param k: rotate to the right k places
    
14.      * @return: the list after rotation
    
15.      */
    
16.     ListNode *rotateRight(ListNode *head, int k) {
    
17.         if (head == NULL) {
    
18.             return head;
    
19.         }
    
20.         
    
21.         int len = 1;
    
22.         ListNode *p = head;
    
23.         while (p->next != NULL) {
    
24.             p = p->next;
    
25.             ++len;
    
26.         }
    
27.         ListNode *t = p;
    
28.         
    
29.         k = (len - k % len) % len;
    
30.         if (k == 0) {
    
31.             return head;
    
32.         }
    
33.         
    
34.         p = head;
    
35.         int i;
    
36.         for (i = 0; i < k - 1; ++i) {
    
37.             p = p->next;
    
38.         }
    
39.         ListNode *h = p->next;
    
40.         p->next = NULL;
    
41.         t->next = head;
    
42.         return h;
    
43.     }
    
44. };

复制代码

复杂度：时间O(N)，空间O(1)。