lc marathon 8.3

899. 有序队列

当 K == 1 时， 只能循环移动每个元素，无法改变相对位置。因此只需要获取循环移动过程中字典序最小的序列。 当 K > 1 时， 可以生成当前字符串的任意序列。因此将原字符串排序生成字典序最小的序列。

dic=set()
minx=None
class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k==1:
            minx=s
            for index,st in enumerate(s):
                if s[1:]+s[0] <minx:
                    minx=s[1:]+s[0]
                s=s[1:]+s[0]
            return minx
        else:
            return "".join(sorted(s))

322. 零钱兑换

简单的背包问题，用动态规划即可

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        # dp[n] 表示n的时候最少的硬币数目

        # dp[n] = min(dp[n-l]) for l in ...

        dp=[0 for i in range(amount+1)]
        dp[0]=0
        for i in range(1,amount+1):
            ls=[]
            for coin in coins:
                if i-coin>=0 and dp[i-coin]!=-1:
                    ls.append(dp[i-coin]+1)
            if len(ls)!=0:
                dp[i]=min(ls)
            else:
                dp[i]=-1
        return dp[amount]

2279. 装满石头的背包的最大数量

贪心 排序即可

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        needs=[cap-rock for cap,rock in zip(capacity,rocks)]
        needs=sorted(needs)
        ns=0
        for need in needs:
            if additionalRocks>=need:
                additionalRocks-=need
                ns+=1
            else:
                break
        return ns
        

334. 递增的三元子序列

算出 从前往后的最小值数组

从后往前的最大值数组

有一个数 比它左边的最小值都大

            又比右边的最大值都小

那就满足啦

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        mins=[]
        min_num=nums[0]
        for num in nums:
            if num <= min_num:
                min_num=num
            mins.append(min_num)
        maxs=[]
        max_num=nums[-1]
        for num in nums[::-1]:
            if num>=max_num:
                max_num=num
            maxs.append(max_num)
        maxs=maxs[::-1]
        for index,num in enumerate(nums):
            if index!=0 and index!=len(nums)-1:
                if num>mins[index-1] and num<maxs[index+1]:
                    return True
        return False