LeetCode（Linked List)705. Design HashSet

╰半夏微凉° 2023-09-24 20:10 15阅读 0赞

# 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  
> 2. 如果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);
     */