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

天津做网站的semi final

天津做网站的,semi final,上饶网站优化,做网站的品牌公司Day 67 题目描述 思路 初次思路:此时还不了解什么是前缀树,尝试自己实现一下 由于我们需要快速定位前缀和字符串,于是我想到了使用hashset实现,tes用于存放字符串,prefixs存放前缀,获取前缀通过使用subst…

Day 67

题目描述

在这里插入图片描述

思路

初次思路:此时还不了解什么是前缀树,尝试自己实现一下
由于我们需要快速定位前缀和字符串,于是我想到了使用hashset实现,tes用于存放字符串,prefixs存放前缀,获取前缀通过使用substring进行拆分。

class Trie {Set<String>tes;Set<String>prefixs;public Trie() {tes=new HashSet<String>();prefixs=new HashSet<String>();num=new ArrayList<String>();}public void insert(String word) {if(tes.contains(word)){return;}else{tes.add(word);for(int i=0;i<=word.length();i++){String a=word.substring(0,i);prefixs.add(a);}}}public boolean search(String word) {return tes.contains(word);}public boolean startsWith(String prefix) {return prefixs.contains(prefix);}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

学习前缀树后
前缀树的作用在于快速检索字符串的前缀,插入一个字符串,即为从根一次插入孩子节点,将字符串最后一个字符对应的节点标记结束节点,再插入另外一个相同前缀但最后n个字符不一样的字符串,那么在相同前缀的部分,不需要插入新的节点,直到第一个不同的字符,添加一个新的子节点。
这样做的好处,我们如果要获取两个字符串的前缀,只需要从根节点向下遍历,比较两个字符串,只要到某个节点出现了分支,则这个节点之前的节点就是两个字符的公共前缀。同时节约了存储空间
做法如下:

class Trie {public Trie[]child;//孩子节点,可能插入的是26个英文字母中的一个public boolean isend;//判断是否为一个字符串的结束 区分前缀和字符串public Trie() {child=new Trie[26];isend=false;}public void insert(String word) {Trie node=this;//根节点for(int i=0;i<word.length();i++){char a=word.charAt(i);int index=a-'a';//转化为序号if(node.child[index]==null){node.child[index]=new Trie();//创建为新孩子}node=node.child[index];//移动到下一个孩子}node.isend=true;//将结束标志置为true}public boolean search(String word) {Trie node=searchPrefix(word);if(node!=null&&node.isend){return true;}return false;}public boolean startsWith(String prefix) {Trie node=searchPrefix(prefix);if(node!=null){return true;}return false;}public Trie searchPrefix(String prefix){Trie node=this;for(int i=0;i<prefix.length();i++){char a=prefix.charAt(i);int index=a-'a';if(node.child[index]==null){//还没遍历完前缀就结束了 说明找不到return null;}node=node.child[index];}return node;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/
http://www.mmbaike.com/news/108283.html

相关文章:

  • 阿里云学生认证免费服务器seo网络排名优化
  • 厦门建站网址费用百度网盘客服人工电话95188
  • wordpress.com杭州seo营销公司
  • 网站设计与建设第一章如何做网络营销?
  • 域名访问宁波seo外包方案
  • 做vi的网站专业搜索引擎seo公司
  • 第一次做ppt怎么弄seo关键词的选择步骤
  • 济南网站建设工作在线咨询 1 网站宣传
  • 专业零基础网站建设教学服务上海高端seo公司
  • 可以做数据图的的网站有哪些百度推广怎么才能效果好
  • 免费wordpress简洁博客模板佛山seo技术
  • 移动网站建设商网络seo是什么工作
  • 2017网站制作报价单杭州产品推广服务公司
  • 家居企业网站建设新闻软文广告经典案例短的
  • 本溪 网站建设 做网站八百客crm系统登录入口
  • 江西赣州市北京seo不到首页不扣费
  • 武汉站建设太原seo网站优化
  • 安康网站开发公司价格网络营销推广流程
  • 谁有网站推荐一下好产品怎么做推广和宣传
  • dw做的网页在网站图片不显示沈阳高端关键词优化
  • 广州做外贸网站公司百度推广退款电话
  • 利用图床做网站网站优化排名软件推广
  • 中央人民政府网网址免费下载百度seo
  • 网站服务器查找企业网站制作需要多少钱
  • 做暧小视频免费网站站长工具网址是多少
  • 哪家做网站靠谱湖北百度推广公司
  • 密云重庆网站建设下载百度app最新版
  • 盱眙县住房和城乡建设局网站培训心得体会范文大全1000
  • app网站开发成本关键词三年级
  • 中国空间站完整图今日重大财经新闻