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

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

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


第1次实验

日期:2018.10.17

实验题目1

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.
Example:
Input: J = “aA”, S = “aAAbbbb”
Output: 3
Input: J = “z”, S = “ZZ”
Output: 0
Note:
• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

参考代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#coding=utf-8
# File : 1-1.py
# Desc :
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/10/17 19:06

def main():
J = input("J = ")
S = input("S = ")
count = 0
for s in S:
if s in J:
count += 1
print(count)

if __name__=="__main__":
main()

实验题目2

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2
Output:
[
​ [2,4],
​ [3,4],
​ [2,3],
​ [1,2],
​ [1,3],
​ [1,4],
]

参考代码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
#coding=utf-8
# File : 1-2.py
# Desc :
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/10/17 19:14

def dfs(n, k, start, comb, ans):
if not k: #当k=0时,将当前组合添加到ans中
ans.append(comb)
return
for i in range(start, n + 1): # 1-4
dfs(n, k - 1, i + 1, comb + [i], ans)

# i = 1: self.dfs(4, 1, 2, [1], [])
# i = 2: self.dfs(4, 0, 3, [1, 2], [])
# i = 3: self.dfs(4, 0, 4, [1, 3], [])
# i = 4: self.dfs(4, 0, 5, [1, 4], [])

# i = 2: self.dfs(4, 1, 3, [2], [])
# i = 3: self.dfs(4, 0, 4, [2, 3], [])
# i = 4: self.dfs(4, 0, 5, [2, 4], [])

# i = 3: self.dfs(4, 1, 4, [2], [])
# i = 4: self.dfs(4, 0, 5, [3, 4], [])

# i = 4: self.dfs(4, 1, 5, [2], [])
# range(5, 5) 终止

# n: 数字范围
# k: 表示还可以添加到列表的个数,所以每dfs一次要减一
# start:表示开始的数字,所以每dfs一次要+1,不能是小于当前数字的值,防止重复
# lst: 当前组合
# ans: 保存最终答案

def main():
n = int(input("n = "))
k = int(input("k = "))
ans = []
dfs(n, k, 1, [], ans)
print(ans)

if __name__=="__main__":
main()


第2次实验

日期:2018.10.24

实验题目1

给定一个 m×n 矩阵,如果某个元素为 0,则将其整个行和列都设置为 0。
Example:
Input:
[
​ [1,1,1],
​ [1,0,1],
​ [1,1,1]
]
Output:
[
​ [1,0,1],
​ [0,0,0],
​ [1,0,1]
]
Input:
[
​ [0,1,2,0],
​ [3,4,5,2],
​ [1,3,1,5]
]
Output:
[
​ [0,0,0,0],
​ [0,4,5,0],
​ [0,3,1,0]
]
Follow up:
• 使用 O(mn)空间的解决方案可能不会很好。
• 你能设计一个恒定的空间复杂度解决方案吗?
• 学会用自己的 IDE 进行 Debug 断点调试,验收时现场演示。

参考代码1

暂无


第3次实验

日期:2018.10.31

实验题目1

Remove all elements from a linked list of integers that have value val.
Example:
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

参考代码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
#coding=utf-8
# File : 3-1.py
# Desc : Remove all elements from a linked list of
# integers that have value val.
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/10/30 20:48

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

def initial(head):
head = ListNode(0)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(6)
n4 = ListNode(3)
n5 = ListNode(4)
n6 = ListNode(5)
n7 = ListNode(6)
head.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
n6.next = n7
return head

def removeElements(head, val):
pre, cur = head, head.next
while cur:
if cur.val == val:
pre.next = cur.next
else:
pre = cur
cur = cur.next
return head.next

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

if __name__ == '__main__':
head = ListNode(0)
head = initial(head)

List = []
getList(head.next, List)
print(List)

# 删除节点
head = removeElements(head, 6)
List = []
getList(head, List)
print(List)

实验题目2

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
​ [‘A’,’B’,’C’,’E’],
​ [‘S’,’F’,’C’,’S’],
​ [‘A’,’D’,’E’,’E’]
]
Given word = “ABCCED“, return true.
Given word = “SEE“, return true.
Given word = “ABCB“, return false.

参考代码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
#coding=utf-8
# File : 3-2.py
# Desc : Given a 2D board and a word, find if the word
# exists in the grid. The word can be constructed
# from letters of sequentially adjacent cell, where
# "adjacent" cells are those horizontally or
# vertically neighboring. The same letter cell may
# not be used more than once.
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/10/30 21:21

def exist(board, word):
if len(board) == 0:
return False
for i in range(len(board)):
for j in range(len(board[0])):
# 从i,j点作为起点开始搜索
isExisted = search(board, i, j, word, 0)
if isExisted:
return True
return False

def search(board, i, j, word, idx):
if idx>=len(word):
return True
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j] != word[idx]:
return False
# 将已经搜索过的字母标记一下,防止循环。只要变成另外一个字符,就不会再有循环了。
temp = board[i][j]
board[i][j] = '*'
res = search(board, i-1, j, word, idx+1) or search(board, i+1, j, word, idx+1) \
or search(board, i, j-1, word, idx+1) or search(board, i, j+1, word, idx+1)
# 再次异或255就能恢复成原来的字母
board[i][j] = temp
return res

if __name__ == '__main__':
board = [['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
flag = exist(board, "SEE")
print(flag)


第4次实验

日期:2018.11.14

实验题目1

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->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
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
#coding=utf-8
# File : 4-1.py
# Desc : Merge two sorted linked lists and return it as a
# new list. The new list should be made by splicing
# together the nodes of the first two lists.
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/11/14 12:00

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]

if __name__ == '__main__':
L1 = input("L1:").split('->')
L2 = input("L2:").split('->')
L1_head = toList(L1)
L2_head = toList(L2)

mergeHead = ListNode(0)
mergeP = mergeHead
while L1_head.next != None and L2_head.next != None:
if L1_head.next.val <= L2_head.next.val:
mergeP.next = L1_head.next
mergeP = mergeP.next
L1_head.next = L1_head.next.next
else:
mergeP.next = L2_head.next
mergeP = mergeP.next
L2_head.next = L2_head.next.next

while L1_head.next != None:
mergeP.next = L1_head.next
mergeP = mergeP.next
L1_head.next = L1_head.next.next

while L2_head.next != None:
mergeP.next = L2_head.next
mergeP = mergeP.next
L2_head.next = L2_head.next.next

List = []
getListVal(mergeHead.next, List)
print(List)

实验题目2

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.
Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

参考代码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
#coding=utf-8
# File : 4-2.py
# Desc : Given a non-empty, singly linked list with head
# node head, return a middle node of linked list.
# If there are two middle nodes, return the second
# middle node.
# Author : jianhuChen
# license : Copyright(C), USTC
# Time : 2018/11/14 12:43

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

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]

if __name__ == '__main__':
L = input("Input L:").split()
print(L[int(len(L)/2)]) # 方法1

L_head = toList(L) # 方法2

P1 = L_head.next
p2 = L_head.next

while P1 != None and P1.next != None:
P1 = P1.next.next
p2 = p2.next

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