Leetcode第276场周赛write up

发表于

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

1
2
3
4
5
字符串 s 可以按下述步骤划分为若干长度为 k 的组：
第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。
注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。
给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。
1
2
3
4
5
6
7
8
输入：s = "abcdefghi", k = 3, fill = "x"
输出：["abc","def","ghi"]
解释：
前 3 个字符是 "abc" ，形成第一组。
接下来 3 个字符是 "def" ，形成第二组。
最后 3 个字符是 "ghi" ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 "abc"、"def" 和 "ghi" 。
1
2
3
4
5
6
输入：s = "abcdefghij", k = 3, fill = "x"
输出：["abc","def","ghi","jxx"]
解释：
与前一个例子类似，形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组，字符串中仅剩下字符 'j' 可以用。为了补全这一组，使用填充字符 'x' 两次。
因此，形成 4 组，分别是 "abc"、"def"、"ghi" 和 "jxx" 。

常规题，先分割，再填补。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def divideString(self, s, k, fill):
        """
        :type s: str
        :type k: int
        :type fill: str
        :rtype: List[str]
        """
        res = []
        while len(s)>=k:
            t = s[:k]
            s = s[k:]
            res.append(t)
        if len(s)==0:
            return res
        else:
            for i in range(k-len(s)):
                s+=fill
            res.append(s)
            return res

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

1
2
3
4
5
6
你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
在一次行动中，你可以做下述两种操作之一：
递增，将当前整数的值加 1（即， x = x + 1）。
加倍，使当前整数的值翻倍（即，x = 2 * x）。
在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。
1
2
3
输入：target = 5, maxDoubles = 0
输出：4
解释：一直递增 1 直到得到 target 。
1
2
3
4
5
6
7
8
输入：target = 19, maxDoubles = 2
输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。
1
2
3
4
5
6
7
8
输入：target = 10, maxDoubles = 4
输出：4
解释：
最初，x = 1 。 
递增 1 次，x = 2 。 
加倍 1 次，x = 4 。 
递增 1 次，x = 5 。 
加倍 1 次，x = 10 。

这道题我们首先能想到的是，尽可能多的使用“加倍”操作。既然是从1开始，我们就想办法让输入变为1即可。在操作的过程中，我们需要考虑两种情况：当前值是奇数还是偶数。
如果是奇数，我们需要让他变成偶数，方便我们的“除2”操作。因此给当前数减去1即可
如果是偶数，我们又需要考虑两种情况。是否可以进行”除2“操作。
也就是我们需要对maxDoubles的值进行判断。
如果maxDoubles大于零，那我们正常进行除法操作即可。
如果maxDoubles已经变为零，那我们也不需要一个一个的递减了，直接变为1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def minMoves(self, target, maxDoubles):
        """
        :type target: int
        :type maxDoubles: int
        :rtype: int
        """
        count = 0
        while target != 1:
            if target % 2:
                target -= 1
                count +=1
            else:
                if maxDoubles>0:
                    target /=2
                    count+=1
                    maxDoubles -=1
                else:
                    count+=target-1
                    target = 1
        return count

解决智力问题

1
2
3
4
5
6
给你一个下标从0开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri]。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。
请你返回这场考试里你能获得的 最高 分数。
1
2
3
4
5
6
7
输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
1
2
3
4
5
6
7
8
输入：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        #动态规划
        dp = [0 for _ in range(len(questions)+1)]
        for i in range(len(questions)-1,-1,-1):
            #如果当前位置加上brainpower没有超出数组长度
            if i+questions[i][1] < len(questions):
                """
                1.做这道题+做下一跳题的得分和
                2.不做这道题，做下一题的得分
                """
                dp[i] = max(questions[i][0] + dp[i + questions[i][1] + 1],dp[i + 1])
            else:
                #如果当前位置加上brainpower已经超出数组长度
                #当前位置的值是当前值的得分和下一个位置所得分之间的较大值
                dp[i] = max(dp[i+1],questions[i][0])
        return dp[0]