考察知识点：滑动窗口题目分析： 可以通过使用动态的滑动窗口解决问题。首先left和right指向最开始，然后只让right向右移动，每遍历到一个需要的字符时就记录下来。当left和right之间的字符满足条件时，right指针不动，left向右移动，每次遍历到一个需要的字符时需要将相应的字符减一，看是否仍满足条件。直到不满足条件的前一个字符，就是这一次找到的最短的满足需求的字符串。 到这时还没有结束，因为还没有遍历完整个数组，右边可能还有更短的。所以让right继续向右走，直到遍历完整个数组为止。所用编程语言：C++ #include <unordered_m...

考察知识点：单调队列题目分析： 题目中的数组是指一头牛随时间的增加活动范围的变化而形成的数组。然后让求连续的k个小时内，牛的活动的最小范围。即：这类题目应该使用双端队列做一个单调队列，使得队列尾为最小值，从尾到头值依次增大：这样维护一个窗口中的最小值。所用编程语言：C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @r...

考察知识点：单调栈题目分析： 为一个连续的牛舍盖棚时，牛舍的宽度是牛舍的个数，而牛舍的长度是其中的最小牛舍长。例如有三个牛舍，分别长 9 8 7 9 ，那么给这几个牛舍盖棚时，牛舍的宽度就是4，长度就是7。 连续牛舍中的最小长度影响了整个牛棚的长度。为了能得到更大的牛棚面积，我们发现，如果连续牛舍中有一个牛舍长度较小，那么最好是宽度能取宽一点，就是牛舍的个数多一点。先假设牛舍中最小的长度不变，我们扩大牛舍的范围，发现对结果是增益的，因为长不变，宽在增大；扩大的极限在哪里呢，就是取完所有牛舍，或者左边或右边再扩大一个牛舍时，最小长度会变小。 如果取这个更...

考察知识点：数组、单调栈题目分析：方法一：双指针 遍历一遍数组即可。指针i指向第i天，用指针j向后查找看那一天能大于第i天的体重，返回j与i的差值即可。没有找到则返回-1。方法二：单调栈 单调栈适合解决这种找与某个数最近的更大的数或更小的数的问题。 如果我们想要找到右边序列中更大或更小的数，那么就是说我需要先知道右边的数，即我需要从右向左遍历。 如上图所示，第一个遍历到的数是13，他右边没有数，所以它对应的grouth就是-1。而第二个遍历到的数是76，右边的数是13比他小，所以它对应的grouth是-1。第三个数是72，右边的数是76和...

考察的知识点：优先队列、对顶堆题目分析： 因为序列可能是无序的，每加入一个数就需要对所有数进行排序。如果我们将排好序的序列一分为二，发现中位数只与左边序列的最大值和右边序列的最小值有关。可以通过使用对顶堆找到这个最大值和最小值，即使用大顶堆保存左边较小的序列，可以直接获得这些序列中的最大值；使用小顶堆保存右边较大的序列，可以直接获得这些序列中的最小值。 构造这两个堆需要注意两点：为了让更大的数放在上面的堆上，如果新加入的价格大于中位数，则将该价格放入上面的小顶堆中；反之放入下面的大顶堆中。为了让大顶堆中容纳数的范围是从1~N / 2 （注意向0取整），小顶堆中容纳数...

考察知识点： 拓扑排序、队列题目分析： 做一件事之前必须先完成一些事，这样的做事顺序就是拓扑序列。可以使用队列判断一个序列能否是拓扑序。 首先如果做一件事之前不需要做其他事，那么我们就可以选择完成这一件事。当这一件事完成之后，可能就会有依赖这件事的事情可以做了。对该题而言，首先记录每个节点被哪些结点依赖，然后记录每一个结点的入度。 记录完所有的事件后，遍历所有事件的入度，如果为0那么我们就将其加入到队列中。完成后对队列中的元素进行访问，每次访问完毕后将结点加入到vector中并释放该节点，那么依赖该结点的事件就有可能入度为0了。将入度为0的序列加入到队列中等待被重复上述处理即可。 当队列中处理...

考察知识点：拓扑排序、队列题目分析： 做一件事之前必须先完成一些事，这样的做事顺序就是拓扑序列。可以使用队列判断一个序列能否是拓扑序。 首先如果做一件事之前不需要做其他事，那么我们就可以选择完成这一件事。当这一件事完成之后，可能就会有依赖这件事的事情可以做了。对该题而言，首先记录每个节点被哪些结点依赖，然后记录每一个结点的入度。 记录完所有的事件后，遍历所有事件的入度，如果为0那么我们就将其加入到队列中。完成后对队列中的元素进行访问，每次访问完毕后释放该节点，那么依赖该结点的事件就有可能入度为0了。将入度为0的序列加入到队列中等待重复上述处理即可。 当队列中处理完毕后，如果访问到的牛的数量小于...

考察知识点： 数组、双指针题目分析： 可以通过双指针解决题目。首先用指针i遍历整个数组，指针j用来改变数组。每当i遍历到val时，总是让j停下来一步，当指针i指向的值不是val时就覆盖到指针j所指向的数组上。例如：2 1 3 5 7 1 1 1 6 9， val = 1 一开始i和j的指针位置相同，而当i指向val时，j指针就会停下来一步： 此时发现i指向的数据为3，将3覆盖到指针j指向的位置即可。之后发现将i的指针赋值到j的位置时，相当于数组往前移动1位，即找到多少个val后，j与i之间就会相差多少，数组就能前移多少。所用编程语言：C++ class Solution { ...

考察知识点： 树的中序遍历 题目分析：  题目要求按照中序遍历的顺序将二叉树展开。对这样的问题都需要我们动手画图，观察规律。下图给出了某个二叉树的中序遍历。  对该二叉树按照中序遍历的顺序展开之后，会形成如下图所示的链表：  我们首先观察一个简单问题，对于该树的左子树，它发生了如下图所示的变化：  发现该子树中，从根节点9指向左孩子3的指针改变成了从左孩子3指向根节点9。之后我们观察整棵子树：  发现从根节点10指向左孩子9的指针改变成了从叶子节点6指向根节点10。说明我们应该根据中序遍历的顺序调整指针，需要找到从左孩子中不断向右查找，直到找到在左孩子中进行中序遍历访问到的最后一个节点...

考察知识点： 树的遍历 题目分析：  题目要求按照先序遍历的顺序将二叉树展开成链表。首先我们要熟悉先序遍历，在先序遍历序列整体上，先遍历根节点，然后遍历左子树，最后再遍历右子树。  可以看到在访问节点6之后就要开始遍历右子树了。可以直接将右子树连接到节点6的右子树上，因为这样不影响先序遍历的访问顺序，在对这一棵新树进行先序遍历与对原来的树进行先序遍历等价。  将右子树移动到左子树末尾后就可以将根节点的right指针改为左子树，将left指针改为nullptr了。然后通过递归的方式，以root->right为根节点将子树的树形结构展开。 所用编程语言： C++ /** * struc...

考察知识点： 树的遍历 给定中序和其它一种遍历的序列就可以唯一确定一棵二叉树的结构。给出先序和后序遍历序列得到的二叉树结构不唯一。 先序遍历序列、中序遍历序列、后序遍历序列的特点： 先序遍历序列： [3, 9, 20, 15, 7]，第一个数是根节点，右边依次是左子树和右子树中的节点，左子树的节点和右子树的节点都是分别靠在一起的，但是无法确定这两个子树的分界线。 中序遍历序列： [9, 3, 15, 20, 7]，如果确定了根节点，那么就能确定左右子树的分界线，明确左右子树中包含哪些节点。 后序遍历序列： [9, 15, 7, 20, 3]，最后一个数是根节点，左边从左到右依次是左子树和右子...

考察知识点： 树的遍历 给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。给出前序和后序遍历序列确定的二叉树结构不唯一。 前序遍历序列、中序遍历序列、后序遍历序列的特点： 前序遍历序列： [3, 9, 20, 15, 7]，第一个数是根节点，右边依次是左子树和右子树中的节点，左子树的节点和右子树的节点都是分别靠在一起的，但是无法确定这两个子树的分界线。 中序遍历序列： [9, 3, 15, 20, 7]，如果确定了根节点，那么就能确定左右子树的分界线，明确左右子树中包含哪些节点。 后序遍历序列： [9, 15, 7, 20, 3]，最后一个数是根节点，左边从左到右依次是左子树和右...

考察知识点： 深度优先搜索、后序遍历 题目分析：  怎样找到一条路径，使得从一个任意节点到一个叶子节点之间的路径最短呢？我们先考虑简单的情况：  当只有一个节点时，那么最大奶牛群就是这一个奶牛。当有上图所示的三个节点时，发现最大奶牛群是有根节点、左孩子和右孩子构成的。最大奶牛群中一定包含一个子树的根节点。当再复杂一些时，如下图所示：  发现可以考虑以下问题： 若把节点15看作根节点，节点35，15, 40可以构成最大产奶牛群吗？ 若把节点15看作路径中的某个点，那么从节点35过来的大还是从节点40过来的大？  问题1只需要将左子树最长单向路径加上根节点的产奶量再加上右子树的最长单向路径...

考察知识点： 深度优先搜索、先序遍历 题目分析：  由于每一个产奶量都是由一条从根节点到叶子节点的路径构成的，每一个数的高位都是根节点，低位是叶子节点，即产奶量从高位到低位对应着二叉树的深度从低到高。可见我们可以使用先序遍历的方式来解决问题。  在遍历时，首先要将之前得到的产奶量数字末尾加上该节点的数字，可以先将原来的数字乘以10,再加上该节点的数字。当遍历到叶子节点，即左右孩子均为空节点时，将num加入到sum中。由于num是值传递，遍历左子树时修改的num不会影响到右子树。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct...