138. 随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
**输入：**head = ...
136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
**输入：**nums = [2,2,1]
**输出：**1
示例 2 ：
**输入：**nums = [4,1,2,1,2]
**输出：**4
示例 3 ：
**输入：**nums = [1]
**输出：**1
提示：
1 <= nums.length <= 3 * 10(4)
-3 * 10(4) <= nums[i] <= 3 * 10(4)
除了某个元素只出现一次以外，其余每个元素均出现两次。
利用了
a^a = 0
0^a = a
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
**输入：**s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
**输入：**s = “a”
输出：[[“a”]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
按字符进行拼接，每个字符有两个选择
与前一个字符相拼
若已拼字符为回文串，则当前字符可作为新串的开头
可以提前获取每段是否为回文串
12345678910111213141516171819202122232425262728293031323334353637383940class Solution {public: vector<vector<string>> ans; vector<string> mid; vector<vector<string>> partition(string s) { vector&l ...
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
**输入：**nums = [100,4,200,1,3,2]
**输出：**4
**解释：**最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
**输入：**nums = [0,3,7,2,5,8,4,6,0,1]
**输出：**9
示例 3：
**输入：**nums = [1,0,1,2]
**输出：**3
提示：
0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
对数组中每个元素考虑其–和++的元素是否在数组中
可以使用unordered_set us先去重，然后遍历us的每个元素 i ，再不断减一或加一判断其是否在us中，
可以只对i-1（i+1同理）不在us中的元素只判断 i++，这样同一个区间我们只需要判断一次就可以了
12345678910111213141516171819class Soluti ...
124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
**输入：**root = [1,2,3]
**输出：**6
**解释：**最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
**输入：**root = [-10,9,20,null,null,15,7]
**输出：**42
**解释：**最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 10(4)]
-1000 <= Node.val <= 1000
对于每个节点为根节点时都有自己的最大路径和，所以求出每个节点的最大路径和取最大值即可
每个节点的最大路径和有三种情况：
左右子节点最大路径和均>0，l+r+root->val为最大路径和
左右子节点 ...
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
**输出：**5
**解释：**在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
**输入：**prices = [7,6,4,3,1]
**输出：**0
**解释：**在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 10(5)
0 <= prices[i] <= 10(4)
可以把绘制柱形图，最后的结果就是在买入点向右看高低差的最大值
所以我们可以从右向左遍历，每次遇到更高的柱子，我 ...
