Created
October 25, 2015 00:26
-
-
Save gcrfelix/b84e173c83d4f79068a4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
题目: | |
设计一个电话本系统,实现三个功能: | |
查找号码 boolean isTaken(), | |
添加号码 void takeNumber(), | |
返回一个不在电话本里的没人用的号码 number giveMeANumber()。 | |
用的是Trie and boolean array, 不用Hashmap是因为 map的initial size是256,对于这种只需要存0-9十个数的情况就很不划算了 | |
用trie只需要存每层0-9十个boolean,如果这个数已用就把相应的index set一下 | |
用boolean array更省地方,arrays of booleans use 1 byte per element | |
Search Time Complexity: O(length of phone number) | |
Insert Time Complexity: O(length of phone number) | |
public class Numbers{ | |
Node root; | |
public Numbers(){ | |
root=new Node(); | |
} | |
} | |
class Node{ | |
boolean[] children; | |
public Node(){ | |
children=new boolean[10]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment