LeetCode(30) -- 704, 705, 706

P704. Binary Search (Easy)

我的代码

public class E_704_BinarySearch {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
}

100%

答案

class Solution {
  public int search(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
}

P705. Design HashSet (Easy)

自己实现一个HashSet

我的代码

public class E_705_DesignHashSet {
    /** Initialize your data structure here. */

    private static final Integer INITIAL_CAPACITY = 10001;

    private int capacity;

    private ArrayList<Integer>[] table;

    private int size;

    public E_705_DesignHashSet() {
        this.size = 0;
        this.table = (ArrayList<Integer>[]) new ArrayList[INITIAL_CAPACITY];
        this.capacity = INITIAL_CAPACITY;
    }

    public void add(int key) {
        int index = key % capacity;
        ArrayList<Integer> list = table[index];
        if (list == null) {
            table[index] = new ArrayList<>();
            table[index].add(key);
            size++;
        } else if (list.indexOf(key) == -1) {
            list.add(key);
            size++;
        }
//        if (size > capacity / 2) {
//            resize(2 * capacity - 1);
//        }
    }

    public void remove(int key) {
        int index = key % capacity;
        ArrayList<Integer> list = table[index];
        if (list != null) {
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) == key) {
                    list.remove(i);
                    return;
                }
            }
        }
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int index = key % capacity;
        return table[index] != null && table[index].contains(key);
    }

    private void resize(int newCapacity) {
        ArrayList<Integer> buffer = new ArrayList<>(size);
        for (int i = 0; i < table.length; i++) {
            ArrayList<Integer> list = table[i];
            buffer.addAll(list);
        }
        this.table = (ArrayList<Integer>[]) new ArrayList[newCapacity];
        for (Integer integer : buffer) {
            add(integer);
        }
    }
}

resize()方法有bug，懒得找了，弃用了。

P706. Design HashMap (Easy)

自己实现HashMap

我的代码

public class E_706_DesignHashMap {
    class MapEntry {
        private int key;
        private int value;

        public MapEntry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;

    private ArrayList<MapEntry>[] table;

    /** Initialize your data structure here. */
    public E_706_DesignHashMap() {
        capacity = 1009;
        table = (ArrayList<MapEntry>[]) new ArrayList[1009];
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = key % capacity;
        ArrayList<MapEntry> list = table[index];
        if (list == null) {
            table[index] = new ArrayList<>();
            table[index].add(new MapEntry(key, value));
        } else {
            for (MapEntry mapEntry : list) {
                if (mapEntry.key == key) {
                    mapEntry.value = value;
                    return;
                }
            }
            list.add(new MapEntry(key, value));
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int index = key % capacity;
        ArrayList<MapEntry> list = table[index];
        if (list == null) {
            return -1;
        }
        for (MapEntry mapEntry : list) {
            if (mapEntry.key == key) {
                return mapEntry.value;
            }
        }
        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int index = key % capacity;
        ArrayList<MapEntry> list = table[index];
        if (list != null) {
            for (MapEntry mapEntry : list) {
                if (mapEntry.key == key) {
                    list.remove(mapEntry);
                    if (list.size() == 0) {
                        table[index] = null;
                    }
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        E_706_DesignHashMap obj = new E_706_DesignHashMap();
        obj.put(1,1);
        obj.put(2,2);
        obj.get(1);
        obj.get(3);
        obj.put(2,1);
        obj.get(2);
        obj.remove(2);
        obj.get(2);
    }
}