大白羊_Aries-CSDN博客

原创 LeetCode 946. 验证栈序列

当所有元素处理完后，栈部不为空的话则说明栈序列不合法。中的元素入栈，同时判断，栈顶元素是否等于。，如果是则元素出栈，

2022-08-31 21:33:43 1003 1

那么有了序号还需要层遍历吗？不需要，因为在先序遍历中，我们永远都是先访问到这一层最左边的结点，所以先序遍历就可以帮助我们记录到每一层序号最小的元素。如果这道题让你用层遍历会怎么做，即使是空指针的结点也应该记为 -1 这样的一个元素压入到队列中，然后统计每层的宽度。需要注意的是在 C++ 代码中，需要使用 usigned long long 来存储 index。序号的作用就是这样，代替了我们去一个个将空指针转换成 -1 放入到队列中。这道题画个图就清楚很多了，先理解一下为什么我们要编号。.........

2022-08-27 14:50:44 504

原创 LeetCode 658. 找到 K 个最接近的元素

为什么要说这个问题，可能你会想按照下面的写法，让 right 先走，但是。就可以分两半边，两边各记录一个指针，分别比较着原理。双指针，既然数组已经排序好了，那么按照。，这就决定了我们最终取结果时只能是从。有个问题要注意，实例 2 出现。

2022-08-25 16:00:41 1227

原创 LeetCode 39. 组合总和

39. 组合总和这道题超级简单，如果你看过 LeetCode 77. 组合这篇的解法，你肯定知道 backtrace 时 iii 都是从 startstartstart 开始，那么下一层回溯树就是从 start+1start + 1start+1 开始，从而保证 nums[start]nums[start]nums[start] 这个元素不会被重复使用但是，我们现在希望能够重复使用 nums[start]nums[start]nums[start] 这个元素，那么很好办嘛，我只要把 i+1i + 1i+

2022-06-06 22:52:51 675 1

原创 LeetCode 47. 全排列 II

47. 全排列 II这道题同样还是回溯剪枝的问题，但是这里的剪枝有点技巧。我们先来分析一下，例如，nums=[1,2,2′]nums = [1,2,2']nums=[1,2,2′]，不剪枝的话，会得到如下的结果如果我们保证相同元素在排列中的相对位置保持不变，比如说 nums=[1,2,2′]nums = [1,2,2']nums=[1,2,2′] 这个例子，我保持排列中 222 一直在 2′2'2′ 前面。这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：仔细思考，应该很容易明白其中的原

2022-06-06 22:38:16 79

原创 LeetCode 40. 组合总和 II

40. 组合总和 II其实这道题可以看成一个组合问题——计算 candidatescandidatescandidates 中所有和为 targettargettarget 的子集，组合和子集其实是类似的，在看下面代码之前不放先理解一下 LeetCode 90. 子集 II...

2022-06-06 22:16:35 672

原创 LeetCode 90. 子集 II

90. 子集 II我们考虑回溯的方法，但是和 LeetCode 78. 子集不同的是我们这里需要考虑剪枝的问题，例如对于题目例子 nums=[1,2,2]nums = [1,2,2]nums=[1,2,2]，不剪枝的话生成的结果如下图所示而正确的结果应该是所以我们必须有剪枝这一步，体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i]==nums[i−1]nums[i] == nums[i-1]nums[i]==nums[i−1]，则跳过。具体看下面实现...

2022-06-06 22:00:29 854

原创 LeetCode 77. 组合

77. 组合先不考虑效率，这道题就是一个典型回溯框架可以解决的问题，详细可以参考 LeetCode 78. 子集

2022-06-06 21:25:45 622

原创 LeetCode 78. 子集

78. 子集在编程中涉及的排列组合问题都离不开回溯，我们下面贴出一个关于回溯的伪代码，有了这个回溯框架，再结合回溯树就很好理解了

2022-06-06 21:09:23 632

原创 LeetCode 283. 移动零

题目描述283. 移动零解法这道题其实就是 LeetCode 27. 移除元素的延伸，将 0 全部删除然后再补上就好了class Solution {public: void moveZeroes(vector<int>& nums) { int p = removeElement(nums, 0); for (; p < nums.size(); p++) nums[p] = 0; }

2022-05-23 20:02:40 144

原创 LeetCode 27. 移除元素

题目描述27. 移除元素解法解法还是快慢指针：如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步但是，注意这里和有序数组去重（26. 删除有序数组中的重复项）的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0…slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slowclass Solution {public: int removeElemen

2022-05-23 19:48:57 169

原创 LeetCode 83. 删除排序链表中的重复元素

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！这是你第一次使用 Markdown编辑器所展示的欢迎页。如果你想学习如何使用Mar

2022-05-23 19:38:58 80

原创 LeetCode 341. 扁平化嵌套列表迭代器

题目描述341. 扁平化嵌套列表迭代器解法：递归这道题最重要的是先理解题意，在理解的情况下，其实我们要做的就是一棵 N 叉树的遍历，为什么这样说呢？比如说输入是 [[1,1],2,[1,1]][[1,1],2,[1,1]][[1,1],2,[1,1]]，其实就是如下树状结构：把一个 NestedInteger 扁平化就等价于遍历一棵 N 叉树的所有「叶子节点」，我把所有叶子节点都拿出来，不就可以作为迭代器进行遍历了吗？有了如此思路，下面的代码就容易解决了/** * // This is t

2022-05-15 17:55:16 188

原创 LeetCode 1373. 二叉搜索子树的最大键值和

题目描述1373. 二叉搜索子树的最大键值和解法这道题在一个结点处要同时判断三件事情：左右子树是否是 BST左子树的最大值和右子树的最小值左右子树的节点值之和无疑，采用后序遍历才能知道该结点左右子树的情况。因为同时要判断的内容比较多，我们用一个数组来存储一下这些信息，记这个数据为 infosinfosinfos，长度为 444infos[0]infos[0]infos[0] 记录以 root 为根的二叉树是否是 BST，若为 111 则说明是 BST，若为 000 则说明不是 BST

2022-05-12 21:15:22 563

原创 LeetCode 449. 序列化和反序列化二叉搜索树

题目描述449. 序列化和反序列化二叉搜索树解法还是老问题，我们要还原唯一一棵二叉树非中 + 前或中 + 后两种组合不可，之前在 LeetCode 297. 二叉树的序列化与反序列化一题中可以唯一确定一棵二叉树是因为我们保存了空指针信息但是对于 BST 也是一个特殊情况，考虑 BST 的特性，我们可以通过如下操作唯一确定考虑前序遍历一棵 BST，仅保存节点值序列化 BST。那么在反序列化时，我们根据从字符串分割得到的前序遍历结果 nodesnodesnodes 就可以递归还原这棵 BST，对于连

2022-05-11 21:21:14 264

原创 LeetCode 95. 不同的二叉搜索树 II

题目描述95. 不同的二叉搜索树 II解法：如果你知道 96. 不同的二叉搜索树这道题的解法，那么你应该就不陌生下面的代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} *

2022-05-11 20:25:06 194

原创 LeetCode 96. 不同的二叉搜索树

题目描述96. 不同的二叉搜索树解法:我们先举个例子，如果固定 333 作为根节点，左子树节点就是 {1,2}\{1,2\}{1,2} 的组合，右子树就是 {4,5}\{4,5\}{4,5} 的组合。左子树的组合数和右子树的组合数乘积就是 333 作为根节点时的 BST 个数那么接下来的代码就很好写了，按照递归的思路，每次闭区间 [lo,hi][lo, hi][lo,hi] 的数字能组成 count(lo,hi)count(lo, hi)count(lo,hi) 种 BST就能知道 [1,n][1

2022-05-11 20:12:05 471

原创 LeetCode 538. 把二叉搜索树转换为累加树

题目描述538. 把二叉搜索树转换为累加树解法这道题还是用二叉搜索树中序遍历的特性，但是如果是按照升序遍历的话，我们很难统计类似于 2、3 结点的累加值，所以，我们先遍历右子树再遍历左子树，按照降序遍历就非常容易计算累加了/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNod

2022-05-08 15:42:30 522

原创 LeetCode 433. 最小基因变化

题目描述433. 最小基因变化解法：双向 BFS我们知道双向 BFS 最大的特点就是知道起点，知道终点，两头向中间扩散。那么这道题使用双向 BFS 再合适不过，如果你已经做过 752. 打开转盘锁，这道题其实是同理的：打开转盘锁因为限定了 deads 而必须在扩散过程中剪枝，而这道题刚好反过来，只有 bank 中的才可以扩散class Solution {public: int minMutation(string start, string end, vector<string&

2022-05-07 20:49:11 587

原创 230. 二叉搜索树中第K小的元素

题目描述230. 二叉搜索树中第K小的元素解法：中序遍历既然是二叉搜索树，那么中序遍历的结果就是一个升序排序的结果，找第 k 个元素肯定不是什么难事/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nul

2022-04-26 22:35:44 697

原创 LeetCode 868. 二进制间距

题目描述868. 二进制间距解法通过右移计算数字的二进制中有多少个 1，再通过变量 last 记录上一个 1 出现的位置class Solution {public: int binaryGap(int n) { int last = -1, ans = 0; for (int i = 0; n; i++) { if (n & 1) { if (last

2022-04-24 20:30:31 107

原创 396. 旋转函数

题目描述396. 旋转函数解法这道题很简单，像是斐波那契数列一样，存在一个递推的等式class Solution {public: int maxRotateFunction(vector<int>& nums) { int f = 0, n = nums.size(); int all_sum = accumulate(nums.begin(), nums.end(), 0); for (int i = 0; i &l

2022-04-22 11:29:26 178

原创 LeetCode 1672. 最富有客户的资产总量

题目描述1672. 最富有客户的资产总量解法：没啥巧解，就是 O(n∗m)\mathcal O(n*m)O(n∗m) 的方法class Solution {public: int maximumWealth(vector<vector<int>>& accounts) { int max_num = INT_MIN, ans = 0; for (auto row: accounts) {

2022-04-14 15:38:03 205

原创 LeetCode 806. 写字符串需要的行数

题目描述806. 写字符串需要的行数解法：简单模拟一下，lines 表示写了多少行，cursor 表示当前填充光标所在位置class Solution {public: vector<int> numberOfLines(vector<int>& widths, string s) { int lines = 0, cursor = 0; for (auto c: s) { int t

2022-04-12 22:20:12 113

原创 LeetCode 652. 寻找重复的子树

题目描述652. 寻找重复的子树解法：这道题分为两步：一是如何看到自己的子树长什么样子，二是如何看到别人的子树长什么样子对于第一步，可以通过后序遍历序列化来记录当前结点的子树；对于第二步，建立一个 hash map 来记录每个结点子树的序列化结果，同时 hash map 记录当前这种子树出现过的次数，这么做可以帮助我们去除重复的结果/** * Definition for a binary tree node. * struct TreeNode { * int val; *

2022-04-08 22:01:34 505

原创 LeetCode 429. N 叉树的层序遍历

题目描述429. N 叉树的层序遍历解法：二叉树怎么做层遍历，N 叉树就怎么做层遍历/*// Definition for a Node.class Node {public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children)

2022-04-08 20:39:01 470

原创 LeetCode 297. 二叉树的序列化与反序列化

题目描述297. 二叉树的序列化与反序列化解法：我们知道要唯一确定一棵二叉树，要么是前序 + 中序，要么是中序 + 后序。但是，在这道题中前序遍历的结果记录了空指针的信息，那么就可以序列化结果唯一确定一棵二叉树/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x

2022-04-07 23:46:52 739

原创 LeetCode 796. 旋转字符串

题目描述796. 旋转字符串解法：首先，如果 sss 和 goalgoalgoal 的长度不一样，那么无论怎么旋转，sss 都不能得到 goalgoalgoal，返回 false\text{false}false字符串 s+ss+ss+s 包含了所有 sss 可以通过旋转操作得到的字符串，只需要检查 goalgoalgoal 是否为s+ss+ss+s 的子字符串即可class Solution {public: bool rotateString(string s, string goa

2022-04-07 19:45:41 293

原创 LeetCode 310. 最小高度树

题目描述解法：拓扑排序最简单的方法是对每个顶点都做一遍 bfs，记录下每个结点的高度，再取最小即可。想法没问题，超时我们还是沿着 bfs 的思路再想一下，其实我们有一个直觉，最小树的根节点一定是图中最长路径的中间节点，这一点是可以通过数学证明的，详细可以参见官方题解那么，接下来我们就可以根据拓扑排序来确定最长路径上能形成最小数的根节点，如下所示class Solution {public: vector<int> findMinHeightTrees(int n, vec

2022-04-06 23:26:22 154

原创 LeetCode 744. 寻找比目标字母大的最小字母

题目描述744. 寻找比目标字母大的最小字母解法：二分查找，结束后再次 check 一下，如果不满足，则返回数组首元素class Solution {public: char nextGreatestLetter(vector<char>& letters, char target) { int low = 0, high = letters.size() - 1; while (low < high) {

2022-04-03 11:29:38 547

原创 LeetCode 954. 二倍数对数组

题目描述954. 二倍数对数组解法：设 arr\textit{arr}arr 的长度为 nnn，题目本质上是问 arr\textit{arr}arr 能否分成 n2\dfrac{n}{2}2n 对元素，每对元素中一个数是另一个数的两倍。设 cnt[x]\textit{cnt}[x]cnt[x] 表示 arr\textit{arr}arr 中 xxx 的个数对于 arr\textit{arr}arr 中的 000，它只能与 000 匹配。如果 cnt[0]\textit{cnt}[0]cnt[0]

2022-04-01 22:58:08 208

原创 LeetCode 889. 根据前序和后序遍历构造二叉树

题目描述889. 根据前序和后序遍历构造二叉树解法：首先通过数据结构都知道，前序加后序并不能唯一确定一棵二叉树，但是不要紧，我们依然还是能够通过递归构造出一棵可能的二叉树，具体流程如下首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值然后把前序遍历结果的第二个元素作为左子树的根节点的值（实际上，如果根节点的左子树有可能是空指针，那么此时的这个元素就应该是右子树的根节点，所以导致了二叉树结构不唯一，如下图所示）在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引

2022-03-29 22:48:51 702

原创 LeetCode 106. 从中序与后序遍历序列构造二叉树

题目描述106. 从中序与后序遍历序列构造二叉树解法：具体从后序结果和中序结果构造二叉树的流程就不再介绍，我们这里给出一幅图说一下关于索引的确定int leftSize = index - inStart;root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);root.right = build(inorder, ind

2022-03-29 22:23:26 359

原创 LeetCode 105. 从前序与中序遍历序列构造二叉树

题目描述105. 从前序与中序遍历序列构造二叉树解法：具体从前序结果和中序结果构造二叉树的流程就不再介绍，我们这里给出一幅图说一下关于索引的确定int leftSize = index - inStart;root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);root->right = build(preorde

2022-03-28 21:42:34 645

原创 LeetCode 693. 交替位二进制数

题目描述693. 交替位二进制数解法：当给定值 nnn 为交替位二进制数时，将 nnn 右移一位得到的值 mmm 仍为交替位二进制数，且与原数 nnn 错开一位，两者异或能够得到形如 0000...11110000...11110000...1111 的结果 aaa，此时对 aaa 执行加法（进位操作）能够得到形如 0000...100000000...100000000...10000 的结果，将该结果与 aaa 执行按位与后能够得到全 000 结果举个例子一看就懂， 101010101010 右

2022-03-28 21:20:06 166

空空如也

空空如也