周赛笔记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

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

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


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