22. 括号生成

题意

解法1

23. 合并K个升序链表

题意

合并k个升序的链表
是“合并两个升序链表”的扩展版

解法1 暴力两两合并

转换题目，每次仅合并两个升序链表。

合并两个升序链表：

 ListNode* mergeTwoLists(ListNode* a,ListNode* b){
        if((!a)||(!b)) return a?a:b;
        ListNode head,*tail=&head,*aptr=a,*bptr=b;
        while(aptr&&bptr)
        {
            if(aptr->val<bptr->val)
            {
                tail->next=aptr;aptr=aptr->next;
            }
            else
            {
                tail->next=bptr;bptr=bptr->next;
            }
            tail=tail->next;
        }
        tail->next=(aptr?aptr:bptr);
        return head.next;
    }

合并k个升序链表：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
ListNode* mergeTwoLists(ListNode* a,ListNode* b)
{
    if((!a)||(!b)) return a?a:b;
    ListNode head;
    ListNode* aptr=a,*bptr=b,*tail=&head;
    while(aptr&&bptr)
    {
        if(aptr->val<bptr->val)
        {
            tail->next=aptr;aptr=aptr->next;
        }
        else
        {
            tail->next=bptr;bptr=bptr->next;
        }
        tail=tail->next;
    }
    tail->next=(aptr?aptr:bptr);
    return head.next;
}
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans=NULL;
        for(int i=0;i<lists.size();i++)
            ans=mergeTwoLists(ans,lists[i]);
        return ans;
    }
};

解法2 直接获取k个节点中的最小节点（堆）

“合并两个升序链表”每次选择两个链表中最小的节点，那么类比到“合并k个升序链表”，可以每次选择k个链表中最小的节点，这个选择可以靠优先级队列（二叉堆） 来实现。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Status{
        int val;
        ListNode* ptr;
        bool operator < (const Status &rhs) const{
            return val > rhs.val;
        }
    };
    priority_queue<Status> q;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(auto node:lists)
        {
            if(node) q.push({node->val,node});
        }
        ListNode head,*tail=&head;
        while(!q.empty())
        {
            auto f=q.top();q.pop();   //取根
            tail->next=f.ptr;
            tail=tail->next;
            if(f.ptr->next) q.push({f.ptr->next->val,f.ptr->next});
        }
        return head.next;
    }
};

复杂度
优先队列q中元素最多有k个，每次pop和push的复杂度为O(logk)，由于所有链表的每一个节点都会push和pop一遍，所以算法的总复杂度为O(nlogk)。

31. 下一个排列

题意

相当于找下一个尽可能小的更大的数
应当选择最靠右的最左边的较小数与最靠右的尽可能小的数交换，所以选择从右向左遍历寻找目标数。
最靠右的最左边的较小数：从右向左寻找第一个升序二元组 <i,j> ，tar_i=i。
最靠右的尽可能小的数：从右往左第一个大于nums[tar_i]的数，记为tar_j。

解法1 分析找规律

例如，452631，应当选择2与3交换。

也就是说，从右向左寻找第一个升序二元组 <i,j> ，记录tar_i=i，需要注意的是，此时，i的右边一定是一个降序排列。然后再寻找一个比nums[i]大却又尽可能小的数，由于i右边是一个降序排列，所以从右往左寻找第一个大于nums[tar_i]的数即可，记为tar_j。最后，将tar_i右边的数进行升序重排即可。

如果找不到这样一个升序二元组 <i,j> ，说明此时的序列是一个降序序列，那么下一个排列就是这些数的升序排列，直接重新sort即可。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //先不考虑重复数的存在
        int n=nums.size();
        int tar_i=-1,tar_j=-1;
        for(int i=n-2;i>=0;i--)
        {
            if(nums[i]<nums[i+1])
            {
                tar_i=i;
                break;
            }
        }
        if(tar_i==-1)
        {
            sort(nums.begin(),nums.end());
            return ;
        }
        for(int i=n-1;i>tar_i;i--)
        {
            if(nums[i]>nums[tar_i])
            {
                tar_j=i;
                break;
            }
        }
        swap(nums[tar_i],nums[tar_j]);
        sort(nums.begin()+tar_i+1,nums.end());
        return ;
    }
};