Design HashSet

class MyHashSet {
    private final int MAX_LEN = 100000; // the amount of buckets
    private List<Integer>[] set;      // hash set implemented by array
    
    /** Returns the corresponding bucket index. */
    private int getIndex(int key) {
        return key % MAX_LEN;
    }
    
    /** Search the key in a specific bucket. Returns -1 if the key does not existed. */
    private int getPos(int key, int index) {
        // Each bucket contains a list.
        List<Integer> temp = set[index];
        if (temp == null) {
            return -1;
        }
        // Iterate all the elements in the bucket to find the target key.
        for (int i = 0; i < temp.size(); ++i) {
            if (temp.get(i) == key) {
                return i;
            }
        }
        return -1;
    }
    
    /** Initialize your data structure here. */
    public MyHashSet() {
        set = (List<Integer>[])new ArrayList[MAX_LEN];
    }
    
    public void add(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            // Add new key if key does not exist.
            if (set[index] == null) {
                set[index] = new ArrayList<Integer>();
            }
            set[index].add(key);
        }
    }
    
    public void remove(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos >= 0) {
            // Remove the key if key exists.
            set[index].remove(pos);
        }
    }
    
    /** Returns true if this set did not already contain the specified element */
    public boolean contains(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        return pos >= 0;
    }
}

/**
 * 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);
 */

2022-11-22

Contains Duplicate

LeetCode Problem #217

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hs = new HashSet<>();
        for (int n:nums) {
            if (hs.contains(n)) {
                return true;
            }
            else {
                hs.add(n);
            }
        }
        return false;
    }  
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hs = new HashSet<>();
        for (int n:nums) {
            if (!hs.add(n)) {
                return true;
            }
        }
        return false;
    }
        
}

2022-10-03

Happy Number

LeetCode Problem #202

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> hs = new HashSet();
        while (n!=1) {
            int temp = 0;
            while (n != 0) {
                temp = temp + (int)Math.pow((n % 10),2);
                n = n / 10;
            }
            n = temp;
            if (hs.contains(n)) {
                return false;
            }
            else {
                hs.add(n);
            }
        }
        return true;
        
    }
}

2022-11-23

Longest Substring Without Repeating Characters

LeetCode Problem #3

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        // M1
        int size = s.length();
        int fast = 0;
        int slow = 0;
        int max = 0;
        Set<Character> hs = new HashSet<>();
        while (fast<size) {
            char c = s.charAt(fast);
            if (hs.contains(c)) {
                hs.clear();
                slow++;
                fast=slow;
            }
            else {
                hs.add(c);
                max = Math.max(max,hs.size());
                fast++;
            }
        }
        return max;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {

        // M2
        final int n = s.length();
        int len = 0;
        int [] repeat = new int[128];
        for (int c = 0, j = 0, i = 0; j < n; j++) {
            c = s.charAt(j);
            i = Math.max(repeat[c], i);
            len = Math.max(len, j - i +1);
            repeat[c] = j+1;
        }
        return len;
    }
}