0. Post game summary
For some well-known reasons, I didn't participate in the competition this week. I made up the following questions after the competition, and then sorted it out here to encourage you.
1. Topic 1
The test question link given in question 1 is as follows:
1. Problem solving ideas
There is no difficulty in this problem. It is to express the original number in k-ary, and then calculate the sum of the values of each bit.
2. Code implementation
The implementation of python code is as follows:
class Solution:
def sumBase(self, n: int, k: int) -> int:
res = 0
while n != 0:
res += n % k
n = n // k
return res
The submitted code evaluation shows that it takes 28ms and occupies 14.2MB of memory.
2. Topic 2
The link of the test questions given in question 2 is as follows:
1. Problem solving ideas
The key point of this problem is that the data can only increase but not decrease. Therefore, we first sort all the numbers, and then examine each number from small to large. Assuming that the target number is located at this number, the minimum number of transformations must be to change the previous numbers to this number until all the transformation times are exhausted, This can be achieved by maintaining a sliding window.
When the window slides one bit to the right, the operands to be added are (R-L) * (Num [R] - num [l]). If the total number of operations exceeds the rated upper limit K, it is necessary to continuously slide the edge of the left window to the right until the operands used are no more than k.
In this way, we can O ( N ) O(N) The solution is completed under the condition of O(N) algorithm complexity.
2. Code implementation
The implementation of python code is as follows:
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
l, r, n = 0, 1, len(nums)
res = 1
used = 0
while r < n:
delta = nums[r] - nums[r-1]
used += delta * (r-l)
while l < r and used > k:
used -= nums[r] - nums[l]
l += 1
res = max(res, r-l+1)
r += 1
return res
The submitted code evaluation shows that it takes 1184ms and occupies 28.1MB of memory.
3. Topic 3
The test question link of question 3 is as follows:
1. Problem solving ideas
The idea of this question is nothing. Since the vowel alphabetic order is required and all vowel characters must be included, when we encounter characters that are not incremental sequences, we will check whether the preceding substring meets the conditions. If so, update the length of the longest substring. On the other hand, if the new substring starts with a, the calculation is restarted. Otherwise, wait until the next a appears.
2. Code implementation
The implementation of python code is as follows:
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
is_continuous = False
left = -1
res = 0
seen = set()
for i, c in enumerate(word):
if i == 0:
if c == 'a':
is_continuous = True
left = 0
seen.add(c)
continue
if c >= word[i-1]:
if is_continuous:
seen.add(c)
if len(seen) == 5:
res = max(res, i - left + 1)
else:
is_continuous = False
seen = set()
if c == 'a':
is_continuous = True
left = i
seen.add(c)
return res
The submitted code evaluation shows that it takes 852ms and occupies 20.3MB of memory.
But the code implementation is not very elegant.
3. Algorithm optimization
At present, the optimal algorithm takes only 76 MS to implement. It is implemented directly by using regular expressions. The code implementation is given as follows:
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
import re
a = re.findall('a*e*i*o*u*',word)
ans=0
for i in a:
if len(set(i))==5:
ans = max(len(i),ans)
return ans
Alas, this code is much better than our implementation. Shame, shame
4. Topic 4
The test question link of question 4 is as follows:
1. Problem solving ideas
This question is half copied and half done. I have some ideas, which are consistent with the answer, but I didn't understand one detail. Then I revised my ideas after reading the answer
The idea of this problem is to sort all restrictions according to the index, and then if we give each restriction to the upper limit, we can find the highest value that can be reached between the two restriction positions is: ( w 2 − w 1 + ∣ h 2 − h 1 ∣ ) / 2 + m i n ( h 1 , h 2 ) (w_2 - w_1 + |h_2 - h_1|) / 2 + min(h_1, h_2) (w2−w1+∣h2−h1∣)/2+min(h1,h2).
However, there is a premise here that all the restricted positions can reach the upper limit position, but this can not be guaranteed. Therefore, we need to adjust the upper limit value first, but I didn't think about how to adjust it very clearly.
The idea given in the answer is to update it respectively according to the pre order and post order, so as to ensure that every position can be reached. It is a very direct and concise idea.
2. Code implementation
We give the python code implementation as follows:
class Solution:
def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
restrictions = [[1, 0]] + sorted(restrictions)
if restrictions[-1][0] != n:
restrictions.append([n, n])
m = len(restrictions)
for i in range(1, m):
restrictions[i][1] = min(restrictions[i][1], restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0])
for i in range(m-2, -1, -1):
restrictions[i][1] = min(restrictions[i][1], restrictions[i+1][1] + restrictions[i+1][0] - restrictions[i][0])
res = max([x[1] for x in restrictions[:-1]])
for i in range(m-1):
delta = restrictions[i+1][0] - restrictions[i][0] + abs(restrictions[i+1][1] - restrictions[i][1])
res = max(res, delta // 2 + min(restrictions[i+1][1], restrictions[i][1]))
return res
The submitted code evaluation shows that it takes 1924ms and occupies 52.6MB of memory.