class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        preA = list1
        for _ in range(a-1):
            preA = preA.next
        preB = preA
        for _ in range(b - a + 2):
            preB = preB.next
        preA.next = list2
        while list2.next:
            list2 = list2.next
        list2.next = preB
        return list1

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        m = 0  # At the beginning, it can only be constructed 0
        coins.sort()
        for c in coins:
            if c > m + 1:  # coins Sort，There is no comparison c Smaller
                break  # Unable to construct m+1，Continue to loop is meaningless
            m += c  # Can be constructed [0,m+c] All integer
        return m + 1  # [0,m] China m+1 An integer

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def res(num: int) -> int:
            return int(str(num)[::-1])
        cnt = Counter()
        ans = 0
        for i in nums:
            j = res(i)
            # whencnt[i-res(i)]When there is no existence，Will return0.
            ans += cnt[i-j]
            # Thus, incnt[i-j] have2次值的hour候才Will return到ansmiddle
            # becausecnt[]=1hour，yes不会经过ansAssociated
            cnt[i-j] += 1
        return ans % (10 ** 9 + 7)

1802. Specify the maximum value of the lower bid in the bounded array
      medium
      182
      company
      Amazon
      company
      Facebook
      Give you three positive integers n、index and maxSum 。You need to construct an array that meets all the conditions at the same time nums（Bidding from 0 start count）：

nums.length == n
nums[i] yes Positive integer ，in 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，in 0 <= i < n-1
nums 中所有元素之and不超过 maxSum
nums[index] Value maximize
Return to the array you constructed nums[index] 。

Notice：abs(x) equal x 的前提yes x >= 0 ；otherwise，abs(x) equal -x 。



Exemplary example 1：

enter：n = 4, index = 2,  maxSum = 6
Output：2
explain：Array [1,1,2,1] and [1,2,2,1] Meet all conditions。不存在其他在指定BiddingPlace具有更大值的有效Array。
Exemplary example 2：

enter：n = 6, index = 1,  maxSum = 10
Output：3


hint：

1 <= n <= maxSum <= 109
0 <= index < n

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        list1 = sentence1.split(' ')
        list2 = sentence2.split(' ')

        if len(list1) < len(list2):
            temp = list1
            list1 = list2
            list2 = temp
        ans=copy.deepcopy(list2)
        for i in list2:
            for index, j in enumerate(list1):
                if i == j and (index == 0 or index == len(list1) - 1):
                    ans.remove(i)
        if not ans:
            return True
        else:
            return False

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        words1 = sentence1.split()
        words2 = sentence2.split()
        i, j = 0, 0
        while i < len(words1) and i < len(words2) and words1[i] == words2[i]:
            i += 1
        while j < len(words1) - i and j < len(words2) - i and words1[-j - 1] == words2[-j - 1]:
            j += 1
        return i + j == min(len(words1), len(words2))

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        dict1 = defaultdict(set)
        list1 = [0] * k
        for i, j in logs:
            dict1[i].add(j)
        for i in dict1:
            print(dict1[i])
            # TypeError object of type ‘type‘ has no len() Because ofdictLess1
            list1[len(dict1[i]) - 1] += 1
        return list1

class MKAverage:

    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.list1 = []

    def addElement(self, num: int) -> None:
        self.list1.append(num)

    def calculateMKAverage(self) -> int:
        if len(self.list1) < self.m:
            return -1
        else:
            list2 = self.list1[-1:-self.m-1:-1]
            list2 = sorted(list2)
            list2 = list2[self.k:len(list2) - self.k]
        return sum(list2) // len(list2)

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        n = len(obstacles)
        dis = [[n] * 3 for _ in range(n)]
        dis[0][1] = 0
        q = deque([(0, 1)])  # starting point
        while True:
            i, j = q.popleft()
            d = dis[i][j]
            if i == n - 1: return d  # reach destination
            if obstacles[i + 1] != j + 1 and d < dis[i + 1][j]:  # To the right
                dis[i + 1][j] = d
                q.appendleft((i + 1, j))  # Add to the team
            for k in (j + 1) % 3, (j + 2) % 3:  # The other two other runways are enumerated（up/down）
                if obstacles[i] != k + 1 and d + 1 < dis[i][k]:
                    dis[i][k] = d + 1
                    q.append((i, k))  # Add to the tail

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Seek to solve whether the European -style distance from the center is less than r
        ans = [0] * len(queries)
        flag = 0
        for x, y, r in queries:
            for i, j in points:
                if ((x - i) ** 2 + (y - j) ** 2) ** (1 / 2) <= r:
                    ans[flag] += 1
            flag += 1
        return ans

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        points = sorted(points)

        res = [0 for _ in range(len(queries))]

        for i, (u, v, r) in enumerate(queries):
            left, right = u - r, u + r

            idx1 = bisect_left(points, [left, -inf])
            idx2 = bisect_right(points, [right, inf])

            for x, y in points[idx1: idx2 + 1]:
                if (v - r <= y <= v + r and 
                    (x - u) * (x - u) + (y - v) * (y - v) <= r * r):
  
                    res[i] += 1

        return res