网站搜索推广销售代运营公司怎么找客户

当前位置： 首页 > news >正文

网站搜索推广销售,代运营公司怎么找客户,邢台是哪个省的城市,团购模板网站前言 前缀树#xff0c;又称字典树#xff0c;Trie树#xff0c;是一种方便查找前缀信息的数据结构。 一、字典树的实现 1.类描述实现 #include bits/stdc.h using namespace std;class TrieNode { public:int pass0;int end0;TrieNode* nexts[26]{NULL}; };Tri…前言 前缀树又称字典树Trie树是一种方便查找前缀信息的数据结构。 一、字典树的实现 1.类描述实现 #include bits/stdc.h using namespace std;class TrieNode { public:int pass0;int end0;TrieNode* nexts[26]{NULL}; };TrieNode* rootNULL;void insert(string word) {TrieNode* noderoot;node-pass;for(int i0,path;iword.length();i){pathword[i]-a;if(node-nexts[path]NULL){node-nexts[path]new TrieNode();}nodenode-nexts[path];node-pass;}node-end; }int search(string word) {TrieNode* noderoot;for(int i0,path;iword.length();i){pathword[i]-a;if(node-nexts[path]NULL){return 0;}nodenode-nexts[path];}return node-end; }int prefixNumber(string word) {TrieNode* noderoot;for(int i0,path;iword.length();i){pathword[i]-a;if(node-nexts[path]NULL){return 0;}nodenode-nexts[path];}return node-pass; }void deleteWord(string word) {if(search(word)0){TrieNode* noderoot;node-pass–;for(int i0,path;iword.length();i){pathword[i]-a;if(–node-nexts[path]-pass0){node-nexts[path]NULL;return ;}nodenode-nexts[path];}node-end–;} }int main() {int m;cinm;rootnew TrieNode();int op;string word;for(int i0;im;i){cinop;cinword;if(op1){insert(word);}else if(op2){deleteWord(word);}else if(op3){cout(search(word)?YES:NO)endl;}else if(op4){coutprefixNumber(word)endl;;}} } 类描述的方法不推荐重点是静态数组的实现方法。 2.静态数组实现 #include bits/stdc.h using namespace std;const int MAXN150001;int trie[MAXN][26]; int treePass[MAXN]{0}; int treeEnd[MAXN]{0}; int cnt1;//节点数void insert(string word) {int cur1;//节点编号treePass[cur];for(int i0,path;iword.length();i){pathword[i]-a;if(trie[cur][path]0){trie[cur][path]cnt;}curtrie[cur][path];treePass[cur];}treeEnd[cur]; }int search(string word) {int cur1;for(int i0,path;iword.length();i){pathword[i]-a;if(trie[cur][path]0){return 0;}curtrie[cur][path];}return treeEnd[cur]; }int prefixNumber(string word) {int cur1;for(int i0,path;iword.length();i){pathword[i]-a;if(trie[cur][path]0){return 0;}curtrie[cur][path];}return treePass[cur]; }void deleteWord(string word) {if(search(word)0){int cur1;treePass[cur]–;for(int i0,path;iword.length();i){pathword[i]-a;if(–treePass[ trie[cur][path] ]0){trie[cur][path]0;return ;}curtrie[cur][path];}treeEnd[cur]–;} }int main() {int m;cinm;int op;string word;for(int i0;im;i){cinop;cinword;if(op1){insert(word);}else if(op2){deleteWord(word);}else if(op3){cout(search(word)?YES:NO)endl;}else if(op4){coutprefixNumber(word)endl;;}} } 首先说明前缀树的原理每个节点有pass和end两个信息同时还有指向下一个节点的指针节点与节点间的路径表示每个字符。所以在树往下扎到底的过程中沿途路径经过的字符就组成了一个字符串其中pass的数值表示的是有几个字符串经过这个节点end表示的是有几个字符串在这个节点结束。如“aab”和“abc”二者首先经过公共节点“a”然后出现分支“a”和“b”所以第一个“a”的pass2第二个“a”的pass1最后一个“b”的end1第二个“b”的pass1end0。 首先设置全局变量trie数组的一维表示节点的编号二维表示每条分支去往的下个节点的编号。因为字母只有26个所以准备26大小即可。之后设置cnt为节点个数从1开始。 函数部分首先是insert函数用来插入字符串。首先cur表示当前节点的编号开始为1然后先让pass。之后遍历word字符串每次取出当前字符作为path若trie[cur][path]0即没有后续节点那就让其等于cnt建出节点。之后让cur跳到下个节点然后pass。最后让end。 之后是search函数用来搜索字符串个数。基本思路和insert差不多只是若trie等于0即没有后续节点说明不存在这个字符串就返回0否则最后返回end即字符串数量。 重点是prefixNumber函数用来搜索以某个字符串为前缀的串。思路和search差不多主要区别是最后返回的是pass即前缀数量。 最后是delete函数用来删除字符串。思路就是反向的insert每次让pass-1。注意此时的判断若下一个节点的pass-1后等于0即后续节点被删没了直接让trie等于0后结束即可。 二、前缀树相关题目 1.接头密匙 class Solution { public:#define MAXN 100int trie[MAXN][12];int pass[MAXN]{0};int end[MAXN]{0};int cnt1;void insert(string word){int cur1;pass[cur];for(int i0,path;iword.length();i){pathword[i]-?10:(word[i]#?11:word[i]-0);if(trie[cur][path]0){trie[cur][path]cnt;}curtrie[cur][path];pass[cur];}end[cur];}int prefixNumber(string word){int cur1;for(int i0,path;iword.length();i){pathword[i]-?10:(word[i]#?11:word[i]-0);if(trie[cur][path]0){return 0;}curtrie[cur][path];}return pass[cur];}vectorint countConsistentKeys(vectorvectorint b, vectorvectorint a){for(int i0;ia.size();i){string cur;for(int j1;ja[i].size();j){cura[i][j]-a[i][j-1]0;cur#;}insert(cur);}vectorintans(b.size(),0);for(int i0;ib.size();i){string word;for(int j1;jb[i].size();j){wordb[i][j]-b[i][j-1]0;word#;}ans[i]prefixNumber(word);} return ans;} }; 这个题的重点是你得看出来这个情境是求前缀。捂脸 之后转化一下把数组里每个数的差变成字符串两个数之间用“#”间隔加上负号trie一共开12大小即可。之后先把a数组insert进去再根据b数组一个一个找就行。 2.数组中两个数的最大异或值 class Solution { public:#define MAXN 3000001int trie[MAXN][2];int cnt1;int high;void insert(int n){int cur1;for(int ihigh,status;i0;i–){status1(ni);if(trie[cur][status]0){trie[cur][status]cnt;}curtrie[cur][status];}}int maxXOR(int n){int ans0;int cur1;for(int ihigh,status,want;i0;i–){status1(ni);wantstatus^1;if(trie[cur][want]0){want^1;}ans|(status^want)i;curtrie[cur][want];}return ans;}int findMaximumXOR(vectorint nums) {int mxINT_MIN;for(int i0;inums.size();i){mxmax(mx,nums[i]);}//找最大值的前导1的位置for(int i31;i0;i–){if( (mx(1i) )!0){highi;break;}}for(int i0;inums.size();i){insert(nums[i]);}int ans0;for(int i0;inums.size();i){ansmax(ans,maxXOR(nums[i]));}return ans;} }; 这个题就需要一点思考了。首先思考要达成异或和最大最好的办法肯定是选二进制中第一个1最靠前的数即最大的数。之后要想异或和最大理想情况就是找每一位都与最大的数不同的数这样异或起来每一位就都是1了。 所以首先把最大值抓出来接着为了加速可以把最大值的前导1的数位取出来这样后续从这个位置开始找即可不需要从31位开始。再把每个数的二进制形式insert进去由于只有0和1两种状态所以trie的大小为2即可。 重点就是maxXOR函数首先每次让status为n第i位上的状态。注意这里由于trie只有0和1两条分支所以选择让ni的方法。然后最优选择肯定是找status不同的状态所以wantstatus^1若没有找到就再^1回到原状态。最后把这一位的异或结果或进ans里即可。 这个题说实话还是有点难度的。 3.单词搜索 II class Solution { public:#define MAXN 10001int trie[MAXN][26];int pass[MAXN]{0};string end[MAXN];int cnt1;void insert(string word){int cur1;pass[cur];for(int i0,path;iword.length();i){pathword[i]-a;if(trie[cur][path]0){trie[cur][path]cnt;}curtrie[cur][path];pass[cur];}end[cur]word;}int prefix(string word){int cur1;for(int i0,path;iword.length();i){pathword[i]-a;if(trie[cur][path]0){return 0;}curtrie[cur][path];}return pass[cur];}//返回值为找到的字符串个数int dfs(vectorvectorcharboard,int i,int j,int t,vectorstringans){if(i0||iboard.size()||j0||jboard[0].size()||board[i][j]0){return 0;}int tmpboard[i][j];int pathtmp-a;ttrie[t][path];if(pass[t]0||t0)//找过了或没有{return 0;}int num0;if(end[t]!)//找到一个{num;ans.push_back(end[t]);end[t];}board[i][j]0;numdfs(board,i1,j,t,ans);numdfs(board,i-1,j,t,ans);numdfs(board,i,j1,t,ans);numdfs(board,i,j-1,t,ans);pass[t]-num;//找完一个就删除board[i][j]tmp;return num;}vectorstring findWords(vectorvectorchar board, vectorstring words) {vectorstringans;for(int i0;iwords.size();i){insert(words[i]);}for(int i0;iboard.size();i){for(int j0;jboard[i].size();j){dfs(board,i,j,1,ans);}}return ans;} }; 这个题就更是群贤毕至不仅有前缀树还有带路径的递归和还原现场。 前缀树在这个题的作用就是剪枝而且有三次剪枝。首先通过前缀树可以让每次递归去往的都是有效的格子。其次这里让end数组直接存放整个字符串可以方便递归结束时直接收集结果。最后每次在找完一个字符串后就把节点删除也可以减少不必要的搜索。 重点就是这个dfs函数首先若越界了或走到走过的格子就返回0。之后取当前格子上的字符和patht表示前缀树当前节点的编号所以让t去下一个节点若下一个节点找过了或者没有就返回0。然后若end有东西说明找到了就记录答案之后删除。接着分别去四个方向递归注意这里在回来时不仅要把格子还原还有让pass减去找到的数量即删去找过的字符串所以要让dfs函数带上返回值表示找到的字符串个数。 有一说一这个题确实难。 总结 前缀树还是很强的用好了能很大程度优化算法。 END