"""
two-pointers, slide-window - EASY problems from leetcode for bytedance

141. 环形链表

"""

question_list = [141,167,26,88,392,350,27]

"""

141. 环形链表
167. 两数之和 II - 输入有序数组
88. 合并两个有序数组
26. 删除有序数组中的重复项
392. 判断子序列
350. 两个数组的交集 II
27. 移除元素（数组原地移除元素）

"""
def hasCycle(self, head):
    """
    快慢指针追，只要快慢相等了就一定有环。
    或者用hash也行，空间复杂度高一些。
    """
    if not head:
        return False
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

"""
167. 两数之和 II - 输入有序数组

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
"""
def twoSum_2(numbers, target):
    """
    :type numbers: List[int]
    :type target: int
    :rtype: List[int]
    """
    i, j = 0, len(numbers) - 1
    while i < j:
        s = numbers[i] + numbers[j]
        if s == target:
            return [i + 1, j + 1]
        elif s < target:
            i += 1
        else:
            j -= 1
    return []

"""
88. 合并两个有序数组

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
"""
def merge_two_seq_arrays(nums1, m, nums2, n):
    """
    思路：双指针+逆向填充。只要双指针，时间复杂度就是O(m+n)，逆向填充可保证空间复杂度是O（1）。
    关键：逆向填充，merge时反着来
    """
    i = m - 1
    j = n - 1
    z = m + n - 1

    while i >= 0 and j >= 0:
        if nums1[i] >= nums2[j]:
            nums1[z] = nums1[i]
            i -= 1
        else:
            nums1[z] = nums2[j]
            j -= 1
        z -= 1

    if i < 0:
        while j >= 0:
            nums1[z] = nums2[j]
            j -= 1
            z -= 1

"""
26. 删除有序数组中的重复项

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
"""
def removeDuplicates(nums):
    """
    快慢指针，原地替换
    tips：其实也可以不用记录上一个值，从1开始遍历就行了。
    """
    i, j = 0, 0
    last = float('inf')
    while i < len(nums):
        if nums[i] != last:
            nums[j] = nums[i]
            j += 1
        last = nums[i]
        i += 1
    return j

"""
392. 判断子序列
输入：s = "abc", t = "ahbgdc"
输出：true
"""
def isSubsequence(s, t):
        """
        双指针
        """
        i, j = 0, 0

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        if i == len(s):
            return True
        return False

"""
350. 两个数组的交集 II 
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
"""
def intersect(nums1, nums2):
    """
    [快慢指针]
    先排序!!
    然后再双指针，各走各的
    """
    nums1.sort()
    nums2.sort()

    ret = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            ret.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            i += 1
    return ret

"""
27. 移除元素
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
"""
def removeElement(nums, val):
    """
    [快慢指针]
    原地重新赋值，两个指针，一个遍历指针，一个赋值指针。这题其实有点意思。
    """
    idx, ret = 0, 0
    for num in nums:
        if num != val:
            nums[idx] = num
            idx += 1
            ret += 1
    return ret

"""
283. 移动零
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
"""
def moveZeroes(nums):
    """
    [快慢指针]
    原地重新赋值，两个指针，一个遍历指针，一个赋值指针。跟【27.移除元素】一样的
    """
    i, j = 0, 0
    while i < len(nums):
        if nums[i] != 0:
            nums[j] = nums[i]
            j += 1
        i += 1

    while j < len(nums):
        nums[j] = 0
        j += 1