Leetcode题解（六）

21、Merge Two Sorted Lists

题目

直接上代码：

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *helper=new ListNode(0);
        ListNode *head=helper;
        while(l1 && l2)
        {
             if(l1->val<l2->val) helper->next=l1,l1=l1->next;
             else helper->next=l2,l2=l2->next;
             helper=helper->next;
        }
        if(l1) helper->next=l1;
        if(l2) helper->next=l2;
        return head->next;
    }
};

-------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------------

22、Generate Parentheses

题目

题目分析：

在构造这个括号字符串时，分别用left和right表示剩下的左括号和右括号个数，str表示已经构造出的字符串。通过分析，可以找出如下关系：

a.当left==right时，只能进行str+‘(’操作；

b.当left<right并且left != 0,可以进行str+')'或者str+‘(’操作，相应的符号个数将减少1；

c.当left>right，这种情况肯定不存在；

实现代码如下:

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         vector<string> res;
 5         string str="";
 6         generateParenthesis(res,n,n,str);
 7 
 8         return res;
 9 
10     }
11     void generateParenthesis(vector<string> &res,int left,int right,string str)
12     {
13         if(0 == left)
14         {
15             for(int i=0;i<right;i++)
16                 str += ')';
17 
18             res.push_back(str);
19             return;
20         }
21         else
22         {
23             if(left == right)
24                 generateParenthesis(res,left-1,right,str+'(');
25             else
26             {
27                 generateParenthesis(res,left-1,right,str+'(');
28                 generateParenthesis(res,left,right-1,str+')');
29             }
30         }
31     }
32 };

上面的实现过程是递归实现，既然能用递归，那就能通过使用stack的方式直接求解而不用递归。

非递归的方法：每次stack压栈压入一个三元组（left，righ，str）。

 1 struct node
 2 {
 3     node(int l,int r,string s)
 4     {
 5         left = l;
 6         right = r;
 7         str = s;
 8     }
 9     int left;
10     int right;
11     string str;
12 };
13  
14 class Solution {
15 public:
16     vector<string> generateParenthesis(int n) {
17         vector<string> res;
18         string str="";
19         stack< node* > mystack;
20         int l = n-1;
21         int r = n;
22 
23         node *temp = new node(l,r,"(");
24         mystack.push(temp);
25         while(!mystack.empty())
26         {
27             temp = mystack.top();
28             mystack.pop();
29             if(temp->left == 0)
30             {
31                 for(int i=0;i<temp->right;i++)
32                     temp->str += ')';
33                 res.push_back(temp->str);
34                 continue;
35             }
36             if(temp->left == temp->right)
37             {
38                 mystack.push(new node(temp->left -1,temp->right,temp->str+'('));
39             }
40             else
41             {
42                 mystack.push(new node(temp->left -1,temp->right,temp->str+'('));
43                 mystack.push(new node(temp->left,temp->right - 1,temp->str+')'));
44             }
45         }
46         return res;
47 
48     }
49 };

----------------------------------------------------------------------------------------------分割线------------------------------------------------------------------------------

23、Merge k Sorted Lists

题目

这道题目可以仿照21题，一次对每一个链表就行merge，也就是L0和L1进行merge，得到的结果再和L2进行Merge。代码如下：

 1 class Solution {
 2 public:
 3     ListNode* mergeKLists(vector<ListNode*>& lists) {
 4         int count = lists.size();
 5         int i=1;
 6         if(lists.empty())
 7             return NULL;
 8         ListNode* first,*second,*temp;
 9         first = lists[0];
10         for (;i<count;i++)
11         {
12             temp = mergeTwoLists(first,lists[i]);
13             first = temp;
14         }
15         return first;
16     }
17     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
18         ListNode *helper=new ListNode(0);
19         ListNode *head=helper;
20         while(l1 && l2)
21         {
22             if(l1->val<l2->val) helper->next=l1,l1=l1->next;
23             else helper->next=l2,l2=l2->next;
24             helper=helper->next;
25         }
26         if(l1) helper->next=l1;
27         if(l2) helper->next=l2;
28         return head->next;
29     }
30 };

但是，这样提交的话，会超时。不能通过。

对算法进行改进，首先L0和L1进行Merge，L2和L3进行Merge。。。如此循环，把得到的结果再Merge，直到最后得出结果。

代码如下:

 1 class Solution {
 2 public:
 3     ListNode* mergeKLists(vector<ListNode*>& lists) {
 4         int count = lists.size();
 5         int i=0;
 6         if(lists.empty())
 7             return NULL;
 8         queue<ListNode*> myque;
 9         ListNode* first,*second,*temp;
10         first = lists[0];
11         for (;i+2<=count;i+=2)
12         {
13             temp = mergeTwoLists(lists[i],lists[i+1]);
14             myque.push(temp);
15         }
16         if(i<count)
17             myque.push(lists[i]);
18         while (!myque.empty())
19         {
20             first = myque.front();
21             myque.pop();
22             if(myque.empty())
23                 return first;
24             second = myque.front();
25             myque.pop();
26             temp = mergeTwoLists(first,second);
27             myque.push(temp);
28 
29         }
30         return first;
31     }
32     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
33         ListNode *helper=new ListNode(0);
34         ListNode *head=helper;
35         while(l1 && l2)
36         {
37             if(l1->val<l2->val) helper->next=l1,l1=l1->next;
38             else helper->next=l2,l2=l2->next;
39             helper=helper->next;
40         }
41         if(l1) helper->next=l1;
42         if(l2) helper->next=l2;
43         return head->next;
44     }
45 };