代码随想录刷题笔记

一、数组

1. 数组的定义

数组是存放在连续内存空间上的相同类型数据的集合。

2. 二分查找

• 防止溢出技巧：使用 mid = l + (r - l) / 2 而不是 mid = (l + r) / 2，避免 l + r 过大导致整数溢出
  • return a / gcd(a, b) * b; 在此处先 进行 a / gcd(a, b) 的计算也是为了防止溢出
• 注意事项：二分类问题要着重注意溢出和边界问题，可以考虑采用 long long 类型处理大数值

3. 双指针法

• 应用场景：双指针法（快慢指针法）在数组和链表的操作中非常常见，适用于很多考察数组、链表、字符串等操作的面试题
• 灵活性：根据题意设置指针的位置，除了快慢指针，还有相向指针（例如有序数组平方问题）

4. 滑动窗口

• 本质：属于双指针的一种特殊应用
• 关键点：要明确窗口的定义和 j 的含义（通常为窗口的终止位置）

5. 前缀和

• 适用场景：前缀和对于解决区间和问题非常合适
• 注意事项：使用前缀和时要注意区间左右边界的开闭情况

二、链表

1. 链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成：

• 数据域：存储节点的值
• 指针域：存放指向下一个节点的指针
• 特点：最后一个节点的指针域指向 null（空指针）

五、 哈希表

1. 哈希表理论基础

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

四、字符串

1. 数组填充类问题的通用解法

• 解决步骤：先预先给数组扩容到填充后的大小，然后从后向前进行操作
• 优点：
  1. 不需要申请新的数组
  2. 从后向前填充元素，避免了从前向后填充时每次添加元素都要将后续所有元素向后移动的问题
• 例题：替换数字 https://kamacoder.com/problempage.php?pid = 1064

2. 反转字符串

• 解决步骤： 双指针法 swap

3. 翻转字符串里的单词

• 解决步骤： 先全局翻转 去除多余空格后再局部翻转
• 例题：
  1. leetcode 151.反转字符串中的单词
  2. 右旋转字符串 （此题不需要去除空格，借鉴这种划分思想即可，把划分的两部分看成两个单词，则解法一致）

4. KMP 算法

• 算法用途: 解决字符串匹配问题（文本串里是否出现模式串）
• 解决步骤：
  1. 递归求解 next 数组
     next 数组的本质 是寻找子串中“相同前后缀的长度”，并且一定是最长的前后缀，不能是字符串本身
     假设当前前后缀相同
     如下一个相同，则加一
     如不同， 则 退回
• 例题：leetcode 28.找出字符串中第一个匹配项的下标