Skip to content

Instantly share code, notes, and snippets.

@gcrfelix
Created October 25, 2015 00:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gcrfelix/b84e173c83d4f79068a4 to your computer and use it in GitHub Desktop.
Save gcrfelix/b84e173c83d4f79068a4 to your computer and use it in GitHub Desktop.
题目:
设计一个电话本系统,实现三个功能:
查找号码 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