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

144

Q1(3360). Stone Removal Game

def canAliceWin(self, n: int) -> bool:
  cnt = 10

  while n >= cnt:
    n -= cnt
    cnt -= 1

  return True if cnt % 2 else False

Q2(3361). Shift Distance Between Two Strings

def shiftDistance(self, s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int:
  ans = 0

  def pre_cost(i, j):
    cnt = 0
    pos_i = ord(i) - ord('a')
    pos_j = ord(j) - ord('a')
    while pos_i != pos_j:
      cnt += previousCost[pos_i]
      if pos_i == 0:
        pos_i = 25
      else:
        pos_i -= 1

    return cnt

  def next_cost(i, j):
    cnt = 0
    pos_i = ord(i) - ord('a')
    pos_j = ord(j) - ord('a')
    while pos_i != pos_j:
      cnt += nextCost[pos_i]
      if pos_i == 25:
        pos_i = 0
      else:
        pos_i += 1
      return cnt

  for i in range(len(s)):
    ans += min(pre_cost(s[i], t[i]), next_cost(s[i], t[i]))
  return ans

145

Q1(3375). Minimum Operations to Make Array Values Equal to K

def minOperations(self, nums: List[int], k: int) -> int:
  if min(nums) < k:
    return -1
  nums = set(nums)
  return len(nums) - 1 if min(nums) == k else len(nums)

146

Q1(3392). Count Subarrays of Length Three With a Condition

def countSubarrays(self, nums: List[int]) -> int:
  ans = 0

  for i in range(len(nums) - 2):
    if nums[i + 1] == 2 * (nums[i] + nums[i + 2]):
      ans += 1
  return ans

Q2(3393). Count Paths With the Given XOR Value

def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
  ROW = len(grid)
  COL = len(grid[0])
  MOD = 10 ** 9 + 7

  @cache
  def dfs(i, j, v):
    if i >= ROW or j >= COL:
      return 0
    v ^= grid[i][j]

    if i == ROW - 1 and j == COL - 1:
      if v == k:
        return 1
      return 0
    return (dfs(i + 1, j, v) + dfs(i, j + 1, v)) % MOD

  return dfs(0, 0, 0) % MOD