小杨的握手问题
时间限制：1.0 s
内存限制：128.0 MB
问题描述
小杨的班级里共有N名同学，学号从0至N-1。
某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班N名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学号小于自己的同学握手。
现在，小杨想知道，整个班级总共会进行多少次握手。
提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。
输入描述
输入包含2行。第一行一个整数N，表示同学的个数；第二行N个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0~N-1之间，表示该同学的学号。
保证每位同学会且只会进入教室一次。
输出描述
输出一行一个整数，表示全班握手的总次数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4
2 1 3 0
样例输出 1
2
样例解释 1
2号同学进入教室，此时教室里没有其他同学。
1号同学进入教室，此时教室里有2号同学。1号同学的学号小于2号同学，因此他们之间不需要握手。
3号同学进入教室，此时教室里有1,2号同学。3号同学的学号比他们都大，因此3号同学需要分别和另外两位同学握手。
0号同学进入教室，此时教室里有1,2,3号同学。0号同学的学号比他们都小，因此0号同学不需要与其他同学握手。
综上所述全班一共握手0+0+2+0=2次。
样例输入 2
6
0 1 2 3 4 5
样例输出 2
15
样例解释 2
全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号是当前教室里最大的，所以他需要和教室里的每位其他同学进行握手。
数据规模
对于30%的测试点，保证N≤100。
对于所有测试点，保证2≤N≤3×105。
相似题推荐
给定一棵二叉树，采用广度优先搜索(BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def rightSideView(root):
rightmost_value_at_depth = {}
max_depth = -1
node_queue = []
depth_queue = []
node_queue.append(root)
depth_queue.append(0)
while node_queue:
node = node_queue.pop(0)
depth = depth_queue.pop(0)
if node is not None:
max_depth = max(max_depth, depth)
rightmost_value_at_depth[depth] = node.val
node_queue.append(node.left)
node_queue.append(node.right)
# (1) 填空处
depth_queue.append(depth + 1)
depth_queue.append(depth + 1)
right_view = []
# (2) 填空处
for depth in range(max_depth + 1):
right_view.append(rightmost_value_at_depth[depth])
return right_view
if __name__ == "__main__":
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))| A． （1）depth , depth ;（2）0 , max_depth |
B． （1）depth + 1 , depth + 1 ;（2）0 , max_depth + 1 |
| C． （1）depth + 1 , depth + 1 ;（2）1 , max_depth + 1 |
D． （1）depth , depth ;（2）1 , max_depth |
游乐园的过山车每次限坐4 人，用循环队列管理排队（容量MAX=5，空一格判满）。下面代码执行后，循环队列是否已满？rear 的值是多少？
MAX = 5
queue = [None] * MAX
front = 0
rear = 0
def enqueue(x):
global rear, queue
queue[rear] = x
rear = (rear + 1) % MAX
def dequeue():
global front
front = (front + 1) % MAX
if __name__ == "__main__":
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
dequeue()
dequeue()
enqueue(5)
enqueue(6)
print("队列数组: ", queue)
print("front下标位置: ", front)
print("rear下标位置: ", rear)| A． 已满，rear = 1 |
B． 未满，rear = 1 |
| C． 已满，rear = 2 |
D． 未满，rear = 4 |
设二叉树共有n个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder(root, res):
if root is None:
return
res.append(root.val)
preorder(root.left, res)
preorder(root.right, res)
def preorderTraversal(root):
res = []
preorder(root, res)
return res
if __name__ == "__main__":
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
result = preorderTraversal(root)
print("前序遍历结果: ", result) | A．正确 | B．错误 |
在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（）。
| A． 该树一定是一棵完全二叉树。 |
B． 元素4和5不可能是兄弟节点。 |
| C． 元素1所在节点的深度可能大于3（根节点深度为1）。 |
D． 元素2一定是元素1的父节点。 |
