程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Subsets

leetcode筆記:Subsets

編輯:關於C++

一. 題目描述

Given a set of distinct integers, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

二. 題目分析

該題的大意是,給定一個集合,求出這個集合所有的子集(所謂子集,就是包含原集合中的一部分元素的集合)。可使用DFS遞歸嵌套。總共N層,時間復雜度為O(2^N)。我的做法是使用位運算,一個含有N個元素的數組有2^N個子集,因此該題目可轉換為求數組的元素組合。使用一個N位二進制位表示數組nums的各下標出現與否,當某一位為1表示這次組合中出現當前下標所對應的元素,否則表示不選擇當前下標元素,時間復雜度也是O(2^N)

三. 示例代碼

// 方法一,位運算
class Solution {
public:
    vector> subsets(vector& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int MAX = 1 << n;
        vector> result;
        for (int i = 0; i < MAX; ++i)
        {
            vector temp;
            int index = 0;
            int j = i;
            while (j > 0)
            {
                if (j & 1) // 二進制數的最低位為1,表示該位出現在此次排列中
                    temp.push_back(nums[index]);
                j = j >> 1; // 一次次移位,判斷各位上是否為1
                ++index;    // nums的下標逐次加1
            }
            result.push_back(temp);
        }
        return result;
    }
};
// 方法二,DFS
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector > result;
    vector temp;
    vector> subsets(vector& nums) {
        if(nums.empty()) return result;
        sort(nums.begin(), nums.end());
        dfs(0, temp, nums);
        return result;

    }

private:
    void dfs(int k, vector temp, vector nums){
        result.push_back(temp);
        for(int i = k; i < nums.size(); ++i){
            temp.push_back(nums[i]);
            dfs(i + 1, temp, nums);
            temp.pop_back();
        }
    }
};

四. 小結

就提交結果來看,似乎還有更快的算法。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved