2460

run.qq
lukehan
_6

kingsealaugh
dran
OnjoujiToki
RichardHJC

Minuet
OpenAll_Zzz
Barbed
itdef
yxc
Yuuujii

shanez
Mere

5小时前
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
d = defaultdict(list)
n, m = len(mat), len(mat[0])
for i in range(n):
for j in range(m):
d[i + j].append(mat[i][j])
res = []
for k, v in d.items():
if k % 2 == 0:
[res.append(x) for x in v[::-1]]
else:
[res.append(x) for x in v]
return res


8小时前
"""

"""

class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
start = '0000'
if start == target:
return 0
if start in S:
return -1
q = deque([start])
dist = defaultdict(int)
dist[start] = 0
while q:
t = q.popleft()
for i in range(4):
for j in [-1, 1]:
state = list(t)
state[i] = str((int(state[i]) + j) % 10)
key = ''.join(state)
if dist[key] == 0 and key not in S:
dist[key] = dist[t] + 1
if key == target:
return dist[key]
q.append(key)
return -1


11小时前
"""

f(i) 玩完前i天最后一张票以i结尾
"""

class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
n = len(days)
f = [0] * (n + 1)
a = b = c = 0
for i in range(1, n + 1):
while days[i - 1] - days[a] >= 1:
a += 1
while days[i - 1] - days[b] >= 7:
b += 1
while days[i - 1] - days[c] >= 30:
c += 1
f[i] = min(f[a] + costs[0], f[b] + costs[1], f[c] + costs[2])
return f[n]


14小时前
"""
TLE
"""

def main():
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
res = float('inf')
for i in range(n):
p1 = p[:i] + p[i + 1:]
minx = min(x[0] for x in p1)
maxx = max(x[0] for x in p1)
miny = min(x[1] for x in p1)
maxy = max(x[1] for x in p1)
a = (maxx - minx) * (maxy - miny)
res = min(res, a)
print(res)

main()


1天前
"""
DP
状态表示 f(i, j)
集合：所有由前i个字母构成且结尾为j的所有不同方案的集合
属性：数量
状态计算
分成两类
a[i] != j
f(i - 1, j)
a[i] == j
倒数第二个字母
空       1
'a'
'b'
'c'
...      k   最后一个字母是a[i]. 倒数第二个字母为k： f(i - 1, k)
'z'

算出以a[i] 结尾的集合后，证明以a[i] 结尾的集合 == 以j结尾的集合
"""

class Solution:
def distinctSubseqII(self, s: str) -> int:
MOD = 10 ** 9 + 7
f = [0] * 26
for c in s:
x = ord(c) - ord('a')
t = 1
for i in range(26):
t = (t + f[i]) % MOD
f[x] = t

res = 0
for x in f:
res = (res + x) % MOD
return res


1天前
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
w = []
for x, y in zip(quality, wage):
w.append([y / x, x])
w.sort()
heap = []
res = float('inf')
s = 0
for r, q in w:
s += q
heappush(heap, -q)
if len(heap) > k:
s += heappop(heap)
if len(heap) == k:
res = min(res, s * r)
return res


1天前
"""

& 的结果不超过它们本身

s 用list会超时，改用Counter，dict都行
"""

class Solution:
def countTriplets(self, nums: List[int]) -> int:
n = len(nums)
s = Counter()
for i in range(n):
for j in range(n):
s[nums[i] & nums[j]] += 1
res = 0
for k in range(n):
for x in s:
if not nums[k] & x:
res += s[x]
return res


1天前
def main():
n = int(input())
r = [int(input()) for _ in range(n)]
tot = sum(r)
avg = tot / n
r = [0] + r * 2
s = [0] * (n * 2 + 1)
for i in range(1, n * 2 + 1):
s[i] = s[i - 1] + r[i] - avg

k = 0
for i in range(1, n + 1):
if s[i] < s[k]:
k = i
k += 1
res = 0
for i in range(n):
res += i * r[k + i]

print(res)

main()


2天前
"""
O(4 * 3 * 4 * 3 * 2 * 4 * 2 * 4) = 9216
4 * 3: 四个数挑两个
* 4 四种运算

* 4 四种运算

* 4 四种运算

"""

class Solution:
def judgePoint24(self, cards: List[int]) -> bool:
def get(nums, i, j, x):
res = []
for k in range(len(nums)):
if k != i and k != j:
res.append(nums[k])
res.append(x)
return res

def dfs(nums):
if len(nums) == 1:
return abs(nums[0] - 24) < 1e-8
for i in range(len(nums)):
for j in range(len(nums)):
if i != j:
a, b = nums[i], nums[j]
if dfs(get(nums, i, j, a + b)):
return True
if dfs(get(nums, i, j, a - b)):
return True
if dfs(get(nums, i, j, a * b)):
return True
if b and dfs(get(nums, i, j, a / b)):
return True
return False
return dfs(cards)


2天前
"""
|________________|________|_____
0                k         n

f(i) = 1 / w * (f(i + 1) + f(i + 2) + ... + f(i + w))

f(i + 1) = 1 / w * (f(i + 2) + f(i + 2) + ... + f(i + w) + f(i + w + 1))

O(n)
"""

class Solution:
def new21Game(self, n: int, k: int, w: int) -> float:
if k == 0:
return 1
f = [0] * 20010
for i in range(k, n + 1):
f[i] = 1
for i in range(1, w + 1):
f[k - 1] += f[k - 1 + i] / w
for i in range(k - 2, -1, -1):
f[i] = f[i + 1] + (f[i + 1] - f[i + w + 1]) / w
return f[0]