leetcode 随笔 Combinations Subsets -- 利用位运算

本文主要是介绍leetcode 随笔 Combinations Subsets -- 利用位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这两天去了北京故宫博物院和八达岭长城，真是人挤人，公交车上撸了一道Combinations，手机登陆leetcode写代码总是存在奇怪的中文编码的问题，可以选择使用app黑客键盘，编码相对舒服一丢丢，如果还是存在编码问题就一行一行的删空格吧。

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

相当于是把C(n,k)的所有情况给列出来。

第一个想到的办法还是利用递归，每次插入一个数，然后传递给下一次递归状态，整体还是比较简单的。

	class Solution {public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> tmp;go(res, tmp, 0, 1, k, n); return res;}void go(vector<vector<int>>&res, vector<int> &now, int nindex, int num, int k, int n){if (num == k) {for (int i = nindex; i<n; i++){now.push_back(i + 1);res.push_back(now); now.pop_back();}}else {for (int i = nindex; i<n - k + num; i++){now.push_back(i + 1);go(res, now, i + 1, num + 1, k, n);now.pop_back();}}}};

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

求一个集合的子集，集合中的数字保证是不重复的。

想到的办法还是递归，跟上一题思路类似的递归

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {//sort(nums.begin(), nums.end());vector<int> tmp;vector<vector<int>> res;res.push_back(tmp);for(int i=1;i<=nums.size();i++)go(res, nums, tmp, 0, i, 0, nums.size());return res;}void go(vector<vector<int>> &res, vector<int> nums, vector<int> &local, int now_index, int K_num, int size, int n){if (K_num == n + 1) return;if (K_num == 1){for (int i = now_index; i<n; i++){local.push_back(nums[i]);res.push_back(local);local.pop_back();}return;}else{for (int i = now_index; i <= n - K_num; i++){local.push_back(nums[i]);go(res, nums, local, i + 1, K_num - 1, size + 1, n);local.pop_back();}}}
};

然后看完discuss发现了一个利用位运算计算该问题的办法，看完代码可以说是......豁然开朗

让我们来看看这个巧妙的思路：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {       int cnt = 0;int n = nums.size();int sub = pow(2, n);vector<vector<int>> result(sub, vector<int>());for(int i = 0; i < n; i ++){for(int j = 0; j < sub; j++){if(j>>i & 1){result[j].push_back(nums[i]);}}}return result;}   
};

思路可以说是相当简单了，

假设我们的集合nums为{1，2，3，5，8，13，21}

我们可以利用位图来表示该集合，这个位图即为7位的二进制数 111 1111

比如这个nums集合的子集为{1，2，3}，所对应的位图即为 111 0000

如果为空集即为 000 0000

而所有子集的情况，即为 000 0000 - 111 1111的所有二进制数！

if(j>>i &1) 这句话的涵义是判断所有二进制数上的第i位是不是1

这篇关于leetcode 随笔 Combinations Subsets -- 利用位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---