avatar


4.递归

  • 在第一章讨论衡量算法优劣指标的时候,我们提到了空间复杂度,但没有展开讨论。我们说要先讨论递归。
  • 在第二章讨论链表的时候,我们提到了链表反转,但没有展开讨论。我们说要先讨论递归。
  • 在第三章讨论栈的时候,我们提到了栈有多个应用,例如递归。

这一章,我们终于开始讨论递归。

盗梦空间与递归

我们从一部电影开始,《盗梦空间》。
盗梦空间

在影片中,导演有意留了一个话题,到底有几层梦?
现在,我们来解答这个问题。

我们让由小李子扮演的Cobb转动他的那个陀螺,如果陀螺不会停,说明在梦里,那么就GoBack,同时次数加1。如果陀螺会停,那么说明Cobb在真实世界,记作0。

上面这么一个过程,用代码表示如下。

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package ch04;

public class Inception {

public static class Cobb{
// top:陀螺
// 陀螺是否会停止
boolean topStop;

// 上一层梦的Cobb
Cobb prev;

/**
* 构造方法
* @param topStop 陀螺是否会停止
*/
public Cobb(boolean topStop) {
this.topStop = topStop;
}

}

/**
* 回到上一层
* @param cobb 男主角
* @return 几层梦
*/
public static int GoBack(Cobb cobb){
if (cobb.topStop == false){
// 回到上一层
cobb = cobb.prev;
// 递归
return GoBack(cobb) + 1;
}else{
// 如果陀螺停了,说明在第0层
return 0;
}
}

public static void main(String[] args) {
// 定义Cobb的梦
// 假的Cobb,他的陀螺不会停
Cobb fakeCobb = new Cobb(false);
fakeCobb.prev = new Cobb(false);
fakeCobb.prev.prev = new Cobb(false);
fakeCobb.prev.prev.prev = new Cobb(false);
fakeCobb.prev.prev.prev.prev = new Cobb(false);
fakeCobb.prev.prev.prev.prev.prev = new Cobb(false);
fakeCobb.prev.prev.prev.prev.prev.prev = new Cobb(false);

// 真实的Cobb,他的陀螺会停
Cobb realCobb = new Cobb(true);
fakeCobb.prev.prev.prev.prev.prev.prev.prev = realCobb;

// 递归,求Cobb梦的大小
// fackCobb开始GoBack
int DreamSize = GoBack(fakeCobb);
System.out.println(DreamSize);

}
}

运行结果:

1
7

示例代码:

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
46
47
# Cobb
class Cobb:

def __init__(self, topStop):
"""
构造方法
:param topStop: 陀螺停止
"""
self.topStop = topStop
self.prev = None


def GoBack(cobb):
"""
GoBack
:param cobb:
:return:
"""
# 如果Cobb的陀螺不会停
if not cobb.topStop:
# Cobb回到上一层
cobb = cobb.prev
return GoBack(cobb) + 1
else:
# 如果Cobb的陀螺会停,说明在真实世界,0层
return 0


if __name__ == '__main__':
# 定义Cobb的梦
# 假的Cobb
fakeCobb = Cobb(False)
fakeCobb.prev = Cobb(False)
fakeCobb.prev.prev = Cobb(False)
fakeCobb.prev.prev.prev = Cobb(False)
fakeCobb.prev.prev.prev.prev = Cobb(False)
fakeCobb.prev.prev.prev.prev.prev = Cobb(False)
fakeCobb.prev.prev.prev.prev.prev.prev = Cobb(False)

# 真实的Cobb,他的陀螺会停
realCobb = Cobb(True)
fakeCobb.prev.prev.prev.prev.prev.prev.prev = realCobb

# 递归,求Cobb梦的大小
# fakeCobb开始GoBack
DreamSize = GoBack(fakeCobb)
print(DreamSize)

运行结果:

1
7

通过这个例子,我们对递归能有一个初步的认识。

  1. 一个问题的解可以分解为几个子问题的解,且与分解之后的子问题,除了数据规模不同,求解思路完全一样。
    比如:GoBack
  2. 存在递归终止条件
    比如:陀螺停了

接下来,我们用递归来玩一个游戏,汉诺塔,以此强化递归。

汉诺塔

如果大家没有玩过这个游戏,可以去4399等网站试玩一下。
汉诺塔

总之,这个游戏的目标是把最左边的圆盘移动到最右边,并且小圆盘只能在大圆盘的上面。

方法一

我们来把问题拆解。
目标是:把NN层圆盘从左边移动到右边

一、怎么把NN层圆盘从左边移动到右边

  1. 11层到第N1N-1层圆盘从左边移动到中间
  2. NN层圆盘从左边移动到右边
  3. 11层到第N1N-1层圆盘从中间移动到右边

二、怎么把NN层圆盘从左边移动到中间

  1. 11层到第N1N-1层圆盘从左边移动到右边
  2. NN层圆盘从左边移动到中间
  3. 11层到第N1N-1层圆盘从右边移动到中间

三、怎么把NN层圆盘从中间移动到右边

  1. 11层到第N1N-1层圆盘从中间移动到左边
  2. NN层圆盘从中间移动到右边
  3. 11层到第N1N-1层圆盘从左边移动到右边

四、怎么把NN层圆盘从右边移动到中间

  1. 11层到第N1N-1层圆盘从右边移动到左边
  2. NN层圆盘从右边移动到中间
  3. 11层到第N1N-1层圆盘从左边移动到中间

五、怎么把NN层圆盘从中间移动到左边

  1. 11层到第N1N-1层圆盘从中间移动到右边
  2. NN层圆盘从中间移动到左边
  3. 11层到第N1N-1层圆盘从右边移动到左边

六、怎么把NN层圆盘从右边移动到左边

  1. 11层到第N1N-1层圆盘从右边移动到中间
  2. NN层圆盘从中间移动到左边
  3. 11层到第N1N-1层圆盘从中间移动到左边

六个递归循环调用,但是入口是从左边移动到右边
这样我们就把一个大问题拆成了几个小问题,而且这些小问题的解决方案都差不多。
那么递归终止条件是什么呢?当只一个圆盘的时候。

例如,3层汉诺塔。

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package ch04;

public class HaNuoTa {
// 请把1~N层圆盘 从左 -> 右
public static void leftToRight(int n) {
if (n == 1) { // base case
System.out.println("Move 1 from left to right");
return;
}
leftToMid(n - 1);
System.out.println("Move " + n + " from left to right");
midToRight(n - 1);
}

// 请把1~N层圆盘 从左 -> 中
public static void leftToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(n - 1);
System.out.println("Move " + n + " from left to mid");
rightToMid(n - 1);
}

public static void rightToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(n - 1);
System.out.println("Move " + n + " from right to mid");
leftToMid(n - 1);
}

public static void midToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to right");
return;
}
midToLeft(n - 1);
System.out.println("Move " + n + " from mid to right");
leftToRight(n - 1);
}

public static void midToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(n - 1);
System.out.println("Move " + n + " from mid to left");
rightToLeft(n - 1);
}

public static void rightToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(n - 1);
System.out.println("Move " + n + " from right to left");
midToLeft(n - 1);
}

public static void main(String[] args) {
leftToRight(3);
}
}
运行结果:
1
2
3
4
5
6
7
Move 1 from left to right
Move 2 from left to mid
Move 1 from right to mid
Move 3 from left to right
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to right

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
# 请把1~N层圆盘 从左 -> 右
def left_to_right(n):
if n == 1:
print("Move 1 from left to right")
return
left_to_mid(n - 1)
print("Move " + str(n) + " from left to right")
mid_to_right(n - 1)


# 请把1~N层圆盘 从左 -> 中
def left_to_mid(n):
if n == 1:
print("Move 1 from left to mid")
return
left_to_right(n - 1)
print("Move " + str(n) + " from left to mid")
right_to_mid(n - 1)


def right_to_mid(n):
if n == 1:
print("Move 1 from right to mid")
return
right_to_left(n - 1)
print("Move " + str(n) + " from right to mid")
left_to_mid(n - 1)


def mid_to_right(n):
if n == 1:
print("Move 1 from mid to right")
return
mid_to_left(n - 1)
print("Move " + str(n) + " from mid to right")
left_to_right(n - 1)


def mid_to_left(n):
if n == 1:
print("Move 1 from mid to left")
return
mid_to_right(n - 1)
print("Move " + str(n) + " from mid to left")
right_to_left(n - 1)


def right_to_left(n):
if n == 1:
print("Move 1 from right to left")
return
right_to_mid(n - 1)
print("Move " + str(n) + " from right to left")
mid_to_left(n - 1)


if __name__ == '__main__':
left_to_right(3)
运行结果:
1
2
3
4
5
6
7
Move 1 from left to right
Move 2 from left to mid
Move 1 from right to mid
Move 3 from left to right
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to right

方法二

太极剑法

在金庸的武侠小说《倚天屠龙记》中,有一个桥段是张三丰传授太极剑法给张无忌。当张无忌不再拘泥于招式形式,而领悟到太极剑法真谛的时候,才是张无忌真正学会太极剑法,

现在,让我们也忘记左中右
我们做的不是过把NN层圆盘从from移动到to上:

  1. 11层到第N1N-1层从from移动到other
  2. NN层从from移动到to
  3. 11层到第N1N-1层从other移动到to

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package ch04;

public class HaNuoTa2nd {

public static void func(int N, String from, String to, String other) {
if (N == 1) { // base
System.out.println("Move 1 from " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
func(N - 1, other, to, from);
}
}

public static void main(String[] args) {
func(3,"left","right","mid");
}
}
运行结果:
1
2
3
4
5
6
7
Move 1 from left to right
Move 2 from left to mid
Move 1 from right to mid
Move 3 from left to right
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to right

示例代码:

1
2
3
4
5
6
7
8
9
10
11
def func(n, froms, tos, other):
if n == 1:
print("Move 1 from " + froms + " to " + tos)
else:
func(n - 1, froms, other, tos)
print("Move " + str(n) + " from " + froms + " to " + tos)
func(n - 1, other, tos, froms)


if __name__ == '__main__':
func(3, "left", "right", "mid")
运行结果:
1
2
3
4
5
6
7
Move 1 from left to right
Move 2 from left to mid
Move 1 from right to mid
Move 3 from left to right
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to right

递归和栈

在第三章,我们留了一个话题没讨论,递归和栈的关系。现在讨论。

递归执行过程

就以刚刚汉诺塔的方法二为例子,讨论递归代码的执行过程。

首先,计算机在执行上述的程序的时候,会专门分配一块内容,用来存储方法调用栈。
我们传入3,"left","right","mid",这时候func(3,"left","right","mid")的调用信息进入方法调用栈。

func(3,"left","right","mid")

处理栈顶的调用信息。

因为3 != 1,所以执行else中的代码,执行代码func(N - 1, from, other, to)
即,调用信息func(2,"left","mid","right")进入方法调用栈。

func(2,"left","mid","right")
func(3,"left","right","mid")

处理栈顶的调用信息。

因为2 != 1,所以执行else中的代码,执行代码func(N - 1, from, other, to)
即,调用信息func(2,"left","right","mid")进入方法调用栈。

func(1,"left","right","mid")
func(2,"left","mid","right")
func(3,"left","right","mid")

处理栈顶的调用信息。

因为1 == 1,所以执行代码print("Move 1 from " + from + " to " + to)
打印内容:

1
Move 1 from left to right

该方法没有再去递归调用任何方法,执行结束后,该方法出栈。

func(2,"left","mid","right")
func(3,"left","right","mid")

处理栈顶的调用信息。

继续处理调用信息func(2,"left","mid","right")
执行代码print("Move " + N + " from " + from + " to " + to)
打印内容:

1
Move 2 from left to mid

执行代码func(N - 1, other, to, from),调用信息func(1,"right","mid","left")入栈。

func(1,"right","mid","left")
func(2,"left","mid","right")
func(3,"left","right","mid")

处理栈顶的调用信息。

接下来,执行代码print("Move 1 from " + from + " to " + to)
打印内容:

1
Move 1 from right to mid

该方法没有再去递归调用任何方法,执行结束后,该方法出栈。

调用信息func(1,"right","mid","left")、调用信息func(2,"left","mid","right")依次出栈。

func(3,"left","right","mid")

处理栈顶的调用信息。

依次执行代码
print("Move " + N + " from " + from + " to " + to)
func(N - 1, other, to, from)

调用信息func(2,"mid","right","left")入栈。

func(2,"mid","right","left")
func(3,"left","right","mid")

后续过程略。

总之,调用信息一个一个进栈,每次处理栈顶的调用信息,结束后出栈。

这也是为什么,在递归代码中,我们一定要控制好递归的终止条件。否则无限的调用信息进入方法调用栈,最后会导致堆栈溢出。(在Python中不是堆栈溢出,Python设置了递归最大深度。)

具体报错信息:

1
Exception in thread "main" java.lang.StackOverflowError
1
2
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

空间复杂度

在第一章,我们留了一个话题没讨论,空间复杂度。现在讨论。

递归空间

首先,递归的空间复杂度。
正如我们刚刚讨论的递归调用过程。
因为有一个方法调用栈,所以对于递归代码,其空间复杂度与递归深度相关,O(n)O(n)

除了递归空间外,还有

  • 常量空间
  • 线性空间
  • 二维空间

常量空间

例如

1
int i = 0;
1
i = 0

intdoublelong等,所占用的字节当然是不同的。但是对于空间复杂度,一律是O(1)O(1)

线性空间

例如

1
int[] a = new int[n]
1
a = [None] * n

其空间复杂度是O(n)O(n)

二维空间

例如

1
int[][] m = new int[n][n]
1
m = [[None] * n] * n

其空间复杂度是O(n2)O(n^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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package ch04;

public class ReverseLinkedList_Recur {

/**
* 链表节点
*/
private static class Node {
// 节点的值
int data;
// next
Node next;

/**
* 构造方法
* @param data
*/
Node(int data) {
this.data = data;
}
}

/**
* 反转链表
* @param head head节点
* @return
*/
public static Node reverse(Node currNode){
// 如果当前节点是空,或者当前节点的下一个节点是空,说明已经是尾节点了
if (currNode == null || currNode.next == null)
return currNode;
// 如果前面的没有命中,说明不是尾节点
// 当前节点的下一个节点
Node nextNode = currNode.next;
// 下一个节点进行属于下一个节点反转
Node newNextNode = reverse(nextNode);
// 当前节点做属于当前节点的反转操作
nextNode.next = currNode;
currNode.next = null;
// 返回
return newNextNode;
}

/**
* 输出链表
* @param head
*/
public static void print(Node headNode){
String rnt = "";
while (headNode!=null) {
rnt = rnt + headNode.data + " ";
headNode = headNode.next;
}
System.out.println(rnt);
}

public static void main(String[] args) {
Node head = new Node(0);
head.next = new Node(1);
head.next.next = new Node(2);
head.next.next.next = new Node(3);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(5);
head.next.next.next.next.next.next = new Node(6);
head.next.next.next.next.next.next.next = new Node(7);
head.next.next.next.next.next.next.next.next = new Node(8);
head.next.next.next.next.next.next.next.next.next = new Node(9);

print(head);

Node reHead = reverse(head);

print(reHead);
}
}

运行结果:

1
2
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 链表的节点
class Node:
def __init__(self, data):
"""
构造方法
:param data:
"""
self.data = data
self.next = None


def reverse(currNode):
"""
反转
:param currNode: 当前节点
:return:
"""
# 如果当前节点是None或者当前节点的下一个节点是None
if currNode is None or currNode.next is None:
# 说明是尾节点
return currNode

# 如果前面的都没有命中,说明不是尾节点
# 下一个节点
nextNode = currNode.next
# 下一个节点进入属于他的反转
newNextNode = reverse(nextNode)
# 当前节点进行反转
nextNode.next = currNode
currNode.next = None

return newNextNode


def output(headNode):
"""
输出节点
:param headNode: 头节点
:return:
"""
rnt = []
while headNode is not None:
rnt.append(headNode.data)
headNode = headNode.next
print(rnt)


if __name__ == '__main__':
head = Node(0)
head.next = Node(1)
head.next.next = Node(2)
head.next.next.next = Node(3)
head.next.next.next.next = Node(4)
head.next.next.next.next.next = Node(5)
head.next.next.next.next.next.next = Node(6)
head.next.next.next.next.next.next.next = Node(7)
head.next.next.next.next.next.next.next.next = Node(8)
head.next.next.next.next.next.next.next.next.next = Node(9)

output(head)

reHead = reverse(head)

output(reHead)

运行结果:

1
2
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

非递归

那么,链表反转,可以用非递归的方法实现吗?
当然可以。
我们回忆一下,递归的时候,计算机做了什么?
把一个一个的调用信息push进方法调用栈,处理栈顶的调用信息。
一个一个处理,一个一个弹出。
那么,对于这个过程,我们可以用循环代替。

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package ch04;

public class ReverseLinkedList_NO_Recur {
/**
* 链表节点
*/
private static class Node {
// 节点的值
int data;
// next
Node next;

/**
* 构造方法
* @param data
*/
Node(int data) {
this.data = data;
}
}

/**
* 反转
* @param currNode 当前节点
* @return
*/
public static Node reverse(Node currNode){
// 前一个节点
Node prevNode = null;
// 下一个节点
Node nextNode = null;
// 如果当前节点不等于空,说明还没反转完
while (currNode != null){
// 把当前节点的下一个节点,赋值给nextNode
nextNode = currNode.next;

// 让节点的next指针,指向前一个节点prevNode
currNode.next = prevNode;

// 为下一轮循环做准备
// 把当前节点作为前一个节点
// 把下一个节点作为当前节点
prevNode = currNode;
currNode = nextNode;
}
// 如果当前节点是空的话,那么前一个节点就一定是反转之后链表的head
return prevNode;
}

/**
* 输出链表
* @param head
*/
public static void print(Node headNode){
String rnt = "";
while (headNode!=null) {
rnt = rnt + headNode.data + " ";
headNode = headNode.next;
}
System.out.println(rnt);
}

public static void main(String[] args) {
Node head = new Node(0);
head.next = new Node(1);
head.next.next = new Node(2);
head.next.next.next = new Node(3);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(5);
head.next.next.next.next.next.next = new Node(6);
head.next.next.next.next.next.next.next = new Node(7);
head.next.next.next.next.next.next.next.next = new Node(8);
head.next.next.next.next.next.next.next.next.next = new Node(9);

print(head);

Node reHead = reverse(head);

print(reHead);
}
}

运行结果:

1
2
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0

示例代码:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# 链表的节点
class Node:
def __init__(self, data):
"""
构造方法
:param data:
"""
self.data = data
self.next = None


def reverse(currNode):
"""
反转链表
:param currNode: 当前节点
:return:
"""
# 上一个节点
prevNode = None
# 下一个节点
nextNode = None
# 如果当前节点不等于空,说明还没反转完
while currNode is not None:
# 把当前节点的下一个节点,赋值给next
nextNode = currNode.next

# 当前节点的next指针,指向prevNode,反转
currNode.next = prevNode

# 为下一轮循环做准备
# 把当前节点作为前一个节点
# 把下一个节点作为当前节点
prevNode = currNode
currNode = nextNode

# 如果当前节点是空的话,那么前一个节点就一定是反转之后链表的head
return prevNode


def output(headNode):
"""
输出节点
:param headNode: 头节点
:return:
"""
rnt = []
while headNode is not None:
rnt.append(headNode.data)
headNode = headNode.next
print(rnt)


if __name__ == '__main__':
head = Node(0)
head.next = Node(1)
head.next.next = Node(2)
head.next.next.next = Node(3)
head.next.next.next.next = Node(4)
head.next.next.next.next.next = Node(5)
head.next.next.next.next.next.next = Node(6)
head.next.next.next.next.next.next.next = Node(7)
head.next.next.next.next.next.next.next.next = Node(8)
head.next.next.next.next.next.next.next.next.next = Node(9)

output(head)

reHead = reverse(head)

output(reHead)

运行结果:

1
2
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

两个代码的区别

最后,我们再来讨论一下,上述的代码。除了一个是递归,一个不是递归外。还有没有区别?
我想,最主要的区别是,递归的代码是调用信息依次入栈,依次执行,依次弹出。所以是从尾节点到头节点,依次反转。
而非递归的代码,很明显,是从头节点到尾节点依次反转。

在下一个例子中,我们会有更深刻的理解。

子序列

我们先来辨析一下什么是子串,什么是子序列。
现在有一个字符串abc,其子串有:

  • 0位置开始:aababc
  • 1位置开始:bbc
  • ······

这种很简单,也不需要递归,两个for循环就够了。

而子序列的条件比子串的条件更宽松,子序列不要求连续,但位置不能乱。比如:ac是子序列,但ca不是子序列。
所以子序列问题其实是0位置1位置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
package ch04;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Subsquence {

public static ArrayList<String> process(Queue<Character> queue){
ArrayList<String> rnt = new ArrayList<>();
if (queue.isEmpty()){
rnt.add("");
return rnt;
}
Character t = queue.poll();
String s_yes = t.toString();
String s_no = "";
for (String str : process(queue)){
rnt.add(s_yes + str);
rnt.add(s_no + str);
}

return rnt;
}


public static void main(String[] args) {
char[] str = "abc".toCharArray();
Queue<Character> queue = new LinkedList<>();
for (Character c : str){
queue.offer(c);
}
ArrayList<String> ans = process(queue);
System.out.println(ans);
}
}
运行结果:
1
[abc, bc, ac, c, ab, b, a, ]

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from queue import Queue


def process(q):
rnt = []
if q.empty():
rnt.append("")
return rnt
t = q.get()
s_yes = t
s_no = ""
for s in process(q):
rnt.append(s_yes + s)
rnt.append(s_no + s)
return rnt


if __name__ == '__main__':
s = ['a', 'b', 'c']
q = Queue()
for c in s:
q.put(c)
ans = process(q)
print(ans)
运行结果:
1
['abc', 'bc', 'ac', 'c', 'ab', 'b', 'a', '']

似乎有点奇怪,虽然结果对了,但是打印顺序和我们刚刚分析的不一样啊?
这是因为,我们的代码和我们刚刚讨论的思路就不一样。
回忆一下,我们刚刚说的,方法调用依次入栈,然后依次执行,依次弹出。
这样,我们首先处理的是最后一个位置,3位置的元素要或不要。
如图所示,在我们的思路中,我们首先处理的是0元素的位置要不要。

那么,我们这么做。

示例代码:

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
package ch04;

import java.util.ArrayList;

public class Subsquence2nd {

/**
* @param str 固定参数
* @param index 来到了str[index]字符,index是位置
* @param ans
* @param path 之前已经决定的不能改变,即使path
* @return
*/
public static void process(char[] str, int index, ArrayList<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
// 要了index位置的字符
process(str, index + 1, ans, path + String.valueOf(str[index]));
// 没有要index位置的字符
process(str, index + 1, ans, path);
}


public static void main(String[] args) {
char[] str = "abc".toCharArray();
String path = "";
ArrayList<String> ans = new ArrayList<>();
process(str, 0, ans, path);
System.out.println(ans);
}
}
运行结果:
1
[abc, ab, ac, a, bc, b, c, ]

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def process(s, index, ans, path):
if index == len(s):
ans.append(path)
return
# 要了index位置的字符
process(s, index + 1, ans, path + s[index])
# 没有要index位置的字符
process(s, index + 1, ans, path)


if __name__ == '__main__':
s = ['a', 'b', 'c']
path = ''
ans = []
process(s, 0, ans, path)
print(ans)
运行结果:
1
['abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', '']

特别的,如果我们要求不出现重复字面值呢?
在上例中,我们给定的字符串是abc,是天然不会出现重复字面值。
但,如果我们给定的字符串是aaa,我们要0位置和1位置,得到的是aa,要0位置和2位置得到的也是aa,这就是重复字面值。

这个问题,我们在讨论哈希表的时候再讨论。

排列

这个问题,我们在高中数学中就学过。
现在有三同学。
排列

我们来看实现过程。

示例代码:

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
package ch04;

import java.util.ArrayList;

public class Permutation {
/**
* @param str 固定参数
* @param index 来到了str[index]字符,index是位置
* @param ans
* @param path 之前已经决定的不能改变,即使path
* @return
*/
public static void process(ArrayList<Character> str, ArrayList<String> ans, String path) {
if (str.isEmpty()) {
ans.add(path);
return;
}
for (int i = 0; i < str.size(); i++) {
ArrayList<Character> temp = (ArrayList<Character>) str.clone();
temp.remove(i);
process(temp, ans, path + String.valueOf(str.get(i)));
}
}


public static void main(String[] args) {
ArrayList<Character> l = new ArrayList<>();
l.add('甲');
l.add('乙');
l.add('丙');
ArrayList<String> ans = new ArrayList<>();
String path = "";
process(l, ans, path);
System.out.println(ans);
}
}
运行结果:
1
[甲乙丙, 甲丙乙, 乙甲丙, 乙丙甲, 丙甲乙, 丙乙甲]

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def process(s, ans, path):
if len(s) == 0:
ans.append(path)
return
for i in range(len(s)):
temp = s.copy()
temp.pop(i)
process(temp, ans, path + s[i])


if __name__ == '__main__':
l = ['甲', '乙', '丙']
ans = []
path = ""
process(l, ans, path)
print(ans)
运行结果:
1
['甲乙丙', '甲丙乙', '乙甲丙', '乙丙甲', '丙甲乙', '丙乙甲']

如果对于这个问题,我们也要求不出现重复排列呢?

我们会在讨论哈希表的时候再讨论。

跳台阶

跳台阶,这是很经典的一个问题。
有一种与这个问题类似的问题,换零钱。

  • 【排列】 现在有N阶台阶,每次只能跳1阶或者2阶,有多少种方法?
  • 【组合】 现在有N元钱,要换成1元的或者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
package ch04;

public class Steps {

/**
* 跳
* @param n
* @return 方法数
*/
public static int jump(int n){
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return (jump(n-1) + jump(n-2));
}

public static void main(String[] args) {
int total = jump(6);
System.out.println(total);
}
}

运行结果:

1
13

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def jump(n):
"""

:param n:
:return:
"""
if n == 1:
return 1
if n == 2:
return 2

return jump(n - 1) + jump(n - 2)


if __name__ == '__main__':
total = jump(6)
print(total)

运行结果:

1
13

这个求解过程有没有问题?
当然没有问题,用递归就是得这么算。
但我们看一看
重复计算

  • f(4)被重复计算了
  • f(3)也被重复计算了。

重复计算
这就是递归的一个缺点。
那么,怎么克服这个问题呢?
这个问题,我们还是在讨论哈希表的时候再讨论。

将JSON转成小驼峰

最后,举一个我在工作中实际用到的例子。将JSON的key转成小驼峰格式。

示例代码:

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
46
47
public static void main(String[] args) {
// System.out.println(diGuiJa(JSONArray.parseArray(js)));
System.out.println(diGuiJo(JSONObject.parseObject(js)));
}

private static JSONArray diGuiJa(JSONArray obj) {
JSONArray toRntJa = new JSONArray();
for (int i = 0; i < obj.size(); i++) {
if (obj.get(i) instanceof JSONArray) {
toRntJa.add(diGuiJa(obj.getJSONArray(i)));
}else if (obj.get(i) instanceof JSONObject) {
toRntJa.add(diGuiJo(obj.getJSONObject(i)));
}else {
toRntJa.add(obj.get(i));
}
}
return toRntJa;
}

private static JSONObject diGuiJo(JSONObject obj) {
JSONObject toRntJo = new JSONObject();
for (String k : obj.keySet()) {
if (obj.get(k) instanceof JSONObject) {
toRntJo.put(lowerCamelCase(k), diGuiJo(obj.getJSONObject(k)));
}else if (obj.get(k) instanceof JSONArray) {
toRntJo.put(lowerCamelCase(k), diGuiJa(obj.getJSONArray(k)));
}else {
toRntJo.put(lowerCamelCase(k), obj.get(k));
}
}
return toRntJo;
}

private static String lowerCamelCase(String k) {
String r = "";
String[] kArr = k.split("_");
int index = 0;
for (String kArrIter : kArr) {
if (index == 0) {
r = r + (kArrIter.substring(0, 1).toLowerCase() + kArrIter.substring(1, kArrIter.length()));
}else {
r = r + (kArrIter.substring(0, 1).toUpperCase() + kArrIter.substring(1, kArrIter.length()));
}
index = index + 1;
}
return r;
}
文章作者: Kaka Wan Yifan
文章链接: https://kakawanyifan.com/10604
版权声明: 本博客所有文章版权为文章作者所有,未经书面许可,任何机构和个人不得以任何形式转载、摘编或复制。

留言板