7-1 集合基础和基于二分搜索树的集合实现

public interface Set<E> {void add(E e);boolean contains(E e);void remove(E e);int getSize();boolean isEmpty();
}

利用上一章实现的二分搜索树

public class BSTSet<E extends Comparable<E>> implements Set<E> {private BST<E> bst;public BSTSet(){bst = new BST<>();}@Overridepublic int getSize(){return bst.size();}@Overridepublic boolean isEmpty(){return bst.isEmpty();}@Overridepublic void add(E e){bst.add(e);}@Overridepublic boolean contains(E e){return bst.contains(e);}@Overridepublic void remove(E e){bst.remove(e);}
}

7-2 基于链表的集合实现

import java.util.ArrayList;public class LinkedListSet<E> implements Set<E> {private LinkedList<E> list;public LinkedListSet(){list = new LinkedList<>();}@Overridepublic int getSize(){return list.getSize();}@Overridepublic boolean isEmpty(){return list.isEmpty();}@Overridepublic void add(E e){if(!list.contains(e))list.addFirst(e);}@Overridepublic boolean contains(E e){return list.contains(e);}@Overridepublic void remove(E e){list.removeElement(e);}
}

7-3 集合类的复杂度分析

7-4 LeetCode中的集合问题

LeetCode 804

import java.util.TreeSet;public class Solution {public int uniqueMorseRepresentations(String[] words) {String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};TreeSet<String> set = new TreeSet<>();for(String word: words){StringBuilder res = new StringBuilder();for(int i = 0 ; i < word.length() ; i ++)res.append(codes[word.charAt(i) - 'a']);set.add(res.toString());}return set.size();}
}

7-5 映射基础

public interface Map<K, V> {void add(K key, V value);V remove(K key);boolean contains(K key);V get(K key);void set(K key, V newValue);int getSize();boolean isEmpty();
}

7-6 基于链表的映射实现

import java.util.ArrayList;public class LinkedListMap<K, V> implements Map<K, V> {private class Node{public K key;public V value;public Node next;public Node(K key, V value, Node next){this.key = key;this.value = value;this.next = next;}public Node(K key, V value){this(key, value, null);}public Node(){this(null, null, null);}@Overridepublic String toString(){return key.toString() + " : " + value.toString();}}private Node dummyHead;private int size;public LinkedListMap(){dummyHead = new Node();size = 0;}@Overridepublic int getSize(){return size;}@Overridepublic boolean isEmpty(){return size == 0;}private Node getNode(K key){Node cur = dummyHead.next;while(cur != null){if(cur.key.equals(key))return cur;cur = cur.next;}return null;}@Overridepublic boolean contains(K key){return getNode(key) != null;}@Overridepublic V get(K key){Node node = getNode(key);return node == null ? null : node.value;}@Overridepublic void add(K key, V value){Node node = getNode(key);if(node == null){dummyHead.next = new Node(key, value, dummyHead.next);size ++;}elsenode.value = value;}@Overridepublic void set(K key, V newValue){Node node = getNode(key);if(node == null)throw new IllegalArgumentException(key + " doesn't exist!");node.value = newValue;}@Overridepublic V remove(K key){Node prev = dummyHead;while(prev.next != null){if(prev.next.key.equals(key))break;prev = prev.next;}if(prev.next != null){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;return delNode.value;}return null;}
}

7-7 基于二分搜索树的映射实现

import java.util.ArrayList;public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {private class Node{public K key;public V value;public Node left, right;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;}}private Node root;private int size;public BSTMap(){root = null;size = 0;}@Overridepublic int getSize(){return size;}@Overridepublic boolean isEmpty(){return size == 0;}// 向二分搜索树中添加新的元素(key, value)@Overridepublic void add(K key, V value){root = add(root, key, value);}// 向以node为根的二分搜索树中插入元素(key, value)，递归算法// 返回插入新节点后二分搜索树的根private Node add(Node node, K key, V value){if(node == null){size ++;return new Node(key, value);}if(key.compareTo(node.key) < 0)node.left = add(node.left, key, value);else if(key.compareTo(node.key) > 0)node.right = add(node.right, key, value);else // key.compareTo(node.key) == 0node.value = value;return node;}// 返回以node为根节点的二分搜索树中，key所在的节点private Node getNode(Node node, K key){if(node == null)return null;if(key.equals(node.key))return node;else if(key.compareTo(node.key) < 0)return getNode(node.left, key);else // if(key.compareTo(node.key) > 0)return getNode(node.right, key);}@Overridepublic boolean contains(K key){return getNode(root, key) != null;}@Overridepublic V get(K key){Node node = getNode(root, key);return node == null ? null : node.value;}@Overridepublic void set(K key, V newValue){Node node = getNode(root, key);if(node == null)throw new IllegalArgumentException(key + " doesn't exist!");node.value = newValue;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left == null)return node;return minimum(node.left);}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}// 从二分搜索树中删除键为key的节点@Overridepublic V remove(K key){Node node = getNode(root, key);if(node != null){root = remove(root, key);return node.value;}return null;}private Node remove(Node node, K key){if( node == null )return null;if( key.compareTo(node.key) < 0 ){node.left = remove(node.left , key);return node;}else if(key.compareTo(node.key) > 0 ){node.right = remove(node.right, key);return node;}else{   // key.compareTo(node.key) == 0// 待删除节点左子树为空的情况if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 待删除节点右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 待删除节点左右子树均不为空的情况// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置Node successor = minimum(node.right);successor.right = removeMin(node.right);successor.left = node.left;node.left = node.right = null;return successor;}}
}

7-8 映射的复杂度分析

7-9 LeetCode上更多集合和映射的问题

349. 两个数组的交集

import java.util.ArrayList;
import java.util.TreeSet;class Solution349 {public int[] intersection(int[] nums1, int[] nums2) {TreeSet<Integer> set = new TreeSet<>();for(int num: nums1)set.add(num);ArrayList<Integer> list = new ArrayList<>();for(int num: nums2){if(set.contains(num)){list.add(num);set.remove(num);}}int[] res = new int[list.size()];for(int i = 0 ; i < list.size() ; i ++)res[i] = list.get(i);return res;}
}

350. 两个数组的交集 II

import java.util.ArrayList;
import java.util.TreeMap;public class Solution350 {public int[] intersect(int[] nums1, int[] nums2) {TreeMap<Integer, Integer> map = new TreeMap<>();for(int num: nums1){if(!map.containsKey(num))map.put(num, 1);elsemap.put(num, map.get(num) + 1);}ArrayList<Integer> res = new ArrayList<>();for(int num: nums2){if(map.containsKey(num)){res.add(num);map.put(num, map.get(num) - 1);if(map.get(num) == 0)map.remove(num);}}int[] ret = new int[res.size()];for(int i = 0 ; i < res.size() ; i ++)ret[i] = res.get(i);return ret;}
}