16场双周赛

题目描述5135

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

提示：

1 <= arr.length <= 10^4
1 <= arr[i], target <= 10^5

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findBestValue(_ arr: [Int], _ target: Int) -> Int {
           
    var arr = arr.sorted()
    let n = arr.count
    arr.append(Int.max)
    var at = 0, best = Int.max, bi = 0, sum = 0
    for i in 0...target+5 {
        while arr[at] <= i {
            sum += arr[at]
            at += 1
        }
        var tmp = sum + (n - at) * i
        tmp = abs(tmp - target)
        if tmp < best {
            best = tmp
            bi = i
        }
    }
    return bi

}

题目描述5137

给你一个正方形字符数组 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]

提示：

2 <= board.length == board[i].length <= 100

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func pathsWithMaxScore(_ board: [String]) -> [Int] {
    let dic: [Character :Int] = ["1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8,
                                 "9": 9, "E": 0, "S": 0]
    let n = board.count
    var martrix =  [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
    for i in board.indices {
        let chars = Array(board[i])
        for j in chars.indices {
            martrix[i][j] = dic[chars[j], default: -1]
        }
    }
    if martrix[n-1][n-1] == -1 { return [0, 0] }
    var methodMatrix = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
    methodMatrix[n-1][n-1] = 1
    var scoreMatrix = martrix

    for i in stride(from: n-2, to: -1, by: -1) {
        methodMatrix[n-1][i] = (martrix[n-1][i] == -1 ? 0 : methodMatrix[n-1][i+1])
        scoreMatrix[n-1][i] =  (methodMatrix[n-1][i] == 0 ? -1 : scoreMatrix[n-1][i+1] + martrix[n-1][i])
        methodMatrix[i][n-1] = (martrix[i][n-1] == -1 ? 0 : methodMatrix[i+1][n-1])
        scoreMatrix[i][n-1] =  (methodMatrix[i][n-1] == 0 ? -1 : scoreMatrix[i+1][n-1] + martrix[i][n-1])
    }
    let md = 1000_000_007
    for r in stride(from: n-2, to: -1, by: -1) {
        for c in stride(from: n-2, to: -1, by: -1) where martrix[r][c] != -1 {
            let d = max(-1, scoreMatrix[r+1][c+1])
            let a = max(-1, scoreMatrix[r][c+1])
            let b = max(-1, scoreMatrix[r+1][c])
            let maxv = max(a, b, d)
            if maxv == -1 {
                scoreMatrix[r][c] = -1
                continue
            }
            if a == maxv {
                methodMatrix[r][c] = (methodMatrix[r][c] + methodMatrix[r][c+1])%md
            }
            if b == maxv {
                methodMatrix[r][c] = (methodMatrix[r][c] + methodMatrix[r+1][c])%md
            }
            if d == maxv {
                methodMatrix[r][c] = (methodMatrix[r][c] + methodMatrix[r+1][c+1])%md
            }
            scoreMatrix[r][c] = (maxv+martrix[r][c])%md
        }
    }
    return methodMatrix[0][0] == 0  ? [0, 0] : [scoreMatrix[0][0], methodMatrix[0][0]]
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-paths-with-max-score