7哈希表
哈希表
适用条件:给出一个元素,判断在集合里是否出现过
哈希结构:
数组
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 ...
6队列和栈解题技巧
队列和栈栈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 ...
5队列和栈基础知识
队列和栈
双端队列:只操作头尾,队列和栈是双端队列的子集
队列:先进先出
栈:先进后出
链表:实现简单,直接复用api
数组:实现复杂,数据搬移O(n)
first和last指针
循环数组
4链表补充优先队列
优先队列详细看这个视频: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 ...
3链表解题技巧
链表双指针技巧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循环 ...
2数组解题技巧
数组双指针技巧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 ...
1数组链表基础知识
前言学习路线总纲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
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) ...
面向对象下0
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-13
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 ...