算法基础课听的不是很牢固,故听算法提高的时候边整合算法基础的内容,之后边学习边复习完善,同时补全语法基础的细节,并把相关的题目(leetcode和acwing)整理成题单,方便复习和强化思路,之后整理出一系列的总结

数据结构

每个数据结构先说明其对应的stl并且如何实现

先说线性表

线性表分成链表,顺序表 栈和队列等等

基础数据结构一:链表

链表无与伦比的优势是其可以以O(1)的复杂度实现普通数组O(n)才能实现的操作,比如插入元素和删除元素,链表可分为单链表和双链表

结构体单链表

语法课中讲的单链表主要是单链表的使用,也是leetcode中的常见题型
多以结构体(相当于类)的方式表示,核心就是struct的运用,一个节点存值的同时,用地址表示下一个节点

• 模板代码的理解:指针表示下一个节点的位置,整个结构体只需要将值传入进去
  定义一个节点 auto p = new(1) new很慢笔试不用,面试用;
  模板代码:

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x),next(Null){} //表示指向空的地方
};
for(auto i = head;;i = i->next) 遍历链表

• 常见操作:
  插入:1.头插(用的最多) 2.尾插 3.中间插 acwing 36.合并两个排序的链表
  删除:链表删除并非删除该节点,而是跳过该节点acwing 28.在O(1)时间删除链表结点,注意最后释放一下内存

• 常见做题的技巧与注意:
  1:虚拟头节点:自己引入一个头节点 p->next = head
  2.做题前,先将一个链表画出
  3.链表最末尾是0;

• 相关题目:
  Leetcode 707 设计链表 (强烈推荐自己动手写过一遍就彻底理解了)
  acwing 35 反转链表
  acwing 66.两个链表的第一个公共节点
  leetcode 203.移除链表元素

数组模拟单链表

由于new过慢,所以数组模拟单链表登场(数组可以实现任何数据结构,yyds)
acwing 826.单链表
模板

void init()//初始化可不能忘
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)//最重要的代码,贯穿整个算法的核心代码之一,即头插法的实现
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

双链表

在单链表的基础上,两个节点的next互相指向对方(作用极大,可用于储存图和树)

• acwing 827.双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

基础数据结构二:栈

栈的最重要的性质当然是LIFO(先进后出),操作总在同一端,栈在计算机组成中占有很重要的应用,其很多就是栈的思想,包括局部变量以及函数的实现,同时递归的深层原理就是栈

• 对应的stl中的stack

• 常用操作:
  size()
  empty()
  push() 向栈顶插入一个元素
  top() 返回栈顶元素
  pop() 弹出栈顶元素

• acwing 830.单调栈

同样的数组模拟栈

因为只用在头部操作,故只用一个指针

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

单调栈

• acwing 830.单调栈

  比较好理解的方式,就是相当于函数的单调递增

while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素，则出栈
        if (!tt) printf("-1 ");//如果栈空，则没有比该元素小的值。
        else printf("%d ", stk[tt]);//栈顶元素就是左侧第一个比它小的元素。
        stk[ ++ tt] = x;

暂且到这,之后慢慢补充