随想录

## 题目：[332. 重新安排行程](https://leetcode.cn/problems/reconstruct-itinerary/) ### 思路： 其实这里已经是图的部分了，回溯应该也可以。Hierholzer算法解决欧拉问题 ### 代码： ```go func findItiner ......

### 二分查找 对数组的要求有两点： 有序 无重复元素，若有重复元素则返回的元素下标不唯一 边界条件是 `while(left 点击查看代码 ``` class Solution { public: int search(vector& nums, int target) { int length ......

## 题目：[491. 递增子序列](https://leetcode.cn/problems/non-decreasing-subsequences/ "491. 递增子序列") ### 思路： 核心问题——同层去重，这一题不能够重新排序因此不可以用`i > index && nums[i] == ......

## 题目：[93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/ "93. 复原 IP 地址") ### 思路： 1. 函数参数：参数就一个stirng，path先收集ip地址的四个部分，最后存入res中时拼接成一个str ......

530.二叉搜索树的最小绝对差 卡哥建议：需要领悟一下二叉树遍历上双指针操作，优先掌握递归 题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%8 ......

## 题目：[39. 组合总和](https://leetcode.cn/problems/combination-sum/description/ "39. 组合总和") ### 思路： 一样的递归套路： 1. 函数参数：因为要求和，所以有一个当前和的参数；另外因为**要保证没有重复的结果**，所 ......

654.最大二叉树 卡哥建议：又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%B ......

## 题目：[216. 组合总和 III](https://leetcode.cn/problems/combination-sum-iii/) ### 思路： 多加一个记录和的参数，还有一个起始位置的参数(不重复就得加) 结束条件是个数到了k： 1. 如果此时sum == n那就说明答案正确 2. ......

哈希表部分： 哈希表，简单来说就是k-v形式查询的结构，用来快速判断一个元素是否出现集合里，如hashmap 核心是哈希函数，k存哈希函数的值，找的时候找查询项的哈希函数值就行，返回v 出现哈希碰撞的时候，查找的流程怎么走呢？（*存疑，之后查一下） 类型：数组+集合set（set、multiset、 ......

203.移除链表元素 题目 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 第一想法 定义一个指针a指向头节点，顺序遍历链表，循环结束的条件是指针a.next为null 删除操作是判断a.next.val= ......

## 题目：[77. 组合](https://leetcode.cn/problems/combinations/) ### 思路： 回溯就是dfs的一个特殊情况也就是递归的一种情况，值得注意的一点： 要记得深拷贝，不然最后全是空 ### 代码： ```go var res [][]int var ......

977.有序数组的平方 题目 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 第一想法 隐隐约约有印象是用双指针法头尾一起向中间移动，因为这个数组的特点决定了平方数中间小两边大 思路&题解 class Solution { publ ......

## 题目：[669. 修剪二叉搜索树](https://leetcode.cn/problems/trim-a-binary-search-tree/) ### 思路： 遍历到的值小于最小值，说明左子树里的所有节点都小于最小值，舍弃左子树。 遍历到的值大于最大值，说明右子树里的所有节点都大于最大值 ......

找树左下角的值 卡哥建议：本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下 题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80% ......

卡哥建议：迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。 110.平衡二叉树 （优先掌握递归） 卡哥建议：再一次涉及到，什么是高度，什么是深度，可以巩固一下。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A ......

## 题目：[235. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/) ### 思路： BST和普通二叉树不同的一点是可以根据特性来找最近公共祖先，只要找到第一个值 ......

## 单调数列：滑动窗口最大值(力扣239.) - 给定滑动窗口的范围，求每个滑动窗口范围内的最大值 - 使用单调队列实现 - 对于最大值数字前面的数字不存入数列，对于最大值数字后面的数字存入数列中 - 单调队列中数字的大小呈递减顺序 - pop(value)：如果窗口移除的元素等于单调队列的队口元 ......

## 题目：[530. 二叉搜索树的最小绝对差](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/) ### 思路： 一个关键问题——BST的中序遍历是由小到大的顺序，也就是说记录遍历的前一个节点，每次比较当前节点-前一 ......

## 有效的括号(力扣20.) - 括号匹配时使用栈解决的经典问题 - 题意其实就像我们在写代码的过程中，要求括号的顺序是一样的 - 有左括号，那么在对应位置则必须有右括号 - 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false 第二种情况 ......

代码随想录 (programmercarl.com) 这里总结一下一次没有思路做出来的题目 12、113、654、98、530、501 二叉搜索树的题目一开始递归做起来不太顺畅，需要巩固 此外，leetcode上已写好的函数形式会提醒我思路，例如，递归的时候到底应不应该返回值，是void还是Tree ......

## 题目：[654. 最大二叉树](https://leetcode.cn/problems/maximum-binary-tree/) ### 思路： 和前中序构造树差不多的方法，以前是返回值，现在是返回树 ### 代码： ```go /** * Definition for a binary ......

## 题目：[513. 找树左下角的值](https://leetcode.cn/problems/find-bottom-left-tree-value/) ### 思路： 层序遍历是最好的选择了，先放右节点，再放左节点最后一个元素就是最左侧的节点。 说白了层序遍历就是广度优先搜索BFS。 ### ......

## 题目：[110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/) ### 思路： ![20210203155515650.png](https://s2.loli.net/2023/08/11/zAjhQ2sON5WXaTd ......

104.二叉树的最大深度 （优先掌握递归） 卡哥建议：什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。大家要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0 ......

层序遍历 卡哥建议：看完本篇可以一口气刷十道题，试一试， 层序遍历并不难，大家可以很快刷了十道题。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8 ......

## 题目：[104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/) ### 思路： 本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。 - 二叉树节点的深 ......

704 二分查找 题目 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 第一想法 判断条件是 value = target 因为数组是升序，其实每种查找方法应该相差不大？ 不过 ......

# 栈与队列 ## 理论知识 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。 **栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔 ......

理论基础 卡哥建议：需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义 文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 补充的知识点： ......

## KMP算法(没掌握) - 主要功能：字符串匹配 - 理论：检测文本串中是否出现过模式串 - 前缀就是包含首字母不包含尾字母的所有子串 - 后缀就是包含尾字母不包含首字母的所有子串 - 最长相等前后缀：对子串分别分析，从左向右 - **前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时 ......