网站建设包含图文设计,邢台市的做网站制作公司,深圳seo排名优化,文件备案网站建设方案原题链接#xff1a;子集 (Subsets) - 力扣 (LeetCode)
原码于文章末尾会给出。
本文通过位运算#xff0c;实现题目要求#xff0c;之后可能更新其他方法#xff0c;敬请关注...... 题目#xff1a; 给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该…原题链接子集 (Subsets) - 力扣 (LeetCode)
原码于文章末尾会给出。
本文通过位运算实现题目要求之后可能更新其他方法敬请关注...... 题目 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 输入{1369}
输出[] [1] [3] [1,3] [6] [1,6] [3,6] [1,3,6] [9] [1,9] [3,9] [1,3,9] [6,9] [1,6,9] [3,6,9] [1,3,6,9] 具体步骤如下 1. 首先我们需要了解什么是集合的子集。集合的子集是指原集合中的元素可以任意个数包括0个或全部挑选出来组成的集合。 2. 对于一个有n个元素的集合它的子集数量为2^n个。因此我们需要遍历从0到2^n-1的所有数字每个数字代表一个子集。 3. 利用位运算我们可以很容易地得到一个数字表示的子集。例如数字1的二进制表示为0001它表示集合中的第一个元素数字3的二进制表示为0011它表示集合中的第一个和第三个元素。 4. 在遍历所有数字后我们可以得到所有的子集。每个子集都是一个长度为n的数字序列表示集合中的元素是否包含在当前子集中。 5. 最后我们将所有子集输出即可。这里比较难的点在于如何通过位运算得到我们想要的结果。 下面先将我们代码实现功能的主要函数列出来
void GetSubSet(int* num, int len, int tag) {int tmp;for (int i 0; i pow(2, len); i) {tmp tag;tag 1;int is_first 1;printf([);for (int j 0; j len; j) {if (tmp 0x1) {if (is_first) {printf(%d, num[j]);is_first--;}else {printf(,%d, num[j]);}}tmp 1;}printf(] );}
}
函数GetSubSet接受三个参数
int* num指向整数数组的指针该数组包含了要生成子集的元素。int len整数数组的长度即数组中元素的个数。int tag用于跟踪当前生成子集的标记初始时它被设置为0。
初始化 函数开始时tag被设置为0表示空集。
循环遍历所有子集 使用一个for循环循环2^len次每次循环代表一个子集。 重点来了
位运算 在每次循环中使用tmp变量来暂存tag的值然后通过tag 1来计算下一个子集的tag。 这里实际上是在对tag进行二进制位操作每次循环将tag的最低位设置为1 然后通过tmp 1将tag右移一位。 关于位运算这里可能理解比较困难下面我将画图讲解。 刚开始的时候我们设置了输入集合的元素总个数n这个n会在GetSubSet函数的位运算操作中生成n个二进制位。比如我们设置的n4那么我们下面就产生4个二进制位。 在遍历第一层第一次for循环时临时变量tmp0即4位二进制都为0
0000 在遍历第一层第二次for循环时临时变量tmp1即4位二进制变为0001
0001 以此类推...... 此时符合条件tmp 0x1意思是用于检查变量 tmp 的最低位二进制的第0位是否为1。 is_first用于判断是否是第一次进入到这个for循环。 在遍历第一层第二次for循环时临时变量tmp1即4位二进制变为0001相对应的num[j]子集元素中的第一个元素——1。 每执行完一次for循环tmp 1也就是说tmp0001会向右移动一位变为000。
以上就是位运算的原理。 打印子集在循环内部使用另一个for循环来遍历数组num中的每个元素。如果当前tag的二进制表示中的第j位是1说明元素num[j]应该被包含在子集中。如果这是子集列表中的第一个元素则直接打印否则打印逗号和元素。递归调用虽然这段代码中没有递归调用但这个思想可以用来生成子集树每个子集都可以作为下一个子集的父集。 这个算法的关键在于理解如何使用二进制数来表示和生成子集。每个子集都可以通过改变tag的某一位来得到下一个子集。当tag的某一位被设置为1时表示对应数组元素被包含在子集中当该位被设置为0时表示对应元素不被包含。通过这种方式我们可以遍历所有可能的子集。
实现代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include math.h#define MAX_SIZE 100void GetSubSet(int* num, int len, int tag);int main() {int len;int num[MAX_SIZE];while (scanf(%d, len) len ! 0) {for (int i 0; i len; i) {scanf(%d, num i);}GetSubSet(num, len, 0);printf(\n);}return 0;
}void GetSubSet(int* num, int len, int tag) {int tmp;for (int i 0; i pow(2, len); i) {tmp tag;tag 1;int is_first 1;printf([);for (int j 0; j len; j) {if (tmp 0x1) {if (is_first) {printf(%d, num[j]);is_first--;}else {printf(,%d, num[j]);}}tmp 1;}printf(] );}
}
