【LeetCode】位运算 bit manipulation(共32题)
【78】Subsets
给了一个 distinct 的数组,返回它所有的子集。
Example:
Input: nums = [,,]
Output:
[
[],
[],
[],
[,,],
[,],
[,],
[,],
[]
]
题解:我是直接dfs(backtracking)了,有个小地方写错了(dfs那里),至少调整了十多分钟,下次不要写错了。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
vector<int> visit(n, );
vector<int> temp;
if (n == ) { return ans; }
dfs(nums, visit, temp, );
return ans;
}
void dfs(const vector<int>& nums, vector<int>& visit, vector<int>& temp, int cur_idx) {
ans.push_back(temp);
if (cur_idx == n) { return; }
for (int i = cur_idx; i < n; ++i) {
if (!visit[i]) {
visit[i] = ;
temp.push_back(nums[i]);
dfs(nums, visit, temp, i + ); //一开始写成了 dfs(nums, visit, temp, cur_idx + 1) 挂了半天
visit[i] = ;
temp.pop_back();
}
}
return;
}
vector<vector<int>> ans;
int n;
};
backtracking
我看分类是 位运算,学习一下位运算解法。https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation
题解的解释参考:https://www.mathsisfun.com/sets/power-set.html (有点像状态压缩的感觉)
//bit manipulation, 我认为是状态压缩的最简单的题.
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
const int n = nums.size();
if (n == ) { return vector<vector<int>>{}; }
// n 个元素一共有 2^n 个子集。
int tot = pow(, n);
vector<vector<int>> ans(tot, vector<int>{});
// 然后用二进制一个一个往里面塞
for (int i = ; i < n; ++i) {
for (int j = ; j < tot; ++j) {
if (j >> i & ) {
ans[j].push_back(nums[i]);
}
}
}
return ans;
} };
bit manipulation
【136】Single Number (2018年11月4日)(剑指offer上有个变种题,有两个数只出现了一次,求出出现一次的这两个数)
给了一个数组,说数组里面除了一个数只出现了一次,其他数都出现了两次。找出只出现一次的那个数。
题解:出现两次的数取异或之后为0,把全部数字异或起来,最后结果就是要求的那个数。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = ;
for (int i = ; i < nums.size(); ++i) {
ans ^= nums[i];
}
return ans;
}
};
【137】Single Number II
【169】Majority Element
【187】Repeated DNA Sequences
【190】Reverse Bits
【191】Number of 1 Bits (2018年11月4日,无聊做的)
给了一个数的 hamming weight,返回它的二进制中 1 的个数。
题解:方法同 231, n & (n-1) 这个表达式能消除 n 的二进制表达中最右边的一个 1.
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = ;
while (n) {
cnt++;
n = n & (n-);
}
return cnt;
}
};
【201】Bitwise AND of Numbers Range
【231】Power of Two (相关题目 342 Power of Four)(2018年11月4日,无聊做的)
给了一个数,判断它是不是2的幂。
题解:2的幂的二进制中只有一个1,所以我们用 num&(num-1) == 0 判断是不是2的幂次。
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > && (n & (n-)) == ;
}
};
另外,还有判断一个数是不是3的幂的(326),一个数是不是4的幂的(342)。
【260】Single Number III (2018年11月24日,算法群)
题解:本题剑指offer书上好像是有的。
【268】Missing Number
【318】Maximum Product of Word Lengths (2019年3月26日)
给了一组wordlist,返回里面两个单词的长度的乘积最大是多少。要求这两个单词里面不能有重复的字母。题目中给定所有单词都是小写字母。
题解:因为已经说明了每个单词的字母都是小写字母,所以我们可以用一个32位整数来编码当前单词是否出现过这个字母。重要代码如下:
x = words[i][j] - 'a'
code |= ( << x)
然后判断两个单词是否有相同字母,使用如下语句判断: code[i] & code[j] == 0
class Solution {
public:
int maxProduct(vector<string>& words) {
const int n = words.size();
vector<int> codes(n, );
for (int i = ; i < n; ++i) {
for (int j = ; j < words[i].size(); ++j) {
int x = words[i][j] - 'a';
codes[i] |= ( << x);
}
}
int res();
for (int i = ; i < n; ++i) {
for (int j = i + ; j < n; ++j) {
if (codes[i] & codes[j]) {continue;}
int length = (int)words[i].size() * words[j].size();
res = max(res, length);
}
}
return res;
}
};
【320】Generalized Abbreviation
【338】Counting Bits
【342】Power of Four (231题的升级版,判断是不是4的幂)(2018年11月4日,无聊做的)
给了一个数,判断这个数是不是4的幂。
题解:可能是负数,所以先把负数排除。一个数是4的幂的前提条件是它的2的幂,2的幂的二进制中只有一个1,所以用 num&(num-1) == 0 判断是不是 2 的幂。(这个方法也用在数一个数的二进制中有几个1用到了,【191】题,Number of 1 Bits)。然后增加判断它是不是 4 的幂,就是如果一个数是 2 的幂,那么增加一个条件, num % 3 == 1,满足这个条件,它就是 4 的幂。
//一个数是4的幂次,首先它要是2的幂次,2的幂次怎么求,2的幂次二进制中只有一个1.
class Solution {
public:
bool isPowerOfFour(int num) {
return num > && (num&(num-))== && num % == ;
}
};
discuss中还有 & 一堆5的,那个要研究一下。
【371】Sum of Two Integers (2018年11月26日)
返回 a + b 的答案,不能用 +。
题解:位运算。为啥我也还没搞懂。先写着。
https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary:-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
class Solution {
public:
int getSum(int a, int b) {
do {
int sum = a ^ b;
int carry = (a & b) << ;
a = sum, b = carry;
} while (b != );
return a;
}
};
【389】Find the Difference
【393】UTF-8 Validation
【397】Integer Replacement
【401】Binary Watch
【405】Convert a Number to Hexadecimal
【411】Minimum Unique Word Abbreviation
【421】Maximum XOR of Two Numbers in an Array
【461】Hamming Distance (2019年2月16日)
两个整数对应二进制位置不同的个数叫做hamming distance。给了两个正整数 x 和 y,计算他们的hamming distance。
题解:我这里想强调下左移右移。左移低位补0,相当于乘以2,右移,如果是正数的话,高位补0,如果是负数的话,低位补0.
class Solution {
public:
int hammingDistance(int x, int y) {
int res = ;
while (x || y) {
res += (x & ) ^ (y & );
x >>= ; y >>= ;
}
return res;
}
};
【476】Number Complement (2019年2月16日)
返回一个正整数的补码。
The complement strategy is to flip the bits of its binary representation.
题解:我们用一个unsigned mask,mask一开始是 ~0 = FFFFFFFF,然后我们把 mask 尾部跟 number 有重叠的部分全 set 成 0。然后 返回 ~num & ~mask
class Solution {
public:
int findComplement(int num) {
unsigned mask = ~;
while (num & mask) {mask <<= ;}
return ~num & ~mask;
}
};
【477】Total Hamming Distance
【693】Binary Number with Alternating Bits
【751】IP to CIDR
【756】Pyramid Transition Matrix
【762】Prime Number of Set Bits in Binary Representation
【784】Letter Case Permutation
【898】Bitwise ORs of Subarrays
最新文章
- 如何在EF中实现left join(左联接)查询
- ab post 测试 http 和 webservice 接口方法及用例
- html 图像映射
- eclipse查看hadoop中文件出现乱码
- [HTML]background-size可以缩放大小
- python 包管理
- 【甘道夫】HBase(0.96以上版本号)过滤器Filter具体解释及实例代码
- Sharepoint 2010 根据用户权限隐藏Ribbon菜单(利用css)
- php中global和$GLOBALS[]的分析之一
- 用正则表达式解析XML
- ubuntu12.04硬盘安装
- VS2010-使用“预先生成事件命令行”和“后期生成事件命令行”功能
- KVO 模式详解
- ST-LINK V2 DIY笔记(一)
- 【Python 07】汇率兑换1.0-2(基本元素)
- Ant之build.xml详解
- create-react-app-typescript 知识点
- docker 容器时间跟宿主机时间同步
- Katalon Studio学习笔记(二)——请求响应中文乱码解决方法
- KCP 传输协议
热门文章
- 如何删除eclipse的subclipse插件记住的SVN用户名和密码
- SIEM中心日志节点WEF搭建说明
- What is the difference between Kill and Kill -9 command in Unix?
- python异常处理(try-except)
- 大数据架构师必读的NoSQL建模技术
- Foxit_PDF_Editor(特别版)-PDF文档编辑器 V2.21 V3.1
- Backbone中bind和bindAll的作用
- java项目中,针对缓存问题的处理方式【接口中的处理方式】
- Error querying database. Cause: org.apache.ibatis.reflection.ReflectionException: There is no getter for property named &#39;ItemsCustom&#39; in &#39;class com.pojo.OrderDetailCustom
- 域名 端口 DNs 网络