資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告