Учитывая список чисел, большинство больше половины. Если мы случайным образом выберем число из чисел, какова вероятность того, что хотя бы одно число является числом большинства?
Вероятно, это должно быть 1- (каждое выбранное число не является большинством)
1-(1-P(большинство))**n
Поскольку P(большинство) ≥0,5
1-(1-P(большинство))**n ≤(1–0,5**n)
Мы можем получить результат n и верхнюю границу 1-(1-P(большинство))**n
>>> for n in range(1, 21): ... print(n, ":", 1-0.5**n) ... 1 : 0.5 2 : 0.75 3 : 0.875 4 : 0.9375 5 : 0.96875 6 : 0.984375 7 : 0.9921875 8 : 0.99609375 9 : 0.998046875 10 : 0.9990234375 11 : 0.99951171875 12 : 0.999755859375 13 : 0.9998779296875 14 : 0.99993896484375 15 : 0.999969482421875 16 : 0.9999847412109375 17 : 0.9999923706054688 18 : 0.9999961853027344 19 : 0.9999980926513672 20 : 0.9999990463256836
Это означает, что если мы случайным образом выберем 20 чисел, хотя бы одно из них является вероятностью большинства, может быть 0,9999990463256836.
Одна проблема с буквенным кодом связана с этой базовой вероятностью.
1157. Элемент онлайн-большинства в подмассиве
У меня есть следующий код, однако он получил TLE.
21 из 27 тестовых случаев пройдено.
class MajorityChecker:
def __init__(self, arr: List[int]):
self.arr = arr
self.i_v_cnt = collections.defaultdict(lambda :collections.defaultdict(int))
self.i_v_cnt[0][arr[0]] +=1
for i in range(1, len(arr)):
v = arr[i]
###need deep copy this line will generate a shallow copy
#self.i_v_cnt[i] =self.i_v_cnt[i-1]
#### this is deep copy
self.i_v_cnt[i] = copy.deepcopy(self.i_v_cnt[i-1])
self.i_v_cnt[i][v] += 1
def query(self, left: int, right: int, threshold: int) -> int:
from random import randrange
this_arr = [self.arr[i] for i in (randrange(left, right+1) for _ in range(20))]
for num in set(this_arr):
if self.i_v_cnt[right][num] - self.i_v_cnt[left-1][num] >=threshold:return num
return -1
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)
Причина может заключаться в том, что размер self.i_v_cnt может быть очень большим. Поскольку максимальная длина arr будет составлять 20 000, а в худшем случае — 10 000 уникальных номеров. Это сделает self.i_v_cnt очень большим.
Вдохновлен
Мы можем сохранить только индекс num в обр. Затем разделите его пополам на индексы, чтобы найти вхождение этого числа в область видимости.
Решение, основанное на идеях выше
Время выполнения: 1548 мс, быстрее, чем 6,95% онлайн-заявок Python3 для онлайн-элемента большинства в подмассиве.
class MajorityChecker:
def __init__(self, arr: List[int]):
a2i = collections.defaultdict(list)
for i, x in enumerate(arr):
a2i[x].append(i)
self.arr, self.a2i = arr, a2i
def query(self, left: int, right: int, threshold: int) -> int:
from random import randrange
this_arr = [self.arr[i] for i in (randrange(left, right+1) for _ in range(40))]
def get_count(a):
idxes = self.a2i[a]
return bisect.bisect(idxes, right) - bisect.bisect_left(idxes, left)
for num in set(this_arr):
count = get_count(num)
if count>=threshold: return num
return -1
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)
Еще один, связанный с использованием вероятности.
837. Новая 21 игра
https://leetcode.com/problems/new-21-game/
Наивная DFS получит TLE.
Пройдено 86 из 146 тестов.
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
res = []
total = []
def dfs(remain, cur_pro):
if remain==1:
total.append(cur_pro)
valid = sum(K-1+w<=N for w in range(1, W+1))
res.append(cur_pro*valid/W)
elif remain<=0:
total.append(cur_pro)
if K-remain<=N:res.append(cur_pro)
else:
for w in range(1, W+1):
dfs(remain-w, cur_pro/W)
dfs (K, 1)
return sum(res)/sum(total)
Использование кеша также дало TLE, но добавило еще 10 тестов AC
Пройдено 96 из 146 тестов.
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
from functools import lru_cache
@lru_cache(None)
def dfs(remain):
if remain==1:
valid = sum(K-1+w<=N for w in range(1, W+1))
return 1, valid/W
elif remain<=0:
return 1, K-remain<=N
else:
total, res = 0, 0
for w in range(1, W+1):
this_remain =remain- w
this_total, this_res = dfs(this_remain)
total += this_total/W
res += this_res/W
return total, res
total, res = dfs(K)
return res/total
Этот код, скорректированный из поста ниже, также получил TLE.
Сложность O((K + W) * W)
Пройдено 96 из 146 тестов.
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
if K == 0 or N >= K + W: return 1
max_ = K + W - 1
dp = [0]*(max_+1)
dp[0] = 1
for i in range(1, max_+1):
for j in range(1, W+1):
if i-j>=0 and i-j<K:
dp[i] += dp[i-j]/W
return sum(dp[i] for i in range(K, N+1))
Затем я понимаю, что уравнение перехода dp[i] = (dp[i - W] + dp[i - W + 1] + ... + dp[i - 1]) / W можно упростить до dp[i] = (sum[i - 1] - sum[i - W - 1]) / W.
Кроме того, если мы используем dp[i] для прямого представления sum[i], мы можем получить dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - W - 1]) / W. Это уравнение приводит нас к окончательному O(K + W) решению. Просто позаботьтесь о начале и конце массива.
dp (200 ms)
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
if K == 0 or N >= K + W: return 1
max_ = K + W - 1
dp = [0]*(max_+1)
dp[0] = 1
for i in range(1, max_+1):
dp[i] = dp[i-1]
if i<=W:
dp[i] += dp[i-1]/W
else:
dp[i] += (dp[i-1]-dp[i-W-1]) / W
if i>K:
dp[i] -= (dp[i-1]-dp[K-1])/W
return dp[N]-dp[K-1]
Наконец, из поста от lee215 я понял, что это проблема DP. Временная сложность, если O(n) и код по ссылке ниже
https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)
Время выполнения (70 мс)
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
if K == 0 or N >= K + W: return 1
dp = [1.0] + [0.0] * N
Wsum = 1.0
for i in range(1, N + 1):
dp[i] = Wsum / W
if i < K: Wsum += dp[i]
if i - W >= 0: Wsum -= dp[i - W]
return sum(dp[K:])
Или другой DP (60 мс)
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
dp = [0.0] * (N + W + 1)
# dp[x] = the answer when Alice has x points
for k in range(K, N + 1):
dp[k] = 1.0
S = min(N - K + 1, W)
# S = dp[k+1] + dp[k+2] + ... + dp[k+W]
for k in range(K - 1, -1, -1):
dp[k] = S / W
S += dp[k] - dp[k + W]
return dp[0]
Этот пост хорош.
https://leetcode.com/problems/new-21-game/discuss/437832/Python-DP-iterate-on-points-rather-than-draw-count.-Should-be-a- жесткий -проблема
Я скопировал содержимое, как показано ниже:
«dp(n) означает вероятность получения точки «n» при любом количестве розыгрышей.
например. когда случайное число равно 1~3, мы имеем:
dp(n)=dp(n-3)*(1/3)+dp(n-2)*(1/3)+dp(n- 1)*(1/3)
И этот вид суммы можно оптимизировать с помощью суммы скользящего окна.
Мы не можем итерировать DP при подсчете отрисовки, потому что трудно решить, когда прекратить итерацию. Вместо этого мы повторяем полученную точку, потому что каждая точка может быть получена по значению dp предыдущих точек.
Эта задача должна быть «сложной», а не «средней».
def new21Game(self, N: int, K: int, W: int) -> float:
if K==0 or K-1+W<=N:
return 1
dp=[1]+[0]*N
cursum=1
for i in range(1,N+1):
# dp[i]=sum(dp[max(0,i-W):min(i,K)])*(1/W)
dp[i]=cursum*(1/W)
if i<K:
cursum+=dp[i]
if i>=W:
cursum-=dp[i-W]
return sum(dp[K:])808. Порции супа
from functools import lru_cache
class Solution:
def soupServings(self, N: int) -> float:
if N > 4800: return 1
@lru_cache(None)
def f(a, b):
if a <= 0 and b <= 0: return 0.5
if a <= 0: return 1
if b <= 0: return 0
return (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3))/4
N = math.ceil(N / 25)
return f(N, N)
Спасибо за чтение.
