LEETCODE 第16场双周赛

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

Contents

1 第一题：将每个元素替换为右侧最大元素
2 第二题：转变数组后最接近目标值的数组和
3 第三题：层数最深叶子节点的和
4 第四题：最大得分的路径数目

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

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

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

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        ans = [-1]
        if len(arr) <= 1:
            return ans
        m = arr[-1]
        for i in range(len(arr)-2, -1, -1):
            ans = [m] + ans
            if arr[i] > m:
                m = arr[i]
        return ans

class Solution:

def replaceElements(self, arr: List[int]) -> List[int]:

ans = [-1]

if len(arr) <= 1:

return ans

m = arr[-1]

for i in range(len(arr)-2, -1, -1):

ans = [m] + ans

if arr[i] > m:

m = arr[i]

return ans

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

　　给你一个整数数组 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。

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        s = sorted(arr, reverse=True)
        all = sum(arr)
        if all <= target:
            return s[0]

        for i, num in enumerate(s[1:]):
            r = (s[i] - num) * (i+1)
            if all - r <= target:
                # return s[i] - (all-target) // (i+1)
                m1 = s[i] - (all-target) // (i+1)
                m2 = m1 - 1
                if abs(all - (s[i] - m1) * (i+1) - target) >= abs(all - (s[i] - m2) * (i+1) - target):
                    return m2
                else:
                    return m1

            all -= r

            # print(i, all)

        i = len(s) - 1
        m1 = s[-1] - (all - target) // (i + 1)
        m2 = m1 - 1
        if abs(all - (s[i] - m1) * (i + 1) - target) >= abs(all - (s[i] - m2) * (i + 1) - target):
            return m2
        else:
            return m1

class Solution:

def findBestValue(self, arr: List[int], target: int) -> int:

s = sorted(arr, reverse=True)

all = sum(arr)

if all <= target:

return s[0]

for i, num in enumerate(s[1:]):

r = (s[i] - num) * (i+1)

if all - r <= target:

# return s[i] - (all-target) // (i+1)

m1 = s[i] - (all-target) // (i+1)

m2 = m1 - 1

if abs(all - (s[i] - m1) * (i+1) - target) >= abs(all - (s[i] - m2) * (i+1) - target):

return m2

else:

return m1

all -= r

# print(i, all)

i = len(s) - 1

m1 = s[-1] - (all - target) // (i + 1)

m2 = m1 - 1

if abs(all - (s[i] - m1) * (i + 1) - target) >= abs(all - (s[i] - m2) * (i + 1) - target):

return m2

else:

return m1

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

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

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

class Solution {
public:
    int layer=1;
    queue<TreeNode*> q;
    int deepestLeavesSum(TreeNode* root) {

        if(root == NULL)return 0;
        q.push(root);q.push(NULL);
        int level = 1;
        int ans = 0;
        while(!q.empty())
        {
            TreeNode * t = q.front();q.pop();
            if(t == NULL)
            {
                if(q.empty())break;
                level ++;
                ans = 0;


                q.push(NULL);
                puts("");
                continue;
            }
            ans += t -> val;
            // cout << level <<(t -> val) << " ";
            if(t -> left)q.push(t -> left);
            if(t -> right)q.push(t -> right);

        }
        return ans;
    }
};

class Solution {

public:

int layer=1;

queue<TreeNode*> q;

int deepestLeavesSum(TreeNode* root) {

if(root == NULL)return 0;

q.push(root);q.push(NULL);

int level = 1;

int ans = 0;

while(!q.empty())

{

TreeNode * t = q.front();q.pop();

if(t == NULL)

{

if(q.empty())break;

level ++;

ans = 0;

q.push(NULL);

puts("");

continue;

}

ans += t -> val;

// cout << level <<(t -> val) << " ";

if(t -> left)q.push(t -> left);

if(t -> right)q.push(t -> right);

}

return ans;

}

};

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

　　给你一个正方形字符数组 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位置方案数。

def pathsWithMaxScore(board: list) -> list:
    froms = ((1, 0), (0, 1), (1, 1))
    M = 1000000007

    l = len(board)
    score = [[0 for i in range(l)] for i in range(l)]  # 得分
    plans = [[0 for i in range(l)] for i in range(l)]  # 方案

    board[0] = '0' + board[0][1:]  # 把E替换成0
    plans[l - 1][l - 1] = 1

    def handle(x, y):
        if board[x][y] == 'X':
            return

        for x1, y1 in froms:
            fx, fy = x + x1, y + y1
            if fx < l and fy < l and board[fx][fy] != 'X':  # 能走
                update = int(board[x][y]) + score[fx][fy]  # 更新后的分
                if update > score[x][y]:  # 分数更高了 方案数等于来的时候的方案数
                    score[x][y] = update
                    plans[x][y] = plans[fx][fy]
                elif update == score[x][y]:  # 分数相同 加上方案数
                    plans[x][y] += plans[fx][fy]

    for i in range(l-1, -1, -1):
        for j in range(i, -1, -1):  # 竖着向上
            x, y = j, i
            handle(x, y)

        for j in range(i-1, -1, -1):  # 横着向左
            x, y = i, j
            handle(x, y)

    if plans[0][0] == 0:
        return [0, 0]

    return [score[0][0] % M, plans[0][0] % M]

def pathsWithMaxScore(board: list) -> list:

froms = ((1, 0), (0, 1), (1, 1))

M = 1000000007

l = len(board)

score = [[0 for i in range(l)] for i in range(l)] # 得分

plans = [[0 for i in range(l)] for i in range(l)] # 方案

board[0] = '0' + board[0][1:] # 把E替换成0

plans[l - 1][l - 1] = 1

def handle(x, y):

if board[x][y] == 'X':

return

for x1, y1 in froms:

fx, fy = x + x1, y + y1

if fx < l and fy < l and board[fx][fy] != 'X': # 能走

update = int(board[x][y]) + score[fx][fy] # 更新后的分

if update > score[x][y]: # 分数更高了方案数等于来的时候的方案数

score[x][y] = update

plans[x][y] = plans[fx][fy]

elif update == score[x][y]: # 分数相同加上方案数

plans[x][y] += plans[fx][fy]

for i in range(l-1, -1, -1):

for j in range(i, -1, -1): # 竖着向上

x, y = j, i

handle(x, y)

for j in range(i-1, -1, -1): # 横着向左

x, y = i, j

handle(x, y)

if plans[0][0] == 0:

return [0, 0]

return [score[0][0] % M, plans[0][0] % M]