LeetCode（Linked List)705. Design HashSet

1.问题

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

void add(key) Inserts the value key into the HashSet.
bool contains(key) Returns whether the value key exists in the HashSet or not.
void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
Example 1:

Input
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // return False, (already removed)

Constraints:

0 <= key <= 106
At most 104 calls will be made to add, remove, and contains.

2. 解题思路

方法1：

1.定义arr为boolean的数组
2.arr的数组长度为1000000+1 （0 <= key <= 106）
3.添加，如果数组arr[key] = true
4.删除，如果数组arr[key] = false
5.如果此集合包含指定元素，则返回 true

方法2：

1.定义Node,head为null

如果head为null，head的值为key；判断添加的值是否在node里，如果不是添加
3.如果head为null，return；如果head.val==key，删除，head=head.next;否者遍历直到node的值和key值相等
4.如果head为null返回false，如果head的值等于key返回true；否则遍历直到node的值和key值相等返回true

3. 代码

代码1：

class MyHashSet {
boolean[] arr;//1.定义arr为boolean的数组
public MyHashSet() {
    arr = new boolean[1000000+1];//2.arr的数组长度为1000000+1 （0 <= key <= 106）
}
public void add(int key) {
    //3.添加，如果数组arr[key] = true
    arr[key] = true;
}
public void remove(int key) {
    //4.删除，如果数组arr[key] = false
    arr[key] = false;
}
public boolean contains(int key) {
    //5.如果此集合包含指定元素，则返回 true
    return arr[key];
 }
}

代码2：

class Node{
    Node next;
    int val;
    public Node(int key){
        this.val=key;
        this.next=null;
    }
}
class MyHashSet {
    Node head;
    public MyHashSet() {
    //1.定义Node,head为null
       head=null; 
    }
    public void add(int key) {
    //2. 如果head为null，head的值为key；判断添加的值是否在node里，如果不是添加
        if(head==null) 
        {
            head= new Node(key);
            return;
        }
        boolean doesExists=contains(key);
        if(!doesExists){
            Node temp=head;
            while(temp.next!=null)
                temp=temp.next;
            temp.next=new Node(key);
        }
    }
    public void remove(int key) {
    //3.如果head为null，return；如果head.val==key，删除，head=head.next;否者遍历直到node的值和key值相等
        if(head==null) return;
        if(head.val==key){
            head=head.next;
            return;
        }
        Node temp=head;
        while(temp.next!=null){
            if(temp.next.val==key) temp.next=temp.next.next;
            temp=temp.next;
        }
    }
    public boolean contains(int key) {
    //4.如果head为null返回false，如果head的值等于key返回true；否则遍历直到node的值和key值相等返回true
        if(head==null) return false;
        if(head.val==key) return true;
        Node temp=head;
        while(temp.next!=null){
            if(temp.next.val==key) return true;
            temp=temp.next;
        }
        return false;
    }
}
/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */