以下内容结合了我的总结，若有不对，欢迎指教，前面的后期刷完后会接着补充
29.集合set
- 特点：①无序（排序不固定）②元素不重复
因此，插入重复元素的时候还是只保存一次
- ?判断以下是否是集合：
{1,2,3,3,2}? 不是
{1,2,4} 有可能是? ?{1,4,2}?
- 主要作用：
①检查某一个元素是否存在
②查找重复元素
- set有：HashSet、LinklistSet、TreeSet
- 哈希集合的运作方式：先获取元素，通过哈希函数获取它的哈希值，再通过查找哈希表进行操作。
- ?哈希冲突的解决方法：可以使用链表的方法。将next指针指向一个空间存储引起冲突的元素
- set时间复杂度：
Python3 Set
# Python3 Set
class Test_set:
def test(self):
# 创建
# 使用数组创建hash
s = set()
# 添加元素
s.add(10)
s.add(3)
s.add(5)
s.add(2)
s.add(2)
print(s)
# {2,10,3,5}
# 查找元素
print (2 in s)
# True
# 删除元素
s.remove(2)
print(s)
# {10,3,5}
# Size
len(s)
if __name__ == "__main__":
test = Test_set()
test.test()C++ Set
#include<iostream> //c++标准头文件，可以使用cout，cin等标准编译用法
#include<set> // 使用set需要带上这个文件
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin、cout、map、set、vector
int main() {
//定义
set<int> s;
//添加元素
s.insert(10);
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(2);
//{10,3,5,2}
//遍历1:for
for (int c : s) {
cout << c << ' ';
}
cout << endl;
//遍历2.1:使用迭代器
set<int>::iterator it;
for (it = s.begin(); it != s.end(); it++) {
cout << *it << ' ';
}
cout << endl;
set<int>::iterator it2;
//遍历2.2：降序迭代器遍历
for (it2 = --s.end(); it2 != --s.begin(); it2--) {
cout << *it2 << ' ';
}
cout << endl;
//遍历2.3：逆序迭代器遍历
set<int>::reverse_iterator rit;
for (rit = s.rbegin(); rit != s.rend(); rit++) {
cout << *rit << ' ';
}
cout << endl;
//遍历3：使用foreach遍历
for (auto it : s) {
cout << it << ' ';
}
cout << endl;
//查找元素
cout << "是否包含元素2:" << s.count(2) << endl; //返回1为真，存在
//是否为空
cout << "是否为空" << s.empty() << endl; //返回1为真，为空
//删除元素
s.erase(2);
//清空集合
//s.clear();
//size
s.size();//返回元素的个数
return 0;
}力扣 217 存在重复元素
使用map的时候是计算每一个数字出现的次数，使用set则更加简单，可以直接查找集合中是否有该元素
Python3 217
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
s= set()
for num in nums:
if num in s:
return True
s.add(num)
return FalseC++ 217
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> s;
for(int num : nums){
if(s.count(num) == 1){
return true;
}
s.insert(num);
}
return false;
}
};力扣 705 设计哈希集合
思路：设计一个在【0,1000000】的数组，数组中存放bool类型数组，索引就是数值，比如要是存在1，也就还是查找索引1对应的值为True
思考：占的空间大，然后要知道范围才知道需要多大的数组空间
Python 705
class MyHashSet:
def __init__(self):
self.hashset = [0]*1000001
def add(self, key:int )-> None:
self.hashset[key] = 1
def remove(self, key:int) -> None:
self.hashset[key] = 0
def contains(self, key:int) -> None:
if self.hashset[key] == 1:
return True
else:
return False
c++ 705
class MyHashSet {
public:
int *hashset;//[1000001] = {0};
// int* array = new int[100];
MyHashSet() {
//this->hashset = {0};
this->hashset = new int[1000001];
}
void add(int key) {
this->hashset[key] = 1;
}
void remove(int key) {
this->hashset[key] = 0;
}
bool contains(int key) {
if(this->hashset[key] == 1){
return true;
}
else{
return false;
}
}
};34.数据结构---树
- 树描述的是父子关系
- 术语
- 结点：每一个元素
- 根结点：第一个开始的结点
- 叶子结点：没有孩子结点的结点
- 高度：从下往上计算
- 深度：从上往下
- 层：从根节点开始数
二叉树
- 普通二叉树：每一个节点最多只有两个节点，可以没有节点
- 满二叉树：所有叶子节点在同一层，除了叶子节点，其他节点都有两个节点
- 完全二叉树：从树的根节点，从上到下，从左到右依次填满节点形成二叉树
二叉树的遍历：
- 前序遍历：根结点---左子树---右子树
- 中序遍历：左子树---跟结点---右子树
- 后续遍历：左子树---右子树---根节点
前：A B D E C F G ????????中：D B A E F C G ????????后：D B E A C G?
?力扣练习题：144? 94? 145
堆
是完全二叉树，且每一个节点都要 大于等于? 或者? 小于等于 孩子节点，
?
?特点：
- 最大堆：最大值是堆顶元素
- 最小堆：最小值是堆顶元素
Python 堆的基本操作
# 最小堆 Python默认创建最小堆
# 想要最大堆 将存入的数值转为负数，取出再给它取负数
import heapq
class Test:
def test(self):
# 创建最小堆
minheap = []
heapq.heapify(minheap)
# 添加元素
heapq.heappush(minheap, 10)
heapq.heappush(minheap, 8)
heapq.heappush(minheap, 9)
heapq.heappush(minheap, 2)
heapq.heappush(minheap, 1)
heapq.heappush(minheap, 11)
# [1,2,9,10,8,11]
print(minheap)
# 访问
# !
print(minheap[0])
# 删除
heapq.heappop(minheap)
# size
len(minheap)
# 遍历
while len(minheap) != 0:
print(heapq.heappop(minheap))
if __name__ == "__main__":
test = Test()
test.test()
?c++ 堆基本操作
#include<iostream> //c++标准头文件，可以使用cout，cin等标准编译用法
#include<vector> // 使用vector需要带上这个文件
#include<algorithm> //heap的头文件
#include<functional> //使用less<int>() 、 greater<int>()
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin、cout、map、set、vector
int main()
{
//创建
vector<int> nums{ 2,10,3,6,8,12,1 };
make_heap(nums.begin(), nums.end(),less<int>());//创建最大堆
//make_heap(nums.begin(), nums.end(), greater<int>()); //创建最小堆
//添加
nums.push_back(4);
push_heap(nums.begin(), nums.end(), less<int>());
//访问 直接访问vector即可
//3
cout << "nums[2]=" << nums[2] << endl;
//遍历
//12 10 3 6 8 2 1 4
for (int num : nums) {
cout << num << " ";
}
cout << endl;
//删除 与添加相反
pop_heap(nums.begin(), nums.end(), less<int>());
nums.pop_back();
// 10 8 3 6 4 2 1
for (int num : nums) {
cout << num << " ";
}
cout << endl;
//读取堆顶元素
cout << nums[0] << endl;
//size
//7
cout << nums.size() << endl;
return 0;
}力扣215? 找出数组的第k个最大元素
思路：使用最大堆，可以依次提取出最大的数
python 215
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) ->int:
#创建最大堆，取出来的就是最大值，Python默认创建最小堆，所以数值需要取反,转为最大堆
heap = []
heapq.heapify(heap)
#数据存入堆中
for num in nums:
heapq.heappush(heap,num*-1)
while k > 1:
heapq.heappop(heap)
k = k-1
return -heapq.heappop(heap)c++215
#include<algorithm> //heap的头文件
#include<functional> //使用less<int>() 、 greater<int>()
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//创建最大堆
make_heap(nums.begin(),nums.end(),less<int>());
//开始查找
while( k>1){
//取出堆顶元素
pop_heap(nums.begin(),nums.end(),less<int>());
nums.pop_back();
k--;
}
return nums[0];
}
};力扣692：前k个高频单词
最大堆方法：key：单词，value：出现次数，需要自定义对比函数（谁value大，谁大；同等value值，谁字母小谁先）
最小堆方法：key|value 加到最小堆，自定义对比函数，谁value小，谁在栈顶，谁字母大，谁先
Python692
import heapq
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
#使用最小堆来进行排序
#创建哈希表
maping = {}
for word in words:
if word not in maping:
maping[word] = 0
maping[word] = maping[word] +1
heap = []
for key,value in maping.items():
#最小堆
heapq.heappush(heap,Node(key,value))
if len(heap) > k :
heapq.heappop(heap)
res = []
while len(heap) > 0:
temp = heapq.heappop(heap)
res.append(temp.key)
res.reverse()
return res
#自定义类用于存储key，value值，重写比较函数
class Node:
def __init__(self,key,value):
self.key = key
self.value = value
def __lt__(self,nxt):
# 下面这句没懂
return self.key > nxt.key if self.value == nxt.value else self.value < nxt.valuec++692
C++ 自定义堆比较（使用了队列的方式）补充知识
priority_queue<Type, Container, Functional>：
Type?就是数据类型，Container?就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional?就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）class my_cmp{
public:
bool operator()(const pair<string,int> &p1,const pair<string,int> &p2){
return (p1.second == p2.second) ? (p1.first < p2.first) : (p1.second > p2.second);
}
};
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
//创建哈希表
map<string,int> wordsmap;
for(string word:words){
if(wordsmap.find(word) == wordsmap.end()){
wordsmap.insert(map<string,int>::value_type(word,0));
}
//更新map
wordsmap[word] = wordsmap[word] +1;
}
//创建最小堆
priority_queue<pair<string,int>, vector<pair<string,int>>, my_cmp> minheap;
//auto也是迭代器的一种使用方法
for(auto it = wordsmap.begin() ; it != wordsmap.end(); it++){
//将map元素存入进优先级队列
minheap.emplace(*it);
if(minheap.size() > k){
minheap.pop();
}
}
//前k个已经排序在堆中，最小堆存储是从小到大，所以取出需要逆序,且只需取出key值
vector<string> res;
while(!minheap.empty()){
res.push_back(minheap.top().first);
minheap.pop();
}
reverse(res.begin(),res.end());
return res;
}
};图：朋友关系
术语：
- 顶点
- 邻居结点
- 边：一条线是一条边
- 度：每条边是一个度
- 图:无向图、有向图、权重图
- 有向图：
- ? 入度：多少边指向该结点
- ? 出度：该点指向别的顶点的边
- 矢量图
- 用于：求最短路径（贝尔曼-福特算法、狄克斯特拉算法）
- 有向图：
数据结构总结
访问、搜索、插入、删除的时间特性
- 数组：
- 优点：适用于读操作，读的时候时间复杂度是O(1)
- 缺点：更新慢，插入和删除的时间复杂度是O(N)
- 链表：写多读少的场景
- 插入删除很快O(1)，访问O(N)
- 队列：水管，先入先出
- 栈：水杯，先入后出
- 堆：
- 最大堆
- 最小堆
- 哈希表：key，value
- 哈希碰撞
- 独一无二特性
- 集合