# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution: #假设为[1,2,3,4]
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: #递归出口
            return head
        newnode = head.next #储存第二位2
        head.next = self.swapPairs(head.next.next) #此时为[1,4,3]
        newnode.next = head #[2,1,4,3]
        return newnode

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        flowerbed = [0] + flowerbed + [0]
        for i in range(1,len(flowerbed)-1):
            if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:
                n -= 1
                flowerbed[i] = 1
        return n <= 0

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(amount+1):
           for coin in coins: #
               if i >= coin:
                   dp[i] = min(dp[i],dp[i-coin]+1)
        
        return -1 if (dp[-1] == float("inf")) else dp[-1]

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

#1
class Solution:
    def removeDuplicateLetters(s: str):
        res = ""
        while s: #用递归也可以
            loc = min(map(s.rindex,s)) #s.rindex是返回列表各值最后出现的索引 求这个最小的索引
            a = min(s[:loc+1]) #求字典序最小的
            res += a
            s = s[s.index(a):].replace(a,"") #把已经加入的和与其重复的都去掉了
        return res



#2
#遍历字符串，压入栈，如果遇到比栈顶小的元素且当前字符后面还有与栈顶相同的元素时，移除栈顶元素
class Solution:
    def removeDuplicateLetters(s: str) -> str:
        stack = []
        for i, t in enumerate(s):
            if t in stack:
                continue
            while stack !=[] and t < stack[-1] and s[i:].find(stack[-1]) != -1:
                stack.pop()
            stack.append(t)
        return "".join(stack)