Leetcode Weekly Contest Round 276

毕设真是令人头秃啊，感觉大四下学期事情不能算多，但是也谈不上少，居然还有双学位辅修plus专业选修课，但凡我有一点准备也不至于一点准备也没有啊🤷‍♂️

真的很想早点去Shopee看看，但是还是最好认清现实，放弃幻想，少想着提前去实习的事情了…

Anyway，最近还是在小心翼翼的跟进Golang的相关学习，也在进行Gin Web框架的相关学习，问题不大。

而周赛就当是我的Golang语法练习小结得了:(

起码练练语法，学点花哨的写法，尽量提升代码的健壮性也是极好的。

T1 2138. 将字符串拆分为若干长度为 k 的组

题目

字符串 s 可以按下述步骤划分为若干长度为 k 的组：

第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组，如果字符串剩下的字符不足 k 个，需使用字符 fill 来补全这一组字符。
注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。

给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。

示例 1：

输入：s = “abcdefghi”, k = 3, fill = “x”
输出：[“abc”,“def”,“ghi”]

解释：
前 3 个字符是 “abc” ，形成第一组。
接下来 3 个字符是 “def” ，形成第二组。
最后 3 个字符是 “ghi” ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 “abc”、“def” 和 “ghi” 。

示例 2：

输入：s = “abcdefghij”, k = 3, fill = “x”
输出：[“abc”,“def”,“ghi”,“jxx”]

解释：
与前一个例子类似，形成前三组 “abc”、“def” 和 “ghi” 。
对于最后一组，字符串中仅剩下字符 ‘j’ 可以用。为了补全这一组，使用填充字符 ‘x’ 两次。
因此，形成 4 组，分别是 “abc”、“def”、“ghi” 和 “jxx” 。

提示：

$1 \leq s.length \leq 100$
s 仅由小写英文字母组成
$1 \leq k \leq 100$
fill 是一个小写英文字母

题解

题目倒也没啥难度，纯简单模拟即可。在Java里面我们用substring()，在Golang里面直接用切片即可。

至于需要进行重复的字母fill，我们有strings.Repeat方法直接进行重复的处理。

Golang代码如下：

func divideString(s string, k int, fill byte) []string {
    n := len(s)
    res := []string{}
    for i := 0; i < n; i += k {
        if n - i >= k {
            res = append(res, s[i: i + k])
        } else {
            res = append(res, s[i: ] + strings.Repeat(string(fill), k - n + i))
        }
    }
    return res
}

T2 2139. 得到目标值的最少行动次数

题目

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。

在一次行动中，你可以做下述两种操作之一：

递增，将当前整数的值加 1（即， x = x + 1）。
加倍，使当前整数的值翻倍（即，x = 2 * x）。

在整个游戏过程中，你可以使用递增操作任意次数。但是只能使用加倍操作至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。

示例 1：

输入：target = 5, maxDoubles = 0
输出：4

解释：一直递增 1 直到得到 target 。

示例 2：

输入：target = 19, maxDoubles = 2
输出：7

解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。

示例 3：

输入：target = 10, maxDoubles = 4
输出：4

解释：
最初，x = 1 。
递增 1 次，x = 2 。
加倍 1 次，x = 4 。
递增 1 次，x = 5 。
加倍 1 次，x = 10 。

提示：

$1 \leq target \leq 10^9$
$0 \leq maxDoubles \leq 100$

题解

从1快速增长到我们所需的target，很显而易见的贪心思路可以让我们想到尽量使用翻倍来完成增长。但是target的奇偶情况对我们的操作造成了一些困扰。

我们不妨进行反向操作，将target使用减一和减半的操作使其快速下降到1。

与上方同理，我们应当尽量使用减半操作来实现数值的快速下降，减半操作的实行只受到如下两点的制约：一是maxDoubles的最多次数，而是如果当前的target是一个奇数，我们就无法进行减半操作，得首先进行减一操作。

此外，这里也留下了一个挺小的坑，当我们的减半次数maxDouble用尽时，我们没必要使用纯模拟的方式来进行手动倒数，这样会极大的增加运行时长，导致TLE。

至于写法，那自然可以使用更易理解的递归写法，也可使用普通的带模拟性质的循环写法。

递归写法如下：

func minMoves(target int, maxDoubles int) int {
    if target == 1 {
      //如果target已经减为一，直接跳出递归
        return 0
    }
    if maxDoubles == 0 {
      //减半剩余次数为0，进行倒数，返回即可
        return target - 1
    }
    if target % 2 == 1 {
      //奇数，先减一再减半
        return 1 + minMoves(target - 1, maxDoubles)
    }
  //偶数，减半，减半剩余次数减一
    return 1 + minMoves(target / 2, maxDoubles - 1)
}

或者模拟循环写法：

func minMoves(target int, maxDoubles int) (res int) {
    for target > 1 {
        if maxDoubles == 0 {
            return res + target - 1
        }
        if target % 2 == 1 {
            res++
            target--
        }
        maxDoubles--
        target /= 2
        res++
    }
    return
}

T3 2140. 解决智力问题

题目

给你一个下标从 0 开始的二维整数数组 questions ，其中 $questions[i] = [points_i, brainpower_i]$ 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择解决或者跳过操作。解决问题 i 将让你获得 $points_i$ 的分数，但是你将无法解决接下来的 $brainpower_i$ 个问题（即只能跳过接下来的 $brainpower_i$ 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
- 如果问题 0 被解决了，那么你可以获得 3 分，但你不能解决问题 1 和 2 。
- 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的最高分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5

解释：解决问题 0 和 3 得到最高分。

解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。

不能解决问题 1 和 2

解决问题 3 ：获得 2 分

总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。

跳过问题 0

解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。

不能解决问题 2 和 3

解决问题 4 ：获得 5 分

总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

提示：

$1 \leq questions.length \leq 10^5$
$questions[i].length == 2$
$1 \leq points_i, brainpower_i \leq 10^5$

题解

其实就是一道升级版的打家劫舍，也是使用动态规划DP相关的知识来进行解决的。

我来讲一讲我的一点简单点思路过程：

首先我们看到对于一道特定的题目questions[i]，我们一旦选取了就必须跳过后续的若干道题目。由于这个问题是看后继的，因此整个DP的计算都要逆着数组倒着来。

我们创建一个相同长度的数组dp，记dp[i]为从questions[i:]中选取，且使用questions[i]时的最大收益。那么就有：

$dp[i] = \max \limits_{i + brainpower_i \lt k \lt len(questions)}(points_i + dp[k])$

我们从后继可行选项中选出一个最大收益，与我们当前收益进行叠加。但是我们很快意识到这样不对，因为 $1 \leq questions.length \leq 10^5$ 会造成时间复杂度 $O(n^2)$ 过高。

最后考虑，我们将数组进行一点修改，我们认为dp数组表示的含义是，记dp[i]为questions[i:]中选取的最大收益。因此我们有：

$dp[i]=max(dp[i+1], points_i + dp[i + brainpower_i+1])$ 。

也就是questions[i:]中的最大收益由questions[i+1: ]（暗示当前问题不选取，直接使用[i + 1: ]最大收益）和points + dp[i + brainpower + 1]（暗示选取当前问题，将当前问题收益和[i + brainpower + 1: ]中的最大收益进行相加）中进行决定。

当然我们还需要处理一下简单的边界情况，如果i + brainpower + 1越界了，我们直接取零即可。

Golang代码如下：

func mostPoints(questions [][]int) int64 {
    dp := make([]int, len(questions))
    for i := len(questions) - 1; i >= 0; i-- {
        q := questions[i]
        if i + q[1] + 1 >= len(questions) {
            dp[i] = q[0]
        } else {
            dp[i] = q[0] + dp[i + q[1] + 1]
        }
        
        if i < len(questions) - 1 {
            dp[i] = max(dp[i], dp[i + 1])
        }
    }
    //fmt.Println(dp)
    return int64(dp[0])
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

T4 2141. 同时运行 N 台电脑的最长时间

题目

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的最长分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4

解释：

一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1]
输出：2

解释：

一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

提示：

$1 \leq n \leq batteries.length \leq 10^5$
$1 \leq batteries[i] \leq 10^9$

题解

这道题目我们不用去理解电池奇奇怪怪的分配方式，但是需要理解的是：

n台电脑同时运行x天的充要条件是保证所有电池所剩电量能够供应至少n*x的时长。

具体的充分性和必要性的证明如下，引用大佬的题解：

假设我们可以让 $n$ 台电脑同时运行 $x$ 分钟，那么对于电量大于 $x$ 的电池，其只能被使用 $x$ 分钟。因此每个电池的使用时间至多为 $\min(\textit{batteries}[i], x)$ ，我们将其累加起来，记作 $\textit{sum}$ 。那么要让 $n$ 台电脑同时运行 $x$ 分钟，必要条件是 $n\cdot x\le \textit{sum}$ 。

下面证明该条件是充分的，即当 $n\cdot x\le \textit{sum}$ 成立时，必然可以让 $n$ 台电脑同时运行 $x$ 分钟。

对于电量不小于 $x$ 的电池，我们可以让其给一台电脑供电 $x$ 分钟。由于一个电池不能同时给多台电脑供电，因此该电池若给一台电脑供电 $x$ 分钟，那它就不能用于其他电脑了。我们可以将所有电量不小于 $x$ 的电池各给一台电脑供电。

对于其余的电池，设其电量和为 $\textit{sum}'$ ，剩余 $n'$ 台电脑未被供电。我们可以随意选择剩下的电池，供给剩余的第一台电脑，多余的电池电量供给剩余的第二台电脑，依此类推。注意由于这些电池的电量小于 $x$ ，按照这种做法是不会出现同一个电池在同一时间供给多台电脑的。

由于 $\textit{sum}'=\textit{sum}-(n-n')\cdot x$ ，结合 $n\cdot x \le \textit{sum}$ 可以得到 $n'\cdot x\le \textit{sum}'$ ，这意味着剩余电池可以让剩余电脑运行 $x$ 分钟。充分性得证。

如果我们可以让 $n$ 台电脑同时运行 $x$ 分钟，那么必然也可以同时运行低于 $x$ 分钟，因此答案满足单调性，可以二分答案，通过判断 $n\cdot x\le \textit{sum}$ 来求解。

我使用Golang简单的写了一个二分：

func maxRunTime(n int, batteries []int) int64 {
    sum := 0
    for _, v := range batteries {
        sum += v
    }
    lo, hi := 0, sum
    res := 0
    for lo <= hi {
        mid := lo + (hi - lo) / 2
        //fmt.Println(mid)
        if check(mid, n, batteries) {
            res = mid
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return int64(res)
}

func check(time int, n int, batteries []int) bool {
    total := time * n
    sum := 0
    for _, v := range batteries {
        sum += min(v, time)
    }
    return sum >= total
}

func min(a, b int) int {
    if a > b {
        return b
    } else {
        return a
    }
}

居然发现Golang也有自带的二分…

func maxRunTime(n int, batteries []int) int64 {
	tot := 0
	for _, b := range batteries {
		tot += b
	}
	return int64(sort.Search(tot/n, func(x int) bool {
		x++
		sum := 0
		for _, b := range batteries {
			sum += min(b, x)
		}
		return n*x > sum
	}))
}

func min(a, b int) int { if a > b { return b }; return a }