2.算法-双指针(滑动窗口)

滑动窗口算法通用模板

def slidingWindow(self, s: str, p: str):
        left, right = 0, 0
        #一些初始化
        while right < len(s):
            c1 = s[right]
            right += 1
            #做一些逻辑处理
            while (窗口需要shrink的条件):
                c2 = s[left]
                left += 1
                #再做一些逻辑处理

3. 无重复字符的最长子串

def lengthOfLongestSubstring(self, s: str) -> int:
        left=right=count=max_l=0#count表示字符重复数
        from collections import defaultdict
        dic = defaultdict(int)
        while right<len(s):
            if dic[s[right]]>0:
                count+=1#如果已经存在,表示重复
            dic[s[right]]+=1
            right+=1#因为这里提前+1所以后面算length是right-left
            while count>0:#这里主要理解shrink条件
                if dic[s[left]]>1:
                    count-=1
                dic[s[left]]-=1
                left+=1
            max_l=max(right-left,max_l)
        return max_l

438. 找到字符串中所有字母异位词

def findAnagrams(self, s: str, p: str) -> List[int]:
        left, right = 0, 0
        p_arr = [0] * 26
        s_arr = [0] * 26
        for c in p:
            p_arr[97-ord(c)] += 1
        ans = []
        while right < len(s):
            c1 = s[right]
            right += 1
            s_arr[97-ord(c1)] += 1
            if p_arr == s_arr:
                ans.append(left)
            while (right+1-left>len(p)):
                c2 = s[left]
                left += 1
                s_arr[97-ord(c2)] -= 1
                if p_arr == s_arr:
                    ans.append(left)
        return ans

某度面试题:求子串重复数目

def getCount(s,substr):
    ans = 0
    p1 = p2 = 0
    while(p1 < len(s)):
        if  p2<len(substr) and s[p1]==substr[p2]: #第一次写的时候没有写p2<len(str) 导致当len(substr)==1的时候判断substr[p2]会越界
            if p2 == len(substr)-1:
                ans += 1
                p2 = 0
            p1 += 1
            p2 += 1 
        else:
            p2 = 0 
            if s[p1]!=substr[p2]:
                p1 += 1      
    return ans

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

def removeDuplicates(self, nums: List[int]) -> int:
        low,high = 0,1 # 初始化双指针相邻位置
        while(high<len(nums)):
            if nums[high] == nums[low]: 
                high += 1 #重复则跳过
            else:
                nums[low+1] = nums[high] #不重复赋值且慢指针前进
                low+=1
        return low + 1

402. 移掉K位数字

思路：单调栈

numStack = []
for digit in num:
    while k and numStack and numStack[-1] > digit:
        numStack.pop()
        k -= 1
    numStack.append(digit)

# 如果 K > 0，删除末尾的 K 个字符
finalStack = numStack[:-k] if k else numStack
return "".join(finalStack).lstrip('0') or "0"

经典用链表思路解决数组问题

287. 寻找重复数

def findDuplicate(self, nums: List[int]) -> int:
        #思路:快慢指针法，通过元素所在下标构建链表
        #如果有重复元素，则链表一定有环，转化为求环入口问题
        slow = fast = 0 
        slow = nums[slow] 
        fast = nums[nums[fast]]
        #快慢指针相遇
        while nums[fast]!=nums[slow]:
            slow=nums[slow]
            fast=nums[nums[fast]]
        #把慢指针放回起始位置，再次相遇时就是入口位置，也就是重复元素所在位置
        slow = 0
        while(nums[slow]!=nums[fast]):
            slow=nums[slow]
            fast=nums[fast]
        return nums[slow]

4. 219. 存在重复元素 II

独特的用set 解决的滑动窗口方法，很经典啊感觉

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        record = set()
        for i in range(len(nums)):
            if nums[i] in record:
                return True
            record.add(nums[i])
            if len(record) == k + 1:
                record.remove(nums[i-k])
        return False

不行了，最近开始质疑自己了，之前碰到一个双指针的问题，然后是看了答案
这次又来一个，看着还是写的很复杂最后也没有写出来

1. 713. 乘积小于K的子数组

def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1: return 0
        prod = 1
        ans = left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod /= nums[left]
                left += 1
            ans += right - left + 1
        return ans

你细看这么简单，你品呀。。。仔细品