Design a Phone Directory which supports the following operations:get: Provide a number which is not assigned to anyone.check: Check if a number is available or not.release: Recycle or release a number.Example:// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.PhoneDirectory directory = new PhoneDirectory(3);// It can return any available phone number. Here we assume it returns 0.directory.get();// Assume it returns 1.directory.get();// The number 2 is available, so return true.directory.check(2);// It returns 2, the only number that is left.directory.get();// The number 2 is no longer available, so return false.directory.check(2);// Release number 2 back to the pool.directory.release(2);// Number 2 is available again, return true.directory.check(2);
my HashSet+ ArrayList, 删除的时候把要删的index与末尾对调。get()其实不需要random, 因为anyone is ok
1 public class PhoneDirectory { 2 ArrayList<Integer> arr; 3 HashSet<Integer> set; 4 5 /** Initialize your data structure here 6 @param maxNumbers - The maximum numbers that can be stored in the phone directory. */ 7 public PhoneDirectory(int maxNumbers) { 8 arr = new ArrayList<Integer>(); 9 set = new HashSet<Integer>();10 for (int i=0; i<maxNumbers; i++) {11 arr.add(i);12 set.add(i);13 }14 }15 16 /** Provide a number which is not assigned to anyone.17 @return - Return an available number. Return -1 if none is available. */18 public int get() {19 if (arr.size() == 0) return -1;20 Random random = new Random();21 int index = random.nextInt(arr.size());22 int temp = arr.get(index);23 arr.set(index, arr.get(arr.size()-1));24 arr.set(arr.size()-1, temp);25 arr.remove(arr.size()-1);26 set.remove(temp);27 return temp;28 }29 30 /** Check if a number is available or not. */31 public boolean check(int number) {32 return set.contains(number);33 }34 35 /** Recycle or release a number. */36 public void release(int number) {37 if (!set.contains(number)) {38 arr.add(number);39 set.add(number);40 }41 }42 }43 44 /**45 * Your PhoneDirectory object will be instantiated and called as such:46 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);47 * int param_1 = obj.get();48 * boolean param_2 = obj.check(number);49 * obj.release(number);50 */
HashSet+ Queue网上vote最高的solution,
1 public class PhoneDirectory { 2 3 Set<Integer> used = new HashSet<Integer>(); 4 Queue<Integer> available = new LinkedList<Integer>(); 5 int max; 6 public PhoneDirectory(int maxNumbers) { 7 max = maxNumbers; 8 for (int i = 0; i < maxNumbers; i++) { 9 available.offer(i);10 }11 }12 13 public int get() {14 Integer ret = available.poll();15 if (ret == null) {16 return -1;17 }18 used.add(ret);19 return ret;20 }21 22 public boolean check(int number) {23 if (number >= max || number < 0) {24 return false;25 }26 return !used.contains(number);27 }28 29 public void release(int number) {30 if (used.remove(number)) {31 available.offer(number);32 }33 }34 }35 36 /**37 * Your PhoneDirectory object will be instantiated and called as such:38 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);39 * int param_1 = obj.get();40 * boolean param_2 = obj.check(number);41 * obj.release(number);42 */
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。