lc297.二叉树的序列化与反序列化
题目链接
此题与jz037.序列化二叉树相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: Tre...
jz039.数组中出现次数超过一半的数字
题目链接
哇看到第一眼就是用哈希表，随手写了一下，没想到有更快的另外两种方法，先写一部分吧，今天不想写了哈哈哈。那第一个方法就不用说了吧。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
第二个思路也很简单，就是先把数组拍序，中位数必定是所求的数。因为出现次数多于一半的话，连续相同的这个数必定跨度大于数组的一半。这个算法的时间复杂度为O（NlogN）。
第三个思路是用快速排序来做，这个等弄完排序专题再来补充。
还有另外一个方法，叫做摩尔投票法，这个算法首先用一个votes来记录票数和，并且规定记众数的票数为+1，非众数的票数为-1，那么由于众数的数量大于总数的一半，故对于整个数组来说，最后的votes值肯定大于0。还有一个特性，当从前往后遍历数组时，若前a个数的votes...
jz037.序列化二叉树
题目链接
如果做过jz007.重建二叉树的话，我们知道可以从前序遍历序列和中序遍历序列中构造出一棵二叉树。受此启发，我们可以先把一棵二叉树序列化成一个前序遍历序列和一个中序遍历序列，然后在反序列化时通过这两个序列重构出二叉树。这种思路有两个缺点：一是该法要求二叉树中不能有数值重复的节点；二是只有当两个序列中所有的数据都读出后才能开始反序列化。如果两个遍历序列的数据是从一个数据流中读出来的，那么可能需要等待较长的时间。
实际上，如果二叉树的序列化是从根节点开始的，那么相应的反序列化在根节点的数值读出来的时候就可以开始了。因此，我们可以根据前序遍历的顺序来序列化二叉树，因为前序遍历是从根节点开始的。在遍历二叉树碰到空节点时，这些空节点化为一个特殊的字符，如“$”。接着，在反序列化的时候...
lc072.编辑距离
题目链接
这个题目我上课学过了等以后有心情再写吧，就是很典型的动态规划算法而已。这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。其中M，N分别为两个词的长度。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
lw1, lw2 = len(word1), len(word2)
m = [[0] * (lw1+1) for _ in range(lw2+1)]
for i in range(lw1+1):
m[0][i] = i
for i in range(lw2+1):
...
lc426.将二叉搜索树转化为排序的双向列表
题目链接
此题与jz036.二叉搜索树与双向列表相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return
...
lc138.复制带随机指针的列表
题目链接
此题与jz035.复杂链表的复制相同，在这里就放一下最优的代码。这个算法的时间复杂度是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 copyRandomList(self, head: 'Node') -> 'Node':
...
jz036.二叉搜索树与双向列表
题目链接
在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点。当遍历根节点的时候我们把树看成3部分：根节点，左子树和右子树。根据排序链表的定义，根节点将和它的左子树的最大的一个节点连接起来，同时还和右子树中最小的节点链接起来。而对于各个子树，过程是类似的，所以我们很容易就能想到用递归或者说分治算法。另外，我们还需要注意将双向链表的两端连接起来。这个算法的时间复杂度是O（N）,N为二叉树的节点数，中序遍历需要访问所有节点。;空间复杂度是O...
jz035.复杂链表的复制
题目链接
这个题，有一种思路是将此复杂链表看成一个图，图的基本单位是顶点，顶点之间的关联关系为边。由于图的遍历方式有深度优先搜索和广度优先搜索，同样地，对于此链表也可以使用深度优先搜索与广度优先搜索两种方式进行遍历。算法1中展示的就是用dfs解答。首先从头节点开始拷贝，使用递归拷贝所有的next节点，再递归拷贝所有的random节点。在拷贝每个节点的时候，有两种情况，一是如果某个节点没有被拷贝，则创建一个新的节点进行拷贝，并将拷贝过的节点保存在哈希表中；另一种情况是，如果某个节点已经被拷贝过了，则不需要被重复拷贝。这个算法的时间复杂度是O（N），空间复杂度是O（N）。至于用bfs遍历图的算法我就没有记录，主要是因为懒。
还有一种更加优化的算法如2，在不用辅助空间的情况下实现O（N）...
lc113.路径总和II
题目链接
此题与jz034.二叉树中和为某一值的路径相同，这个算法的时间复杂度是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 pathSum(self, root: TreeNode, tar: int) -> List[List[int]]:
stack, res = [], []
d...
jz034.二叉树中和为某一值的路径
题目链接
由于路径是从根节点到叶节点的，因此我们需要先遍历根节点。在树的前序、中序、后序3种遍历方式中，只有前序遍历是首先访问根节点的。按照前序遍历的顺序遍历一个二叉树，在访问根节点后，会访问左子节点，并且我们知道在本题的二叉树节点中没有指向根节点的指针，所以当访问左子节点时我们不知道之前经过了什么节点，除非我们把经过的路径上的节点都保存下来。每访问一个节点，我们都把当前节点添加到路径中去。继续遍历，当遇到叶节点时将路径上的节点值的和与目标值相比较，若路径上节点值的和与目标值不等，则先将叶节点弹出路径列表，若遍历到某个叶节点时路径上的节点值和为目标值，则记录该路径。以此类推遍历整个二叉树。我们不难看出保存路径的数据结构实际上是一个栈。代码如下。自己一遍几乎没错写下来了（除了完了考虑空...
260 post articles, 26 pages.