头像

秀策




离线:1小时前


最近来访(67)
用户头像
人间凑数
用户头像
_6
用户头像
Minuet
用户头像
OpenAll_Zzz
用户头像
Barbed
用户头像
itdef
用户头像
yxc
用户头像
Yuuujii
用户头像
褐色.x.
用户头像
伍六柒_6
用户头像
shanez
用户头像
Mere
用户头像
航_0
用户头像
kingsealaugh
用户头像
Na.
用户头像
打十铜人ing
用户头像
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)


活动打卡代码 AcWing 655. 输出二叉树

秀策
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)


活动打卡代码 AcWing 1945. 奶牛棒球

秀策
12小时前
"""
数据范围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. 最短的桥

秀策
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]':
        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地址

秀策
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)