力扣 第 153 场双周赛 讲题

Q1.字符串的反转度

• 签到题,直接建立一个映射表即可

class Solution:
    def reverseDegree(self, s: str) -> int:
        # 先建立映射表
        ss = "abcdefghijklmnopqrstuvwxyz"
        store = {}
        i = 0
        for j in range(26,0,-1):
            store[ss[i]] = j
            i += 1
        ans = 0
        for i,c in enumerate(s):
            ans += (i+1)*store[c]
        return ans©leetcode

Q2.操作后最大活跃区段数I

• 这题有点小坑：求解的是操作之后1的最大的全部数目，开始我求解的是最大的连续的1的个数，为了完成能够满足这个翻转的条件，我们需要将这个原来的字符串进行转换
• 在这里，我们将连续的1和连续的0合并，后续的操作只用关注连续的正数-负数-正数-负数-正数的5个连续的元素即可

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        # 打算使用前缀和后缀来写，分别来记录前面和后面的位置连续的1和0的个数
        news = '1' + s + '1'
        # 将使用一次遍历进行完成
        newstore = []
        one,zero = 0,0
        for i,c in enumerate(news):
            if c == '1':
                one += 1
            elif c == '0':
                zero -= 1
            if i > 0 :
                if c == '1' and news[i-1] == '0':
                    newstore.append(zero)
                    zero = 0
                elif c == '0' and news[i-1] == '1':
                    newstore.append(one)
                    one = 0
        if one != 0 :
            newstore.append(one)
        elif zero != 0:
            newstore.append(zero)
        # 其实只要判断，负数的个数如果小于等于1，那么直接返回最大的那个正数
        ans = 0
        fu = [i for i in newstore if i <0]
        for i in newstore:
            if i >0: ans += i
        if len(fu) <= 1:
            # 返回总和？
            return ans - 2
        # 否则的话，就找到正数+负数+正数+负数+正数的组合
        # 那么其实就要这个组合最少是5
        n = len(newstore)
        res = 0
        for i in range(n-4):
            if newstore[i] > 0 and newstore[i+1] <0 and newstore[i+2] >0 and newstore[i+3]<0 and newstore[i+4]>0:
                tmp = ans + abs(newstore[i+1]+newstore[i+3])
                res = max(res,tmp-2)
        return res 

• 更加通用的做法应该是使用前后缀分解，就是得记录这个1前面和后面的0的个数，当最后遍历的时候，出现一个1的位置的前面和后面的0的个数都不为0 ，那么我们就可以更新答案

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        # 打算使用前缀和后缀来写，分别来记录前面和后面的位置连续的1和0的个数
        # 首先求解的是全部的1的个数，但是只用求解这个010就是得记录1的左边和右边的0的数量即可
        n = len(s)
        pre = [0]*n 
        suf = [0]*n 
        zero = 0
        one = 0
        # 记录每一个'1'位置的前面的0的个数，连续的1的话，0的个数继承前面的1的情况
        for i,c in enumerate(s):
            if i == 0:
                if c == '0':
                    zero += 1
                if c == '1':
                    one += 1
                continue
            if c == '0':
                zero+=1
            elif c == '1':
                one += 1
                pre[i] = zero
                if i < n-1 and s[i+1] == '0':
                    zero = 0
        zero = 0
        # 记录每一个`1`的位置的后面的0的个数，连续的1的话，0的个数继承后面的1的情况
        for i in range(n-1,0,-1):
            if i == n-1:
                if s[i] == '0':
                    zero += 1
                continue
            if s[i] == '0':
                zero += 1
            elif s[i] == '1':
                suf[i] = zero
                if i > 0 and s[i-1] == '0':
                    zero = 0
        ans = 0
        for i in range(1,n-1):
            if s[i] == '1' and pre[i] * suf[i] != 0:
                ans = max(ans,pre[i]+suf[i])
        return one + ans

3500.将数组分割为子数组的最小代价

• 首先，这是一个划分的问题