C++学习笔记

哈希表 适用条件：给出一个元素，判断在集合里是否出现过 哈希结构： 数组 set集合 map映射 最常用：unordered_set 简单操作： unorder_set cnt(a, a+6)：输入参数为第一个元素和最后一个元素之后的迭代器，因此有a，a+1，a+2，a+3，a+4，a+5共6个元素 s.insert()：插入 s.erase()：删除 s.size()：大小，元素个数 s.empty()：空 s.find()：查找，返回迭代器。没找到返回end s.count()：统计元素出现次数 s.end()：end()并不是最后一个元素，最后一个元素是end()-1。因此返回的是最后一个元素之后的迭代器 1有效字母异位词 思路：哈希表-数组 伪代码：123456int record[26] = 0;for 遍历s字符串 频次表++for 遍历t字符串 频次表--检查record是否全为0 2两个数组的交集 思路：哈希表-set 伪代码：12345将数组1初始化为setfor 遍历数组2 如果数组1能find到，也就是有共同的元素 添加到结果set里ret ...

队列和栈栈1.1重排链表 思路：链表大综合 伪代码：1找中点，反转，合并 1.2有效的括号 思路：栈 伪代码：123456stack<char> stk;for 遍历字符串 if c是左括号，栈里放右括号 else //c是右括号 if 栈不为空且c=堆顶元素，弹出栈顶元素 //括号匹配 else return false //不匹配return stk.empty() 1.3逆波兰表达式求值 思路： 后缀表达式，算符写在后面，(1+2)(3+4)=(12+)(34+) 数字入栈，算符取出栈顶两个数字运算，结果入栈 伪代码：12345678stack<char> stk;for 遍历字符串 if 是运算符 弹出堆顶元素 运算 else //是数字 入栈return stk.top() 1.4用队列实现栈 思路：让后入的元素到队首 queue1主队列，queue2入栈辅助队列 后入元素进入queue2 queue1的元素进入queue2（后入元素到队首了） queu ...

队列和栈 双端队列：只操作头尾，队列和栈是双端队列的子集 队列：先进先出 栈：先进后出 链表：实现简单，直接复用api 数组：实现复杂，数据搬移O(n) first和last指针 循环数组

优先队列详细看这个视频：BV1P64y1h7dk 引入头文件 定义 priority_queue <int> que; priority_queue <int, vector<int>,less<int>> que; 内部元素类型int 使用容器vector 比较方法less大顶堆，greater小顶堆 对象名字que 默认最大堆 操作 que.size()优先队列元素数量 que.push(x)向优先队列插入元素x que.pop()删除优先级最高的元素 que.top()访问优先级最高的元素，堆顶元素 que.empty()判断堆是否为空 1234567891011#include <queue>... priority_queue<int> que; que.push(7); que.push(1); que.push(5); while(!que.empty()){ cout<<que.top()<<""; qu ...

链表双指针技巧1合并两个有序链表 思路：两个链表各有一个指针p1，p2 while循环每次比较p1和p2的大小，把较小的节点链接到结果链表上 伪代码 12345678while (...){ if (p1->val > p2->val){ p->next = p2; p2 = p2->next; } else.. p = p->next;} 示意图： //初始 p1 1->3->5->7 p2 2->4->6->8 //第一次循环 p -1->1->3->5->7 p1 3->5->7 p 1->3->5->7 //第二次循环 p 1->2->4->6->8 p2 4->6->8 2单链表的分解 思路：同两个链表的合并，while循环 ...

数组双指针技巧1快慢指针1.1有序数组去重 思路： 如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2) 快指针探路，找到不重复的元素再赋值给慢指针 伪代码： 1234567while fast<size{ if num[fast] != num[slow]{ slow++; num[slow] = num[fast]; } fast++;} 1.2数组元素原地删除 思路：如果fast遇到值为val的元素，则直接跳过，否则就赋值给 slow指针，并让slow前进一步。 伪代码： 123456789val=2[0,1,2,2,4]→[0,1,4]while fast<size{ if num[fast]!=val{ num[slow]=num[fast]; slow++; } fast++;} 1.3滑动窗口框架1234567891 ...

前言学习路线总纲https://zhuanlan.zhihu.com/p/157355850 讲C++面向对象讲得很好https://zhuanlan.zhihu.com/p/225175529 C++学习路线https://tobebetterjavaer.com/xuexiluxian/ccc.html 数组和链表 数组特点：首地址已知，数组元素大小已知，存储连续 链表特点：存储不连续，根据next指针一个一个找 数组缺点：删除元素，后面的元素要挨个往前挪，总之要满足紧凑、连续的特性，有一定代价 链表缺点：多存储一个指针的空间 代码实现 数据结构的代码实现主要就是增删查改 数组： 检查边界，注意增的边界可以<= 末尾增：扩容2倍 中间增：数据搬移，赋值 末尾删：小于1/4时，缩容为一半最后一个元素置空，不能直接size-1 中间删：数据搬移，删除最后一个元素 双向链表 构造函数：哨兵节点，不用判断空节点 插入元素：插入元素指针插入元素前一个的指针插入元素后一个的指针 删除元素 中间插入元素： 遍历到第index个节点（优化，前向遍历和后向 ...

1 导读 泛型编程 虚函数 2 转换函数conversion function 将一个类的对象A转换为另一个类，比如一个分数类转换为小数double类型 operator double() const{ 相当于对double函数进行重载 3 构造函数关键词explicit 小数转换为分数 non-explicit，不能和转换函数共存 explict，让编译器不要自动转换，例如把3变成3/1 （代理模式） 4 pointer-like classes 智能指针：class设计出来像一个指针 *操作符重载，return *px ->操作符重载，return px 迭代器 5 function-like classes ()操作符重载 select1st (()) 6 namespace 使用场景：两个人写的程序合并时，出现重复命名的情况 7 模板template 使用场景：想要让class中部分类型允许使用者指定 用法 template<typename T> commplex<double> c1(2.5, 1.5) ...

1 导读 泛型编程 虚函数 2 转换函数conversion function 将一个类的对象A转换为另一个类，比如一个分数类转换为小数double类型 operator double() const{ 相当于对double函数进行重载 3 构造函数关键词explicit 小数转换为分数 non-explicit，不能和转换函数共存 explict，让编译器不要自动转换，例如把3变成3/1 （代理模式） 4 pointer-like classes 智能指针：class设计出来像一个指针 *操作符重载，return *px ->操作符重载，return px 迭代器 5 function-like classes ()操作符重载 select1st (()) 6 namespace 使用场景：两个人写的程序合并时，出现重复命名的情况 7 模板template 使用场景：想要让class中部分类型允许使用者指定 用法 template<typename T> commplex<double> c1(2.5, 1.5) ...

10扩展补充：类模板，函数模板，及其他 静态static 静态的函数只能处理静态的数据 静态数据初始化方法 静态函数两种调用方法，没有对象也可以调用 Singleton 构造函数放在private，限制对象只有一个 优化Meyers Singleton cout是ostream类型 模板template template <typename T> 函数模板 template <class T> namespace 将名字封装，using namespace将封装打开 更多细节operator type() const类型转换重载explicit构造函数pointer-like objectfunction-like objecttemplate specializationStandard Library C++11等variadic templetemove ctorRvalue referenceautolambdarange-base foe loopunordered containers 11组合与继承 继承 复合composition ...