周赛笔记201

一、整理字符串

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：

• 0 <= i <= s.length - 2
• s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。

请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的两个相邻字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意：空字符串也属于整理好的字符串，尽管其中没有任何字符

class Solution:
    def makeGood(self, s: str) -> str:
        stack=[]
        for i in s:
            last=None
            if stack: last=stack.pop()
                
            if last and (ord(i)-32==ord(last) or ord(last)-32==ord(i)): 
                continue
            else:
                stack.extend([last,i])
        return ''.join([i for i in stack if i])

#熟悉了stack，ord()与32，list.extend()

二、找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

S1 = "0"
当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
其中 +表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）

例如，符合上述描述的序列的前 4 个字符串依次是：

S1 = “0”
S2 = “011”
S3 = “0111001”
S4 = “011100110110001”
请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s='0'
        for i in range(n-1):
            s=s+'1'+''.join([str(int(i)^1) for i in s])[::-1]
        return s[k-1]

# 熟悉了 ^1 操作

三、和为目标值的非空不重叠子数组最大数目

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        res = 0
        pre = set([0])  #这是一个前缀和的集合
        
        sum = 0
        for num in nums:
            sum += num
            if sum - target in pre: #有一段和满足要求
                res += 1
                sum = 0
                pre = set([0])
            else:
                pre.add(sum)
        return res

# 像560.和为k的子数组,忘了
# 一遍就出来了,思路都固定死了，就是前缀和

四、切棍子的最小成本

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        import sys   
        sys.setrecursionlimit(10000000)  #改一下递归深度
        
        import functools
        @functools.lru_cache(None)   #用一下缓存

        def dp(i, j):
            res = float('inf')
            for c in cuts:
                if c > i and c < j:
                    res = min(res, dp(i, c) + dp(c, j) + j - i)
            if res == float('inf'):
                return 0
            return res
        
        return dp(0, n)

# 懂了一些，dp的不是表，是函数了，厉害