1. 统计数组中峰和谷的数量

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

要注意检查数组下标

代码

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        i = 1
        while i < n and nums[i] == nums[i - 1]: i += 1
        if i >= n - 1: return 0 
        while i < n - 1:
            if (nums[i - 1] - nums[i]) * (nums[i] - nums[i + 1]) < 0:
                ans += 1
            elif (nums[i - 1] - nums[i]) * (nums[i] - nums[i + 1]) == 0:
                left = (nums[i - 1] - nums[i])
                i += 1
                while i < n - 1 and nums[i] == nums[i + 1]:
                    i += 1
                if i < n - 1 and left * (nums[i] - nums[i + 1]) < 0:
                    ans += 1
            i += 1
        return ans

2. 统计道路上的碰撞次数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

慢是慢了点，但是能过。

把碰撞看作一个字符串替换的过程，字符串中每个“RL”、“RS”、“SL”都必定会碰撞，那么只要每次都把这三种字符对替换为“S”即可，直到没有匹配。最后计算处理完的字符串比原始字符串少了多少“R”和“L”即可。

当然，这也算是个笨方法，正解应当是，除了道路两端往外跑的车，其他车都一定会碰撞，所以统计两端的连续想外跑的车即可。所以还是逆向思维，你要统计碰撞的车数，那我就找不会撞的车数。

代码

class Solution:
    def countCollisions(self, directions: str) -> int:
        old = ""
        new = directions
        while old != new:
            old = new
            new = new.replace("RL", "S")
        old = ""
        while old != new:
            old = new
            new = new.replace("RS", "S")
        old = ""
        while old != new:
            old = new
            new = new.replace("SL", "S")
        origin = directions.count("L") + directions.count("R")
        now = new.count("L") + new.count("R")
        return origin - now

正解

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions)
        ans = 0
        total = directions.count("L") + directions.count("R")
        for i in range(n):
            if directions[i] == "L": ans += 1
            else: break
        for i in range(n - 1, -1, -1):
            if directions[i] == "R": ans += 1
            else: break
        return total - ans

灵神的代码就更简洁了，用python库函数三行搞定

class Solution:
    def countCollisions(self, s: str) -> int:
        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞
        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞
        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞

其中 lstrip() 和 rstrip() 分别用于去除字符串的前缀、后缀指定字符，默认为空格。

3. 射箭比赛中的最大得分

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

在没有思路的时候，要想到考虑枚举，如果枚举需要考虑的情况不多，则应该可行。且若每次枚举仅有两种情况，要想到二进制枚举。

注意当箭多了的时候，全加到0上。

代码

class Solution:
    __res: List[int]
    __maxProfit: int
    def count(self, rest: int, profit: int, ans: List[int], cur: int, aliceArrows: List[int]) -> None:
        if cur >= 12: return
        if rest >= aliceArrows[cur] + 1:
            rest -= aliceArrows[cur] + 1
            ans[cur] = aliceArrows[cur] + 1
            profit += cur
            if profit > self.__maxProfit:
                self.__maxProfit = profit
                temp = list(ans)
                temp[0] += rest
                self.__res = list(temp)
            self.count(rest, profit, ans, cur + 1, aliceArrows)
            rest += aliceArrows[cur] + 1
            ans[cur] = 0
            profit -= cur
        self.count(rest, profit, ans, cur + 1, aliceArrows)
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        self.__res = [0 for i in range(12)]
        self.__maxProfit = 0
        profit = 0
        ans = [0 for i in range(12)]
        cur = 0
        self.count(numArrows, profit, ans, cur, aliceArrows)
        return self.__res

4. 由单个字符重复的最长子字符串

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

线段树相关，待复习。

代码

5. 将数组划分成相等数对

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

检查计数是否为偶数即可。

代码

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        cnts = [0 for i in range(501)]
        for num in nums: cnts[num] += 1
        for cnt in cnts:
            if (cnt & 1) != 0: return False
        return True

6. 字符串中最多数目的子字符串

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

细节考虑还不够。

代码

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        cnts = [0, 0]
        pre1 = []
        for ch in text:
            if ch == pattern[0]:
                cnts[0] += 1
            elif ch == pattern[1]:
                cnts[1] += 1
                pre1.append(cnts[0])
        if pattern[0] == pattern[1]:
            return ((cnts[0] + 1) * cnts[0] // 2)
        if cnts[0] < cnts[1]:
            return sum(pre1) + cnts[1]
        else:
            return sum(pre1) + cnts[0]

7. 将数组和减半的最少操作次数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

两分钟解决。实际上就是每次取出池子中的最大数，减半再放回去，直到总和不大于初始总和。那么用堆就可以了。

代码

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        ans = 0
        hp = []
        total = sum(nums)
        cur = total
        target = total / 2
        for num in nums:
            heappush(hp, -num)
        while cur > target:
            num = -heappop(hp)
            num /= 2
            cur -= num
            heappush(hp, -num)
            ans += 1
        return ans

8. 用地毯覆盖后的最少白色砖块

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

本来以为跟上次那个地毯覆盖砖块的差不多，但这次枚举不了好像。

题解使用DP，这个状态转移方式有点令人费解。

对于 dp[i][j] ，我们考虑是否使用第 i 块地毯的右边缘覆盖第 j 块砖。

如果不用，那么相当于 dp[i][j - 1] + floor[j] == "1" ，因为不用的话相当于第 j 块砖不存在的情况（地毯依旧是 i ）加上0或1。

如果用，那么 i 将会覆盖到从 j 往前 carpetLen 块砖，所以是这些砖和第 i 块地毯不存在的情况下的白砖数量。

在上面两种情况中取最小。需要注意的是，每次砖块下标是从 carpetLen * i 起始的，是因为当地毯总长度大于砖块数目时，剩余白砖一定为0，这比较难意识到。

代码

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        if numCarpets * carpetLen >= n: return 0
        dp = [[0 for i in range(n)] for j in range(numCarpets + 1)]
        cnt = 0
        for i in range(n):
            if floor[i] == "1":
                cnt += 1
            dp[0][i] = cnt
        for i in range(1, numCarpets + 1):
            for j in range(carpetLen * i, n):
                dp[i][j] = min(dp[i][j - 1] + int(floor[j]), dp[i - 1][j - carpetLen])
        return dp[numCarpets][n - 1]