Leetcode notes: Weekly contest 298

• LeetCode note ：Weekly Contest 298
  • 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/weekly-contest-298

1. Topic 1

The link to question 1 is as follows ：

• 2309. Greatest English Letter in Upper and Lower Case

1. Their thinking

The idea of this question is relatively simple , Just record all the characters in the string first , Then traverse the characters in the reverse order of dictionary order , Just take a look at the first result where both case and case exist in the string .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def greatestLetter(self, s: str) -> str:
        cnt = Counter(s)
        for i in range(26):
            l, u = chr(ord('a') + 25 - i), chr(ord('A') + 25 - i)
            if l in cnt and u in cnt:
                return u
        return ""

The submitted code was evaluated ： Time consuming 64ms, Take up memory 13.8MB.

2. Topic two

The link to question 2 is as follows ：

• 2310. Sum of Numbers With Units Digit K

1. Their thinking

This question makes n Mantissa is k The sum of the numbers of must be exactly equal to num, Then there must be n*k And num Have the same mantissa , And the former is no greater than the latter .

Besides , If the above conditions are met , Then we can always construct a group with a length of n The mantissa of all numbers is k, And the sum is num.

in fact , Just allocate the remainder appropriately to this n The number can be increased .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, 11):
            a = i * k
            if a <= num and a % 10 == num % 10:
                return i
        return -1

The submitted code was evaluated ： Time consuming 75ms, Take up memory 13.8MB.

3. Topic three

The link to question 3 is as follows ：

• 2311. Longest Binary Subsequence Less Than or Equal to K

1. Their thinking

The result of this question is in front of the train of thought 0 There can be any number of , But once you take one 1 after , Then the following possible permutations can only form one at most k, That is , hypothesis k The binary of is m position , Then the number of digits that can be used in the future can only be m position .

therefore , Sum up , We're just going to iterate through all the positions as the real valid start , under these circumstances , The result in each position is the one in front of it 0 The number of and the number that can be formed subsequently shall not be greater than k The maximum number of digits in the two-level system .

then , Let's look at how to find the maximum number of bits that can form a binary number from a certain position , This is actually simple , obviously , If the total number of digits is less than m, Then you can use all of them , If the number of digits is greater than m, There is also a need for classified discussion , If you can find n The number of substrings is less than k, So the result is k, conversely , The result is m-1.

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        kd = []
        while k != 0:
            kd.insert(0, k % 2)
            k = k // 2
        m = len(kd)
        
        def get_max(idx):
            if n - idx < m:
                return n-idx
            sub = s[idx:]
            less, j = False, 0
            for i, ch in enumerate(sub):
                if j >= m:
                    break
                if not less:
                    if int(sub[i]) > kd[j]:
                        continue
                    elif int(sub[i]) < kd[j]:
                        less = True
                j += 1
            return m if j >= m else m-1
        
        res, cnt = 0, 0
        for i, ch in enumerate(s):
            if ch == "0":
                cnt += 1
                res = max(res, cnt)
            else:
                res = max(res, cnt + get_max(i))
        return res

The submitted code was evaluated ： Time consuming 429ms, Take up memory 14MB.

4. Topic four

The link to question 4 is as follows ：

• 2312. Selling Pieces of Wood

1. Their thinking

My basic idea for this question is greedy Fill of , First , We put... According to the value of the unit square prices Sort , then greedy Use a square to fill .

The filling method is to say , Let's start with the current largest prices To fill the rectangle of the body , Then the filling of the remaining leftover materials .

The above solution can realize the functions we need , But there will be a timeout if it is not handled , Therefore, we need to prune on the basis of the above .

The idea of pruning is also relatively simple , First , If the row or column can be directly marked by the current largest price The rectangle completely covers , Then we can just use it directly , Only if it cannot be completely covered , It is possible for other rectangles to be filled to produce a larger total price The situation of .

therefore , We can reduce the complexity of the algorithm by pruning based on this , Pass the final test .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        prices = sorted(prices, key=lambda x: -x[2] / (x[0] * x[1]))
        
        @lru_cache(None)
        def dp(w, h, idx):
            res = 0
            for x, y, p in prices[idx:]:
                if x > w or y > h:
                    continue
                if p / (x * y) * (w * h) <= res:
                    break
                if w % x == 0 and h % y == 0:
                    res = max(res, (w//x) * (h//y)*p)
                    break
                elif w % x == 0:
                    i = w // x
                    for j in range(h//y, 0, -1):
                        s = i * j * p
                        wr, hr = w - x*i, h - y*j
                        res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
                elif h % y == 0:
                    j = h // y
                    for i in range(w//x, 0, -1):
                        s = i * j * p
                        wr, hr = w - x*i, h - y*j
                        res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
                else:
                    for i in range(w//x, 0, -1):
                        for j in range(h//y, 0, -1):
                            s = i * j * p
                            wr, hr = w - x*i, h - y*j
                            res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
            return res
        
        return dp(m, n, 0)

The submitted code was evaluated ： Time consuming 1049ms, Take up memory 22MB.