国内网站开发 框架,褚明宇wordpress,网络设计毕业设计,数据中台建设心路历程#xff1a;
一道题干进去了一个下午#xff0c;单纯从解题角度可以直接用python的集合就很简单地解决#xff08;不知道是不是因为python底层的set()类#xff09;。后来从网上看到这道题应该从前缀树的角度去做#xff0c;于是花了半个多小时基于字典做了前缀树…
心路历程
一道题干进去了一个下午单纯从解题角度可以直接用python的集合就很简单地解决不知道是不是因为python底层的set()类。后来从网上看到这道题应该从前缀树的角度去做于是花了半个多小时基于字典做了前缀树的做法后来想锻炼一下多叉树的做法又花了一个多小时尝试。 前缀的含义是一个字符串的包含第一个元素作为开始的子序列在代码自动补全里应用很多。
注意的点
1、在利用字典建立多叉树的时候一般是利用循环不变量的原则每一层赋值root然后判断当前层是否已经之前创建过。 2、利用class建立多叉树的时候注意不要在初始化默认参数处设置children[]否则所有示例化对象的children都指向同一个内存花了很长时间找这个bug。 3、注意在一个单词添加完之后结尾要跟上一个结束判断符来区分到底是一个完整的单词还是一个其他长单词的一个部分。 4、写出来bug是很正常的事情只要按照顺序检查输入输出关系即可debug。
解法一python原生集合
class Trie:def __init__(self):self.set set()self.prefixset set()def insert(self, word: str) - None:self.set.add(word)for j in range(1, len(word)1): # 这块是取不到的所以要加一两个取不到的叠加self.prefixset.add(word[:j])def search(self, word: str) - bool:if word in self.set:return Trueelse:return Falsedef startsWith(self, prefix: str) - bool:# return True 直接return true可以过一半测试用例if prefix in self.prefixset:return Trueelse:return False解法二用字典实现多叉前缀树
class Trie:def __init__(self): # 用字典做一个前缀树self.dict {}self.end !def insert(self, word: str) - None:root self.dictfor i in range(len(word)):if word[i] not in root.keys():root[word[i]] {} # 循环不变量root root[word[i]]root[self.end] Nonedef search(self, word: str) - bool:# print(self.dict)root self.dictfor c in word:if c in root.keys():root root[c]else:return False# 还得保证单词结尾if self.end in root.keys():return Trueelse:return Falsedef startsWith(self, prefix: str) - bool:root self.dictfor c in prefix:if c in root.keys():root root[c]else:return Falsereturn True 解法三利用多叉树类实现前缀树对比起来还是用字典实现多叉树方便一些
class TreeNode:def __init__(self, valNone): # 不能在这里给children[]赋值然后再self.children children否则所有实例都维护一个列表内存浅拷贝问题self.val valself.children [] # !!!def values(self):values []for eve in self.children:values.append(eve.val)return valuesdef findvalindex(self, aval):for i in range(len(self.children)):if self.children[i].val aval:return iassert Falseclass Trie:def __init__(self): # 用多叉树作前缀树self.root TreeNode()def insert(self, word: str) - None:root self.rootfor i in range(len(word)):if word[i] not in root.values():node TreeNode(word[i])root.children.append(node)root node # 这句话无法赋值有赋值作用并且内存也确实变了但是不知道为什么.values()方法都赋值到了根节点上去-》因为浅拷贝到了一个列表上# print(root, root.children[-1])else:vindex root.findvalindex(word[i])root root.children[vindex]leaf TreeNode(!)root.children.append(leaf) # 加入结束符号def search(self, word: str) - bool:root self.rootfor c in word:if c in root.values():vindex root.findvalindex(c)root root.children[vindex]else:return False# print(root.values())# 此时root的children中应该包含leafif ! in root.values():return Trueelse:return Falsedef startsWith(self, prefix: str) - bool:root self.rootfor c in prefix:if c in root.values():vindex root.findvalindex(c)root root.children[vindex]else:return Falsereturn True # 不需要是none
