LCR 124. 推理二叉树
某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。
注意：preorder 和 inorder 中均不含重复数字。
示例 1：
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
前序遍历的结果为[根节点，左子树前序，右子树前序]
中序遍历的结果为[左子树中序，根 ...
LCR 123. 图书整理 I
书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。
示例 1：
**输入：**head = [3,6,4,1]
输出：[1,4,6,3]
提示：
0 <= 链表长度 <= 10000
可以反转链表
12345678910111213141516171819class Solution {public: vector<int> reverseBookList(ListNode *head) { if (head == nullptr) return {}; ListNode *pre = nullptr, *cur = head; while (cur != nullptr) { ListNode *ne = cur->next; cur->next ...
LCR 121. 寻找目标值 - 二维数组
m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：
每行中，每棵植物的右侧相邻植物不矮于该植物；
每列中，每棵植物的下侧相邻植物不矮于该植物。
请判断 plants 中是否存在目标高度值 target。
示例 1：
**输入：**plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8
**输出：**true
示例 2：
**输入：**plants = [[1,3,5],[2,5,7]], target = 4
**输出：**false
提示：
0 <= n <= 1000
0 <= m <= 1000
考虑数组的有序性，[0][0]为最小值，[m][n]为最大值
想到另两个对角点，对于右上角，向左变小，向右变大，所以寻找target的过程就是向左向右选择的过程
1234567891011121314151617181920class Solution {public: bool findTargetIn2DPlants(vector<vector<i ...
LCR 120. 寻找文件副本
设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。
示例 1：
**输入：**documents = [2, 5, 3, 0, 5, 0]
**输出：**0 或 5
提示：
0 ≤ documents[i] ≤ n-1
2 <= n <= 100000
原地排序，由题目documents[i]的范围可得数组下标与元素是一一对应的，
所以遍历下标时只需要考虑当前值和下标是否相等
不相等要把元素交换到对应下标直到当前下标是对应的元素
或者当前元素对应下标所含元素已经是正确的值（此时交换会死循环，也即找到重复值）
12345678910111213141516class Solution {public: int findRepeatDocument(vector<int> &documents) { for (int i = 0; i < documents.size(); i++) { i ...
400. 第 N 位数字
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。
示例 1：
**输入：**n = 3
**输出：**3
示例 2：
**输入：**n = 11
**输出：**0
**解释：**第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0 ，它是 10 的一部分。
提示：
1 <= n <= 2(31) - 1
我们可以先找出第n个数字是在几位数中，再找出是第几个数，最后找出是哪一位
一个变量 start 表示从start开始的第n个数字
num表示几位数，maxN表示一共多少个数字，例如一位数共9个，两位数共（99-9）*2
三位数共（999-99）*3个
n每次减去当前num位数的总数字，直到不足maxN
12345678910111213141516171819202122232425class Solution { public : int findNthDigit(int n) { ...
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
此树为二叉搜索树，我们可以很容易得到到达每个结点的路径
所以可以分别获取到达两个结点路径，然后寻找最后一次重复的结点
1234567891 ...
