146.LRU cache

字数统计: 447字   |   阅读时长: 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

字数统计: 78字   |   阅读时长: 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 >>

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

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

213.Hiccup III

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

topic：

screenshot2023-09-18 afternoon1.08.41.png
topic链接

Thought：

Reference ylb 大佬的answer，
这道题andHiccup1and2The difference is，这道题是一棵Binary tree，And you can’t rob the neighboring node。
So his youngest child problem is：Robbing the current node，You can’t rob your left and right children。
If you steal root node，那么不能偷取其左右子node，Result root.val+lb +rb；
If not steal root node，那么可以偷取其左右子node，Result max(la, lb)+max(ra ,rb)。

Code：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def _rob(root: Optional[TreeNode]) -> (int, int):
            # Minority problem:dp[i]=dp[i-2]+nums[i], dp[i-1]
            if not root:
                return 0, 0
            la, lb = _rob(root.left)
            ra, rb = _rob(root.right)
            return root.val + lb + rb, max(la, lb) + max(ra, rb)
        return max(_rob(root))

show all >>