#Python #数据结构与算法
与leetcode的式下核心代码模式不同，acm模式下需要自己编写输入与输出函数。入输
推荐以下几个网站练习acm模式：
牛客网：OJ在线编程常见输入输出练习场
牛客网：华为机试
AcWing
1. 输入函数模板
1.1 获取输入数据
Python输入数据主要通过input()函数实现，式下input()会读取控制台一行的入输输入，如果输入有多行的式下话，需要多次使用input()。入输
# 输入为: 1 2 3 4 5a = input()# a = '1 2 3 4 5'与Python2中不同，式下Python3中的入输input()会将接受的数据返回为一个string类型，如果一行中有多个数据的式下话，则需要使用split()进行切割。入输split()切割后返回一个列表。式下
# 输入为： 1 2 3 4 5a = input().split() # split()默认以空字符为分隔符，入输包括空格、式下换行(\n)、入输制表符(\t)等# a = ['1',式下 '2', '3', '4', '5'] # 输入为：1,2,3,4,5b = input().split(',') # 以逗号为分隔符# b = ['1', '2', '3', '4', '5']因为input()返回的是string，分割后也是一个字符列表，如果输入数据是数字则需要进行类型转换。可以单个转换或是用列表批量转换，或者是使用map()并行转换。map()函数返回的是一个迭代器，不能改变值，如果需要改变值的话还需要转换成列表
# 输入为： 1 a = int(input()) # 单个转换 # 输入为：1 2 3 4 5b = input().split() # b = ['1', '2', '3', '4', '5']c = [int(i) for i in b] # 使用列表进行批量转换 c = [1, 2, 3, 4, 5]d = [int(i) for i in input().split()] # 当然可以一步倒位 # 使用map进行并行转换e = map(int, input().split()) # 此时e是一个map迭代器，不能赋值，也不能索引f = list(e) # 转换为列表，e = [1, 2, 3, 4, 5]g = list(map(int, input().split())) # 一步到位 1.2 三种情况的输入数据
情况1: 多行输入，同时未指定用例的个数，例子1
while True: try: data = input() solve(data) # 核心函数 except: break情况2: 多行输入， 指定用例个数， 例子2
n = int(input()) 获取用例个数for _ in range(n): data = input() solve(data) # 核心函数情况3: 多行输入，指定某个条件退出，例子3
while True: data = input() if judge(data): # 判断 break solve(data)2. 输出函数模板
Python3的输出主要靠print()函数，就是把结果打印至终端。需要对print()函数的sep和end两个参数有一定的了解，可以查看菜鸟教程
情况1: 输出单个数字
# 输出 a (a = 1)print(a)情况2: 输出多个数字，同时要求以分隔符隔开
# 输出 a=1, b=2, c=3print(a, b, c) # print默认以空格为分隔符# output：1 2 3print(a, b, c, sep=',') # 以逗号为分隔符# output：1,2,3情况3：最终结果是一个列表
# 最终结果 res = [1, 2, 3]# 1. 直接输出列表print(res)# 2. 输出列表, 每个元素单独输出for i in range(len(res)): print(res[i])#output: 1# 2# 3# 3. 输出列表，每个元素单独输出，同时还需要在同一行输出, 以空格分隔for i in range(len(res)): print(res[i], end=' ') # end的默认值是'\n'，即换行 # output: 1 2 3 情况4: 将字符列表合成一个字符串，需要用到join()函数
# res = ['a', 'b', 'c']# 输出是一个字符串print("".join(res))# output: abc# 输出是一个字符串，且用 * 号分隔print("*".join(res))# output: a*b*c# 如果用 print(res[i], end = '*') 的话，输出就是 a*b*c*了，在末尾还多了一个*3. 链表的输入输出
acm模式中的链表也是通过输入一个数组来模拟的，所以获取输入数据和前面没有什么不同。
主要在于定义链表结构、将输入数据转化为链表以及输出链表。
华为机试：从单向链表中删除指定值的节点
华为机试：输出单向链表中倒数第k个节点
# 定义链表结构class ListNode: def __init__(self,val,next=None): self.val = val self.next = next# 数组转链表def nums2ListNode(nums): dummy = ListNode(None) root = ListNode(nums[0]) dummy.next = root i = 1 while i < len(nums): node = ListNode(nums[i]) root.next = node root = root.next i += 1 root.next = None return dummy.next# 打印链表nums = [1,2,3,4,5]root = nums2ListNode(nums)while root: print(root.val) root = root.next4. 二叉树
4. 二叉树的输入输出
4.1 完全二叉树格式输入
acm模式中一般用输入一行数字代表一个二叉树，一般会以完全二叉树格式输入。这行数字的按照层序遍历的顺序排列，且其中空节点一般会用特定的符号表示，如0或是null
可以直接用数组表示二叉树，例如列表Tree, 将Tree[i]的左子树和右子树分别为Tree[2*i+1]和Tree[2*i+2]，不过会比较占用空间。
# 中序遍历def inorder_traversal(nums, index): if index >= len(nums) or nums[index] == -1: return left, right = 2 * index + 1, 2 * index + 2 inorder_traversal(nums, left) print(nums[index], end = ' ') inorder_traversal(nums, right) # 输入为 1 2 3 null 4 null 5# 1# / \# 2 3# \ \# 4 5if __name__ == "__main__": nums = input().split() nums = [int(num) if num != 'null' else -1 for num in nums] inorder_traversal(nums, 0) # output: 2 4 1 3 5 也可以用链表实现，更省空间，但操作更复杂一些。
# 定义二叉树类函数class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 由数组转二叉树def construct_binary_tree(nums, index): if index >= len(nums): return # -1作为空节点 if nums[index] == -1: return None left = index * 2 + 1 right = index * 2 + 2 root = TreeNode(nums[index]) root.left = construct_binary_tree(nums, left) root.right = construct_binary_tree(nums, right) return root# 中序遍历def inorder_traversal(root): if not root: return inorder_traversal(root.left) print(root.val, end=' ') inorder_traversal(root.right)# 输入为 1 2 3 null 4 null 5# 1# / \# 2 3# \ \# 4 5if __name__ == "__main__": nums = input().split() nums = [int(num) if num != 'null' else -1 for num in nums] root = construct_binary_tree(nums, 0) inorder_traversal(root) # output: 2 4 1 3 5 4.2 其他格式输入
有部分题目的输入格式不是完全二叉树，例如leetcode的二叉树格式，输入的数组虽然也是按照层序遍历的顺序，但并不是每一层的空节点都会表示出来，而是仅表示与非空节点连接的空节点。
# 数组转二叉树def construct_binary_tree(nums): # nums = ['1', '2', '3', 'null', 'null', 'null', '5'] if nums == []: return root = TreeNode(nums[0]) queue = collections.deque() queue.append(root) i = 1 while i < len(nums): node = queue.popleft() if i < len(nums) and nums[i] != -1: node.left = TreeNode(nums[i]) queue.append(node.left) i += 1 if i < len(nums) and nums[i] != -1: node.right = TreeNode(nums[i]) queue.append(node.right) i += 1 return root # 中序遍历def inorder_traversal(root): if not root: return inorder_traversal(root.left) print(root.val, end=' ') inorder_traversal(root.right) # 输入 1 null 1 null 1 2# 1# / \#null 1# / \# null 1# /# 2if __name__ == "__main__": nums = input().split() nums = [int(num) if num != 'null' else -1 for num in nums] root = construct_binary_tree(nums) inorder_traversal(root) # 输出 1 1 2 1参考博客
ACM模式笔试编程题Python3的输入和输出格式详解
ACM模式下链表、二叉树的输入Python实现
本文链接
http://t.csdn.cn/m7VMg
