数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中单词长度的最大乘积
假设我们有一个名为 words 的字符串数组，找到 length(word[i]) * length(word[j]) 的最大值，其中这两个单词不共享公共字母。我们可以假设每个单词只包含小写字母。如果不存在这样的两个单词，则返回 0。因此，如果输入类似于 [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]，则输出将为 16，因为两个单词可以是“abcw”，“xtfn”。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 getRev() 的方法，它将 x 作为输入
ret := 0
对于 i 的范围从 0 到 25
如果 x / (2^i) 为偶数，则 ret := ret OR 2^i
返回 ret
从主方法中，执行以下操作：
创建一个映射 m，n := words 数组的大小
对于 i 的范围从 0 到 n – 1
s := words[i]，key := 0
对于 j 的范围从 0 到 s 的大小
- key := key OR 2^(s[j] – ‘a’ 的 ASCII 码)
m[i] := key
ret := 0
对于 i 的范围从 0 到 words 的大小 - 1
对于 j 的范围从 i + 1 到 words 的大小 – 1
如果 m[i] AND m[j] = 0，则 ret := word[i] 的大小 * word[j] 的大小的最大值
返回 ret
示例 (C++)
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h&g;
using namespace std;
class Solution {
public:
int getRev(int x){
int ret = 0;
for(int i = 0; i <= 25 ; i++){
if(!((x >> i) & 1)){
ret |= (1 << i);
}
}
return ret;
}
int maxProduct(vector<string>& words) {
unordered_map <int, int> m;
int n = words.size();
for(int i = 0; i < n; i++){
string s = words[i];
int key = 0;
for(int j = 0; j < s.size(); j++){
key |= 1 << (s[j] - 'a');
}
m[i] = key;
}
int ret = 0;
for(int i = 0; i < words.size(); i++){
for(int j = i + 1; j < words.size(); j++){
if((m[i] & m[j]) == 0){
//cout << i << " " << j << endl;
ret = max(ret, (int)words[i].size() * (int)words[j].size());
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
cout << (ob.maxProduct(v));
}输入
["abcw","baz","foo","bar","xtfn","abcdef"]
输出
16
更新于: 2020年5月2日
416 次浏览
广告