Python-位运算-LeetCode318最大长度乘积

接着上一篇关于python位运算，这篇主要是关于位运算的使用-状态压缩

会涉及以下几方面内容:

• & 按位与运算符: 0&0=0&1=1&0=0，1&1=1
• | 按位或运算符: 0 | 1=1 | 0=1 | 1=1，0 | 0=0
• << 左移动运算符: 1<<2=1 x 2^2=1 x 4 =4 =100

主要参考的相关网站有以下:

https://leetcode.cn/problems/maximum-product-of-word-lengths/description/

其他说明：

• 这题可以一题双解，除了用位运算之外；也可以用set求交集来求解

{1,2,3}&{3,4,5,2}={3,2}

字符状态压缩

模拟实例:

有两个字符串，分别为abcw, baz 字符变量的情况如下:

当两个字符 string-1&string-2等于0，表示没有相同的字母；

class Solution:
#2进制字符状态压缩
def maxProduct(self, words) -> int:
  maxLength=0
  n=len(words) #字符串长度
  check=[0]*len(words) #位运算状态
  #字符串状态压入
  for n1,word1 in enumerate(words): #循环每个字符串
    for ch in word1: #循环每个字母
      # 用位运算统计每个字符串中，每个字符的使用情况
      # 具体参考上面说明
      check[n1]|=1<<(ord(ch)-97) #ord(a)=97
  #双指针循环比较，是否有重复字母
  for n1 in range(n): #遍历已记录字符串
    for n2 in range(n1+1,n): #比后一位开始比较
      if (check[n1]&check[n2])==0: #如果没有重复字母
        #取乘积和较大值
        maxLength=max(maxLength,len(words[n1])*len(words[n2]))
  return maxLength #返回值
words = ["abcw","baz","foo","bar","xtfn","abcdef"]
ans=Solution().maxProduct(words)
print(ans)print(f'~a 的值为={c}',bin(c))

集合方法-求交集

class Solution:
#set集合方法
def maxProduct_set(self, words) -> int:
  maxLength=0
  n=len(words) #字符串长度
  vSet=[set(word) for word in words] #为每个字符串生成set
  for n1 in range(n): #遍历已记录字符串
    for n2 in range(n1+1,n): #比后一位开始比较
      if not vSet[n1]&vSet[n2]: #如果没有重复字母
        #取乘积和较大值
        maxLength=max(maxLength,len(words[n1])*len(words[n2]))
  return maxLength #返回值
words = ["abcw","baz","foo","bar","xtfn","abcdef"]
ans2=Solution().maxProduct_set(words)
print(ans2)

这个题目是一个很好的一题双解，对理解位运算有很好的帮助。