Sky小天的个人博客

coding问题：即不涉及算法，仅需知道数据结构怎么使用即可解出的问题 哈希表：在c++中哈希表为：unordered_map<T,T> 在进行增删改查其时间复杂度为常数级别（但常数级比数组的直接寻址大） 7）补充：内存占用为8字节，与存入数据的内存大小无关 有序表： 进行增删改查时时间复杂度为O(logN) 7）补充：内存占用为8字节，与存入数据的内存大小无关 链表：单链表：使用struct实现，包含数据和指向下一个节点的指针，类型为自己创建的节点类型 双链表：使用struct实现，包含数据和指向下一个节点和指向上一个节点的指针，类型为自己创建的节点类型 对链表操作的函数，若改变头部有返回值，不改变头部就是用void 两个链表，从头开始比较数据大小，谁小，谁向后移动，相同时候打印并且共同向后移动 将链表的右边部分存入栈中，存完之后将栈中的数依次弹出与原链表左半边做比较（使用快慢指针，快指针走两步，慢指针走一步，当快指针走到底，慢指针刚好到链表中间）此方法用于笔试 使用快慢指针找到链表中点，将链表的后半反转，中间点置空从链表两边开始比较，最后要把右半边链表反转回 ...

对数器： 用于测试一个方法是否正确（使用一个速记数据生成器生成数据，将数据带入方法测试，以及一个简单的，不管时间复杂度的，正确的，功能一样的方法中得出结果并比较） 递归： master公式：用于求子问题为等规模的递归的时间复杂度 T(N)为母问题规模 T(N/b)为子问题的规模，a为子问题被调用次数 O(N^d)除调用子问题之外的进程的时间复杂度 归并排序：整体为一个递归排序，左右独立有序，再让其整体有序，整体有序国产过程中使用了外排序方法 时间复杂度为O(N*log N)，空间复杂度为O(n) 求小和：求数组中各个数的左边比它小的数的和 利用归并排序求小和，但是在比较合并时若右边的数小于等于左边的数，则先存右边数组的数 逆序对：在一个数组中，若一个数比其右边的数大（两数不一定相邻），则组成一个逆序对 快速排序：荷兰国旗问题：一个数组，对于一个给定的值，小于这个值的数放到数组左边，等于这个值的数放到数组中间，大于这个值的数放到数组右边 快排1.0：使用数组中最后一个数将数组大于其的数放在数组右边，小于等于的数放在左边，两边进递归，时间复杂度O(n^2) 快排2.0：使用 ...

基础概念六大组件：容器，算法，迭代器，仿函数，适配器，空间配置器 容器：各种数据结构 算法：各种常用的算法 迭代器：扮演了容器和算法之间的结合剂 仿函数：行为类似函数，可以作为算法的魔种策略 适配器：一种用来修饰容器或者仿函数或则迭代器接口的东西 空间配置器：负责空间的配置和管理 容器：​ 1，序列式容器，无序 ​ 2，关联式容器，有序 算法：1， 质变算法 a) 运算过程中会改变区间内元素的内容 ，如，拷贝，替换，删除 2， 非质变算法 a) 运算过程中，不会更改区间内元素内容，如，查找，计数，遍历，寻找 迭代器：​ 每个容器都有自己的迭代器，类似指针，但不单是指针 vector容器vector的基本操作： 判断vector中是否存在某个元素： 寻找元素在vector中的位置： max_element(begin, end)返回列表中最大值的下标位置，前面加*为取值 min_element(begin, end)返回列表中最小值的下标位置，前面加*为取值 string容器基本概念 构造函数 赋值操作 字符串拼接 string操作 栈操作stack ...

方法：字符串匹配​ 对于字符串s，将其两个连在一起如果满足移除第一个和最后一个字符后，字符串s还是该字符串的子字符串，就满足要求可以使用字符串的find函数来完成 123456class Soluton{public: bool repeatendSubstringPattern(string s){ return (s + s).find(s, 1) != s.size(); } }