做网站的时候说需求的专业术语,海口免费网站建设,免费代加工项目合作,学校网站怎么做的好处位运算本质上不是一种算法#xff0c;而是一种trick#xff0c;用来节约时间/空间的trick。背后常常有集合论、状态压缩等思想的支撑。这里探讨的位运算指的是其背后的指导思想而不是trick本身。因此对trick本身的证明就略过了。
位运算各种trick的详解请参照灵神的教学贴而是一种trick用来节约时间/空间的trick。背后常常有集合论、状态压缩等思想的支撑。这里探讨的位运算指的是其背后的指导思想而不是trick本身。因此对trick本身的证明就略过了。
位运算各种trick的详解请参照灵神的教学贴leetcode.cn/circle/discuss/CaOJ45/
如果想获取位运算的知识图谱以及集合论的一些基础知识。我在子集状压DP篇收录了相关图片搬运别人的可以在该博客找到。
一、集合论
常见的有枚举已知集合的子集、判断子集元素、集合交并补对称差等。
1.1. LC 78 子集
这里涉及最简单的枚举已知集合的子集。我们可以为集合中的每个元素编号假设集合的势为n则编号为0~(n-1)那么子集就可以写作一个0-1串选取则为1不选则为0。采用小端法。
例如共计4个元素选取第0个和第2个就是0101。我们把这个0-1串看成二进制则它在十进制下就是5。而这种映射显然是一一对应的双射。因此5就代表了子集{02}用一个4字节整型就压缩了一个子集。
现在既然要枚举子集那么就要确定子集的范围很明显是全零到全一也就是[ 0 , 2^n-1 ]。对于每个数我们判断子集元素即可。
那么如何判断子集元素每次位于1若为1则说明末位为1应选取然后整个数右移更新末位循环直至整个0-1串被遍历即可。或者可以把1移位这个看个人喜好
另外这一题是一道比较经典的题他还能训练深搜回溯的基础算法。这里强调位运算集合论就不放了。
复杂度O(n*2^n):共O(2^n)个子集每个移位判断O(n)次。
import java.util.ArrayList;
import java.util.List;class Solution {public ListListInteger subsets(int[] nums) {// 位运算写法枚举子集int n nums.length;ListListInteger ans new ArrayList();// [ 0 , 1 n - 1 ] 不选对应0int j 1 n;for (int i 0; i j; i) {ArrayListInteger sub new ArrayList();int tmp i;int index 0;while(tmp0){if((tmp1)1){sub.add(nums[index]);}index;tmp 1;}ans.add(sub);}return ans;}
}
