from typing import List


class CQueue:
    """两个栈实现一个队列"""
    def __init__(self):
        self.stackA = []
        self.stackB = []

    def append_tail(self, value: int) -> None:
        self.stackA.append(value)

    def pop_head(self) -> int:
        if not self.stackB:
            if not self.stackA:
                return -1
            else:
                for i in range(len(self.stackA)):
                    self.stackB.append(self.stackA.pop())
        return self.stackB.pop()


def is_palindrome(x: int) -> bool:
    """递归解决回文数"""
    def inner(s, flag=True) -> bool:
        s = str(s)
        if len(s) in (0, 1):
            return flag
        if s[0] == s[-1]:
            return inner(s[1:-1])
        else:
            flag = False
            return flag
    return inner(x)


def two_sum(nums: List[int], target: int) -> List[int]:
    """两数之和"""
    dic = {}
    for k, v in enumerate(nums):
        if target - v in dic:
            return [dic[target - v], k]
        dic[v] = k


def roman_int(s: str) -> int:
    """罗马数字转整型"""
    mapping = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    total = 0
    length = len(s)
    for i in range(length):
        if i < length - 1 and mapping[s[i]] < mapping[s[i+1]]:
            total -= mapping[s[i]]
        else:
            total += mapping[s[i]]
    return total


def plus_one(digits: List[int]) -> List[int]:
    """加一"""

    a = ""
    for i in digits:
        a += str(i)
    return list(map(int, str(int(a) + 1)))


def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """合并两个有序数组"""
    i, j = 0, 0
    while j < n:
        if i > m + j:
            nums1[i: i+n-j] = nums2[j:n]
            break
        if nums1[i] < nums2[j]:
            i += 1
        else:
            nums1[i], nums1[i+1:] = nums2[j], nums1[i: len(nums1) - 1]
            j += 1
            i += 1


def last_remaining1(n: int, m: int) -> int:
    """约瑟夫环正常解法"""
    index = 0
    lis = list(range(n))
    while len(lis) > 1:
        index = (index +m - 1) % len(lis)
        lis.pop(index)
    return lis.pop()


def last_remaining2(n: int, m: int) -> int:
    """约瑟夫环公式法"""
    res = 0
    for i in range(2, n+1):
        res = (res + m) % i
    return res


def pivot_index(nums: List[int]) -> int:
    """寻找数组中心下标"""
    nums_count = sum(nums)
    left = 0
    for index, value in enumerate(nums):
        if left + left + value == nums_count:
            return index
        else:
            left += value
    return -1


def longest_common_prefix(strs: List[str]) -> str:
    """寻找最长公共前缀"""
    n = 0
    for i in list(zip(*strs)):
        if len(set(i)) == i:
            n += 1
        else:
            break
    return strs[0][:n]


def str_index(haystack: str, needle: str) -> int:
    """找字符串的下标"""
    if needle in haystack:
        return haystack.index(needle)
    return -1


def reverse_str(s: List[str]) -> None:
    """翻转字符串：这么简单的面试题。。卡壳了"""
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1


def array_pair_sum(nums: List[int]) -> int:
    """数组拆分"""
    nums.sort()
    return sum(nums[::2])


def find_max_one(nums: List[int]) -> int:
    """找最大1的个数"""
    a, b = 0, 0
    for i in range(len(nums)):
        if nums[i] == 0:
            if a > b:
                b = a
            a = 0
        else:
            a += 1
    return max(a, b)


def reverse_words(s: str) -> str:
    """反转字符串中的单词: 写不下去了。用内置函数"""
    return " ".join([i[::-1] for i in s.split()])


def search_insert(nums: List[int], target: int) -> int:
    """搜索插入的位置: 二分查找的思路"""
    left, right = 0, len(nums) - 1
    while left < right:
        middle = (left + right) // 2
        if nums[middle] < target:
            left = middle + 1
        elif nums[middle] > target:
            right = middle - 1
        else:
            return middle
    if nums[left] < target:
        return left + 1
    else:
        return left


def move_zero(nums: List[int]) -> None:
    """移动0:不等于0的放最前边。补0"""
    slow = 0
    for k, v in enumerate(nums):
        if v != 0:
            nums[slow] = v
            slow += 1
    for i in range(slow, len(nums)):
        nums[i] = 0


def remove_item(nums: List[int], val: int) -> int:
    """移除指定元素"""
    m = 0
    for k, v in enumerate(nums):
        if v != val:
            nums[m] = v
            m += 1
    return m


def remove_dup(nums: List[int]) -> int:
    """移除重复项"""
    m = 0
    for i in range(len(nums)):
        if m < 1 or nums[i] != nums[m-1]:
            nums[m] = nums[i]
            m += 1
    return m