Kira

Kira

Hi, I'm Kira, a computer science student passionate about Digital Media and Artificial Intelligence. My current technical skillset: Unity & C#, Unreal & C++, Python & AI. Thank you for taking the time to get to know me!

数据结构



数组 Array / Vector

概念：
  • 线性表：由n个元素的组成的有限序列，为线性结构。
  • 顺序表： 顺序存储结构的线性表，即数组。
  • 线性链表：链式存储结构的线性表，即链表。

链表 List

概念：
  • 单向链表：单方向，没有循环，正常延伸的最常见的链表
template <typename T>


struct ListNode


{


    T value;


    ListNode<T>* next;


};
通常需要判空。用头指针：head==null，头指针若为头结点：head->next==null

  • 双向链表：有指向前驱元素的prior指针，所以是双向链表
  • 单向循环链表：最后一个结点的next指针不指向null，而是指向头结点，形成循环链表
  • 双向循环链表：最后一个结点的next指针指向头结点，且头结点的prior指针也指向尾结点的双向链表，叫双向循环链表
  • 静态链表 ：StaticLinklist 即定义一个数组包含了链表所需的全部内存空间，在数组内部进行链表存储和寻址
> 这种typedef的写法允许你用 SLinkList a; 来定义一个该struct[10]的数组

Test:
  4. 移除链表元素（善用头结点简化问题）

栈 Stack
python用list（支持append, pop, l[-1], len等方法）或 deque（更推荐，[0], [-1]）
c++用 stack（支持push, pop, top, size, empty等方法）

概念：
  • 顺序栈：栈的大小在申请空间时已定。出入栈只是进行栈顶指针的移动
  • 链栈：链栈的空间是灵活的，由于栈是后入先出，所以每个链栈结点都指向先于自己入栈的那个结点。我们用栈顶指针移动来出入栈，而栈底指针指向nullptr，表示没有前驱结点

常用技巧：
双栈法，倒栈法

队列 Queue
python用from collections import deque（支持append, pop, appendleft, popleft等方法）
c++用 queue或deque（支持push, pop, front, back方法)

概念：
  • 顺序队列：队列的大小在申请空间时已定。出入队列只是进行队头front、队尾rear指针的移动
> 由此可以看出，栈和队列的顺序存储都是不需要删除数据的，只需要移动指针即可实现
  • 循环队列：front和rear指针可以不断移动来利用循环空间的队列，front==rear时，为空；front==(rear+1)%size时，为满；即任何时候队列都需要至少保留一个元素空间，rear指向始终为空
  • 链队列：比较少写，队头front和队尾rear都可以自由移动了，最接近队列本身

Test：


字符串 String
python字符串操作：count(), endswith(), startswith(), find(), format(), join(), max(), min(), replace(), split(), strip()…… 切片 [起始 : 终末 : 步调]

我们在进行字符串匹配时，遇到一个不匹配的字符，就要重新从头开始匹配，这样很低效，所以KMP算法提出了构造"部分匹配表"的形式，来优化匹配效率，如：
模式字符串ABCDABD的AB与前缀重复，因此如果我们已经匹配到ABCDAB的时候，发现最后一个字符D不匹配，我们不用重新从AB开始匹配，而是直接从C开始匹配

匹配过程比较简单，那么"部分匹配表"是怎么产生的？其实也很简单，当前扫描字符序列与字符串前缀序列相符合匹配值就+1

但实际应用中，我们一般用字符串匹配（Brute-Force）算法，也就是朴素匹配，最坏情况下复杂度O(n*m)，而一般来说也就O(n+m)，且不占空间。
或者BM算法（Boyer-Moore），即坏字符匹配，模式串是从后往前匹配的，这样一次移位可以移动很多，是效率最高的匹配算法之一。而且可以用hash表存储模式串，提高移位时的检索效率

树 Tree
树是n（n≥0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：
（1）有且仅有一个特定的称为根（Root）的结点；
（2）当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

概念：
  • 二叉树：有5种形式——空，根，根+左，根+右，根+左右
template <class T>


class TreeNode


{


public:


    T value;


    TreeNode<T> *left, *right;    


    TreeNode(T val): value(val), left(nullptr), right(nullptr);


};
  • 二叉树性质：
    1. 计算结点数 n0=n2+1
    2. 第i层 至多有 2^(i-1)个结点，
    3. 深度为 k 的最多有 2^k -1个结点
  • 完全二叉树性质：
    1. n = n0+n2 = 2n2+1
    2. 深度为 [log2 n] + 1
    3. 2i为其左子节点（偶数），2i+1为右子节点（奇数）（2i+1
  • 二叉树的顺序存储：数组
二叉树的链式存储：二叉链表

Test技巧：
  1. DFS前中后序遍历（递归）
  2. BFS层序遍历（队列）
  3. 计算 depth()：递归 return max(depth(root->left), depth(root->right)) + 1 if(root) else 0;
  4. 清空 Clear(): 后序遍历 freeNode(p->lchild); freeNode(p->rchild); delete p; // 回收
  5. 二叉搜索树：即用来二分查找的树

翻转二叉树(的左右子树)
RU5DMB2IWdy2b3/PQ79mQaXi6fRPNmuW5MzbKWJUNocKmh381UXq5DQvYPs1RJ1J5hVSkOzfuVBFvNig1g6U8c8vhgXnuAzJIM4ieHE30lzFE9lkG3tHDzI904MtkxZB9HsA96MltoBA3Xkf3ohKq5Moq4RwAmcPvUxgKUfte3v2yLReKV0YAXv/4ZsXLjfIbbwdlSqgvyfZCBLlVp2liMO1IUGYMZMh/yOwfa/nqBoFRbxBmtghE/q7Jk3clinF0d7MMAoTaP6ybRm6zZsazF3t5h11T13SO1Mgkg+rHM95JoxL2Ubv/DlhyUUHbhLqv5e6pfSTJK1tPjbUQw+ms5JA1reeVXZwNF6iowU8WhqCWcNn

原理：
RU5DMNDceoHg4elJtc+tGneW1DLiLSmioXat+y5KrBp2ZDKoKVE4CdBVB7e9zOe5XkfTI81/ONPkxlUoJcXsDC8kqLjFm//rV53lYXP1uM4VGz98thsQ+WBhNfQCltW3a3asVUkTmuyACafMyvr/DlCD7EfLn6vUReXd/6bl1kAGjntOrO45GUsXK2YpJ3G4eGZWAPmuDog6WaoNl9R6JnNfLcioYuE3NbbwTJ7EDX7ZYU3wCWwIavdcp9u4X0IoAyCTo+0CB284W9pD/X9WhiRjbT8g5bi/f+NR7v+QeDPkT8Kd7uVUNEpYFY2SGyIEooXrm+4SpqbKDDUBrrlHbTmO27k28qfY5jJeyCj4SYlB8ezmr1b3d+dpiM4Pjm3ksaoHmNL4q7QY3IcXY2u8X+9VgsXhkquPnKT0loXcjs5qjKgCVovgSm1uANmRixtIzu5MBkTswU31iynIQdB4iQeogXPPw9VthqM2KBQEwbBj5Dz6S3ZcLUAylLog5LCpaOkORAt8IZUBTuAfdJKX/iGKvwXt8vHpNjQ7n9DJurW4edNO/5bQi93Fw1kqspZRi1ajQj5oMxCtqREP42XYwEXPs4a2XC6vLhgZNAnrYFyL5ACD8E8DjE8GqhPtgbgE4BOrAC7NneI1PB9BARvh4T4hJV4BzGrD26kyxLH1OUoQGY857Elyw7j1CVR6BalWtKk3cM1pMvZRr9/2W/sqOj11oGN9pVfG/nUkCif/SPIhUFanAGiSr4cXNI5kP27FmBO9YxsvfRTELLCQ4Fnp6o8BPGd0CkrqdTiQKJBT7EggyV6jbHvq2/Ej4m1WBgdNfgHwf3KgouA4lHTP3RG0lPlllLKjbRLgq7l+C3/DNLxFLhchwFJ8P11z/j28Oq5X4sUyDkezLfWr3+2scA8sJfVmJd07RVVJKor9AJ1ieIm0CpMxPxS0FTm8BLNflLtuXTkZ7f8tpPHfNwBFNoL08ctfKbMyOcnHbA5QfPAXb/N4dc0MaPWWkwR5UkVggCR8arwo8Racs/MUYMtnCu655NjL/39O1wD3SfH0ijO1KeUQ9XyAhZ47/gzBqs5PJDtzjOiGTvkcbA735BzavZLWGWDVhGd44Xs7SF9eQ+jRY2NqsPMk9t6WP+sxkFUB7SKp7tljC9qH3ss1hnbkkJPAY1/P7SEtoLbN4TMpMWMz7Go2nMVO

给定一棵树, 找到该树中两个指定节点的最近公共祖先
RU5DMJVQhnj7yA7QfUo7kXDs7uuHZNaqx6SllR4Zb1qMsFmv+AM9E7ZNkon55TadcC9EcNRv5eUdSRoSpzpwhnE69fuVMwZIQTjaQwCesOjj9QtLoG8309ehQXnqvkf16vTwu4hZdNDflhm8n6voV/AMqaoQWKHyz+PWwJUeeEXJut8FaqY/vSQSk8MG3v7ciEG1BpzNUV3t/XKmmV+Z5pD77KqaYPJPiqRoNhaTzAczLw+66M6vkhBbK7HFY7TzCpBzDyNaUoHa7CnvrUbRH2xjjki9A5HvlSY6EEuCY3ss9ykuQEEZY/F5j+tyt/Y5nw3k9djQc8vacHs9lpQ8bn9ZQBYMfN7vZGfvsRJbbEKoRaHEqt5Y5QMjWzMCKha1mJca+hCfRutVnaSj+HdtXFjyE+dZE8nmUvm3nDNrC0ckzY2JuRZzOZVFz1shEPbhY7YKdq4o60n9LRSfbNXmnM5Bh+9RQNRxp1ZPZBhcEtn33PgLSfGSTqDvYs2DUgfZ01SDA9esB3XPvmYWSkkK+hMdwMoEgojQrbtXdkqI6e5P4xMtOFHxEjerPai46wQ7PctfLOliqL11fptVwp2T95JwTIsQ8r9zkJ1VvyekHzLRG9rkJsPtVKLBdYrna79cU9Ews0ljCVHzF8HdGnzlNDkWsXgDOaWxoCH06/UZz7DV8Akknj/7lVSOuARrRCgYSJED1a69P6VBG0S9mjiuntVMPUSjxpMdXIaCRrJMpGrvpuviKNChFy4eviYHPCc7+7smIq3YsSDcSbGcD3J2Vca4xsBMMSds/aSHYu7NsZph8g4niqHy+c+2X9I3wbI+3GQpr+F0/G27w92/hVQrQFYU9mpi/L6kDzBG75jVAGE+Wp7KTaYXwHyAzzUKYNE16BtfggrxqIh64XzVmEq24wn7GqELgtriUmNZr5obTXIieiryb/SKvXG6aH2SGg18Vdsnx4aZjnF3PtUOFxdfMy8h9LyaAZFaFWV16w+UK0NXTYD55AtfhMBxSI3i6p+ZmAwoWtpDsrbbIOGJHHWuThl3pTuwbi7u3dofHhrO7eXKiGPbEfOjPeHfmaDRk0ABbfe8bCTOJTh1+QYy9U4bvPYQMU8Fl6AbcSsD9wMbEVSNf/acdOYZCRlpLjpgQYFnhvjGr5exNntoC5epjjUMRvrdvJcwpP0NhHkobATa2hf7fTBMmHqI1js6Jrtl8j2cOGJvCgeHvRka7TYjfBenCRJYbk++5aidpfCClRydto8nJQBQiXEya16bv7+qbp76vuqzwTcYcUNcdK6CG3VaAFzyLtes4w8vK1HK9NTE+DcJKzPk7WJ6T6WD+NmykBOtHerpovElSt4UjPXH/sDK1GCRAmCZo9ymMT42VXe9fhk10N1Ps/FgHzsZbHei0RTJVeWJO3bmtHt8nvTtZLuXra3NifHpEs7/rjAap11AA0fo41xdTM/kfNtZfBszD9l9NtpCIJuktfXL3NfEhdv/x/jeye3Mv3YPp8AoNamXOv7g5YSc9h6vqBLSvVp4jAW4joQNnUg/2E7JiRqtowaKci4PW/kBlS3y4xzPJe3mYwyaUSkERQkl+YvyggONxk5C/0DrrYiqkhG2hUbMEe19sJmic6KqIGVhPuy5+aGyXi+Eddd91PQ1BEkFZnSTMi5SkI7BAHVUW4qAhIbrJ6o2TGK5pkaLvwIQ4orYc7csEZ1e4vgB1TKufF1HHifJ36gXW1Owvbk1v0nLvoNDeXRYPYCfV3irefLOMy9mrXVdUqbHzTi7PIOsMlyMZlNwJUctfzET+/Ezy2AL65zk0nbLIjFSrUFu0ia1jXrMlGAfbXJRv+W2ao2+UDdQXEF75/i09Byzqn/xi7zyT1dtBodDLJ2CzM8ISq0DwEHwYVW9kwmZ9FbHIZWscxy7odNeLyI5Y62seDBaR/vNbS2agHtMr9zazZzJPvno95gO3cLQf/hCxliFvHgDjPPBjFcKyq+nvLUjDhM5fDtyQgD1FQqUYr+joOcQE8Q6IDyTC1uJ45sX/MjPmRr3a6ezbVm786ASCS7Sjp2ZoEkPFCJ1F5rJotBwQyNnJ4+K8m9wLXPVO6nI8iIX

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以从树中任一节点开始到任一节点结束
RU5DMBjf2F1+T7AoKqOLuBdW6Ih3O8pOPWziGCTt/kBF5rGN1DZIZzKx9XZcLdBmW9GlYEi7g5faxQ1NC7S/ZUMPGmEa9FrPa8TM+zz3SOl2m4ATcGWABd07xo+x1iwuY3rAjXR0ErVuG9jDutFAM4XKnVFLU/S9msTYTd8W4KIKyMO6j0hh1AXWFg9GtufnSOYkaGJpQfhZeqhg5KjaNx5S8qg2GF6tEE7KUTpS7FSHIiq9uyuEZGQT+o+0Ry3fmbIinvyPDCRqSt1DT9V4iNqB9FA0M/UOwX7DEc2y+PVTplvl8Wx7/1P+FR+/KayPVcHSoS2PmrGYV6bEHiwNuAplmHNPNPG7CdrMWfO/t9To4qhSNX17N0EZgXvbkqpUbg1dK3I9DyMc8KhqgPZeX8J3oxbTn986GLQwO58gBhrN4JE1P5J0grZ8WBGGyqui/rLYlgCtlrpPiVRUYxsxLMUkgTXoZxumaGY9oDuwzCTp1pNpfehSt0QNXVkFF0KmFJaS4AVi4ctxm8WC9fdPOKcL6wUQJU4yy9Fj3bajMkZ1BgAlun6q4SMwgfOjZ943GpyU01OWC7f/7xcO0lRF++twHcT7rfxGoYPnY99sVrsU5/ugCkTG084ogWaTz0Eqm/T2nLPUs6Jgb6/acSE1/P6ZMA9cdFQeFcFyFfIeFQtmfETx9hWyxc+VZE4eSUA1y85AI+HGuXDYWt5LotBSkcsrgKq4voAuuojC8JZAVlE7Ws9uQYlDGW3nT8K8SxiZJhM7eRONPmrUnN0lMtGunV4JkCDiMDkWtTgO4F3yzrZbXg8q6X5ZmlU6dCPmHjPPOM0y4NlB7Lg6J8hxYWPJYgg0savWL9BBD+ewr0a4OGKzpcT+FvXVd2Owx36iMS8BuxNPbWeVeARMHVbbrcvI9+QLxIaDTBLSiN4/SCbx3YgNbFpUVrBexvvEP8hNxvJ42PCmzY6pvNa694fuZ+A+YR6QV5/9ZcKrryfx9WgP2UR1DkYDEvhEWeiarUuoIly0+P8gG8VhK22ylS9iulETbda3DsX9ibzEsigFyYe3zGi59HoJqocxInn40WesVrJ2kmKxcMKTEoNEMYotjO0u1Y6V0V5EnmcWPtTkFWDeeOl5K7L8kbaxG5zvtUhyKSNFGXn+reqlMAcf6yB+cU4prk0kOHAum+gzlysUXBGaZ06sWUVpBePWa5bZYfpc6MnpeYOmbYjodPo5a1EcZjshvlWttnMlUIKaF+sBl3ThN7J3QN44vLpJcGwJI/gXbgRMUBzMxC7UldmyvbpPOnI1+NPEg3PXxH8VtJD1mV6EODslvgp5bAt/pycfNtyEvk/yZ1do00e8wvG2JsJRSw0ckSkK8pe1nRrFwyRRsoyjUc7Frd7FC3Tne1aT9QDjryYv9GlrIxfGlgKqyrjKb1aDhVJjxwjGzJFwi1UZIcno4knm3daVb08tYrWGF528QgM4yhprwzpnY6nIW+FiKXhWAmRdWA8=

> 核心是每次构造时寻找最小的两个结点作为叶子结点，最后形成 WPL带权路径长度最小的最优二叉树
huffman树主要用于编码压缩技术（将树根到叶子所经过的路径用01重新编码，使数据变短）。解压时，通过查阅压缩时字符编码与原编码的映射关系（叶点即字符），就可以变为原编码
> 软件压缩算法一般是 把文件的二进制代码压缩，把相邻的0, 1代码减少，比如000000，可以把它变成6个0的写法60

优先队列 / 堆 (Heap)
大顶堆：每次出最大值（每个根结点的值都大于子结点的值）/ 小顶堆：每次出最小值
可以用数组或者deque存储堆（完全二叉树），很省空间，如下图：
二叉树性质：子下标 = 父下标*2 (+1)
  1. heapq.push() / pop() / top() 往往在插入和删除时，做顺带的排序操作（都是做堆化heapify）
  2. heapq.sort() 堆排序（将根结点与末尾元素进行交换并移出，然后将剩余n-1个元素重新构造成一个堆，这样会得到这n-1个元素的极值，如此反复执行，便能得到一个有序序列了）
  3. heap_build() 建堆，是个递归函数，检查自己左右子树是否比根结点大/小，如果不符合就和其中一个元素交换，从root结点一直往下递归，最后形成的就是一个顶堆
  4. 堆化一次的时间复杂度是O(logn)，所以堆排序时间复杂度O(nlogn)，空间O(1)
求中位数，也是用两个堆

构建heapq
  1. 先根据数组，视为一颗完全二叉树。我们将其构建成大顶堆：
  2. 找到最后一个非叶节点 r = n/2 - 1，与子结点 n-1, n-2 进行大小对比交换
  3. 继续找下一个非叶结点，也就是 l=r-1，同样交换（2l, 2l+1）
  4. 如此循环，每次找下一个非叶结点（就是减1）直到根节点，交换后还要检查下换完的子树是否还满足大顶堆的性质，不符合的话就继续递归调整
  5. 最终构造出大顶堆（时间复杂度O(n)，具体计算见 拜托，面试别再问我堆了）
RU5DMIwSf8JuIub9pyZ46w2gXbm3WV5op8SFY/LRZ1YuAz9Zs4CqvEyNaIgm2OBdHzz1Q5wLKDxwh8pBSSSCUh5s5z2wfjXk4IqA9WRc0oOzNPN8kCgp/k5qR8JzYN635ceqRsIbsfoXaHZKypkC+CSRTIhLDTLkvdt6a42zWvYPD/1nO1aEKIaow4ZAkznrcL65MxA3yd4OmlsLvmexJsXRsMMehpsPwGg+vsWPO+cRL/vWg5MZkW/zGYZELoVSKblaOtlE2Lfru4v/Gnk73CEwrTdnHMultZTmUnGrBkJ8KT/jUOJQT7RQDedySgFK06XN48xqy+xnTf8e6ZUAD7dzHIJCGfv8j+ih0rN7J9WIORukveUrAkA341spBVMkNAPOCEGzjNj/MAFqpx51fnh015vKKQx846IxpMD59xugmFQ0J+zqSBXkqo117x/lLFuG4rXGAjf739hmiycBQSR1QoOcqSX0GVCCvH77Vf5ubtgxjfe0rdJOL+kq08vrlK48wyS/rfujo7/q3bXyasUdCEVHLf1aBpBPwli6gtLTlsgY7kCvJ0cX37y0X/Io3qXsEegMgwWwWT0PY+TEEXMj2FrPNEy6KjpvnFmJ/NnOVe4YhHCqa3MW9A4hw7r819HzMzR/3TfFO3nZMq6WHNvFnS8eF8zbAFZA+PFF24SCVZ158bZHa+Z3MOAw2ao6VdHzQpWbyxIIyxnuzn4PhrGGsNNbmMPztkUluedAliVJvElmti4B9kEV10N3/Tvd1BRL1MRwhaNFaW53hNEziGDX4O3v/DNjJzXeRVDlxozQwC3BZ/g0ANIgzGHElpMihHyq0qFtdmtsTDka/Cn+c1aQ9qwowo9ZLuKg+Ms2R/2vsPrui2RXOlIsp3nP2+boCrRUaq9yWodIUZupGaT9tglykuM3M23UmDfyJxiSimEzrxH7yu3UeBeyc9t5mCa3aYwSdXN8mJGQ3nzVVqhLFrjlAagdxv7lu6jC5YSzDXrdAFcGl/VNt3QXBWoFsjCFX4I2S0b9H8lrxMHD7Te4ZYB0XjzNF0xCMNJ4EJut+FECwlHoqZrLLgu+gdSLGZ3Gc/8+GUiWxuKSatrU3IBHKsidJzG8SafmEazySy1YslU0G1fnBt8JRmfCljvi8pDLqxKzuu4G7LZvmttDuC/+209Ad0S+UuOCmg8bDU1tomBgFPapz+jpUB4tTjzFXR8LrHvCca5Y68xiOEP1jhLD4TKcw9AZosx+5+avQiBx919xE1z903Pz1Q9gAwL2D/TxvBd6M9ygflo7gedy1VHmciRT/BlvJOqgV9EtT+jVM8obgQIdmL9B5M+o5Dl3qTobqQ26VRuFPpId0xLEalsX3H8sUOTHngszapSyOhJshGYMSXI/reKVmF+8kVR63VYPxWF05RTwDgzQnvAGRJxfv2WnooZB/cWpVtfO3aY0tBqLMHDqxRCFmEIS0o0G/xcpI8Jphc1vAIS2AHuG3e/AnO1dIP6lADPilAP0LTCXBFtZOoln1LUKDlXc6k+esNNdnmCZbGpzgc1ZXIFJu40Y4LUNhFS9CZxyZI1GGBGqy6QJ6k5hpktWW7mUpvNhj+X+RxuvfJoYNG16oYG2FsBxSN9SJUB0UFy/SW3QM4Et56/BabmLtL+eRdmQXLBHUgKwUgO3Ugi0tx+nKN7DxYlLOSzAMDkiz7ehUhSoJa2Vb94wTdDxmLnB52HfGxA+80Sg/0WhbLuKwXmsfCzaI1GdgUHAz0334vLozZEY1anyDfEYDNc6ZjnunYxTF1XA+VZcefNssrHla5dSaPjDovaKGTllu4jA8dbWHmp1ZIUl10xNl6zSRqWiREFYHqmjRxGo5pSYPrf9Kqpx0dwL5/bhnYaXHWB9QRXeey2jxzNi/dS6I06z+3PJObvSdQ3LZI+tzlGChpcMgvHZOKKzx+XetASk8DtRNa0QyxmTAWB6lmifmsD25FKvFwsJCDM4c5EIAKWdHV6T4X5v94oVYNgPIMBcssMrKMwNnLiVHShxj3PWa7cv3zj85ANO/j0z25E7Hmrw4B7Pyag27srgIwKrip54z3WpYrJ0jjxkn1Zyjostkg3PMHsHzYdSO9wwMaka92hl+5vPvqPNRBwCQSYQVTEIp491/j3RR1S59CNNaovbAEoLr4ZkbZFSuaO0Fwsg03YHocdn/0BWvWkkI9K82g8afO0u98IUT2bPja41qM+XKnlHxbKJ6LK8nd+jAqbsBRIcc/vYkb4AONWzuusy5wK/dXIOtBxzyrP6+5faRZBN89BjZ4p/+pnbVpPsdwPEmQO8/hP8/pfSG6b7al/CQ5pYZhq8l5CwtaSYBAYyhpyPyV1ZkC6E2ujuZvPegvRqwU+iBgmlaJOWL0QPHHCh8PhD+yeWd2Nts/mmP/k4ew1BnRxAbGFGlzDUN3XkIDU2tlKo802zXJJ6Y/7XWf/9k2G4sIi1QJr6dp8eU28F2twfvSDCXctClxSvzMQuejvHlNmfyxes4P8nQL6alpnV9ir6AZRs9XKcvIYaLfjWUNJI5+4AW6//tb3TEszK0e+la/ZAmU+pvTGaHl4FuaHHdTwF2/Mk3NWknFourDqforpM+GQdW8kNQra/M5hFhA6xMFkJg3b/33I5rX2uBCs7gwJ0HuFelTT5b6o5JmB7/FunTY7C9jf3QYUJclGn26PnfDDv7DErjtItK5rARm5iK5QdvbwCHO4UjJLTRRTT9pdecMy/QCtgnoyoOFbDmS/McbAD8VcHVUUPjVCNMCmSZQqKwtz4ttZwkl7Ui9S5Q+4OZmpCAlgiLsCRCnuwEeMJrXXAsW9W1u4bYDg/b2y3SSiXzCVj4kngw+G7YY5NfcKyuSxjl367FnPi8KXGAvrHgYTnLUTIXt8L+lhy9E6nUIDZaOmQlBDn6013/gtV2HtMkiNbS/zrmvVK6lu/HTRDEct5B1iEZxrkknqAftV1qunfmNjiEzHYpa/UZV8f18RnnZxykIbt8DNGnN5IbC6AmSBxNwz4PZF7hDKqZXi2yUH1VYtTTR3m/9A7c/B+3LpTZNwZg+ybH4ReFKOAkrF+hylvzC3vgIEWrr5ixfpZ6PwhQQRSUG2RlwqHo5jkw8R7z/w2PZEtS929E1Go70qoq9Tq6fQvDnl+josS502c0zgoAfAhS1t53qluF2Z2ArchKTrKOPZvsBo4S3W2NNPTqkvEF4QKwZLLFa1kiinPK5a6zqt7y61jbQ+bvFMhdfRZ4thfiGC6a3ad6q+vYhATPOn49bSjVvPUmhW9fnzfs9lF9kwwV5lwGiyahfwRpUHz8ZzVIblKtNtF4DFPeB5GHt6c9GnsEbJVXyx+9VlBUJfQWVU85qb9d+8s2//d85tUi845lBv57wXKY6bXH62+Iwl8NTgDDEEvHMtKnrH9IgqrgyVSz8d97KJtM2VDm3QwkwV79mWBLxmQx2rWJdXr53Fa7GBFfkcKU2eJhVJwNJJz6tmJAgajyHd1U+7OLq5jso5ahdVI3AxhWnR95AMLHuGtwMM3b2ELL8FiwYl3TRRUAlF0jdklcrszHaQQk0r/BZcPTRc2vdkxA+k+ZJpR/id/JKfPMX9SfguU/gH0ocDpfls29zauZuM6O17J456NzHhQBOPY5yTKirvHPw9vYAubclAanNe3gz7KReWDreo3hHko9pUwr7f5ratsSIAMVDlxAVwGRM4akXRPS1xPiStGnewiK+6jpXuHTfi5TPRzylfDHcbYg/hQ/l36s1qHlNVdNdmz+TLKkmTsZLYQMCI8p9jBdA6RcSuw0iVbOSILA1nymqiReQqbPPbWcJA3NrY9dBP/Y1XvsmVUWoC00Zl/tVlKJNJy5a3e5+bQ++eRES0z1KKHidQqYyigEduJpfsLRh3xr4vHpJIl8Dquyf3Za8sifxNXGxi3haM9IWs11K9l3cw5EfwO9M2waYhjTASRyx8SyfABRt+CZJ4vk80lSDEFFFUgpW6stdh4uTOGZhtvAe/V9AaR+8LWyZKGZZLRfi3f7G6fNoht0lBY66zUpjxUYr9uyVQBP/3/yKmthPOfqsazW6tmSosBVGH1etQYnTMB1mZOmsKsZ8GX4N5nSo22kYpITORgLWRe6VKc4lCGkcITP8paAnSm3dzJwG+oN5qwOVVSBEYPFOO7YOj3yFgx76+qbhvHJG7x7E91Fir1TnZI2ReAACUKmYSDt9XrHeTP93hGq3b/x10gtpGeUX6AkX/NAzj0dao70F5lqna4r1N3thrcIzcIe6/ytU9WxEznKYYfCTN3yiWJ1CsRnwsMg0Xsfyi7Uf8xLf3py3nKARZzf6ipNEeMt40fPLCXwFTbR+gz+jI56AxwML5aA36R9i4oGV+V5aiZozqNKjZ0/h0HC4YC7Iti3xRz7lR0kcNt3dWLCF644ZFnyR+ihnyTqxfXeWqWYv6HH2W0Qj8Hc2X43eux3FrqfcOX8/y/fVtXcTYBXaUxCTpwSoCFsW8dgtsZ0WVPGxXd5oQp1sjyjhDMkxqYeEGiCKdG5BtFDV+h3g2nDxa6ysdy8XJ8xaIlL/J9AAi3kdeepU5b4ZIyytdNBkokn7jCui/ijXZRkyCyUM2d9RWB9oYT7Giroyk3XtwKEmJDbufDWfEEhB+seEaQSXdiIzt+njpdk/iOg9c/3GtnBxtVj4MUtl5kEJWonBute/ZBCzH1xXlzNeW6ohNQ5uXYbEYn9LF6J2c2HE4YBSEZoKLMCXX4q4ydSS4ieBYcJMTWe+15ucgVl1QXo2ZMh8WRycRYP+f6sbNcqFrMbl3CItGFxl/C9MJs+7UciZ8HYSUdmWXoKP+VtM9IRi7SYJ+pyiuS+JFkz5Z8uc3QOMzuSExHwPSxhrH0F5UC+kdie+4b7SVBX/c9obGCehM7Nk9yaePaNAcX13u1KMEtHNrFL8D4jfkqmjHN0W9ZT1VvfS9iIb3Tkhofv8UUfKEDQFjbSUb98pNz5n/Jtk321yHdn8OqJMqb05ixSx64ncPEOEGKYiKYs7+/m1Zi0qGchk1m7Enq1qkaRb9dyenehCY/YKOlq9RV3pizw/SPk+U9ZGMJfQyfrn8uSRZzb/On39DdgB7cNSUjLOagDMiTONt2cnBKfbZLzzqoURNH+e3hIaZHcSVy96lh11FyREaUXulM+Lg8WUeLarygl8BtNFygQChwkbvQDpZ3fadSCmzEAVPYPFauc+sAY0/c72k3LZs2jRiQh6ArmVI5ufV8lZACPz8kYvYJ4wbdskmOjeVxFSx0QGlO/PHWBfqONDIIetpLnx5NcdYYQSjZn3N8eZt9kCJmPgreNgvlVVXDzbKYxJ6GjD/tjWbWTkwsmrpo8s2OXsV6Y5PCV0v7AO1n5ILeY0Cy09AN5K58PvzHWt8Wo6JwSm6U8RBmy1FaEqHjvTj7BJLskJCi5DzSbf7aMPAu1e+GKIrqGJJZ3wbNgkC+2SKaII7p4YpGBu3HjWoibxD5TdLRFTJI/GlBlvWg3H71U9PJ2VixOgzNS8gCLjUpWkfCot8PG96FqPK3jpzGY8ExzVUHwo3v1pJ8iV7GQxQ8FCqQZq+FDU7LR/rmAXQSeLz0/ZULM0AAplyluurNL87mG7LrtHSUjRgUoIsKshMZa6HcSoM0wmWy3FRlQU7egDxN2eeKCZSyen/CNvkelLz0bzUVUqf57BxPkY1VPyC2DumMVLjMjD7rT1kO/RqGSj31OwGs9Q9BIadnc4inTDXRAzRbWUqgYrfrqBwQpomNaqr4L/se26IASwmM8uGUsyGcYhm5bLV40BH3avQOCglY5B4fL1aOy4Zer5GV3aGQwUITTt6dzSE6IOD/E7/TpBD2QorAnNLukOX4TVkMmsmoTcop9EW8WKqrZ8mk15471WfODe61xV241UiVM9YJhGcyf5FB5vV/U2uUeyAni1Gl6/v2Zan4jhzgLJdM+Hcp8zj0wcg1TDAEu0zbPfuBPYs38qDm/erqDqFJx8hqo/nhe9cCy4QmFxNqD0uuTo2dpKaty+FXw6trZSMS6kyI48mdnbfonWybfNvIrZozeTOaaTZeONhMLGzw7+L/IMcX5aqgCwhPPP7RBqySFrnsTQiUF6KnLAyowZTeY+7Ry5h/o4aowKfU0MXeoaAnFvCtUqG/rN4OPmPIOoW/qCwiClKTjL4Io+qzAtN2ftuOQ+671RDTJ9yulDXrLRqCO3cYhnGWRKMY3OlB4wlh/NR3Syr12+mip2j5QVZ70LJ3a7Gi+MAIkQOqmTOPE9FPO1Dx6LrAcFRT3EKp2/PDFDJH2NQdUpwBUJdEgqDfETdh2zHqMIFSntC1XaBRBX9/EX2iP3nIyQqsVRTBIt5iEb2pS/5g0mJ6lbr3WOUrR6OeCL43ps4ODs/NH40Pm+1J8T2JqDcpolkngSUg52PoXjzho8NezQXn1bGnA59Ez6cDAj8LRkNA/+RJWa31OT6KQnEklvw4PT3kpES4W1RA0K4oVahG2pEkWsqyD7Gr9LFGns5vgrB9FjPh/yVDiV5M2mx7TZf4qaPy6D22D0F9D1f6WLHRxJIhunP3D8ziV99VIOtPnfC07JnKSF57t3oAmZOxoLfiH2Yoyqjk+myJisW5CWuHXSXQ2uegYesc9Zzd+xx9JcdZrhwmZVPhKS5bAPr01F6Xe4eitELokfLCDskQhzbGJJRH0jOFyipIqU8DKY+6fBvQTnelzuIgkpVHdR02MJiroqyz4SuxBGF6ioZJ4vzcm9nkRZapppSYvHXxed6qvtqNilkcR+i+Qv28j0NyX9Dqa1R3sCMWcTRso5WdvZahoU6u0FwsmFfcYwKaPL16wiWunG9R8Cbga3h5Fs4kltCcuLfZYlka3HScjDsy0iUwpRHIxYaoE2biW8hjatQp+oWHCtZ2eAGw+t0xFMsrB/T5+4eNbsfmOMgQVNKUdN0pMNrtW+cqvpMWLJBNFjbHedTcbY95AjiFh2cNBrW2fhWM7imIqxQ7yumIv7Fex/XAZhv+e+zaFrve0kA2A1RzLdnjUV28d0SMxTLW3LvzbeqnzqbtYSc3GYxaV/F9HirIWe0thUq/1kxfA8yPE6ZtUtZga2nB43X7bI+uQgvbRFPtTnLbKsqessXinoV89ESF62soD7HsJB6mYbL81PpG0UkA4NiTdntQAk5uBqCNSwaQg85cBpYJikgRW92reQgjfuwtvkJoPUeUdvyT/XhbmeaGDDqXjGW4U1xaCNoGy11QY9QOkftEkjqloMqGeEMa8/m7DhGSw7YLXVN+MFTjahz0QaBruQFH7WyOX1k4bf3egJEGr3JD7xyMY9NRnOKNPWx3dUAJJ+VDV3mLBzqoliaxM0RcHlC0AoWKzN69gBvvdjB9B3t8tm/6LqQ1i9VB2cEGkUmEpjD9X/JrIkD5PTEOgH0jDamdUnyssAz43Z2odA8ArISmaJ1NiYzojk8JO7be6NPlPb6JYeH5Wrj491SPsShvj5B2XZ3wRR4XEr19qDP/uJT6YSsUWW7aYnveRXYN0X+yo/lOcTyGpUjUrrmohJ+ixfV361lXaO4Aq1VLOii6mCMwZ1KQBFCjtlaIFgOiyE2Afa6/wF9KNkB5D76qtkskrACGrbaiuT5w430YsI0tfkADR889RMqvraSgBFZd1HVdzbGz40zMQ8/BFkkbyWeZ9+PiOe9dJ6mbLE4RZSP838uG4F9EBAMYGZftRM7REZ/stjsDaDGoBpxke9kmgW7Yugv82IHZluGGIysAQO9JwJlLAZeqyjhBkVBisqaw9KcwDO8ssWNyHeabD3AlM6GObBVBqeqUkn7tXN2rFA/xkhCV/Um856tKHHFQ/4TJYHeeQT4Tl/0f0XIS9Q5idNfWO5FjDRamR1KUSsBlQ5/FOO30fJni05vNjS1VWpE4yOlCSHYxoddp8IkvEavFfkU2m38u0bxAfw8IVx6kOuIpaCWoZ+6cUmzjhNkOmmIwY5uK98zZVl6DwQ261D5EoQWKSs8AIDh/kDZc+H4umB9PE0R2/AG+wp99ZMB1QxLH8syTpZr6QmUY38pMQwp2lN/hyInjPxPZJ6sEb61YKFYF7GML0bYbshaHQicoAjqMRjeSS1iwY1Ow2OAf9SSXRevaMQuO8rrnuyRQ5X3lQk+zsfUbWdZvvXFwhY+47IvfMJhNLgaB3Pv/78lo9OpsvcPOBxhpM+BG6vpyiKzNNmvxwQR33T+lEFzUWx3/1YjhCQLTSMQFarxyQGECQzJerLSKDJQQyQQe+A+0beVVh3zDgIu5BqY/yNLHizQTbI9JcgAVYlgkiQImrh0bO5G3FIa6GRq+Ii3PJaguLDeVAZ7YVZawFngmpoj+MeUtloSxXFdkX/tvljRHHt021HsQxE8pTKQLPzsVdLfBchRZ6Yo5Uyx6A8ij2EYr7ZvFiSQiUrwE5Ev6oyulMDfn8rhDqlIsbKffR6oVIfpZGqnY9WNqgvl7nzeUwdbN11TljoBlKEOkwtO21YtwloStjXsrzCkzPr2GqCaqy/jerleUHx/iShrurACKCpdY1HRIAGHf0qUo64gWN27QwC7NFNMEgf5M7AHcZFd6xGHnR2AZjRQr8aJ56wjSt7LAKIlSZXrJHOlrC4Kq3U1OxZ/TRONpBeLXBSYdrIrg1B90UAlyC06l7vzBMUmsRQkbdD8/2DXWsLykzkaM6qCrvF3WY/zuo+GNdBYDoNm2KQwUi1XaTrLOcCO64J8HMzNMYqLTKi3hJAqyyGcSlVFT3a81OYFydgKsR1dJLp9Ma6MK8UZVjF1C9sRtN7NWBklhuHSBLqOm1tNeWaPZn5E7uTvul3azyq9l2UdE7YoB7JW1m4ukFZNkMODFc2em1Nnsy8+6F2lAZqZ5JWCmCcgTNvc5NrvljZZRxz5+2wmxWdTCLb3lpCGAURZ1tU7RGg5rc+NMuyyZG2nXITSQA0sdvbHZWOPj4uoUB2xoY8kbIxsHYXSmNYGsHQ3+Kn8T4dUIXo189o1y8LXXIeWGnOS2cRHafwCIczh65uLPe+OjA7Au3KqSIXUr9UZm5Qx3e16tp4sCmO063L6OiyKN/inUOZMwSjYzfhmuX9tRSq0QK7gwsn7hxX/b2Kh597a3hzg1VAmghvrBpku3NgqQNBa0xkFmUgT67lNohpxspKL3N+Sl+AJlkR+QB93tORQgXYoZ8y7p0aCo//aivwYDk+itddoIuxXcP7wQcdEpEBzdhNuQ1Wl5wUUk8CqeQqLo0UQqE39BmNhADs+csP2Pvyfi5oSdKu4lnIXiJIPgf5CbVrck+N7JQXf3KEUsmZvxPpxB0CZJFjMkfd2hkg5idUQhCgc+zj+xkGZV8nZCgCrPy8pU+2Hs4FZ8yTGpHUKJtqPjWPUVwifn5CPlNcMiuMeyAEpzA+q3/4nt7qe0w4sktTxzQNQbOqa2mlY3qLcDH2VkZUk2NWuM+Bgu8QavNIBdvOL4x53NCcDQzbS2La+wmk310bXCDIXp4ICPR4kIt4GrEtD1zOsj7++03jRudsZj88m08LwqQBUVhfJRks1X2cw+/X2Wtj77lZQzGXA0SSP4fRs8G2eGDgau0t1Wk4Wzz3x5vz/h6xBaPq37eZhkDXReVSIHIjrpYGbFL4PBMe+QD/W/oqkjQp8uNjI/OnpTLm2EnV0VCU+qLi+yVsIIEk00ATyQA/BwA4s2DFJi9a/o8lUXT1WoGk52AByaNj6K27k5JRvCxqmnMCfOyqMArTs5KYq9rH9qoJwBCyoUuQl9QqpoA33Y12tatnhKayPW2rld/wl9cYVYX8GJ7ySZPtavmUF8ohwiCt0N5ZSdbgGdWohQgvbMWBh81Ea6ZOuRTYohec/CJUXfcTdXt7P5vcHlPNeA8SBjsADELlX9BzOLKAZvnXQxsjUnHOwYKFH3yHJjpAdIvr/tz0U/AfP/ldXgbK8mhVKj6lAuq8kHzPnmt8IxAiAKdFzpSvas8R+5uT7tU0ZoRB6ce43/AbY1Zsid6qO4hsKY7Kho3ZHnquHVqmPTEt1+et5uNAHRyIcA8RzX6egzU5uAYcLaGezF9NngSKPx1pywiARV536eG6PB2VoCMCQ7Os1HOKYtRTqQq9hNeNuuJBggSoYp9F80oPx3pW4f46rDXAnTSEeIG9c4SylQGvVWUAURhpgXIvHyFm0kK32EdHdenRcMmhUYZoLEEh5NqxPWBE5LwSEydKjxGuNEd7e2SS1ZlO7iTKhIm2XKQhi5xOyH2f+xRqokrMO9/6X8vP1o/kTOU6TfCvnNIODB6CwOn3Dl0mvzew0OEZdVdgR2w2fJTjxPMEJPfKlIKZ7lcbPU0Y5/LedMwGHYkBr2uHjYcH3XwexA8QSHO8SPsNDfhW4B2y2gAovT+RQg2fDyRWJ63VI1jfQUtj443xD4jC7IZfpaHzOeWnxQyl0KbiWlsFDCGSMiLSIxpy/dbXLXrDKkWTOTEXm6BTvmhYH2PdAIIP0qDXDTz5xH9dadINziPBxkb2iPAojZnEvfD4vROGT2VD0e93j2GDiN080Xs4NVK7exofxxK1e0QG1vHmnM4PX//4+8XOZVRTB/L88/uULV89zoh2g4wrz96+G4boxj17D7JaMvN5+FAhJbybzuGIhdijWLA3JxzqkMVtbKG1RStwhbl9SNu19BvE8cN33tCAyVMYcBEqXvXQprfNtvm2oSnJFudNOEs+AWRBeXS6AlKraPcU0bph0Yr7lH5NY6PZSLiAcBRhKpamWB6p5G+H1FHgGulplSEAz1UM19clisgwon8DdaAi23tqz3QLAXFOG/FCRiktzMtIMVSvDLSXYCej4tulwKObkVLw48qX1mMii0y4rgQAjpmrvSuSNKE0VphG+MSbZ6rs9cmVMEbPCojqZP5lcdPKcuaAkJNbMj8D/uJ1oQs7G8g+bx1JTOL1pPhJw3nOrMNES1g4HAdh6myGmxHXs+1cmgFA4YMIlZcOpwwNBXIjk1RY+b8+4AuG85fb7Ukq6d0ABNDJO2lm8RCViE5z21biRYaaACeTl2oik5DU0nCgOx+nhN6Pcw5L1xz/RMkC5NsKv7+2P9uS3GbYQHvLjQ9QOeBYlEcL2DEwimPZsn7uh/yDn8l3t1+aNNGF4Lc6MQzjBVNWTpatZB2KgmCf4++U+xzSWMPLTR3d1PGwnflDE/FNqlofYwJtQZ8NsDDbsLf5Xa79WUcH/whF4g/IfhUtFbz/vs9ySYnsJbK3Q/I9ZSmm2gXoJDYMByUiXaJp9XHIVCtHXnIblUdhOMOlysO60gk2de4S5zLI/tJ5aM/2cSwzjFMllh7uau3GNQPqc/BtRImDtU4GtBHyLWGVdjdRtvu7h45Or2gENZQUu7/PVv6MoO1dGrV+qeQKXhqRCggcYQgrIDN3dbVOqy2sXr9200HAo5BcRoGEeMLizYMIZ6ZVL+zz4dQm1JV5gTkr+ptKOk7wwD+JJvhvIq60dk+GqpqNbF7BhIyOduAy6CX2ierQ8feDhrV5GA6d1iKA//9Y3QAyCmczCcFZDrM4Pl6VFL297ZxzNpd5JAcjmUqSA0aRu8/ClpRa8xwVKivjXVkDp6smbcMLaQmYznB4GMLgtRuMm/WBftrT/KlT/c+gMKWThc7XDLmbQ+xTW2DDZoNEUU0Z23hzcWd/HsakDe3p9DuPX9RE09rfkMWlnqIoZ3liJDOLx9/iD/7ubEY3MBbT+jgjQcTs1ky5LsovdtWkm3iqty4KApG3TmWDCFDMHHNvo+ZAREOi3rQ7p3RpLU3SvNKLVNkAOugRpj53ByB4O4ttropz+ip/IM0ti9W02M2uYi0b0QjKUur6uBCGu2OoWvjrimSq/jdqeuQxj/gq2WMJM9yL+NXb4HRpu5C37XV6r9KFncSOJeERLF2Kw+0f+iirQgh9us5bIP4qzSCB89Rt3s5zniN8Ic67VuozP2SNTZwcAsGXJhQ4NdTNW2IYlE0WzQCpKKvlbtAB/eQl7bgUABBKp3j+lUs5Tvuj8Nvz4a2wd+SoaTC8ul0GTeQdzGlxfaFUUEAW4tkdW71Q4pdZr8vWEtLSYSdu8wRVyxKlO0WJE65DN4VJVdoznty2mnvzDm+zPImsY28ncqNbd/7iIOvKiuqZAZJ5dpz+pgIwYUFc+vRD75RHB0n8GdA0pKrjg+ZWjuCUmNtxwaeal4JLL4ReS9v0243m8vvuKrWI039KQq+mCbNhcjl/Wv9sH8bHVi3P40dUObVf5DQ2Jc+h7sQEEHO6++R7rgzEylL0EUnAs/AKFpaqOlr0AmWeGMMnzfihm8XE7nFMcy4CBkwquOQvohC3Ip/Hefm0w5uWctQJH178B6gfOMdG+TodU84WgOCYYUeKYKs/xRtzw8QhRpCeKTNhtsdg+6JnZSI8rym46pCDHRFDJFoBxDX1GUx4O+jhpLX6yIvZi3wzSJ4EeaFpiplQmIVgmQtOR5d4+r6FE2S9HKEKnSjuiUoXsFrUP9n9hsYniscG/TRyzChgo6Y2jkoH1hj6kqAUzaPPQYYSdleHiqD/JmlZRlzWSySnIqIZ54ZUSN5hzR9wU32GWYuJVDWD8NQsx1Ef6GhRoejAirqEjhfawyfNGTa58uE0CEznbUnqxVj5MqmP9YLtXgUi2lCRXdtD4T8uozNjkxlkAOoYn7eJdInowE8ilqrmBCVbwlGoCHCVGmcyb3laZ6ZYZPjbki4ySbwAjkhNXOTTUHCNuuAtHmhoPwVyWI47Z43ovVDvrvGZwDgK8Kpb36AyfxJDWKt67j7GNFLTxhoXhqNpfFWG9NoCxgpOge6xhitKFigL9Z9dVdObjVQSBaQJU1P/mD/RX+T2/r4yQAKaadf2RJq7COAWH8km6MEMtocIEKEdFojam8UlIbhrMdTbu7jZ7XTOGR9nnAcWDXJY6cbtx3ICl8lsOV0CX8n+Qvs0UgiwPUKffuLnya8jylYLIo8dxKMr98uK2BAWwSFzr3na4QXW+BXbFeJmkCVcZYOqljwZNhkFXekKthlV9Wa1O2yrrSM+ZygU77F9DsozrMGVtxjbBFlo/YJQkMOmZlZTR3yHA7X2Nr+4EZDjfDIHfgKHjVZYTIQx0fV9ZbxoJcOaW2+YMhbgAEd1azhpAcyMKomZIUMV1STFDLjP/IfhWbAFd6bwG4C1VPD3Vfsq/V45oK2w9B68CmbJCW9cKYZ25Y3/p2izm4LzUMCVwyztnxna9w4fxNVeyewGTS4LYlrHEbDsSmMXz5gnd0KZ/6T9XQretNWBNnnEHMm406vUPHLdHscFx6/hwRshWLuqFhD+/LqYJkxm+0cIK+PMARh9Fm2oQjBQLGJr+biuBD58vVh54hOpq87RT4TbO4Ibhw/C5r7CexJaMQ+4YjLHCoexonpqce/97UYv3pmqf4QD+jpEJeWRINn+feTyLA0fwj11dsp19cgr/gKYDmbTah2yMDB2DoZ/rMyFJsxa9sU1gkum4vGttrpHCY3lKgfOGS5SijtDRefQIiARrSdAqlexnfNrN0Y7pa2GJGbBJSnoMOsKG6enfil9ccyzFKvk+x0KQsY96Xm2cTJKthmmtADYhxXTZk7Y2sc/DbWVbNutLVZ3fTrkZyxJLlNrZx0cYRvbr/N7gz03SL5G7/HyvGX93lWOuQX9G7GiYXcM7U5RDAdr8ZYA7IEZtvNCfrWWNoB7BldjbQqZUgC0ITc2HbU7kC5bUvY2p4jrHjXZJjM1PrKz8WmMbGlY7Y9Cw1ndBeYSolwOe2mEviK70PefGAGQncsEZu4XDpd8WDb0KaGy8WzRaysmxWfbYdcP97R3nCG5uMp4jJZVD31fSzsTFdNK8EzNoTEbl3wTLUKLNQ48s36/9Q+dzuXMDGcYsme+t6H0taroUrI0wawLT34+J6NL3HnrCe/aguEohUuvsTbIEYzVbgw9ClTjxPbTKmOlyYPa/rU9RnSQrheT9JDBFqOQ+GZbxoBeefegupz/FJf8srBCVGpu6ieZEl4JTGINNsmRFHXQ1Z4Vq0f97gSGZiN+JTg6FzWYzsnidGqAR4F/oRbnU9V3cm2ZBd9LHcxDnZb7CdBdI=

矩阵
多维数组：a[n][n]
交错数组：a*[n]
邻接矩阵：记录点与点之间连接关系的矩阵
邻接表：记录邻接关系的链表数组 List
广义表：类似交错数组，元素可以是一个（原子），也可以说一个广义表，可以为空表，第一个元素是表头，其他元素组成的表是表尾
所含括号的层数为深度

矩阵压缩存储：
1、只为非0元素分配空间
2、对称矩阵， aij=aji，只需要存储左下三角或右上三角

稀疏矩阵是0元素很多、非0元素很少的矩阵。稀疏矩阵可以压缩存储，常用三元组表存储，存储行数、列数和非0元素的个数（分别是哪行哪列什么值）
三元组表：i行j列e值。另外单独存储行数列数和非0元素个数。下图中左侧为有7个元素的稀疏矩阵，右图为存储它的三元组表（感觉也没节省多少）

图
图 G(V,E) 是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)

概念：
  • 无向完全图：在无向图中，如何任意两点之间都存在边，这个图就是无向完全图。有n(n-1)/2条边
  • 有向完全图：在有向图中，如果任意两点之间都存在方向互为相反的两条弧，这个图就是有向完全图。有n(n-1)条边
  • 与图的边或弧相关的数字叫做权（Weight）。
  • 带权的图叫做网（Network）。

表示方式
  1. 邻接矩阵(n*n)：一个n*n的顶点数组，记录两两结点之间的连通性
  2. 邻接表 (n*list)：一个数组，每个元素是一个链表，表示该点相连的其他邻接点
    因为是链表，所以使用头插法建立更方便

  1. 十字链表（邻接表+入度）：首元结点 {data, firstin, firstout} 为每个顶点建立in和out两个链表，分别存储该顶点的入度结点和出度结点。链表结点 {tailvex, headvex, hlink, tlink, info} 分别存储弧尾、弧头、弧头next指针、弧尾next指针、权值信息
  1. 边集数组 (e*3)：也是数组，元素是有3个属性的一维struct；权值有可能是0或负值，所以∞表示无边
图
DFS 深度优先遍历
找到一个未访问点后继续沿着这个点往下访问，在没有碰到重复顶点的情况下始终往左走
但是这样有可能漏过一些结点，所以如果有未访问的结点，则需要作为起点再进行DFS
template<class T>


void MGraph<T>::DFS(MGraph G, int i)


{


       cout << "v" << i << "→";//输出访问的结点


       visited[i] = true;//bool已访问


       for (int j = 0; j < n; j++)//搜索未访问过的邻接点进行递归


              if (G.Exist(i, j) && !visited[j])


                      DFS(G, j);


}
用邻接矩阵需要O(n^2),邻接表的话只要O(n+e)顶点+边

BFS 广度优先遍历
先访问v，依此访问完v的所有邻接点，再从下一个点开始遍历其邻接点
因为是层序遍历，需要一个队列做先入先出处理，访问v点即把其未访问的邻接点入队，不需要递归，只需要对队列循环（和树区别不大）
void MGraph<T>::BFS(MGraph G, int i)


{


       int k;


       queue<int> Q;


       cout << endl << "v" << i << "→";


       visited[i] = true;


       Q.push(i);


       while (!Q.empty())


       {


              k = Q.front();


              Q.pop();


              for (int j = 0; j < n; j++)//循环处理v[i]的每个可能的邻接点


              {


                      if (G.Exist(k, j) && !visited[j])


                      {


                             cout << "v" << j << "→";


                             visited[j] = true;


                             Q.push(j);


                      }


              }


       }


}
时间复杂度和DFS一样

DFS适合目标明确，寻找目标解的情况
BFS适合不断扩大遍历范围，找到相对最优解的情况
都需要visited

图的最小生成树
目标是 把图的n个结点连成一棵树，使其n-1条边权值总和最小
生成的前序遍历树：[v0, v4, v3; v5, v2, v1]
生成算法：
  1. Prim：O(n^2)。从一个点开始找点连边，每次都找目前可连的点中权值最小的，已经连过的点不再连接（不构成环）
  2. Kruskal：O(eloge)。以边为基础找边连点，每次都找最小权值的，只要不形成环路（如用边集数组，让他们按权值升序排列）
  3. 如何判断是否会形成环：看边的两个端点是否已存在当前生成树中

最短路径问题（找一条起点到终点的最短路线）
Dijkstra [BFS，贪心（贪心是特殊的DP）]
从起点开始，对结点的每条边都计算，更新能走到的各点的最短路径值。选取路径最短的那个点作为下一个结点，直到终点
原理：在找到的临近点最短路径的基础上更新到更远顶点的最短路径 （比如v1,v4都能到v3，但是取离起点近的那一个）
最后可以得到起点到各点的最短路径值

需要：
数组P 表示到各点经过的前驱点，以便可通过逆推得到路径
数组D v0到各点的最短路径的权值
数组final 记录查找过的点

时间复杂度O(v2)，如果用优先队列可以优化到O(elogv)

Floyd


  • 用顶点表示活动的有向图，称为AOV网，以邻接表表示，数据结构包括一个记录入度的in。
  • 拓扑排序用于生成有向无环图的拓扑序列，检测该图是否有环（顶点v的入度是以v为终点的弧的数目，环是指一个点经过路径能回到自身），并生成有向无环图DAG的拓扑序列。这样可以检测工程能否顺序进行
  • 原理是每次从有向图中选择一个入度为0的顶点输出，然后删去，并删除以此顶点为尾的弧，直到输出全部顶点或不存在入度为0的顶点为止。

实现：比如用邻接表存储，用queue记录所有入度为0的顶点，那么每次就是从queue中取出结点并修改其关联结点的入度... 再检查入度为0的点入队
时间复杂度 O(n+e)，因为让顶点入度减1的运算执行了e次，而搜索入度为零的顶点花的时间是O(n)

关键路径（找一条最长路径）
有向无环图，用顶点表示事件，用边表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。常用于估算工程完成时间。
在邻接表数据结构基础上加一个weight权值域。每到一个结点，找到达这个结点最长的那个路径，就是关键路径
4个参数：前2个针对顶点vk，后两个针对弧ak，由前2个求出来
只有进入该顶点的所有活动已经结束，从该结点出发的活动才能开始
etv 事件最早发生时间（即进入该顶点的所有活动已经结束的时间）
ltv 事件最晚发生时间（由于可能有更慢的其他路径，所以等待一会儿再开工也来得及。last建议从右往左推出）
ete 活动最早开工时间（根据etv[j]求得）
lte 活动最晚开工时间（根据ltv[k]-weight求得，j、k点是边的两个端点）
当ete=lte时，即在关键路径上

具体过程
由事件vj的最早发生时间和最晚发生时间的定义，可以采取如下步骤求得关键活动：
A、从开始顶点 v1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。
B、从完成顶点 vn 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:
C、求每一项活动ai(1 ≤ i ≤ m)的 最早开始时间e(i)=ve(j)；最晚开始时间：
求出 AOE 网中所有关键活动后，只要删去AOE网中所有的 非关键活动，即可得到 AOE 网的关键路径
注意: 并不是加快任何一个关键活动都可以缩短整个工程完成的时间，只有加快那些包括在所有的关键路径上的关键活动才能达到这个目的。只有在不改变AOE网的关键路径的前提下，加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间。

查找算法
顺序查找 O(n)

二分查找 O(logn)
def find(l, r, a, t):


    while l < r:


        m = l + (r-l)/2


        if a[m] >= t: r=m


        else:         l=m+1


    return l if a[l]=t else -1


或者递归：


    if m <= t:


        return find(m, r, a, t)


    else:


        return find(l, m, a, t)

插值查找：能根据因子1/k，推测出大致位置

分块索引：构建块内无序、块间有序的索引表，加快整体的搜索

跳表：实现链表的二分查找
B树系列（2-3树、B+、B-、B*树）：每一个节点可以有多个孩子，可以存储多个元素，元素间存在特定的排序关系，降低索引树的高度从而减少IO次数，可以避免多次存取内外存

二叉排序树，AVL树

Trie，又称为单词查找树，是哈希树的一种变种：
根节点不包含字符+子节点仅包含一个字符+子结点的字符互不重复。N叉树，实际上是一个状态机

应用：如用于统计、排序和保存大量的字符串 或 数字，查找前缀，经常被搜索引擎用于文本词频统计。
优点：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高

红黑树
二叉搜索树的进阶，但又不像AVL一样要求"完全平衡"，通过标记红黑、旋转，始终让树高保持在logn，因此各种计算也必在logn数量级内解决
  1. 根节点、叶子结点(null结点)是黑的
  2. 红结点的两个子结点必须是黑的

哈希查找
哈希值计算-
开放定址法：F(key)=a*key+b
除留余数法：F(key)=key % p
还有随机数法等等....
解决冲突-
开放定址法，遇到冲突就让F(F(key))作为地址，如果还是原地址就+1；
拉链法，将冲突的key存在链表中，map只引用头指针
计算平均查找长度-
求出查找每个数需要几次，计算总查找次数/关键字数
装填因子-
实际占用空间 / hash空间

排序算法
冒泡排序：每次将一个数冒泡(swap)到最前面，得到一个topk

选择排序：找一个最值，记录下标，然后交换到最前面。相比冒泡排序缺点是不稳定（跳跃交换了，如果有两个相等的元素，因为交换本来在前面的元素被放到后面了，那么稳定性就被破坏了）

插入排序：适用于已经排好序的数组，每次找到元素应该插入的位置，然后比其大的元素要后移，空出位置让其插入

堆排序：完全二叉树，需要先建堆，支持插入、删除元素，全出堆即为排序

归并排序：二分、递归、排序，归并、回溯、合一。自下而上，特点是稳定

快速排序：选取一个pivot，用头尾指针轮流向中间扫描交换，一趟下来将数组重排为左右两部分，右边所有元素都大于左边元素，然后递归二分，最终全部有序（最好nlogn，最坏可能n2退化成冒泡排序）
由于是自上而下，相比归并排序能省去合并的步骤，因此更快！
快排的优化点在于 pivot的选择（median-of-three选端点中点）、小数据用插入排序代替（包括递归到小数组时，有个阀值）、split-end划分算法（降低equals元素参与递归的开销），经过这些优化之后，就够成了STL的sort

class Solution:


    def sortArray(self, nums: List[int]) -> List[int]:


        if len(nums) <= 1:


            return nums


        # 随机取数 避免因为pivot区分度不强造成的算法退化


        pivot = random.choice(nums)


        # O(n)划分


        left  = [x for x in nums if x < pivot] 


        right = [x for x in nums if x > pivot]


        mid   = [x for x in nums if x == pivot]   # 相同值保留 避免因为大量相同元素造成的算法退化





        return self.sortArray(left) + mid + self.sortArray(right)  # 将左右partition递归并自动归并





链接：https://leetcode.cn/problems/sort-an-array/solutions/

基数排序：箱排序，如我先对一组数的最高位进行array[num]放置排序， 然后再对次高位进行放置排序…… 每次我排个序时间都是O(n)的，这样我的总排序时间就是线性的，也就是O(kn)。
这里k取决于你选的基数，比如基于十进制位数，那么k就等于lg(n)；基于二进制位数(bit位)，k就等于log2(n)，这样就和nlogn的算法速度差不多……
这是一个稳定的、非比较型排序，一般要快过基于比较的排序，比如快速排序




Published by Kira on

comments powered by Disqus