周赛笔记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 个单位的木棍,棍上从 0n 标记了若干位置。
给你一个整数数组 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的不是表,是函数了,厉害

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录