1253.Reconstruct 2 Line binary matrix

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

topic：

[1253]Reconstruct 2 Line binary matrix.md
Reconstruct 2 Line binary matrix

Thought：

At first I read the wrong question again，Thought it wascolsumDivideupper and lower两个Array，
The result iscolsum[i]Divideupper[i] and lower[i]Two numbers。
andupper[i]andlower[i]的and等于colsum[i]。
In each cycle，ObtaincolsumValue，Then judge0，1，2仨 仨，0Ignore，2If you allocate it on average。
1if，直接给当前最小的那个Array。（I use hereupperandlowerThe parameters of itself to record the remaining numbers）。
Determine at the beginningif sum(colsum) != upper + lower， Final judgmentif upper + lower != 0。

At first, I misunderstood the question again, thinking that it was about dividing colsum into two arrays, upper and lower. However, it turned out that it was about dividing colsum[i] into two numbers, upper[i] and lower[i]. Additionally, the sum of upper[i] and lower[i] should be equal to colsum[i].
In each iteration, the value of colsum is obtained, and then three scenarios, 0, 1, and 2, are considered. If it’s 0, it is ignored. If it’s 2, the values are evenly distributed. If it’s 1, it is assigned to the array with the current minimum value (using the remaining numbers in upper and lower than parameters).
At the beginning, it is checked whether if sum(colsum) != upper + lower, and finally, it is checked whether if upper + lower != 0.

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
class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        if sum(colsum) != upper + lower:
            return []
        upper_list = [0] * len(colsum)
        lower_list = [0] * len(colsum)
        for i in range(len(colsum)):
            if colsum[i] == 0:
                continue
            if colsum[i] == 2:
                upper_list[i] = 1
                lower_list[i] = 1
                upper -= 1
                lower -= 1
            else:
                if upper >= lower:
                    upper_list[i] = 1
                    upper -= 1
                else:
                    lower_list[i] = 1
                    lower -= 1
        if upper != 0 or lower != 0:
            return []
        return [upper_list, lower_list]

show all >>

1333.Restaurant filter

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

topic：

screenshot2023-09-27 afternoon3.45.32.png

1333.Restaurant filter.md

Thought：

This is the beginningpopThought，But time complexity is too high，400ms，It is later changed to a list derivative。
I think of the senior said，pop()The running time is okay，But once the index is added inside，It will be particularly slow。
sorted and lambda Usage：
lambdayesPythonAnonymous function in。it’s here，lambda x: (x[1], x[0])Definitions a acceptance of an elementx（in this case，xyesrestaurantsA list in the list）And return a tuple(x[1], x[0])The function。

this means，Sort首先基于每个子列表的第二个元素x[1]，Then based on this basisx[0]。in other words，It first followsx[1]进行Sort，ifx[1]same，According tox[0]进行Sort。

1
2
3
4
5
6
7
8
9
10
while ind < len(restaurants):
     i = restaurants[ind]
     if veganFriendly == 1 and i[2] == 0:
         restaurants.pop(ind)
     elif maxPrice < i[3]:
         restaurants.pop(ind)
     elif maxDistance < i[4]:
         restaurants.pop(ind)
     else:
         ind += 1

Code：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> \
            List[int]:
        restaurants = [
            i for i in restaurants
            if (veganFriendly == 0 or i[2] == veganFriendly)
               and i[3] <= maxPrice
               and i[4] <= maxDistance
        ]
        restaurants = sorted(restaurants, key=lambda x: (x[1], x[0]), reverse=True)
        return [i[0] for i in restaurants]

show all >>

1460.Class ScheduleIV

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

topic：

img_2.png

[1460]Class ScheduleIV.md

Thought：

一开始的想法是构建有向picture，然后在有向picture中找到queryDoes the two points have a father -son relationship?。
But watchylbAfter the answer，I find that the accessability is faster first。
First traversalprerequirements，Record all the accessibility。
Then triple cycle，Connect all the availability。

i->j->k，ifi->k，Soi->kIt is。

Code：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[
        bool]:
        f = [[False] * n for _ in range(n)]
        for a, b in prerequisites:
            f[a][b] = True
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    f[i][j] = f[i][j] or (f[i][k] and f[k][j])
        return [f[a][b] for a, b in queries]

show all >>

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

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

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

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