数据结构和算法--仅仅用于理解里面的术语，入门级别
数据结构和算法
预先知识：java
黑马前29节
cmd命令：
文件夹路径不区分大小写
E:
dir:查看所有文件
cd 目录 :进入
cd… 返回上一级
cd 目录1\目录2
cd\ 回到根目录
cls 清屏
exit 退出
打开文件夹必须用cd 查找，但是文件不用，直接输入即可
上下键使用上次使用的命令
环境变量：
操作系统中一个用来存储有关操作系统或应用程序配置信息的动态值。这些变量的值在操作系统级别可被访问，它们对于程序的运行和系统行为具有重要的影响。
简单来说：在任意目录下都可以打开指定 的软件，或者可执行程序，音频等，就可以把软件的路径配置到环境变量中
例如：把本台电脑的微信放到环境变量中，方便打开，内存损耗小
上面是用户变量，电脑有多个用户时修改本用户的，用下面的系统变量是默认设置，对所有用户生效
系统在查找时从上往下查找，放到最前面节省内存和时间
idea的安装
结构：project>module>package>class
新建顺序也是这样一步一步来
创建文件时必须一步一步创建，否则会出现问题
变量命名规则：
变量，方法：第二个单词往后首字母大写
文件（类名）：单词首字母都大写
1.复杂度
大O表示法：忽略常数，系数，低阶
注意：log函数统一为logn
1<logn<n<nlogn<n2<n3<2N<n!<nN
例题：求第n个斐波那契数列（fibonacci number）
0 1 1 2 3 5 后面一个数是前面两个数的和
解析：n=2,加一次；n=3,加两次；n=4，加三次…
所以要循环n-1次，即n–>1(先进行比较，在进行减一，后置就是最后进行加减操作)
package com.itheima.demo1;
public class FibNum {
public static void main(String[] args) {
System.out.println(fib2(30));
System.out.println(fib1(30));
}
public static int fib1(int n){
if(n<=1){
return n;
}
return fib1(n-1)+fib1(n-2);
}
public static int fib2(int n){
if(n<2) return n;
int first = 0;
int second = 1;
while(--n>0){
second+=first;
first = second-first;
}
return second;
}
}
复杂度分析：时间复杂度+空间复杂度，一般只考虑时间复杂度，除非小型机的编程，例如单片机等，内存不大
例：
时间：O（1）空间：O（1）
时间：O（n方），空间：O（1）
时间：O（logn），空间：O（1）
i+=i替代等换是一样的复杂度，意思就是i乘以几次2之后<n，log2(n)
注意：循环里执行几次是由后两个共同决定的，一定要看清楚
O（nlogn）
空间复杂度：O（n）堆区创建数组n个位置内存；时间复杂度：O（n）
现在来分析fib复杂度：首先是不使用回调
public static int fib1(int n){
if(n<=1){
return n;
}
return fib1(n-1)+fib1(n-2);
}
调用几次复杂度就是几直到调用到0或1，假设传入6
n = 6时：1+2+4+8+10 = 25，可以发现增长规律就行：是以前一行的指数型增长2N,发现增长的规律就行
O(2N)时间复杂度是最高的
public static int fib2(int n){
if(n<2) return n;
int first = 0;
int second = 1;
while(n-->1){
second+=first;;
first = second-first;
}
return second;
}
一共循环n-1次，所以是O(n)
1.线性结构：
1.动态数组
static:保证数据只有一份
相当于C++中vector，以下是代码：
案例描述: 实现一个通用的数组类，要求如下：
- 可以对内置数据类型以及自定义数据类型的数据进行存储
- 将数组中的数据存储到堆区
- 构造函数中可以传入数组的容量
- 提供对应的拷贝构造函数以及operator=防止浅拷贝问题
- 提供尾插法和尾删法对数组中的数据进行增加和删除
- 可以通过下标的方式访问数组中的元素
- 可以获取数组中当前元素个数和数组的容量
示例：
myArray.hpp中代码
#pragma once
#include <iostream>
using namespace std;
template<class T>
class MyArray
{
public:
//构造函数
MyArray(int capacity)
{
this->m_Capacity = capacity;
this->m_Size = 0;
pAddress = new T[this->m_Capacity];
}
//拷贝构造
//如果T为对象，而且还包含指针，必须需要重载 = 操作符，因为这个等号不是构造，而是赋值，
// 普通类型可以直接= 但是指针类型需要深拷贝
//指针类型必须进行深拷贝，否则会引起内存重复释放的问题
MyArray(const MyArray & arr)
{
this->m_Capacity = arr.m_Capacity;
this->m_Size = arr.m_Size;
this->pAddress = new T[this->m_Capacity];
for (int i = 0; i < this->m_Size; i++)
{
this->pAddress[i] = arr.pAddress[i];
}
}
//重载= 操作符 防止浅拷贝问题
//返回引用也就是返回实例，有助于链式编程思想
MyArray& operator=(const MyArray& myarray) {
//原来类中的堆区有无数据，不是外部是内部有没有在堆区的
if (this->pAddress != NULL) {
delete[] this->pAddress;
this->m_Capacity = 0;
this->m_Size = 0;
}
this->m_Capacity = myarray.m_Capacity;
this->m_Size = myarray.m_Size;
this->pAddress = new T[this->m_Capacity];
for (int i = 0; i < this->m_Size; i++) {
this->pAddress[i] = myarray[i];
}
return *this;
}
//注意重载运算符时的重复计算
//重载[] 操作符 arr[0]
//这个时候出现【9】就会调用这个函数
//返回引用值，就是实例对象，这样既能当作左值运算,又符合链式编程思想
T& operator [](int index)
{
return this->pAddress[index]; //不考虑越界，用户自己去处理
}
//尾插法，里面加法和插入是由顺序的，怎样简单怎么来，不一定非得要传入参数
void Push_back(const T & val)
{
if (this->m_Capacity == this->m_Size)
{
return;
}
this->pAddress[this->m_Size] = val;
this->m_Size++;
}
//尾删法
void Pop_back()
{
if (this->m_Size == 0)
{
return;
}
this->m_Size--;
}
//获取数组容量
int getCapacity()
{
return this->m_Capacity;
}
//获取数组大小
int getSize()
{
return this->m_Size;
}
//析构
~MyArray()
{
//只有堆区有数据时才需要释放，其他情况不用
//删除之后指向空，避免出现野指针的形象，析构时最好也进行初始化
if (this->pAddress != NULL)
{
delete[] this->pAddress;
this->pAddress = NULL;
this->m_Capacity = 0;
this->m_Size = 0;
}
}
private:
T * pAddress; //指向一个堆空间，这个空间存储真正的数据
int m_Capacity; //容量
int m_Size; // 大小
};
//在涉及堆区释放内存问题时，拷贝构造不需要进行堆区指针的判断，默认时构造新的数据
类模板案例—数组类封装.cpp中
#include "myArray.hpp"
#include <string>
void printIntArray(MyArray<int>& arr) {
for (int i = 0; i < arr.getSize(); i++) {
cout << arr[i] << " ";
}
cout << endl;
}
//测试内置数据类型
void test01()
{
MyArray<int> array1(10);
for (int i = 0; i < 10; i++)
{
array1.Push_back(i);
}
cout << "array1打印输出：" << endl;
printIntArray(array1);
cout << "array1的大小：" << array1.getSize() << endl;
cout << "array1的容量：" << array1.getCapacity() << endl;
cout << "--------------------------" << endl;
MyArray<int> array2(array1);
array2.Pop_back();
cout << "array2打印输出：" << endl;
printIntArray(array2);
cout << "array2的大小：" << array2.getSize() << endl;
cout << "array2的容量：" << array2.getCapacity() << endl;
}
//测试自定义数据类型
class Person {
public:
//这里需要默认构造函数，因为类的构造函数是往后走的
Person() {}
Person(string name, int age) {
this->m_Name = name;
this->m_Age = age;
}
public:
string m_Name;
int m_Age;
};
void printPersonArray(MyArray<Person>& personArr)
{
for (int i = 0; i < personArr.getSize(); i++) {
cout << "姓名：" << personArr[i].m_Name << " 年龄： " << personArr[i].m_Age << endl;
}
}
void test02()
{
//创建数组
MyArray<Person> pArray(10);
Person p1("孙悟空", 30);
Person p2("韩信", 20);
Person p3("妲己", 18);
Person p4("王昭君", 15);
Person p5("赵云", 24);
//插入数据
pArray.Push_back(p1);
pArray.Push_back(p2);
pArray.Push_back(p3);
pArray.Push_back(p4);
pArray.Push_back(p5);
printPersonArray(pArray);
cout << "pArray的大小：" << pArray.getSize() << endl;
cout << "pArray的容量：" << pArray.getCapacity() << endl;
}
int main() {
//test01();
test02();
system("pause");
return 0;
}
https://blog.csdn.net/weixin_43734095/article/details/104847976
看博客就好
牛逼
https://www.hello-algo.com/chapter_hashing/hash_map/
这个真的时神书
https://www.bilibili.com/read/cv29646692/?spm_id_from=333.999.0.0&jump_opus=1
https://www.hello-algo.com/chapter_preface/suggestions/
hello算法(python）：
第一次：
def while_loop(n:int)->int:
res = 0
i = 1
while i<=n:
res+=i
i+=1
return res
def for_loop(n:int)->int:
res = 0
for i in range(1,n+1):
res+=i
return res
def nested_for_loop(n:int)->str:
res = ""
for i in range(1,n+1):
for j in range(1,n+1):
res += f"({i},{j}),"
return res
def recur(n:int)->int:
"""递归"""
#终止条件
if n == 1:
return 1
#递：递归调用
res = recur(n-1)
#归：返回结果
return n+res
def tail_recur(n,res):
"""尾递归"""
#终止条件
if n == 0:
return res
#尾递归调用
return tail_recur(n-1,res+n)
def main():
result = for_loop(100)
print("sum is to ",result)
def fib(n:int)->int:
"""斐波那契数列"""
#终止条件f(1) = 0,f(2) = 1
if n==1 or n==2:
return n-1
#递归调用f(n) = f(n-1)+f(n-2)
res = fib(n-1)+fib(n-2)
#返回结果 f(n)
return res
def for_loop_recur(n:int)->int:
stack = []
res = 0
for i in range(n,0,-1):
stack.append(i)
while stack:
res += stack.pop()
return res
if __name__ =="__main__":
main()
result = while_loop(100)
print("sum1 is to ",result)
result1 = nested_for_loop(10)
print("sum2 is to ",result1)
result3 = tail_recur(100,0)
print("sum3 is to ",result3)
result4 = fib(64)
print("sum4 is to ",result4)
格式化字符串 ： f""
print (‘%d 等于 %d * %d’ % (num,i,j))占位符和格式转换
python学习教程：
https://www.runoob.com/python/python-strings.html
注意python的变量赋值语法，一些常用特点
if __name__ == "__main__":语句的作用是判断当前模块是否作为主程序直接执行。如果模块是直接被执行的，则__name__变量的值为"__main__"，在这种情况下，if __name__ == "__main__":后面的代码块将会被执行；如果模块是被导入的，则__name__变量的值为模块的名称，这时if __name__ == "__main__":后面的代码块将不会被执行。
需要执行的脚本不需要模块名为main,在这种上下文中，"main"通常指的是Python脚本文件作为主程序直接执行时的执行上下文。当Python脚本文件被直接执行时，Python解释器会将这个脚本文件作为主程序运行，此时该脚本文件的特殊变量__name__的值会被设为"__main__"。因此，if __name__ == "__main__":语句的作用就是检查当前模块是否在主程序上下文中运行。
在这个语境中，"main"并不是一个变量或模块名，而是一个特殊的字符串，用于表示当前模块是主程序。"main"一词来自C语言中的main函数，表示程序的入口点。
第二次
def slgorithm(n:int):
a = 2
a = a+1
a = a*2
#_占位符，只需要运行循环，不需要变量
for _ in range(n):
print(0)
def array_traversal(nums:list[int])->int:#nums后面跟类型
count = 0
for num in nums:
count+=1
return count
def bubble_sort(nums:list[int]):
for i in range(0,len(nums)-1):#排序轮数
for j in range(0,len(nums)-1-i):#每轮比较的次数
if(nums[j]<nums[j+1]):
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
print(nums)
return 0
if __name__ =="__main__":
slgorithm(5)
bubble_sort([1,5,3,4,8,2])
class ListNode:
"""链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 后继节点引用
在这段代码中，ListNode 是一个链表节点类，用于表示链表中的一个节点。它具有两个属性：
val：表示节点的值，类型为整数（int）。next：表示指向下一个节点的引用。由于链表中的节点是一个个相互连接的，因此每个节点都需要有一个指向下一个节点的引用。next属性的类型声明为ListNode | None，这意味着它可以是一个指向ListNode类型对象的引用，也可以是None，表示没有后继节点（即链表的最后一个节点）。- 注意：冒号后面都是类型
这里使用了类型注释（type hinting）来指定属性的类型，以增加代码的可读性和可维护性。ListNode | None 使用了 Python 3.10 中的新特性，表示 next 属性可以是 ListNode 类型对象的引用，也可以是 None。
for i ,num in enumerate(nums):
这段代码使用了 Python 中的 enumerate() 函数，用于在循环中同时获取元素的索引和值。
具体来说，enumerate(nums) 将返回一个由 (index, value) 组成的元组序列，其中 index 是元素的索引，value 是元素的值。在 for 循环中，i 和 num 分别表示索引和值，通过 enumerate(nums) 得到的元组中的两个元素。
例如，假设 nums 是一个列表 [10, 20, 30]，那么 for i, num in enumerate(nums): 循环将会迭代三次，每次迭代时 i 和 num 的值分别是 (0, 10)、(1, 20) 和 (2, 30)，分别表示列表中每个元素的索引和值。
数组
#初始化数组
import random
arr:list[int] = [0]*5
nums:list[int] = [1,3,2,5,4]
def random_access(nums:list[int])->int:
'随机访问元素'
#区间[0，len(nums)-1]
# 注意python里面区间是左闭右开,除随机函数外
random_index = random.randint(0,len(nums)-1)
random_num = nums[random_index]
return random_num
def insert(nums:list[int],num:int,index:int):
'在数组的索引index插入元素num'
for i in range(len(nums)-1,index,-1):
nums[i] = nums[i-1]
nums[index] = num
def remove(nums:list[int],index:int):
'删除index的元素'
for i in range(index,len(nums)):
nums[i] = nums[i+1]
def traverse(nums:list[int]):
'遍历数组'
count = 0
for i in range(len(nums)):
count += nums[i]
for num in nums:
count +=num
for i ,num in enumerate(nums):
count +=nums[i]
count +=num
def find(nums:list[int],target:int)->int:
'在数组中查找'
for i in range(len(nums)):
if nums[i] ==target:
return i
return -1
def extend(nums:list[int],enlarge:int)->list[int]:
'扩展数组长度'
res = [0]*(len(nums)+enlarge)
for i in range(len(nums)):
res[i] = nums[i]
return res
链表
class Employee:
'所有员工的基类'
empCount = 0
def __init__(self, name, salary):
self.name = name
self.salary = salary
Employee.empCount += 1
在这段代码中，Employee.empCount += 1 是对类变量 empCount 的增加操作，它位于类的作用域内。而 empCount += 1 则是尝试对一个在方法中未定义的变量进行操作，因此会引发一个 NameError。
**在 Python 中，如果你想要对类变量进行操作，需要使用类名来引用它，以区分类变量和实例变量。类变量是属于整个类的，可以通过类名直接访问和修改。**在这个例子中，Employee.empCount += 1 表示对 Employee 类的 empCount 类变量进行增加操作。
如果你尝试使用 empCount += 1，Python 将会认为 empCount 是一个局部变量，并且它还没有被定义，因此会抛出一个 NameError 异常。
User
class ListNode:
"""链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向下一节点的引用，self.next没有定义怎么可以使用
这行代码使用了类型注释（type hinting）语法，用于指定 self.next 这个实例变量的类型。
具体来说，self.next: ListNode | None = None 的含义如下：
self.next：表示实例变量的名称为next。:：表示类型注释的分隔符，用于将变量名和类型注释分开。ListNode | None：表示该变量的类型可以是ListNode类的实例，也可以是None。ListNode类型表示指向下一个节点的引用，而None表示没有后继节点。=：表示赋值操作符，用于给变量一个初始值。None：表示变量的初始值为None，即表示当前节点没有后继节点。
因此，这行代码的作用是将 self.next 这个实例变量的类型注释为可以是 ListNode 类的实例，也可以是 None，并将其初始值设为 None。
class ListNode:
'链表节点类'
val = 0
next = ListNode|None
def __init__(self,val):
self.val = val
self.next = None
以上是错误的
在 Python 中，类型注释是用于提供类型信息的，但它们不应该在类的属性定义中使用。在你的代码中，next = ListNode|None 并不是一个有效的类型注释，它看起来更像是一个试图指定属性类型的语法错误。正确的做法是在变量声明时使用 :，而不是 |，注意python的类型定义**
#注意这个类里面只有一个函数方法
class ListNode:
'链表节点类'
def __init__(self,val):
self.val:int = val
self.next:ListNode|None = None
class ListNode1:
'双向链表节点类'
def __init__(self,val:int):
self.val:int = val
self.next:ListNode1|None = None
self.prev:ListNode1|None = None
def insert(n0:ListNode,P:ListNode):
'在链表之后插入节点'
n1 = n0.next
P.next = n1
n0.next = P
def remove(n0:ListNode):
'删除之后的一个节点'
if not n0.next:
return
P = n0.next
n1 = P.next
n0.next = n1
def accsee(head:ListNode,index:int)->ListNode|None:
'访问链表确定节点'
for _ in range(index):
#遍历超出范围，返回空
if not head:
return None
head = head.next
return head
def find(head:ListNode,target:int)->int:
'在链表中查找值为target的首个节点'
index = 0
while head:
if head.val == target:
return index
head = head.next
index += 1
return -1
#初始化链表1->3->2->5->4
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
#构建连接
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
列表（动态数组）
#初始化
nums1:list[int] = [6,7]
nums:list[int] = [1,3,2,5,4]
#访问
num:int = nums[1]
nums[1] = 0
#清空
#nums.clear()
nums.append(1)
nums.append(2)
nums.insert(3,6)
#删除索引3的元素
nums.pop(3)
count = 0
for i in range(len(nums)):
count += nums[i]
for num in nums:
count +=num
nums +=nums1
nums.sort() #默认从小到大排序
class MyList:
'列表类'
def __init__(self):
'构造方法'
self._capacity:int = 0
self._arr:list[int] = [0]*self._capacity#数组存储
self._size:int = 0
self._extend_ratio:int = 2 #扩容倍数
def size(self)->int:
'获取长度'
return self._size
def capacity(self)->int:
'获取列表容量'
return self._capacity
def get(self,index:int)->int:
'访问元素'
#索引越界，抛出异常
if index<0 or index >=self._size:
raise IndexError("索引越界")
return self._arr[index]
def set(self,num:int,index:int):
'更新元素'
if index < 0 or index >= self._size:
raise IndexError("索引越界")
self._arr[index] = num
def add(self,num:int):
'在尾部添加元素'
#元素数量超出容量时，触发扩容机制
if self.size() ==self.capacity():
self.extend_capacity()
self._arr[self._size] = num
self._size += 1
def insert(self,num:int,index:int):
'在中间插入元素'
if index < 0 or index >= self._size:
raise IndexError("索引越界")
if self.size() ==self.capacity():
self.extend_capacity()
for j in range(self._size-1,index,-1):
self._arr[j+1] = self._arr[j]
self._size +=1
def remove(self,index:int)->int:
'删除元素'
if index < 0 or index >= self._size:
raise IndexError("索引越界")
num = self._arr[index]
for j in range(index,self._size):
self._arr[j] = self._arr[j+1]
self._size -= 1
return num
def extend_capacity(self):
'列表扩容'
self._arr = self._arr+[0]*self._capacity * (self._extend_ratio-1)
self._capacity = len(self._arr)
def to_array(self)->list[int]:
'返回有效长度的列表'
return self._arr[:self._size]
#切片操作，默认为零，相当于return self._arr[0:self._size]
在 Python 中，每个对象都有一个唯一的标识符（ID），可以通过内置函数 id() 来获取。这个标识符是一个整数，用于唯一标识对象在内存中的位置。
在 Python 中，每个对象都有一个唯一的标识符（ID），可以通过内置函数 id() 来获取。这个标识符是一个整数，用于唯一标识对象在内存中的位置。
对于字符串中的每个字符，虽然它们是不可变的，但在某些情况下，Python 会对相同的字符进行缓存，以节省内存。这意味着对于相同的字符，它们的标识符可能是相同的。但是，对于不同的字符，它们的标识符是不同的。
例如：
pythonCopy codes1 = 'a'
s2 = 'a'
print(id(s1)) # 输出第一个字符 'a' 的标识符
print(id(s2)) # 输出第二个字符 'a' 的标识符，与第一个相同
在上面的示例中，由于 Python 对相同的字符进行了缓存，因此 s1 和 s2 共享相同的标识符。
栈
#初始化栈
#python没有内置的栈，可以把list当作栈来使用
stack:list[int] = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
#访问栈顶
peek:int = stack[-1]
#元素出栈
pop:int = stack.pop()
size:int = len(stack)
is_empty:bool = len(stack) == 0
基于链表实现
class ListNode:
'链表节点类'
def __init__(self,val:int):
self.val:int = val
self.next:ListNode|None = None
class LinkedListStack:
'基于链表实现栈'
def __init__(self):
'构造方法'
self._peek:ListNode|None = None#始终是指向栈顶
self._size:int = 0
def size(self)->int:
'获取栈的长度'
return self._size
def is_empty(self)->bool:
'判断是否为空'
return not self._peek
def push(self,val:int):
'入栈'
node = ListNode(val)
node.next = self._peek #这里要理解原先里面假设有元素，这句话在于将新建的元素与开始的元素连接起来
self._peek = node #上一句连接完成之后，头指针还指向栈顶
self._size += 1
def pop(self)->int:
'出栈'
num = self.peek()
self._peek = self._peek.next
self._size -= 1
return num
def peek(self)->int:
'访问栈顶'
if self.is_empty():
raise IndexError("栈为空")
return self._peek.val
def to_list(self)->list[int]:
'转化为列表用于打印'
arr = []
node = self._peek
while node:
arr.append(node.val)
node = node.next
arr.reverse()
return arr
if __name__ == "__main__":
#初始化栈
stack = LinkedListStack()
#元素入栈
stack.push(1)
stack.push(2)
stack.push(3)
print("栈 stack = ",stack.to_list())
peek = stack.peek()
print("栈顶元素：peek = ",peek)
基于数组实现
class ArrayStack:
'基于数组实现栈'
def __init__(self):
'构造方法'
self._stack:list[int] = []
def size(self)->int:
'获取长度'
return len(self._stack)
def is_empty(self)->bool:
'判断空'
return self._stack == []
def push(self,item:int):
'入栈'
self._stack.append(item)
def pop(self)->int:
'出栈'
if self.is_empty():
raise IndexError("栈为空")
return self._stack.pop()
def peek(self)->int:
'访问栈顶'
if self.is_empty():
raise IndexError("栈为空")
return self._stack[-1]
def to_list(self)->list[int]:
'返回列表'
return self._stack
if __name__ =="__main__":
stack = ArrayStack()
队列
from collections import deque
#在python中，我们将双向队列deque当作队列使用
if __name__ == "__main__":
#初始化
que : deque[int] = deque()
#元素入队
que.append(1)
que.append(3)
que.append(4)
#访问队首元素
front:int = que[0]
print(front)
#元素出队
pop:int = que.popleft()
size:int = len(que)
is_empty:bool = len(que)==0
print(pop,size,is_empty)
基于链表实现
class ListNode:
"""链表"""
def __init__(self,val:int):
self.val:int = val
self.next:ListNode|None = None
class LinkedListQueue:
"""基于链表实现的队列"""
def __init__(self):
"""构造方法"""
self._front:ListNode|None = None #头节点
self._rear:ListNode|None = None #尾节点
self._size:int = 0
def size(self)->int:
"""获取队列的长度"""
return self._size
def is_empty(self)->bool:
"""判断队列是否为空"""
return not self._front
def push(self,num:int):
"""入队"""
#难点在于不断实时更新头尾节点
#在尾节点之后添加
node = ListNode(num)
#如果队列为空，则令头尾节点都指向该节点
if self._front is None:
self._front = node
self._rear = node
#如果不为空，节点添加尾节点之后
else:
self._rear.next = node
self._rear = node
self._size += 1
def pop(self)->int:
"""出队"""
#入队出队都要进行头尾节点的更新
num = self.peek()
self._front = self._front.next
self._size -= 1
return num
def peek(self)->int:
"""访问队首元素"""
#访问时都要考虑是否为空
if self.is_empty():
raise IndexError("队列为空")
return self._front.val
def to_list(self)->list[int]:
"""转化为列表用于打印"""
queue = []
temp = self._front
while temp:
queue.append(temp.val)
temp = temp.next
return queue
if __name__ == "__main__":
#初始化
que = LinkedListQueue()
#元素入队
que.push(1)
que.push(3)
que.push(4)
#访问队首元素
front:int = que.peek()
print(front)
#元素出队
pop:int = que.pop()
size:int = que.size()
is_empty:bool = que.is_empty()
print(pop,size,is_empty)
基于数组实现（环形数组），注意出对入队都是O(1)
class ArrayQueue:
"""基于数组实现的队列"""
def __init__(self,size:int):
"""构造方法"""
self._nums:list[int] = [0]*size
self._front:int = 0
self._size:int = 0
def capacity(self)->int:
"""获取队列的容量"""
return len(self._nums)
def size(self)->int:
"""获取队列的长度"""
return self._size
def is_empty(self)->bool:
"""判断空"""
return self._size == 0
def push(self,num:int):
"""入队"""
if self._size == self.capacity():
raise IndexError("队列已满")
#计算队尾指针，指向队尾索引+1
#通过取余操作实现rear 越过数组尾部回到头部
rear:int = (self._front+self.size())%self.capacity()
self._nums[rear] = num
self._size += 1
def pop(self)->int:
"""出队"""
num:int = self.peek()
#队首指针向后移动一位，若越过尾部，则返回到数组头部
#这样就形成了一个循环队列,没必要进行扩容,下面这句话非常牛逼
self._front = (self._front+1)%self.capacity()
self._size -= 1
return num
def peek(self)->int:
"""访问队首元素"""
if self.is_empty():
raise IndexError("队列为空")
return self._nums[self._front]
def to_list(self)->list[int]:
"""返回列表用于打印"""
res = [0]*self._size
j:int = self._front
for i in range(self._size):
res[i] = self._nums[j%self.capacity()]
j += 1
return res
if __name__ == "__main__":
#初始化
que = ArrayQueue(10)
#元素入队
que.push(1)
que.push(3)
que.push(4)
#访问队首元素
front:int = que.peek()
print(front)
#元素出队
pop:int = que.pop()
size:int = que.size()
is_empty:bool = que.is_empty()
print(pop,size,is_empty)
双端队列
from collections import deque
#初始化
deque= deque()
#元素入队
deque.append(1) #默认队尾
deque.append(2)
deque.append(3)
#默认队首
deque.appendleft(5)
deque.appendleft(4)
print(deque)
#访问队首队尾
front:int = deque[0]
rear:int = deque[-1]
#元素出队
pop_front:int = deque.popleft()
pop_rear:int = deque.pop()
#获取长度
size:int = len(deque)
is_empty:bool = len(deque)==0
print(front)
print(rear)
print(pop_front)
print(pop_rear)
print(size)
print(is_empty)
基于双向链表实现
class ListNode:
"""双向链表节点"""
def __init__(self,val:int):
"""构造方法"""
self.val:int = val
self.next:ListNode|None = None
self.prev:ListNode|None = None
class LinkedListDeque:
"""基于双向链表实现的双向队列"""
def __init__(self):
"""构造方法"""
self._front:ListNode|None = None
self._rear:ListNode|None = None
self._size:int = 0
def size(self)->int:
""""长度"""
return self._size
def is_empty(self)->bool:
"""空"""
return self._size == 0
def push(self,num:int,is_front:bool):
"""入队"""
node = ListNode(num)
#考虑空，头节点和尾节点都指向node
if self.is_empty():
self._front = self._rear = node
#判断是队首还是队尾入队操作
elif is_front:
#队首
self._front.prev = node
node.next = self._front#用来链接结点
self._front = node#更新头节点
else:
self._rear.next = node
node.prev = self._rear
self._rear = node
self._size += 1
def push_first(self,num:int):
""""队首"""
self.push(num,True)
def push_last(self,num:int):
"""队尾"""
self.push(num,False)
def pop(self,is_front:bool)->int:
"""出队"""
if self.is_empty():
raise IndexError("双向队列为空")
#队首
#断开链接(包括两个向前和向后），更新头节点
if is_front:
val:int = self._front.val
fnext:ListNode|None = self._front.next
if fnext!=None:
fnext.prev = None
self._front.next =None
self._front = fnext
#队尾
else:
val:int = self._rear.val
rprev:ListNode|None = self._rear.prev
if rprev!=None:
rprev.next = None
self._rear.prev = None
self._size-=1
return val
def pop_first(self)->int:
"""队首"""
return self.pop(True)
def pop_last(self)->int:
"""队尾"""
return self.pop(False)
def peek_first(self)->int:
"""队首"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._front.val
def peek_last(self)->int:
"""队尾"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._rear.val
def to_array(self)->list[int]:
"""返回数组"""
node = self._front
res = [0]*self.size()
for i in range(self.size()):
res[i] = node.val
node = node.next
return res
基于数组实现（环形数组）
注意：计算环形数组队首和队尾的时候，都是该在的那个位置取余，同时要注意取余的情况
class ArrayDeque:
"""基于数组的双向队列"""
def __init__(self,capacity:int):
"""构造方法"""
self._nums:list[int] = [0]*capacity
self._front:int = 0
self._size:int = 0
def capacity(self)->int:
"""容量"""
return len(self._nums)
def size(self)->int:
"""长度"""
return self._size
def is_empty(self)->bool:
""""空"""
return self._size==0
def index(self,i:int)->int:
"""计算环形数组索引"""
#通过取余操作实现数组首尾相连
#当i越过尾部返回头部反之亦然
#这里面加不加self.capacity都一样，因为要求余数
return (i+self.capacity())%self.capacity()
def push_first(self,num:int):
"""队首"""
if self._size ==self.capacity():
print("双向队列已满")
return
#队首指针向左移动
#通过取余实现环形
self._front = self.index(self._front-1)
self._nums[self._front] = num
self._size += 1
def push_last(self,num:int):
"""队尾"""
if self._size ==self.capacity():
print("双向队列已满")
return
rear = self.index(self._front+self._size)
self._nums[rear] = num
self._size += 1
def pop_first(self)->int:
"""队首出队"""
num = self.peek_first()
self._front = self.index(self._front+1)
self._size -= 1
return num
def pop_last(self)->int:
"""队尾出队"""
num = self.peek_last()
self._size -= 1
return num
def peek_first(self)->int:
"""访问队首"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._nums[self._front]
def peek_last(self)->int:
"""访问队尾"""
if self.is_empty():
raise IndexError("双向队列为空")
#计算尾元素索引
last = self.index(self._front+self._size-1)
return self._nums[last]
def to_array(self)->list[int]:
"""返回数组"""
#在最后一个操作中不要试图进行修改元素
res = []
for i in range(self._size):
res.append(self._nums[self._front+i])
return res
哈希表
if __name__ == "__main__":
#初始化哈希表
hmap:dict = {}
#加键值对
hmap[123] = "你哈"
hmap[124] = "加"
hmap[125] = "键"
print(hmap)
#查询
name = hmap[125]
print(name)
#删除
hmap.pop(123)
print(hmap)
#哈希表的遍历
if __name__ =="__main__":
hmap: dict = {}
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"
for key,value in hmap.items():
print(key,"->",value)
for key in hmap.keys():
print(key)
for value in hmap.values():
print(value)
class Pair:
"""键值对"""
def __init__(self,key:int,val:str):
self.key = key
self.val = val
class ArrayHashMap:
"""基于数组实现的哈希表"""
def __init__(self):
"""构造方法"""
#初始化数组，包含100个桶
self.buckets:list[Pair|None] = [None]*100
def hash_func(self,key:int)->int:
"""哈希函数，返回索引"""
index = key%100
return index
def get(self,key:int)->str:
"""查询"""
index:int = self.hash_func(key)
pair:Pair = self.buckets[index]
if pair is None:
return None
return pair.val
def put(self,key:int,val:str):
"""添加操作"""
pair = Pair(key,val)
index :int = self.hash_func(key)
self.buckets[index] = pair
def remove(self,key:int):
"""删除"""
index:int = self.hash_func(key)
#置为None,代表删除
self.buckets[index] = None
def entry_set(self)->int:
"""获取所有键值对"""
result:list[pair] = []
for pair in self.buckets:
if pair is not None:
result.append(pair)
return result
def key_set(self)->list[str]:
"""获取所有键"""
result :list[int] = []
for pair in self.buckets:
if pair is not None:
result.append(pair.key)
return result
def value_set(self) -> list[str]:
"""获取所有值"""
result: list[str] = []
for pair in self.buckets:
if pair is not None:
result.append(pair.val)
return result\
def print(self):
"""打印哈希表"""
for pair in self.buckets:
if pair is not None:
print(pair.key,"->",pair.val)
，包含100个桶
self.buckets:list[Pair|None] = [None]*100
def hash_func(self,key:int)->int:
"""哈希函数，返回索引"""
index = key%100
return index
def get(self,key:int)->str:
"""查询"""
index:int = self.hash_func(key)
pair:Pair = self.buckets[index]
if pair is None:
return None
return pair.val
def put(self,key:int,val:str):
"""添加操作"""
pair = Pair(key,val)
index :int = self.hash_func(key)
self.buckets[index] = pair
def remove(self,key:int):
"""删除"""
index:int = self.hash_func(key)
#置为None,代表删除
self.buckets[index] = None
def entry_set(self)->int:
"""获取所有键值对"""
result:list[pair] = []
for pair in self.buckets:
if pair is not None:
result.append(pair)
return result
def key_set(self)->list[str]:
"""获取所有键"""
result :list[int] = []
for pair in self.buckets:
if pair is not None:
result.append(pair.key)
return result
def value_set(self) -> list[str]:
"""获取所有值"""
result: list[str] = []
for pair in self.buckets:
if pair is not None:
result.append(pair.val)
return result\
def print(self):
"""打印哈希表"""
for pair in self.buckets:
if pair is not None:
print(pair.key,"->",pair.val)