如何用双指针处理接雨水问题？当前柱子能否盛水和桶的高度有关，而桶的高度又由左右两个边界的最少那个决定，因此需要双指针来指向数组的首尾边界。由于柱子能否盛水跟桶的高度有关，所以最短边界的那边才能盛水，因此如果确定了最短边界，就从最短边界那边遍历柱子来确定盛水量，但是如果柱子比边界大就无法盛水了，此时就要更新当前边界，并由当前的两个边界确定新的桶高度，再从新的较低边界那边确定盛水量，如此往复直到两个指针相遇。参考https://blog.nowcoder.net/n/cd5a55084e6143bcbe18b83f1cfd4994?f=commenthttps://blog.nowcoder.ne...

应该使用什么类型的双指针解决此题？容器的容积和最短边长和底边长有关，要求最大的容积，可以用贪心的思想，即让底边长尽可能大，以及左右边长尽可能大。要使左右边长尽可能大，则应该使用对撞指针，即初始时左右指针指向首尾，要使最短边长尽可能大，则左右指针应该是边长小的一边移动，因为贪心思想下较长的一边比较短的一边更可能出现更大容积，移动过程更新最大容积。参考https://blog.nowcoder.net/n/48d8b18532324e60817a9a8db21b376d?f=comment /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * ...

基本思路遍历过程中维护一个无重复的子数组，然后每次遇到重复数字时就重置这个无重复子数组，同时更新目前最大的无重复子数组的长度。可以用双指针构建一个子数组，然后用哈希表保证子数组中没有重复数字，即先为每个不重复的数字构建哈希表，然后遍历过程为每个不重复数字计数，如果计数超过1说明当前数字重复了，需要移动窗口统计下一个不重复子数组。也可以构建一个存放不重复数字的数组，利用数组的includes方法保证该数组的数字不重复，遍历过程往这个数组中存放元素，如果遇到重复数字则将目前数组的内容清空，再以当前数字为起点统计下一个不重复的子数组。参考https://blog.nowcoder.net/n/587...

如何利用滑动窗口寻找最小覆盖子串？利用双指针实现一个滑动窗口，初始时左右指针都指向数组开头，开始寻找时右指针开始移动，直到满足某个条件时停下，此时左右指针构造的滑动窗口就满足了题目条件所需内容。为了进一步达到最小条件要求，需要移动左指针缩小窗口，直到不满足条件时，再移动右指针寻找满足条件的窗口，直到右指针达到数组末尾，每次达到满足条件的窗口时，都更新所要求的最值状态。本题初始时左右指针指向S的字符串开头，右指针移动寻找能够覆盖T字符串中所有字符的窗口，如果找到后，则更新当前窗口为最小覆盖子串，为了得到全局最小覆盖子串，需要再移动左指针缩小窗口使窗口中不能覆盖T字符串中的所有字符，此时右指针再继...

如何使用双指针合并区间？如果两个相邻的区间需要合并，那么此时前一个区间的末尾要大于后一个区间的开头，因此我们可以用一个指针用于遍历区间数组，还有一个指针指向原区间数组中的当前区间的开头，将当前区间的开头和合并区间数组的最后一个区间的末尾比较，来判断当前区间是否需要合并。为了能方便判断相邻区间是否需要合并，需要先对区间数组按每个区间的第一个元素来进行排序。如何使用贪心思想合并区间？贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。最小子问题为两个相邻区间是否能合并，则我们每次判断合并区间数组的最后一...

双指针思想双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。如何将两个有序的数组融合到第一个有序的数组中？由于题目中A已经扩容到可以容纳两个数组元素的容量了，多于的元素用了0作为占位符，所以在融合数组时，应该使用下标进行赋值替换操作，而不是用push来进行插入操作，因此需要第三个指针操作最终A数组的下标。由于要替换扩容后的A中的后面为0的占位符，所以元素比较应该从最后一个元素开始，因此初始的A和B的指针应该指向两者最后...

如何用递归搜索最大路径？最大路径的起点并不知道，因此我们需要遍历矩阵中的每个元素为起点，然后递归寻找这个起点开始的最大路径长度。如何保证路径中的单元格不重复？由于路径的单元格不能重复，我们需要一个dp数组保存矩阵中每个元素为起点的最大路径长度。如果矩阵中的某个单元格没有更新最大路径长度，我们就增加一更新这个单元格的路径长度，表示这个单元格访问过了。后面会再从上下左右四个方向更新这个单元格出发的最大路径长度，而且后面单元格的路径长度也会使用到前面单元格的路径长度来更新。感想此题跟岛屿数量 思路类似，都是用深度优先遍历来搜索二维矩阵中的所有元素来得到最终结果。即先遍历矩阵中的每个元素，然后以这个元...

如何使用递归构造匹配的括号串？初始时一共有n个左括号和n个右括号，递归的逻辑应该体现为使用一个左括号后，只能从剩下的n-1个左括号和n个右括号中继续选择括号构造括号串，因此初始应该是一个空字符串节点，然后逐个往下构造完整的括号串，知道左括号和右括号的数量都用完时表示括号串构造完成。如何保证构造匹配的括号串？要保证左括号的数量多于右括号的数量时，才能添加右括号，这样构造的就是匹配的括号串。参考https://blog.nowcoder.net/n/9ce748d0398e4f69abc39c69bfe68d6f?f=comment /* * @Author: LibraStalker ****...

如何判断皇后是否冲突？用一个pos数组记录每一行已经存放的皇后的列数，即pos的下标为皇后的行坐标，pos的内容是皇后的列坐标，之后每次递归的根据这个pos数组中已经记录的皇后的位置，来判断当前位置是否能摆放皇后，如果能摆放皇后就继续递归判断后面的行数中能摆放皇后的位置，直到达到最大行则回溯。设要摆放的皇后的位置为row,col，当前已记录的皇后的位置为i,pos[i]，则两者是否在同一对角线上可以用abs(row-i) == abs(col-pos[i])判断，是否为同一行用row==i判断，是否为同一列用col==pos[i]判断。参考https://blog.nowcoder.net/n...

深度优先搜索(DFS)深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。如何不重复统计岛屿？为了不重复统计岛屿，可以在遇到1时把相邻的上下左右4个方向都置为0，这个过程是深度优先搜索的，即如果相邻的上下左右四个方向的内容是1，则将其置为0的过程中继续对这个位置的相邻上下左右四个方向的内容置为0终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。返回值： 每...

如何思考剪枝过程？数组中有重复数字会导致出现重复的排列，因为要对原数组循环遍历每个数字来递归获取排列数。要阻止出现重复排列的情况，就要在同一层循环中不使用重复的数字来递归，为了方便判断是否为重复的数字，可以先对数组进行排序，再判断相邻的两个数字是否重复即可。used数组用于判断某个数字是否被使用过，如果被使用过则跳过这个数字避免重复使用。但在重复数字的场景下，如果数字没被使用过还需要判断他是否是跟前一个数字重复，如果重复了也要跳过这个数字。used数组只在递归过程会逐个变true，如果used[i-1]为false说明和当前数字相同的上一个数字在上一次循环中被递归使用了，回溯后当前层为fals...

递归和回溯递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。如何思考递归和回溯？递归过程需要传入...

多个整体状态的DP数组应该保存什么？此题跟打家劫舍（二）的环形房屋都有多状态，环形房屋有两种情况的状态，一个是只选第一个房子不选最后一个房子，一个是只选最后一个房子不选最后一个房子，最后比较这两种状态的DP数组的最大值。由于本题最多只能进行两次股票买卖，因此需要分多个整体状态来分析最大收益值，因此需要一个二维dp数组dp[i][j]，表示第i天股票状态为j的收益，这跟前一天的股票状态有关。一共有五种状态：0表示到第i天为止都从未买过股票的收益，1表示到第i天为止买过一次股票但是没有卖出的收益，2表示到第i天为止买过一次股票也卖过一次的收益，3表示到第i天为止买过两次股票但只卖出一次的收益，4表...

DP数组应该保存什么？题目要求的是根据价格数组买卖股票的最大收益，但是DP数组不能简单的设置成在第i天卖出股票能获得的最大收益（这样类似于贪心的做法，无法依赖于前面的状态）。DP数组应该设置为当天持股dp[i][1]或不持股dp[i][0]所能获得的最大收益，这样当天持股或不持股的收益依赖于前一天持股或不持股的收益，最后一天不持股的收益即为当前能获得的最大收益。最小子问题第一天不持股，收益为0：dp[0][0] = 0第一天持股，即买入当天股票，收益为负的该股票价格：dp[0][1] = -prices[0]如何思考状态转移方程？如果当天不持股，则当天的收益依赖于前一天是否持股的收益最大值，即...