image-20231021095935123

位运算

首先介绍一下常见位运算的符号（通常在各个编程语言中位运算的符号都是相似的）

运算符 描述
& 按位与运算，参与运算的两个值如果二进制对应位置都为1结果为1，否则为0
| 按位或运算，参与运算的两个值如果二进制对应位置有一个为1结果为1，两个均为0结果才为0
^ 按位异或运算，当两个二进制位置对应位置不同时，结果为1，否则为0
~ 按位取反运算，对数据的每个二进制位置取反，把0变为1，把1变为0
<< 左移运算符：运算数的各位二进制全部左移若干位，由<<符号右边的数字决定左移多少位，高位丢弃，低位自动补0
>> 右移运算符：运算数的各位二进制全部右移若干位，由>>符号右边的数字决定右移多少位。

位运算在力扣中有很多题目的应用，位运算通常都是常数级别的时间复杂度

  1. 按位与（&）、按位或（|）、按位异或（^）等基本位运算的时间复杂度是 O(1)，它们在一个常数时间内完成。
  2. 位左移（<<）**和**位右移（>>）运算的时间复杂度也是 O(1)，因为它们只是在二进制数的表示上进行了移位操作。

2135.统计追加字母可以获得的单词

我第一次解法

整体思路如下：

  1. 首先将startWords中的单词全部转换为一个集合存放在一个列表中
  2. 将targetWords中的单词也全部转换为集合存放在列表中
  3. 通过两层for循环来遍历所有在target中的单词，和start中的单词集合元素取不同时包含在st集合与ta集合中的元素且要满足ta的长度-1等于st的长度，这样就可以确保由st中的单词随机添加一个就可以构成ta中的单词了
  4. 如果满足条件，将res+1，然后break掉，判断下一个单词是否可以由st中的单词获得
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        res = 0
        start = [set(x) for x in startWords]
        # print("start",start)
        target = [set(x) for x in targetWords]
        # print("target",target)
        for ta in target:
            for st in start:
                # print("ta={},st={}".format(ta,st))
                # if 0<=len((ta-st))<=1 and len((st-ta))==0:
                if len(st^ta)==1 and len(ta)-1==len(st):
                    # print(st)
                    res+=1
                    break
    
        return res

由于当startWords和targetWords中的单词可能会特别长，在理论上集合最长的情况下，集合取各种关系的时候需要重复遍历整个集合，容易造成很大的时间开销，因此我这个代码在部分测试用例的时候可以通过，整体不能通过

位运算+哈希表解法

官方给出的解法是可以使用位运算，我看了下源代码，就是在我用集合进行比较的地方将其换成位运算操作能够极大的减少时间开销。

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
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        # s是一个用于存放startWords中的元素的哈希表，查询速度为O(1)
        s = set()
        for word in startWords:
            mask = 0
            for ch in word:
                # 按位或运算 只要对应的二进制有一个为1那么结果就为1，这样就把一个单词中的所有字符用掩码的形式表示出来了
                mask |= 1 << (ord(ch) - ord('a'))
            # 将每个单词的掩码存放在一个哈希表中
            s.add(mask)
        # print("startword中的mask",s)
        ans = 0
        for word in targetWords:
            mask = 0
            # print("word",word)
            # 计算整个单词的掩码
            for ch in word:
                mask |= 1 << (ord(ch) - ord('a'))
            # 遍历单词，在去掉单词的每个字符的情况下，对比是否在哈希表中，如果在则将结果+1并break出来，
            for ch in word:
                if mask ^ (1 << (ord(ch) - ord('a'))) in s:  # 去掉这个字符
                    ans += 1
                    break
        return ans

备注：ord()是Python内置方法，用于求一个字符的unicode编码

371.两整数之和

给你两个整数a和b，不使用运算符+和-，计算并返回两整数之和。

思路

image-20231026203400843