L2知识点整理

L2主要知识点我划分成了以下几类:

图论:考察图的存储结构理论知识搜索算法相关算法

  • 存储结构:邻接表,邻接矩阵,边集数组
  • 理论知识:邻接点,有向图和无向图的区别,割点概念
  • 相关算法:dijkstra(单源最短路),tarjan(求割点、桥、连通分量)
  • 搜索算法:DFS(深度优先搜索),BFS(广度优先搜索)

链表:主要考察对链表理论知识的理解以及:增加删除等对前驱和后继结点的操作

  • 数组模拟:采用静态链表的概念,用数组来模拟链表的操作

模拟:

  • 通过题目给出的条件和约束,用代码来模拟其场景,这个知识点需要考虑的细节很多,通常跟字符串的知识点相并而出,最好先在纸上模拟一遍题目给出的场景以及对数据的处理,然后一步一步考虑如何用代码解决,这个知识点没得套路.....也是我错的最多的..

二叉树:主要考察:二叉树的前、中、后遍历二叉树的结构特点数组存储二叉树

  • 二叉树遍历:必须掌握二叉树的前、中、后序递归遍历,以及层次遍历,这里用到了BFS的思想
  • 二叉树的结构特点(相对应的二叉树计算公式):叶子结点的总数二叉树的层次计算左右结点和根节点的关系左右子树和二叉树的递归定义
  • 数组存储二叉树:这个非常重要!结合二叉树的基本理论知识就可以掌握二叉树的数组存储结构!根据根结点的编号能确定左右子树的编号!

并查集:

  • 这个知识点也很重要,将所有所属一个集合内的元素归并成一个集合,在查找的时候只需要比对其对应的双亲是否一样即可确定是否在一个集合中,通常用于家谱,族谱,相对应关系等题型,这个知识点大多数题目可以用图论解决,这个只有一个查找元素的模板,看看视频做完模板题很快就能理解,代码量不大,主要是思维

排序:

这个算是一个比较小的知识点,通常配合着map、set等结构应用出现,用于对某键值进行排序,只需要掌握stl或者第三方库内快排的应用即可,或者手写快排,模板也不难

堆、栈、队列:这类题目出的较少,堆即是优先队列,是一棵二叉树,这个看下它的理论即很快就能懂

  • 栈是一种先进后出的存储结构
  • 队列是一种先进先出的存储结构

题目分类:重点标注的即是模板题

图论题

  • L2-001 紧急救援 (25 分)(dijkstra)
  • L2-010 排座位 (25 分)(邻接矩阵和并查集的应用)
  • L2-013 红色警报 (25 分)(tarjan求割点)
  • L2-023 图着色问题 (25 分)(邻接点判断)
  • L2-025 分而治之 (25 分)(边集数组)
  • L2-026 小字辈 (25 分)(邻接矩阵,搜索)
  • L2-028 秀恩爱分得快 (25 分)(邻接矩阵)
  • L2-031 深入虎穴 (25 分)(邻接矩阵,搜索)
  • L2-036 网红点打卡攻略 (25 分)(搜索)

链表(数组模拟)

  • L2-002 链表去重 (25 分)
  • L2-022 重排链表 (25 分)

模拟

  • L2-003 月饼 (25 分)(简单贪心)
  • L2-008 最长对称子串 (25 分)(简单动态规划,暴力)
  • L2-014 列车调度 (25 分)(思维,二分)
  • L2-018 多项式A除以B (25 分)
  • L2-029 特立独行的幸福 (25 分)
  • L2-034 口罩发放 (25 分)(字符串Hash,map应用)

二叉树

  • L2-004 这是二叉搜索树吗? (25 分)
  • L2-006 树的遍历 (25 分)
  • L2-011 玩转二叉树 (25 分)
  • L2-035 完全二叉树的层序遍历 (25 分)

Hash(数组模拟)

  • L2-005 集合相似度 (25 分)

并查集

  • L2-007 家庭房产 (25 分)
  • L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
  • L2-020 功夫传人 (25 分)
  • L2-024 部落 (25 分)
  • L2-030 冰岛人 (25 分)(字符串应用)

排序

  • L2-009 抢红包 (25 分)(数组模拟Hash,结构体排序)
  • L2-015 互评成绩 (25 分)(数组模拟Hash,结构体排序)
  • L2-017 人以群分 (25 分)(简单排序)
  • L2-019 悄悄关注 (25 分)(结构体排序)
  • L2-021 点赞狂魔 (25 分)(数组模拟Hash,结构体排序)
  • L2-027 名人堂与代金券 (25 分)(结构体排序,模拟)

堆、栈、队列

  • L2-012 关于堆的判断 (25 分)(堆操作,字符串)
  • L2-032 彩虹瓶 (25 分)(栈的应用)
  • L2-033 简单计算器 (25 分)(栈的应用)

学习视频:

图论:

理论基础知识:https://www.bilibili.com/video/BV12t411v7Dn?from=search&seid=2237891164234448454

数组模拟邻接表:https://www.bilibili.com/video/BV1yi4y1x7Ax/?spm_id_from=333.788.recommend_more_video.-1

深度优先搜索和广度优先搜索:https://www.bilibili.com/video/BV1254y1976m?from=search&seid=5076968849994726377

二叉树:

二叉树的遍历:https://www.bilibili.com/video/BV1K4411M72T?from=search&seid=8907844068876128238

二叉树的理论:https://www.bilibili.com/video/BV1TJ411k7kT/?spm_id_from=333.788.recommend_more_video.0

并查集:

https://www.bilibili.com/video/BV1vt411y7Bu?from=search&seid=15571700243577868684

堆:

https://www.bilibili.com/video/BV1uK4y177nQ?from=search&seid=7793628285062821067

上述所有数据结构都是采用数组的方式存储,这里放上来各位估摸着也看不下,先把模板题撸了,不懂得直接百度或者哔哩哔哩就好了!

本文链接:

https://nullcode.fun/137.html
1 + 9 =
1 评论
    yunxiao99Chrome 89Windows 10
    4月21日 回复

    thanks