数字马力毁意向，应届生欲哭无泪。。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近关于数字马力毁意向这件事在牛客网频频出现，原因就是数字马力发出的offer接受率高于预期，导致剩余缺口不多。那些OC过的可能收不到offer了，OC是什么意思呢？Offer Call简称OC，当面试官决定录用求职者后，HR会通过电话联系的方式询问求职者是否接受Offer，口头的形式，不是正式的书面offer。

虽然不是书面offer，但你之前Offer Call的时候给别人说打算录用你了，准备给你发offer了，而现在突然又不发了，这就叫毁意向。我们知道如果发了书面offer在返回是违法的，但这种口头承诺的offer，后面又不发了，到底违不违法？不管违不违法，反正是不得人心的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第318题：最大单词长度乘积。

问题描述

来源：LeetCode第318题

难度：中等

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"] 输出：16 解释：这两个单词为 "abcw", "xtfn"。

示例2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"] 输出：4 解释：这两个单词为 "ab", "cd"。

• 2 <= words.length <= 1000

• 1 <= words[i].length <= 1000

• words[i] 仅包含小写字母

问题分析

这题是让找出两个单词长度的最大乘积，并且这两个单词不能有公共的字母。计算单词长度的乘积比较简单，这里的关键点是怎么判断两个字符串是否有公共的字母。

因为提示中说了字符串仅包含小写字母，小写字母总共有26个，所以我们可以使用位运算来判断。对于每一个字符串都可以使用一个int类型的数字来标记，从右往左第一位是 a，第二位是 b ……，出现了哪个字母就在相应的位置标记为 1 。

如果两个数字通过与运算（&）结果为 0 ，说明这两个字符串没有公共的字母，可以计算它两长度的乘积，最后只需要保留最大乘积即可。

JAVA：

public int maxProduct(String[] words) {     int length = words.length;     // 记录每个字符串中有哪些字母     int[] bits = new int[length];     int ans = 0;     for (int i = 0; i < length; i++) {         // 标记当前字符串有哪些字母         for (char ch : words[i].toCharArray())             bits[i] |= 1 << (ch - 'a');         // 如果当前字符串和之前的字符串没有公共的字母，就计算他们的         // 乘积，保留最大值即可。         for (int j = 0; j < i; j++) {             // 如果结果为0，表示他们没有公共的字母             if ((bits[i] & bits[j]) == 0)                 ans = Math.max(ans, (words[i].length() * words[j].length()));         }     }     return ans; }

C++：

public:     int maxProduct(vector

  &words) {         int length = words.size();         // 记录每个字符串中有哪些字母         vector

  bits(length);         int ans = 0;         for (int i = 0; i < length; i++) {             // 标记当前字符串有哪些字母             for (char &ch: words[i])                 bits[i] |= 1 << (ch - 'a');             // 如果当前字符串和之前的字符串没有公共的字母，就计算他们的             // 乘积，保留最大值即可。             for (int j = 0; j < i; j++) {                 // 如果结果为0，表示他们没有公共的字母                 if ((bits[i] & bits[j]) == 0)                     ans = max(ans, int(words[i].size() * words[j].size()));             }         }         return ans;     }

Python：

def maxProduct(self, words: List[str]) -> int:     length = len(words)     # 记录每个字符串中有哪些字母     bits = [0] * length     ans = 0     for i in range(0, length):         # 标记当前字符串有哪些字母         for ch in words[i]:             bits[i] |= 1 << (ord(ch) - ord('a'))         # 如果当前字符串和之前的字符串没有公共的字母，就计算他们的         # 乘积，保留最大值即可。         for j in range(0, i):             # 如果结果为0，表示他们没有公共的字母             if (bits[i] & bits[j]) == 0:                 ans = max(ans, len(words[i]) * len(words[j]))     return ans

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。