2131

_6
Minuet
OpenAll_Zzz
Barbed
itdef
yxc
Yuuujii

shanez
Mere

kingsealaugh
Na.

notion

IER

5小时前
"""
O(nlogn)
"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
global S
S = defaultdict(list)

self.dfs(root, 0, 0)
ans = []
for y in sorted(S.keys()):
ans.append([x[1] for x in sorted(S[y])])
return ans

def dfs(self, root, x, y):
if not root:
return
S[y].append([x, root.val])
self.dfs(root.left, x + 1, y - 1)
self.dfs(root.right, x + 1, y + 1)


5小时前
"""
1. 确定h, w
h = max(lh, rh)
w = max(lw, rw) * 2 + 1
2. 递归
"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
global ans
h, w = self.dfs(root)
ans = [[''] * w for _ in range(h)]
self.myprint(root, 0, 0, w - 1)
return ans

def dfs(self, root):
if not root:
return 0, 0
lh, lw = self.dfs(root.left)
rh, rw = self.dfs(root.right)
return max(lh, rh) + 1, max(lw, rw) * 2 + 1

def myprint(self, root, h, l, r):
if not root:
return
mid = l + r >> 1
ans[h][mid] = str(root.val)
self.myprint(root.left, h + 1, l, mid - 1)
self.myprint(root.right, h + 1, mid + 1, r)


12小时前
"""

z的范围为 2y - x <= z <= 3y - x
2y - x <= 3y - x -> x <= y所以一定有解

｜————————————————｜————｜————｜————｜——————————｜
y   y'     l'    l

假设当y走到y'，有l' 可以比l取到更靠左为位置
由于 y' > y （因为y严格递增）
l' - y > l' - y' >= y' - x >= y - x
则有 l' - y >= y - x
说明可以找到比l更左的l'也满足条件，则与l是最靠左的满足条件的定义矛盾

"""

def main():
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()

res = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
p = q = j + 1
while p < n and a[p] - a[j] < a[j] - a[i]:
p += 1
while q < n and a[q] - a[j] <= (a[j] - a[i]) * 2:
q += 1
res += q - p
print(res)

main()


1天前
class Solution:
def shortestBridge(self, _g: List[List[int]]) -> int:
global g, n, m, dx, dy, dist, q
g = _g
n, m = len(g), len(g[0])
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
q = deque()
dist = [[1e8] * m for _ in range(n)]

for i in range(n):
for j in range(m):
if g[i][j]:
self.dfs(i, j)
return self.bfs()

return -1

def dfs(self, x, y):
global q
g[x][y] = 0
dist[x][y] = 0
q.append([x, y])
for i in range(4):
a, b = x + dx[i], y + dy[i]
if 0 <= a < n and 0 <= b < m and g[a][b]:
self.dfs(a, b)

def bfs(self):
global q
while q:
x, y = q.popleft()
for i in range(4):
a, b = x + dx[i], y + dy[i]
if 0 <= a < n and 0 <= b < m and dist[a][b] > dist[x][y] + 1:
dist[a][b] = dist[x][y] + 1
if g[a][b]:
return dist[a][b] - 1
q.append([a, b])
return -1

"""
AcWing 2060.奶牛选美 代码照搬
lc美服tle

"""

class Solution:
def shortestBridge(self, g: List[List[int]]) -> int:
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
n, m = len(g), len(g[0])

def dfs(x, y, ps):
g[x][y] = 0
ps.append((x, y))
for i in range(4):
a, b = x + dx[i], y + dy[i]
if 0 <= a < n and 0 <= b < m and g[a][b]:
dfs(a, b, ps)

k = 0
points = [[], []]
for i in range(n):
for j in range(m):
if g[i][j]:
dfs(i, j, points[k])
k += 1
res = 1e8
for x1, y1 in points[0]:
for x2, y2 in points[1]:
res = min(res, abs(x1 - x2) + abs(y1 - y2) - 1)
return res


1天前
"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""

class Solution:
def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
return res[0]

return None, None

while cur:
tail = cur
if cur.child:
t = self.dfs(cur.child)
cur.child = None
t[1].next = cur.next
if cur.next:
cur.next.prev = t[1]
cur.next = t[0]
t[0].prev = cur
cur = t[1].next
tail = t[1]
else:
cur = cur.next


1天前
class Solution:
def validIPAddress(self, ip: str) -> str:
if '.' in ip and ':' in ip:
return 'Neither'
if '.' in ip:
return self.check_ipv4(ip)
if ':' in ip:
return self.check_ipv6(ip)
return 'Neither'

def check_ipv4(self, ip):
items = ip.split('.')
if len(items) != 4:
return 'Neither'
for item in items:
if not item or len(item) > 3:
return 'Neither'
if len(item) > 1 and item[0] == '0':
return 'Neither'
for c in item:
if not c.isdigit():
return 'Neither'
t = int(item)
if t > 255:
return 'Neither'
return 'IPv4'

def check_ipv6(self, ip):
items = ip.split(':')
if len(items) != 8:
return 'Neither'
for item in items:
if not item or len(item) > 4:
return 'Neither'
for c in item:
if not self.check(c):
return 'Neither'
return 'IPv6'

def check(self, c):
if c.isdigit():
return True
if 'a' <= c <= 'f' or 'A' <= c <= 'F':
return True
return False


1天前
"""
O(n)
"""

class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l + 1 < len(nums) and nums[l + 1] >= nums[l]:
l += 1
if l == r:
return 0
while r - 1 >= 0 and nums[r - 1] <= nums[r]:
r -= 1

for i in range(l + 1, len(nums)):
while l >= 0 and nums[l] > nums[i]:
l -= 1
for i in range(r - 1, -1, -1):
while r < len(nums) and nums[r] < nums[i]:
r += 1
return r - l - 1


1天前
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = s[i - 1] + nums[i - 1]
h = defaultdict(int)
h[0] = 1
res = 0
for i in range(1, n + 1):
res += h[s[i] - k]
h[s[i]] += 1
return res


2天前
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root:
return 0
val = root.val
if low <= val <= high:
return val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
elif val < low:
return self.rangeSumBST(root.right, low, high)
return self.rangeSumBST(root.left, low, high)


2天前
N = 19997

class MyHashMap:

def __init__(self):
self.h = [[] for _ in range(N)]

def put(self, key: int, val: int) -> None:
h = self.h
t = key % N
k = self.find(h[t], key)
if k == -1:
h[t].append([key, val])
else:
h[t][k][1] = val

def get(self, key: int) -> int:
h = self.h
t = key % N
k = self.find(h[t], key)
if k == -1:
return -1
return h[t][k][1]

def remove(self, key: int) -> None:
h = self.h
t = key % N
k = self.find(h[t], key)
if k != -1:
h[t].pop(k)

def find(self, h, key):
if not h:
return -1
for i in range(len(h)):
if h[i][0] == key:
return i
return -1

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)