Leetcode notes: biweekly contest 69

• LeetCode note ：Biweekly Contest 69
  • 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

1. Topic 1

The link to question 1 is as follows ：

• 2129. Capitalize the Title

1. Their thinking

It's nothing , It is to divide words according to the meaning of the title and then convert the format of each word .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        words = title.split()
        for i, w in enumerate(words):
            if len(w) <= 2:
                words[i] = w.lower()
            else:
                words[i] = w[0].upper() + w[1:].lower()
        return " ".join(words)

The submitted code was evaluated ： Time consuming 33ms, Take up memory 14.1MB.

2. Topic two

The link to question 2 is as follows ：

• 2130. Maximum Twin Sum of a Linked List

1. Their thinking

My thinking on this question is very violent , Just use one first list Re write down all val, Then you can quickly find all pair 了 , You can find the maximum value .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        n = len(vals)
        return max(vals[i] + vals[n-1-i] for i in range(n//2))

The submitted code was evaluated ： Time consuming 1161ms, Take up memory 55MB.

3. Topic three

The link to question 3 is as follows ：

• 2131. Longest Palindrome by Concatenating Two Letter Words

1. Their thinking

This question is actually simple , Just use one first counter Count all the characters .

We want to form a palindrome , All you need is the opposite string , So we just have to find all the opposite combinations of strings , Then count the number of pair The number of .

The only thing to notice is that , about aa String of type , We need to look at it alone , Because for such characters , His opposite string is itself , Therefore, it can constitute pair Of its total 1/2.

More special , because aa The class string can be placed in the center to form itself pair, therefore , If there are odd numbers aa Type character , Then the result has to add 2.

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        cnt = Counter(words)
        res = 0
        mid = False
        for w in cnt.keys():
            if w == w[::-1]:
                k = cnt[w]
                res += 4*(k//2)
                if k % 2 == 1:
                    mid = True
            else:
                k = min(cnt[w], cnt[w[::-1]])
                res += 4 * k
                cnt[w] -= k
                if w[::-1] in cnt.keys():
                    cnt[w[::-1]] -= k
        return res+2 if mid else res

The submitted code was evaluated ： Time consuming 1384ms, Take up memory 38.5MB.

4. Topic four

The link to question 4 is as follows ：

• 2132. Stamping the Grid

1. Their thinking

In fact, my thinking on this question is quite direct , Is to traverse all nodes first , Find all the places where stamps can be affixed and make a mark ; Then go through each position again , Check whether all nodes can be covered by at least one stamp .

however , The difficulty here is to say how to $O(1)$ Confirm whether a certain position can be stamped and whether a certain position can be covered by a certain stamp within the time complexity of .

Fortunately, the two methods are unified , Is to examine the sum of elements within a rectangle , This can be achieved quickly through a cumulative array .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n, m = len(grid), len(grid[0])
        cumsum = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(n):
            for j in range(m):
                cumsum[i+1][j+1] = grid[i][j] + cumsum[i+1][j] + cumsum[i][j+1] - cumsum[i][j]
        
        status = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(n-stampHeight+1):
            for j in range(m-stampWidth+1):
                if cumsum[i+stampHeight][j+stampWidth] + cumsum[i][j] - cumsum[i+stampHeight][j] - cumsum[i][j+stampWidth] != 0:
                    continue
                status[i][j] = 1
        
        for i in range(n-1):
            status[i+1][0] += status[i][0]
        for j in range(m-1):
            status[0][j+1] += status[0][j]
        for i in range(n-1):
            for j in range(m-1):
                status[i+1][j+1] += status[i+1][j] + status[i][j+1] - status[i][j]
                
        def is_cover(i, j):
            if i < stampHeight and j < stampWidth:
                return status[i][j]
            elif i < stampHeight:
                return status[i][j] - status[i][j-stampWidth]
            elif j < stampWidth:
                return status[i][j] - status[i-stampHeight][j]
            else:
                return status[i][j] - status[i][j-stampWidth] - status[i-stampHeight][j] + status[i-stampHeight][j-stampWidth]
                
        return all(is_cover(i, j) + grid[i][j] > 0 for i in range(n) for j in range(m))

The submitted code was evaluated ： Time consuming 4392ms, Take up memory 55.8MB.