一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 657|回复: 7
收起左侧

[Leetcode] Leetcode刷题总结,bit manipulation,附带python和C++答案

[复制链接] |试试Instant~ |leetcode
我的人缘0

分享帖子到朋友圈
woziji | 显示全部楼层 |阅读模式
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 woziji 于 2019-12-9 22:52 编辑

Bit manipulation的一些操作总结,

&  按位与运算符:参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
|  按位或运算符:只要对应的二个二进位有一个为1时,结果位就为1
^  按位异或运算符:当两对应的二进位相异时,结果为1
~  按位取反运算符:对数据的每个二进制位取反,即把1变为0,把0变为1。~x 类似于 -x-1
<< 左移动运算符:运算数的各二进位全部左移若干位,由"<<"右边的数指定移动的位数,高位丢弃,低位补0
>> 右移动运算符:把">>"左边的运算数的各二进位全部右移若干位,">>"右边的数指定移动的位数

>>= 向右移位,然后赋值给左边变量。例如 a >>= 2, a向右移动两位,然后把结果赋值给a。
<<= 向左移位,然后赋值给左边变量。例如 a <<= 2, a向左移动两位,然后把结果赋值给a。
&=  按位与,然后赋值给左边变量。例如 a &= 2, a和2按位与,然后把结果赋值给a。
|=  按位或,然后赋值给左边变量。例如 a |= 2, a和数字2按位或,然后把结果赋值给a。
^=  按位异或,然后赋值给左边变量。例如 a ^= 2, a和数字2按位异或,然后把结果赋值给a。

然后,来看5道Leetcode的题目,我们用bit manipulation来解。我会把题目,分析和解答(C++ solution and Python solution)放在下面的评论里。

希望大家给多加点大米!!!非常感谢!!!










评分

参与人数 6大米 +19 收起 理由
mrbeen + 2 很有用的信息!
兴趣使然 + 2 给你点个赞!
yeehaah + 3 赞一个!
sddlpeter + 1 赞一个
rexue70 + 10 给你点个赞!
klkathy + 1 赞一个

查看全部评分


上一篇:Leetcode前300高频题重新分类
下一篇:如何准备巨硬的BQ问题啊
我的人缘0
 楼主| woziji 2019-12-10 12:28:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
本帖最后由 woziji 于 2019-12-9 22:44 编辑

一,
Leetcode, 第78题,https://leetcode.com/problems/subsets/

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

把nums的每一个位置看作一个二进制位。每一个这样的二进制位可以是0(表示所在位置的数字不被包含在一个子集里),
也可以是1(表示所在位置的数字出现在一个子集里)。假设nums共有n个数字,那么一共有2的n次方个子集(因为每一个
位置的数字可以被包含在某个子集中,也可以不被包含在这个子集中),那就是从0到2的n次方-1.具体到某一个,只要检查
这个整数的前len(num)二进制位,是1的话,把所在位的数字记录在当前的子集里,是0的话,不做任何操作。

Python solution,

class Solution:
    def subsets(self, nums):
        res = []

        for i in range(pow(2,len(nums))):
            temp = []

            for j in range(len(nums)):
                if ((i>>j) & 1) == 1:
                    temp.append(nums[j])

            res.append(temp)

        return res


C++ solution,

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

回复

使用道具 举报

我的人缘0
 楼主| woziji 2019-12-10 12:29:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
本帖最后由 woziji 于 2019-12-9 22:45 编辑

二,Leetcode, 第201题,https://leetcode.com/problems/bitwise-and-of-numbers-range/

题目:
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

从m到n的所有数字中,只要有一个数字在某一位有一个0,那么最终结果的对应位也是0。
因为从m到n,每次+1,在最低那些位,都经历了0和1的反复变化,对应最终结果都是零。
只有m和n的相同的高位,才最终保留在结果里。我们每次向右移动m和n,直到结果m == n。
用counter记录了移动的次数,然后把当前的m或者n再向左移动counter位就是最终结果。

Python solution,

class Solution:
    def rangeBitwiseAnd(self, m, n):
        counter = 0

        while m != n:
            m >>= 1
            n >>= 1

            counter += 1

        return m << counter


C++ solution,

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int counter = 0;

        while (m != n) {
            m >>= 1;
            n >>= 1;

            ++counter;
        }

        return m << counter;
    }
};
回复

使用道具 举报

我的人缘0
 楼主| woziji 2019-12-10 12:30:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
本帖最后由 woziji 于 2019-12-9 23:28 编辑

三,Leetcode, 第268题,https://leetcode.com/problems/missing-number/
题目:
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

这个题目我们可以用异或操作来解决,
(1)一个数字跟自己异或等于0,例如 a^a = 0, a是任意整数
(2)一个数字跟0异或等于这个数字自己, 例如 a^0 = a, a是任意整数

nums包含从0到n的,只缺了一个数字,的所有整数。我们用例子来说明,n = 7, 缺的数字是3,
index: 0, 1, 2, 3, 4, 5, 6
nums:  0, 1, 2, 4, 5, 6, 7

所以,
index: temp1 = 0^1^2^3^4^5^6
nums:  temp2 = 0^1^2  ^4^5^6

然后我们可以得知,
temp1^3 = temp2,

然后,
temp^temp1^3 = temp1^temp2

最后得到,
3 = temp1^temp2

等价于,
7^(0^0)^(1^1)^(2^2)^(3^4)^(4^5)^(5^6)^(6^7) = 3

Python solution,

class Solution:
    def missingNumber(self, nums):
        res = len(nums)

        for i in range(len(nums)):
            res ^= i ^ nums

        return res


C++ solution,

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();

        for (int i = 0; i < nums.size(); ++i)
            res ^= i ^ nums;

        return res;
    }
};
回复

使用道具 举报

我的人缘0
 楼主| woziji 2019-12-10 12:30:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
本帖最后由 woziji 于 2019-12-9 22:47 编辑

四,Leetcode, 第397题,https://leetcode.com/problems/integer-replacement/

题目:
Given a positive integer n and you can do operations as follow:
If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1?

题目中的两个操作,
1,n是偶数,把n替换成n/2:从二进制来看就是把n向右移了1位。
2,n是奇数,把n换成n+1或者n-1。从二进制来看就是把最后一位变成0的两个情况。
+1是把最后一位的1进到倒数第二位去,-1是直接去掉最后一个1。

所以我们要开始向右按位移动所给的数字了,直到这个数字变为1为止。
如果最后一位是0,对应操作1,直接把数字向右移动一位。
如果最后一位是1,我们可以+1也可以-1。分情况讨论,
(1)如果这个数字+1可以被4整除,并且这个数字不是3(3的二进制是11),那么我们将
这个数字+1,然后最后的几位都会变成0,可以向右连续移动多次。例如当前数字是15,二进制表示是1111,加1之后是10000,
然后连续向右移动四次。每次都-1,然后右移动,显然需要更多的步数。
但是如果当前数字是3的话,我们只需要将最后一个1去掉,然后向右一次就最终得到结果1。
(2)其他情况都是-1,就是去掉最后一个1。比如当前数字的二进制是1000001,那自然是直接-1,然后右移最节省步数。

Python solution,

class Solution:
    def integerReplacement(self, n):
        steps, m = 0, n

        while m - 1:
            if (m & 1) == 0:
                m >>= 1
            elif (m + 1)%4 == 0 and m != 3:
                m += 1
            else:
                m -= 1

            steps += 1

        return steps


C++ solution,

class Solution {
public:
    int integerReplacement(int n) {
        int steps = 0;
        long long m = n;
        
        while (m - 1) {
            if ((m & 1) == 0)
                m >>= 1;
            else if ((m + 1)%4 == 0 && m != 3)
                m += 1;
            else
                m -= 1;
            
            ++steps;
        }
   
        return steps;
    }
};
回复

使用道具 举报

我的人缘0
 楼主| woziji 2019-12-10 12:31:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
本帖最后由 woziji 于 2019-12-9 22:47 编辑

五,Leetcode, 第405题,https://leetcode.com/problems/convert-a-number-to-hexadecimal/

题目:
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

16 = pow(2,4)。一个16进制的数字可以用4个二进制的数字表示,所以我们以4个二进制位为一组来处理。
一个integer有32位(考虑C++里的情况,Python的整数比32多),操作8次。
每次操作的时候把要处理的那4位移位到最低的4位的位置。
然后跟数字15按位&,15的二进制是1111,按位&的结果就是table中的对应的16进制数字的index。
最后还要注意开头的”0“要去掉。
这个题目用bit manipulation非常的方便。

Python solution,

class Solution:
    def toHex(self, num):
        if not num:
            return "0"

        table = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"]

        s = ""
        for i in range(8):
            s = table[15 & num] + s
            num = (num >> 4)

        cur = 0
        while True:
            if s[cur] != '0':
                break
            else:
                cur += 1

        return s[cur:]


C++ solution,

class Solution {
public:
    vector<string> table = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};

    string toHex(int num) {
        if (num == 0) return "0";

        string str = "";
        for (int i = 0; i < 8; ++i) {
            str = table[15 & num] + str;
            num = (num >> 4);
        }

        int cur = 0;
        while (true) {
            if (str[cur] != '0')
                break;
            else
                ++cur;
        }

        return str.substr(cur);
    }
};
回复

使用道具 举报

我的人缘0
Huadx 2019-12-10 20:53:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
bit manipulation 出现频率高么 一直觉得记着有点烦 都是要用的时候现查的。。。
回复

使用道具 举报

我的人缘0
 楼主| woziji 2019-12-11 00:49:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (40)
 
 
2% (1)    👎
Huadx 发表于 2019-12-10 06:53
bit manipulation 出现频率高么 一直觉得记着有点烦 都是要用的时候现查的。。。

你面试的时候怎么现查?总共没几个操作,很难记吗?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-19 02:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表