Algorithm

package me.jy.list;

/**
 * 基于数组实现线性表
 *
 * @author jy
 */
class ArrayList<T> implements List<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULT_EMPTY_DATA = {};

    private Object[] elements;

    private int size;

    public ArrayList() {
        this.elements = DEFAULT_EMPTY_DATA;
    }

    public ArrayList(int size) {
        this.elements = new Object[Math.max(0, size)];
    }

    @Override
    public void add(T e) {
        if (this.elements.length == size) {
            resize(size + (size >> 1));
        }
        elements[size++] = e;
    }

    private void resize(int i) {
        i = Math.max(DEFAULT_CAPACITY, i);
        Object[] newElements = new Object[i];
        System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }

    @Override
    public T get(int index) {
        checkRange(index);
        return (T) elements[index];
    }

    @Override
    public void remove(int index) {
        checkRange(index);
        elements[index] = null;
        if (index != --size) {
            System.arraycopy(elements, index + 1, elements, index, size - index + 1);
        }
    }

    @Override
    public int size() {
        return size;
    }

    private void checkRange(int index) {
        if (index >= size) {
            throw new RuntimeException("Index out of bounds!");
        }
    }

}

3.1.1. 时间复杂度

get: \$O(1)\$
add: \$O(n)\$
remove: \$O(n)\$

3.2. 链表

每个元素包含一个指针指向下一个元素.

package me.jy.list;

/**
 * 双向链表实现
 *
 * @author jy
 */
class LinkedList<T> implements List<T> {

    private ListNode<T> head;

    private ListNode<T> tail;

    private int size;

    // tag::reverse-list[]
    public static <T> ListNode<T> reverse(ListNode<T> head) {
        ListNode<T> prev = null;
        ListNode<T> current = head;
        while (current != null) {
            ListNode<T> next = current.getNext();
            current.setNext(prev);
            prev = current;
            current = next;
        }
        return prev;
    }
    // end::reverse-list[]

    @Override
    public void add(T e) {
        ListNode<T> node = new ListNode<>(e);
        if (this.tail == null) {
            head = this.tail = node;
        } else {
            node.setPrev(tail);
            this.tail.setNext(node);
            this.tail = node;
        }
        size++;
    }

    @Override
    public T get(int index) {
        ListNode<T> current = head;
        for (int i = 0; i < index && current != null; i++) {
            current = current.getNext();
        }
        if (current == null) {
            throw new RuntimeException("Index out of bound!");
        }
        return current.getData();
    }

    @Override
    public void remove(int index) {
        ListNode<T> current = head;
        for (int i = 0; i < index && current != null; i++) {
            current = current.getNext();
        }
        if (current == null) {
            throw new RuntimeException("Index out of bound!");
        }
        ListNode<T> prev = current.getPrev();
        if (prev == null) {
            head = current.getNext();
        } else {
            prev.setNext(current.getNext());
        }
        size--;
    }

    @Override
    public int size() {
        return size;
    }

}

3.2.1. 时间复杂度

get: \$O(n)\$
add: \$O(1)\$
remove: \$O(n)\$

3.2.2. ArrayList和LinkedList比较

ArrayList的实现基于数组, LinkedList的实现基于双向链表.
对于随机访问, ArrayList优于LinkedList.
对于新增元素, LinkedList优于ArrayList.
LinkedList比ArrayList更占内存.
因为LinkedList要维护前驱和后继节点的指针.

3.2.3. 翻转单链表

    public static <T> ListNode<T> reverse(ListNode<T> head) {
        ListNode<T> prev = null;
        ListNode<T> current = head;
        while (current != null) {
            ListNode<T> next = current.getNext();
            current.setNext(prev);
            prev = current;
            current = next;
        }
        return prev;
    }

3.3. 队列

先进先出.

3.3.1. 数组实现队列

package me.jy.list;

/**
 * @author jy
 */
class ArrayQueue<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULT_EMPTY_DATA = {};

    private Object[] elements;

    private int size;

    public ArrayQueue() {
        this.elements = DEFAULT_EMPTY_DATA;
    }

    public ArrayQueue(int capacity) {
        this.elements = new Object[Math.max(capacity, DEFAULT_CAPACITY)];
    }

    public void push(T e) {
        if (this.elements.length == size) {
            resize(size + (size >> 1));
        }
        this.elements[size++] = e;
    }

    public T pop() {
        if (this.size == 0) {
            return null;
        }
        T data = (T) this.elements[0];
        System.arraycopy(elements, 1, elements, 0, --size);
        return data;
    }

    public int size() {
        return size;
    }

    private void resize(int i) {
        Object[] newElements = new Object[Math.max(i, DEFAULT_CAPACITY)];
        System.arraycopy(elements, 0, newElements, 0, size);
        this.elements = newElements;
    }
}

3.3.2. 链表实现队列

package me.jy.list;

/**
 * @author jy
 */
class LinkedQueue<T> {

    private ListNode<T> head;
    private ListNode<T> tail;

    private int size;

    public LinkedQueue() {
    }

    public void push(T e) {
        ListNode<T> node = new ListNode<>(e);
        if (head == null) {
            head = tail = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
        size++;
    }

    public T pop() {
        if (size == 0) {
            return null;
        }

        ListNode<T> legacyHead = this.head;

        this.head = this.head.getNext();

        if (head == null) {
            this.tail = null;
        } else {
            this.head.setPrev(null);
        }

        legacyHead.setNext(null);
        size--;

        return legacyHead.getData();
    }

    public int size() {
        return size;
    }
}

3.4. 栈

先进后出.

3.4.1. 数组实现栈

package me.jy.list;

/**
 * 基于数组实现栈
 *
 * @author jy
 */
class ArrayStack<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULT_EMPTY_DATA = {};

    private Object[] elements;

    private int size;

    public ArrayStack() {
        this.elements = DEFAULT_EMPTY_DATA;
    }

    public ArrayStack(int capacity) {
        this.elements = new Object[Math.max(capacity, DEFAULT_CAPACITY)];
    }

    public void push(T e) {
        if (this.size == elements.length) {
            resize(size + (size >> 1));
        }
        this.elements[size++] = e;
    }

    private void resize(int i) {
        Object[] newElements = new Object[Math.max(i, DEFAULT_CAPACITY)];
        System.arraycopy(elements, 0, newElements, 0, size);
        this.elements = newElements;
    }

    public T pop() {
        if (this.size == 0) {
            return null;
        }
        T element = (T) this.elements[size - 1];
        this.elements[--size] = null;
        return element;
    }

    public int size() {
        return size;
    }
}

3.4.2. 双向链表实现栈

package me.jy.list;

/**
 * @author jy
 */
class LinkedStack<T> {

    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;

    public void push(T e) {
        ListNode<T> node = new ListNode<>(e);
        if (tail == null) {
            head = this.tail = node;
        } else {
            tail.setNext(node);
            node.setPrev(tail);
            tail = node;
        }
        size++;
    }

    public T pop() {
        if (size == 0) {
            return null;
        }

        ListNode<T> legacyTail = this.tail;
        this.tail = this.tail.getPrev();

        if (tail == null) {
            head = null;
        } else {
            this.tail.setNext(null);
        }

        legacyTail.setPrev(null);
        size--;

        return legacyTail.getData();
    }

    public int size() {
        return size;
    }
}

3.5. 哈希表

对key计算hash值, 确定元素存放的位置.

3.5.1. 解决哈希冲突

线性检测: 往散列表中插入数据, 如果某个数据经过hash后存放位置被占用了, 则从当前位置开始向后依次查找直到找到一个空闲的位置.
二次检测: 每次检测的步长为平方数, 如 \$1^2,2^2,3^2...\$
二次散列: 哈希冲突后第二次计算hash值.
链地址法: 使用链表存储冲突的元素.

4. 树

4.1. 术语

根节点
叶子节点
边
深度
高度
满二叉树: 除了叶子节点, 其他节点均有两个子节点.
完全二叉树: 最后一层叶子节点从左到右排列, 最后一层以上的节点均有两个节点.

4.2. 二叉树

树中任意一个节点, 其左子节点的值都小于该节点的值, 其右子节点的值都大于该节点的值.

4.2.1. 实现

package me.jy.tree;

import java.util.Optional;

/**
 * @author jy
 */
public class BinarySearchTree<T extends Comparable<? super T>> {

    private Node root;

    public void insert(T value) {
        Node node = new Node(value);
        if (root == null) {
            root = node;
            return;
        }
        Node current = root;
        while (true) {
            int compare = current.value.compareTo(value);
            if (compare == 0) {
                return;
            }
            if (compare < 0) {
                if (current.right == null) {
                    current.right = node;
                    break;
                }
                current = current.right;
            } else {
                if (current.left == null) {
                    current.left = node;
                    break;
                }
                current = current.left;
            }
        }
    }

    public void remove(T value) {
        checkValue(value);
        remove(value, root);
    }

    public T findMin() {
        if (root == null) {
            return null;
        }
        return findMinNode(root).value;
    }

    public T findMax() {
        if (root == null) {
            return null;
        }
        return findMaxNode(root).value;
    }

    public boolean contains(T value) {
        checkValue(value);
        return contains(value, root);
    }

    public int height() {
        return height(root);
    }

    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    private boolean contains(T value, Node node) {
        if (node == null) {
            return false;
        }
        int compare = value.compareTo(node.value);
        if (compare == 0) {
            return true;
        }
        if (compare < 0) {
            return contains(value, node.left);
        }
        return contains(value, node.right);
    }

    /**
     * 删除
     *
     * @param value 要删除的节点的值
     * @param node  根节点
     */
    private Node remove(T value, Node node) {
        if (node == null) {
            return null;
        }

        int compare = value.compareTo(node.value);
        if (compare < 0) {
            node.left = remove(value, node.left);
        } else if (compare > 0) {
            node.right = remove(value, node.right);
        } else if (node.left != null && node.right != null) {
            // 找到右子节点中最小的节点, 变为node的右子节点
            node.value = findMinNode(node.right).value;
            node.right = remove(node.value, node.right);
        } else {
            // node为树叶或者只有一个子节点
            node = Optional.ofNullable(node.left).orElse(node.right);
        }
        return node;
    }

    private Node findMaxNode(Node node) {
        if (node.right == null) {
            return node;
        }
        return findMaxNode(node.right);
    }

    private Node findMinNode(Node node) {
        if (node.left == null) {
            return node;
        }
        return findMinNode(node.left);
    }

    private void checkValue(T value) {
        if (value == null) {
            throw new IllegalArgumentException("No soup for u!");
        }
    }

    private class Node {

        private T value;
        private Node left;
        private Node right;

        private Node(T value) {
            this.value = value;
        }
    }

}

4.2.2. 时间复杂度

最坏 \$O(n)\$, 平均 \$O(logn)\$

4.3. AVL树

4.3.1. 性质

可以是空树.
任意左右子树均是AVL树, 且高度之差不能大于1.

4.3.2. 二叉树失衡场景

LL: 向左子树的左子树插入元素.
LR: 向左子树的右子树插入元素.
RR: 向右子树的右子树插入元素.
RL: 向右子树的左子树插入元素.

4.3.3. 实现

package me.jy.tree;

/**
 * @author jy
 */
public class AVLTree<T extends Comparable<T>> {

    private Node root;

    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    private int heightBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return Math.abs(height(node.left) - height(node.right));
    }

    /**
     * 将Z节点变为X节点的右子节点, X节点原有的右子节点变为Z节点的左子节点.
     */
    public Node llRotate(Node node) {
        Node pivot = node.left;
        node.left = pivot.right;
        pivot.right = node;

        return pivot;
    }

    /**
     * 将Z节点变为Y节点的左子节点, Y节点原有的左子节点变为Z节点的右子节点.
     */
    public Node rrRotate(Node node) {
        Node pivot = node.right;
        node.right = pivot.left;
        pivot.left = node;
        return pivot;
    }

    /**
     * 以X节点的右子节点为轴进行左单旋(用X节点的右子节点替换X节点), 然后以新的X节点为轴进行右单旋.
     */
    private Node lrRotate(Node node) {
        Node left = node.left;
        Node pivot = left.right;

        // ll
        left.right = pivot.left;
        pivot.left = left;
        node.left = pivot;

        // rr
        node.left = pivot.right;
        pivot.right = node;

        return pivot;
    }

    /**
     * 以Y节点的左子节点为轴进行右单旋(用Y节点的左子节点替换Y节点), 然后以新的Y节点为轴进行左单旋.
     */
    private Node rlRotate(Node node) {
        Node right = node.right;
        Node pivot = right.left;

        // rr
        right.left = pivot.right;
        pivot.right = right;
        node.right = pivot;

        // ll
        node.right = pivot.left;
        pivot.left = node;

        return pivot;
    }

    public void insert(T value) {
        root = insert(root, value);
    }

    private Node insert(Node root, T value) {
        Node node = new Node(value);
        if (root == null) {
            root = node;
        } else if (root.value.compareTo(value) < 0) {
            root.right = insert(root.right, value);
            if (heightBalanceFactor(root) > 1) {
                if (root.right.value.compareTo(value) < 0) {
                    root = rrRotate(root);
                } else {
                    root = rlRotate(root);
                }
            }
        } else {
            root.left = insert(root.left, value);
            if (heightBalanceFactor(root) > 1) {
                if (root.left.value.compareTo(value) > 0) {
                    root = llRotate(root);
                } else {
                    root = lrRotate(root);
                }
            }
        }
        return root;
    }

    public int heightFactor() {
        return heightBalanceFactor(root);
    }

    /**
     * 中序遍历
     */
    public void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.value);
        inOrder(node.right);
    }

    public void print() {
        inOrder(root);
    }

    private class Node {

        private final T value;
        private Node left;
        private Node right;

        private Node(T value) {
            this.value = value;
        }
    }
}

5. 图

5.1. 表示方法

邻接矩阵
邻接表

5.2. 遍历

5.3. 广度优先算法

5.4. 深度优先算法

6. 排序

6.1. 冒泡排序

    /**
     * 冒泡排序
     * 两两比较, 如果左边的元素比右边的大, 则交换位置.
     * O(n^2)
     */
    public static class BubbleSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            for (int i = arr.length - 1; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    if (less(arr[j + 1], arr[j])) {
                        exchange(arr, j, j + 1);
                    }
                }
            }
        }
    }

6.1.1. 时间复杂度

比较次数: \$(n-1) + (n-2) + (n-3)+...+2+1=((n-1+1)*(n-1))/2=(n^2-n)/2\$
交换次数: \$(n-1) + (n-2) + (n-3)+...+2+1=((n-1+1)*(n-1))/2=(n^2-n)/2\$
总: \$O(n^2-n)=O(n^2)\$

6.2. 选择排序

    /**
     * 选择排序
     * 选择数组剩余元素中最小的元素放到首位
     * O(n^2)
     */
    public static class SelectSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (less(arr[j], arr[minIndex])) {
                        minIndex = j;
                    }
                }
                exchange(arr, i, minIndex);
            }
        }
    }

6.2.1. 时间复杂度

比较次数: \$(n-1) + (n-2) + (n-3)+...+2+1=((n-1+1)*(n-1))/2=(n^2-n)/2\$
交换次数: \$O(n-1)\$
总: \$O((n^2+n)/2-1)=O(n^2)\$

6.3. 插入排序

    /**
     * 插入排序
     * 保证索引左边的元素排好序
     * O(n^2)
     */
    public static class InsertSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                for (int j = i; j > 0; j--) {
                    if (less(arr[j], arr[j - 1])) {
                        exchange(arr, j, j - 1);
                    } else {
                        break;
                    }
                }
            }
        }
    }

6.3.1. 时间复杂度

比较次数: \$(n-1) + (n-2) + (n-3)+...+2+1=((n-1+1)*(n-1))/2=(n^2-n)/2\$
交换次数: \$(n-1) + (n-2) + (n-3)+...+2+1=((n-1+1)*(n-1))/2=(n^2-n)/2\$
总: \$O(n^2-n)=O(n^2)\$

6.4. 希尔排序

    /**
     * 希尔排序(优化过的插入排序)
     * <p>
     * 步骤:
     * 1. 选定一个增长量, 对元素进行分组.
     * 2. 对每组元素进行插入排序.
     * 3. 减小增长量直至1, 重复步骤2.
     */
    public static class ShellSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            int gap = 1;
            while (gap < arr.length / 2) {
                gap = gap * 2 + 1;
            }
            for (; gap > 0; gap /= 2) {
                for (int i = gap; i < arr.length; i++) {
                    for (int j = i; j >= gap; j -= gap) {
                        if (less(arr[j], arr[j - gap])) {
                            exchange(arr, j, j - gap);
                        } else {
                            break; // 如果左边比j小, 则不需要继续向左比较了.
                        }
                    }
                }
            }
        }
    }

6.5. 归并排序

    /**
     * 归并排序
     * 将数组切成若干小数组后排序, 最后合并.
     */
    public static class MergeSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            sort(arr, 0, arr.length - 1);
        }

        private void sort(int[] arr, int lo, int hi) {
            if (lo >= hi) {
                return;
            }
            int mid = lo + (hi - lo) / 2;
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            merge(arr, lo, mid, hi);
        }

        /*private void sort2(int[] arr) {
            int n = arr.length;
            for (int i = 1; i < n; i += i) {
                for (int lo = 0; lo < n - i; lo += i * 2) { // 每次处理i*2个元素再合并
                    merge(arr, lo, lo + i - 1, Math.min(n - 1, lo + i * 2 - 1));
                }
            }
        }*/

        private void merge(int[] arr, int lo, int mid, int hi) {

            int[] tmpArr = new int[arr.length];

            int i = 0, p1 = lo, p2 = mid + 1;
            while (p1 <= mid && p2 <= hi) {
                if (less(arr[p1], arr[p2])) {
                    tmpArr[i++] = arr[p1++];
                } else {
                    tmpArr[i++] = arr[p2++];
                }
            }
            while (p1 <= mid) {
                tmpArr[i++] = arr[p1++];
            }
            while (p2 <= hi) {
                tmpArr[i++] = arr[p2++];
            }
            System.arraycopy(tmpArr, 0, arr, 0, tmpArr.length);
        }

    }

6.5.1. 时间复杂度

拆分次数: \$O(logn)\$
每次合并比较次数: \$O(n)\$
总: \$O(nlogn)\$

6.6. 快速排序

    /**
     * 快速排序
     * 保证某一元素左边值比该元素值小且有序, 右边值比该元素值大且有序, 则该数组有序.
     * 1. 找到1个分界值, 把比分界值小的放左边, 把比分界值大的放右边.
     * 2. 重复步骤1将分界值左右两边分别排序.
     */
    public static class QuickSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            sort(arr, 0, arr.length - 1);
        }

        private void sort(int[] arr, int lo, int hi) {
            if (lo >= hi) {
                return;
            }
            int partitionIndex = partition(arr, lo, hi);
            sort(arr, lo, partitionIndex - 1);
            sort(arr, partitionIndex + 1, hi);
        }

        private int partition(int[] arr, int lo, int hi) {
            int left = lo;
            int partitionValue = arr[hi];

            for (int i = left; i < hi; i++) {
                if (arr[i] < partitionValue) {
                    exchange(arr, i, left++);
                }
            }
            exchange(arr, left, hi);
            return left;
        }

        /*private void sort2(int[] arr, int lo, int hi) {
            if (hi <= lo) {
                return;
            }
            // 随机选择数组中一位作为partition
            exchange(arr, hi, ThreadLocalRandom.current().nextInt(lo, hi));
            // 取到左区间和右区间位置
            int[] indexes = partition(arr, lo, hi);
            sort(arr, lo, indexes[0]);
            sort(arr, indexes[1] + 1, hi);
        }

        private int[] partition(int[] arr, int lo, int hi) {
            int less = lo - 1;
            int more = hi;
            while (lo < more) {
                if (arr[lo] < arr[hi]) {
                    // 左指针加1, 交换lo
                    exchange(arr, ++less, lo++);
                } else if (arr[lo] > arr[hi]) {
                    // 右指针减1
                    exchange(arr, --more, lo);
                } else {
                    lo++;
                }
            }
            exchange(arr, more, hi);
            return new int[]{less, more};
        }*/
    }

6.6.1. 时间复杂度

拆分次数: 最优\$O(logn)\$, 最坏\$O(n)\$
每次比较交换次数: \$O(n)\$
总: 最好\$O(nlogn)\$, 最坏\$O(n^2)\$

6.6.2. 快速排序和归并排序的区别

归并排序将子数组切分后有归并的动作, 快速排序将子数组排完序后整个数组就自然而然的有序了.
归并排序每次切分数组都是等分.

6.7. 堆排序

    /**
     * 堆排序
     * 先将数组转成最大堆的形式, 再将第一项放到最后. 逐步重复1..n-1项
     */
    public static class HeapSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {

            int last = arr.length - 1;

            // 构造最大堆
            buildMaxHeap(arr, last);
            while (last > 0) {
                // 交换首尾元素
                exchange(arr, 0, last);
                buildMaxHeap(arr, --last);
            }
        }

        private void buildMaxHeap(int[] arr, int last) {

            if (last == 0) {
                return;
            }
            // 当前尾节点的父节点
            int parent = (last - 1) / 2;

            while (parent >= 0) {
                int left = parent * 2 + 1;
                int right = parent * 2 + 2;
                // 找到两个子节点中的值最大的节点
                int maxChildIndex = right <= last && less(arr[left], arr[right]) ? right : left;
                // 如果父节点值小, 则交换
                if (less(arr[parent], arr[maxChildIndex])) {
                    exchange(arr, parent, maxChildIndex);
                }
                parent--;
            }
        }
    }

6.7.1. 时间复杂度

建堆: \$O(logn)\$
总: \$O(nlogn)\$

6.8. 桶排序

    /**
     * 桶排序
     * 将元素按照大小放入不同的桶中, 对每个桶进行排序. 最后取出所有桶内元素.
     */
    public static class BucketSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {
            List<Integer> list = sort(Arrays.stream(arr).boxed().collect(Collectors.toList()), 5);
            for (int i = 0; i < list.size(); i++) {
                arr[i] = list.get(i);
            }
        }

        private List<Integer> sort(List<Integer> arr, int bucketSize) {

            if (arr.size() <= 1 || bucketSize < 1) {
                return arr;
            }

            IntSummaryStatistics statistics = arr.stream().mapToInt(i -> i).summaryStatistics();
            int min = statistics.getMin();
            int max = statistics.getMax();

            // 计算出桶数量
            int bucketCount = (max - min) / bucketSize + 1;

            List<List<Integer>> buckets = IntStream.range(0, bucketCount).mapToObj(i -> new ArrayList<Integer>()).collect(Collectors.toList());

            for (int value : arr) {
                int bucketIndex = (value - min) / bucketSize;
                buckets.get(bucketIndex).add(value);
            }

            List<Integer> result = new ArrayList<>();

            // 桶内排序
            for (List<Integer> bucket : buckets) {
                if (bucket.isEmpty()) {
                    continue;
                }
                if (bucketCount == 1) {
                    bucketSize--;
                }
                result.addAll(sort(bucket, bucketSize));
            }
            return result;
        }
    }

6.8.1. 时间复杂度

总: \$O(n)\$

6.9. 计数排序

    public static class CountingSort implements SortTemplate {

        @Override
        public void sort(int[] arr) {

            IntSummaryStatistics statistics = Arrays.stream(arr).summaryStatistics();
            int min = statistics.getMin();

            // 计算桶数量
            int bucketCount = statistics.getMax() - min + 1;
            int[] countingArray = new int[bucketCount];

            for (int i : arr) {
                countingArray[i - min]++; // 统计出现次数
            }

            int position = 0;
            for (int i = 0; i < countingArray.length; i++) { // 遍历桶
                for (int j = 0; j < countingArray[i]; j++) { // 桶里值为几, 就代表该桶代表的数出现几次
                    arr[position++] = i + min;
                }
            }
        }
    }

6.9.1. 时间复杂度

总: \$O(n)\$

7. 查找

7.1. 二分查找

package me.jy.search;

/**
 * @author jy
 */
class BinarySearch {

    public int uniqueSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2 + 1;
            if (arr[mid] == target)
                return mid;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

}

时间复杂度为 \$O(logn)\$

7.2. BF

package me.jy.search;

/**
 * @author jy
 */
public class BF {

    public int search(String origin, String target) {
        if (origin.length() < target.length()) {
            return -1;
        }
        char[] originChars = origin.toCharArray();
        char[] targetChars = target.toCharArray();

        // 移动双指针来比较两个子串.
        int o = 0, t = 0;
        while (o < originChars.length && t < targetChars.length) {
            if (originChars[o] == targetChars[t]) {
                o++;
                t++;
            } else {
                o = o - t + 1;
                t = 0;
            }
        }

        if (t == targetChars.length) {
            return o - t;
        }
        return -1;
    }
}

7.3. RK

package me.jy.search;

/**
 * @author jy
 */
public class RK {

    public int search(String origin, String target) {
        if (origin.length() < target.length()) {
            return -1;
        }
        int hash = hash(target, 26, 31, 0, target.length());

        for (int i = 0; i < origin.length() - target.length() + 1; i++) {
            // 比较每一个子串的哈希值, 如果哈希值相同则比较两个子串是否完全相等.
            if (hash(origin, 26, 31, i, target.length()) == hash && match(origin, target, i)) {
                return i;
            }
        }
        return -1;
    }

    private boolean match(String origin, String target, int i) {
        for (int j = 0; j < target.length(); j++) {
            if (origin.charAt(i + j) != target.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 计算指定子串hash值
     */
    private int hash(String str, int r, int k, int start, int length) {
        int hash = 0;
        for (int i = start; i < start + length; i++) {
            hash = (r * hash + str.charAt(i) % k);
        }
        return hash;
    }

}

7.4. KMP

package me.jy.search;

/**
 * @author jy
 */
public class KMP {

    public int search(String origin, String target) {

        int[] next = next(target);

        int i = 0;
        int j = 0;
        while (i < origin.length()) {
            while (j > 0 && target.charAt(j) != origin.charAt(i)) {
                j = next[j - 1];
            }
            if (target.charAt(j) == origin.charAt(i)) {
                j++;
            }
            i++;
            if (j == target.length()) {
                return i - j;
            }
        }
        return -1;
    }

    private int[] next(String target) {
        int[] next = new int[target.length()];

        next[0] = 0;

        for (int i = 1, k = 0; i < target.length(); i++) {
            while (k > 0 && target.charAt(i) != target.charAt(k)) {
                k = next[k - 1];
            }
            if (target.charAt(i) == target.charAt(k)) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }
}

8. 算法思想

8.1. 贪心

只考虑局部的利益最大化.

8.1.1. 适用场景

局部最优解能导致产生全局最优解.

8.1.2. 思路

建立数学模型来描述问题.
把求解的问题分成若干个子问题.
对每一个子问题求解, 得到子问题的局部最优解.
把子问题的局部最优解合成原来解问题的一个解.

8.2. 分治

把一个复杂的问题分解为多个子问题求解.

8.2.1. 适用场景

原问题和子问题有相同的模式.
子问题之间没有相关性.
具有分解终止条件, 即当问题足够小时, 可以直接求解.
可以将子问题合并成原问题.

8.3. 回溯

按优选条件向前搜索, 以达到目标.但当探索到某一步时, 发现原先选择并不优或达不到目标, 就退回一步重新选择.

8.4. 动态规划

把原问题分解为相对简单的子问题的方式求解复杂问题的方法.
记住已经解决过的子问题的解的方法: ① 自顶向下的备忘录法.
② 自底向上.

8.4.1. 适用场景

问题的最优解包含子问题的最优解.
某一子问题的解一旦确定, 就不会受之后子问题的解的影响.
子问题重叠, 一个子问题在下一阶段决策中可能被多次使用到.