头像

秀策




离线:3小时前


最近来访(76)
用户头像
嘴平衡之助
用户头像
run.qq
用户头像
lukehan
用户头像
_6
用户头像
茶颜悦色
用户头像
kingsealaugh
用户头像
dran
用户头像
OnjoujiToki
用户头像
RichardHJC
用户头像
人间凑数
用户头像
Minuet
用户头像
OpenAll_Zzz
用户头像
Barbed
用户头像
itdef
用户头像
yxc
用户头像
Yuuujii
用户头像
褐色.x.
用户头像
伍六柒_6
用户头像
shanez
用户头像
Mere

活动打卡代码 LeetCode 498. 对角线遍历

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


活动打卡代码 LeetCode 752. 打开转盘锁

秀策
8小时前
"""
无向图求最短路 - 边权为1: BFS
"""


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        start = '0000'
        if start == target:
            return 0
        S = set(deadends)
        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


活动打卡代码 LeetCode 983. 最低票价

秀策
11小时前
"""
序列DP
    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]


活动打卡代码 AcWing 1826. 农田缩减

秀策
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天前
"""
直接枚举三位 1 <= nums.length <= 1000, 10 ^ 9 会超时
空间换时间,枚举两位,10 ^ 6 ,方案数为100万
但是数值的范围是 0 <= nums[i] < 2 ^ 16 = 65536
所以 枚举两位,Ai, Aj, 计算 Ai & Aj,需要存的Ai & Aj的个位数为 65536
& 的结果不超过它们本身
再枚举第三位,时间复杂度为 65536 * 1000 = 6.5536 e+7 可以过
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


活动打卡代码 AcWing 1843. 圆形牛棚

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


活动打卡代码 LeetCode 679. 24 点游戏

秀策
2天前
"""
O(4 * 3 * 4 * 3 * 2 * 4 * 2 * 4) = 9216
4 * 3: 四个数挑两个
* 4 四种运算
计算完后剩下2个数,挑两个 3 * 2
* 4 四种运算
计算完后剩下2个数,挑两个 2 * 1
* 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)


活动打卡代码 LeetCode 837. 新21点

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

f(i) = 1 / w * (f(i + 1) + f(i + 2) + ... + f(i + w))
这样算时间复杂度是n方,采取类似于背包优化递推公式的方式,看一下f(i + 1)是什么东西
f(i + 1) = 1 / w * (f(i + 2) + f(i + 2) + ... + f(i + w) + f(i + w + 1))

可以推出 f(i) = f(i + 1) + 1 / w * (f(i + 1) - f(i + w + 1))
注意:f(k - 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]