Leetcode notes: biweekly contest 83

• LeetCode note ：Biweekly Contest 83
  • 0. Summary
  • 1. Topic 1
    • 1. Their thinking
    • 2. Code implementation
  • 2. Topic two
    • 1. Their thinking
    • 2. Code implementation
  • 3. Topic three
    • 1. Their thinking
    • 2. Code implementation
  • 4. Topic four
    • 1. Their thinking
    • 2. Code implementation

• Match Links ：https://leetcode.com/contest/biweekly-contest-83

0. Summary

This week's two games are also a little injured , All the big guys just need 7、8 Problems that can be solved in minutes , I just didn't think of a good idea for the two fourth questions , In the end, it was only after reading the answers of other big guys , Then I found that these two questions only need a few lines , It hurts ……

I feel that my recent state is really not very good , alas ……

1. Topic 1

The link to question 1 is as follows ：

• 2347. Best Poker Hand

1. Their thinking

This question is rule based Translate what is given in the question 4 One situation is enough .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def bestHand(self, ranks: List[int], suits: List[str]) -> str:
        if len(set(suits)) == 1:
            return "Flush"
        cnt = Counter(ranks).values()
        if max(cnt) >= 3:
            return "Three of a Kind"
        elif max(cnt) == 2:
            return "Pair"
        else:
            return "High Card"

The submitted code was evaluated ： Time consuming 34ms, Take up memory 13.9MB.

2. Topic two

The link to question 2 is as follows ：

• 2348. Number of Zero-Filled Subarrays

1. Their thinking

This problem is actually to find all the continuous in the original sequence 0 The subsequence , Then calculate the number of subsequences they can form , Finally, add all these numbers .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res, cnt = 0, 0
        for x in nums:
            if x == 0:
                cnt += 1
            else:
                res += cnt * (cnt+1) // 2
                cnt = 0
        res += cnt * (cnt+1) // 2
        return res

The submitted code was evaluated ： Time consuming 1895ms, Take up memory 24.7MB.

3. Topic three

The link to question 3 is as follows ：

• 2349. Design a Number Container System

1. Their thinking

The main difficulty of this problem is that we need to quickly find the smallest of each number index, Therefore, we need to establish an ordered index Array of , Then maintain this array all the time .

2. Code implementation

give python The code implementation is as follows ：

class NumberContainers:

    def __init__(self):
        self.nums = []
        self.index = defaultdict(list)
        

    def change(self, index: int, number: int) -> None:
        idx = bisect.bisect_left(self.nums, (index, -1))
        if idx >= len(self.nums) or self.nums[idx][0] != index:
            bisect.insort(self.nums, (index, number))
            bisect.insort(self.index[number], index)
        else:
            x = self.nums[idx][1]
            self.nums[idx] = (index, number)
            bisect.insort(self.index[number], index)
            self.index[x].pop(bisect.bisect_left(self.index[x], index))
        return 

    def find(self, number: int) -> int:
        return -1 if self.index[number] == [] else self.index[number][0]

The submitted code was evaluated ： Time consuming 2350ms, Take up memory 58.5MB.

4. Topic four

The link to question 4 is as follows ：

• 2350. Shortest Impossible Sequence of Rolls

1. Their thinking

In fact, I didn't expect this question at the beginning , But after reading the answer, I found that it was actually quite simple , In fact, it is a simple construction problem .

We give a construction method , After the first round of all the numbers , So for a length of 1 The subsequence , We can always construct this sequence .

Suppose we can now complete a length of $n$ Sequence , If we can have another round after it $1\to k$ The number of , Then we can construct any length of $n+1$ The subsequence .

conversely , If there is a number that does not exist , Then we can always find a subsequence , So that this sequence cannot be successfully constructed .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        seen = set()
        res = 1
        for x in rolls:
            seen.add(x)
            if len(seen) == k:
                res += 1
                seen = set()
        return res

The submitted code was evaluated ： Time consuming 1503ms, Take up memory 28.3MB.