科大软院-《算法设计与分析》实验汇总-Part2

(实验课结束啦,更新完毕……)

由于实验一共有7次,放在一起太长了,所以我分了两个部分

如果发现错误请联系我,感激不尽!


第5次实验

日期:2018.11.21

实验题目1

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

例1:
输入:1->2->3->4->5->NULL
输出:1->3->5->2->4->NULL
例2:
输入: 2 ->1->3->5->6->4->7->NULL
输出:2->3->6->7->1->5->4->NULL

参考代码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
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
# -*- coding: utf-8 -*-
# @File : 5-1.py
# @Author : jianhuChen
# @Date : 2018-11-21 16:32:11
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-11-21 20:45:07

from random import *

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

# isRandom:是否随机找一个点循环
def toRandomCycleList(L, isRandom=False, cycleStart=1):
Nodes = [ListNode(0)]
for x in L:
Nodes.append(ListNode(int(x)))
for i in range(len(Nodes)-1):
Nodes[i].next = Nodes[i+1]
if isRandom:
Nodes[len(Nodes)-1].next = Nodes[randint(1, len(Nodes)-1)]
else:
Nodes[len(Nodes)-1].next = Nodes[cycleStart]
return Nodes[0]

def findCycleStart(head):
isCycle = False
fast = head
slow = head
while slow != None and fast != None:
slow = slow.next
if fast.next == None:
return None
fast = fast.next.next
if slow == fast:
isCycle = True
break
if not isCycle:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next

return slow

if __name__ == '__main__':
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# 将列表转换为链表形式,注意返回的链表带有一个头结点
# 所以待会儿找循环的起始位置时,传入的链表head应该为L1_head.next
L1_head = toRandomCycleList(L1, isRandom=True)
start = findCycleStart(L1_head.next)
# 如果没有循环则输出None
if start:
print(start.val)
else:
print("None")

参考资料:https://leetcode.com/problems/linked-list-cycle-ii/

实验题目2

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

参考代码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
# -*- coding: utf-8 -*-
# @File : 5-2.py
# @Author : jianhuChen
# @Date : 2018-11-21 16:32:32
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-11-21 19:02:21

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def getListVal(node, List):
if node != None:
List.append(node.val)
getListVal(node.next, List)


def toList(L):
Nodes = [ListNode(0)]
for x in L:
Nodes.append(ListNode(int(x)))
for i in range(len(Nodes)-1):
Nodes[i].next = Nodes[i+1]
return Nodes[0]

def oddEvenList(L):
if L != None:
odd = L # 奇数索引首节点
even = L.next # 偶数索引首节点
evenHead = even
while even != None and even.next != None:
odd.next = odd.next.next
even.next = even.next.next
odd = odd.next
even = even.next
odd.next = evenHead
return L

if __name__ == '__main__':
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
L1_head = toList(L1)
# 转换
head = oddEvenList(L1_head.next)
List = []
getListVal(head, List)
print("before:",L1)
print("after :",List)

参考资料:https://leetcode.com/problems/odd-even-linked-list/


第6次实验

日期:2018.11.28

实验题目1

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7

Note: The merging process must start from the root nodes of both trees.

参考代码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
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
# -*- coding: utf-8 -*-
# @File : 6-1.py
# @Author : jianhuChen
# @Date : 2018-11-27 19:09:27
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-11-27 20:23:57

# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x=0):
self.val = x
self.left = None;
self.right = None;
# 将树转换为先序列表
def getListFromTree(self, listTree):
listTree.append(self.val)
if self.left:
self.left.getListFromTree(listTree)
if self.right:
self.right.getListFromTree(listTree)

# 定义一棵树,供后面测试用
def init_tset():
# 第一棵树
tree1 = TreeNode(1)
Node1_1 = TreeNode(3)
Node1_2 = TreeNode(2)
Node1_3 = TreeNode(5)
tree1.left = Node1_1
tree1.right = Node1_2
Node1_1.left = Node1_3
# 第二棵树
tree2 = TreeNode(2)
Node2_1 = TreeNode(1)
Node2_2 = TreeNode(3)
Node2_3 = TreeNode(4)
Node2_4 = TreeNode(7)
tree2.left = Node2_1
tree2.right = Node2_2
Node2_1.right = Node2_3
Node2_2.right = Node2_4
return tree1, tree2

# 方法一:使用递归
def mergeTrees(t1, t2):
if t1 == None: # 若t1为空,则返回t2的地址,此时若t2也为空,则最后该节点的位置为空
return t2
if t2 == None: # 若t2为空,则返回t1地址
return t1
t1.val += t2.val # 若两者都不为空,将t1的值改为他们的和
t1.left = mergeTrees(t1.left, t2.left)
t1.right = mergeTrees(t1.right, t2.right)
return t1

# Complexity Analysis
# Time complexity : O(m). A total of m nodes need to be traversed. Here, mm represents the minimum number of nodes from the two given trees.
# Space complexity : O(m). The depth of the recursion tree can go upto m in the case of a skewed tree. In average case, depth will be O(logm).

# 测试
def main():
t1, t2= init_tset()
t1 = mergeTrees(t1, t2)
listTree = []
t1.getListFromTree(listTree)
print("先序遍历:", listTree)

if __name__ == '__main__':
main()

# 第二个迭代的方法可以看看下方的参考资料链接

参考资料:https://leetcode.com/articles/merge-two-binary-trees/

运行结果1

6-1

实验题目2

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

1
2
3
4
5
6
7
8
Given the tree:
4
/ \
2 7
/ \
1 3

And the value to search: 2

You should return this subtree:

1
2
3
  2     
/ \
1 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# -*- coding: utf-8 -*-
# @File : 6-2.py
# @Author : jianhuChen
# @Date : 2018-11-27 19:26:27
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-11-27 20:28:41

# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x=0):
self.val = x
self.left = None
self.right = None
# 将树转换为先序列表
def getListFromTree(self, listTree):
listTree.append(self.val)
if self.left:
self.left.getListFromTree(listTree)
if self.right:
self.right.getListFromTree(listTree)

def searchBST(root, val):
stack = [root]
while stack:
cur = stack.pop()
if cur.val == val:
return cur
if cur.left and cur.val > val: # 含有左孩子,并且待查找关键字比当节点的值小,此时去左边找
stack.append(cur.left)
elif cur.right and cur.val < val: # 含有右孩子,并且待查找关键字比当节点的值大,此时去右边找
stack.append(cur.right)
return None

# 定义一棵树,供后面测试用
def init_tset():
tree = TreeNode(4)
Node1 = TreeNode(2)
Node2 = TreeNode(7)
Node3 = TreeNode(1)
Node4 = TreeNode(3)
tree.left = Node1
tree.right = Node2
Node1.left = Node3
Node1.right = Node4
return tree

def main():
newTree = searchBST(init_tset(), 4) # 注意我这里找的是4,所以才会得到下面的输出结果
listTree = []
newTree.getListFromTree(listTree)
print("先序遍历:", listTree)

if __name__ == '__main__':
main()

参考资料:https://leetcode.com/problems/search-in-a-binary-search-tree/

运行结果2

6-2

注意我代码第49行里找的是4,所以才会得到上面的输出结果


第7次实验

日期:2018.12.05

实验题目1

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

6
/ \
3 5
\ /
2 0
\
1

Note:

  1. The size of the given array will be in the range [1,1000].

参考代码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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# -*- coding: utf-8 -*-
# @File : 7-1.py
# @Author : jianhuChen
# @Date : 2018-12-05 12:31:48
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-12-05 12:48:40

# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x=0):
self.val = x
self.left = None;
self.right = None;
# 将树转换为先序列表
def getListFromTree(self, listTree):
listTree.append(self.val)
if self.left:
self.left.getListFromTree(listTree)
if self.right:
self.right.getListFromTree(listTree)

def construct_maximum_binary_tree(nums):
if not nums: #递归终点
return None
i = nums.index(max(nums)) # 找到最大数量的索引
node = TreeNode(nums[i]) # 建立节点
# 以i索引为分界线,一分为二
node.left = construct_maximum_binary_tree(nums[:i])
node.right = construct_maximum_binary_tree(nums[i + 1:])
return node

def main():
nums = [3, 2, 1, 6, 0, 5]
head = construct_maximum_binary_tree(nums)
listTree=[]
head.getListFromTree(listTree)
print(listTree)

if __name__ == '__main__':
main()

# 我们来看看算法的前几个步骤。
# 数组中的最大数字6,存在于索引处3。
# 左子阵列(来自索引0 -> 2)的最大数量是3。
# 右子阵列中的最大数量(来自索引4 -> 5)是5。
# 根节点6和左,右的孩子3和5分别。
# 我们可以在左右子阵列上重复相同的算法,直到数组为空。

# 因此,我们得到以下算法:
# 1. 检查是否nums为空。如果是,请返回None。这可能会形成我们树的叶子。
# 2. 找到最大数量的索引。让我们说它在索引处i。
# 3. 创建一个内部元素为的节点nums[i]。
# 4. 使用nums[:i]右侧子树递归左侧子树nums[i + 1:]。
# 5. 返回节点。

运行结果1

7-1

参考资料:

https://leetcode.com/problems/maximum-binary-tree/

https://shreydesai.github.io/2017/08/07/leetcode-maximum-binary-tree.html

实验题目2

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its depth = 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# -*- coding: utf-8 -*-
# @File : 7-2.py
# @Author : jianhuChen
# @Date : 2018-12-05 12:48:55
# @License : Copyright(C), USTC
# @Last Modified by : jianhuChen
# @Last Modified time: 2018-12-05 18:49:57

# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x=None):
self.val = x
self.left = None;
self.right = None;

# 定义一棵树,供后面测试用
def init_tset():
tree = TreeNode(3)
Node1 = TreeNode(9)
Node2 = TreeNode(20)
Node3 = TreeNode(15)
Node4 = TreeNode(7)
tree.left = Node1
tree.right = Node2
Node2.left = Node3
Node2.right = Node4
return tree

# 方法一:递归
def maxDepthRecursion(root):
if root is None:
return 0
else:
left_height = maxDepthRecursion(root.left)
right_height = maxDepthRecursion(root.right)
return max(left_height, right_height) + 1

# 方法二:迭代
def maxDepthIteration(root):
stack = []
if root is not None:
stack.append((1, root))

depth = 0
while stack != []:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))

return depth

def main():
tree = init_tset() # 构造一棵树用于测试

depth1 = maxDepthRecursion(tree) # 方法一:递归
depth2 = maxDepthIteration(tree) # 方法二:迭代
print("maxDepth-Recursion:", depth1)
print("maxDepth-Iteration:", depth2)

if __name__ == '__main__':
main()

运行结果2

7-2

参考资料:https://leetcode.com/articles/maximum-depth-of-binary-tree/

如果你觉得此页面对你有帮助,或者想资瓷我一下,欢迎点击下面打赏哦,谢谢~