GIS与Climate

V1

2022/09/25阅读:19主题:默认主题

算法60天:Day 5-数组和链表小总结

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day5,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的,具体可以看参考链接【1】。

今日知识点

今天是回顾前面四天的知识,因为是第一遍刷题,更多的是理解和动手。

链表理论基础:

  • 链表是一种串联、线性结构
  • 每个节点有两部分组成,值域和指针域,指针域存放指向下一个节点的指针;
  • 最后一个节点的指针域指向null(注意不同语言的写法,比如python是None);

数组理论基础:

  • 存放相同类型数据;
  • 在内存上是连续的(二维数组视语言而定);
  • 数组元素不能删除,只能覆盖;

在解题的时候要注意链表和数组的特征,比如数组元素不能删除、链表是线性结果等。

题目回顾

可以看着题目想解法:

  1. 数组:
  • 二分查找:不断对分
  • 移除元素:把不要的放后面
  • 有序数组的平方:最大的元素平方在两端
  • 长度最小的子数组:要注意两层循环
  • 螺旋矩阵:注意offset和loop的边界
  1. 链表
  • 移除元素:移除就是使得指针跳过
  • 设计链表:
  • 翻转链表:注意保存马山要锻炼掉的“链”
  • 两两交换链表中的节点:“两两”交换
  • 删除链表中的倒数第N个节点:双指针的巧用
  • 链表相交:两个链条如果有交点必定能生成环(想象);
  • 环形链表:数学公式的推导

需要牢记/注意的几点

  1. 双指针的用法
  2. 数组相关题目中循环的边界条件
  3. 删除链表节点其实就是修改了上一个链表的指针域(python自动回收内存);
  4. 虚拟头结点的用法

参考

【1】代码随想录:https://programmercarl.com/

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注