"9001 discuss.leetcode.com"

class Solution:
def subdomainVisits(self, cpdomains):
"""
:type cpdomains: List[str]
:rtype: List[str]
"""
cnt = collections.defaultdict(int)
for cp in cpdomains:
n, addr = cp.split(' ')
n, addr, p = int(n), '.'+addr, 0
while p != -1:
return ['{} {}'.format(v, k) for k, v in cnt.items()]


class Solution:
def expressiveWords(self, S, words):
"""
:type S: str
:type words: List[str]
:rtype: int
"""
def group(word):
return [''.join(g) for _, g in itertools.groupby(word)]

ps= group(S)
def check(word):
pw = group(word)
if len(ps) != len(pw):
return False
for a, b in zip(ps, pw):
if a[0] != b[0] or len(a) < len(b):
return False
if len(a) == 2 and a != b:
return False
return True

return sum(check(word) for word in words)


1. 消耗100ml汤A和0ml汤B
2. 消耗75ml汤A和25ml汤B
3. 消耗50ml汤A和50ml汤B
4. 消耗25ml汤A和75ml汤B

$$P(n, m) = 0.25(P(n-4, m)+P(n-3, m-1)+P(n-2, m-2)+P(n-1, m-3))$$

$f(n, m) = a+0.5c$, 其中$<a, b, c> = P(n, m)$. 那么$f(n, m)$同样满足上述递推公式：

$$f(n, m) = 0.25(f(n-4, m)+f(n-3, m-1)+f(n-2, m-2)+f(n-1, m-3))$$

class Solution:
def soupServings(self, N):
"""
:type N: int
:rtype: float
"""
N = (N+24) // 25

memo = {}
def f(n, m):
if n <= 0 and m <= 0:
return 0.5
if n <= 0 or 2*N-m-n > 400:
return 1.0
if m <= 0:
return 0
if (n,  m) in memo:
return memo[n, m]
memo[n, m] = 0.25 * sum(f(n+i-4, m-i) for i in range(4))
return memo[n, m]

return f(N, N)


class Solution:
def xorGame(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
x = 0
for n in nums:
x ^= n
return x == 0 or len(nums) & 1 == 0