Home

题目链接 啊这个题之前有看见过不过那个时候还是很早的时候没什么思路，然后就看了一眼别人的思路，原来就是一个状态空间搜索而已，就用递归写出来了，虽然感觉好像写得没有别人的简洁（见实现2）。这个算法的时间复杂度是O（N），空间复杂度是O（1）（我也不知道多少，如果考虑是在原先的grid上更改的话应该是O（1））。 class Solution: def numIslands1(self, grid: List[List[str]]) -> int: self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] self.grid = grid cnt = 0 self.lrow...

题目链接 啊这个题之前有看见过不过那个时候还是很早的时候没什么思路，然后就看了一眼别人的思路，原来就是一个状态空间搜索而已，就用递归写出来了，虽然感觉好像写得没有别人的简洁（见实现2）。用深度优先遍历的时间复杂度是O（MN），空间复杂度是O（MN）（我也不知道多少，如果考虑是在原先的grid上更改的话应该是O（1）？）。当然，更自然的，我们也可以使用广度优先遍历算法，如实现3所示，广度优先遍历的时间复杂度为O（MN），空间复杂度O(min(M,N))，在最欢情况下，整个网格均为陆地，队列的大小可以达到min(M,N)。 最近发现自己不太会做并查集相关的题目，在复习，然后来写一下关于这个题的新做法，即用并查集代替搜索。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则...

题目链接 嗯嗯，第一眼看见这个题目感觉是用循环顺序表或者队列和哈希表来实现，可是尝试了之后发现一个问题，就是题目中的get操作也会使得某个值被操作从而改变其在顺序表/队列中的位置，这会导致每次get操作时都要按顺序将后半部分的元素往前位移之类的操作，从而时间复杂度为O（N）与题意不符合。所以我就考虑应该用链表加哈希表来实现，不过由于不太熟练就直接看了别人的解答，这题可以使用python里已有的结合了双向链表和哈希表的数据结构如OrderedDict（见实现2），当然这样就和题意不符了。所以这题需要自己将双向链表写出来（见实现1），这个实现的各项操作中，访问哈希表的时间复杂度为O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为O(1)。而将一个节点移到双向链表的头...

题目链接 这种题就是典型的使用双指针法或者说滑动窗口法解决的题目，稍微看了一下别人的思路然后自己写了一下，写得有点丑陋感觉。首先，我们用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...

题目链接 嗯嗯，第一眼看见这个题目感觉是用循环顺序表或者队列和哈希表来实现，可是尝试了之后发现一个问题，就是题目中的get操作也会使得某个值被操作从而改变其在顺序表/队列中的位置，这会导致每次get操作时都要按顺序将后半部分的元素往前位移之类的操作，从而时间复杂度为O（N）与题意不符合。所以我就考虑应该用链表加哈希表来实现，不过由于不太熟练就直接看了别人的解答，这题可以使用python里已有的结合了双向链表和哈希表的数据结构如OrderedDict（见实现2），当然这样就和题意不符了。所以这题需要自己将双向链表写出来（见实现1），这个实现的各项操作中，访问哈希表的时间复杂度为O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为O(1)。而将一个节点移到双向链表的头...

题目链接 此题与lc138相同。第一个算法的时间复杂度是O（N），空间复杂度是O（N）。第二个算法的时间复杂度为O（N），空间复杂度为O（1）。 """ # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList1(self, head: 'Node') -> 'Nod...

题目链接 此题与lc102一样。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] res, st...

题目链接这个题可以用双指针法，如下所示，这个算法的时间复杂度是O（N），空间复杂度是O（N）。我们完全可以在原字符串上进行判断从而优化空间复杂度，使其减小为O（1）。 class Solution: def isPalindrome1(self, s: str) -> bool: sp = "".join(ch.lower() for ch in s if ch.isalnum()) i, j = 0, len(sp)-1 while i < j: if sp[i].lower() != sp[j].lower(): return False ...

题目链接，这个题用一维dp就很好解决，算法的时间复杂度是O（N），空间复杂度是O（N），可以被优化成O（1）。 class Solution: def maxProfit1(self, prices: List[int]) -> int: if not prices: return 0 res = [0]*len(prices) pre_min = prices[0] res[0] = 0 for i in range(1, len(prices)): if prices[i] < pre_min: pre...