140

Q2(3301). Maximize the Total Height of Unique Towers

def maximumTotalSum(self, maximumHeight: List[int]) -> int:
  res = []
  picked = set()

  for n in maximumHeight:
    tmp = n
    while tmp in picked:
      tmp -= 1
    if tmp <= 0:
      return -1
    picked.add(tmp)
    res.append(tmp)

  return sum(res)

# Time Limit Exceeded

def maximumTotalSum(self, maximumHeight: List[int]) -> int:
  maximumHeight.sort(reverse=True)
  res = 0
  cur = maximumHeight[0]

  for h in maximumHeight:
    if cur > h:
      cur = h
    if cur <= 0:
      return -1
    res += cur
      cur -= 1
  return res

Q3(3302). Find the Lexicographically Smallest Valid Sequence

前后缀分解 子序列匹配 Z函数 | LeetCode Biweekly Contest 140 - YouTube

Q4(3303). Find the Occurrence of First Almost Equal Substring - LeetCode

141

Q1(3314). Construct the Minimum Bitwise Array I
Q2(3315). Construct the Minimum Bitwise Array II

def minBitwiseArray(self, nums: List[int]) -> List[int]:
  ans = []
  N = len(nums)

  for i in range(N):
    for j in range(nums[i]):
      if j | j + 1 == nums[i]:
        ans.append(j)
        break
      if j == nums[i] - 1:
        ans.append(-1)
    return ans

def minBitwiseArray(self, nums: List[int]) -> List[int]:
  for i, x in enumerate(nums):
    if x == 2:
      nums[i] = -1
    else:
      t = ~x
      lb = t & -t
      nums[i] ^= lb >> 1

    return nums

Q3(3316). Find Maximum Removals From Source String

解法: Link

  def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
    targetIndices = set(targetIndices)
    @cache
    def f(i,j):
      if i < 0 and j < 0:
        return 0
      if i < j:
        return -inf

      res = f(i - 1, j) + (i in targetIndices)
      if j >= 0 and source[i] == pattern[j]:
        return max(f(i - 1, j - 1), res)
      return res

    return f(len(source) - 1, len(pattern) - 1)

142

Q1(3330). Find the Original Typed String I

def possibleStringCount(self, word: str) -> int:
  ans = 1

  for i in range(1, len(word)):
    if word[i - 1] == word[i]:
      ans += 1
  return ans

def possibleStringCount(self, word: str) -> int:
  ans = 1

  for x, y in pairwise(word):
    if x == y:
      ans += 1
  return ans

Q3(3332). Maximum Points Tourist Can Earn

def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
  if k == 1:
    return max(stayScore[0] + [max(t) for t in travelScore])

  @cache
  def f(d, city):
    if d > k - 1:
      return 0
    res = 0
    for i in range(n):
      if i == city:
        res = max(res, f(d + 1, i) + stayScore[d][i])
      else:
        res = max(res, f(d + 1, i) + travelScore[city][i])
    return res

  res = 0
  for i in range(n):
    res = max(res, f(0, i))
  return res

143

Q1(3345). Smallest Divisible Digit Product I

def smallestNumber(self, n: int, t: int) -> int:
  def digit(num):
    s = 1
    while num:
      s *= num % 10
      num //= 10
    return s

  i = 0
  while True:
    if digit(n + i) % t == 0:
      return n + i
    i += 1