当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 5: maximum product of word length
[algorithm] sword finger offer2 golang interview question 5: maximum product of word length
2022-07-06 12:51:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 5: Maximum product of word length
subject 1:
Given an array of strings words, Please calculate when two strings words[i] and words[j] Does not contain the same characters , The maximum of the product of their lengths . Suppose that the string contains only English lowercase letters . If there is no pair of strings that do not contain the same characters , return 0.
Example 1:
Input : words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
Output : 16
explain : These two words are “abcw”, “fxyz”. They do not contain the same characters , And the product of length is the largest .
Example 2:
Input : words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output : 4
explain : These two words are “ab”, “cd”.
Example 3:
Input : words = [“a”,“aa”,“aaa”,“aaaa”]
Output : 0
explain : There are no such two words .
Tips :
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] Only lowercase letters
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/aseY1I
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas 1:
The number of letters is only 26 individual , We can use one int 32 To record whether the word contains the letter
such as
“ac”0101
ac: Last 1 On behalf of a There is , Next to last 0 representative b non-existent
“bd”1010
ac Binary system & bd If the binary of is 0, Prove different , On the contrary, they are the same
- take word Convert to binary time complexity O(n*k)
- Use & The operation finds no duplicate numbers word Calculation length refresh length time complexity O(n2)
Code
func maxProduct(words []string) int {
// Ideas :
// * take word Convert to binary time complexity O(n*k)
// * Use & The operation finds no duplicate numbers word Calculation length refresh length time complexity O(n2)
// Processing parameters
if len(words) < 2 {
return 0
}
// take word Convert to binary time complexity O(n*k)
nums := make([]int,len(words))
for i:=0;i<len(words);i++ {
for j:=0;j<len(words[i]);j++{
nums[i] |= (1<<(words[i][j] - 'a'))
}
}
// Use & The operation finds no duplicate numbers word Calculation length refresh length time complexity O(n2)
max := 0
for i:=0;i<len(words);i++ {
for j:=i + 1;j<len(words);j++{
if nums[i] & nums[j] == 0 {
tempMax := len(words[i]) * len(words[j])
if tempMax > max {
max = tempMax
}
}
}
}
return max
}
test
边栏推荐
- Latex learning
- [Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
- 【无标题】
- (the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)
- (core focus of software engineering review) Chapter V detailed design exercises
- [offer78] merge multiple ordered linked lists
- Naive Bayesian theory derivation
- Mixed use of fairygui button dynamics
- Mysql database index
- VLSM variable length subnet mask partition tips
猜你喜欢
[算法] 剑指offer2 golang 面试题6:排序数组中的两个数字之和
Force buckle 1189 Maximum number of "balloons"
Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
微信小程序开发心得
2021.11.10 compilation examination
Particle system for introduction to unity3d Foundation (attribute introduction + case production of flame particle system)
[算法] 剑指offer2 golang 面试题2:二进制加法
MySQL shutdown is slow
(core focus of software engineering review) Chapter V detailed design exercises
Fairygui gain buff value change display
随机推荐
Mysql database index
Idea problem record
In 2020, the average salary of IT industry exceeded 170000, ranking first
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
Itext 7 生成PDF总结
idea中导包方法
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
SVN更新后不出现红色感叹号
FairyGUI增益BUFF数值改变的显示
Unity3D,阿里云服务器,平台配置
[leetcode622]设计循环队列
Vulnhub target: hacknos_ PLAYER V1.1
How to reduce the shutdown time of InnoDB database?
The master of double non planning left the real estate company and became a programmer with an annual salary of 25W. There are too many life choices at the age of 25
[Offer18]删除链表的节点
Fairygui gain buff value change display
Expected value (EV)
[offer9] implement queues with two stacks
FairyGUI人物状态弹窗
堆排序【手写小根堆】