牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份。密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：密匙 b 的长度不超过密匙 a 的长度。对于任意 0 <= i < length(b)，有 b[i+1] – b[i] == a[i+1] – a[i]。现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组。请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙a。

区块链毕设网qklbishe.com为您提供问题的解答

牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份。密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：

密匙 b 的长度不超过密匙 a 的长度。
对于任意 0 <= i < length(b)，有 b[i+1] – b[i] == a[i+1] – a[i]。

现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组。请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙a。

简单的字典树应用，
这题的母题： <- 重要

“`

#include<bits/stdc++.h>

using namespace std;

const int N = 450;

// 0 1 2 3 4 5 6 7 8 9 10 11

// ‘0’ ‘1’ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’ ‘-‘ ‘#’

class Solution

{

private:

vector<int> ans;

int cnt; // 当前结点(第几个结点)

int Tree[N][26]; // 结点路径记录表

int pass[N]; // 该结点的通过数

int endd[N]; // 该结点作为末尾数

private:

string vec_to_str(vector<int> arr)

{

string ans;

ans.clear();

for(int i=1 ; i<=arr.size()-1 ; i++)

{

ans.append(to_string(arr[i]-arr[i–1]));

ans+=‘#’;

}

return ans;

}

// 12种方向的转化：

int transform(const char& c)

{

// ‘0’ ~ ‘9’

if((c>=‘0’) && (c<=‘9’))

{

return (c–‘0’);

}

// ‘-‘

else if(c==‘-‘)

{

return 10;

}

else

{

return 11;

}

// 插入单词到字典树中

void word_insert(string word)

{

int tool=1;

int path=0;

pass[tool]++;

for(const auto& c : word)

{

path = transform(c);

if(Tree[tool][path]==0)

{

Tree[tool][path] = ++cnt;

}

tool = Tree[tool][path];

pass[tool]++;

}

endd[tool]++;

return;

}

// 在字典树中找单词

int word_find(string word)

{

int tool=1;

int path=0;

for(const auto& c : word)

{

path = transform(c);

if(Tree[tool][path]==0)

{

return 0;

}

else

{

tool = Tree[tool][path];

}

return pass[tool];

}

void word_clear()

{

memset(&Tree[0][0] , 0 , sizeof(int)*12*(cnt+1));

memset(&pass[0] , 0 , sizeof(int)*(cnt+1));

memset(&endd[0] , 0, sizeof(int)*(cnt+1));

cnt=1;

}

public:

// 求与 b[x] 一致的 a[y] 有几个 ===> 拿着 b[x] 去找 a[y]

vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a)

{

cnt=1;

// 答案：

ans.clear();

// 将 a 作为答案放入 Trie

for(const auto& e : a) // e 是 a[i]

{

word_insert(vec_to_str(e)); // 将 e 变成 word 再加入字典树

}

for(const auto& e : b) // e 是 b[i]

{

ans.push_back(word_find(vec_to_str(e))); // 在 a 中找 b 为前缀的单词

}

word_clear(); // 重置字典树

return ans;

}

};

“`

34:35

以上就是关于问题牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份。密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：密匙 b 的长度不超过密匙 a 的长度。对于任意 0 <= i < length(b)，有 b[i+1] – b[i] == a[i+1] – a[i]。现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组。请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙a。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训