0%

此文为链表的学习笔记。

1. 概述

与数组相似,链表也是一种线性的数据结构,下图为单链表的例子:

链表中的每一个元素实际上是一个单独的对象,而对象之间的链接,则是每个元素中的引用字段构造的。

链表有两种类型:单链表双链表,下图为双链表的例子:

2. 单链表

单链表中的每个结点不仅包括,还包括链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来。

如上图中的蓝色箭头则为链接结点的组合方式。

在大多数情况下,我们将使用头结点(第一个结点)来表示整个列表。

2.1. 与数组的不同处

与数组不同,我们无法在常量时间内访问单链表中的随机元素

如果我们想获得第i个元素,我们必须从头结点逐个遍历。我们按照索引访问元素平均花费O(N)时间,其中N为链表的长度。

所以,在通过索引访问数据时(与数组相比),性能不好。但是在操作和删除操作时,有链表的好处。

2.2. 单链表的添加操作

如果我们想在给定的结点prev之后添加新值,我们应该:

  • 使用给定值初始化新结点cur

  • 将cur的next字段链接到prev的下一结点next

  • 将prev中的next字段链接到cur

数组不同,我们不需要将元素移动到插入元素后。所以,我们可以在O(1)的时间复杂度将新结点插入到链表中,十分高效。

2.2.1. Python 实现(力扣自代的链表定义)

2.2.1.1. 单链表添加

比如我们想在第二个结点6后插入一个新的值9。

我们首先初始化一个值为9的新结点,将结点9链接到结点15,最后将结点6链接到结点9。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next

# print(head)
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
cur = ListNode(9)
cur.next = head.next.next
head.next.next = cur
# print(head)
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 9, next: ListNode{val: 15, next: None}}}}

插入后的链表:

2.2.1.2. 单链表在开头添加结点

在链表中,我们使用头结点来表示整个列表。

  • 初始化一个新结点cur

  • 将新结点链接到我们的原始头结点

  • 将cur指定为head

例如,让我们在列表的开头添加一个新结点9。

  1. 我们初始化一个新结点9并将其链接到当前头结点23。
  1. 指定结点9为新的头结点。
1
2
3
4
5
6
7
# print(head) 
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
cur = ListNode(9)
cur.next = head
head = cur
# print(head)
# ListNode{val: 9, next: ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}}

2.2.1.3. 单链表在末尾添加结点

[23,6,15][23,6,15,9]

1
2
3
4
5
6
7
8
9
10
# print(head) 
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
cur = ListNode(9)
dum = head
while head.next:
head = head.next
head.next = cur
head = dum
# print(head)
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: ListNode{val: 9, next: None}}}}

2.3. 单链表的删除操作

2.3.0.1. 删除单链表中的一个结点

如果我们想从单链表中删除现有结点cur,可以分两步完成

  • 找到cur的上一个结点prev及其下一个结点next
  • 接下来链接prev到cur的下一个节点next

在第一步中,我们需要找出prevnext,使用cur的参考字段很容易找出next,但是我们必须从头结点遍历链表以找出prev,它的平均时间是O(N),其中N是链表的长度。因此,删除结点的时间复杂度将是O(N)

示例:

尝试把结点6从链表中删去:

  • 从头遍历链表,直到我们找到前一个结点prev即结点23

  • prev(结点23)与next(结点15)链接

另外一个更清晰的解释:

参考:18.删除链表的节点

  • 特例处理: 当应删除头节点 head 时,直接返回 head.next 即可。
  • 初始化: pre = head , cur = head.next 。
  • 定位节点: 当 cur 为空 或 cur 节点值等于 val 时跳出。
  • 保存当前节点索引,即 pre = cur 。
  • 遍历下一节点,即 cur = cur.next 。
  • 删除节点: 若 cur 指向某节点,则执行 pre.next = cur.next ;若 cur 指向 nullnull ,代表链表中不包含值为 val 的节点。
  • 返回值: 返回链表头部节点 head 即可。
1
2
3
4
5
6
7
8
9
10
11
# print(head)
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
if head.val == val:
return head.next
pre, cur = head, head.next
while cur and cur.val != val:
pre, cur = cur, cur.next
if cur:
pre.next = cur.next
return head
# ListNode{val: 23, next: ListNode{val: 15, next: None}}

2.3.0.2. 删除链表头结点

1
2
3
4
5
# print(head)
# ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
if head.val == val:
return head.next
# ListNode{ListNode{val: 6, next: ListNode{val: 15, next: None}}

2.3.0.3. 删除最后一个结点

1
2
3
4
5
6
7
# head = ListNode{val: 23, next: ListNode{val: 6, next: ListNode{val: 15, next: None}}}
dummy = pre = head
while pre.next.next:
pre = pre.next
pre.next = None
return dummy
# dummy = ListNode{val: 23, next: ListNode{val: 6, next: None}}

3. 单链表中的快慢指针技巧

链表题目中,有两种使用双指针的情景

  • 两个指针从不同位置出发:一个从始端开始,一个从末端开始
  • 两个指针以不同速度移动:一个指针快些,一个指针慢些

但对于单链表来说,我们只能在一个方向上遍历链表,所以第一种场景无法实现。第二种情况,也称为快慢指针,是非常有用的。

3.1. 题目1: 环形链表

LeetCode原题141.环形链表

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:
你能用 O(1)(即,常量)内存解决此问题吗?

示例1:

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例2:

1
2
3
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例3:

1
2
3
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个 有效索引。

3.1.1. 解法1: set集合遍历链表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return None

s = set()
node = head

while (node):
if node in s:
return True
else:
s.add(node)
node = node.next

return False

3.1.2. 解法2: 双指针法(龟兔赛跑)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return None

fastnode = head
slownode = head

while (fastnode):
if fastnode.next and fastnode.next.next:
fastnode = fastnode.next.next
slownode = slownode.next
else:
return False

if fastnode == slownode:
return True

return False

3.1.3. 解法3: 哈希表(字典)法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
m = dict()
while head:
if m.get(head):
return True
else:
m[head] = 1
head = head.next
return False

3.1.4. 解法4: 链表计数法(牛逼)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""

count = 0
while head and count <= 10000:
count += 1
head = head.next
return count>10000

3.2. 题目2: 环形链表2

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:
你是否可以使用 O(1) 空间解决此题?

示例1:

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例2:

1
2
3
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例3:

1
2
3
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

3.2.1. 解法

环形链表这道题不同之处在于,前者只需要判断链表是否有环,现在需要判断环的入口在哪里。

参考:代码随想录

Ps这个解释的数学推导无比清晰,视频也无比优秀

假设从头结点到环形入口结点的结数为x, 环形入口到fast/slow指针相遇的结点结数为y,从相遇结点到环形入欧结点结数为z,如图所示:

那么相遇时

slow指针走过的结点数为:x + y

fast指针走过的结点数为:x + y + n(y+z), 其中n为fast指针在环内走了n圈才遇到slow指针,(y + z) 为一圈内结点的个数

fast指针一步走两个结点,slow指针一步走一个结点,所以fast指针走过的结点数 = 2 * slow指针走过的结点数

(x + y) * 2 = x + y + n (y + z)

两边消掉一个(x+y): x + y = n (y + z)

因为我们要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。

所以我们要求x ,将x单独放在左面:x = n (y + z) - y

在从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针

这个公式说明什么呢,

先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。

当 n为1的时候,公式就化解为 x = z

这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点

也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。

让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。

那么 n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点。

在参考链接里的动画解释很好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 如果相遇
if slow == fast:
p = head
q = slow
while p!=q:
p = p.next
q = q.next
#你也可以return q
return p

return None

3.3. 题目3: 相交链表

160.相交链表

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

示例1:

1
2
3
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例2:

1
2
3
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例3:

1
2
3
4
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

3.3.1. 解法

参考:派派

分别为链表A和链表B设置指针A和指针B,然后开始遍历链表,如果遍历完当前链表,则将指针指向另外一个链表的头部继续遍历,直至两个指针相遇。
最终两个指针分别走过的路径为:
指针A :a+c+b
指针B :b+c+a
明显 a+c+b = b+c+a,因而如果两个链表相交,则指针A和指针B必定在相交结点相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""

if not headA or not headB:
return None

nodeA, nodeB = headA, headB

while (nodeA != nodeB):
nodeA = nodeA.next if nodeA else headB
nodeB = nodeB.next if nodeB else headA

return nodeA

3.4. 题目4: 删除链表的倒数第N个结点

19.删除链表的倒数第N个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

示例1:

1
2
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例2:

1
2
输入:head = [1], n = 1
输出:[]

示例2:

1
2
输入:head = [1,2], n = 1
输出:[1]

3.4.1. 解法:

参考:派派

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
if not head:
return head

slownode = ListNode(0)
slownode.next = head

fastnode = slownode

for i in range(n):
fastnode = fastnode.next

while fastnode.next != None:
slownode = slownode.next
fastnode = fastnode.next

if slownode.next == head:
head = head.next
else:
slownode.next = slownode.next.next

return head

LeetCode每日一题(2021.03.18)之反转链表2

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例1:

1
2
输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例2:

1
2
输入:head = [5], left = 1, right = 1
输出:[5]

提示

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶
你可以使用一趟扫描完成反转吗?

0.0.1. 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseBetween(self, head, left, right):
"""
:type head: ListNode
:type left: int
:type right: int
:rtype: ListNode
"""
count = 1

dummy = ListNode(0)
dummy.next = head

pre = dummy

while pre.next and count < left:
pre = pre.next
count += 1

cur = pre.next
tail = cur

while cur and count <= right:
nxt = cur.next
cur.next = pre.next
pre.next = cur
tail.next = nxt
cur = nxt
count += 1
return dummy.next

LeetCode每日一题(2021.03.15)之螺旋矩阵
难度:中等

0.0.1. 题目

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例1:

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例2:

1
2
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

0.0.2. 解法1

负雪明烛

0.0.2.1. 思路

打印矩阵类似的题目中,要考虑以下几个问题:

  • 起始位置
  • 移动方向
  • 边界
  • 结束条件
0.0.2.1.1. 起始位置

螺旋矩阵的遍历起始于矩阵的左上角(0,0)

0.0.2.1.2. 移动方向

起始位置的下一个移动方向是向右。在遍历的过程中,移动的方向是固定的:

移动的方向按照上面的顺序进行,每次移动到了边界,才会更改方向,但边界并不是固定的

0.0.2.1.3. 边界

本题中,边界随着遍历的过程而改变,已经遍历过的位置不再遍历,边界会越来越小。

规则是:如果当前行(列)遍历结束后,就把这一行(列)的边界向内移动一格。

以下面的图为例,up, down, left, right 分别表示四个方向的边界,初始时分别指向矩阵的四个边界。如果我们把第一行遍历结束(遍历到了右边界),此时需要修改新的移动方向为向下、并且把上边界 up 下移一格,即从旧up 位置移动到 新up 位置。

当绕了一圈后,从下向上走到 新up 边界的时候,此时需要修改新的移动方向为向右、并且把左边界 left 下移一格,即从 旧left 位置移动到 新left 位置。

0.0.2.1.4. 结束条件

螺旋遍历的结束条件是所有的位置都被遍历到。

0.0.2.2. 代码

  • up, down, left, right 分别表示四个方向的边界
  • x,y 表示当前位置
  • dirs 表示移动的方向是右,下,左,上
  • cur_d 表示当前的移动方向的下标,dirs[cur_d] 就是下一个方向需要怎么修改 x, y。
  • cur\_d == 0 and y == right 表示当前的移动方向是向右,并且到达了右边界,此时将移动方向更改为向下,并且上边界 up 向下移动一格。
  • 结束条件是结果数组 res 的元素个数能与 matrix 中的元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
# 排除边界条件
if not matrix or not matrix[0]: return []
M, N = len(matrix), len(matrix[0]) # M => 行数, N => 列数

#定义四个方向的边界
left, right, up, down = 0, N-1, 0, M-1
#定义当前位置
x, y = 0, 0
#定义四个移动方向 [右,下,左,上]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

res = []
cur_d = 0

#当res里的数量不等于M*N时
while len(res) != M * N:
res.append(matrix[x][y])
if cur_d == 0 and y == right:
cur_d += 1
up += 1
elif cur_d == 1 and x == down:
cur_d += 1
right -= 1
elif cur_d == 2 and y == left:
cur_d += 1
down -= 1
elif cur_d == 3 and x == up:
cur_d += 1
left += 1
cur_d %= 4
x += dirs[cur_d][0]
y += dirs[cur_d][1]
return res

0.0.3. 解法2 (利用zip函数)

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
res = []
while matrix:
res += matrix.pop(0) #每次提取第一排元素
matrix = list(zip(*matrix))[::-1] #将剩余的元素进行逆时针旋转九十度
return res

更喜欢第二种解法 :)

LeetCode每日一题系列(2021.03.12)之验证二叉树的前序序列化
难度:中等

0.0.1. 题目

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如#

1
2
3
4
5
6
7
     _9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #

例如,上面的二叉树可以被序列化为字符串"9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。

给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。

你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 “1,,3” 。

示例 1:

1
2
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

1
2
输入: "1,#"
输出: false

示例 3:

1
2
输入: "9,#,#,1"
输出: false

0.0.2. 解法

还是参考负雪明烛大神的两种解法。

我做了好长时间这道题,一直卡在了一种case上:
当char已经遍历完,最后三个字符刚好是符合9,#,#转换为#这种情况的,但由于我没有利用好while导致一直没有得到正确的答案,而且代码又臭又长,深感水平太差啊。。。

0.0.2.1. 利用栈的做法

首先要明确的是树的前序遍历是按照根节点,左子树,右子树的顺序来排列的,那9,#,#代表一个两个孩子都为空的节点,即它是一个叶子节点;当一个节点不是叶子节点时,有两种情况:1)两个孩子都非#(空)2)一个孩子为空,一个孩子不为空。

这道题的重点思路来了:

  • 把有效的叶子节点#代替,比如把4##换成#

具体操作流程示例如下:

如输入: “9,3,4,#,#,1,#,#,2,#,6,#,#” ,当遇到 x,#,# 的时候,就把它变为 #。

模拟一遍过程:

[9,3,4,#,#] => [9,3,#],继续
[9,3,#,1,#,#] => [9,3,#,#] => [9,#] ,继续
[9,#2,#,6,#,#] => [9,#,2,#,#] => [9,#,#] => [#],结束
下面的动画模拟了”9,3,4,#,#,1,#,#,#”的操作过程:

代码比较简单,最需要注意的还是这个for循环里精准的while:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
stack = []
for node in preorder.split(','):
stack.append(node)
while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3].isdigit():
stack = stack[:-3] #stack.pop(),stack.pop(),stack.pop()
stack.append('#')

return len(stack) == 1 and stack.pop() == '#'

  • 时间复杂度:O(N)
  • 空间复杂度:O(N)

0.0.2.2. 计算入度出度 (还未掌握)

除了负雪明烛用了这个办法,另外一个超棒的博主笨猪爆破组也是写的这个方法,等待学习!

背景知识:

  • 入度: 有多少个节点指向它
  • 出度:它指向多少个节点

在树中,所有节点的入度之和等于出度之和。故,可以通过这个特点判断输入序列是否为有效的!

在一棵二叉树中:

  • 每个空节点( “#” )会提供 0 个出度和 1 个入度。
  • 每个非空节点会提供 2 个出度和 1 个入度(根节点的入度是 0)。

image

我们只要把字符串遍历一次,每个节点都累加 diff = 出度 - 入度 。在遍历到任何一个节点的时候,要求diff >= 0,原因是还没遍历到该节点的子节点,所以此时的出度应该大于等于入度。当所有节点遍历完成之后,整棵树的 diff == 0 。

这里解释一下为什么下面的代码中 diff 的初始化为 1。因为,我们加入一个非空节点时,都会对 diff 先减去 1(入度),再加上 2(出度)。但是由于根节点没有父节点,所以其入度为 0,出度为 2。因此 diff 初始化为 1,是为了在加入根节点的时候,diff 先减去 1(入度),再加上 2(出度),此时 diff 正好应该是2.

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def isValidSerialization(self, preorder):
nodes = preorder.split(',')
diff = 1
for node in nodes:
diff -= 1
if diff < 0:
return False
if node != '#':
diff += 2
return diff == 0
  • 时间复杂度:O(N)
  • 空间复杂度:O(1)

每日一题(2021.03.11)之基本计算器
难度:中等

0.0.1. 一、题目

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1:

1
2
输入:s = "3+2*2"
输出:7

示例 2:

1
2
输入:s = " 3/2 "
输出:1

示例 3:

1
2
输入:s = " 3+5 / 2 "
输出:5

提示:

  • 1 <= s.length <= 3 * 10^5
  • s 由整数和算符 (‘+’, ‘-‘, ‘*‘, ‘/‘) 组成,中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数,且在范围 [0, 2^31 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

0.0.2. 解法

好亲切的连环题(误 而且一看还是个medium,比起昨天hard的残虐,稍微松了一口气。。。
凭着脑海里昨日的记忆,欣喜若狂的写下这个愚蠢的答案。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
sign = 0 # 0 => +, 1 => - , 2 => *, 3 => /
res = 0
n = len(s)
i = 0
while i<n:
if s[i] == ' ':
i += 1
elif s[i] == '+':
sign = 0
i += 1
elif s[i] == '-':
sign = 1
i += 1
elif s[i] == '*':
sign = 2
i += 1
elif s[i] == '/':
sign = 3
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
while i<n and s[i].isdigit():
tmp += tmp*10 + int(s[i])
i += 1
if sign == 0:
res += tmp
tmp = 0
elif sign == 1:
res -= tmp
tmp = 0
elif sign == 2:
res *= tmp
tmp = 0
elif sign == 3:
res /= tmp
tmp = 0

return res

这个答案在遇到第一个示例s="3+3*2时就通过不了了,忘记了乘除法比加减法优先计算了。。。这就叫做乐极生悲吗

然后我又不识好歹的写下了这个答案逃之夭夭

1
2
3
4
5
6
7
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
return eval(s)

说正经的,当有加减乘除四种运算符时,考虑运算符优先级别,所以思路就是利用,假如遇到的是数字+-号时直接入栈(-换成-num入栈,之后就可以用sum(stack)返回结果了。遇到*,/的时候先把栈顶弹出,计算完结果后再保存回栈顶。

这里要注意一个python的细节,///的定义不同。//为向下取整,比如(-3)//2 = -2。我们不需要取整,-(abs(一个负数)/num)通过这个方式,就可以正确求职。

思路代码参考负雪明烛 这肯定是个小天使姐姐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""

stack = []
pre_op = '+'
num = 0
for i,each in enumerate(s):
if each.isdigit():
num = num*10 + int(each)
if i == len(s)-1 or each in '+-*/':
if pre_op == '+':
stack.append(num)
elif pre_op == '-':
stack.append(-num)
elif pre_op == '*':#遇到乘法,栈顶跳出计算,结果再储存
stack.append(stack.pop()*num)
elif pre_op == '/':#遇到除法,栈顶跳出计算,结果再储存
top = stack.pop()
if top < 0:
#这句稍有不同
stack.append(-(abs(top)/num))
else:
stack.append(top//num)
pre_op = each
num = 0

#由于栈内只有数字了(减法用负数表示),直接求和
return sum(stack)

这道题比起昨天的hard模式不是非常难,但是也是细节满满,学到了

一天一个声学参数之短时傅里叶变换STFT及其Python和Matlab的实现,在C++稍微上手一点儿后来补充C++的版本。

0.0.1. 1. 原理

短时傅里叶变换(Short Time Fourier Transform, STFT)是一个用于语音信号处理的通用工具(时频分析方法)。短时傅立叶变化的过程是把一个较长的时间信号分成相同长度的更短的段落,在每个更短的段上计算傅立叶变换

在实现时,短时傅里叶变换的计算实际上是一系列加窗数字信号的快速傅里叶变换(Fast Fourier Transform, FFT),其中窗口随时间”滑动Slide“或”跳跃Hop”。

0.0.1.1. 为什么要用STFT

短时傅里叶变换主要用于分析非平稳信号。非平稳信号由于波形的变化没有规律,也没有瞬间频率的概念,不能直接使用快速傅里叶变换。加窗使信号平稳化(从时间上截断,使得短时间内波形没有显著变化),于是可以对加窗的分段信号一段一段的使用FFT。也可以说,STFT得到的是按时间顺序排列的n段信号的频谱。

0.0.1.2. STFT的频率分辨率和时间分辨率

在短时傅里叶变化过程中,窗的长度决定频谱图的时间分辨率和频率分辨率,窗长越长,截取的信号越长,频率分辨率越高,时间分辨率越差。在STFT中,时间分辨率和频率分辨率不可兼得,应该按照具体需求取舍。换句话说,窄窗口时间分辨率高、频率分辨率低,宽窗口时间分辨率低、频率分辨率高。对于时变的非稳态信号,高频适合小窗口,低频适合大窗口。

0.0.1.3. STFT的物理和数学公式

短时傅里叶变换过程:将信号与一个窗函数想成,再进行一维的傅里叶变换。并通过窗函数的滑动得到一系列变化结果。

公式:

其中,z(t)为原信号函数,g(t)为窗函数。

为了方便计算机处理,一般将信号离散化: z(t) => z(n):

0.0.2. STFT的编程实现过程

0.0.2.1. 基于Matlab的实现过程(未验证)

  • 第一步:确定相关参数

参数主要包括:原信号,窗函数类型,窗长,重叠点数,采样频率,傅里叶点数等

其中,傅里叶点数主要用在傅里叶变化过程中,当信号长度小于傅里叶点数时,系统会自动进行补零,然后再进行快速傅里叶变换(FFT)。

  • 第二步:计算窗滑动的次数

计算信号的长度nx,并根据信号长度nx窗长WinLen以及窗口之间的重叠点数OverLap计算出需要窗口滑动的次数n。同时,也是源信号分成多少个短信号的列数。

n = fix((nx-overlap)/(WinLen-overlap))
(fix是matlab里的取整函数)

  • 第三步:确定每一列的值,得到一个列数为n,行数为WinLen的矩阵Fig

unknown block tag: asset_jupyter’col_index = (0:(t-1))*(WinLen-noverlap)
rowindex = (1:WinLen)’

xin = zeros(frame_length,t);
xin(:) = x(rowindex(:,ones(1,t))+colindex(ones(WinLen,1),:));

  • 第四步:把转换为列向量的窗函数扩展为n列的矩阵w,并对矩阵Fig和w进行点乘,并对点乘的结果进行快速傅里叶变换,得到时频矩阵。

xin = win(:,ones(1,t)).*xin;

  • 第五步:根据时频矩阵,输出频谱图

以上参考短时傅里叶变化原理解

0.0.2.2. 基于Python的实现过程

在程序中,frame\_size是被分成较短信号的帧的大小。在语音处理中,帧大小通常在20-40ms,这里设置25ms,即frame_size=0.025.

frame_stride为相邻帧的滑动尺寸/跳跃尺寸,通常帧的滑动尺寸在10ms到20ms之间,这里设置初始化为10ms,即frame_stride=0.01,此刻,相邻帧的交叠大小为15ms。

窗函数采用汉明窗函数(Hamming Function)

在每一帧,进行512点的快速傅里叶变换,即NFFT=512

以上参考短时傅里叶变换(Short Time Fourier Transform)原理及 Python 实现

0.0.2.3. Python实现STFT代码 三种方法

LeetCode之整数反转
难度:简单

0.0.1. 一、题目

给你一个 32 位的有符号整数 x ,返回 x 中每位上的数字反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

1
2
输入:x = 123
输出:321

示例 2:

1
2
输入:x = -123
输出:-321

示例 3:

1
2
输入:x = 120
输出:21

示例 4:

1
2
输入:x = 0
输出:0

提示:

-2**31 <= x <= 2**31 - 1

0.0.2. 二、我的解法

24ms, 83.28%; 12.9MB, 76.51%

因为在Python里,int没有长度,所以将其转换为str来获得其长度信息,代码很简单,主要是为了在第三部分学习他人简洁的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""


flag = False
if x < 0:
flag = True
x = -x

n = len(str(x))
res = 0

for i,ch in enumerate(str(x)[::-1]):
res += int(ch) * (10 ** (n-i-1))

res = -res if flag else res

if -2**31<res<2**31-1:
return res
else:
return 0

0.0.3. 三、他人的解法

如下参考Will

例子:1234 => 4321

这是一个4位的数字,个位数转换后变成了千位,十位变成了百位…

但是在这道题中,输入数字x的大小无法确定

思路为每次截取x的最后一位,按照倍数变化操作,通过while来完成

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def reverse(self, x):
a = 0
while x!=0:
if x>0:
a=a*10+x%10
x = x//10
else:
a=a*10+x%-10
x = -(x//-10)
return a if-2**31<a<2**31-1 else 0

每日一题系列(2021.03.10)之基本计算器
难度:困难

0.0.1. 一、题目

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

示例1:

1
2
输入:s = "1 + 1"
输出:2

示例2:

1
2
输入:s = " 2-1 + 2 "
输出:3

示例3:

1
2
输入:s = "(1+(4+5+2)-3)+(6+8)"
输出:23

提示:

  • 1 <= s.length <= 3 * 10^5
  • s 由数字、+、-、(、)、和 组成
  • s 表示一个有效的表达式

0.0.2. 二、我的解法(误

我看到这一题第一反应是:

1
return eval(s)

完事走人(抓回来

想必LeetCode早就预见了我等无耻之人,于是乎,eval作废,我的脑子也废了,现在开始学习大神的解法。。。

ps:我总感觉这题在hw的题库里好像见过也做过,但是咋一点儿印象也米有了

0.0.3. 三、真正的解法

这道题里有加减号,也有括号,分三部来考虑这个问题:

  • 不考虑括号,只考虑数字、加减号和空格
  • 考虑括号,数字,加减号和空格
  • 考虑括号,数字,加减乘除号和空格

以下部分参考了powcai的做法

0.0.3.1. 不考虑括号,考虑加减号

在不考虑括号的情况时,不需要用到的思路,在顺序上也没有强行要求,要注意的一点是,看到加号或减号时,要同时考虑符号前一位的数字,和符号后一位的数字。所以用一个sign来记录。

在下面的代码中,只有当进入elif s[i].isdigit():这个格子里的时候,才有真正对res进行计算的操作:res+= tmp * sign。这里就迎来了第二个要注意的点,有时候数字并非只是个位数。

以下为实现这个操作的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""

res = 0
sign = 1
i = 0
n = len(s)
while i<n:
if s[i] == ' ': #空格跳过
i += 1
elif s[i] == '-':
sign = -1
i += 1
elif s[i] == '+':
sign = 1
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
#验证这是不是一个非单位数,如果是的话,进入下面的while循环
while i<n and s[i].isdigit(): #如果数字有很多位的情况
tmp = tmp*10 + int(s[i])
i += 1
#真正的计算操作
res += tmp * sign

return res

0.0.3.2. 考虑括号,考虑加减号(第一种做法)

这一步则是到达了这道题目所要求的部分,也正是因为括号的出现,我们需要考虑计算的先后顺序,在这里,就要运用到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""

res = 0
sign = 1
i = 0
n = len(s)
stack = []
while i<n:
if s[i] == ' ': #空格跳过
i += 1
elif s[i] == '-':
sign = -1
i += 1
elif s[i] == '+':
sign = 1
i += 1
elif s[i] == '(':
stack.append(res)
stack.append(sign)
res = 0
sign = 1
i += 1
elif s[i] == ')':
res = res * stack.pop() + stack.pop()
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
#验证这是不是一个非单位数,如果是的话,进入下面的while循环
while i<n and s[i].isdigit(): #如果数字有很多位的情况
tmp = tmp*10 + int(s[i])
i += 1
#真正的计算操作
res += tmp * sign

return res

0.0.3.3. 考虑括号,考虑加减号(负雪明烛)

负雪明烛

来实现递归。

一个表达式可以分为三个部分:左边表达式①,运算符③,右边表达式②

左边和右边的表达式可以是一个数字,也可以是一个括号包起来的表达式;运算符可以是加减。

先计算左边的表达式,再计算右边表达式,最后根据运算符,计算 ① 和② 的运算。

"(1+(4+5+2)-3)+(6+8)"为例:

编程思路即:先计算左边的表达式① ,把①的结果和运算符③保存在栈内,再计算右边的表达式②,最后计算① 和②的运算。

在有括号的情况下,栈顶保留的是最里层嵌套的运算,弹出栈的时候,正好先计算最里层括号的,再计算外边括号的。

代码:

  • res 表示左边表达式除去栈内保存元素的计算结果;
  • sign 表示运算符;
  • num 表示当前遇到的数字,会更新到 res 中;
  • 用栈保存遇到左括号时前面计算好了的结果和运算符。

操作的步骤是:

  • 如果当前是数字,那么更新计算当前数字;
  • 如果当前是操作符+或者-,那么需要更新计算当前计算的结果 res,并把当前数字 num 设为 0,sign 设为正负,重新开始;
  • 如果当前是 ( ,那么说明遇到了右边的表达式,而后面的小括号里的内容需要优先计算,所以要把 res,sign 进栈,更新 res 和 sign 为新的开始;
  • 如果当前是 ) ,那么说明右边的表达式结束,即当前括号里的内容已经计算完毕,所以要把之前的结果出栈,然后计算整个式子的结果;
  • 最后,当所有数字结束的时候,需要把最后的一个 num 也更新到 res 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
def calculate(self, s):
res, num, sign = 0, 0, 1
stack = []
for c in s:
if c.isdigit():
num = 10 * num + int(c)
elif c == "+" or c == "-":
res += sign * num
num = 0
sign = 1 if c == "+" else -1
elif c == "(":
stack.append(res)
stack.append(sign)
res = 0
sign = 1
elif c == ")":
res += sign * num
num = 0
res *= stack.pop()
res += stack.pop()
res += sign * num
return res

LeetCode每日一题(2021.03.09)之删除字符串中的所有相邻重复项
难度:简单

0.0.1. 一、题目

给出由小写字母组成的字符串s重复项删除操作会选择两个相邻且相同的字母,并删除它们。

s上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符。答案保持唯一。

示例:

1
2
3
4
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"

提示:

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

0.0.2. 二、我的解法

思路

  • 如从字符串abba中先删除bb,会有新的重复字符串aa出现,所以需要保存当前还未被删除的字符串,联想到这种数据结构
  • 当字符串中有多组相邻重复项时,先删除哪一组不影响结果

296ms, 11.52%; 13.4MB, 73.03%
我的小菜鸡伪栈法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def removeDuplicates(self, S):
"""
:type S: str
:rtype: str
"""

res = ' '
for char in S:
if char != res[-1]:
res += char
else:
res = res[:-1]
return res[1:]

0.0.3. 三、其他的解法

0.0.3.1. 3.1 栈

感觉想法差不多,官方的栈效率高多了:
52ms, 88.07%; 13.4MB, 81.74%

1
2
3
4
5
6
7
8
9
class Solution:
def removeDuplicates(self, S: str) -> str:
stk = list()
for ch in S:
if stk and stk[-1] == ch:
stk.pop()
else:
stk.append(ch)
return "".join(stk)

今天是个简单题,yeah