letcode 双指针数组-day

import collections
from typing import List


# 将数组中的所有值为 0 的元素移到数组末尾
def remove_right_0(arr):
    slow, fast = 0, len(arr) - 1
    while slow < fast:
        while slow < fast and arr[fast] == 0:
            fast -= 1
        while slow < fast and arr[slow] != 0:
            slow += 1
        if slow < fast:
            tmp = arr[slow]
            arr[slow] = arr[fast]
            arr[fast] = tmp
            fast -= 1
            slow += 1
    print(arr)


# 对数组中的某些元素进行「原地删除」。
def remove_val(arr, val=0):
    slow, fast = 0, 0
    while fast < len(arr):
        if arr[fast] != val:
            arr[slow] = arr[fast]
            slow += 1
        fast += 1

    print(arr[0:slow])


# 删除有序数组中的重复项
def remove_dump(arr):
    slow, fast = 0, 0
    while fast < len(arr):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
        fast += 1

    print(arr[0:slow + 1])


# 有序数组 两数之和
def twoSum(arr, target):
    slow, fast = 0, len(arr) - 1
    while slow < fast:
        slow_arr_fast = arr[slow] + arr[fast]
        if slow_arr_fast < target:
            slow += 1
        elif slow_arr_fast > target:
            fast -= 1
        else:
            return slow + 1, fast + 1
    return -1, -1


def binarySearch(arr, target):
    slow, fast = 0, len(arr) - 1
    while slow < fast:
        mid = (slow + fast) // 2
        if arr[mid] < target:
            slow = mid + 1
        elif arr[mid] > target:
            fast = mid - 1
        else:
            return mid
    return -1


def reverse_arr(arr):
    slow, fast = 0, len(arr) - 1
    while slow < fast:
        tmp = arr[slow]
        arr[slow] = arr[fast]
        arr[fast] = tmp
        slow += 1
        fast -= 1
    print(arr)


# 最长回文字串
class Solution:
    def palindrome(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1: right]

    def longestPalindrome(self, s: str) -> str:
        res = ''
        for i in range(len(s)):
            s1 = self.palindrome(s, i, i)
            s2 = self.palindrome(s, i, i + 1)
            res = res if len(res) > len(s1) else s1
            res = res if len(res) > len(s2) else s2
        return res

if __name__ == '__main__':
    # remove_dump([1, 1, 2])
    # print(twoSum([2, 7, 11, 15], 9))
    # print(binarySearch([2, 7, 11, 15], 11))
    # print(reverse_arr([2, 7, 11, 15]))
    s = Solution()
    print(s.longestPalindrome("cbbd"))

数组 k

# n 个正整数的数组和一个正整数 target， 找出最短和>=target的数组长度，
def minSubArrayLen(arr, target):
    n = len(arr)
    left = 0
    ans = n + 1
    s = 0
    for right, x in enumerate(arr):
        s += arr[right]
        while s - arr[left] >= target:
            s -= arr[left]
            left += 1
        if s >= target:
            ans = min(ans, right - left + 1)
    return ans if ans <= n else 0

#给你一个整数数组 nums 和一个整数 k ，
#请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
def numSubarrayProductLessThanK(nums: List[int], k: int) -> int:
    if k <= 1:
        return 0
    ans = 0
    s = 1
    left = 0
    for right, x in enumerate(nums):
        s = s * x
        while s >= k:
            s = s / nums[left]
            left += 1
        ans += right - left + 1
    return ans

# 无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
def lengthOfLongestSubstring(s: str) -> int:
    ans = 0
    left = 0
    cnt = {}
    for right, x in enumerate(s):
        cnt[x] = cnt.get(x, 0) + 1
        while cnt[x] > 1:
            cnt[s[left]] = cnt[s[left]] - 1
            left += 1
        ans = max(ans, right - left + 1)
    return ans