資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中每個謎題的有效單詞數
假設有一個謎題字串，如果滿足以下兩個條件，則一個單詞是有效的：
單詞包含謎題的第一個字母。
單詞中的每個字母都在謎題中。
例如，如果謎題是“abcdefg”，則有效單詞為“face”、“cabbage”等；但無效單詞為“beefed”（因為它不包含'a'）和“based”（因為它包含's'，而's'不在謎題中）。
我們必須找到答案列表，其中answer[i]是給定單詞列表words中相對於謎題puzzles[i]有效的單詞數。
因此，如果輸入類似於words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"], 則輸出將為[1,1,3,2,4,0]，因為“aboveyz”有一個有效單詞：“aaaa”，“abrodyz”有一個有效單詞：“aaaa”，“abslute”有三個有效單詞：“aaaa”、“asas”、“able”，“absoryz”有兩個有效單詞：“aaaa”、“asas”，“actresz”有四個有效單詞：“aaaa”、“asas”、“actt”、“access”，而“gaswxyz”沒有有效單詞，因為列表中沒有單詞包含字母'g'。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式getMask()，它將接收s作為引數：
mask := 0
for i := 0 to size of s -1:
mask := mask OR 2^(s[i] - 'a'的ASCII碼)
return mask
在主方法中執行以下操作：
定義一個數組ans
定義一個map m
for i := 0 to size of w -1:
word := w[i]
mask := 0
for j := 0 to size of word -1:
mask := mask OR getMask(w[i])
m[mask]++
for i := 0 to size of p -1:
word := p[i]
mask := getMask(word)
first := 2^(word[0] - 'a'的ASCII碼)
current := mask
temp := 0
while current > 0:
if current & first != 0:
temp += m[current]
current := (current - 1) & mask
ans.append(temp)
return ans
讓我們看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
lli getMask(string s){
lli mask = 0;
for(int i =0;i<s.size();i++){
mask|= 1<<(s[i]-'a');
}
return mask;
}
vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
vector <int> ans;
map <lli, lli > m;
for(int i =0;i<w.size();i++){
string word = w[i];
lli mask = 0;
for(int j =0;j<word.size();j++){
mask|= getMask(w[i]);
}
m[mask]++;
}
for(int i = 0; i<p.size();i++){
string word = p[i];
lli mask = getMask(word);
lli first = 1<<(word[0]-'a');
lli current = mask;
lli temp = 0;
while(current>0){
if(current & first)temp+=m[current];
current = (current-1)&mask;
}
ans.push_back(temp);
}
return ans;
}
};
main(){
Solution ob;
vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
print_vector(ob.findNumOfValidWords(v,v1));
}即時演示
{"aaaa","asas","able","ability","actt","actor","access"},
{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}輸入
[1, 1, 3, 2, 4, 0, ]
更新於：2020年6月8日
