114. 二叉树展开为链表——flatten-binary-tree-to-linked-list给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
12输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
12输入：root = []输出：[]
示例 3：
12输入：root = [0]输出：[0]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ked-list
我的思路1ms|击败32.28%
原本想着递归拿到先序序列，再构建这个新的“链表”
12345678910111213141516171819202122232425262728class So ...
算法题解
未读105. 从前序与中序遍历序列构造二叉树——construct-binary-tree-from-preorder-and-inorder-traversal给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
12输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7]
示例 2:
12输入: preorder = [-1], inorder = [-1]输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前 ...
考试复习
未读填空一、散列查找1.哈希查找：计算哈希地址→构建表（链地址法或者开放定址法）→统计查找长度
哈希函数：题目给出 H(k) = k mod 11（地址范围 0~10）；
解决冲突方式：
链地址法→竖着画（同一地址的关键字按顺序连成链表，新冲突元素默认插在链表尾部，除非题目指定头部）；
开放定址法→横着画（看是线性探测还是二次探测）
查找成功的平均查找长度ASL = 所有关键字的查找长度之和 ÷ 关键字总数 n；
在等概率情况下查找不成功时的平均查找长度是=加起来/地址空间个数
例子：78，25，30，19，6，130，205，115，39，396，63，337
用上述关键字序列构造散列表，散列表的地址空间为A[0…14]，哈希函数采用除留余数法设计，处理冲突的办法采用线性探测再散列法。请问：
在散列表中查找关键字396需要依次和哪些关键字比较（不包括关键字396）（19-6）；
在散列表中查找关键字51需要依次和哪些关键字比较才能确定不存在（25-63-337-78-130-39）；
散列表地址空间中，空的没有填写关键字的地址下标（从小到大）依次是（3-5-9）；
在 ...
102. 二叉树的层序遍历——binary-tree-level-order-traversal给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
12输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]
示例 2：
12输入：root = [1]输出：[[1]]
示例 3：
12输入：root = []输出：[]
提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
我的思路
最简单的就是直接顺序输出层序遍历，但是这里要分层（每层是一个List）
我想到了老师讲的哨兵结点：
我的错误代码1234567891011121314151617181920212223242526272829303132class Solution { public List<List<Integer>> levelOrder(TreeNode root) { ...
98. 验证二叉搜索树——validate-binary-search-tree给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
12输入：root = [2,1,3]输出：true
示例 2：
123输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
第一想法
就是广度优先搜索，先入队根节点，访问孩子的时候，检查+入队，直到队列为空
我的错误代码
我把入栈、出栈与入队、出队搞混了
12345678910111213141516171819202122232425262728293031323334353637383940public class TreeNode ...
96. 不同的二叉搜索树——unique-binary-search-trees给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
12输入：n = 3输出：5
示例 2：
12输入：n = 1输出：1
提示：
1 <= n <= 19
第一想法
二叉搜索树就是左小右大
用回溯法，先选一个，然后递归，回溯
但是如果是先选2的话，后面的顺序是13和31创建的二叉搜索树是一样的：
123 2 / \1 3
官方答案方法一：动态规划思路
给定一个有序序列 1⋯n，为了构建出一棵二叉搜索树，我们可以遍历每个数字 i，将该数字作为树根，将 1⋯(i−1) 序列作为左子树，将 (i+1)⋯n 序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。
在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。
由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。
算法
题目要求是计算 ...
79. 单词搜索——word-search给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
12输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"输出：true
示例 2：
12输入：board = [['A','B','C','E'],['S',' ...
78. 子集——subsets给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
12输入：nums = [0]输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
看到了官方给的提示我才知道咋写：位运算 数组 回溯
我的答案：回溯123456789101112131415161718192021class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList< ...
75. 颜色分类——sort-colors给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
12输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2]
示例 2：
12输入：nums = [2,0,1]输出：[0,1,2]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶：
你能想出一个仅使用常数空间的一趟扫描算法吗？
我的「不符合题目要求」答案：
居然过了，但是时间复杂度太高→3ms|击败2.64%（而且不符合要求）
12345class Solution { public void sortColors(int[] nums) { Arrays.sort(nums); }}
我 ...
72. 编辑距离——edit-distance给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
123456输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
示例 2：
12345678输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e') ...
公告
