一刷总结（ 代码随想录）_t.erase(t.end() - 1)

代码随想录

1. 数组

二分查找:

• 暴力解法时间复杂度：O(n)

• 二分法时间复杂度：O(logn)

双指针

• 暴力解法时间复杂度：O(n^2)

• 双指针时间复杂度：O(n)

滑动窗口

• 暴力解法时间复杂度：O(n^2)

• 滑动窗口时间复杂度：O(n)

模拟行为

循环变量原则

2. 链表

• 单链表数据结构

struct ListNode {

int val;

ListNode *next;

ListNode() : val(0), next(nullptr) {}

ListNode(int x): val(x), next(nullptr){}

ListNode(int x, ListNode *next: val(x), next(next){}

};

• 种类：单链表、双链表、循环链表

• 存储方式： 节点分散，指针相连

• 增删改查

经典题目：

虚拟头节点；基本操作；反转；删除倒数节点；相交；环形

3. 哈希表

理论基础

1. 哈希表 hashtable

2. 哈希函数 hashcode: 传入的key映射到符号表的索引上

• 哈希碰撞: 多个key映射到相同索引上时

拉链法： 冲突元素存储在链表中

线性探测法：保证tableSize大于dataSize

3. 哈希结构

• 数组

• 集合set

• set 红黑树

• multiset 红黑树

• unordered_set 哈希表 无序

红黑树是一种平衡二叉搜索树，key值有序不可改，只能删除或增加。O（logn）

• 映射map

• map

• multimap

• Unordered_map

解决哈希问题时，集合优先用unordered_set；

有序用set；有序且重复用multiset。

map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

哈希法：快速判断一个元素是否出现集合里

算法记录

• 范围for循环

for(int num : nums2)

int num;

for(int i=0;i<nums2.length;i++)

{

num=nums2[i];

}

1.通式for(要遍历的数据类型 遍历变量 ： 遍历对象)注： 遍历的数据类型要和遍历的对象元素类型一致

2.范围for循环不能用于循环体中有改变容器大小的操作。举例子：循环体内不能向vector容器添加元素。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/245825