Home

题目链接 我大意了啊，这题很快就知道应该用双指针做，可是我在移动指针的条件的时候一直没有想对，我总是在考虑按照指针所指的旁边那块板的高度来判断是否该移动指针，而正确思路实际上就简单地按照指针所指的那块板来判断即可，因为若左边的板高度小于右边的板的高度，只有先移动左边指针才有可能或者更大的面积（反之不行，因为如果先移动右指针会导致面积严格减小，达不到效果），实现如下所示。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def maxArea(self, height: List[int]) -> int: ans = float("-inf") left, right = 0, len(height...

题目链接 emmm依然按照递归的思路做了一下题，但是为什么时间上只超过了不到百分之10的人啊，难度递归真的太慢了嘛还是因为我重复查找了每一个target啊，感觉应该是因为后者吧。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。嗯再看看别人怎么实现的吧。啊我知道了，因为我没有利用好数组有序的这个特性导致在递归的时候同时递归了两边的区间，而实际上只需要递归左区间或者右区间就可以了，啊我尝试更改实现1感觉如果按照2的思路的话得拆分成两个方法（除非使用targt+1的技巧，但是那样写出来应该就是和实现2把left_func拆分成一个独立的方法而已）。所以按这样看到话，我的思路慢的原因就这样花费了多余的时间去找到了每个和target值相对应的值才求出了左右边界。 class So...

题目链接 嗯第一眼就感觉是二分查找法，然后我就一通乱写，就写完了，时间复杂度是O（logN），空间复杂度是O（1）。不过我这个是递归版本的而且好像并没有利用有序这个特性，所以我就又复制了一版用循环实现的。 class Solution: def search1(self, nums: List[int], target: int) -> int: self.ans = -1 left, right = 0, len(nums)-1 self.find(nums, target, left, right) return self.ans def find(self, nums, target, l...

题目链接 做过一个类似的生成各种不同的排列的题目，如果不是原地返回的话，可以先生成所有排列然后进行排序然后取下一个，我翻出了之前的记录写了一下给定字符生成各个排序的集合。但是这题要求原地返回并且将所有排列全都求出来也非常地浪费时间，因此必须要有一种方法能够直接求出下个排列。对于下个排列，我们有两个发现：一就是我们需要将一个左边的”较小数“与右边的一个”较大数“交换，以能够使当前排列变大，从而得到下一个排列；二就是，我们同时要让这个”较小数“尽量靠右而”较大数“尽可能小。当交换完成后，”较大数“右边的数需要按照升序重新排列，这样才能保证新排列大于原来排列的情况下，变大的幅度尽可能小。 那么如何具体实现上述的思想呢。首先，我们先找“较小数”，我们从后往前寻找第一个顺序对(i, i+1)...

题目链接 啊感觉这个题做过的，然后自己写了一下，倒是过了示例，但是提交之后发现有特殊情况没有考虑，比如说在链表中只有一个元素的时候要删除倒数第一个节点，我的实现就会有问题，然后看了一下两年前提交的答案，发现使用的dummyt节点是在head之前的节点而非我这样将dummy设成head。另外，在这样设置dummy后，在提前走n步时我们要改成提前走n+1步。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self....

题目链接 这题可以用双指针法解决，与两数之和这题类似。难点在于题目要求返回的数组中不含有重复的数对。实现如下，其中带注释的行是有在做跳过重复字符这件事。这个算法的时间复杂度是O（N^2），空间复杂度是O（1）。 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = [] for i in range(len(nums)-2): if nums[i] > 0: break if i > 0 and nums[...

题目链接 我大意了啊，这题很快就知道应该用双指针做，可是我在移动指针的条件的时候一直没有想对，我总是在考虑按照指针所指的旁边那块板的高度来判断是否该移动指针，而正确思路实际上就简单地按照指针所指的那块板来判断即可，因为若左边的板高度小于右边的板的高度，只有先移动左边指针才有可能或者更大的面积（反之不行，因为如果先移动右指针会导致面积严格减小，达不到效果），实现如下所示。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def maxArea(self, height: List[int]) -> int: ans = float("-inf") left, right = 0, len(height...

题目链接 啊我看到题的第一反应就是使用归并的方式（参考lc088），可是归并的方式时间复杂度为O（M+N），不满足题意的O(log(M+N))，注意到时间复杂度里有log存在，我们可以考虑用二分查找法。在这之前，我们讲一下暴力求解法，即先将两个数组合并然后用排序算法排序后取出中位数，这种算法的时间复杂度一般为O((M+N)log(M+N))，这个时间复杂度过大，是因为其没有利用原先两个数组是有序的这一特性。 现在考虑二分查找法，首先，我们考虑只有一个有序数组的情况，我们可以用一条线将数组划分成两部分，在数组元素总数为偶数的情况下，线的两侧分别为求中位数要用到的两个数字，在数组元素总数为奇数的情况下，线可以划分在中间偏右侧的位置，也就是左半部分刚好比右半部分多一个元素并且这个靠近线的...

题目链接 这种题就是典型的使用双指针法或者说滑动窗口法解决的题目，稍微看了一下别人的思路然后自己写了一下，写得有点丑陋感觉。首先，我们用defaultdict基于t初始化需要被包含的字符这样可以在遍历s中的字符时检查哪个字符还需要或者哪个字符已经多余了。这个defaultdict中t中包含的字符的个数都随着遍历慢慢减为1时我们知道滑动的窗口就包含所有t中的字符了，我们可以遍历一遍defaultdict来判断。但是这样遍历造成了浪费，因此我们可以用一个all_chars来记录，每被包含进一个t中的字符我们就将all_chars减1，当all_chars为0时说明所有t中的字符都被包含进去了。但此时，我们只是求出了一对滑动窗口的左右边界，为了找到最小的窗口长度，我们要收缩左边界即向左移动...

题目链接 这一题，最直观的思路就是，遍历height里的每一个位置然后找出该位置左边区间的最大值与该位置右边区间的最大值，得到两个最大值后用两个最小值中的较小值减去该位置的高度，得到了在该位置上能够积累的雨水。这种直观思路的暴力实现如1所示。这个实现的时间复杂度是O（N^2），空间复杂度是O（1）。这个实现的时间复杂度过高原因是在求左右两边的最大值时重复访问了各个元素多次，因此我们能够想到用动态规划的方法将时间复杂度降低。这种思路首先将数组从左往右遍历一次求出每个位置左边的最大值以及从右往左遍历一次求出每个位置右边的最大值，再利用这两个最大值数组求出每个位置的积水量。这个实现见2，时间复杂度与空间复杂度都是O（N）。 另外一种方法，是用单调递减栈来解决的，如实现3所示，我们在遍历h...