心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #盛水最多的容器#

应该使用什么类型的双指针解决此题？容器的容积和最短边长和底边长有关，要求最大的容积，可以用贪心的思想，即让底边长尽可能大，以及左右边长尽可能大。要使左右边长尽可能大，则应该使用对撞指针，即初始时左右指针指向首尾，要使最短边长尽可能大，则左右指针应该是边长小的一边移动，因为贪心思想下较长的一边比较短的...

2023-04-27

0 197

题解 | #最长无重复子数组#

基本思路遍历过程中维护一个无重复的子数组，然后每次遇到重复数字时就重置这个无重复子数组，同时更新目前最大的无重复子数组的长度。可以用双指针构建一个子数组，然后用哈希表保证子数组中没有重复数字，即先为每个不重复的数字构建哈希表，然后遍历过程为每个不重复数字计数，如果计数超过1说明当前数字重复了，需要移...

2023-04-27

0 324

题解 | #最小覆盖子串#

如何利用滑动窗口寻找最小覆盖子串？利用双指针实现一个滑动窗口，初始时左右指针都指向数组开头，开始寻找时右指针开始移动，直到满足某个条件时停下，此时左右指针构造的滑动窗口就满足了题目条件所需内容。为了进一步达到最小条件要求，需要移动左指针缩小窗口，直到不满足条件时，再移动右指针寻找满足条件的窗口，直到...

2023-04-25

0 339

题解 | #合并区间#

如何使用双指针合并区间？如果两个相邻的区间需要合并，那么此时前一个区间的末尾要大于后一个区间的开头，因此我们可以用一个指针用于遍历区间数组，还有一个指针指向原区间数组中的当前区间的开头，将当前区间的开头和合并区间数组的最后一个区间的末尾比较，来判断当前区间是否需要合并。为了能方便判断相邻区间是否需要...

2023-04-24

0 309

题解 | #合并两个有序的数组#

双指针思想双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。如何将两个有序的数组融合到第一个有序的数组中？由于题目中A已经...

2023-04-23

0 257

题解 | #矩阵最长递增路径#

如何用递归搜索最大路径？最大路径的起点并不知道，因此我们需要遍历矩阵中的每个元素为起点，然后递归寻找这个起点开始的最大路径长度。如何保证路径中的单元格不重复？由于路径的单元格不能重复，我们需要一个dp数组保存矩阵中每个元素为起点的最大路径长度。如果矩阵中的某个单元格没有更新最大路径长度，我们就增加一...

2023-04-21

0 320

题解 | #括号生成#

如何使用递归构造匹配的括号串？初始时一共有n个左括号和n个右括号，递归的逻辑应该体现为使用一个左括号后，只能从剩下的n-1个左括号和n个右括号中继续选择括号构造括号串，因此初始应该是一个空字符串节点，然后逐个往下构造完整的括号串，知道左括号和右括号的数量都用完时表示括号串构造完成。如何保证构造匹配的...

2023-04-20

0 294

题解 | #N皇后问题#

如何判断皇后是否冲突？用一个pos数组记录每一行已经存放的皇后的列数，即pos的下标为皇后的行坐标，pos的内容是皇后的列坐标，之后每次递归的根据这个pos数组中已经记录的皇后的位置，来判断当前位置是否能摆放皇后，如果能摆放皇后就继续递归判断后面的行数中能摆放皇后的位置，直到达到最大行则回溯。设要摆...

2023-04-20

0 280

题解 | #岛屿数量#

深度优先搜索(DFS)深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。如何不重复统计岛屿？为了不重复统计岛屿，可以在遇到1时把相邻的上下...

2023-04-20

0 247

题解 | #有重复项数字的全排列#

如何思考剪枝过程？数组中有重复数字会导致出现重复的排列，因为要对原数组循环遍历每个数字来递归获取排列数。要阻止出现重复排列的情况，就要在同一层循环中不使用重复的数字来递归，为了方便判断是否为重复的数字，可以先对数组进行排序，再判断相邻的两个数字是否重复即可。used数组用于判断某个数字是否被使用过，...

2023-04-20

0 412