1. Topic 1
The test question link given in question 1 is as follows:
1. Problem solving ideas
For this question, just count all the colors in each position, and then count the positions containing all 3 colors.
2. Code implementation
The python code is implemented as follows:
class Solution:
def countPoints(self, rings: str) -> int:
n = len(rings)
cnt = defaultdict(set)
for i in range(0, n, 2):
cnt[rings[i+1]].add(rings[i])
return len([x for x in cnt if len(cnt[x]) == 3])The submitted code evaluation shows that it takes 32ms and occupies 14.1MB of memory.
2. Topic 2
The link of the test questions given in question 2 is as follows:
1. Problem solving ideas
This question was originally thinking about whether there was any good idea, but after hitting the wall several times, it was finally handled with the most violent double cycle. After all, it is not a difficult problem, but I still think there should be a better way to solve the problem. Alas
2. Code implementation
The coarse python code is implemented as follows:
class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
n = len(nums)
res = 0
for i in range(n-1):
_min, _max = nums[i], nums[i]
for j in range(i+1, n):
_min = min(nums[j], _min)
_max = max(nums[j], _max)
res += _max - _min
return resThe submitted code evaluation shows that it takes 4272ms and occupies 14.4MB of memory.
3. Topic 3
The test question link for question 3 is as follows:
1. Problem solving ideas
This problem also feels that it can be realized step by step according to the meaning of the problem.
2. Code implementation
The python code is implemented as follows:
class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
n = len(plants)
i, j = 0, n-1
a, b = capacityA, capacityB
res = 0
while i < j:
if a < plants[i]:
a = capacityA
res += 1
a -= plants[i]
i += 1
if b < plants[j]:
b = capacityB
res += 1
b -= plants[j]
j -= 1
return res+1 if i == j and max(a, b) < plants[i] else resThe submitted code evaluation shows that it takes 848ms and occupies 29.4MB of memory.
4. Topic 4
The test question link given in question 4 is as follows:
1. Problem solving ideas
The final result of this problem is the number of fruits in a certain range before and after eating. Therefore, what we have to do is first use a cumulative array to record the number of fruits in front of each position, and then traverse the total number of fruits in all covered ranges with length k.
2. Code implementation
The python code is implemented as follows:
class Solution:
def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
n = len(fruits)
for i in range(n-1):
fruits[i+1][1] += fruits[i][1]
fruits = [[-1, 0]] + fruits + [[math.inf, fruits[-1][1]]]
l = bisect.bisect_left(fruits, [startPos-k, 0])
res = 0
while fruits[l][0] <= startPos:
lbound = fruits[l][0]
rbound = max(k - 2*(startPos-lbound) + startPos , startPos + (k - (startPos-lbound)) // 2)
r = bisect.bisect_right(fruits, [rbound, math.inf]) -1
res = max(res, fruits[r][1] - fruits[l-1][1])
l += 1
rbound = startPos + k
r = bisect.bisect_right(fruits, [rbound, math.inf]) -1
res = max(res, fruits[r][1] - fruits[l-1][1])
return res The submitted code evaluation shows that it takes 1860ms and occupies 60.8MB of memory.