146.LRU cache

字数统计: 449字   |   阅读时长: 2min

topic：

I met for the first time：’2023/3/14-15:21’
screenshot2023-09-25 morning1.14.08.png

146.LRU cache.md

Thought：

Simple simulation，Use the dictionary to make it，好像完全没用到双向Linked和LRU的Thought。。。I’m guilty，I can remember the air conditioner made in half a year ago。
answer就看Code的注释应该就能看懂，I will reply if I don’t understand。

Code：

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
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = collections.OrderedDict()

    def get(self, key: int) -> int:
        # ifkeyIn the dictionary，returnvalue
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]

        else:
            # ifkey不In the dictionary，return-1
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # ifkeyIn the dictionary，renewvalue
            self.cache.move_to_end(key)
            self.cache[key] = value
        else:
            if len(self.cache) == self.capacity:
                # ifkey不In the dictionary，The dictionary is full，Delete the least recently used elements
                self.cache.popitem(last=False)
            # ifkey不In the dictionary，Dictionary is not full，Add element
            # self.cache.move_to_end(key)
            self.cache[key] = value

Second solution

screenshot2023-09-25 morning1.25.22.png

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Node:
    # Improve the speed of access attributes，And save memory
    __slots__ = 'prev', 'next', 'key', 'value'

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dummy = Node()  # Sentry node
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.key_to_node = dict()

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:  # No this book
            return None
        node = self.key_to_node[key]  # Have this book
        self.remove(node)  # Draw this book
        self.push_front(node)  # Put on the top
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:  # Have this book
            node.value = value  # renew value
            return
        self.key_to_node[key] = node = Node(key, value)  # new book
        self.push_front(node)  # Put on the top
        if len(self.key_to_node) > self.capacity:  # There are too many books
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # Remove the last book

    # Delete a node（Draw a book）
    def remove(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev

    # 在Linked头添加一个节点（把一本书Put on the top）
    def push_front(self, x: Node) -> None:
        x.prev = self.dummy
        x.next = self.dummy.next
        x.prev.next = x
        x.next.prev = x

show all >>

213.Hiccup II

字数统计: 258字   |   阅读时长: 1min

topic：

screenshot2023-09-18 morning2.31.30.png
topic链接

Thought：

这一次终于懂一点Dynamic planning了，The first is the youngest problem，I first thought it was to consider where to start，Start from the first or the second one（这刚好是和Hiccup1Difference）。
但实际上最小子问题还是和Hiccup1Same：Whether to rob the current house。
First we set onedpArray，dp[i]Indicate robbery to the firstiThe maximum return when a house。
Then we rob the current house after we rob the current house dp[i] = dp[i-2] + nums[i]，(Because the house can not be robbed before the current house is robbed)，Do not rob the current house dp[i] = dp[i-1]。
So we can get the state transfer equation：dp[i] = max(dp[i-2] + nums[i], dp[i-1])。
Last classification discussion and robbery, the first or the second start。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob1(nums: List[int]) -> int:
            if len(nums) == 1:
                return nums[0]
            ans = 0
            dp = [0] * len(nums)
            # def: dp[i]Express the robberyiHome
            # theft FirstiHouse，The income isdp[i-2]+nums[i], 不theftFirstiHouse，The income isdp[i-1]
            for i in range(len(nums)):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
                ans = max(ans, dp[i])
            return ans
        # 打劫First一家，或者First二家开始
        return max(rob1(nums[:-1]), rob1(nums[1:])) if len(nums) != 1 else nums[0]

show all >>

2251.The number of flowers during the flowering period

字数统计: 142字   |   阅读时长: 1min

topic：

screenshot2023-09-29 morning12.54.48.png

2251.The number of flowers during the flowering period.md

Thought：

看的answer，The idea is too complicated。Learned a new library，bisect，Two -point search，Can be used to find the insertion position。

bisect_right(a, x): List in orderaMediumx，returnxThe position that should be inserted，This position is located inaThe right side of all the same elements。

bisect_left(a, x): List in orderaMediumx，returnxThe position that should be inserted，This position is located inaAll of the same elements in the left。

We can usebisect_rightHere，usebisect_leftHere。

Code：

1
2
3
4
5
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)
        # Calculate how many starts before the person have-How many end
        return [bisect_right(start, p) - bisect_left(end, p) for p in people]

show all >>

2490Return ring sentence

字数统计: 70字   |   阅读时长: 1min

topic：

2023-07-01.png
[2490]Return ring sentence.md

Thought：

Divide each word，Then stitch together（123Stitch123123），Determine whether the next word corresponding to each word meets whether the next word meets the same first。

Code：

1
2
3
4
5
6
7
8
9
class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        sentence = sentence.split(' ')
        length = len(sentence)
        sentence += sentence
        for i in range(0, length):
            if sentence[i][-1] != sentence[i+1][0]:
                return False
        return True

show all >>

2562.Find the series of the array

字数统计: 100字   |   阅读时长: 1min

topic：

screenshot2023-10-12 afternoon11.08.18.png
2562.Find the series of the array.md

Thought：

This question andquiz4very similar，都是Double pointer。
I made a mistake when I did this question，When calculating the right pointer, the negative index is calculatedright = -left + 1，It is difficult to calculate the relationship between positive indexes，So replacedright = len(nums) - 1 - left。

Code：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        sums = 0
        for left in range(len(nums)):
            right = len(nums) - 1 - left
            if left == right:
                sums += nums[left]
                break
            elif left < right:
                sums += int(str(nums[left]) + str(nums[right]))
        return sums

show all >>

2582.Pillow

字数统计: 82字   |   阅读时长: 1min

topic：

screenshot2023-09-27 morning2.19.52.png

2582.Pillow.md

Thought：

math题，Find a rule，npersonal，interval=n-1，The number of cycles in the crowd= $time // (n-1)$，The number of cycles is2The number of times from scratch，Otherwise, the number of forwards from the back。

screenshot2023-09-27 morning2.24.10.png

Code：

1
2
3
4
5
6
7
8
class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        if n > time:
            return time + 1
        if time // (n-1) % 2 == 0:
            return time % (n-1) + 1
        else:
            return n - time % (n-1)

show all >>

2596.Check the Cavaliers patrol plan

字数统计: 215字   |   阅读时长: 1min

topic：

screenshot2023-09-13 afternoon5.14.07.png
topic链接

Thought：

I thought it was at first glance NQueen question，Then read it for a long time and didn’t read the question for a long time，So take a look at the answer（）。
turn out to begrid[row][col] Index cells (row, col) It is the first of the Cavaliers grid[row][col] Cell。meanspos[grid[i][j]] = (i, j)
Then I understand，Set the initial value（2，1），Then from（0，0）Start traverse each point andlastIs the difference in the value of the value?2，1or1，2，if not，Just returnFalse。

In the answer，ylbUsepairwiseThe method of calculating the two elements of the front and rear
for (x1, y1), (x2, y2) in pairwise(pos): dx, dy = abs(x1 - x2), abs(y1 - y2)

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        if grid[0][0]:
            return False
        n = len(grid)
        pos = [(0, 0)] * (n * n)
        for i in range(n):
            for j in range(n):
                pos[grid[i][j]] = (i, j)
        last = -2, 1
        for i, j in pos:
            if (abs(i - last[0]) == 2 and abs(j - last[1]) == 1) or \
                    (abs(i - last[0]) == 1 and abs(j - last[1]) == 2):
                pass
            else:
                print(i, j)
                return False
            last = (i, j)

        return True

show all >>

2 .Two numbers

字数统计: 388字   |   阅读时长: 2min

topic：

2023-07-03.png
[2].Two numbers.md

Thought：

I originally wrote the stupidest way，把两个Linked转换成数字，Then add，再转换成Linked。But it’s strange that I was right when I was running locally，But it’s wrong when you submit，
What is deducted is a very strange oneprecompiled.listnode.ListNode，But mine is'__main__.ListNode'。
So I can only watch0x3fs answer。

Two node values ​​each time`l1.val`，`l2.val`In -digit`carry`Add，Divide 10 The remaining number is the digital digit that the current node needs to be saved，Divide10The business is the new position value

Code implementation，There is a trick to simplify code：ifrecursion中发现l2Length ratio ratiol1Longer，So it can be exchangedl1and l2，ensure l1Not an empty node，So as to simplify code logic。

Code：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # l1 and l2 Node for current traversal，carry Be in place
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:  # recursion边界：l1 and l2 All empty nodes
            return ListNode(carry) if carry else None  # If you are in place，Just create an additional node
        if l1 is None:  # if l1 Empty，Then then l2 一定Not an empty node
            l1, l2 = l2, l1  # exchange l1 and l2，ensure l1 non empty，从而简化Code
        carry += l1.val + (l2.val if l2 else 0)  # 节点值andcarry加在一起
        l1.val = carry % 10  # Each node saves a digital position
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)  # carry
        return l1
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
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
        l1_list = []
        l2_list=[]
        def recursion_list(node:ListNode, listt):
            if not node:
                return listt
            listt.append(node.val)
            return recursion_list(node.next, listt)
        l1_list = recursion_list(l1, l1_list)
        l2_list = recursion_list(l2, l2_list)
        l1_list = ''.join(map(str, l1_list))
        l2_list = ''.join(map(str, l2_list))
        l3 = str(int(l1_list)+int(l2_list))
        print(l3)
        def recursion_linkArray(num):
            if not num:
                return None
            head = ListNode(0)
            current = head
            for c in num:
                current.next = ListNode(int(c))
                current = current.next
            return head.next
        head = recursion_linkArray(l3[::-1])
        print(recursion_list(head, []))
        print(type(l1), type(head))
        return head

show all >>

630.Class ScheduleIII

字数统计: 580字   |   阅读时长: 2min

topic：

img_1.png

topic链接

Thought：

思路来自于宫水三叶ofgreedy + Priority queue，

  1. first，We sort them according to the end of the course。The purpose of doing this is to try every course，See if it can adapt to our timetable。
  2. becausePythonofheapqThe default is a minimum pile，So when we join a course，我们使用其持续时间of负数，从而使得堆顶部始终是持续时间最长ofcourse。
  3. When you traverse each course，尝试把它加入到我们of日程中。but，如果我们发现加入该course后总时间超过了该courseof结束时间，那么我们需要从我们of日程中去掉一个course，最好去掉那个持续时间最长ofcourse，because这将释放出最多of时间，This is why use a maximum pile。
    sum += heapq.heappop(q)
  4. Java中ofArrays.sort(courses, (a,b)->a[1]-b[1]); Equivalent toPython中ofcourses.sort(key=lambda x: x[1])

The original text is quoted below，About why you usegreedy：

topic是要我们构造出一种可行of排列，排列中每个courseof实际结束时间满足「The latest time」Require，
求可行排序of最大长度（每个course对答案of贡献都是 1）。
This is easy to guide us「Generalized backpack」Think：simply put，For a certain item（course）For，Different costs under different conditions，
At the timeline `[1,courses[i][1]−courses[i][0]]` The item can be selected，The cost is its duration，
在比该范围大of数轴上无法被选，Cost is infinite。因此某一段特定of时间轴上，问题可抽象成有条件限制of组合优化问题。
Because the data range is 10^4，Generalized backpack做法需要记录of维度大于一维，Not be considered。
It's easy to think of「Two points」，Obviously the maximum selection quantity ans 为分割点of数组上具有「Secondary」：
1. The quantity is less than equal to ans ofcourse能够构造出合法排序（Consider making subtraction on the longest legal sequence）；
2. Use the quantity greater than ans ofcourse无法构造出合法排列。
此时Two points范围为 `[0,n]`，The problem converts to：
How to `O(n)` Check whether it can construct a length len of合法排列（accomplish `check` method）。
常规of线性扫描做法无法确定是否存在某个长度of合法排列，因此Two pointsNot be considered。
We need to use「greedy」思维考虑可能of方案。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])

        # This will be a max-heap based on course duration
        q = []
        sum = 0
        for c in courses:
            d, e = c
            sum += d
            heapq.heappush(q, -d)
            if sum > e:
                sum += heapq.heappop(q)
        return len(q)

show all >>