数据结构
网络
关系数据库管理系统 (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日
