我已經(jīng)解決了這個問題，但無法提出通過所有測試用例的最有效的問題。它在 5 個測試用例中超時。確定句子包含短語的所有單詞0：克里斯和詹妮弗今天早上吵架了1：克里斯去度假2：詹妮弗在監(jiān)獄里查詢短語為0：chris jennifer1：jennifer2：監(jiān)獄目標(biāo)是為每個查詢找到匹配句子的索引，如果不存在匹配的句子，則為 -1。單詞的順序無關(guān)緊要。輸出：00 22即第一個查詢在句子 0 中有匹配的詞，在句子 0 和 1 中有第二個匹配詞，依此類推。約束n：句子數(shù)m: prases 的數(shù)量n, m < 10^4任何句子或查詢短語中的單詞數(shù)在 [1-10] 范圍內(nèi)每個單詞最多有 11 個字符沒有單詞出現(xiàn)在超過 10 個句子中每個單詞僅由大小寫字母組成每個單詞必須完全匹配——即喜歡和喜歡不匹配。輸入格式：3克里斯和詹妮弗今天早上吵架了克里斯去度假詹妮弗在監(jiān)獄里3克里斯詹妮弗監(jiān)獄每個 3 代表句子或查詢的數(shù)量。以下是我嘗試過的...1.我的第一個解決方案：為每個句子制作 HashMap對于短語中的每個拆分單詞：2-1。檢查句子hashmap2-2中是否存在所有單詞。如果是這樣，則存儲索引2-3。如果所有句子都不存在匹配的句子，則存儲-1。打印結(jié)果let p = 句子中的最大單詞數(shù) let k = 查詢中的最大單詞數(shù)Big O 是O(npk)
3 回答
蝴蝶刀刀
TA貢獻(xiàn)1801條經(jīng)驗 獲得超8個贊
維護(hù)一個HashMap將Strings映射到Set<Int>. 這個想法是跟蹤給定單詞出現(xiàn)在哪些句子中。我們使用集合而不是數(shù)組來支持有效地計算兩個集合的交集。
對于每個輸入句子：
將其分詞成詞，將當(dāng)前句子的索引加入當(dāng)前分詞對應(yīng)的Set中。
對于每個查詢短語：
將其標(biāo)記為單詞。
查詢每個詞對應(yīng)的索引集
取所有這些集合的交集。
時間復(fù)雜度：假設(shè)每個句子有 10 個單詞，構(gòu)建 HashMap 的成本是 O(10N log N)。每個查詢的成本是 O(10 * log(N))。
尚方寶劍之說
TA貢獻(xiàn)1788條經(jīng)驗 獲得超4個贊
我有以下可能會加速的想法，它似乎與 Rishav 提出的類似：
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new FileInputStream("file.txt"));
int numberOfSentences = Integer.parseInt(sc.nextLine());
Set<Integer> sentences = new HashSet<Integer>();
Map<String, Set<Integer>> words2Sentences = new HashMap<String, Set<Integer>>();
for (int i = 0; i < numberOfSentences; i++) {
String words[] = sc.nextLine().split(" ");
for (int j = 0; j < words.length; j++) {
if (!words2Sentences.containsKey(words[j])) {
words2Sentences.put(words[j], new HashSet<Integer>());
}
words2Sentences.get(words[j]).add(i);
}
sentences.add(i);
}
int numberOfPhrases = Integer.parseInt(sc.nextLine());
List<Set<Integer>> phraseResults = new ArrayList<Set<Integer>>();
for (int i = 0; i < numberOfPhrases; i++) {
Set<String> phrases = new HashSet<String>(Arrays.asList(sc.nextLine().split(" ")));
Set<Integer> result = new HashSet(sentences);
for (String s : phrases) {
result.retainAll(words2Sentences.get(s));
}
phraseResults.add(result);
}
for (Set<Integer> set : phraseResults) {
for (Integer i : set) {
System.out.print(i);
}
System.out.println();
}
}
收到一只叮咚
TA貢獻(xiàn)1821條經(jīng)驗 獲得超5個贊
這種方法應(yīng)該有效。
#include <bits/stdc++.h>
using namespace std;
vector<set<int>> getres(vector<string> sentences, vector<string> phrases, vector<set<int>> v){
map<string,set<int>> m;
map<string,set<int>> :: iterator itr;
for(int i=0;i<sentences.size();i++){
string temp = sentences[i];
temp.push_back(' ');
string word = "";
for(int j=0;j<temp.length();j++){
if(temp[j] == ' '){
itr = m.find(word);
if(itr == m.end()){
set<int> s;
s.insert(i);
m.insert({word,s});
}
else if(itr != m.end()){
itr->second.insert(i);
}
word = "";
}
else{
word.push_back(temp[j]);
}
}
}
// for(itr = m.begin();itr!= m.end();itr++){
// cout<<itr->first <<" ";
// for(auto f= itr->second.begin();f!= itr->second.end();f++){
// cout<<*f<<" ";
// }
// cout<<endl;
// }
for(int i=0;i<phrases.size();i++){
string temp = phrases[i];
temp.push_back(' ');
string word = "";
int flag = 0;
set<int> s1,s2,s3;
for(int j=0;j<temp.length();j++){
if(temp[j] == ' '){
// cout<<"yes";
itr = m.find(word);
if(itr == m.end()){
flag = 1;
break;
}
else if(itr != m.end()){
if(s1.empty()){
s1 = itr->second;
}
else{
set_intersection(s1.begin(),s1.end(),itr->second.begin(),itr->second.end(),inserter(s3,s3.begin()));
s1 = s3;
s3.clear();
if(s1.empty()){
flag = 1;
break;
}
}
// for(auto f=s1.begin();f!= s1.end();f++){
// cout<<*f<<" ";
// }
// cout<<endl;
}
word = "";
}
else{
word.push_back(temp[j]);
}
}
if(flag == 1){
s1.clear();
s1.insert(-1);
v[i] = s1;
flag = 0 ;
}
else{
v[i] = s1;
}
s1.clear();
s2.clear();
s3.clear();
}
return v;
}
int main() {
vector<string> sentences = {"chris and jennifer had a fight this morning", "chris went on a holiday", "jennifer is in prison"};
vector<string> phrases = {"chris jennifer", "jennifer", "prison"};
vector<set<int>> v(phrases.size());
v = getres(sentences,phrases,v);
for(int i=0;i<v.size();i++){
set<int> :: iterator itr;
for(itr = v[i].begin() ;itr != v[i].end();itr++){
cout<<*itr<<" ";
}
cout<<endl;
}
// cout<<"finish"<<endl;
}
添加回答
舉報
0/150
提交
取消