目录
最大单词长度乘积方法一:位运算(java)方法一:位运算(go)最大单词长度乘积
给你一个字符串数组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"。
示例 3:输入:words = ["a","aa","aaa","aaaa"]
输出:0
解释:不存在这样的两个单词。
方法一:位运算(java)
为了得到最大单词长度乘积,朴素的做法是,遍历字符串数组 words 中的每一对单词,判断这一对单词是否有公共字母,如果没有公共字母,则用这一对单词的长度乘积更新最大单词长度乘积。
题目约定了每个单词仅包含小写字母,所以,我们可以将单词中的每个字母都映射到一个 int 类型的不同位上,这样,就做到了每个单词都对应一个 int 类型的数值,这样的话,我们对比两个单词是否包含相同的字母,只需要把它们对应的 int 数值做 & 运算,看是不是等于 0 即可,如果等于 0 ,说明没有相同的位是 1,也就不存在相同的字母。
这样,我们在比较两个单词是否没有公共字母的时候只要直接按位与一下即可,没有公共字母应该得到的值是0,其他情况得到的值都不为零。
class Solution { public int maxProduct(String[] words) { Mapmap = new HashMap (); int length = words.length; for (int i = 0; i < length; i++) { int mask = 0; String word = words[i]; int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { mask |= 1 << (word.charAt(j) - "a"); } if (wordLength > map.getOrDefault(mask, 0)) { map.put(mask, wordLength); } } int maxProd = 0; Set maskSet = map.keySet(); for (int mask1 : maskSet) { int wordLength1 = map.get(mask1); for (int mask2 : maskSet) { if ((mask1 & mask2) == 0) { int wordLength2 = map.get(mask2); maxProd = Math.max(maxProd, wordLength1 * wordLength2); } } } return maxProd; } }
l:数组中所有单词的长度之和
n:数组长度
时间复杂度:o(l+n^2)
空间复杂度:o(n)
方法一:位运算(go)
具体的方法思路已经在上文中表述,详情请看上文内容
func maxProduct(words []string) int { hash := func(word string) int { res := 0 for _, r := range word{ res |= 1 << (r - "a") } return res } m, ans := map[int]int{}, 0 for _, word := range words { h := hash(word) if m[h] < len(word) { for other, v := range m { if((other & h) == 0){ if tmp := v * len(word); tmp > ans { ans = tmp } } } m[h] = len(word) } } return ans }
l:数组中所有单词的长度之和
n:数组长度
时间复杂度:o(l+n^2)
空间复杂度:o(n)
以上就是Go Java算法最大单词长度乘积示例详解的详细内容,更多关于Go Java算法单词长度乘积的资料请关注脚本之家其它相关文章!
X 关闭
X 关闭
- 1联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 2亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 3现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 4如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 5AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 6转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 7充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 8好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 9名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?
- 10亚马逊云科技成立量子网络中心致力解决量子计算领域的挑战