from collections import deque

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue1 = deque()  # in
        self.queue2 = deque()  # out


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.queue1.append(x)


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        assert not self.empty(), 'Empty stack!'
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        ret = self.queue1.popleft()
        self.queue1, self.queue2 = self.queue2, self.queue1
        return ret


    def top(self) -> int:
        """
        Get the top element.
        """
        assert not self.empty(), 'Empty stack!'
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        ret = self.queue1[0]
        self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1
        return ret


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.queue1) == 0 and len(self.queue2) == 0

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 首先是判断是存在num[i]==num[j]，存在的情况下才判断|i-j|<=k
        nums_len = len(nums)
        if nums_len <= 1:
            return False
        nums_dict = {}
        for i in range(nums_len):
            if nums[i] in nums_dict:
                if i-nums_dict[nums[i]] <= k:
                    return True
            nums_dict[nums[i]] = i
        return False

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        set1 = set(nums)
        if len(set1) == len(nums):
            return False
        else:
            return True

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapping = dict()
        used = set()
        for i, char in enumerate(s):
            if char not in mapping and t[i] not in used:
                mapping[char] = t[i]
                used.add(t[i])
            elif char not in mapping or mapping[char] != t[i]:
                return False
        return True

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<2:
            return 0;
        isPrime=[1]*n;
        # 合数对应0；素数对应1
        isPrime[0]=isPrime[1]=0;
        #埃式筛
        for i in range(2,int(n**0.5)+1):
            if isPrime[i]:
                isPrime[i*i:n:i]=[0]*((n-1-i*i)//i+1);#个数
        return sum(isPrime);

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        node = ListNode(val+1)
        node.next = head
        pre, cur = node, head
        while cur:
            if cur.val == val:
                pre.next = cur.next
                cur = cur.next
            else:
                pre = cur
                cur = cur.next
        return node.next

class Solution:
    def isHappy(self, n: int) -> bool:
        mem = set()                #利用 set（）集合，保存平方求和后的数值
        while n != 1:              #利用 while 实现循环      
            n = sum([int(i)**2 for i in str(n)])    #通过str（n）调取输入整数各个位数的值
            if n not in mem:       #若平方求和后的数值是首次出现，则添加进集合中
                mem.add(n)
            else:                  #若求和后数值，在集合中存在，则直接返回false,即出现死循环
                return False
        return True                #最终当n==1时，跳出while循环，返回true

class Solution:
    def rob(self, nums: List[int]) -> int:
        last = 0 
        now = 0
        for i in nums: 
            #这是一个动态规划问题
            last, now = now, max(last + i, now)
        return now

class Solution:
    def hammingWeight(self, n: int) -> int:
        return str(bin(n)).count('1')

class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 31
        while n:
            ret += (n & 1) << power
            n = n >> 1
            power -= 1
        return ret

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        while k != 0:
            nums.insert(0,nums.pop())
            k -= 1

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # 核心：数5，每个5会带来一个0，每个25会带来两个0，每个5^p会带来p个0
        i = 0
        f = 5
        while True:
            i += n//f
            if n//f==0:
                return i
                break
            f = f*5

class Solution:
    def titleToNumber(self, s: str) -> int:
        #26进制转10进制
        ans = 0
        for x in s:
            ans *= 26
            ans += ord(x)-ord('A')+1
        return ans

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

class Solution:
    def convertToTitle(self, n: int) -> str:
        s = ''
        while(n):
            n -= 1
            s = chr(n%26+65) + s
            n = n//26
        return s

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers)-1      
        while left < right:
            if numbers[left] + numbers[right] == target:                
                return [left+1, right+1]
            elif numbers[left] + numbers[right] < target:
                left = left + 1
            else:
                right = right - 1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

class MinStack:

    # 辅助栈和数据栈同步
    # 思路简单不容易出错

    def __init__(self):
        # 数据栈
        self.data = []
        # 辅助栈
        self.helper = []

    def push(self, x):
        self.data.append(x)
        if len(self.helper) == 0 or x <= self.helper[-1]:
            self.helper.append(x)
        else:
            self.helper.append(self.helper[-1])

    def pop(self):
        if self.data:
            self.helper.pop()
            return self.data.pop()

    def top(self):
        if self.data:
            return self.data[-1]

    def getMin(self):
        if self.helper:
            return self.helper[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        dic = {}
        while head:
            if head in dic:
                return True
            else:
                dic[head] = 1
            head = head.next
        return False

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for num in nums:
            a = a ^ num
        return a

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(filter(str.isalnum,s)).lower()
        return s==s[::-1]

第一种方法：深度优先搜索，时间复杂度 O(2^n)，这个通过不了 LeetCode，不过能 work，测试了多组测试样例是正确的

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        self.prices = prices
        self.profit = []
        self.helper(0, 0, 0)
        return max(self.profit)

    # have 0:未持有  1:持有
    def helper(self, i, have, profit):
        if i == len(self.prices):
            self.profit.append(profit)
            return
        if have: # 如果持有中
            self.helper(i+1, 0, profit + self.prices[i]) # 卖出
            self.helper(i+1, 1, profit) # 不动
        else: # 如果未持有
            self.helper(i+1, 0, profit) # 不动
            self.helper(i+1, 1, profit - self.prices[i]) # 买入

第二种方法：贪心算法，一次遍历，只要今天价格小于明天价格就在今天买入然后明天卖出，时间复杂度 O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                ans += prices[i] - prices[i-1]
        return ans

第三种方法：DP 动态规划，第 i 天只有两种状态，不持有或持有股票，当天不持有股票的状态可能来自昨天卖出或者昨天也不持有，同理，当天持有股票的状态可能来自昨天买入或者昨天也持有中，取最后一天的不持有股票状态就是问题的解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        dp = [[0]*2 for _ in range(n)]
        # dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
        dp[0][0], dp[0][1] = 0, - prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
        return dp[n-1][0]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 1. 记录【今天之前买入的最小值】
        # 2. 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
        # 3. 比较【每天的最大获利】，取最大值即可
        if len(prices) <= 1:
            return 0

        min_input = prices[0]
        max_profit = 0
        for p in prices[1:]:
            min_input = min(p, min_input)
            max_profit = max(max_profit, p - min_input)

        return max_profit

# 方法 1：生成一半，另一半对称生成的一半
class Solution1:
    def generate(self, rowIndex):
        cur = []
        for i in range(rowIndex + 1):
            # 每行首个元素为 1
            temp = [1]
            # 由上一行生成当前行前一半的元素
            for j in range(i // 2):
                temp += [pre[j] + pre[j + 1]]
            # 对称生成另一半后合并，并组成新杨辉三角
            cur = temp + temp[::-1][(i + 1) % 2:]
            pre = cur
        return cur


# 方法 2：直接循环计算生成
class Solution2:
    def generate(self, rowIndex):
        cur = [1]
        for i in range(1, rowIndex + 1):
            # 每行首个元素为 1
            temp = [1]
            # 由上一行循环生成当前行元素（除两端）
            for j in range(1, i):
                temp += [pre[j - 1] + pre[j]]
            # 添加最后一个元素 1，并组成新杨辉三角
            cur = temp + [1]
            pre = cur
        return cur


# 方法 3：先直接生成所需空间（用 1 填充），再循环计算更新生成
class Solution3:
    def generate(self, rowIndex):
        for i in range(rowIndex + 1):
            # 用 1 先填充每行所有元素
            cur = [1] * (i + 1)
            # 由上一行循环生成当前行元素（除两端）
            for j in range(1, i):
                cur[j] = pre[j - 1] + pre[j]
            pre = cur
        return cur


# 方法 4：使用公式
# 组合公式C(n,i) = n!/(i!*(n-i)!)
# 则第(i+1)项是第i项的倍数=(n-i)/(i+1)
class Solution4:
    def generate(self, rowIndex):
        temp = 1
        res = []
        for i in range(rowIndex + 1):
            res.append(temp)
            temp = temp * (rowIndex - i) // (i + 1)
        return res


# 方法 5：使用公式生成一半
class Solution5:
    def generate(self, rowIndex):
        temp = 1
        res = []
        # 生成前半部分
        for i in range((rowIndex) // 2 + 1):
            res.append(temp)
            temp = temp * (rowIndex - i) // (i + 1)
        # 前半部分与其镜像对称的后半部分合并
        return res + res[::-1][(rowIndex + 1) % 2:]


# 方法 6：当前行等于上一行前后添零累加：[1,4,6,4,1] = [0,1,3,3,1] + [1,3,3,1,0]
class Solution6:
    def generate(self, rowIndex):
        res = [1]
        for i in range(rowIndex + 1):
            # temp1, temp2 = [0] + res, res + [0]
            # res = [temp1[j] + temp2[j] for j in range(i + 1)]
            res = [([0] + res)[j] + (res + [0])[j] for j in range(i + 1)]
        return res