"""
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)
活动打卡代码
LeetCode 987. 二叉树的垂序遍历
活动打卡代码
AcWing 655. 输出二叉树
"""
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)
活动打卡代码
AcWing 1945. 奶牛棒球
"""
数据范围3 ≤ N ≤ 1000 暗示了算法的时间复杂度是n方或这nlogn
可以想到是否可以用二分，或者双指针
题目要求 y - x <= z - y <= 2 (y - x)
枚举x, y为n方时间复杂度，二分找z就是logn复杂度
z的范围为 2y - x <= z <= 3y - x
2y - x <= 3y - x -> x <= y所以一定有解
求z：找 >= 2y - x的最小值和 > 3y - x的最小值前面一个位置
进一步优化考虑是否可以使用双指针将y，z的时间复杂度nlogn降为n
双指针的充要条件是 两个指针都是单调的
当枚举x，选定了x，指针y往后走，z的指针是否也单调往后走
｜————————————————｜————｜————｜————｜——————————｜
y y' l' l
以找 >= 2y - x的最小值为例，假设l为满足条件的最小值
则有 y - x <= l - y -> l - y >= y - x
反证法：
假设当y走到y'，有l' 可以比l取到更靠左为位置
由于 y' > y （因为y严格递增）
l' - y > l' - y' >= y' - x >= y - x
则有 l' - y >= y - x
说明可以找到比l更左的l'也满足条件，则与l是最靠左的满足条件的定义矛盾
所以 当y单调递增向右移动，l的指针也单调递增向右移动
同理可以证明 找> 3y - x的最小值的指针也是单调递增向右移动
所以可以用双指针来做
"""
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()
活动打卡代码
LeetCode 934. 最短的桥
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
活动打卡代码
LeetCode 430. 扁平化多级双向链表
"""
# 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]':
res = self.dfs(head)
return res[0]
def dfs(self, head):
if not head:
return None, None
tail = cur = head
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
return head, tail
活动打卡代码
LeetCode 468. 验证IP地址
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
活动打卡代码
LeetCode 581. 最短无序连续子数组
"""
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
活动打卡代码
LeetCode 560. 和为K的子数组
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
活动打卡代码
LeetCode 938. 二叉搜索树的范围和
# 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)
活动打卡代码
LeetCode 706. 设计哈希映射
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)
