算法与数据结构

2022-06-13 本文已影响0人 bowen_wu

概述

程序 = 算法 + 数据结构

算法是计算机科学的本质，是计算机世界的基石。算法决定了程序如何运行
数据结构决定了程序的数据如何被存储

算法的复杂度

时间复杂度

定性描述算法的运行时间

O(1) => 常数时间 => 运行时间与问题的规模无关 => 哈希桶 | 数组随机寻址 => 数组(Array) | 线性表(Linear Table)
O(n) => 线性时间 => 运行时间与问题的规模成正比 => 遍历 | 求数组、链表的最大值
O(log(n)) => 对数时间 => 每次操作其所需要的额外计算时间会变小 => 二分查找 | 二叉树
O(n*log(n)) => 基于比较的排序算法的下界
O(n^2) => 解决问题的复杂度和问题规模的平方成正比 => 冒泡排序

时间复杂度计算时忽略常数 => O(n) == O(2n)
时间复杂度的计算中，高阶复杂度会吞并低阶复杂度 => O(n^2) + O(n) == O(n^2) => 对数组进行排序后遍历，复杂度是多少？ => O(n*log(n)) + O(n) == O(n*log(n))

最好时间复杂度
最坏时间复杂度
平均时间复杂度

线性时间复杂度

求数组、链表的最大值 | 和
寻找数组中的重复元素
判断链表是否存在环(快慢指针)
求阶乘
合并两个链表
翻转链表

对数时间复杂度

二叉树

遍历二叉树

深度优先遍历 DFS(Depth First Search) => 递归
- 前序遍历(根节点 => 左节点 => 右节点)
- 中序遍历(左节点 => 根节点 => 右节点)
- 后序遍历(左节点 => 右节点 => 根节点)
广度优先遍历 BFS(Breadth First Search) => 经典的广度优先遍历算法 => 队列(先进先出 FIFO)

递归

将大问题分解成小问题
假设小问题已经解决
对分解的小问题进行求解

空间复杂度

解决问题所需要的辅助空间的大小

常数空间复杂度 => O(1) => 只需要固定大小的辅助空间 => 寻找最大值 | 求数组所有元素的和 | 非递归计算阶乘
线性空间复杂度 => O(n) => 需要的辅助空间和问题规模成正比 => 递归计算阶乘 | 带缓存(备忘录)的斐波那契数列求值

带缓存(备忘录)的斐波那契数列求值

斐波那契数列 => 1 1 2 3 5 8 13 21 34 55 89 ...

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2

class Counter {
    HashMap<Integer, Integer> cache = new HashMap<>();

    public int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public int fibonacci4Cache(int n) {
        if (cache.containsKey(n)) {
            // 缓存命中 cache hit
            return cache.get(n);
        }

        // cache miss
        if (n == 0 || n == 1) {
            return 1;
        }
        int result = fibonacci4Cache(n - 1) + fibonacci4Cache(n - 2);
        cache.put(n, result);
        return result;
    }
}

数据结构

数组 | 线性表

java.util.ArrayList => 扩容

随机寻址 => RandomAccess => 常数时间 => O(1)
插入 | 删除 => 线性时间 => O(n)
查找
- 无序数组查找 => 线性时间 => O(n)
- 有序数组查找 => 对数时间(二分查找[递归 & 非递归]) => O(log(n))

二分查找

应用于有序数组的快速算法

非递归 => 双指针

public static int binarySearch(int[] array, int key) {
     int low = 0;
     int high = array.length - 1;

     while (low <= high) {
         int mid = (low + high) / 2;
         int midVal = array[mid];

         if (midVal < key) {
             low = mid + 1;
         } else if (midVal > key) {
             high = mid - 1;
         } else {
             return mid; // key found
         }
     }
     return -(low + 1);  // key not found.
}

递归

public static int binarySearchForRecursion(int[] array, int target, int start, int end) {
     int mid = (start + end) >>> 1;
     int midVal = array[mid];
     if (start > end) {
         return -1;
     } else if (target == array[start]) {
         return start;
     } else if (target == midVal) {
         return mid;
     } else if (target == array[end]) {
         return end;
     } else if (array[start] < target && target < midVal) {
         return binarySearchForRecursion(array, target, start + 1, mid - 1);
     } else {
         return binarySearchForRecursion(array, target, mid + 1, end - 1);
     }
 }

链表 & 双向链表

java.util.LinkedList => 双向链表(Doubly-linked list) => addAll & get

寻址 => 线性时间 => O(n)
插入 | 删除 => 常数时间 => O(1)
查找 => 线性时间 => O(n)

遍历链表数据

for(Node current = head; current != null; current = current.next) {
    System.out.println(current.value);
}

如果要删除一个数据，需要将前一个数据的 next 指向下一个数据，之后将删除数据的 next 删除

翻转链表

// TODO

判断链表是否成环

// TODO

栈 Stack

java.util.Stack extends java.util.Vector => push & pop

FILO(First In Last Out)

应用：方法栈

手写一个栈的实现

public class Stack {
    private final LinkedList<Object> data = new LinkedList<>();

    // 将一个元素推入栈中
    public void push(Object obj) {
        data.add(obj);
    }

    // 将一个元素从栈顶弹出
    public Object pop() {
        return data.removeLast();
    }

    // 看看栈顶的元素，不弹出来
    public Object peek() {
        return data.getLast();
    }
}

队列 Queue

java.util.Queue.java => java.util.LinkedList.java

FIFO(First In First Out)

应用：线程池

手写一个队列的实现

// TODO => add | offer | remove | poll => java.util.LindedList

哈希表

java.util.HashMap => put & get

哈希表的时间复杂度指的是平均时间复杂度
查找 | 插入 | 删除 => 常数时间 => O(1)
哈希算法 & 碰撞
- Java8之前 => 哈希桶 + 链表
- Java8之后 => 哈希桶 + 链表 | 红黑树

二叉树

搜索二叉树

红黑树

自平衡二叉查找树 => 修改、插入、删除之后可以自己变成平衡的 => java.util.TreeSet(java.util.TreeMap) & java.util.concurrent.ConcurrentSkipListSet => put & remove
平衡二叉树很难做成线程安全的，在旋转、修改的过程中多个线程并发访问会有问题

二叉树前序遍历(根节点 => 左节点 => 右节点)

递归

class OrderTraversal {
    public List<Integer> preorderTraversalRecursion(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        result.add(root.val);
        if (root.left != null) {
            result.addAll(preorderTraversalRecursion(root.left));
        }
        if (root.right != null) {
            result.addAll(preorderTraversalRecursion(root.right));
        }
        return result;
    }
}

非递归

class OrderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> treeNodeStack = new Stack<>();
        TreeNode node = root;
        while (node != null || !treeNodeStack.isEmpty()) {
            while (node != null) {
                treeNodeStack.add(node);
                result.add(node.val);
                node = node.left;
            }
            node = treeNodeStack.pop().right;
        }

        return result;
    }
}

二叉树中序遍历(左节点 => 根节点 => 右节点)

递归

class OrderTraversal {
    public List<Integer> middleOrderTraversalRecursion(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root.left != null) {
            result.addAll(middleOrderTraversalRecursion(root.left));
        }
        result.add(root.val);
        if (root.right != null) {
            result.addAll(middleOrderTraversalRecursion(root.right));
        }
        return result;
    }
}

非递归

class OrderTraversal {
    public List<Integer> middleOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> treeNodeStack = new Stack<>();
        TreeNode node = root;
        while (node != null || !treeNodeStack.isEmpty()) {
            while (node != null) {
                treeNodeStack.push(node);
                node = node.left;
            }
            node = treeNodeStack.pop();
            result.add(node.val);
            node = node.right;
        }

        return result;
    }
}

二叉树后序遍历(左节点 => 右节点 => 根节点)

// TODO

二叉树广度优先遍历 BFS

// 将根节点加入队列，算法开始
// 如果队列不为空，则进入循环
// 队列头节点出队列 & 同时将其孩子依次加入队列
public static List<Integer> bfs(Node root) {
     List<Integer> list = new ArrayList<>();
     Queue<Node> queue = new LinkedList<>(Collections.singleton(root));

     while (!queue.isEmpty()) {
         Node head = queue.remove();
         list.add(head.value);
         if (head.left != null) {
             queue.add(head.left);
         }
         if (head.right != null) {
             queue.add(head.right);
         }
     }
     return list;
}

算法

排序算法

稳定 vs 不稳定 => 如果两个相等的数字，排序前和排序后位置保持不变，则是稳定的，否则是不稳定的。
基于比较的排序时间复杂度下限是 O(n * log(n))
Java 默认使用 DualPivotQuicksort.sort 排序 => Arrays.sort & Collections.sort

冒泡排序

时间复杂度 => O(n^2)

public class BubbleSort {
    public static void main(String[] args) {
        bubbleSort(new int[]{1, 5, 1, 6, 2, 7, 3, 8});
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                int next = array[j + 1];
                if (array[j] > next) {
                    array[j] = next;
                    array[j + 1] = array[j];
                }
            }
        }
    }
}

快速排序

每次将等待排序的数据划分成两部分
递归进行
直到所有数据有序

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 1, 6, 2, 4, 2, 3};
        List<Integer> list = quickSort(Arrays.asList(5, 1, 6, 2, 4, 2, 3));
        quickSortForInPlace(array);
        System.out.println(list);
    }

    // 分治法(Divide and conquer)需要O(n)的额外空间
    public static List<Integer> quickSort(List<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }

        List<Integer> left = new ArrayList<>(), pivot = new ArrayList<>(), right = new ArrayList<>();
        Integer pivotValue = list.get(0);
        for (Integer element : list) {
            if (element < pivotValue) {
                left.add(element);
            } else if (element.equals(pivotValue)) {
                pivot.add(element);
            } else {
                right.add(element);
            }
        }
        return Stream.of(quickSort(left), pivot, quickSort(right)).flatMap(Collection::stream).collect(Collectors.toList());
    }

    // 原地(in-place)分割版本
    public static void quickSortForInPlace(int[] array) {
        quickSortPartition(array, 0, array.length - 1);
    }

    // 对数组中的某个区域进行排序
    public static void quickSortPartition(int[] array, int left, int right) {
        if (right > left) {
            // 将 [left - right] 区域分成了
            // [left, pivotIndex - 1] 和 [pivotIndex + 1, right] 两个
            int pivotIndex = partition(array, left, right);
            quickSortPartition(array, left, pivotIndex - 1);
            quickSortPartition(array, pivotIndex + 1, right);
        }
    }

    public static int partition(int[] array, int left, int right) {
        // 挑选最右侧的作为基准值
        int pivotValue = array[right];
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (array[i] <= pivotValue) {
                swap(array, i, storeIndex);
                storeIndex += 1;
            }
        }
        swap(array, storeIndex, right);
        return storeIndex;
    }

    private static void swap(int[] x, int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}

桶排序

不基于比较排序，所以不受O(n * log(n))限制
总的时间复杂度 => O(n)
空间复杂度 => O(n)

动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

首先将问题分解，假设子问题已经解决 => 然后推导出来一个状态转移公式 => 状态是如何从更小规模的子问题到难题转移的

上台阶问题

// TODO

有一楼梯共m级，若每次只能跨上一级或两级，要走上m级，总共有多少走法？

硬币问题

public class Coins {
    // 硬币：[1, 5, 10, 25]
    // f(k, n) 只用前k种硬币组成n分的情况
    //   = f(k-1, n - 0 * COIN) // 只用前k-1种硬币组成n分的情况（0个第k个硬币）
    //     + f(k-1, n - 1 * COIN) // 只用前k-1种硬币组成 n - 1 * COIN 分的情况（1个第k个硬币）
    //     + f(k-1, n - 2 * COIN) // 只用前k-1种硬币组成 n - 2 * COIN 分的情况（2个第k个硬币）
    //     + ...
    //     + f(k-1, n - i * COIN) // 只用前k-1种硬币组成 n - i * COIN 分的情况（i个第k个硬币）
    //     直到 n - i * COIN 的值为 0

    public static int[] coin = new int[]{0, 1, 5, 10, 25};
    public static int[] coins = new int[]{1, 5, 10, 25};
    public static HashMap<Integer, Integer> cache = new HashMap<>();

    public static int f(int k, int n) {
        if (k == 1) {
            return 1;
        }
        int currentCoin = coin[k];
        int result = 0, i = 0;
        while ((n - i * currentCoin) >= 0) {
            result += f(k - 1, n - i * currentCoin);
            i++;
        }
        return result;
    }

    public static int waysToChange(int n) {
        return f(4, n);
    }

    public static void main(String[] args) {
        System.out.println(waysToChange(6));
        System.out.println(howManyCoins(6));
    }

    // 假定 f(n) 是组成n分情况的总和
    // 对于 每个硬币 COIN
    //   = 不使用 COIN + 使用 COIN
    //   = 使用0个COIN + 使用1个COIN + 使用2个COIN + ... + 使用i个COIN
    public static int howManyCoins(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        for (int coin : coins) {
            // 对于每个 COIN，可以组成 COIN 分，COIN + 1 分 ... n分
            for (int i = coin; i <= n; i++) {
                result[i] = (result[i] + result[i - coin]) % 1000000007;
            }
        }

        return result[n];
    }
}

不同的二叉搜索树

public class BinarySearchTree {
    // f(n) n个节点二叉搜索树
    // g(i) i为根节点，n个节点的二叉搜索树
    //      左子树一定有 i - 1 个元素 => 左子树有 f(i-1) 种情况
    //      右子树一定有 n - i 个元素 => 右子树有 f(n-i) 中情况
    // f(n) = g(1) + g(2) + g(3) + ... + g(n-1) + g(n)
    //      = f(0) * f(n-1) + f(1) * f(n-2) + f(2) * f(n-3) + ... + f(n-2) * f(1) + f(n-1) * f(0)

    // f(3) = g(1) + g(2) + g(3)
    // g(1) 左子树一定有0个元素，右子树一定有2个元素
    // g(2) 左子树一定有1个元素，右子树一定有1个元素
    // g(3) 左子树一定有2个元素，右子树一定有0个元素
    public static int recursion(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += recursion(i) * recursion(n - i - 1);
        }
        return result;
    }

    public static int loop(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        if (n >= 0) {
            result[1] = 1;
        }
        if (n >= 1) {
            result[2] = 2;
        }
        for (int i = 3; i <= n; i++) {
            // 计算第i个位置上的结果，第i个位置上的结果由前i-1个结果生成
            int sum = 0;
            for (int j = 0; j < i; j++) {
                sum += result[j] * result[i - j - 1];
            }
            result[i] = sum;
        }
        return result[n];
    }

    public static void main(String[] args) {
        System.out.println(loop(3));
    }
}

分治

把大问题分解成较小的问题，分别求解，之后将小问题的解合起来，同时设置一些退出条件

// 数组求和
public class ArraySum {
    public static int sum(int[] array) {
        return sum(array, 0, array.length);
    }

    public static int sum(int[] array, int start, int end) {
        if (start == end) {
            return array[start];
        }
        if (start > end) {
            return 0;
        }

        int mid = (start + end) / 2;
        return sum(array, start, mid - 1) + array[mid] + sum(array, mid + 1, end);
    }
}

Fork/Join 框架 => 分而治之的实例

// ForkJoinPool 解决数组求和
public class ArraySumForForkJoinPool {
    public static int sumParallel(int[] array) throws ExecutionException, InterruptedException {
        ForkJoinPool pool = new ForkJoinPool();
        return pool.submit(new SubArraySum(array, 0, array.length - 1)).get();
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        System.out.println(sumParallel(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));
    }
}

class SubArraySum extends RecursiveTask<Integer> {
    private final int[] array;
    private final int start;
    private final int end;

    public SubArraySum(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Integer compute() {
        if (start == end) {
            return array[start];
        }
        if (start > end) {
            return 0;
        }

        int mid = (start + end) / 2;
        SubArraySum leftArrayTask = new SubArraySum(array, start, mid - 1);
        SubArraySum rightArrayTask = new SubArraySum(array, mid + 1, end);

        leftArrayTask.fork();
        rightArrayTask.fork();

        System.out.println(Thread.currentThread().getName() + ", " + start + ", " + end);

        return leftArrayTask.join() + array[mid] + rightArrayTask.join();
    }
}

最大子数组和

class MaxSubarraySum {
    public static void main(String[] args) {
        System.out.println(new MaxSubarraySum().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    public int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);
    }

    public int maxSubArray(int[] nums, int start, int end) {
        if (start == end) {
            return nums[end];
        }
        if (start > end) {
            return 0;
        }
        if (start + 1 == end) {
            return Math.max(Math.max(nums[start], nums[end]), nums[start] + nums[end]);
        }
        int mid = (start + end) / 2;
        int leftMax = maxSubArray(nums, start, mid - 1);
        int rightMax = maxSubArray(nums, mid + 1, end);
        int midMax = getMidMax(nums, start, end, mid);
        return Math.max(Math.max(leftMax, rightMax), midMax);
    }

    private int getMidMax(int[] nums, int start, int end, int mid) {
        int leftSum = 0;
        int leftMax = Integer.MIN_VALUE;
        for (int i = mid - 1; i >= start; i--) {
            leftSum += nums[i];
            if (leftSum > leftMax) {
                leftMax = leftSum;
            }
        }

        int rightSum = 0;
        int rightMax = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= end; i++) {
            rightSum += nums[i];
            if (rightSum > rightMax) {
                rightMax = rightSum;
            }
        }
        return Math.max(leftMax, 0) + nums[mid] + Math.max(rightMax, 0);
    }
}

数组中出现次数超过一半的数字

class MajorityElement {
    public static void main(String[] args) {
        System.out.println(new MajorityElement().majorityElement(new int[]{4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5}));
    }

    public int majorityElement(int[] nums) {
        return majorityElement(nums, 0, nums.length - 1);
    }

    public int majorityElement(int[] nums, int start, int end) {
        if (start == end || start + 1 == end) {
            return nums[start];
        }

        int mid = (start + end) / 2;
        int left = majorityElement(nums, start, mid - 1);
        int right = majorityElement(nums, mid, end);
        if (left == right) {
            return left;
        }

        // 左右两侧数组中出现次数最多的数字不相同
        int leftCount = getCount(nums, start, mid - 1, left);
        int rightCount = getCount(nums, mid, end, right);
        if (leftCount > rightCount) {
            return left;
        }
        return right;
    }

    public int getCount(int[] nums, int start, int end, int target) {
        return (int) IntStream.range(start, end + 1).filter(i -> nums[i] == target).count();
    }
}

WordCount

class WordCount {
    // 统计一个文件中的每个单词出现的数量
    // 例如：I am a good boy a
    // I -> 1
    // am -> 1
    // a -> 2
    // ...
    public static Map<String, Long> sumParallel(List<File> files) throws ExecutionException, InterruptedException {
        ForkJoinPool pool = new ForkJoinPool();
        return pool.submit(new CountWord(files)).get();
    }
}

class CountWord extends RecursiveTask<Map<String, Long>> {
    private final List<File> files;

    public CountWord(List<File> files) {
        this.files = files;
    }

    @Override
    protected Map<String, Long> compute() {
        if (files.isEmpty()) {
            return Collections.emptyMap();
        }
        if (files.size() == 1) {
            return count(files.get(0));
        }

        int mid = files.size() / 2;

        CountWord left = new CountWord(files.subList(0, mid));
        CountWord right = new CountWord(files.subList(mid, files.size()));

        left.fork();
        right.fork();

        return Stream.of(left.join(), right.join())
                .flatMap(map -> map.entrySet().stream())
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        Long::sum
                ));
    }

    // 统计一个文件的单词
    private Map<String, Long> count(File file) {
        String str;
        try {
            str = new String(Files.readAllBytes(file.toPath()));
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return Stream.of(str.split("//s+")).collect(Collectors.groupingBy(word -> word, Collectors.counting()));
    }
}

贪心

买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += (prices[i] - prices[i - 1]);
            }
        }
        return profit;
    }
}

无重叠区间

class EraseOverlapIntervals {
    public static void main(String[] args) {
        System.out.println(new EraseOverlapIntervals().eraseOverlapIntervals(new int[][]{new int[]{1, 100}, new int[]{11, 22}, new int[]{1, 11}, new int[]{2, 12}}));
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
        int result = 0;
        int[] current = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < current[1]) {
                // 重叠了
                result += 1;
            } else {
                current = intervals[i];
            }
        }
        return result;
    }
}

回溯

决策树

八皇后问题

leetcode

class SolveNQueens {
    public static void main(String[] args) {
        System.out.println(new SolveNQueens().solveNQueens(8).size());
    }

    public List<List<String>> solveNQueens(int n) {
        return solveNQueens(n, n);
    }

    // 解决N皇后问题的第x层
    // 在解决第x层之前，假设第x-1层已经得到的解决
    public List<List<String>> solveNQueens(int n, int x) {
        if (x == 1) {
            // 正在棋盘的第1行摆放皇后
            List<List<String>> solutionOfFirstRow = new ArrayList<>();

            for (int i = 1; i <= n; i++) {
                solutionOfFirstRow.add(Collections.singletonList(queenAt(i, n)));
            }

            return solutionOfFirstRow;
        }

        // 每个元素代表一个解
        // 其中的每个String都是N长度的
        // 例如：现在正在解决4皇后问题的第3层，那么假设第2层已经得到了解决
        // [
        //   [".Q.."]
        //   ["...Q"]
        // ]
        List<List<String>> resultOfXMinus1 = solveNQueens(n, x - 1);

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

        for (List<String> solutionOfXMinus1 : resultOfXMinus1) {
            // 对于上一行的每个可行的解，摆放N次棋子，检查可行性，若可行，将其加入结果集中
            for (int i = 1; i <= n; i++) {
                // 第x层有n种可以摆放的方案
                if (isValid(solutionOfXMinus1, i, x)) {
                    List<String> solution = new ArrayList<>(solutionOfXMinus1);
                    solution.add(queenAt(i, n));
                    result.add(solution);
                }
            }
        }

        return result;
    }

    // 若把皇后摆放在第x行第i列的位置，不和之前的解冲突，则返回 true，否则返回 false
    // 所有的坐标都是从1开始的
    private boolean isValid(List<String> solutionOfXMinus1, int i, int x) {
        for (int rowIndex = 0; rowIndex < solutionOfXMinus1.size(); rowIndex++) {
            // 例如： "...Q"
            String row = solutionOfXMinus1.get(rowIndex);
            int queenRowIndex = rowIndex + 1;
            int queenColIndex = row.indexOf("Q") + 1;

            // 在同一列
            if (queenColIndex == i) {
                return false;
            }

            // 在对角线
            if (((queenRowIndex + queenColIndex) == (x + i)) || ((queenRowIndex - queenColIndex) == (x - i))) {
                return false;
            }

        }
        return true;
    }

    // 创造一个长度为n的字符串，其中第i列是Q
    private String queenAt(int i, int n) {
        StringBuilder item = new StringBuilder();
        for (int j = 1; j <= n; j++) {
            item.append(i == j ? "Q" : ".");
        }
        return item.toString();
    }
}

应用

计算匹配的括号

public class ParenthesisMatching {
    // [] => valid
    // {[]} => valid
    // [(]) => invalid

    public static void main(String[] args) {
        System.out.println(isValid("[]"));
        System.out.println(isValid("{[]}"));
        System.out.println(isValid("{[]}()"));
        System.out.println(isValid("{[]}([)]"));
    }

    public static boolean isValid(String string) {
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put('[', ']');
        bracketMap.put('(', ')');
        bracketMap.put('{', '}');

        if (string == null || string.isEmpty()) {
            return true;
        }
        Deque<Character> stack = new ArrayDeque<>();
        char[] chars = string.toCharArray();
        for (char ch : chars) {
            if ("[{(".indexOf(ch) >= 0) {
                stack.push(ch);
                continue;
            }
            Character head = stack.peek();
            if ("]})".indexOf(ch) >= 0) {
                if (head != null && ch == bracketMap.get(head)) {
                    stack.pop();
                    continue;
                } else {
                    return false;
                }
            }
            throw new IllegalArgumentException("参数非法：" + string);
        }
        return stack.isEmpty();
    }
}

知识点

TreeSet 的复杂度 == O(log(n)) => ArrayList -> TreeSet => 把算法复杂度从线性时间下降到对数时间
机械硬盘转速单位 RPM(Revolution(s) Per Minute)，每分钟转速
哈希桶 | 哈希表的缺陷 => 在有限的容量中存放无限多可能的对象 => 一定存在若干个对象的哈希值相同，需要放置在同一个位置上 => 使用链表串起来
学院派经典哈希表的实现
- 数组来存储哈希表中的元素
- 链表处理碰撞
- () => parentheses
- [] => square bracket
- {} => curly bracket
二叉树可以退化至链表，此时时间复杂度由O(log(n)) 变为 O(n) =>
1024个数据，平衡二叉树 O(log(n)) 1024 -> 10, 链表O(n) 1024 -> 1024
算法题 =>
1. 沟通，理解题意
2. 给出暴力解(不动脑子)
3. 分析问题，沟通
4. 给出正常的算法解 => 优化(剪枝)

算法与数据结构

概述

算法的复杂度

时间复杂度

线性时间复杂度

对数时间复杂度

遍历二叉树

空间复杂度

带缓存(备忘录)的 斐波那契数列 求值

数据结构

数组 | 线性表

二分查找

链表 & 双向链表

遍历链表数据

翻转链表

判断链表是否成环

栈 Stack

手写一个栈的实现

队列 Queue

手写一个队列的实现

哈希表

二叉树

二叉树前序遍历(根节点 => 左节点 => 右节点)

二叉树中序遍历(左节点 => 根节点 => 右节点)

二叉树后序遍历(左节点 => 右节点 => 根节点)

二叉树广度优先遍历 BFS

算法

排序算法

快速排序

WordCount

应用

知识点

猜你喜欢

热点阅读

带缓存(备忘录)的斐波那契数列求值