LEETCODE 第16场双周赛

最后一题比赛中没做出来。。

第一题:将每个元素替换为右侧最大元素

  给你一个数组 arr ,请你将每个元素用它右边最大的元素替换,如果是最后一个元素,用 -1 替换。
  
  完成所有替换操作后,请你返回这个数组。
  
  示例:
  
  输入:arr = [17,18,5,4,6,1]
  输出:[18,6,6,6,1,-1]

  思路:这题用python自带的max([arr[i:]])居然超时了两次😒,无奈从右往左遍历🤷‍♀️,最后一个置为-1,max置为最后一个元素,然后只要有比max大的就更新max,返回max即可。

第二题:转变数组后最接近目标值的数组和

  给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近  target (最接近表示两者之差的绝对值最小)。
  
  如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。
  
  请注意,答案不一定是 arr 中的数字。
  
  示例 1:
  输入:arr = [4,9,3], target = 10
  输出:3
  解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。
  
  示例 2:
  输入:arr = [2,3,5], target = 10
  输出:5
  
  示例 3:
  输入:arr = [60864,25176,27249,21296,20204], target = 56803
  输出:11361

  思路:(有点coarse-to-fine的意思?)。先将arr降序排序,然后将value逐渐降低到arr中的每个元素,看数组之和会不会小于target,如果没有小于就继续降到下一个台阶,否则就回升一点。
  注意题目中 “如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。”,这个我判断的方式比较粗暴,直接用整除后的value和value-1看谁更接近,如果一样就返回value-1。

第三题:层数最深叶子节点的和

  给你一棵二叉树,请你返回层数最深的叶子节点的和。
  
  示例:
  输入:root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
  输出:15

  思路:层序遍历并记录当前层数的和,返回最后一层即可。
  另一种思路:先序遍历,分别记录值和层数,然后把层数最大的求和。

第四题:最大得分的路径数目

  给你一个正方形字符数组 board ,你从数组最右下方的字符 ‘S’ 出发。
  
  你的目标是到达数组最左上角的字符 ‘E’ ,数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中,你可以向上、向左或者左上方移动,可以移动的前提是到达的格子没有障碍。
  
  一条路径的 「得分」 定义为:路径上所有数字的和。
  
  请你返回一个列表,包含两个整数:第一个整数是 「得分」 的最大值,第二个整数是得到最大得分的方案数,请把结果对 10^9 + 7 取余。
  
  如果没有任何路径可以到达终点,请返回 [0, 0] 。
  
  示例 1:
  输入:board = [“E23″,”2X2″,”12S”]
  输出:[7,1]
  
  示例 2:
  输入:board = [“E12″,”1X1″,”21S”]
  输出:[4,2]
  
  示例 3:
  输入:board = [“E11″,”XXX”,”11S”]
  输出:[0,0]

  思路,只能向上或向左走,因此不需要🙅‍♀️搜索,用dp即可。访问的顺序如下图所示:



  from位置为右、下或右下。每个位置board[x][y]如果不为’X’,设update值为from位置的score加上当前位置的数字。如果update分数大于当前位置的score,则更新score,方案数等于from位置的方案数;如果update=当前位置的score,则不用更新score,方案数=当前位置方案数+from位置方案数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注