周赛笔记253

一、检查字符串是否为数组前缀

1. 暴力

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        arr = []
        tmp = ""

        for word in words:
            tmp += word
            arr.append(tmp)

        return s in arr

二、移除石子使总数最小

1. 堆

from math import floor
from heapq import *

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        h = [-num for num in piles]
        heapify(h)

        for i in range(k):
            num = heappop(h)
            heappush(h,floor(num/2))

        #print(h)
        return -sum(h)

# 数字转负，python 的 heapq 为小根堆

三、使字符串平衡的最小交换次数

1. 双指针

class Solution:
    def minSwaps(self, s: str) -> int:
        l, r = 0, len(s)-1
        s = list(s)
        stack = []
        ans = -1 

        while l < r:
            while l<r and not (s[l]=="]" and not stack):
                if s[l]=="[":
                    stack.append(s[l])
                else:
                    stack.pop()
                l += 1

            while l<r and not (s[r]=="[" and not stack):
                if s[r]=="]":
                    stack.append(s[r])
                else:
                    stack.pop()
                r -= 1

            s[l]="["
            s[r]="]"
            ans += 1
        return ans

2. 官方题解

class Solution:
    def minSwaps(self, s: str) -> int:
        cnt = mincnt = 0
        for ch in s:
            if ch == '[':
                cnt += 1
            else:
                cnt -= 1
                mincnt = min(mincnt, cnt)
        return (-mincnt + 1) // 2

四、找出到每个位置为止最长的有效障碍赛跑路线

1. dfs，超时

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        ans = []

        def dfs(arr, h, n, k):
            if n==0: return k

            tmp = [dfs(arr[:i],arr[i],i,k+1) for i in range(n-1, -1, -1) if arr[i]<=h]
            if tmp:
                return max(tmp)

            return k

        for i,h in enumerate(obstacles):
            arr = obstacles[:i]
            ans.append(dfs(arr,h,len(arr),1))

        return ans
#... 好菜

2. 动态规划 + 二分查找

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        d = []
        ans = []

        for ob in obstacles:
            if not d or ob >= d[-1]:
                d.append(ob)
                ans.append(len(d))
            else:
                loc = bisect_right(d, ob)
                ans.append(loc + 1)
                d[loc] = ob

        return ans

#copy
#参考第300题