随机问题

1161 二叉树的最大层级和

from collections import deque
class TreeNode:
  def __init__(self, val = 0, left = None, right = None):
    self.val = val
    self.left = left
    self.right = right

def maxLevelSum(root):
  res = [0, float('-inf')] # [level, sum]

  deck = deque([root])
  curr_level = 0

  while deck:
    level_sum = 0
    curr_level += 1
    for _ in range(len(deck)):
      curr = deck.popleft()

      if curr.left:
        deck.append(curr.left)
      if curr.right:
        deck.append(curr.right)
      
      level_sum += curr.val
    if res[1] < level_sum:
      res = [curr_level, level_sum]
  return res[0] 

1975 最大矩阵和

关键在于理解，你可以使用“翻转”方法，在矩阵中移动任何单个负号。如果负号的总数为偶数，你可以通过将它们配对来消除所有负号。如果负号的总数为奇数，你可以将负号移动到最小的元素，并将其他元素配对。最终，我们减去 2 * smallest，因为总共有两个最小的元素（它是所有元素之和）。

def maxMatrixSum(matrix):
  neg_count = 0
  smallest = float('inf')
  total = 0

  for row in matrix:
    for elem in row:
      if elem < 0:
        neg_count += 1
      abs_elem = abs(elem)
      smallest = min(smallest, abs_elem)
      total += abs_elem
  
  if neg_count % 2 == 0:
    return total
  else:
    return total - 2 * smallest