细语呢喃

技术改变生活

0%

leetcode 位运算

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括

  • 89. Gray Code
  • 136 Single Number
  • 137 Single Number II
  • 190 Reverse Bits
  • 191 Number of 1 Bits
  • 201 Bitwise AND of Numbers Range
  • 260 Single Number III
  • 268 Missing Number

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 01 - 1 11 - 3 10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

题目地址：leetcode Gray Code

题目大意：给定数字n，要你输出[0, 2^n - 1]格雷码。

思路：二进制x转化为格雷码的操作是  x ^ (x>> 1)

C++ 

1
2
3
4
5
6
7
8
9
class Solution {
public:
	vector<int> grayCode(int n) {
		vector<int> ans;
        for(int i = 0; i < (1 << n); ++i)
            ans.push_back(i ^ (i >> 1));
        return ans;
	}
};

Python 

1
2
3
4
5
6
7
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        return [i ^ (i >> 1) for i in range(1 << n)]

 

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目地址：leetcode Single Number

题意：一个数组，除了一个元素出现一次外，其余每个元素都是出现两次，求出只出现过一次的元素

思路：用异或的性质，两次异或等于本身。so~

C++ 

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int num: nums)
            ans ^= num;
        return ans;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        for num in nums:
            ans ^= num
        return ans

 

137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目地址：leetcode Single Number II

题意：一个数组，除了一个元素出现一次外，其余每个元素都是出现三次，求出只出现过一次的元素

思路：

方法1

输入为Int有32位，对数组中每个数的各个位上进行相加，然后Mod3就是该位上只出现一次应该取的值。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (int num : nums) {
                cnt += (num >> i) & 1;
            }
            ans |= (cnt % 3) << i;
        }
        return ans;
    }
};

Python

python需要注意的是如果有负数出现，那么py最后进行移位不会认为它是负数，而是认为它是一个正数！

故需手动判断最高位是否为1，如果为1代表负数，求其补码（取反，末位+1）

1
2
3
4
5
6
7
8
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum([(num >> i) & 1 for num in nums])
            ans |= (cnt % 3) << i
            
        return ans if ans & 0x80000000 == 0 else -((ans ^ 0xffffffff) + 1)

 

方法2

上面的方法遍历了nums数组32次，虽然时间复杂度仍为\(O(n)\)，但是可以继续改进：可以只遍历一遍就分析出结果！

解法1中其实就是计数然后mod 3，因此每个位可能有余数为0\1\2三种情况，而一个二进制只能表示2种情况，因此我们需要2位数来表示，即00 01 10三种情况，用two来表示2位数的高位，one来表示2位数的低位，可以根据输入num来写出如下的转移表

num two one 转以后： two one
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 0 0

因此可以看出，one = one ^ num & ~two，即one计算其实就是简单的按位加（异或），但是当two == 1的时候，设置为0

类似的有two = two ^ num & ~one

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one = two = 0
        for num in nums:
            one = one ^ num & ~two
            two = two ^ num & ~one
        return one

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up: If this function is called many times, how would you optimize it?

传送门

题意：给定一个32位无符号整形，求把它的二进制颠倒顺序的结果。

思路：将ans左移并且加上n的最高位，然后将n右移，直到n为0。最后，需要左移上n前导0的个数。

1
2
3
4
5
6
7
8
9
10
class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        ans = cnt = 0
        while n:
            ans = (ans<<1) + (n&1)
            n >>=1
            cnt+=1
        return ans<<(32-cnt)

 

191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

传送门

题意：给定一个32位整型，求它1 的个数

思路：

方法一

每次 &1 右移即可。

Python:

1
2
3
4
5
class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        return 0 if n==0 else (n&1) + self.hammingWeight(n>>1)

其实上面一行代码只是下面这个的好看版。哈哈

1
2
3
4
5
6
7
8
9
class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        cnt = 0
        while n:
            if n&1: cnt+=1
            n>>=1
        return cnt

C++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n){
            if(n&1) res++;
            n >>=1;
        }
        return res;
    }
};

 

方法二：

先考虑一下我们从一个数减去1的时候发生了什么。

如： 0111 0000 - 1 = 0110 1111

就是从最低位到最低的1那一位全部取反。

接下来，我们看看n & (n-1)

0111 0000 & 0110 1111 =  0110 0000

我们看到，最后一个1变成了0，所以我们只需要O(m)次 ，m为1的个数就可以求出1的个数

C++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n){
            n = n & ( n - 1 );
            res++;
        }
        return res;
    }
};

 

Python 

1
2
3
4
5
6
7
class Solution(object):
    def hammingWeight(self, n):
        numOnes = 0
        while n:
            n = n & (n-1)
            numOnes += 1
        return numOnes

 

201. 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.

For example, given the range [5, 7], you should return 4.

传送门

题意：给定m和n，求从m连续 按位与到 n 的结果

思路：

一开始想，如果m的长度小于n，那结果必为0。只有一样长度的才需要进行与，所以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # @param m, an integer
    # @param n, an integer
    # @return an integer
    def rangeBitwiseAnd(self, m, n):
        def num_len(m):
            res = 0
            while m: m , res = m>>1 ,res+1
            return res
        m_len , n_len= num_len(m),num_len(n)
        if m_len < n_len: return 0
        ans = m
        for i in xrange(m+1,n+1):
            ans = ans & i
        return ans

虽然1A，但是实际上我们只需要求两个数字的二进制的最长公共前缀即可！

1
2
3
4
5
6
7
8
class Solution:
    # @param m, an integer
    # @param n, an integer
    # @return an integer
    def rangeBitwiseAnd(self, m, n):
        cnt = 0
        while m!=n: m,n,cnt=m>>1,n>>1,cnt+1
        return n<<cnt

 

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

题目地址：leetcode Single Number III

题意：给定一个数组，里面只有两个元素a,b出现一次，其他的元素均出现两次，求a,b

思路：

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

  • In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value '1') in the XOR result. Find out an arbitrary set bit (for example, the rightmost set bit).
  • In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.From https://discuss.leetcode.com/topic/21605/accepted-c-java-o-n-time-o-1-space-easy-solution-with-detail-explanations

就是首先先异或一次，这样就得到了a^b的值diff，接着由于a!=b，所以diff!=0，我们找diff最低位的元素作为分类的依据。（diff = diff&-diff 类似树状数组）因为，a和b这个位置的二进制不同，借此把a和b划分开。

接着，遍历数组，对于数组中的元素num, 若num & diff == 0 我们归为第一组，a ^= num 否则就是b^=num啦

C++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
	vector<int> singleNumber(vector<int>& nums) {
		int diff = accumulate(nums.begin(), nums.end(),0, bit_xor<int>());
		diff &= -diff; //lower  bit
		vector<int> ans(2, 0);
		for (int num:nums) 
			ans[(num & diff) == 0] ^= num;
		return ans;
	}
};

Python3 

1
2
3
4
5
6
7
8
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        x = functools.reduce(lambda a, b: a ^ b, nums, 0)
        x = x & -x
        ans = [0, 0]
        for num in nums:
            ans[num & x == 0] ^= num
        return ans

 

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

题目地址：leetcode Missing Number

题意：给定一个n个元素组成的数组，求0~n中缺失了哪一个？

思路：

看到这个，立马就觉得直接sum求和，也过了（其实数据量大会overflow）

1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        for(int num:nums) sum += num;
        return (((1+nums.size()) * nums.size() ) >>1)  - sum;
    }
};

Python 

1
2
3
4
5
6
7
class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return (((1 + len(nums)) * len(nums)) >> 1 )- sum(nums)

 

更好的方法是异或，利用两次异或 = 没有异或的性质 （如 x ^ 1 ^ 1 = x）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x = 0;
        for(int i=0;i<nums.size();i++) {
            x ^= i;
            x ^= nums[i];
        }
        return x ^ nums.size();
    }
};
请我喝杯咖啡吧~