随想录

## 题目：[102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/) ### 思路： 先把根放进去，然后每次都是左右就可以了。 记录一个深度，当`len(res) == deepth`的时候就说明 ......

很大程度上是熟悉了一遍stack queue dequeue priority_queue的语法 贴一下总结不错的参考 https://zhuanlan.zhihu.com/p/352404451 优先队列 此外，push 和 emplace这两个操作，除了一个是产生副本移动，一个是直接构造添加外， ......

今天的题目就是二叉树的前中后序遍历，目前只写了递归方法，之后再补迭代方法。 ## 题目：[144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/) ### 思路： 前序遍历：根-左-右 ### 代码1： ......

## # 977.有序数组的平方 题目链接： [有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/) 题目： 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序 ......

239. 滑动窗口最大值 （一刷至少需要理解思路） 卡哥建议：之前讲的都是栈的应用，这次该是队列的应用了。本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A ......

## 题目：[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/) ### 思路： ![239.滑动窗口最大值.gif](https://s2.loli.net/2023/08/07/9ohI1LGQlZmMVjn.g ......

20. 有效的括号 卡哥建议：讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。 大家先自己思考一下 有哪些不匹配的场景，在看视频 我讲的都有哪些场景，落实到代码其实就容易很多了。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89 ......

# 字符串 ## 反转字符串(力扣344.) - **如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。** 毕竟面试官一定不是考察你对库函数的熟悉程度， 如果使用python和java 的同学更需要注意这一点，因为python、java提供的库函数十分丰富。 - **如果库函数仅仅是 ......

关于字符串string一些库函数的使用，不太熟悉，导致开始做的时候比较磕磕绊绊 主要用到了<algorithm>中的reverse，以及string的resize，substr，erase等，在这贴一个 C++ 字符串（string）常用操作总结 - 知乎 (zhihu.com) C++的strin ......

## 题目：[20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/) ### 思路： 很简单的一个栈的题目： 1. 如果是左括号就存 2. 如果是右括号就和栈顶的匹配 1. 匹配失败就返回false 2. 匹配成功就删除栈顶元素 3. ......

84.柱状图中最大的矩形 要求： 有多个矩形，要求返回可能勾勒出的最大矩形 思路： 寻找右边第一个小于当前节点的index 寻找左边第一个小于当前节点的index 右边：累加的方式，如果当前节点小于，那么判读后放进去 左边，放进去了之后，当前节点后一个，就是左边最小的 代码： 1 // 要求：和相邻 ......

232.用栈实现队列 卡哥建议：大家可以先看视频，了解一下模拟的过程，然后写代码会轻松很多。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.h ......

## 题目：[232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/) ### 思路： 因为go没有栈和队列的类型，直接自己写就行了。 比较简单的实现，具体看代码中的注释。 ### 代码： ```go type ......

## 四数相加II(力扣454.) - 前两个数组的值直接遍历，并将和存入map中，key为和，value为出现次数 - 后两个数组再次遍历，在map中寻找是否存在0-(c+d)，若存在，count+=value - for(a:A){//遍历AB - for(b:B){ - map[a+b]++; ......

503.下一个更大元素II 要求： 数组是环，需要找到下一个最大的元素 思路1： 先作为直线遍历，然后没有的节点，放到首部，再找比他大的节点 注意：头节点 代码： 1 // 要求：返回循环数组中下一个更大的数字步数 2 // 思路：先不循环遍历， 3 // 然后对每个-1节点，以他为起始，放到数组的 ......

KMP算法就是在一个字符串中寻找另一个子串，避免了“跳回下一个字符再重新匹配”，实现了在一次字符串的遍历过程中就可以匹配出子串。 28. 实现 strStr() （本题可以跳过） 卡哥建议：因为KMP算法很难，大家别奢求 一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立 ......

344.反转字符串 卡哥建议： 本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下 平时刷题什么时候用 库函数，什么时候 不用库函数 题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD ......

## 题目：[28. 找出字符串中第一个匹配项的下标](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/) ### 思路： 说白了就是匹配字符串，朴素就是暴力以每一个位置为起点都跑一遍。 ......

739. 每日温度 单调栈的思路： 如果要找左边第一个比当前数字大的节点 这个栈里面存放的是index，大——》小 如果一个新节点，比栈顶大，那么就是栈顶的第一个大于它的节点 代码： 1 // 单调栈：一维数组，寻找 元素右边，或者左边自己大或者小的元素的位置 2 3 // 要求：找到比当前节点值高 ......

## 题目：[344. 反转字符串](https://leetcode.cn/problems/reverse-string/) ### 思路： 每次把最前面和最后面的交换位置即可 `strings`库里没有反转的方法 ——这个反转是之后几个题的一个基础 ### 代码： 双指针调换位置 ```go ......

647. 回文子串 要求： 找出回文子串的个数 思路： 设置起始节点 如果头尾相等，且是相差为1，指定回文 如果相差很多，那么就看它的字串 代码： 1 // 要求：找出 正反相等，且连续字符，开始结束位置不同，也认为是一个 2 // dp[n][n] 起始-中止位置 3 // 4 // 如果两边相等 ......

583. 两个字符串的删除操作 要求： 删除最少的步数，来让这两个字符串相等 思路： 求末尾的最长公共子序列的长度，然后减去他们的长度 代码： 1 // 要求：两个字符串，删除任意一个字符后，让这两个字符相等 2 // dp[n][m] 以n-1结尾的字符串变成节点为m-1为子序列的最大个数 3 / ......

392.判断子序列 要求： 判断第一个字符串是否是第二个字符串的子序列 思路1： 设置成deque，如果长度为0则是 代码1： 1 // 要求： 判断s 是否是t的子序列 2 // 思路： 将s作为queue，如果头相等，那么就弹出，遍历后，查看是否为0 3 // 4 bool isSubseque ......

454.四数相加II 卡哥建议：本题是使用map巧妙解决的问题，好好体会一下 哈希法如何提高程序执行效率，降低时间复杂度，当然使用哈希法会提高空间复杂度，但一般来说我们都是舍空间换时间， 工业开发也是这样。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0454 ......

1143.最长公共子序列 要求： 可以跳过，找出来最长符合的节点 难点： 如何跳过了之后仍然保留之前的值 思路: 如果不符，并不是dp[i-1][j-2]等于之前的值，而是dp[i][j] 等于它的相关节点 以上很重要 代码 ： 1 // 要求： 两个子数组，可以删减跳过，找出最长的长度 2 // ......

## 题目：[454. 四数相加 II](https://leetcode.cn/problems/4sum-ii/) ### 思路： 首先，因为下标不同，因此相同的序列可能会出现很多次。 A + B + C + D = 0，那么当知道保存了A+B的和之后，就看有没有A + B = 0 - C - ......

# 哈希表 ## 哈希表理论基础 哈希表，又称为散列表（Hash Table)，是根据关键码的值而直接进行访问的数据结构 其中，数组就是一张哈希表；表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素 - 哈希表解决的问题：一般哈希表都是用来快速判断一个元素是否出现在集合中 - 哈希函数： ......

242.有效的字母异位词 卡哥建议： 这道题目，大家可以感受到数组用来做哈希表给我们带来的遍历之处。 题目链接/文章讲解/视频讲解： https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E ......

## 题目：[242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/) ### 思路： 很简单，就是看两个字符串每个字母出现的次数是不是相同的。 可以用两个数组来比较，也可以用一个数组比较。 ### 代码： 一个数组 ```go func ......

哈希表内容整体简单，关键是要有利用map映射的思想，以及巩固一些c++标准库的操作 这次三数之和一题没有直接做出来，关键在于如何查重一点比较绕 15. 三数之和 - 力扣（LeetCode） 利用排序+双指针解决三数之和的思路更加清楚 此外，四数之和中，四个数相加会溢出int，应改为 ......