数据结构与算法基础

发表于 | 分类于

复杂度、对数器、二分法、异或运算

常见的评估算法优劣的核心指标：

  • 时间复杂度(流程决定)
  • 额外空间复杂度(流程决定)
  • 常数项时间(实现细节决定)

基本步骤

什么是常数时间的操作？
如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间，这样的操作被称为常数时间的操作。

常见的常数时间操作：

  • 算数运算(+ - * % /)等
  • 常见的位运算(>> >>> << | & ^)等
  • 赋值、比较、自增、自减操作
  • 数组寻址操作

执行时间固定的操作都是常数时间的操作，执行时间不固定的操作，都不是常数时间的操作

JAVA中LinkedList的get(i)就不是常数时间的操作

如何确定算法流程的总操作数量与样本数量之间的表达式关系？

  1. 想象该算法流程所处理的数据状况，要按照最差情况来
  2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作
  3. 如果数据为N,看看基本动作的数量和N是什么关系

如何确定算法流程的时间复杂度？
当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。
记为O(忽略掉系数的高阶项)

时间复杂度

时间复杂度就是来衡量在整个流程中发生了多少次的常数操作这件事.

时间复杂度的意义：
当我们要处理的样本很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的；真正重要的是最高阶项

时间复杂度是衡量算法流程的复杂度的一种指标，该指标只与数据量有关，与过程之外的优化无关

常见的时间复杂度排序(从好到差): O(1) > O(logN) > O(N) > O(N*logN) > O(N²) O(N³)… O(N^k) > O(2^N) O(3^N)… O(k^N) > O(N!)

基本排序

  • 选择排序O(n²)： 轮询数组，将最小的数放到最前面
  • 冒泡排序O(n²)： 数组之间两两元素顺序交换，大的值放后面
  • 插入排序：将i位置上的数与前面的数相比较，只要前面的数比它大，就交换

注：

  • 算法的过程和具体的语言无关
  • 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
  • 一定要确保在拆分算法的流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己用过的每一个系统api都是非常熟悉，否则会影响你对时间复杂度的估算

额外空间复杂度

实现算法流程的过程中，你需要开辟一些新的空间来支持你的算法流程

作为输入参数的空间，不算额外空间
作为输出结果的空间，不算额外空间

因为输入参数和输出结果都是必要的、和现实目标有关的，所以都不算额外空间

除上述以外，你的流程中如果还需要开辟空间才能继续下去，这部分的空间就是额外空间

如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)

常数项时间

时间复杂度这个指标是忽略低阶项和所有常数系数的。
但同样的时间复杂度的流程，运行时实际也并不是一样好。
时间复杂度只是一个重要指标，如果两个时间复杂度一样的算法还要咋时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

两个流程的常数项时间进行比拼不采用理论分析，直接生成随机数据测试

最优解

一般情况下认为，解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解

一般最优解都是忽略掉常数项的，因为常数项这个因素只决定了实现层次的优化和考虑，和怎么解决整个问题的思想无关。

对数器

  1. 你想要测的方法a
  2. 实现复杂度不好，但是容易实现的方法b
  3. 实现一个随机样本产生器
  4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
  5. 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b
  6. 当样本数量很多时，比对测试依然正确，可以确定方法a已经正确

二分法

算术运算怎么转换成位运算？

  • 在一个有序数组中，找某个数是否存在
  • 在一个有序数组中，找>=某个数最左侧的位置
  • 在一个有序数组中，找<=某个数最右侧的位置
  • 局部最小值问题

异或运算

异或运算： 相同为0，不同为1
同或运算： 相同为1，不同为0

异或运算其实就是无进位的相加，即产生了进位则忽略成0

异或运算的性质:

  1. 0 ^ N == N N ^ N == 0
  2. 异或运算满足交换律和结合律

异或运算的应用

  1. 如何不用额外变量交换两个数？
    int a = m;
    int b = n;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    最终结果： a = n; b = m;

    以上的交换只能a b的值为两个不同的内存空间才能操作，若a=b=arr[i]则不能用以上方法，因此实际使用时还是使用临时变量temp进行交换

  2. 一个数组中有一种数出现了奇数次，其他都出现了偶数次，怎么找到并打印这种数？

    1
    2
    3
    4
    int eor = 0;
    for(int i = 0; i < arr.length; i++) {
    	eor = eor ^ arr[i];
    }

    以上代码运行出来最终得到的eor的值就是出现了奇数次的数

  3. 如何把一个int类型的数提取出最右侧的1来？

    例如：int N = 00…1101010000

    将最右侧的1提取出来的结果是：00…0000010000

    N & ((~N) + 1)

    先将N取反，取反后的值+1，最后将这个值与N进行与运算得到的结果就是只保留最右侧的1其他位为0

  4. 一个数组中有两种数出现了奇数次，其他都出现了偶数次，怎么找到并打印这两种数？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    	
    // 使用eor=0将所有数都^一遍，最终得到的结果 eor = a ^ b
    // 且eor != 0,表示eor必然有一个位置上是1
    int eor = 0;
    for(int i = 0; i < arr.length; i++) {
    	eor ^= arr[i];
    }

    // 提取eor中最右侧的1
    int rightOne = eor ^ ((~eor) + 1);

    // 定义一个新的变量onlyOne=0,将所有与eor最右侧是1同类的数进行操作
    int onlyOne = 0;
    for(int i = 0; i < arr.length; i++) {
    	if((arr[i] & rightOne) != 0) {
    		// (arr[i] & rightOne) != 0表示arr[i]在rightOne中为1的位数上也是1
    		onlyOne ^= arr[i];
    	}
    }

    // 以上得到的onlyOne的结果是a或者b
    // 出现奇数次的两个数a b 分别是 onlyOne和 eor^onlyOne

链表结构、栈、队列、递归行为、哈希表

链表结构

  • 单向链表节点结构(可以实现成范型)

    1
    2
    3
    4
    5
    6
    7
    8
    9

    public class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

  • 双向链表节点结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    public class DoubleNode {
    	public int value;
    	public DoubleNode last;
    	public DoubleNode next;

    	public DoubleNode(int data) {
    		value = data;
    	}
    }

单向链表和双向链表最简单的练习

  • 单链表和双链表如何反转

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    	
    public class Code_ReverseList {
        /* 单向链表单反转 */
        // 1. 定义单向链表
        class Node {
            public int value;
            public Node next;

            public Node(int data) {
                value = date;
            }
        }

        // 2. 反转单向链表
        public Node reverseLinkedList(Node head) {
            Node pre = null;
            Node next = null;

            while(head != null) {
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
        }

        /*双向链表反转*/
        // 1. 定义双向链表
        class DoubleNode {
            public int value;
            public DoubleNode last;
            public DoubleNode next;

            public DoubleNode(int data) {
                value = data;
            }
        }

        // 2. 反转双向链表
        public DoubleNode reverseDoubleList(DoubleNode head) {
            DoubleNode pre = null;
            DoubleNode next = null;
            while(head != null) {
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }
    }

  • 删除给定值

    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
    28
    29
      /**
      * 指定删除head中值为num的节点
      */
    public Node removeValue(Node head, int num) {
        // 首次遍历，过滤头节点为num的情况
        // 找到第一个不需要删的位置
        while(head != null) {
            if(head.value != num) {
                break;
            }else {
                head = head.next;
            }
        }

        Node pre = head;
        Node cur = head;

        while(cur != null) {
            if(cur.value == num) {
                // 当前值为num,将当前值的下一位赋于pre.next
                pre.next = cur.next;
            }else {
                // 当前值保留,记录当前值
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

栈和队列

逻辑概念

  • 栈： 先进后出

  • 堆： 先进先出

实际实现

  • 双向链表实现

  • 数组实现

常见面试题

  1. 怎么用数组实现不超过固定大小的队列和栈

    栈： 正常使用

    队列： 环形数组

  2. 实现一个特殊的栈，在基本功能的基础上再实现返回栈中最小元素的功能

递归

Master公式：

$$
T(N) = a * T(\frac{N}{b}) + O(N^d)
$$

  • a b d 均为常数

假设整个递归的数据量是N，递归行为的所有子问题的规模一律能变成更小的规模（N/b）(如果有一次递归行为的子规模不能变成N/b，则不适用上述公式),将子规模调用了a次，除去子规模调用之外的时间复杂度是$O(N^d)$。只要满足上述规则的递归就适用上述公式。

对于满足上述公式的递归有以下结论：

  • $\log_{b}^{a} > d$ 时间复杂度为$O(N^(\log_{b}^{a}))$
  • $\log_{b}^{a} < d$ 时间复杂度为$O(N^d)$
  • $\log_{b}^{a} = d$ 时间复杂度为$O(N^d * logN)$

哈希表

哈希表增删改查在使用时时间复杂度都是O(1)

哈希表在使用层面上可以理解为一种集合结构

  • 如果只有key没有value，可以使用HashSet结构
  • 如果既有key又有value，可以使用HashMap结构
  • HashMap和HashSet实际结构是一样的
  • 放入哈希表的东西，如果是基础类型，内部按照值传递，内存占用是这个东西的大小
  • 放入哈希表的东西，如果不是基础类型，内部按照引用传递，内存占用是8字节

有序表

java中的treeMap是有序表

有序表的增删查改的时间复杂度是O(logN)

归并排序与随机快排

归并排序

  • 整体是递归，左边排好序 + 右边排好序 + merge让整体有序
  • 让整体有序的过程里用了排外序的方法
  • 利用master公式来求解时间复杂度
  • 可以用非递归实现

常见面试题

在一个数组中，一个数左边比它小的数的总和叫数的小和，所有数的小和累加起来，叫做数组小和，求数组小和。

例： [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

求每个数左边有多少数大或者右边有多少数大之类的问题可以用mergesort

随机快排

Partition过程：

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

荷兰国旗划分问题

随机快排的时间复杂度分析

  • 通过分析知道，划分值越靠近中间性能越好；越靠近两边性能越差
  • 随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件
  • 把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N
  • 那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望

时间复杂度O(N * logN),额外空间复杂度O(logN)都是这么来的

堆与比较器

堆

堆结构：

  • 用数组实现的完全二叉树结构
  • 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
  • 完全二叉树中如果每棵子树的最小值都在最顶部就是小根堆
  • 堆结构的heapInsert与heapify操作
  • 堆结构的增大和减少
  • 优先级队列结构就是堆结构

堆排序： 将无序数组调整成大根堆，再将第一个数与最后一个数交换，交换后堆的大小–，对剩下的数组进行heapify,最终的数组是从小到大的有序数组

  • 让整个数组都变成大根堆的结构建立堆的过程：从上到下的方法时间复杂度是O(N*logN);从下到上的方法，时间复杂度是O(N)
  • 把堆的最大值和堆末尾的值交换，然后减少堆的大小后再去调整堆，周而复始，时间复杂度是O(N*logN)
  • 堆的大小减小成0之后，排序完成

Java中的PriorityQueue底层默认是小根堆

与堆相关的题目

已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
请选择一个合适的排序策略，对这个数组进行排序。

比较器

任何比较器遵循-1表示前者比后者小，0表示两者相等，1表示后者比前者大

  • 比较器的实质是重载比较运算符
  • 比较器可以很好的用在特殊标准的排序上
  • 比较器可以很好的应用在根据特殊标准排序的结构上
  • 写代码变得容易，还用于泛型编程

trie、桶排序和排序总结

前缀树：

  1. 单个字符串中，字符从前到后的加到一颗多叉树上
  2. 字符放在路上，节点上有专属的数据项（常见的是pass和end值）
  3. 所有样本都这样添加，如果没有路就新建，如有路就复用
  4. 沿途节点的pass值增加1，每个字符串结束时来到的节点end值加1

桶排序

计数排序 & 基数排序

  • 桶排序思想下的排序都是不基于比较的排序
  • 时间复杂度为O(N),额外空间复杂度O(M)
  • 应用范围有限，需要样本的数据满足桶的规划

桶排序是一种思想，计数排序和基数排序是实现方法

基于比较的排序有更广泛的用途

排序算法的稳定性

稳定性是指同样大小的样本在排序之后不会改变相对次序

对基础类型来说，稳定性毫无意义

对非基础类型来说，稳定性有重要意义

有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的

排序算法总结

时间复杂度 额外空间复杂度 稳定性
选择排序 $O(N^2)$ O(1) 无
冒泡排序 $O(N^2)$ O(1) 有
插入排序 $O(N^2)$ O(1) 有
归并排序 $O(N * logN)$ O(N) 有
随机快排 $O(N * logN)$ O(logN) 无
堆排序 $O(N * logN)$ O(1) 无
计数排序 O(N) O(M) 有
基数排序 O(N) O(M) 有

排序算法的选择

  1. 不基于比较的排序，对样本数据有严格要求，不易改写
  2. 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
  3. 基于比较的排序，时间复杂度的极限是O(N*logN)
  4. 时间复杂度O(N * logN)、额外空间复杂度低于O(N)、且稳定的基于比较排序是不存在的
  5. 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

常见的坑

  1. 归并排序的额外空间复杂度可以变成O(1),“归并排序 内部缓存法”，但是将变得不在稳定
  2. “原地归并排序”是垃圾帖，会让时间复杂度变成O(N^2)
  3. 快速排序稳定性改进，”01 stable sort”,但是会对样本数据要求更多
    例如： “在整型数组中，请把奇数放在数组的左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变
    时间复杂度做到O(N),额外空间复杂度做到O(1)” 实际partition过程做不到稳定性

链表相关面试题

  • 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
  • 对于面试，时间复杂度依然在第一位，但是一定要找到空间最省的方法

链表面试题常用数据结构与技巧

  1. 使用容器（哈希表、数组等）
  2. 快慢指针

面试题

  1. 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
  2. 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
  3. 输入链表头结点，奇数长度返回中点前一个，偶数长度返回上中点前一个
  4. 输入链表节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

常见面试题

  • 将单向链表按某值划分成左边小、中间相等、右边大的形式
    1) 把链表放入数组里，在数组上做partition（笔试用）
    2) 分成小、中、大三部分，再把各个部分之间串起来（面试用）

  • 给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null

    要求：如果两个链表长度之和为N，时间复杂度请达到O（N），额外空间复杂度请达到O(1)

  • 能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉。

    要删除链表的节点，必须给头节点，否则出现很多引用相关的问题

二叉树

二叉树的先序、中序、后序遍历

先序： 任何子树的处理顺序都是，先头节点、再左子树、然后右子树

中序： 任何子树的处理顺序都是，先左子树、再头节点、然后右子树

后序： 任何子树的处理顺序都是，先左子树，再右子树、然后头节点

递归序：

先序 中序 后序本质是递归序，只是打印顺序不同，第一次到达一个节点打印就是先序，第二次打印中序，第三次打印后序

实现二叉树按层遍历

  1. 其实就是宽度优先遍历，用队列
  2. 可以通过设置flag变量的方式来发现某一层的结束

二叉树的序列化和反序列化

序列化： 线性形式保存二叉树的结构

  1. 可以使用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化
  2. 用了什么方式序列化，就用什么样的方式反序列化

二叉树面试题

  1. 如何设计一个打印整棵树的函数

  2. 二叉树结构如下定义：

    1
    2
    3
    4
    5
    6
    Class Node {
        V value;
        Node left;
        Node right;
        Node parent;
    }

    给你二叉树中的某个节点，返回该节点的后继节点

    后继节点： 一个二叉树中，中序遍历的节点中，一个节点的下一个节点；

    暴力解法： 给定一个节点，获取这个节点的父节点，一直到根节点，再进行中序遍历，遍历到给定的节点下一个节点就是后续节点

    解题思路：

    如果一个节点没有右数，就往上找，如果当前节点是父节点的右孩子，则继续往上找，直到找到一个节点是其父节点的左孩子，那么这个父节点就是指定节点的后继节点

    整棵树的最后一个节点是没有后继的，因此如果一直往上找找不到左结点，说明指定的这个节点是最后的一个节点，返回空

  3. 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折一次，压出折痕后展开。此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。如果从纸条的下边向上方连续对折两次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

    给定一个输入的参数N，代表纸条都是从下边向上方连续对折N次。请从上到下打印所有折痕的方向。

    例如N=1时，打印down; N=2时，打印 down down up;

    从上到下打印顺序实际上就是一个二叉树的中序遍历

    暴力解法： 建立一个2^n-1的二叉树

    解题思路：

    此二叉树的规律： 头节点是凹节点，左节点都是凹节点，右节点都是凸节点；

二叉树的递归套路

可以解决面试中绝大多数的二叉树问题，尤其是树形dp问题

本质是利用递归遍历二叉树的便利性

  1. 假设以X节点为头，假设可以向X左树和X右树要任何信息
  2. 在上一步的假设上，讨论以X为头节点的树，得到答案的可能性
  3. 列出所有可能性后，确定到底需要向左树和右树要什么信息
  4. 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
  5. 递归函数都返回S，每一颗子树都这么要求
  6. 写代码，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息

二叉树的递归实践

  1. 给定一颗二叉树的头节点head,返回这颗二叉树是不是平衡二叉树

    X为头节点，需要知道左树右树的信息为：

    • 左/右树是否平衡
    • 左/右树的高度差是否不超过1

  2. 给定一个二叉树的头节点head, 任何两个节点之间都存在距离，返回整颗二叉树的最大距离

  3. 给定一个二叉树的头节点head,返回这颗二叉树中最大的二叉搜索子树的头节点

    搜索二叉树： 整棵树上没有重复值，左树的值比头节点小，右树值比头节点大，每棵子树都满足

    题目中的二叉树并不表示搜索二叉树，需要找的是满足搜索二叉树的子树

  4. 给定一棵二叉树的头节点head，返回这棵二叉树中是不是完全二叉树

    思路：

    • 任何节点，有右无左，返回false

    • 一旦遇到左右孩子不双全，后续遇到的所有节点必须为叶

      递归套路：

      每棵树返回是否是满二叉树、是否是完全二叉树、高度信息

  5. 给定一棵二叉树的头节点head,和另外两个节点a和b，返回a和b的最低公共祖先

    公共祖先： 二叉树中某两个节点往上走初次交汇的父节点

贪心算法

  • 最自然智慧的算法
  • 用一种局部最功利的标准，总是做出当前看来是最好的选择
  • 难点在于证明局部最功利的标准可以得到全局最优解
  • 对于贪心算法的学习主要以增加阅历和经验为主

贪心算法求解的标准过程

  1. 分析业务
  2. 根据业务逻辑找到不同的贪心策略
  3. 对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性，这往往是特别困难的，要求数学能力很高且不具有统一的技巧性

贪心算法的解题套路

  1. 实现一个不依靠贪心策略的解法X,可以用最暴力的尝试
  2. 脑补出贪心策略A、贪心策略B、贪心策略C…
  3. 用解法X和对数器，用实验的方法得知哪个贪心策略正确
  4. 不要去纠结贪心策略的证明

堆和排序是完成贪心策略最常用的技巧

给定一个由字符串组成的数组strs,必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果

字典序： 当长度一样长时，字符串看成是k进制的正数进行比较；长度不一样时，补0将长度变成一样长

Java中的compareTo方法比较的就是字典序

并查集结构和图相关的算法

并查集

  • 有若干个样本a b c d…假设类型是V
  • 在并查集中一开始认为每个样本都在单独的集合里
  • 用户可以在任何时候调用如下两个方法：
    boolean isSameSet(V x, V y): 查询样本x和样本y是否属于一个集合
    void union（V x, V y）： 把x和y各自所在集合的所有样本合并成一个集合
  • isSameSet和union方法的代价越低越好

图

  • 由点的集合和边的集合构成
  • 虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
  • 边上可能带有权值

图的拓扑排序算法

  • 在图中找到所有入度为0的点输出
  • 把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始

  • 图的所有店都被删除后，依次输出的顺序就是拓扑排序

    要求：有向图且其中没有环
    应用： 事件安排、编译顺序