一、水库抽样算法

给你一个未知长度的单链表，请你设计一个算法，只能遍历一次，随机地返回连表中的一个节点，这里的随机是要求每个节点被返回的概率是1/n。

下面给出一个示例：

python">import randomclass ListNode:def __init__(self, value=0, next=None):self.val = valueself.next = nextdef get_random_node(head):if not head:return Nonerandom_node = headcurrent = headn = 1while current:if random.randint(1, n) == 1:random_node = currentcurrent = current.nextn += 1return random_node# 使用示例
# 创建一个简单的链表：1 -> 2 -> 3 -> 4
node4 = ListNode(4)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)# 获取随机节点
random_node = get_random_node(node1)
print("随机选中的节点值为:", random_node.val)

算法解释：

• random_node 初始化为链表的头部节点。
• 随着链表的遍历，逐步更新计数器 n，并在每个节点上以 1/n 的概率更新 random_node。
• 最终，当遍历结束时，random_node 包含了以均等概率选择的链表中的一个节点，多次运行之后，random_node节点应该是均等选择各个节点。

这种方法确保了每个节点被选中的概率是均等的，即 1/n，其中 n 是链表的长度。这样做的优点是我们不需要知道链表的长度，也不需要存储额外的数据结构，从而保持了空间复杂度为 O(1)，时间复杂度为 O(n)。

二、bingo棋盘

1、假设你有一个5*5的棋盘，第一行可选1-15之间的数字，第二行可选16-30的数字，后面的行依次类推，每一行的数字都不能重复，只能使用random(x,y)函数来确定每个位置的数字，random(x,y)函数会生成x-y之间的随机数，要求能够构造出所有可能且有效的棋盘。

第一问感觉还是比较简单的，这里描述一下自己的思路，不一定是正确的：

定义列表number = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

• 选择第一个数时，使用random(1, 15)生成一个随机数，假如生成的结果是4，将第4个位置对应的数字4和number的最后一个数字15交换，此时number = [1, 2, 3, 15, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 4]。
• 选择第二个数时，使用random(1, 14)生成一个随机数，假如生成的结果是1，将第1个位置对应的数字1和number的倒数第二个数字14交换，此时number = [14, 2, 3, 15, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 4]。
• 选择第三个数时，使用random(1, 13)生成一个随机数，假如生成的结果是4，将第4个位置对应的数字15和number的倒数第三个数字13交换，此时number = [14, 2, 3, 13, 5, 6, 7, 8, 9, 10, 11, 12, 15, 1, 4]。
• 这样执行五轮次之后，假设number = [14, 2, 3, 13, 12, 6, 7, 8, 11, 10, 9, 5, 15, 1, 4]，此时number的最后五个数字就可以作为棋盘的第一行的数字，并且是随机且无重复的，这种方法理论上是可以取遍所有情况的。
• 同样，其他行按照此方法进行操作。

python">import randomdef generate_board_row(start, end):numbers = list(range(start, end + 1))row = []for i in range(5):# 随机选取一个位置的数字pick_index = random.randint(0, len(numbers) - 1 - i)# 将选中的数字添加到行中row.append(numbers[pick_index])# 将选中的数字和当前最后一个可选数字交换numbers[pick_index], numbers[-1 - i] = numbers[-1 - i], numbers[pick_index]return rowdef generate_full_board():board = []for i in range(5):start = i * 15 + 1end = start + 14row = generate_board_row(start, end)board.append(row)return board# 生成棋盘并打印结果
board = generate_full_board()
for row in board:print(row)

2、如果你现在有5个棋盘呢？要保证五个棋盘都是随机，并且五个棋盘都不一样（只要有一个元素不一样，就认为棋盘不一样）

这个题目我的方法是按照上面只有一个棋盘时选择第一行的方法，现在改为使用上面的方法选择五个棋盘的第一行的第一个元素，通过上面的方法可以保证五个棋盘第一行第一个元素值不同，这样就可以保证五个棋盘是不同的，然后第一个棋盘第一个元素选定之后，使用number1列表记录所选择的元素，并放在最后，同样，其他棋盘的第一行选定之后，都使用一个number列表记录所选择数字并将其放在最后。当五个棋盘第一个数字都选定之后，再依次按照对应的number列表选择每个棋盘第一行的其他元素。

python">import randomdef initialize_numbers(start, end):return list(range(start, end + 1))def pick_unique_first_elements(numbers_list, count):picked = []for _ in range(count):index = random.randint(0, len(numbers_list) - 1)picked.append(numbers_list.pop(index))return pickeddef generate_row(numbers, already_picked):row = [already_picked]numbers.remove(already_picked)for _ in range(4):pick_index = random.randint(0, len(numbers) - 1)row.append(numbers[pick_index])numbers[pick_index], numbers[-1] = numbers[-1], numbers[pick_index]numbers.pop()return rowdef generate_full_board(first_elements):boards = []for first_element in first_elements:board = []start = 1for i in range(5):end = start + 14numbers = initialize_numbers(start, end)if i == 0:row = generate_row(numbers, first_element)else:row = generate_row(numbers, numbers[random.randint(0, 14)])board.append(row)start += 15boards.append(board)return boards# 初始化第一行的所有可能数字
first_row_numbers = initialize_numbers(1, 15)
# 为五个棋盘挑选不同的第一个元素
first_elements = pick_unique_first_elements(first_row_numbers, 5)# 生成五个不同的棋盘
boards = generate_full_board(first_elements)# 打印棋盘
for i, board in enumerate(boards):print(f"Board {i+1}:")for row in board:print(row)print()# 输出
Board 1:
[2, 12, 5, 6, 14]
[20, 22, 25, 30, 23]
[37, 31, 42, 35, 36]
[49, 58, 59, 55, 48]
[68, 67, 65, 75, 74]Board 2:
[3, 8, 4, 6, 11]
[25, 20, 24, 23, 30]
[37, 36, 44, 39, 42]
[47, 59, 50, 52, 48]
[65, 72, 68, 74, 67]Board 3:
[12, 10, 4, 5, 9]
[25, 22, 19, 20, 24]
[33, 43, 35, 40, 45]
[50, 57, 60, 54, 51]
[61, 75, 64, 65, 67]Board 4:
[4, 2, 3, 1, 14]
[29, 22, 27, 18, 23]
[43, 38, 31, 45, 44]
[50, 59, 54, 53, 46]
[73, 67, 75, 61, 63]Board 5:
[13, 5, 12, 3, 9]
[19, 23, 29, 27, 22]
[40, 37, 43, 42, 45]
[53, 60, 47, 59, 56]
[62, 65, 68, 70, 73]