4. 寻找两个正序数组的中位数

题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/我的思路这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。题解官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这

二分法 · 06-04

154. 寻找旋转排序数组中的最小值 II

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/我的思路基本上是延续153题的思路，但和153题不一样的是，这题中可能会有重复的相同元素出现，因此需要多加思考。考虑到的可能情况为：[3,3,1,3], [10,1,10,10,10]，nums[mid] >或< nums[r]的情况比较好解决，和153中的思路一样，但当二者相等时，要如何处理呢？一开始只想到了笨方法，有灵光一现想到只要考虑右边即可（因为原数组已经是按非递减顺序排好），但没有抓住这个思路继续想下去，而是继续尝试笨方法：分情况讨论。数值相同的情况可能有几种，比如[3,3,1,3]，l在0处，r在3处，mid = 1，以及[10,1,10,10,10]，l在0处，r在4处，mid = 2，那很自然想到说要判断一下mid前后的数值情况，如果nums[mid - 1] == nums[mid]，那就从左边缩短区间，l = mid + 1，如果nums[mid + 1] == nums[mid]，那

二分法 · 05-14

153. 寻找旋转排序数组中的最小值

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/我的思路经历了第34题的摧残后，这道题显得没有那么难了，拿到题目读了一下题意和要求后稍微调整了一下解法就顺利通过了，结果表现也还不错。但还是把这题记录下来，是其中有一个地方和34中不太一样，就是当nums[mid]<nums[r]时，应该将mid直接赋给r，而不是mid-1，解释：因为在这里我们要找到的时最小值，nums[mid]<nums[r]可能会存在于下面的情况：…18…3,1,2…9…，此时l位于18处，r位于9处，mid指向1，而1的前面是3，1就是我们要找的最小值了，因此不能把此时mid这个位置的元素给排除掉（我们之前mid-1就是因为从mid起，包括mid在内的右边部分全部没用了，所以才这么赋值），此时mid指向的位置就是r的最小值了，区间不能再从右边往里面缩了，之后的判断操作也只能从左边开始缩区间结果0ms 100%, 17.63MB 94.39%

二分法 · 05-08

34. 在排序数组中查找元素的第一个和最后一个位置

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/我的思路大前提：序列已经按非递减顺序排列好。题目要求时间复杂度只能为$O(\log n)$，因此不能用简单的指针法（那样的复杂度为n），只能用二分法来求解。用两次二分法，第一次找第一个出现的位置，第二次找最后一个出现的位置，二分法的时间复杂度本身就为$O(\log n)$，用两次加起来$O(\log n)+O(\log n)$也仍然是$O(\log n)$target出现位置肯定满足条件nums[mid] == target，但也需要进一步判断：第一次出现位置：mid == 0 or nums[mid - 1] < target （有可能回到了列表起点），如果都不符合，那说明nums[mid - 1] = target（这个时候不可能是>target了，否则和先决条件nums[mid] == target以及非递减序列的大前提矛盾），意味着此时的mid还不够靠左，要把mid

二分法 · 05-06

69. x的平方根 

题目链接：https://leetcode.cn/problems/sqrtx/description/我的思路明显的用二分法的问题，根据教材提示，已知输入为$x$，问题可转化为求$f(y)=y^2-x$的零点问题，可得$f(0)=0-x=-x<0, f(x)=x^2-x>0$，于是我们可以把初始区间定为$[0,x]$，然后开始二分。回顾一下二分的核心思想，不断缩短考察的区间，二分二分，顾名思义要取中间值$mid=(0+x)/2$，之后再判断$f(mid)$是大于0还是小于0，如果大于0，即$mid^2>x$，那就把区间设置为$[0,mid]$，如果小于0，即$mid^2<x$，那就把区间设置为$[mid,x]$，接着继续取新的二分中间值$mid_1=(l+r)/2$，这里的l和r分别代表了区间的左右边界值但是，卡在了这里，一开始只要找到了$mid^2<x$的值，就把mid作为结果返回，但后来发现这样不对，就不知道该怎么确定结果值了。这样的思路会让程序陷入死循环，或者直接返回更小的那个符合题意得值（比如x=6，二分会让程序跳到1，返回1，但应该是2），问题

二分法 · 05-03

524. 通过删除字母匹配到字典里最长单词

题目链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/description/我的思路也是一开始就想到了用双指针，并且根据指导书中写的，这道题是归并两个有序数组的变式，那自然想到一个指针p放在字符串s，一个指针q放在单词word中，依次遍历。思路为：初始化一个结果变量ans=’’以及last_p=len(s)用于判断实现“字母序最小”的要求（比如s="abce", dictionary=["abe","abc"]时应该输出abc而非abe，一开始理解的是c在s中更靠前，所以abc是字母序更小的单词）首先固定q，p移动，判断word[q]是否等于s[p]，如果相等，则p,q同时右移1位，如果不相等，则只移动p，重复该步骤直到遍历完word，即q==len(word)-1，结束该单词的循环，判断len(word)是否>len(ans)，同时判断此时p值是否小于last_p，如果小于，意味着这个答案在s中的次序更靠前，更小，满足题意在同时满足上面三个条件的情况下，则将word赋值给an

双指针 · 04-20

680. 验证回文串 II

题目链接：https://leetcode.cn/problems/valid-palindrome-ii/description/我的思路在这道题上卡了巨久，虽然只是一道标记为简单级别的题，但评论也说了，能比得上中等。亲身尝试后发现确实如此，有很多坑在里面，顺利解答出来也需要一些巧思。我一开始的思路：想到了用双指针，但不知道该从何下手，一开始走入了一个误区（可能是受之前题目的影响，没有仔细看清楚题意），就是尝试修改原字符串，把不一样的赋值成一样的，然后再继续做判断，但是忽略了题目中的要求：最多可以删除一个字符，因此还是要尝试其他的办法想了一下后的思路是：找到那个不对称的位置，然后尝试把这个元素去掉，再判断生下来的字符串是否满足回文，想到了会有一些特殊情况，比如是要去掉左边的元素（例如cd…d，此时应该删掉左边的c），还是去掉右边的元素（例如c…cd，此时应该删掉右边的d），同时还可能只有三个元素（例如abc，或者aba），最多允许删除一个元素……于是就开始了尝试枚举考虑所有可能的特殊情况，删除左边还是右边元素的条件是判断s[left]和s[right]与他们相邻元素是否相同：当出现s

双指针 · 04-15

633. 平方数之和

题目链接：https://leetcode.cn/problems/sum-of-square-numbers/description/我的思路知道要用双指针法，但也还是被题目给吓到了，给的c的范围是0到2的31次方-1，感觉从0开始遍历的话复杂度太高了。一开始想着遍历范围是从0到c/2，但感觉这样还是太大。也想过范围为0到根号c，但以为leetcode无法引入其他的库来执行均方根操作，所以一直卡在这，遂去看题解了。纠正枚举法：枚举a=0,1,2,…，把式子变成$b=\sqrt{(c-a^2)}$，只要b是整数的话，就返回True，但a能一直枚举下去吗？不可以，如果枚举到$2a^2>c$的话，仍没有找到合适的b，就停止，证明：此时$a^2>c-a^2$，假如继续枚举能找到符合等式的a和b，比如a=5, b=3，那么之前在枚举到a=3时，也能发现a=3, b=5符合等式，矛盾。所以当枚举到$2a^2>c$时，后面不可能找到符合等式的a和b。双指针法：同样也需要明确指针的活动范围，应该是0到$int(\sqrt c)$，把左指针放到0，右指针放到$int(\sqrt c)

双指针 · 04-08