LeetCode算法题整理（位运算篇）Bit Manipulation

Posted on   |   Updated on | In | | Visitors

191. Number of 1 Bits

计算数字的二进制中有多少个1。原题

1
2
3
Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011

方法一：常规解法，使用1与n作与运算，如果不是0说明，含有一个1。

1
2
3
4
5
6
7
def hamming_weight(n):
    bits, mask = 0, 1
    for _ in range(32):
        if n&mask != 0:
            bits += 1
        mask <<= 1
    return bits
方法二：关键点是，一个数n和n-1的与运算操作，相当于去掉了最右面的1。 
1
2
3
4
5
6
def hamming_weigth(n):
    bits = 0
    while n:
        bits += 1
        n = (n-1) & n
    return bits

136. Single Number

找出数组中不重复的元素。其它元素出现两次。原题

1
2
Input: [4,1,2,1,2]
Output: 4
1
2
def single_num(nums):
    return reduce(lambda x, y: x ^ y, nums)

137. Single Number II

找出数组中出现一次的元素，其它元素出现三次。原题

1
2
Input: [2,2,3,2]
Output: 3

方法一：找出单独元素每一位的值。如果把所有数字的二进制每一位加起来，如果某一位可以被3整除，则表示单独元素的该位为0，否则为1。以下使用count来表示每一位1的个数。假设count%3!=0为True，说明该元素i位为1，然后是用|=更新ans在第i个位置的值，这里也可以使用+=，但是效率稍慢。convert的作用是因为python中的int是个对象，且没有最大限制，不是在第32位使用1来表示负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def singleNumber(self, nums, n=3):
    ans = 0
    for i in range(32):
        count = 0
        for num in nums:
            if ((num >> i) & 1):
                count += 1
        ans |= ((count%n!=0) << i)
    return self.convert(ans)

def convert(self, x):
    if x >= 2**31:
        x -= 2**32
    return x

这里有个状态机的解法，不明觉厉，留坑。讨论1和讨论2

1
2
3
4
5
6
def singleNumber(self, nums):
    ones, twos = 0, 0;
    for i in range(len(nums)):
        ones = (ones ^ nums[i]) & ~twos
        twos = (twos ^ nums[i]) & ~ones
    return ones

260. Single Number III

找出数组中两个唯一出现一次的元素，其余元素均出现两次。原题

1
2
Input:  [1,2,1,3,2,5]
Output: [3,5]

思想：将这两个元素分到两个组，由于这两个数不相等，所以亦或结果不为0，也就是说二进制中至少有一位1，记为第n位。我们以第n位是否为1，把数组分为两个子数组。

1
2
3
4
5
6
7
8
9
10
11
12
def singleNumber(self, nums):
    total_xor = self.get_xor(nums)
    mask = 1
    while total_xor&mask == 0:
        mask <<= 1
    p1 = [num for num in nums if num&mask==0]
    p2 = [num for num in nums if num&mask!=0]
    return [self.get_xor(p1), self.get_xor(p2)]
    
def get_xor(self, nums):
    from functools import reduce
    return reduce(lambda x, y: x ^ y, nums)

面试题 17.19. 消失的两个数字

此题和260很像，不同在于是从1~N消失了两个数字。要求在O(N)时间，O(1)空间实现。

方法一：可以使用260的方法，但是这样空间复杂度不符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
def missingTwo(self, nums: List[int]) -> List[int]:

    def get_missing(ary):
        return reduce(operator.xor, ary)
    nums = nums + list(range(1, len(nums)+3))
    total = get_missing(nums)
    mask = 1
    while total & mask == 0:
        mask <<= 1
    n1 = (n for n in nums if n&mask!=0)
    n2 = (n for n in nums if n&mask==0)
    return get_missing(n1), get_missing(n2)

方法二：以0~n-1中缺失的数字题为基础来解。写完了发现和方法一不就是同一种方法嘛，只不过用了循环来代替数组产生的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def missingTwo(self, nums: List[int]) -> List[int]:

    total = reduce(operator.xor, nums)
    for i in range(1, len(nums)+3):
        total ^= i
    mask = 1
    while mask & total == 0:
        mask <<= 1
    one = 0
    for n in nums:
        if mask & n: one ^= n
    for i in range(1, len(nums)+3):
        if mask & i: one ^= i
    return one, total^one
方法三：将方法一改为常数空间复杂度。 
1
2
3
4
5
6
7
8
9
10
11
12
13
def missingTwo(self, nums: List[int]) -> List[int]:

    def get_missing(ary):
        return reduce(operator.xor, ary)

    a, b, c = itertools.tee(chain(nums, range(1, len(nums)+3)), 3)
    total = get_missing(a)
    mask = 1
    while total & mask == 0:
        mask <<= 1
    n1 = (n for n in b if n&mask!=0)
    n2 = (n for n in c if n&mask==0)
    return get_missing(n1), get_missing(n2)
方法四：数学方法，根据0~n-1缺失的数字数学方法。使用两数的平均数来讲原数组分为两部分。这样问题就变成了找到一个缺失的数字。 
1
2
3
4
5
6
def missingTwo(self, nums: List[int]) -> List[int]:
    total = sum(range(1, len(nums)+3)) - sum(nums)
    mid = total / 2
    small = (n for n in nums if n <= mid)
    one = sum(range(1, int(mid)+1)) - sum(small)
    return one, total-one

方法五：这个是从评论中学习到的方法，很有意思。将对应索引置为负数，然后最后找正数的索引，就是缺失的两个数字。但是这样空间复杂度貌似不符合要求了。

1
2
3
4
5
def missingTwo(self, nums: List[int]) -> List[int]:
    nums += [1, 1]
    for n in nums[:-2]:
        nums[n-1] = -1
    return [i+1 for i, n in enumerate(nums) if n!=-1]

方法六：很快，我想到了生成器islice，但是用了发现不对，为什么？因为我在循环中改变了nums，导致了n出现了-1的情况。所以我们只改变符号，不改变数字，需要用一个abs。

1
2
3
4
5
def missingTwo(self, nums: List[int]) -> List[int]:
    nums += [1, 1]
    for n in islice(nums, len(nums)-2):
        nums[abs(n)-1] = -nums[abs(n)-1]
    return [i+1 for i, n in enumerate(nums) if n>0]

371. Sum of Two Integers

不用加减乘除做加法。原题

解析为何Python位运算有些不同

实际上加法分为三个步骤

  1. 相加但不进位，1^0=1，1^1=0，0^0=0，所以第一步用异或。
  2. 只求进位的结果，只有两个1才会进位，所以用&，然后左移1位，表示要进的位。
  3. 把前两步的结果再重复1，2步，直到没有进位产生，即b=0。
1
2
3
4
5
6
7
8
9
10
11
12
13
def getSum(self, a, b):
    # 32 bits integer max
    MAX = 0x7FFFFFFF  # 2**31-1
    # 32 bits interger min  
    MIN = 0x80000000  # -2**31
    # mask to get last 32 bits
    mask = 0xFFFFFFFF  # 2*32-1
    while b != 0:
        # ^ get different bits and & gets double 1s, << moves carry
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    # if a is negative, get a's 32 bits complement positive first
    # then get 32-bit positive's Python complement negative
    return a if a <= MAX else ~(a ^ mask)

190. Reverse Bits

返回一个数的二进制的倒序的十进制。原题

1
2
3
4
Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100, 
             return 964176192 represented in binary as 00111001011110000010100101000000.

方法一：使用原生库。ljust表示在右侧补’0’。或者使用format来补0。

1
2
3
def reverseBits(self, n):
    return int(bin(n)[:1:-1].ljust(32, '0'), 2)
    # return int('{:0<32s}'.format(bin(n)[:1:-1]), 2)

方法二：自己实现进制转换，使用位运算优化。

1
2
3
4
5
6
def reverseBits(self, n):
    code = ''
    for _ in range(32):
        code += str(n & 1)
        n >>= 1
    return sum([int(bit) << i for i, bit in enumerate(code[::-1])])
方法二改进：这里有个误区，为什么非要将整个二进制完整体现出来，再去遍历它转成int，而不是直接构建这个int。 
1
2
3
4
5
6
def reverseBits(self, n):
    code = 0
    for _ in range(32):
        code = (code<<1) + (n&1)
        n >>= 1
    return code

389. Find the Difference

s和t两个由小写字母组成的字符串，t是由s打乱顺序并再随机添加一个小写字母组成。原题

方法一：使用Collection。

1
2
3
def findTheDifference(self, s, t):
    from collections import Counter
    return next((Counter(t) - Counter(s)).elements())
方法二：使用异或。 
1
2
3
4
def findTheDifference(self, s, t):
    from operator import xor
    from functools import reduce
    return chr(reduce(xor, map(ord, s+t)))

401. Binary Watch

有这样一个二进制的手表，输入一个n，表示有几个亮着的灯，返回所有可能出现的时间。时间范围为12小时制，即hours(0-11)，minutes(0-59)。原题

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
一开始的思路：这是个错误的解法，因为分钟的灯不应该超过60分钟，因为要进位。类似的4和8的小时灯也不能同时亮起。 
1
2
3
4
5
6
7
def readBinaryWatch(self, num):
    from itertools import combinations
    # transform hours to minutes
    minutes = list(map(lambda x: x * 60, (1, 2, 4, 8))) + [32, 16, 8, 4, 2, 1]
    minutes_groups = combinations(minutes, num)
    res = ['{:d}:{:0>2d}'.format(sum(g)//60, sum(g)%60) for g in minutes_groups]
    return res

方法二：正确的写法。需要分开判断小时和分钟，然后再合并。

1
2
3
4
5
6
7
8
9
10
11
12
def readBinaryWatch(self, num):
    from itertools import combinations
    # transform hours to minutes
    hours = list(map(lambda x: x*60, (1, 2, 4, 8)))
    minutes = (1, 2, 4, 8, 16, 32)
    res = []
    for i in range(num+1):
        get_hours = [x for x in list(combinations(hours, i)) if sum(x) < 12 * 60]
        get_minutes = [x for x in list(combinations(minutes, num-i)) if sum(x) < 60]
        minutes_groups = [h+m for h in get_hours for m in get_minutes]
        res += ['{:d}:{:0>2d}'.format(sum(g)//60, sum(g)%60) for g in minutes_groups]
    return res
方法三：遍历所有可能的时间，找到符合条件的。因为表中的数组都是二进制，所以’1’的个数就是亮灯的个数。 
1
2
3
4
def readBinaryWatch(self, num):
    return ['{:d}:{:0>2d}'.format(h, m)
            for h in range(12) for m in range(60)
            if (bin(h)+bin(m)).count('1') == num]

405. Convert a Number to Hexadecimal

把一个32位有符号的整数转换成16进制。原题

1
2
3
4
5
6
7
8
9
Input:
26
Output:
"1a"

Input:
-1
Output:
"ffffffff"
1
2
3
def toHex(self, num):
    return ''.join(['0123456789abcdef'[(num >> 4 * i) & 15]
                     for i in range(8)])[::-1].lstrip('0') or '0'

461. Hamming Distance

求两个正数的原码中不同位的个数。原题

1
2
3
4
5
6
7
Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.
1
2
def hammingDistance(self, x, y):
    return bin(x ^ y).count('1')

476. Number Complement

给定一个正数，求其原码的按位取反后的数。原题

1
2
3
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

方法一：暴力的方法。

1
2
def findComplement(self, num):
    return int(''.join([str(1 ^ int(d)) for d in bin(num)[2:]]), 2)

方法二：其实就是求101和111的异或。所以先找到111。

1
2
3
4
5
def findComplement(self, num):
    i = 1
    while i <= num:
        i <<= 1
    return (i-1) ^ num
方法三：更少的位移。核心思想还是找到111。比如一个8位数，最高代表符号：1000000，先将其右移1位，使得左边两位都变成1。然后再右移2位，使得左边四位变成1，以此类推，8位数最多移动3次就可以得到1111111，32位则还需要再移动2次。 
1
2
3
4
5
def findComplement(self, num):
    mask = num
    for i in range(5):
        mask |= mask >> (2**i)
    return num ^ mask

693. Binary Number with Alternating Bits

二进制是否是交替的0和1。原题

1
2
3
4
Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

方法一：字符串法。

1
2
def hasAlternatingBits(self, n):
    return '00' not in bin(n) and '11' not in bin(n)

方法二：除2法。

1
2
3
4
5
6
7
def hasAlternatingBits(self, n):
    n, cur = divmod(n, 2)
    while n:
        if cur == n % 2:
            return False
        n, cur = divmod(n, 2)
    return True
方法三：异或。 
1
2
3
4
5
def hasAlternatingBits(self, n):
    if not n:
        return False
    num = n ^ (n >> 1)
    return not (num & num+1)

762. Prime Number of Set Bits in Binary Representation

求某范围的所有自然数中，二进制中1的个数是质数的个数。原题

1
2
3
4
5
6
7
8
9
Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

方法一：direct.

1
2
3
4
5
6
7
8
def countPrimeSetBits(self, L: 'int', R: 'int') -> 'int':
    primes = {2, 3, 5, 7, 11, 13, 17, 19}
    # ans = 0
    # for num in range(L, R+1):
    #     if bin(num)[2:].count('1') in primes:
    #         ans += 1
    # return ans
    return sum(bin(n)[2:].count('1') in primes for n in range(L, R+1))
方法二：位运算。p 的2，3，5，7。。位是1，其余是0，这样在右移后，可&1就可以判断这个数是否是质数。 
1
2
3
def countPrimeSetBits(self, L: 'int', R: 'int') -> 'int':
    p = int('10100010100010101100', 2)
    return sum(p >> bin(i).count('1') & 1 for i in range(L, R+1))

868. Binary Gap

二进制两个1的最大距离。原题

1
2
3
4
5
6
7
8
Input: 22
Output: 2
Explanation: 
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.

方法一：字符串或是位运算都可以。

1
2
3
4
5
6
7
8
9
10
def binaryGap(self, N: 'int') -> 'int':
    ans, last = 0, None
    # for i, b in enumerate(bin(N)[2:]):
    for i in range(32):
        # if b == '1':
        if (N >> i) & 1:
            if last is not None:
                ans = max(ans, i - last)
            last = i
    return ans
方法二：列表生成式。 
1
2
3
4
def binaryGap(self, N: 'int') -> 'int':
    one = [i for i, v in enumerate(bin(N)) if v == '1']
    # return max([one[i+1] - one[i] for i in range(len(one)-1)] or [0])
    return max([b-a for a, b in zip(one, one[1:])] or [0])

268. Missing Number

0~n中缺失的数字。原题

方法一：数学公式。

1
2
3
4
5
def missingNumber(self, nums):
    n = len(nums)
    expected_sum = n*(n+1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum
方法二：XOR.
index 0 1 2
value 3 0 1 
1
2
3
4
5
def missingNumber(self, nums: 'List[int]') -> 'int':
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing

1012. Complement of Base 10 Integer

非负数的反码。原题

1
2
3
4
5
6
def bitwiseComplement(self, N: int) -> int:
    mask = 1
    while mask < N:
        mask = (mask << 1) + 1
    # return mask - N
    return N ^ mask

1404. Number of Steps to Reduce a Number in Binary Representation to One

几下操作可以将其变为1。偶数除以2，奇数+1.原题

1
2
3
4
5
6
7
8
9
Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

方法一：将其转为数字最简单，但是失去了此题的意义。评论区看到的一个解法

110010 -> 110100 -> 111000 -> 1000000 takes 2(which is count of mid zeros) + 1 moves.
1000000 -> 1 takes 6 moves because length of s increases 1.

1
2
3
4
5
6
7
8
def numSteps(self, s: str) -> int:
    i, mid_0 = 0, 0
    for j in range(1, len(s)):
        if s[j] == '1':
            mid_0 += j - i - 1
            i = j
    if i == 0: return len(s) - 1
    return mid_0 + 1 + len(s)

201. Bitwise AND of Numbers Range

范围内的数字求与运算和。原题

1
2
Input: [5,7]
Output: 4
1
2
3
4
5
6
7
def rangeBitwiseAnd(self, m: int, n: int) -> int:
    i = 0 
    while m != n:
        m >>= 1
        n >>= 1
        i += 1
    return n << i

1442. Count Triplets That Can Form Two Arrays of Equal XOR

数组中找出两段的异或和相等。原题

方法一：此题在竞赛中做出来了，需要找到规律。

1
2
3
4
5
6
7
8
def countTriplets(self, arr: List[int]) -> int:
    m = list(itertools.accumulate([0] + arr, operator.xor))
    count = 0
    for i in range(len(m)):
        for j in range(i+1, len(m)):
            if m[i] == m[j]:
                count += j-i-1
    return count

1238. Circular Permutation in Binary Representation

返回指定为位数的二进制环，每两个数的二进制只有1位不同。原题

1
2
3
4
Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

方法一：我想了半天这道题，以为和二进制无关，是个数学题，没想到最后还得用异或来解决。这是个 gray code的问题，有一个公式。

1
2
def circularPermutation(self, n, start):
    return [start ^ i ^ i >> 1 for i in range(1 << n)]

393. UTF-8 Validation

题目描述非常之难懂，母语的人看着都看不明白。此题在Leetcode-cn上看的中文描述。针对一些数，它的二进制必须满足几种形式，如果是0开头，就是一个1字节的字符；如果110开头，说明是2字节的字符，其后面的二进制形式必须是10开头；如果1110开头，说明是3字节字符，后面必须跟两个10开头的字符。原题

1
2
3
4
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

方法一：字符串方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def validUtf8(self, data: List[int]) -> bool:
    b = 0
    for d in data:
        s = '{:0>8b}'.format(d)[-8:]
        if b:
            if not s.startswith('10'):
                return False
            else:
                b -= 1
                continue
        if s.startswith('0'): continue
        head = re.match(r'(^1{2,4}0)*', s).groups()[0]
        if not head:
            return False
        b = len(head) - 1
    return b == 0

方法二：位运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def validUtf8(self, data: List[int]) -> bool:
    b = 0
    for d in data:
        mask1, mask2 = 1<<7, 1<<6
        if b:
            if not((d&mask1) and (not d&mask2)):
                return False
            else:
                b -= 1
                continue
        while d&mask1:
            b += 1
            mask1 >>= 1
        if b==0: continue
        if b==1 or b>4: return False
        b -= 1
    return b == 0

318. Maximum Product of Word Lengths

给你一个单词列表，返回最大的两个没有相同字符的单词长度乘积。原题

1
2
3
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

方法一：直观解法。

1
2
3
4
5
6
7
8
def maxProduct(self, words: List[str]) -> int:
    ws = [(len(word), set(word)) for word in words]
    ans = 0
    for i in range(len(ws)):
        for j in range(i+1, len(ws)):
            if not ws[j][1] & ws[i][1]:
                ans = max(ans, ws[i][0]*ws[j][0])
    return ans
方法二：位运算。评论区看到的答案，怎么想的呢，单词只包含26个小写字母，又有相同字符判断，从而可以想出这样的解法。 
1
2
3
4
5
6
7
8
def maxProduct(self, words: List[str]) -> int:
    d = {}
    for w in words:
        mask = 0
        for c in set(w):
            mask |= 1<<(ord(c)-ord('a'))
        d[mask] = max(d.get(mask, 0), len(w))
    return max([d[i]*d[j] for i in d for j in d if not i&j] or [0])

1177. Can Make Palindrome from Substring

给定一个 字符串s，进行一些查询，针对s的切片内容能否将其打乱然后重新排列，在替换k个字符内将其变成回文的。返回这些查询结果。原题

1
2
3
4
5
6
7
8
Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

方法一：bit mask。我学会了，开始的时候想用Counter来计算，虽然通过了但是效率很慢。这样只包含字母的题可以用位运算异或来进行。思路和榜一大神不谋而合。

1
2
3
4
5
6
7
8
9
10
11
12
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
    
    d = [0]
    for c in s:
        d.append(d[-1] ^ (1 << (ord(c)-ord('a'))))

    ans = []
    for i, j, k in queries:
        cur = d[j+1] ^ d[i]
        # print(count_one(cur), i, j, format(cur, 'b'))
        ans.append(format(cur, 'b').count('1')//2 <= k)
    return ans
方法二：整理一下方法一。 
1
2
3
4
5
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
    d = [0]
    for c in s:
        d.append(d[-1] ^ (1 << (ord(c)-ord('a'))))
    return [bin(d[j+1] ^ d[i]).count('1')//2 <= k for i, j, k in queries]

421. Maximum XOR of Two Numbers in an Array

数组中两个数最大的异或值时多少。线性时间复杂度实现。

1
2
3
4
5
Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

方法一：Stefan的方法研究了半天。改成循环其实更容易理解。

1
2
3
4
5
6
7
def findMaximumXOR(self, nums: List[int]) -> int:
    ans = 0
    for i in range(32)[::-1]:
        ans <<= 1
        prefixes = {num>>i for num in nums}
        ans += any(ans^1^p in prefixes for p in prefixes)
    return ans

如何实现的呢？首先我们1位1位来更新ans，从最高位开始，尽可能让它为1，那么ans就会越大。

改成循环容易观察。每次我们想尽量获得nxt，然后找是否有另一个q，满足q ^ p = nxt。所以看到ans^1就是nxt。

1
2
3
4
5
6
7
8
9
10
11
def findMaximumXOR(self, nums: List[int]) -> int:
    ans = 0
    for i in range(32)[::-1]:
        ans <<= 1
        prefixes = {num>>i for num in nums}
        nxt = ans + 1
        for p in prefixes:
            if p ^ nxt in prefixes:
                ans = nxt
                break
    return ans

面试题 05.04. 下一个数

找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）

1
2
输入：num = 2（或者0b10）
输出：[4, 1] 或者（[0b100, 0b1]）

方法一：先用字符串来解。较大的数通过翻转最低位的01，然后重排后面的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findClosedNumbers(self, num: int) -> List[int]:
    nb = format(num, 'b')
    i, j, n = nb.rfind('01'), nb.rfind('10'), len(nb)
    if i >= 0:
        tail = nb[:i] + '10' + ''.join(sorted(nb[i+2:]))
        big = int(tail, 2)
    else:
        big = int('10' + nb[1:], 2)
    if j >= 0:
        tail = nb[:j] + '01' + ''.join(sorted(nb[j+2:], reverse=True))
        small = int(tail, 2)
    else:
        small = -1
    return big, small

方法二：位运算，这个方法没怎么看懂。评论区大佬的答案。

1
2
3
4
5
6
7
8
9
10
def findClosedNumbers(self, num: int) -> List[int]:
    if num == 1:
        return [2, -1]

    def next_combo(num):
        t = num & -num
        y = num + t
        return ((num & ~y)//t >> 1)|y

    return [next_combo(num), ~next_combo(~num)]

1029. Binary Prefix Divisible By 5

二进制前缀能否被5整除。原题

1
2
Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]

方法一：首次AC的方法。

1
2
3
4
5
6
7
def prefixesDivBy5(self, A: List[int]) -> List[bool]:
    num, ans = 0, []
    for d in A:
        num <<= 1
        num |= d 
        ans.append(not bool(num%5))
    return ans
方法二：取余操作具有累加性，简单的优化提升了3倍的速度。 
1
2
3
4
5
6
7
8
def prefixesDivBy5(self, A: List[int]) -> List[bool]:
    num, ans = 0, []
    for d in A:
        num <<= 1
        num |= d 
        num %= 5
        ans.append(not bool(num))
    return ans

645. Set Mismatch

1~n数组中包含一个重复的元素和一个缺失的元素。找出这两个元素。原题

1
2
Input: nums = [1,2,2,4]
Output: [2,3]
方法一：开始还想着用Counter实现，有些愚蠢。 
1
2
3
def findErrorNums(self, nums):
    diff_sum = sum(set(nums))
    return sum(nums)-diff_sum, sum(range(1, len(nums)+1))-diff_sum

方法二：在原数组元素*-1记录。空间复杂度为常数，但是改变了原数组，时间复杂度稍微高一点，因为迭代两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
def findErrorNums(self, nums: 'List[int]') -> 'List[int]':
    dup, miss = -1, 1
    for num in nums:
        if nums[abs(num)-1] < 0:
            dup = abs(num)
        else:
            nums[abs(num)-1] *= -1
    
    for i in range(len(nums)):
        if nums[i] > 0:
            miss = i + 1
    
    return dup, miss

方法三：XOR。

1734. Decode XORed Permutation

说有个奇数长度的数组是，从1到n的全排列的一种。将每两个相邻的数做异或运算。得到一个新的数组encoded。给你这个encoded，让你还原原数组。

1
2
Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

方法一：这题并不算难，只是竞赛没时间做了。首先从题中获取条件，可以得到1~n的异或和，然后考虑奇数条件如何使用。这点没有想到，我们可以跳跃切分来用，比如4^1=5，5^3=6，这样我们可以通过总的异或和求出第一个数是多少。

1
2
3
4
def decode(self, encoded: List[int]) -> List[int]:
    xor_sum = reduce(xor, range(1, len(encoded)+2))
    first = reduce(xor, encoded[1::2]) ^ xor_sum
    return list(accumulate([first] + encoded, xor))

1178. Number of Valid Words for Each Puzzle

找到每个谜面符合条件的单词数，谜面的第一个字符在单词中，单词的所有字符均在谜面中出现过。

1
2
3
4
5
6
7
8
9
10
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

方法一：状态压缩+哈希。对于每个单词根据是否出现可以压缩成一个26的数字。对于每个puzzle来说，只要puzzle[0] 和puzzle[1:]字符串的一个子集压缩后时相等的，那么就有一个word是符合条件的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:

    def compress_word(w):
        bit = 0
        for c in w:
            bit |= 1 << (ord(c)-ord('a'))
        return bit

    freq = Counter()
    for word in words:
        freq[compress_word(word)] += 1

    res = []
    for puzzle in puzzles:
        total = 0
        bit = 1 << (ord(puzzle[0])-ord('a'))
        for sub in self.subsets(puzzle[1:]):
            bit2 = bit
            bit2 |= compress_word(''.join(sub))
            total += freq[bit2]
        res.append(total)
    return res

def subsets(self, word):
    ans = [[]]
    for c in word:
        ans += [pre+[c] for pre in ans]
    return ans

2354. Number of Excellent Pairs

找到优质数对。如果弯转过来了很简单。比赛是忽略了是与运算和或运算的和。所以其实就是统计两个数1的个数。

方法一：Lee的方法。

1
2
3
def countExcellentPairs(self, A: List[int], k: int) -> int:
    c = Counter(map(int.bit_count, set(A)))
    return sum(c[k1] * c[k2] for k1 in c for k2 in c if k1 + k2 >= k)

779. K-th Symbol in Grammar

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

方法一：自己想的递归。规律为每一行新增了上一行的反码。

1
2
3
4
5
6
7
def kthGrammar(self, n: int, k: int) -> int:
    if n == 1:
        return 0
    if k > 2**(n-2):
        return self.kthGrammar(n-1, k-2**(n-2)) ^ 1
    else:
        return self.kthGrammar(n-1, k)

方法二：位运算，由于k从1开始，我们将它-1.一行中的第 i个字符，会在第 2i和第 2i+1 个位置产生两个字符。如果第 i 个字符是 00，那么在位置2i 和 2i+1 产生的字符分别是 0 和1；如果第 i 个字符是 1，产生的字符是 1和 0。

可以发现，第 2i （偶数位）个字符总是和第 i个字符相同，而第 2i+1 （奇数位）个字符是第 i 个字符的反转。也就是说，奇数位上的字符总是发生了一次反转而来的。反转偶数次，字符不变；反转奇数次，相当于反转了一次。

因此，我们只需要看 k 这个数字是否是奇数，若是，累计一次反转。然后将 k 除以 2，继续判断，并累计反转次数，直至 k 为 0。

最后判断反转的次数是否为奇数，是则答案为 1，否则为 0。

1
2
def kthGrammar(self, n: int, k: int) -> int:
    return (k - 1).bit_count() & 1