Note for Data Structure in CPP

Posted on | Edited on | In | | Views:
Symbols count in article: 6.2k | Reading time ≈ 6 mins.

刷题中遇到了瓶颈，图论的很多知识只记得有这么个东西，但具体不记得了，一翻课件发现大二上的『算法与数据结构』中很多东西都能找到，就暂停一下，把这部分知识重新过一遍。暂时只记录关键的算法，至于各种数据结构的实现就只是一笔带过了。（原本想翻译成英文的=_=

Stack

Feature

  • Last in First out: all insertions and deletions of entries are made at one end.
  • CPP: #include <stack>, supports push, pop, top, empty.

    Implementation

  • 存储方式：必须表现元素之间的关系、利于栈运算的实现。
    -> 数组：写起来容易，很方便；但当规模到达数组容量上限，需要扩容并复制一波过去。
    -> 链表：动态、灵活、可任意扩容；但写法比数组复杂。（栈顶对应的是链表头部）

    Application

  • 括号匹配：一个只包含三种括号的字符串，判断各个括号是否合法匹配。
    Solution：左括号入栈，出现右括号就与栈顶匹配，成功则弹出。
  • 算数表达式的转换：前缀(polish)、中缀、后缀(reverse polish)。口诀分别是『根左右』、『左根右』、『左右根』。
    将中缀转成后缀：操作数直接输出到结果，左括号和操作符入栈；遇到右括号，则一直弹出栈顶元素直到左括号，输出这部分操作符到结果；还有一种情况需要弹出，就是栈中的操作符必须满足低优先级的在栈底，因此当新进入的操作符优先级低于栈顶，则需要一直弹出不符合的直到空或左括号（相同优先级也弹出），按弹出顺序将这些操作符放入结果中，最后再将新的操作符入栈。

Queue

Feature

  • First in First out: Additions at one end and deletion at the other.
  • CPP; #include <Queue>, supports append, serve, retrieve, empty.

    Implementation

  • 数组：使用circular arrays节省空间，用索引front表示队首，rear表示下一个要插入的位置。注意当队为空时和队满时，都是front == (rear + 1) % max，因此需要引入一个flag标记队是否满了。

    Application

  • Palindrome：（虽然我觉得这个方法很低效）输入时把每个字符分别入队和入栈，然后分别serve和pop来比较。
  • 双栈模拟队列：stack1专门push来enqueue，stack2专门pop来dequeue。若stack2为空无法取得元素，则把stack1现有元素全部pop依次push到stack2当中，再取之。
  • BFS：搜索图或树，将当前节点的邻居或后代全部入队，然后将当前节点出队。

LinkedList

Feature

  • Singly: 只有value和next，可引入伪头部dummy，链表真正的头部为dummy.next，这样插入、删除都方便很多。
  • Doubly：除了value和next，还有一个prev指向前一节点，同样可以引入一个dummy。双向链表的删除可以O(1)直接根据传入的节点删除，因为利用prev可以访问到前一个节点。而单向链表如果不传入prev的话，删除时需要遍历一波。
  • Orthogonal：可以看作有向图的一种存储形式，可以高效存储稀疏矩阵。链表内有非零元素的row, col和value，还有同一行的后继节点right指针，和后续行（因为下一行不一定直接有后继节点）的后继节点down。

    Application

  • 双指针问题：例如给一个[min, max]的范围，删除这段范围之间的链表节点。又例如数组中的元素swap使得所有奇数都在偶数前面，各占前后两部分。
  • 判断链表是否有环：快慢指针，fast走两格、slow走一格，看fast会否重新与slow重合。
  • 找到有环单向链表的环的入口：快慢指针的基础上再引入一个指针p，当fast与slow重合的时候，p从链表头出发，slow再继续一格格向后挪，当slow与p相遇即为环的入口。这是因为假设从头到入口长度为a，换部分为b，入口到fast和slow相遇为x，则2*(a + x) = a + b + x，因此a = b - x，而slow继续往后走，p从头往后走，分别对应的长度就是b-x和a。
  • 判断两个链表是否相交：将其中一个链表遍历到最后，然后将另一个链表头接在它后面，然后判断是否成环即可。

Searching

  • 在基于comparison的搜索算法中，二分查找是最优的。
  • forgetful：在二分的过程中可能已经出现了A[mid] == target，但坚持做到最后。
  • recognizing equality：每一步都check是否吻合target，无法返回『第一次出现的』。因此如果要返回尽可能靠前的结果，则不应该在查找到target的时候就返回索引。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private int binarySearch(int start, int[] nums, int target) {
      int left = start, right = nums.length - 1;
      while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
          return mid;
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return -1;
    }

Application

  • 最大值最小化：给一个正整数数组，划分成m个连续子序列，使得这些序列各自的和的最大值最小。
    解法：二分查找这个最小的最大值。先一波O(n)求序列总和为S，单个数字的最大值为Y，就以这俩值为上下界开始二分查找，假设答案为X = (S+Y) / 2，然后再来一波操作求问题P(X)『能否将原序列划分成m个部分，每次尽量往右划分，使得每个部分的和都不超过X』。如果最终的序列数小于m，说明X太大，将上界降低至X-1再二分；如果序列数大于m，说明X太小，将下界提升至X+1再二分；当序列数刚好等于m，也还需要确认是否真的出现了等于m的子序列，否则X还是太大。

Sorting

普林斯顿coursera笔记里有了。

Recursion

  • 经典例子：汉诺塔，挪动小碟子使得大碟子永远在小碟子下面。
  • Stack frame栈帧：为每个调用函数分配的临时存储区域，包括返回地址、调用参数、局部变量等。对于递归函数的嵌套调用，符合『后入先出』的栈的特点。
  • 递归or迭代：若时间空间允许，递归可读性更强；递归在必要时可以通过迭代+栈的方式代替。
  • Tail recursion：若递归函数的最后一句执行语句再次调用本身，就是尾迭代。尾迭代可以在主函数中通过外层包裹while循环、内层在执行完递归函数之后修改参数的方式改掉。

Binary Trees

Storage

  • 数组：连续存储，直接是2*index + 1, 2*index + 1的索引存储孩子节点。但如果不是满二叉树（堆），k层的二叉树一定要2^k这么大规模的数组，不划算。
  • 链式：用left和right指针/引用指向后续孩子节点。更常用。

    Terminologies

  • Length of paths：路径的长度就是从节点A到节点B经过的边数。
  • Depth：根的深度为0，从当前节点到根节点的边数。
  • Height：叶子的高度为0，从当前节点到叶子节点的边数。

    Traversal

  • 前序pre：输出当前节点value，再迭代地访问左右节点；或者利用Stack + while，先输出当前节点curr.value，入栈当前节点，然后看左节点是否为null，非空则把这个左节点设为curr；若没有左节点了，则pop栈顶节点出来，看是否有右节点，有则将右节点设为curr，没有就继续pop。直到curr和Stack都空。
  • 中序in：先迭代访问左节点直到null，然后输出当前节点value，再迭代访问右节点；或者利用Stack + while，先入栈当前节点，然后看左节点是否为null，非空则把这个左节点设为curr继续入栈；若没有左节点了，则pop栈顶节点出来，看是否有右节点，有则将右节点设为curr去入栈，没有就继续pop。直到curr和Stack都空。
  • 后续post：迭代地访问左右节点，再输出当前节点value。双Stack+while可以办到，或者直接使用一个Stack+while，但是是使用addFirst将输出的值插入到List的开头。
  • 层级level：利用Queue + while，取队首节点输出同时把其左右子节点放到队尾。
  • 根据上面这些x序遍历的结果还原二叉树：必须有中序才能唯一确定树的结构，否则可能不唯一。例如给定中序和前序，在前序中先出现的为根，那对应去中序里看看这个根的左边都是什么节点、右边都是什么节点，递归找下去。当然，用迭代+Stack也可以。

    Binary Search Tree

  • 左子树的值都小于根节点、右都大于，不允许重复的值。与堆的区别在于，堆的左右子树之间没什么关系，只是要求根比两个孩子大或小。
  • BST Sorting：BST的中序遍历即为排好序的结果。
  • BST Removal：叶子节点直接删除并将父亲节点对应引用改为null，若只有一个子树则直接用该子树根代替被删除节点，若有两个节点，则取左子树的最右根拿上来代替带删除的节点。

    Free Trees

  • 不一定只有两个子节点了。而且free tree不一定有root，但一定不能有环。
  • Lexicographic Search Trees(Tries)：字典树是一种多路树，每一个节点存放指针（Java中是引用）的数组和数据域。LeetCode 208就让实现Trie。
  • Disjoint-Set：一片Forest，用Find操作搜索该树的根节点、用Union操作将两个树合并。LeetCode 200可以用并查集来做。

Graphs

Terminologies

  • connected: 无向图总是存在一条通路连接任意两个点。
  • strongly connected: 有向图中总是存在path连接任意两个点。
  • weakly connected: 有向图中将方向忽略，对应的无向图是connected的。
  • degree: 该点处的indegree（指向它） + outdegree（指出去）。

    Storage

  • Adjacency matrix: 矩阵A[i][j]对应从点i到点j有一条边，将1改为w则可以表示权重。行i的非零项数表示out-degree[i]，列j的非零项数表示in-degree[j]。
  • Adjacency List: 由于点多的话矩阵可能会很稀疏，因此可以用动态List如vector(ArrayList/LinkedList)来代替静态数组；或者自定义ListNode链表节点，用链式结构存储。

    Traverse

  • DFS：有点类似二叉树的前序遍历，借助一个visit数组方便判定是否已经访问过当前节点的邻居，当所有邻居都访问过了就回溯。结合Stack可以记录路径，每次判定栈顶元素即可进行search。
  • BFS：有点类似二叉树的层级遍历，借助Queue将当前节点的所有邻居入队，每次都从队首取元素。也需要利用visit数组保证放入Queue的这些邻居都是未曾访问过的。
  • BFS Application:
    -> 无权图最短路：最快到达目标节点的路径就是最短路，那么在BFS的时候一旦入队的节点是目的地，那之前出队的那些节点形成的路径就是最短路了，如果不需要记录路径只需要长度，那每次出队都加加就好了。
    -> 连通块计数：若一波BFS之后仍有未访问到的节点，说明该节点属于另一个连通块，计数加加然后对该点进行下一波BFS。

    Topological Sorting

  • 有向无环图，表示先后关系的一种排序。对应LeetCode 210。
  • BFS：一波流找到所有in-degree为0的节点作为起始点，将这些起始点入队。每次pop队首，将该点的所有出边删除，也就是将相邻点的indegree减减；若出现了新的in-degree为0的点，也入Queue。
  • DFS：维护一个visit数组和onpath数组，分别表示是否访问过且进入了结果List、是否是递归过程中经过了的，全初始化为false，取任意未访问的节点进行DFS，将该点对应visit和onpath改为true，然后深入DFS它的邻接点，一旦发现回路（即onpath为真）就返回false，当这些点都访问成功则在退出DFS之前将当前这个点插入到结果链表LinkedList的头部，并恢复onpath、但不能恢复visit。

Weighted Graphs

Minimum Spanning Tree

  • 给定一个无向带权图，适当地删除边使各边权重和最小。
  • Kruskal: 把所有边按照权重进行排序，从小到大取边，维护一个并查集，若发现是回路就放弃当前边继续往后取，直到所有节点都访问到。这样一种贪心的策略选出来的边权重之和就是最小了。
  • Prim：任取一点开始，标记为0，这个标记意味着当前生成树到达该点的权重，除了起始点，所有点的权重都初始化为MAX。每次循环都把与当前生成树直接相邻的点标记上对应经过的边的权重，每次将其中的最小的点加入当前的生成树，然后继续刷新相邻点的标记。

    Shortest Path

  • Dijkstra：（单源最短路、权重都为正数、O(N^2)）与Prim非常相似，用数组维护从起始点到该处的最小权重和，当前生成树的邻居点加入进来后，可能对原有生成树中的点的权重有优化（该点邻居权重 + 边的权重 < 该点当前权重），则需要更新。
  • Bellman-Ford：（单源最短路、权重可含负数、O(V*E)）初始化所有点dis[]为正无穷，起点为0；进入循环对每个点i进行『relax』，即比较dis[i]和dis[j] + w[j,i]，若后者小则需要更新前者。需要注意的是，可能出现负权环，在这种情况下最短路不存在，因为越走越短呀。其实这算是一种DP了。
  • Floyd-Warshall：（多源最短路、非负权、O(N^3)）相当于完整的DP，三重循环，w[i,j]_k表示点i到点j的最短路使用1~k的点作为中间经过的点，在最内层的循环每次都加入新的中间点提供选择，w[i,j]_k = Min{w[i,j]_k-1, w[i,k]_k-1 + w[k,j]_k-1}。