MoreRSS

site iconRunye | 算法花园修改

博客 编程 AI
滴滴、飞猪。分享算法，竞赛性编程，阅读等主题内容。
RSS: https://blog.xiang578.com/atom.xml
请复制 RSS 到你的阅读器，或快速订阅到 :

Inoreader Feedly Follow Feedbin Local Reader

Runye | 算法花园的 RSS 预览

lc732. 我的日程安排表 iii

2025-01-05 00:00:00

题目链接：732. 我的日程安排表 III

题解

LC729. 我的日程安排表 I、LC731. 我的日程安排表 II、LC732. 我的日程安排表 III 三题基本差不多。由于先写的 732，当时写了线段树，所以这三题都用线段树写了。标准区间查询和区间修改题目。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
class MyCalendarThree:
    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

    def update(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return
        if start <= l and r <= end:
            self.tree[idx] += 1
            self.lazy[idx] += 1
        else:
            mid = (l + r) // 2
            self.update(start, end, l, mid, idx * 2)
            self.update(start, end, mid + 1, r, idx * 2 + 1)
            self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])

    def book(self, start: int, end: int) -> int:
        self.update(start, end - 1, 0, 10 ** 9, 1)
        return self.tree[1]

lc731. 我的日程安排表 ii

2025-01-05 00:00:00

题目链接：

题解

LC729. 我的日程安排表 I、LC731. 我的日程安排表 II、LC732. 我的日程安排表 III 三题基本差不多。由于先写的 732，当时写了线段树，所以这三题都用线段树写了。标准区间查询和区间修改题目。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
class MyCalendarTwo:

    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

    def update(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return
        if start <= l and r <= end:
            self.tree[idx] += 1
            self.lazy[idx] += 1
        else:
            mid = (l + r) // 2
            self.update(start, end, l, mid, idx * 2)
            self.update(start, end, mid + 1, r, idx * 2 + 1)
            self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])
        
    def check(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return 0
        if start <= l and r <= end:
            return self.tree[idx] 
        else:
            mid = (l+r) //2
            return self.lazy[idx] + max(self.check(start, end, l, mid, idx*2), self.check(start, end, mid + 1, r, idx*2+1))

    def book(self, startTime: int, endTime: int) -> bool:
        ret = self.check(startTime, endTime - 1, 0, 10 ** 9, 1)
        # print(startTime, endTime, ret)
        if ret >= 2:
            return False
        else:
            self.update(startTime, endTime - 1, 0, 10 ** 9, 1)
            return True

lc729. 我的日程安排表 i

2025-01-05 00:00:00

题目链接：729. 我的日程安排表 I

题解

LC729. 我的日程安排表 I、LC731. 我的日程安排表 II、LC732. 我的日程安排表 III 三题基本差不多。由于先写的 732，当时写了线段树，所以这三题都用线段树写了。标准区间查询和区间修改题目。

数据量比较小，也可以直接双重 for 循环求解。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
class MyCalendar:

    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

    def update(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return
        if start <= l and r <= end:
            self.tree[idx] += 1
            self.lazy[idx] += 1
        else:
            mid = (l + r) // 2
            self.update(start, end, l, mid, idx * 2)
            self.update(start, end, mid + 1, r, idx * 2 + 1)
            self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])
        
    def check(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return 0
        if start <= l and r <= end:
            return self.tree[idx] 
        else:
            mid = (l+r) //2
            return self.lazy[idx] + max(self.check(start, end, l, mid, idx*2), self.check(start, end, mid + 1, r, idx*2+1))

    def book(self, startTime: int, endTime: int) -> bool:
        ret = self.check(startTime, endTime - 1, 0, 10 ** 9, 1)
        # print(startTime, endTime, ret)
        if ret > 0:
            return False
        else:
            self.update(startTime, endTime - 1, 0, 10 ** 9, 1)
            return True

lc2241. 设计一个 atm 机器

2025-01-05 00:00:00

题目链接：LC2241. 设计一个 ATM 机器 2241. 设计一个 ATM 机器

题解

按题意模拟，可能写的有点复杂了。。。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
class ATM:

    def __init__(self):
        self.banknotes = {}
        self.a = [20, 50, 100, 200, 500]
        for i in [20, 50, 100, 200, 500]:
            self.banknotes[i] = 0

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(5):
            self.banknotes[self.a[i]] += banknotesCount[i]

    def withdraw(self, amount: int) -> List[int]:
        
        ans = []
        tmp = amount
        # print(self.banknotes)
        for i in range(4, -1, -1):
            x = min(int(tmp/self.a[i]), self.banknotes[self.a[i]])
            # self.banknotes[self.a[i]] -= x
            # print(self.a[i], x, tmp)
            ans.append(x)
            tmp -= x * self.a[i]
        if tmp != 0:
            return [-1]
        ans = ans[::-1]
        for i in range(5):
            self.banknotes[self.a[i]] -= ans[i]
        return ans


# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)

lc3280. 将日期转换为二进制表示

2025-01-01 00:00:00

题目链接：3280. 将日期转换为二进制表示

题解

Python 基础语法题，leetcode 官方新年第一天的温柔。

参考代码

1
2
3
4
5
6
7
8
 
class Solution:
    def convertDateToBinary(self, date: str) -> str:
        y, m, d = date.split("-")
        yy = bin(int(y))[2:]
        mm = bin(int(m))[2:]
        dd = bin (int(d))[2:]
        return f"{yy}-{mm}-{dd}"

lc3219. 切蛋糕的最小总开销 ii

2025-01-01 00:00:00

链接： 3219. 切蛋糕的最小总开销 II - 力扣（LeetCode）

题解

贪心半天，最后还是看了题解，只差一层窗户纸，还是要独立自己写。

解题比较关键的一点是，逆向思考，从 n*m 块小蛋糕最终合并成一个大蛋糕。问题变成水平合并 m-1 次，垂直合并 n-1 次。为了结果最小，刚开始应该先合并开销小的。

假设水平当前已经合并到 i，垂直已经合并到 j，分别开销是 horizontalCut[i]*(n-j) 和 verticalCut[j]*(m-i)。

  • 自己一直每一步是选择这两个值里面最小的合并，如果两个值相等，就选择两个之间 horizontalCut[i] 和 verticalCut[j]，这样下一步开销会减小的更多。
  • 看题解直接是贪心选择 horizontalCut[i] 和 verticalCut[j] 之间最小的即可，这样才是下一步开销减小最多的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
    
        horizontalCut.sort()
        verticalCut.sort() 
        cost = 0
        i = 0
        j = 0
        while True:
            if m == 1 and n == 1:
                break
            # print(i, j, m, n)
            if n == 1:
                cost += horizontalCut[i]
                i += 1
                m -= 1
            elif m == 1:
                cost += verticalCut[j]
                j += 1
                n -= 1
            elif horizontalCut[i] < verticalCut[j]:
                cost += horizontalCut[i] * n
                i += 1
                m -= 1
            else:
                cost += verticalCut[j] * m
                j += 1
                n -= 1
            
        return cost