代码随想录(leetcode) | Blog of Huiteng

type

status

date

slug

summary

📝 力扣

😀

此篇为leetcode算法的基础方法论：限时+先写最简单的+调试包括 1. 一次遍历(学习中)尽可能的理解和记住知识 2. 手撕才是key point 3. 代码随想录 https://www.bilibili.com/video/BV1cy4y167mM/ 4. 展开阅读展开阅读展开阅读

双向指针

😇

啥时候用: 数组

解法: while(left<right) 什么条件++ — 有些可能需要先排序

两数之和

核心: 递增，只对应唯一的答案，不可以重复使用

三数之和

先排序，然后写出两数之和

记得循环要包多少，push完后还要++

while (nums[left] == nums[left - 1] && right > left)

特例： nums[i]>0 只有相等++之后判断与原值是否一样，以及开头

二分搜索法

核心: 更新左右端点

注意: 坚持对区间的定义才能搞请while(left≤right) right=mid-1

有序数组的平方

核心: 有负数存在，所以最小数一定在中间

注意: 双指针

四数之和

while(nums[left-1]==nums[left] &&)

left++; 在搞定后

if(j>=2 && nums[j-1]==nums[j]&& j != i + 1)

越界了 [1000000000,1000000000,1000000000,1000000000]

自己强转会比系统强转快

其他

344.反转字符串：双向指针交换位置

KMP算法

字符串匹配的问题找一模一样的子串

最接近的三数之和

统计和小于目标的下标对数目：

cnt += right - left;

有效三角形的个数

有三个非负整数，如果小的两个的和大于第三个，那它一定能组成三角形

存最多的雨水

去掉长边，面积一定变小，尽量在一次循环中处理掉更多的数据

接雨水:

两个O(n)的做法，两数组: 黑箱子也看成雨水，高度差间有透明玻璃
不创建数组的做法：双指针，利用透明玻璃一定越来越高的原理

同向指针其他

😇

啥时候用: 数组

解法: slow fast

子数组子串

乘积小于k的子数组（713）：

无重复字符的最长子串：滑动窗口最后都是要检测的 hashset 还不如vector{128,0}

长度最小的子数组

正数性质，滑动窗口到底的for循环

乘积小于 K 的子数组

无重复字符的最长子串

最大连续1的个数 III

替换子串得到平衡字符串

将 x 减到 0 的最小操作数

快慢指针

😇

啥时候用: 数组、链表

解法: slow fast

移除元素

核心: 双指针解决，快指针赋值给慢支针跳过元素

注意: erase的时间复杂度是O(n),

中间节点：

核心: 快指针走两步伐，慢走一步

环形节点：

快指针走两步，满指针走一步，那么环内，相对速度为+1，则一定会相遇

while(fast!= nullptr && fast->next!=nullptr)

if(slow == fast)

环形链表2

找入口就是相遇的那点看是 return nullptr;

需要注意顺序问题 if(head==slow) 与 head=head->next;

重排链表(太秀了: 寻找链表中点 + 链表逆序 + 合并链表)

我们先用快慢指针找到链表的中点，然后将链表的后半部分反转，最后将左右两个链表合并

寻找链表中点 + 链表逆序 + 合并链表)

回文链表

快慢指针找

比较，然后恢复

K 个一组翻转链表

两两交换链表中的节点

两数相加 II

反转链表II

反转中间任意一段
第一个节点前面加一个哨兵节点
left right 是

哈希表

😇

啥时候用: 判断一个元素是否出现过

数组unordered_map<char, int> dic;

解法: set map

set与muti-set 底层红黑树：取值慢

有效的字母异位词

哈希表：一次性为两个数组，用数组是因为下标可控

3层循环，有的话就++，无的话就--，最后看是否有非0

两个数组的交集

学习set的用法

两数之和

存遍历过的元素

四数相加

下标不可控，要统计出现的次数

分组 2(a+b) 2 (0 - c - d)在不在map中

找到了其实应该加上 value 的值(因为没有去重)

栈与队列

😇

啥时候用: std::stack的pop()函数并不返回任何值，它只是从栈中移除栈顶元素

栈实现队列：两个栈

队列实现栈：一个队列 123 弹出3 则重新把12加到3后面

删除字符串中的所有相邻重复项

string有stack的特性

字符串拼接用加法

逆波兰表达式求值

遇到符号取两个元素，遇到数字放进去

数的后序遍历

stack<int>会比stack<string>好

std::stoi 与 std::to_string atoi

滑动窗口最大值

优先队列通过大小顶堆实现：顺序变了，无法pop

单调队列：维护出口值一定是最大的，push进来的元素比前面大。则弹出所有前面的元素。本质上是

前 K 个高频元素

数字: 出现的频次，把频次排序，所以用map非常的合适 [数字: 频次]

前k个就好：大小顶堆，将快排的nlogn 变为nlogk： n为map中个数，大小顶堆每加入一个元素，调整时间复杂度是logk

而且要用小顶堆，使得树一直是k个节点，每加入一个，淘汰最小的。

递归

验证二叉搜索树

区间的思想

LONG_MIN, LONG_MAX

或者用，

二叉搜索树——递增序列——做节点的值<节点的树<有节点的值——一定比上个节点值大，判断所有相邻的元素
照递归左子树访问节点值，节点值，再递归右子树这样的顺序去遍历一定是递增序列
//函数的定义: 节点值是不是比上个节点值大
其实就是中序遍历：递归处理递归

遍历非递归遍历非递归遍历-中序层序遍历（广搜优先搜索）翻转二叉树对称二叉树二叉树的最大深度二叉树的最小深度完全二叉树节点的数量平衡二叉树二叉树的所有路径左叶子之和二叉树：14.找左下角的值二叉树：15. 路径总和二叉树：16.从中序与后序遍历序列构造二叉树二叉树：17.最大二叉树二叉树：18.合并二叉树二叉树：19.二叉搜索树中的搜索二叉树：20.验证二叉搜索树 21:56 二叉树：21.二叉搜索树的最小绝对差 11:53 二叉树：22.二叉搜索树中的众数 21:56 二叉树：23. 二叉树的最近公共祖先 19:03 二叉树：24. 二叉搜索树的最近公共祖先 15:34 二叉树：25.二叉搜索树中的插入操作 10:57 二叉树：26.删除二叉搜索树中的节点 26:23 二叉树：27. 修剪二叉搜索树 19:25 二叉树：28.将有序数组转换为二叉搜索树 14:57 二叉树：29.把二叉搜索树转换为累加树