Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.
Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.
Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Letztes Mal Leet Code Day 37 "105. Konstruieren Sie einen Binärbaum aus Vorbestellung und Inorder Traversal"
Im Moment löse ich das Medium mit den 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
208. Implement Trie (Prefix Tree) Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen.
Das Problem ist, dass Sie die Funktionen Einfügen, Suchen und Starten mit in einer Klasse namens Trie implementieren sollten.
Darüber hinaus, wie jedes Verhalten,
Trie trie = new Trie();
trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app");
trie.search("app"); // returns true
Es sieht aus wie das.
Grundsätzlich werden alle Argumente einmal mit der for-Anweisung überprüft. Wenn sie im ursprünglich gehaltenen element nicht vorhanden sind, wird False zurückgegeben oder{}zugewiesen.
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.element = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
inserted = self.element
for tmp in word:
if tmp not in inserted:
inserted[tmp] = {}
inserted = inserted[tmp]
inserted["-"] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
searched = self.element
for tmp in word:
if tmp not in searched:
return False
searched = searched[tmp]
return "-" in searched
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
started = self.element
for tmp in prefix:
if tmp not in started:
return False
started = started[tmp]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
# Runtime: 128 ms, faster than 94.63% of Python3 online submissions for Implement Trie (Prefix Tree).
# Memory Usage: 27.3 MB, less than 66.67% of Python3 online submissions for Implement Trie (Prefix Tree).
Es war schneller als ich erwartet hatte und ich konnte es gut umsetzen.
In Bezug auf die Diskussion war die andere wichtige Antwort
from collections import defaultdict
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.nodes = defaultdict(TrieNode) # Easy to insert new node.
self.isword = False # True for the end of the trie.
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curr = self.root
for char in word:
curr = curr.nodes[char]
curr.isword = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.root
for char in word:
if char not in curr.nodes:
return False
curr = curr.nodes[char]
return curr.isword
def startsWith(self, prefix):
"""
Returns if there is any word in the trie
that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
curr = self.root
for char in prefix:
if char not in curr.nodes:
return False
curr = curr.nodes[char]
return True
# Runtime: 192 ms, faster than 57.66% of Python3 online submissions for Implement Trie (Prefix Tree).
# Memory Usage: 32.5 MB, less than 7.41% of Python3 online submissions for Implement Trie (Prefix Tree).
Es war so. Sie haben eine separate Klasse mit dem Namen "TrieNode" erstellt und etwas namens defaultdict verwendet. In Bezug auf diese Zeit denke ich jedoch, dass die frühere Antwort leichter zu verstehen und schneller ist, daher denke ich, dass dies besser ist.
Diesmal sieht es so aus, danke für deine harte Arbeit.
Recommended Posts