Featured image of post Weekly Report 2024.15

Weekly Report 2024.15

the learning curve

Why grow up? and why they didn’t.

Entertainment

Nah

Learning

Graph with PQ

  • use pq to calculate least steps
 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
class Solution:
    def minimumTime(
        self, n: int, edges: List[List[int]], d: List[int]
    ) -> List[int]:
        adj = defaultdict(list)
        for u, v, l in edges:
            adj[u].append((l, v))
            adj[v].append((l, u))

        # use sys.maxsize to mark non-reachable
        res = [sys.maxsize] * n
        # (cost, index)
        pq = [(0, 0)]
        while pq:
            cost, i = heapq.heappop(pq)
            if res[i] > cost:
                res[i] = cost
                # to next index, and check accessibility
                for (c, j) in adj[i]:
                    nc = cost + c
                    if nc < d[j] and nc < res[j]:
                        heapq.heappush(pq, (nc, j))

        # update non-reachable index
        for i in range(n):
            if res[i] == sys.maxsize:
                res[i] = -1

        return res

MonotonicStack

 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
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        # (index, height), the start index which could form rectangle with height
        stk = []
        res = 0

        for i, h in enumerate(heights):
            # reserve start_index with i
            start_index = i
            # pop out greater ones from stk
            # update maximal area, also the feasible index of current h to previous index
            while stk and stk[-1][1] > h:
                index, height = stk.pop()
                res = max(res, height * (i - index))
                start_index = index
            stk.append((start_index, h))

        # if stack is not empty, the left parts, it's non-decreasing order
        # [2,1,5,6,2,3]
        # [(4,2), (5,3)]
        for i, h in stk:
            res = max(res, h * (n - i))

        return res

Life

  • leetcode contests are overwhelmingly hard for me

Sharing

We tend to measure performance by what happens when things are going well. Yet how people, organizations, companies, leaders, and other things do on their best day isn’t all that instructive. To find the truth, we need to look at what happens on the worst day.

References

overall, very useful sharing.

Licensed under CC BY-NC-SA 4.0
Last updated on Jan 09, 2024 11:32 CST
The older I get, the more I realize that most of life is a matter of what we pay attention to, of what we attend to [with focus].
Built with Hugo
Theme Stack designed by Jimmy