Leetcode Day4 合并排序連結清單

1、合并排序連結清單

給定一個連結清單數組，每個連結清單都已經按升序排列。

請将所有連結清單合并到一個升序連結清單中，傳回合并後的連結清單。

思路：無腦周遊所有的元素，用vector存儲後sort排序，建立新連結清單傳回即可

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        ListNode*pre=NULL;
        ListNode*p=NULL;
        ListNode*head=NULL;
        int n=lists.size();
        vector<int>nums;
        for(int i=0;i<n;i++){
            while(lists[i]!=NULL){
                nums.emplace_back(lists[i]->val);
                lists[i]=lists[i]->next;
            }
        }
        sort(nums.begin(),nums.end());
        int m=nums.size();
        for(int i=0;i<m;i++){
            p=new ListNode(nums[i]);
            if(pre!=NULL){
                pre->next=p;
            }else{
                head=p;
            }
            pre=p;
        }
        return head;
    }
};
           

2、所有子集

給定一個整數數組 nums ，數組中的元素 互不相同 。傳回該數組所有可能的子集（幂集）。

解集 不能 包含重複的子集。你可以按 任意順序 傳回解集。

【傳送門】

思路：其實本質上依然是一個dfs的深搜的問題,套用基本模闆即可

class Solution {
public:
    vector<vector<int> >ans;
    vector<int>array;
    int n;
    void dfs(int i,vector<int>&temp){
        temp.emplace_back(array[i]);
        ans.emplace_back(temp);
        for(int j=i+1;j<n;j++){
            dfs(j,temp);
        }
        temp.pop_back();
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        //傳回所有子集2的n方
        vector<int>temp;
        ans.emplace_back(temp);
        n=nums.size();
        array=nums;
        
        for(int i=0;i<n;i++){
            dfs(i,temp);
        }
        return ans;
    }
};