周赛笔记213

第一题：https://leetcode-cn.com/problems/check-array-formation-through-concatenation/
第二题：https://leetcode-cn.com/problems/count-sorted-vowel-strings/
第三题：https://leetcode-cn.com/problems/furthest-building-you-can-reach/
第四题：https://leetcode-cn.com/problems/kth-smallest-instructions/

一、能否连接形成数组

输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出：true
解释：依次连接 [91]、[4,64] 和 [78]

输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        for piece in pieces:
            for x in piece:
                if x not in arr: 
                    return False
            pre=arr.index(i[0])
            for x in i[1:]:
                cur=arr.index(x)
                if cur-pre!=1:
                    return False
                pre+=1
        return True

# 有些繁杂，可以优化map

二、统计字典序元音字符串的数目

n=1 return 5 [“a”,”e”,”i”,”o”,”u”]
n=2 return 15 [“aa”,”ae”,”ai”,”ao”,”au”,”ee”,”ei”,”eo”,”eu”,”ii”,”io”,”iu”,”oo”,”ou”,”uu”]

# 方法一：暴力模拟
class Solution:
    def countVowelStrings(self, n: int) -> int:
        d={1:[],2:[1],3:[2,1],4:[3,2,1],5:[4,3,2,1]}
        ans=[5]
        tmp=ans.copy()
        for i in range(n-1):
            for j in ans:
                tmp+=d[j]
            ans=tmp.copy()
        return sum(ans)

#一开始有点炸，运行中ans变了，for也变了

# 方法二：
class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp=[1]*5
        for i in range(n-1):
            for j in range(5):
                for x in range(j+1,5):
                    dp[j]+=dp[x]
        return sum(dp)

#好好学一下,hzx

三、可以到达的最远建筑

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

• 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
• 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

# TLE dfs
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        
        def dfs(cur,bricks,ladders):
            if bricks<0: return cur-1
            if ladders<0: return cur-1
            if cur+1==len(heights): return cur
            
            height=heights[cur+1]-heights[cur]
            
            if height<0: return dfs(cur+1,bricks,ladders)  # 一：直接走
            
            return max(dfs(cur+1,bricks-height,ladders),dfs(cur+1,bricks,ladders-1))
        
        return dfs(0,bricks,ladders)

#优先队列+贪心
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        # 由于我们需要维护最大的 l 个值，因此使用小根堆
        q = list()
        # 需要使用砖块的 delta h 的和
        sumH = 0
        for i in range(1, n):
            deltaH = heights[i] - heights[i - 1]
            if deltaH > 0:
                heapq.heappush(q, deltaH)
                # 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块
                if len(q) > ladders:
                    sumH += heapq.heappop(q)
                if sumH > bricks:
                    return i - 1
        return n - 1

#设置一个优先队列来当梯子
#。。。。。。。。。。。。。。。。。。。

四、第 K 条最小指令

# 优先确定高位 + 组合计数
# 分解成小问题

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v,h=destination
        self.ans=""
        def f(v,h,k):
            if h==0:
                self.ans+="V"*v
            else:
                tmp=comb(h+v-1,h-1)  #高位为h的个数
                if k>tmp:
                    self.ans+="V"    
                    f(v-1,h,k-tmp)
                else:
                    self.ans+="H"
                    f(v,h-1,k)
        f(v,h,k)
        return self.ans

小结

11.1

困难可以学会很多啊，很多时候并不能事事如愿。

最近看了《大话西游之大圣娶亲》，
有感动，更多的无奈与自嘲，
他好像一条狗啊，那个落寞的背影取经去了…