排序算法

冒泡排序

public class Main {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }
}

选择排序

public class Main {
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }
}

插入排序

public class Main {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
}

归并排序

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

2）让其整体有序的过程里用了排外序方法

时间复杂度O(N*logN)，额外空间复杂度O(N)

public class Main {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }
    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
    public static void merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }
}

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。 例如：[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16

使用归并思路解这个题目，将题目转化为求右边有多少个值比左边的某个值大。

public class Main {
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

    public static int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid)
                + mergeSort(arr, mid + 1, r)
                + merge(arr, l, mid, r);
    }

    public static int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            // 这里计算右边比左边某个值大的个数然后乘以左边值
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }
}

堆排序

public class Main {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }
    // 从下往上调整 
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) /2);
            index = (index - 1)/2 ;
        }
    }
        // 从上往下调整 
    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
}

荷兰国旗问题

1.给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

public class Main {
    /**
     * 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)
     *
     * l 指向小于等于num的最右下标，默认为-1
     * 1. 若arr[i] <= num, 则arr[i]跟arr[l+1]进行交换, 交换后l++, i++
     * 2. 若arr[i] > num, 则i++
     *
     * [小于等于num][大于num][待遍历]
     * 所以当遇到arr[i] <= num, 则将小于等于num的后一个与arr[i]进行交换
     */ 
    public static void NetherlandsFlag1(int[] arr, int num) {
        int l = -1;
        int i = 0;
        while (i < arr.length) {
            if (arr[i] <= num) {
                swap(arr,i,l+1);
                l++;
                i++;
            } else {
                i++;
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度 O(N)

public class Main {
    /**
     * 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
     * 要求额外空间复杂度O(1)，时间复杂度 O(N)
     *
     * int l = -1, r = arr.length
     * l 指向小于num的最右下标, r指向大于num的最左下标
     * 主要分成四个区间
     * [小于num][等于num][待遍历][大于num]
     * 1. 若arr[i] < num, 则arr[i]与[l+1]交换, i++, l++
     * 2. 若arr[i] = num, 则i++
     * 3. 若arr[i] > num, 则arr[i]与arr[r-1]交换, r--, 这一步主要是把大于num的数移到右边, 此时i不变
     */ 
    public static void NetherlandsFlag(int[] arr, int num) {
        int l = -1, r = arr.length;
        int i = 0;
        while (i < r) {
            if (arr[i] < num) {
                swap(arr, i, l+1);
                i++;l++;
            } else if (arr[i] == num){
                i++;
            } else {
                swap(arr, i, r - 1);
                r--;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序

public class Main {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            //  
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }
}

链表问题

反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

判断链表是否为回文

给定一个单链表的头节点head，请判断该链表是否为回文结构。1->2->1，返回true； 1->2->2->1，返回true；15->6->15，返回true；

1->2->3，返回false。

方法一

1.遍历链表，将数据依次入栈

2.遍历链表并将栈中的数据依次出栈，比较这两个数是否相等

方法二

1.使用快慢

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // a -> b -> c -> null 
        // a -> b -> c -> d -> null 
        ListNode n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }
          // mid 保存链表的中点位置 
        ListNode mid = n1;
          // n1指向中点位置的下一个节点
        n1 = n1.next;
        mid.next = null;

        // 反转n1
        n1 = reverseList(n1);
          // n3指向右边链表反转后的头结点 
        ListNode n3 = n1;
          // n2指向链表的头结点
        n2 = head;

        boolean res = true;
          // 开始比较 
        while (n3 != null) {
            if (n3.val != n2.val) {
                res = false;
                break;
            }
            n3 = n3.next;
            n2 = n2.next;
        }

          // 比较完成之后还需要将链表连起来 
        // 反转n1
        n1 = reverseList(n1);
          // 
        mid.next = n1;

        return res;
    }
}

将单向链表按某值划分成左边小、中间相等、右边大的形式

方法一

1.将单链表的节点放入到数组中

2.组数组中使用荷兰国旗问题来划分值

3.然后将数组中的节点依次串起来

方法二

Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail

最后再连接起来

链表相交

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        int count = 0;
        while (curA.next != null) {
            curA = curA.next;
            count++;
        }
        while (curB.next != null) {
            curB = curB.next;
            count--;
        }
        if (curA != curB) {
            return null;
        }
        curA = count > 0 ? headA : headB;
        curB = curA == headA ? headB : headA;
        count = Math.abs(count);
        while (count > 0) {
            curA = curA.next;
            count--;
        }
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}

环形链表

给定一个链表，判断链表中是否有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode s = head;
        ListNode f = head;
        while (f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
            if (s == f) {
                return true;
            }
        }
        return false;
    }
}

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode s = head; // 慢指针
        ListNode f = head; // 快指针 
        while (f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
            if (s == f) {
                break;
            }
        }
        if (s == f) {
              // 运行到这里，说明肯定有环，将快指针指向头结点
            f = head;
              // 最终s和f相遇的节点就是入环的节点 
            while (s != f) {
                s = s.next;
                f = f.next;
            }
            return s;
        } else {
            return null;
        }
    }
}

二叉树

二叉树遍历

前序遍历-递归

public class Main {
    public static void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
}

前序遍历-非递归

public class Main {
    public static void preOrderUnRecur(Node head) {
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
}

中序遍历-递归

public class Main {
    public static void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + " ");
        inOrderRecur(head.right);
    }
}

中序遍历-非递归

public class Main {
    public static void inOrderUnRecur(Node head) {
        System.out.print("in-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }
}

后序遍历-递归

public class Main {
    public static void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + " ");
    }
}

后序遍历-非递归

public class Main {
    public static void posOrderUnRecur1(Node head) {
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }
}

判断是否是搜索二叉树

判断中序遍历是否依次递增

递归

public class Main {
    public static int preValue = Integer.MIN_VALUE;
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        boolean leftIsBst = isBST(head.left);
        if (!leftIsBst) {
            return false;
        }
        // 判断当前值是否大于前一个值 
        if (head.value < preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return isBST(head.right);
    }
}

套路解法

1.左边孩子是搜索二叉树

2.右孩子是搜索二叉树

3.左孩子的最大值小于头结点

4.右孩子的最小值大于头结点

public class Main {
    public static class ReturnType {
        public boolean isBST;
        public int min;
        public int max;
        public ReturnType(boolean minisBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }
    public static boolean isBST(Node head) {
        return process(head).isBST;
    }
    private static ReturnType process(Node x) {
        if (x == null) {
            return null;
        }
        boolean isBST = true;
        int min = x.value;
        int max = x.value;
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        if (leftData != null
            &&
            (!leftData.isBST || leftData.max >= x.value)
        ) {
            isBST = false;
        }

        if (rightData != null
                &&
                (!rightData.isBST || x.value >= rightData.min)
        ) {
            isBST = false;
        }

        return new ReturnType(isBST, min, max);
    }
}

非递归

略

判断完全二叉树

1.使用宽度遍历

2.如果遇到某个节点，左孩子为空，右孩子不为空，则返回false

3.在2条件不违规时，如果遇到了第一个左右孩子不双全的情况，接下来遇到的所有节点都是叶子节点

public class Main {
    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        // 判断是否遇到第一个不双全的节点 
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                // 遇到第一个左右孩子不双全的情况后，如果后面的节点还存在非叶子节点，则返回false
                    (leaf && (l != null || r != null))
                            ||
                            // 左孩子为空，右孩子不为空，直接返回false
                            (l == null && r != null)
            ) {
                return false;
            }
            if (l != null) {
                queue.add(l); // 左孩子进队列
            }
            if (r != null) {
                queue.add(r); // 右孩子进队列
            }
            // 第一次遇到左右孩子不双全的情况 
            if (l == null || r == null) {
                leaf = true;
            }
        }
        return true;
    }
}

判断满二叉树

public class Main {
    public static class ReturnData {
        public int height;
        public int nodes;
        public ReturnData(int height, int nodes) {
            this.nodes = nodes;
            this.height = height;
        }
    }
    public static boolean isFullTree(Node head) {
        ReturnData result = process(head);
        int heigth = result.height;
        int nodes = result.nodes;
        return nodes == (1 << heigth - 1); // nodes == 2 ^ n - 1
    }
    private static ReturnData process(Node x) {
        if (x == null) {
            return new ReturnData(0, 0);
        }
        ReturnData left = process(x.left);
        ReturnData right = process(x.right);
        int heigth = Math.max(left.height, right.height) + 1;
        int nodes = left.nodes + right.nodes + 1;
        return new ReturnData(heigth, nodes);
    }
}

判断平衡二叉树

1.左子树与右子树的高度差不超过1

public class Main {
    public static boolean isBalanced(Node head) {
        return process(head).isBalanced;
    }

    public static class ReturnType {
        public boolean isBalanced;
        public int height;

        public ReturnType(boolean isB, int hei) {
            isBalanced = isB;
            height = hei;
        }
    }

    public static ReturnType process(Node x) {
        if (x == null) {
            return new ReturnType(true, 0);
        }
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        // 左右孩子都是平衡树 
        // 左右孩子高度差不能超过1 
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced
                && Math.abs(leftData.height - rightData.height) < 2;
        return new ReturnType(isBalanced, height);
    }
}

二叉树的最近公共祖先

方法一

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       // 保存所有节点的父节点
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        // 父节点的头结点等于它自己
        parentMap.put(root, root);
        // 设置各节点的父元素
        setParentNode(root, parentMap);

        // 用来保存 o1 往上走经过的节点
        Set<TreeNode> set1 = new HashSet<>();
        TreeNode cur = p;
        while (cur != parentMap.get(cur)) { // 头结点的父节点等于自己，一直从o1走到父节点
            set1.add(cur);
            cur = parentMap.get(cur);
        }
        set1.add(root);

        // 此时遍历o2的父节点，如果父节点存在set1里面，则这个就是他们的最低公共父节点
        cur = q;
        while (cur != parentMap.get(cur)) {
            if (set1.contains(cur)) {
                return cur;
            }
            cur = parentMap.get(cur);
        }
        // 最后一个肯定就是父节点了 
        return root; 
    }


    private void setParentNode(TreeNode head, HashMap<TreeNode,TreeNode> parentMap) {
        if (head == null) {
            return;
        }
        parentMap.put(head.left, head);
        parentMap.put(head.right, head);
        setParentNode(head.left, parentMap);
        setParentNode(head.right, parentMap);
    }
}

方法二

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果 root 为空 或者 遇到 p 或者遇到 q 则直接返回 root 
        // 这里相当于遇到空时返回空，遇到p 、 q时就返回 p 、 q 
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            // 说明 p 和 q都已经遇到了，那么此时的 root 就是公共节点 
            return root;
        }
        // 这里有三种情况 
        // 1. left == null && right == null 
        // 2. left != null && right == null 
        // 3. left == null && right != null 
        // 如果存在不为空的，则返回不为空的那个 
        return left != null ? left : right;
    }
}

前缀树

一个字符串类型的数组arr1，另一个字符串类型的数组arr2。arr2中有哪些字符，是arr1中

出现的？请打印。arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。arr2

中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀

class TrieNode {
    public int path;
    public int end;
    public TrieNode[] nexts; // 这里也可以用Map数据结构

    public TrieNode() {
        this.path = 0;
        this.end = 0;
        this.nexts = new TrieNode[26];
    }
}

class Trie {
    public TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chars = word.toCharArray();
        TrieNode node = root;
        node.path++;

        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.nexts[index] == null) {
                node.nexts[index] = new TrieNode();
            }
            node = node.nexts[index];
            node.path++;
        }
        node.end++;
    }
    // word 这个单词之前加入过几次 
    public int search(String word) {
        if (word == null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        TrieNode node = root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }
    // 所有加入的字符串中，有几个是以 pre 这个字符串作为前缀的 
    public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }
        char[] chars = pre.toCharArray();
        TrieNode node = root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.path;
    }

    // 所有加入的字符串中，有几个是以 pre 这个字符串作为前缀的 
    public void delete(String pre) {
        if (search(pre) == 0) {
            return;
        }
        char[] chars = pre.toCharArray();
        int index = 0;
        TrieNode node = root;
        node.path--;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i] - 'a';
            if (--node.nexts[index].path == 0) {
                node.nexts[index] = null;
                return;
            }
            node = node.nexts[index];
        }
        node.end--;
    }
}

第二章

布隆过滤器

一致性哈希算法

并查集

并查集代码实现

public class UnionFindSet<V> {
    // 将样本包一层 
    class Element<V> {
        public V value;
        public Element(V value) {
            this.value = value;
        }
    }

    // 通过样本元素找到对应的 Element 
    private Map<V, Element> elementMap;
    // Element 指向的父元素 
    private Map<Element, Element> fatherMap;
    // 父Element下集合的大小 
    private Map<Element, Integer> sizeMap;

    public UnionFindSet(List<V> list) {
        this.elementMap = new HashMap<>();
        this.fatherMap = new HashMap<>();
        this.sizeMap = new HashMap<>();
        // 初始化 
        for (V v : list) {
            Element element = new Element(v);
            elementMap.put(v, element);
            fatherMap.put(element, element);
            sizeMap.put(element, 1);
        }
    }

    private Element<V> findHead(Element<V> element) {
        // 这个栈用来保存 element 查找父元素的路径 
        // 主要是有了为一个优化: 将一个长链表扁平化 
        // 比如:a -> b -> c -> d, 如传进来 element = a 
        // 那么 path = a、b、c, element = d 
        // 最后链表变成这样 a -> d, b -> d, c -> d
        Stack<Element> path = new Stack<>();
        while (element != fatherMap.get(element)) {
            path.push(element);
            element = fatherMap.get(element);
        }
        while (!path.isEmpty()) {
            fatherMap.put(path.pop(), element);
        }
        return element;
    }
    // 判断a、b两个元素是否是同一个集合 
    public boolean isSameSet(V a, V b) {
        if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
        }
        return false;
    }
    public boolean union(V a, V b) {
        if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            // 找到元素a的父元素
            Element aH = findHead(elementMap.get(a));
            // 找到元素b的父元素
            Element bH = findHead(elementMap.get(b));
            Element big = sizeMap.get(aH) >= sizeMap.get(bH) ? aH : bH;
            Element small = big == aH ? bH : aH;
            // 小集合的父元素指向大集合的父元素
            fatherMap.put(small, big);
            sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
            sizeMap.remove(small);
        }
        return false;
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        UnionFindSet<String> unionFindSet = new UnionFindSet<>(list);
        unionFindSet.union("A", "B");
        System.out.println(unionFindSet.isSameSet("A", "C"));
        unionFindSet.union("B", "C");
        System.out.println(unionFindSet.isSameSet("A", "C"));
    }
}

例题

岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    infect(i, j, N, M, grid);
                }
            }
        }
        return res;
    }

    private void infect(int i, int j, int N, int M, char[][] grid) {
        if (i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '2';
        // 向下
        infect(i + 1, j , N, M, grid);
        // 向上
        infect(i - 1, j , N, M, grid);
        // 向右
        infect(i, j + 1, N, M, grid);
        // 向左
        infect(i, j - 1 , N, M, grid);

    }
}

[进阶]如何设计一个并行算法解决这个问题

KMP

字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。 如何做到时间复杂度O(N)完成？

public class KMP {
    /**
     * 判断 m 是否是 s 的子串并返回 m 首次出现在 s 的下标
     * 比如 s = abcdefg
     * 若 m = def, 则返回3; 若 m = bbb, 则返回 -1
     * 这里需要知道一个概念:前缀子串跟后缀子串
     * 比如字符串:abbabb_ , 计算下划线前的前缀子串与后缀子串
     * 长度为1时:前缀 = a, 后缀 = b, 前缀 != 后缀
     * 长度为2时:前缀 = ab, 后缀 = bb, 前缀 != 后缀
     * 长度为3时:前缀 = abb, 后缀 = abb, 前缀 = 后缀
     * 长度为4时:前缀 = abba, 后缀 = babb, 前缀 != 后缀
     * 长度为5时:前缀 = abbab, 后缀 = bbabb, 前缀 != 后缀
     * 长度为6时:前缀跟后缀不能等于整体
     *
     * KMP算法中会用到一个辅助数组next,
     * 这个数组记录的就是子串字符串在下标为i位置时最长前缀与最长后缀相等时的前缀长度(或者后缀长度)
     * 比如字符串 m = abbabbc
     * 根据上面的例子可以知道, i = 6 时, 最长前缀等于最长后缀的长度为3, 因此next[6]=3
     * next[0] = -1, 因为下标为0之前已经没有字符了, 所以规定next[0] = -1
     * next[1] = 0, 因为下标为1之前只有一个字符,因为前缀跟后缀不能等于整体,所以next[1]=0
     *
     * 有了这个辅助数组,在进行字符匹配的时候就可以减少很多次重复匹配
     * 比如 s = abbabbabbs, m = abbabbs
     * 第一次: i1 = 6, i2 = 6, s[6] = a, m[6] = s, s[6] != m[6]
     *        此时出现第一次不相等, 通过m的next数组可以知道
     *        对于m, 下标为6时, 它的最长前缀等于最长后缀的长度为3, s[6] != m[6]时, 令 i2 = next[i2] = 3
     *        此时 i1 = 6, i2 = 3
     */ 
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || s.length() < m.length()) {
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        // 获取next数组 
        int[] next = getNextArray(str2);
        // i1 记录 str1 的下标, i2 记录 str2 的下标 
        int i1 = 0, i2 = 0;
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) { // 当前字符相等
                i1++;
                i2++;
            } else if (next[i2] == -1) { // next[i2] == -1, 说明已经没有前缀了, 只能让 str1 的下标往前走
                i1++;
            } else {
                i2 = next[i2]; // i2 往前走
            }
        }
        return i2 == str2.length ? i1 - i2 : -1;
    }

    /**
     * next数组的计算逻辑
     * next[0] = -1;
     * next[1] = 0;
     */ 
    private static int[] getNextArray(char[] str) {
        if (str.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        /**
         * cn 代表了两个含义
         * 1. 最长前缀等于最长后缀的长度
         * 2. 与 i-1位置进行比较的下标
         *    如果 str[cn] == str[i-1], 则next[i] = next[i-1]+1
         *    如果 str[cn] != str[i-1] && cn > 0, 则 cn = next[cn]
         *    如果 str[cn] != str[i-1] && cn <= 0, 则next[i] = 0
         */ 
        int cn = next[i - 1];
        while (i < str.length) {
            if(str[cn] == str[i - 1]) {
                next[i] = cn + 1;
                i++;
                /**
                 * 因为i已经加1了, 所以cn记录的应该是i加1之前的长度, 因此cn也要加1
                 * 相当于 cn = next[i-1]
                 */ 
                cn++;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                // cn 已经不能往前走了
                next[i] = 0;
                i++;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
        System.out.println(str.indexOf(match));
    }
}

Manacher

Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

在进行Manacher算法时，字符串都会进行一个字符处理，比如输入的字符为abacd，用“#”字符处理之后的新字符串就是#a#b#a#c#d#。

回文半径数组radius

回文半径数组radius用来记录以每个字符为中心时的回文半径长度,#a#b#a#b#b#的回文半径数组值如下

Index012345678910#a#b#a#c#d#radius12141212121

最右回文右边界R及中心点C

以#a#b#c#b#b#为例。

默认情况R = -1，C = -1

i = 0时, 回文串为#, R = 0, C = 0

i = 1时, 回文串#a#, R = 2, C = 1

i = 2时, 回文串为#

i = 3时, 回文串为##a#b#a#, R = 6, C = 3

……

代码

// abcbdk s kdbcba
// 
/**
 *
 * 假设以C为中心点的左边界为L, 右边界为R, 当前位置为i,
 * i' = 2*C - i, i'是以 C 为中心的对称点, [][L][][i'][][C][][i][][R][]
 * 求i`主要是为了加速, 因为i'在i的左侧, i'的回文半径是已经知道了的
 * 假设以i'为中心的回文区域的左边界为pL, 以i为中心的回文区域的右边界为pR
 *
 * 1. i > R, radius[i] = 1, 然后尝试往外扩
 * 2. i <= R 时有以下两种情况
 *    2.1 如果i'的回文区域左界pL >= L, 如下所示
 *      [][L][pL][i'][][C][][i][pR][R][]
 *      因为 L 和 R 之间是以 C 为中心的回文串, 所以i的回文半径长度等于i'的回文半径长度
 *      因此, radius[i] = radius[i'], 然后尝试往外扩
 *    2.2 如果i'的回文区域左界 < L, 假设 radius[i] = radius[i'],
 *      因此: [pL][L][][i'][][C][][i][][R][pR]
 *      那么此时i的回文区域右边界pR > R, 但此时大于R范围的数据是不知道的, 所以需要从R之后的位置继续尝试
 *      因此, radius[i] = R - i
 */ 
public class Manacher {
    public int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArray = manacherString(str);
        // 回文半径数组 
        int[] radius = new int[charArray.length];
        // 回文右边界再往右一个位置, 回文右边界有效位置为 R - 1 
        int R = -1;
        // 中心点 
        int C = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < radius.length; i++) {
            radius[i] = R > i ? Math.min(radius[2 * C - i], R - i) : 1;
            while (i + radius[i] < charArray.length && i - radius[i] >= 0) {
                if (charArray[i + radius[i]] == charArray[i - radius[i]]) {
                    radius[i]++;
                } else {
                    break;
                }
            }
            if (i + radius[i] > R) {
                R = i + radius[i];
                C = i;
            }
            max = Math.max(max, radius[i]);
        }
        return max - 1;
    }

    private char[] manacherString(String str) {
        char[] charArray = str.toCharArray();
        char[] res = new char[charArray.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArray[index++];
        }
        return res;
    }

    public static void main(String[] args) {
        Manacher manacher = new Manacher();
        String str1 = "abc1234321ab";
        System.out.println(manacher.maxLcpsLength(str1));
    }
}

滑动窗口

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次 向右边滑

一个位置。

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:

[4 3 5]4 3 3 6 7

4[3 5 4]3 3 6 7

4 3[5 4 3]3 6 7

4 3 5[4 3 3]6 7

4 3 5 4[3 3 6]7

4 3 5 4 3[3 6 7]

窗口中最大值为5 窗口中最大值为5 窗口中最大值为5 窗口中最大值为4 窗口中最大值为6

窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。

请实现一个函数。 输入:整型数组arr，窗口大小为w。

输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的 以本题为例，结果应该

返回{5,5,5,4,6,7}。

public class Main {
    public static void main(String[] args)  {
        int[] arr = new int[]{4,3,5,4,3,3,6,7};
        int w = 3;
        int[] result = new int[arr.length - w + 1];
        int index = 0;
        // 每次都将数据从双端队列dqueue的尾部放进去 
        // 如果当前需要放进去的数据大于等于尾部代表的数据, 则弹出当前尾部的数据直到当前需要放进去的数据小于尾部代表的数据 
        // 从头部开始存放的数据都是单调递减的 
        // 即 dqueue 的头部保存的是当前滑动窗口的最大值的数组下标
        LinkedList<Integer> dqueue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            // 如果存在 arr[i] >= arr[dqueue.getLast()], 则需要将尾部数据弹出 
            while (!dqueue.isEmpty() && arr[i] >= arr[dqueue.getLast()]) {
                dqueue.removeLast();
            }
            dqueue.addLast(i);
            // 判断当前头部的下标是否已经过期了 0 1 2 3 4 
            if (dqueue.getFirst() == i - w) {
                // 头部下标已经过期, 则直接弹出头部
                dqueue.removeFirst();
            }
            if (i >= w - 1) {
                result[index++] = arr[dqueue.getFirst()];
            }
        }
        System.out.println(JSON.toJSON(result));
    }
}

如果是求窗口中的最小值，原理也是相同

public class Main {
    public static void main(String[] args)  {
        int[] arr = new int[]{4,3,5,1,4,5,6,7};
        int w = 3;
        int[] result = new int[arr.length - w + 1];
        int index = 0;
        // dqueue 保存的数据是单调递增的
        LinkedList<Integer> dqueue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            while (!dqueue.isEmpty() && arr[i] <= arr[dqueue.getLast()]) {
                dqueue.removeLast();
            }
            dqueue.addLast(i);
            // 判断头部是否过期 
            if (dqueue.getFirst() == i - w) {
                dqueue.removeFirst();
            }
            if (i >= w - 1) {
                result[index++] = arr[dqueue.getFirst()];
            }
        }
        System.out.println(JSON.toJSON(result));
    }
}