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

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

  • Red
  • Green
  • Blue
  1. Bird
  2. McHale
  3. Parish
  • Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aliquam hendrerit mi posuere lectus. Vestibulum enim wisi, viverra nec, fringilla in, laoreet vitae, risus.
  • Donec sit amet nisl. Aliquam semper ipsum sit amet velit. Suspendisse id sem consectetuer libero luctus adipiscing.

  1. This is a list item with two paragraphs. Lorem ipsum dolor
    sit amet, consectetuer adipiscing elit. Aliquam hendrerit
    mi posuere lectus.

    Vestibulum enim wisi, viverra nec, fringilla in, laoreet
    vitae, risus. Donec sit amet nisl. Aliquam semper ipsum
    sit amet velit.

  2. Suspendisse id sem consectetuer libero luctus adipiscing.

  • A list item with a blockquote:

    This is a blockquote
    inside a list item.

This is an example inline link.

This link has no title attribute.

斜体文本
粗体文本
粗斜体文本

表头 表头
单元格 单元格
单元格 单元格

带下划线文本

  1. 第一项：
    • 第一项嵌套的第一个元素
    • 第一项嵌套的第二个元素
  2. 第二项：
    • 第二项嵌套的第一个元素
    • 第二项嵌套的第二个元素
  • 第一项

    菜鸟教程
    学的不仅是技术更是梦想

  • 第二项

链接也可以用变量来代替，文档末尾附带变量地址：
这个链接用 1 作为网址变量 Google
这个链接用 runoob 作为网址变量 Runoob
然后在文档的结尾为变量赋值（网址）baidu

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

CentOS 7 安装Python3、pip3

CentOS 7 默认安装了 Python 2，当需要使用 Python 3 的时候，可以手动下载 Python 源码后编译安装。

一、安装 Python 3

1.1 安装准备

$ sudo mkdir /usr/local/python3 # 创建安装目录

# 下载 Python 源文件
$ wget --no-check-certificate https://www.python.org/ftp/python/3.6.0/Python-3.6.0.tgz
# 注意：wget获取https的时候要加上：--no-check-certificate

$ tar -xzvf Python-3.6.0.tgz # 解压缩包

$ cd Python-3.6.0 # 进入解压目录

1.2 编译安装

$ sudo ./configure --prefix=/usr/local/python3 # 指定创建的目录

$ sudo make

$ sudo make install

1.3 配置

1.3.1 两个版本共存

创建 python3 的软链接：

$ sudo ln -s /usr/local/python3/bin/python3 /usr/bin/python3

这样默认的 Python 版本就替换为 Python 3 了。

因为 yum 使用 Python 2，因此替换为 Python 3 后可能无法正常工作，因此修改 yum 配置文件

$ sudo vi /usr/bin/yum

将第一行指定的 python 版本改为 python2.7（#!/usr/bin/python 改为 #!/usr/bin/python2.7）

二、安装 pip

2.1 yum 安装

# 首先安装 epel 扩展源
$ sudo yum -y install epel-release

# 安装 python-pip
$ sudo yum -y install python-pip

# 清除 cache
$ sudo yum clean all

通过这种方式貌似只能安装 pip2，想要安装 Python 3 的 pip，可以通过以下的源代码安装方式。

2.2 源码安装

# 下载源代码
$ wget --no-check-certificate https://github.com/pypa/pip/archive/9.0.1.tar.gz

$ tar -zvxf 9.0.1.tar.gz # 解压文件

$ cd pip-9.0.1

# 使用 Python 3 安装
$ python3 setup.py install

创建链接：

$ sudo ln -s /usr/local/python3/bin/pip /usr/bin/pip3

2.3 升级 pip

$ pip install --upgrade pip

备注：安装好Python3 之后，不仅需要改/usr/bin/yum的第一行，也需要将 /usr/libexec/urlgrabber-ext-down 的第一行修改为 #! /usr/bin/python2