mq049.电话号码的字母组合
题目链接
回溯法，自己写了一下非常慢，然后就看了一下题解，和之前的“全排列”那个题的解法几乎一样。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
python:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
d = {
"2":"abc",
"3":"def",
"4":"ghi",
"5":"jkl",
"6":"mno",
...
lc017.电话号码的字母组合
题目链接
回溯法，自己写了一下非常慢，然后就看了一下题解，和之前的“全排列”那个题的解法几乎一样。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
python:
class Solution:
def letterCombinations(self, digits: str):
if not digits:
return []
d = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
...
mq048.最接近原点的K个点
题目链接
本质是一个topK问题，所以也是既能用优先队列/堆来做，也可以用类似于快速排序的方法来做。在第一个方法中我们用python里的heapq来实现，由于python中heapq是小根堆，所以没法直接实现前K小，只能先引入负号使得堆按照坐标平方和的负数来间接完成。具体要说的也不多毕竟原理都明白，说几个点，一个是取负数；一个是用identity这样的方式类似于字典的形式（比截取列表片段更好看？）；用的heappushpop方法，比先push再pop效率高一些，和heapreplace不同的地方在于后者是先pop然后再push新的值进堆。这个算法的时间复杂度是O（NlogK），空间复杂度是O（K）。
第二个方法是快速排序的思路，时间复杂度是O（N），空间复杂度为O（logN）。
...
mq047.搜索二维矩阵II
题目链接
这个也做过好几次了，利用好对角线的特性。这个算法的时间复杂度是O（N+M），空间复杂度是O（1）。
python:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
rownum = len(matrix)
i, j = 0, len(matrix[0])-1
while i < rownum and j >= 0:
if matrix[i][j] > target:
j -= 1
elif ...
mq046.数组中的第K大个最大元素
题目链接
这个做过好几次了，不说了。时间复杂度是O（N），空间复杂度是O（1）。
python:
import random
import heapq
class Solution:
def findKthLargest1(self, nums: List[int], k: int) -> int:
t = len(nums) - k
l, r = 0, len(nums)-1
while True:
index = self.quickSort(nums, l, r)
if index == t:
return nums[index]
...
mq045.合并K个排序链表
题目链接
这个题目上来先尝试了一下顺序合并，就是依次把链表合并但是这样的时间复杂度很高为O（KN^2），其中K是链表的平均长度，N为链表总数。其空间复杂度为O（1）。
所以只能换成分治合并算法，这个算法的时间复杂度是O（NKxlogK），空间复杂度是O（logN）。
然后，还有一种方法是用堆来做，由于需要得到一个升序列表，说明我们需要做一个小顶堆。该算法如3所示，时间复杂度为O(KNxlogK)，空间复杂度为O（NK）。不过这应该不是最正宗的那种利用优先队列的，讲道理应该用优先队列维护一个最长为N的列表，先将所有链表的头部节点加入之后然后依此pop和push相应的链表的下一个节点。
python:
# Definition for singly-linked list.
# ...
lc973.最接近原点的K个点
题目链接
本质是一个topK问题，所以也是既能用优先队列/堆来做，也可以用类似于快速排序的方法来做。在第一个方法中我们用python里的heapq来实现，由于python中heapq是小根堆，所以没法直接实现前K小，只能先引入负号使得堆按照坐标平方和的负数来间接完成。具体要说的也不多毕竟原理都明白，说几个点，一个是取负数；一个是用identity这样的方式类似于字典的形式（比截取列表片段更好看？）；用的heappushpop方法，比先push再pop效率高一些，和heapreplace不同的地方在于后者是先pop然后再push新的值进堆。这个算法的时间复杂度是O（NlogK），空间复杂度是O（K）。
第二个方法是快速排序的思路，时间复杂度是O（N），空间复杂度为O（logN）。
...
lc240.搜索二维矩阵II
题目链接
这个也做过好几次了，利用好对角线的特性。这个算法的时间复杂度是O（N+M），空间复杂度是O（1）。
python:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
rownum = len(matrix)
i, j = 0, len(matrix[0])-1
while i < rownum and j >= 0:
if matrix[i][j] > target:
j -= 1
elif ...
lc023.合并K个排序链表
题目链接
这个题目上来先尝试了一下顺序合并，就是依次把链表合并但是这样的时间复杂度很高为O（KN^2），其中K是链表的平均长度，N为链表总数。其空间复杂度为O（1）。
所以只能换成分治合并算法，这个算法的时间复杂度是O（NKxlogK），空间复杂度是O（logN）。
然后，还有一种方法是用堆来做，由于需要得到一个升序列表，说明我们需要做一个小顶堆。该算法如3所示，时间复杂度为O(KNxlogK)，空间复杂度为O（NK）。不过这应该不是最正宗的那种利用优先队列的，讲道理应该用优先队列维护一个最长为N的列表，先将所有链表的头部节点加入之后然后依此pop和push相应的链表的下一个节点。
python:
# Definition for singly-linked list.
# ...
mq044.另一个树的子树
题目链接
啊这个题如果用暴力做法的话就是枚举s中的节点然后和t的根结点比较，找到后再进行两棵树的遍历去判断是否相等。如1所示，这样做的时间复杂度为O(
s
x
t
)，空间复杂度为O(max{d_s, d_t})，d表示树的深度。
另外一种方法是在DFS序列上做串匹配。我们首先要了解一个小套路：一棵子树上的点在DFS序列（即先序遍历）中是连续的。了解了这个小套路之后，我们可以确定这个问题的方向就是：把s和t先转换成DFS序，然后看t的DFS序是否是s的DFS序的子串。这样做一定正确吗，其实不一定，假设s有两个节点，1是根，2是左孩子，而t也有两个节点，1也是...
260 post articles, 26 pages.