算法：目录

发表于 更新于 分类于
本文字数： 5k 阅读时长 ≈ 9 分钟

算法

HackerRank

思路总结

算法与数据结构是相互分离的。

算法是一个接口，底层的数据结构是一个接口，并且使用数据结构接口去实现所需要的算法接口。

解决问题：

解决问题本身是一个相对的概念，是探讨解决一个问题的解决方案。

正确还包含优化、代码规范、封装性、容错性等。

  • 首先思考数据结构本身能否解决问题。
    • 能，则说明问题符合数据结构的特性，直接使用数据结构解决问题。
    • 不能，则思考哪种数据结构对问题有一些帮助，回想数据结构都能解决哪些类型的问题。并下一步：
  • 思考算法需要应用的业务场景，数据拥有哪些特征。
    • 如果有大量重复数据，则可以选择三路快速排序。
    • 如果都是独特的，则普通的快排就可以。
    • 如果数据量很小，则可以使用插入排序。
    • 如果数据是分数之类即有一个限定范围0-100，则可以使用计数排序、桶排序。
    • 如果是要求稳定性，则可以使用归并排序。
    • 如果是链表组织的，则可以使用归并排序。
    • 如果数据量很大，则需要使用外排。
  • 思考常用算法是否能够解决问题。
    • 例如排序、查找、递归算法。它们是否符合这些常用算法的特性。
  • 思考算法思想，看能否匹配。
  • 写算法先写接口，设计好算法的抽象接口，在抽象的角度上解决问题。
  • 利用数据结构实现算法，解决问题，只要确定实现了抽象的语义，那么一定是可以解决问题的。

常见问题

  • 注意题目中的条件。
    • O(nlogn)，则可能是分治。
    • 无需额外的空间，则开一个额外的空间。
    • 规模是10000，则On^2算法。
    • 有序数组，则二分等方法是否有帮助。
  • 测试用例。
  • 暴力解法。

基础数据结构

线性

  • 数组、动态数组。
  • 链表、栈、队列。
  • 哈希表。

树

  • 二叉树。
  • 二叉查找树、AVL树、红黑树、B树、B+树、B*树。
  • Segment Tree。
  • 多叉树：
    • Trie 树。
    • 并查集。

图

邻接表、邻接矩阵。

串

高层数据结构

高层数据结构指定义好这种数据结构相应的使用接口，包括其本身维持的一些性质，具体的底层实现可以是多种多样的。

栈与队列

底层实现：

  • 数组、链表

概述

  • 优先队列。

适用性

应用场景

集合Set

概述

Set：承载元素的容器，每个元素只能存在一次。

分类

  • 有序集合。有序集合中的元素具有顺序性，一般基于搜索树实现。可以轻易查找前一个元素等，存在一些增强功能。
  • 无序集合。哈希表、链表等。
  • 多重集合。可以容纳重复的元素。

适用性

  • 实现元素去重。

应用场景

  • 客户统计、词汇量统计等。

操作：

  • boolean contain(E);
  • void add(E);

底层实现：

  • 数组、链表。
  • 树：
    • 二分搜索树（AVL、红黑树等）
    • 速度次快。
  • 哈希表。
    • 速度最快。

映射Map

概述

分类

  • 有序映射。
  • 无序映射。

适用性

应用场景

操作：

底层实现：

  • 数组、链表。
  • 二分搜索树。

算法思想

分治

  • 从问题的最小解开始，左右问题相互独立
  • 利用递归（树是一种经典问题）

贪心

贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

因此当前状态的最优解，推算到下一个状态的最优解，也是最优解，因此最终解最优。

回溯

  • Backtracking 主要用于求解 排列组合 问题
  • 例如有 { ‘a’,’b’,’c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。
  • 因为 Backtracking 不是立即就返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
    • 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
    • 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

动态规划

后面的状态依赖于前面已知的状态，根据前面已知，以及最新的数字，可以对后面状态进行推导。

分支限定

常用算法

排序与查找

  • 快速排序
    • Kth Element 问题，使用快速排序的 partition() 进行实现。
  • 堆排序
    • 求解 TopK Elements 问题，通过维护一个大小为 K 的堆，堆中的元素就是 TopK Elements。
    • Kth Element 问题，堆顶元素就是 Kth Element。
  • 桶排序
    • 出现频率最多的 k 个数

递归

双指针

  • 遍历数组
  • 寻找链表的环
  • 节约遍历时间
  • 反转，回文

Graph

广度优先BFS

  • 可以求解最短路径等 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径。
  • 队列：用来存储每一轮遍历得到的节点；
  • 标记：对于遍历过的节点，应该将它标记，防止重复遍历。
  • java pair,配对，用于返回两个值

深度优先DFS

  • 用来求解 可达性 问题。
  • 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
  • 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

算法基础

时间复杂度

常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作。

时间复杂度为一个算法流程中，常数操作数量的指标。常用O来表示。

  • 在常数操作数量的表达式中，只要高阶项，不要低阶项
  • 也不要高阶项的系数
  • 剩下的部分如果记为f(N)，则时间复杂度为O(f(N))
    • 如果存在两个变量，在不知道两个变量的样本量的大小时，需要将两个变量留下，如O（MlogM）+O(M+N)
  • 当由于数据情况不一致，而复杂度不同，则依靠最差时间复杂度估计。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间(指标一致)，即常数项时间

空间复杂度

空间复杂度是指在原来的样本量基础上，额外申请的空间。

递归的本质

递归行为是一种系统压栈，所以任何递归问题都可以改成非递归，改为人工压栈即可。

一种分治的思想。寻找最大值，数组中左边的最大值和右边的最大值当中的最大值一定是全局的最大值。

时间复杂度

master公式T(N)=a*T(N/b)+O(N^d)

  • log(b,a)>d->复杂度为O(N^log(b,a))
  • log(b,a)==d->复杂度为O(N^d*logN)
  • log(b,a)<d->复杂度为O(N^d)

对数器

作用

  • 在online上没有题目，自己验证算法是否正确
  • 在笔试的时候，小样本测试过了。面对大样本报错，找出错误的位置。
    • 验证贪心策略的正确与否

组成

  • 一个随机样本生成器
  • 正确的方法r与最好的方法b
  • 判断两个方法是否正确的方法equals
  • 打印出错特殊case的方法print

步骤

  1. 有一个想要测试的方法b
  2. 实现一个绝对正确但是复杂度不好的方法r
    1. 时间复杂度差的算法很暴力，容易写出。因此绝对正确的算法是可以写出的。
    2. 但是在笔试的时候是过不了的。因此需要算法a
    3. 若方法b不是绝对正确，则在对比的过程中迭代方法修改
  3. 实现随机样本产生器
  4. 实现比对的方法
  5. 把方法a和方法b比对多次来验证方法a是否正确
  6. 如果一个样本使得比对出错，打印样本分析哪个方法出错
  7. 当样本数量很多时比对测试依然正确，则可以确定方法a已经正确

示例

要测的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void bubbleSort(int[] arr)
{
    if (arr==null || arr.length < 2)
        return;
    for (int end = arr.length - 1;end>0; end--)
    {
        for (int i = 0; i < end; i++)
        {
            if (arr[i] > arr[i+1])
                swap(arr, i, i+1);
        }
    }
}

绝对正确的方法

1
2
3
4
// 可以直接用一些库函数来进行测试
public static void rightMethod(int[] arr){
    Arrays.sort(arr);
}

实现一个随机样本发生器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 随机数生成器
public static int[] generateRandomArray(int size, int value)
{
//Math.random() -> double [0,1)
//(int) ((size + 1) * Math.random()) -> [0,size]整数
// 生成长度随机[0, size]的数组
int[] arr = new int[(int) ((size+1) * Math.random())];
for (int i = 0; i < arr.length; i++)
{
    // 一个随机数减去另一个随机数，生成[-value, value]的随机数
    arr[i] = (int) ((value+1) * Math.random()) - (int) (value * Math.random());
}
return arr;
}

实现对比的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 判断两个数组是否相等
public static boolean isEqual(int[] arr1, int[] arr2)
{
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
        return false;
    if (arr1 == null && arr2 == null)
        return true;
    if (arr1.length != arr2.length)
        return  false;
    for (int i = 0; i < arr1.length; i++)
    {
        if (arr1[i] != arr2[i])
            return false;
    }
    return true;
}

main方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void main(String[] args) 
{
    int testTime = 500000;
    int size = 10;
    int value = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++)
    {
        int[] arr1 = generateRandomArray(size, value);
        int[] arr2 = copyArray(arr1);
        int[] arr3 = copyArray(arr1);
        bubbleSort(arr1);
        rightMethod(arr2);
        if (!isEqual(arr1, arr2))
        {
            succeed = false;
            printArray(arr3);
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "error----");
    int[] arr = generateRandomArray(size, value);
    printArray(arr);
    bubbleSort(arr);
    printArray(arr);

}

比较器

实现Comparable接口

参考