接口
- 栈
package myjava;
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
- 队列
package myjava;
public interface Queue<E> {
int getSize();
boolean isEmpty();
E dequeue();
void enqueue(E e);
E getFront();
}
- 集合
package myjava;
public interface Set<E> {
void add(E e);
void remove(E e);
boolean contains(E e);
int getSize();
boolean isEmpty();
}
- 并查集
package myjava;
public interface UnionFind {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}
- 映射
package myjava;
public interface Map<K, V> {
void add(K key, V value); // 添加
void set(K key, V newValue); // 更新
V remove(K key); // 删除
V get(K key); // 得到为key 的值
boolean contains(K key); // 是否包含元素
boolean isEmpty(); // 是否空
int getSize(); // 元素个数
}
数组
// 数组
package myjava;
public class Array<E> {
private E[] data;
private int size;
public Array(int capacity) {
data = (E[])(new Object[capacity]);
size = 0;
}
public Array() {
this(10);
}
public Array(E[] arr) {
data = (E[])(new Object[arr.length]);
for (int i=0; i<arr.length; i++) {
data[i] = arr[i];
}
size = arr.length;
}
public int getSize() { // 当前元素个数
return size;
}
public int getCapacity() { // 容量
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void addLast(E val) {
add(size, val);
}
public void addFirst(E val) {
add(0, val);
}
public void add(int index, E val) { // 插入指定位置
if (size == data.length) {
resize(data.length*2);
}
if (index >= 0 && index <= size) {
for (int i=size-1; i>=index; i--) {
data[i+1] = data[i];
}
data[index] = val;
size++;
}
}
private void resize(int capacity) { // 动态扩容数组容量
E[] newData = (E[])new Object[capacity];
for (int i=0; i<size; i++) {
newData[i] = data[i];
}
data = newData;
}
public E get(int index) { // 查询指定位置元素 return{E}
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
return data[index];
}
// 更新某个位置的元素
// @param{int}index 索引
// @param{E}val 值
public void set(int index, E val) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
data[index] = val;
}
public boolean contains(E val) { // 是否包含某个元素
for (int i=0; i<size; i++) {
if (data[i] == val) {
return true;
}
}
return false;
}
public int find(E val) { // 查找元素的位置
for (int i=0; i<size; i++) {
if (data[i].equals(val)) {
return i;
}
}
return -1;
}
// 删除元素
// @param{int}index 索引
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
if (size == data.length / 2) { // 动态减少数组容量
resize(data.length/2);
}
E ret = data[index];
for (int i=index; i<size-1; i++) {
data[i] = data[i+1];
}
size--;
data[size] = null;
return ret;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size-1);
}
public boolean removeElement(E val) {
int index = find(val);
remove(index);
return index != -1 ? true : false;
}
public void swap(int i, int j) {
if (i < 0 || i>= size || j<0 || j>= size) {
throw new ArrayIndexOutOfBoundsException("index is illegal");
}
E e = data[i];
data[i] = data[j];
data[j] = e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size=%d, capacity=%d", size, data.length));
res.append("[");
for (int i=0; i<size; i++) {
res.append(data[i]);
if (i != size-1) {
res.append(",");
}
}
res.append("]");
return res.toString();
}
}
链表
package myjava;
public class LinkedList<E> {
private class Node<E> { // 链表节点
private E e;
private Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node dummyhead;// 虚拟头结点，方便插入动作
private int size;
public LinkedList(E e) {
dummyhead = new Node(null, null);
dummyhead.next = new Node(e);
size = 1;
}
public LinkedList() {
dummyhead = new Node(null, null);
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// 插入元素
// @param{int}index 位置
// @param{E}e 元素
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is invalid");
}
Node prev = dummyhead;
Node node = new Node(e);
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = new Node(e, prev.next);
size++;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public Node get(int index) { // 得到指定位置元素
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
Node cur = dummyhead.next;
for (int i=0; i<index; i++) {
cur = cur.next;
}
return cur;
}
public Node getFirst() {
return get(0);
}
public Node getLast() {
return get(size-1);
}
public void set(int index, E e) { // 更新指定位置的元素
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
Node cur = dummyhead.next;
for (int i=0; i<index; i++) {
cur = cur.next;
}
cur.e = e;
}
public boolean contains(E e) { // 是否包含某个元素
Node cur = dummyhead.next;
while(cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
public E removeElement(E e) {
Node prev = dummyhead;
while (prev != null) {
if (e.equals(prev.next.e)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
Node ret = prev.next;
prev.next = ret.next;
ret.next = null;
size--;
return (E)ret.e;
}
return null;
}
public E remove(int index) { // 删除
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is invalid");
}
Node prev = dummyhead;
for (int i=0; i<index; i++) {
prev = prev.next;
}
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
return (E) retNode.e;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size-1);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node current = dummyhead.next;
res.append("LikedList: ");
while (current != null) {
res.append(current);
current = current.next;
res.append("->");
}
res.append("NULL");
return res.toString();
}
}
栈
- 数组实现
package myjava;
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
public ArrayStack() {
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
public int getCapacity() {
return array.getCapacity();
}
public void push(E e) { // 入栈
array.addLast(e);
}
public E pop() { // 出栈
return array.removeLast();
}
public E peek() { // 栈顶元素 return{E}
return array.get(array.getSize()-1);
}
@Override
public String toString() {
int size = array.getSize();
StringBuilder res = new StringBuilder();
res.append("Stack: [");
for (int i=0; i<size; i++) {
res.append(array.get(i));
if (i != size-1) {
res.append(", ");
}
}
res.append("] >>");
return res.toString();
}
}
- 链表实现
package myjava;
public class LinkedListQueue<E> implements Queue<E> {
private class Node<E> {
private E e;
private Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head, tail;
private int size;
public LinkedListQueue() {
head = null;
tail = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(E e) {
if (tail == null) {
head = new Node(e);
tail = head;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
public E dequeue() {
if (isEmpty()) {
return null;
}
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null) {
tail = null;
}
size--;
return (E)retNode;
}
public E getFront() {
if (isEmpty()) { return null; }
return (E)head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node current = head;
res.append("Queue: Top ");
while (current != null) {
res.append(current);
current = current.next;
res.append("->");
}
res.append("NULL");
return res.toString();
}
}
队列
- 数组实现
package myjava;
public class ArrayQueue<E> implements Queue<E> {
Array<E> array;
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
public ArrayQueue() {
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void enqueue(E e) { // 进队
array.addLast(e);
}
@Override
public E dequeue() { // 出队 return{E}
return array.removeFirst();
}
@Override
public E getFront() {
return array.get(0);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
int size = array.getSize();
res.append("Queue: << [");
for (int i=0; i<size; i++) {
res.append(array.get(i));
if (i != size-1) {
res.append(", ");
}
}
res.append("] <<");
return res.toString();
}
}
- 链表实现
package myjava;
public class LinkedListQueue<E> implements Queue<E> {
private class Node<E> {
private E e;
private Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head, tail;
private int size;
public LinkedListQueue() {
head = null;
tail = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(E e) {
if (tail == null) {
head = new Node(e);
tail = head;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
public E dequeue() {
if (isEmpty()) {
return null;
}
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null) {
tail = null;
}
size--;
return (E)retNode;
}
public E getFront() {
if (isEmpty()) { return null; }
return (E)head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node current = head;
res.append("Queue: Top ");
while (current != null) {
res.append(current);
current = current.next;
res.append("->");
}
res.append("NULL");
return res.toString();
}
}
二分搜索树
package myjava;
import java.util.Queue;
import java.util.LinkedList;
public class BST<E extends Comparable<E>> {
private class Node {
public E e;
public Node left, right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
root = add(root, e);
}
}
private Node add(Node node, E e) { // 添加
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
return node;
}
public boolean contains(E e) { // 是否包含
return contains(root, e);
}
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}
public void preOrder() { // 前序遍历
preOrder(root);
}
private void preOrder(Node node) {
if (node == null) {return ;}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
public void inOrder() {// 中序遍历
inOrder(root);
}
private void inOrder(Node node) {
if (node == null) {return ;}
preOrder(node.left);
System.out.println(node.e);
preOrder(node.right);
}
public void postOrder() { // 后序遍历
postOrder(root);
}
private void postOrder(Node node) {
if (node == null) {return ;}
preOrder(node.left);
preOrder(node.right);
System.out.println(node.e);
}
public void levelOrder() { // 层次遍历
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
public Node minimum() { // 得到最小值
if (root == null) {return null;}
return minimum(root);
}
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
public Node maxmum() { // 得到最大值
if (root == null) {return null;}
return maxmum(root);
}
private Node maxmum(Node node) {
if (node.right == null) {
return node;
}
return maxmum(node.right);
}
public Node removeMin() {
Node cur = minimum();
root = removeMin(root);
return cur;
}
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;
}
public Node removeMax() {
Node cur = maxmum();
root = removeMax(root);
return cur;
}
private Node removeMax(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
public void remove(E e) {
root = remove(root, e);
}
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else { // 匹配到
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;
return successor;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
private void generateBSTString(Node node, int depth, StringBuilder res) {
if (node == null) {
res.append(generateDepthString(depth)+"nlll\n");
return ;
}
res.append(generateDepthString(depth)+node.e+"\n");
generateBSTString(node.left, depth+1, res);
generateBSTString(node.right, depth+1, res);
}
private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i=0; i<depth; i++) {
res.append("--");
}
return res.toString();
}
}
集合
- 二分搜索树实现
package myjava;
public class BSTSet<E extends Comparable<E>> implements Set<E> {
private BST<E> bst;
public BSTSet() {
bst = new BST<>();
}
@Override
public void add(E e) {
bst.add(e);
}
@Override
public void remove(E e) {
bst.remove(e);
}
@Override
public boolean contains(E e) {
return bst.contains(e);
}
@Override
public int getSize() {
return bst.getSize();
}
@Override
public boolean isEmpty() {
return bst.isEmpty();
}
}
- 链表实现
package myjava;
public class LinkedListSet<E extends Comparable<E>> implements Set<E> {
private LinkedList<E> list;
LinkedListSet() {
list = new LinkedList<>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public boolean contains(E e) {
return list.contains(e);
}
@Override
public void add(E e) {
if (!list.contains(e)) {
list.addFirst(e);
}
}
@Override
public void remove(E e) {
list.removeElement(e);
}
}
映射
- 二分搜索树实现
package myjava;
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() {
this.root = null;
this.size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void add(K key, V value) {
if (root == null) {
root = new Node(key, value);
size++;
} else {
root = add(root, 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 {
node.value = value;
}
return node;
}
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) == 0) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else { // >0
return getNode(node.right, key);
}
}
@Override
public boolean contains(K key) {
Node node = getNode(root, key);
return node != null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node != null ? node.value : null;
}
@Override
public void set(K key, V value) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key+"doesn't exit!");
}
node.value = value;
}
@Override
public 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 { // 匹配到
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;
return successor;
}
}
public Node minimum() { // 得到最小值
if (root == null) {return null;}
return minimum(root);
}
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
public Node removeMin() {
Node cur = minimum();
root = removeMin(root);
return cur;
}
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;
}
}
- 链表实现
package myjava;
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) {
this(key, null, null);
}
public Node() {
this(null, null, null);
}
}
private Node dummyhead;
private int size;
public LinkedListMap() {
this.dummyhead = new Node();
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public 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;
}
@Override
public boolean contains(K key) {
return getNode(key) != null;
}
@Override
public V get(K key) {
Node node = getNode(key);
return node != null ? node.value : null;
}
@Override
public void add(K key, V value) {
Node node = getNode(key);
if (node == null) {
dummyhead.next = new Node(key, value, dummyhead.next);
} else {
node.value = value;
}
}
@Override
public void set(K key, V value) {
Node node = getNode(key);
if (node == null) {
throw new IllegalArgumentException(key+"doesn't exit!");
}
node.value = value;
}
@Override
public V remove(K key) {
Node prev = dummyhead;
while (prev != null) {
if (key.equals(prev.next.key)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
Node ret = prev.next;
prev.next = ret.next;
ret.next = null;
size--;
return ret.value;
}
return null;
}
}
最大堆
package myjava;
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
public MaxHeap() {
data = new Array<>();
}
public MaxHeap(E[] arr) {
data = new Array<>(arr);
for (int i=parent(arr.length-1); i>=0; i--) {
shiftDown(i);
}
}
public int getSize() {
return data.getSize();
}
public boolean isEmpty() {
return data.isEmpty();
}
private int parent(int index) { // 得到父节点的索引
if (index == 0) {
throw new ArrayIndexOutOfBoundsException("index-0 doesn't parent");
}
return (index-1)/2;
}
private int leftChild(int index) { // 返回左孩子索引
return index*2+1;
}
private int rightChild(int index) { // 返回右孩子索引
return index*2+2;
}
public void add(E e) {
data.addLast(e);
shiftUp(getSize()-1);
}
private void shiftUp(int k) {
while (k>0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
data.swap(k, parent(k));
k=parent(k);
}
}
public E findMax() {
if (data.getSize() == 0) {
throw new UnsupportedOperationException("heap is empty");
}
return data.get(0);
}
public E extractMax() {
E ret = findMax();
data.swap(0, data.getSize()-1);
data.removeLast();
shiftDown(0);
return ret;
}
private void shiftDown(int k) {
int size = data.getSize();
while (leftChild(k) < size) {
int j = leftChild(k);
if (j+1 < size && data.get(j+1).compareTo(data.get(j))>0) {
j = rightChild(k);
}
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
data.swap(k, j);
k = j;
}
}
public E replace(E e) { // 返回最大元素并放入一个新元素
E ret = findMax();
data.set(0, e);
shiftDown(0);
return ret;
}
}
优先队列
package myjava;
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap maxHeap;
public PriorityQueue() {
maxHeap = new MaxHeap();
}
@Override
public int getSize() {
return maxHeap.getSize();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
@Override
public E getFront() {
return (E) maxHeap.findMax();
}
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
@Override
public E dequeue() {
return (E)maxHeap.extractMax();
}
}
前缀树
package myjava;
import java.util.TreeMap;
public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
}
public void add(String word) { // 添加单词
Node cur = root;
for (int i=0; i<word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
public boolean contains(String word) { // 查询是否有某个单词
Node cur = root;
for (int i=0; i<word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
public boolean isPrefix(String prefix) { // 是否包含某个前缀
Node cur = root;
for (int i=0; i<prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return true;
}
}
并查集
package myjava;
public class ArrayUF implements UnionFind {
private int[] parent;
private int[] rank;
public ArrayUF(int size) {
parent = new int[size];
rank = new int[size];
for (int i=0; i<size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 && p >= parent.length) {
throw new IllegalArgumentException("p is out of bound");
}
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // 路径压缩，缩短到根节点的距离
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
哈希表
package myjava;
import java.util.TreeMap;
public class HashTable<K, V> {
private TreeMap<K, V>[] hashtable;
private int M;
private int size;
public HashTable(int M) {
this.M = M;
size = 0;
hashtable = new TreeMap[M];
for (int i=0; i<M; i++) {
hashtable[i] = new TreeMap<>();
}
}
public HashTable() {
this(97);
}
public int hash(K key) {
return (key.hashCode() & 0x7ffffff) % M;
}
public int getSize() {
return size;
}
public void add(K key, V value) {
TreeMap<K, V> map = hashtable[hash(key)];
if (map.containsKey(key)) {
map.put(key, value);
} else {
map.put(key, value);
size++;
}
}
public V remove(K key) {
TreeMap<K, V> map = hashtable[hash(key)];
V ret = null;
if (map.containsKey(key)) {
ret = map.remove(key);
size--;
}
return ret;
}
public void set(K key, V value) {
TreeMap<K, V> map = hashtable[hash(key)];
if (!map.containsKey(key)) {
throw new IllegalArgumentException(key+"doesn't exist!");
}
map.put(key, value);
}
public boolean contains(K key) {
return hashtable[hash(key)].containsKey(key);
}
public V get(K key) {
return hashtable[hash(key)].get(key);
}
}
