已經(jīng)工作了，義務(wù)支援下一屆，哈哈，好久不刷題還真有點生疏。Hulu今年秋招的題目并不難，一共四個編程題，基本是在常規(guī)問題上的延伸。今天先整理第一個題目，其他題目后面有時間繼續(xù)整理。

問題描述：

Hulu殺

有 n 個葫蘆娃一起玩Hulu殺，他們被分為好人和壞人兩個陣營，打亂之后圍成一個圈，按照順時針序編號為 0~n-1 。然后隨機選定一個葫蘆娃，從他/她開始由1到m順時針報數(shù)，數(shù)到m的人被殺，下一個人繼續(xù)從1報數(shù)，如此循環(huán)直到剩下最后一個人，這個人所屬陣營獲得勝利。我們用一個整型數(shù)組a[i]=1表示i是好人，a[i]=0表示i是壞人；整型數(shù)組w[i]表示玩家i被選為起始位置的權(quán)重，即玩家i有w[i]/sum(w[i])的概率做起始位置。求好人獲勝的概率，四舍五入到小數(shù)點后五位數(shù)字（不足五位需要補零）

示例 1:
輸入:

# 第一行為2個空格分開的整數(shù)，分別表示n和m # 第二行為n個空格分開的整數(shù)，表示a[i] # 第二行為n個空格分開的整數(shù)，表示w[i] # 輸入范圍0<m<n<=1000, 0<sum(w[i])<=10000000 ------------------------------------------- 3 2 0 0 1 2 1 1

輸出:

# 輸出一個浮點數(shù)，表示好人獲勝的概率 ------------------------------------------- 0.50000

問題分析：

很顯然，這是一個經(jīng)典的約瑟夫環(huán)問題的延伸，只要在約瑟夫環(huán)問題求解基礎(chǔ)上，加上一層映射關(guān)系即可得出答案。具體思路如下：
（1）先求出以第一個人開始，最后剩下的人（也就是約瑟夫環(huán)求解）
（2）在（1）的基礎(chǔ)上求出每個起始位置，最后剩下的人（人）
（3）在（2）的基礎(chǔ)上求出每個起始位置對應(yīng)的是好人獲勝還是壞人獲勝
（4）在（3）的基礎(chǔ)上求出每個起始位置對應(yīng)的好人獲勝的概率（權(quán)重求和即可），然后計算：好人獲勝的概率(權(quán)重) / 總的概率(權(quán)重)即可得出答案。

注意： 輸出要求應(yīng)該是字符串

Python實現(xiàn) AC：

# ============================================================= # !/usr/bin/python # -*- coding=utf-8 -*- # Name: HuluKill # Description: Hulu 2020年校招 筆試題(1) -- Hulu殺 # Author: yinxing # Date: 2019-09-05 19:00 # =============================================================class HuluKill:def JosephRing(self, n, m):"""約瑟夫環(huán)問題求解:param n: n 個人(0, 1, 2 ... n-1):param m: 每 m 人出列:return: 最后剩下的那個人索引"""if n < 1 or m < 1: return -1last = 0for i in range(2, n+1):last = (last + m) % ireturn lastdef Solution(self, n, m, a, w):"""獲取Hulu殺的解:param n: n 個人(0, 1, 2 ... n-1):param m: 每 m 人出列:param a: 好人，壞人列表:param w: 開始的權(quán)重:return: 好人隊獲勝的概率(保留5位小數(shù))"""victory = self.JosephRing(n, m) # 獲取選擇第一個人開始，最后剩下的人(索引)victorylist = [(victory+i) % n for i in range(n)] # 每個位置開始，對應(yīng)獲勝的人peoplelist = [a[victorylist[i]] for i in range(n)] # 每個位置開始，對應(yīng)勝利的人(好人，壞人)GoodPerson = sum([w[i] for i in range(n) if peoplelist[i] == 1]) # 好人獲勝的概率(權(quán)重)return '%.5f' % (GoodPerson/sum(w)) # 結(jié)果 = 好人獲勝的概率(權(quán)重) / 總的概率(權(quán)重)if __name__ == '__main__':hulukill = HuluKill()# n, m = map(int, input().split())# a = list(map(int, input().split()))# w = list(map(int, input().split()))n, m = 3, 2a = [0, 0, 1]w = [2, 1, 1]print(hulukill.Solution(n, m, a, w)) # 0.50000

聲明： 總結(jié)學(xué)習(xí)，有問題或不當(dāng)之處，可以批評指正哦，謝謝。

總結(jié)

以上是生活随笔為你收集整理的Hulu 2020年校招-算法题《Hulu杀》Python的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。