编程知识 cdmana.com

【每日算法】算法复习一

Hash

存在重复元素 II

题目

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums[i]=nums[j],并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

思路

def containsNearbyDuplicate(nums, k):
    #定义 一个map,去记录每个元素在数组中的索引
    dic={}
    for i,v in enumerate(nums):
        if v in dic:
            #判断 是否满足索引差的绝对值至多为 k
            # print(dic[v],i,dic[v]-i)
            if i-dic[v]<=k:
                return True
        dic[v]=i
    return False

存在重复元素 III

题目

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i]-nums[j])<=t ,同时又满足abs(i-j) <= k 。
如果存在则返回 true,不存在返回 false。
示例 1:
输入:nums = [1,2,3,1], k = 3, t = 0
输出:true
示例 2:
输入:nums = [1,0,1,1], k = 1, t = 2
输出:true
示例 3:
输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false

思路

abs(i-j)=k可知,窗口大小为k+1时,窗口内的元素索引差都会小于k,然后在用新增的元素与窗口内的其他元素进行比较差值是否满足abs(nums[i]-nums[j])<=t即可

def containsNearbyAlmostDuplicate(nums, k, t):
    #abs(i-j)<=t,可知窗口的大小为k+1
    q=collections.deque()
    # print(q)
    for i,v in enumerate(nums):
        q.append(i)
        #如果超过窗口的最大值,则移除左左侧的元素
        if len(q)>k+1:
            q.popleft()
        for j in q:
            if j<i and abs(nums[j]-nums[i])<=t:
                return True
    return False

可是在提交测试时,显示超时,时间复杂度len(nums)*k,显然滑动窗口的解法不合适,那使用桶排序吧

桶排序的思路:因为差值为t,所以需要t+1个桶,则桶内每个元素的差值都<=t,如果当前桶内没有元素,则往前一个桶查找,如果有值,并且<=u-t,或者往下一个桶找,并且>=u+t为满足条件,并且k去维护桶的总个数

def containsNearbyAlmostDuplicate(nums, k, t):
    def getIdx(u):
        return u//(t+1)
    buckets={}#定义一个集合
    for i,v in enumerate(nums):
        # print(buckets)
        idx=getIdx(v)#找到该元素数据哪个桶
        #如果集合中保存这个元素,则满足条件直接返回
        if idx in buckets:
            return True
        #找上一个,下一个桶
        if idx-1 in buckets and buckets[idx-1]>=v-t:
            return True
        if idx+1 in buckets and buckets[idx+1]<=v+t:
            return True
        #保存当前元素
        buckets[idx]=v
        if len(buckets)>k:
            buckets.pop(getIdx(nums[i-k]))
    return False

滑动窗口

长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
输入:target = 4, nums = [1,4,4]
输出:1

思路

使用可变的窗口,首先扩大窗口,使窗口内的总和扩大,当出现和>=target时,记录窗口左右边界的值,然后再缩小窗口,直到小于target时,在记录左右边界,并与之前比较,记录最小的那个;然后在重复上面的步骤,直到数组结尾。

def minSubArrayLen(target, nums):
    #分别记录左右边界,和窗口内和
    left,right,total=0,0,0
    res=(left,float('inf'))
    n=len(nums)
    while right<n:
        total+=nums[right]
        if total>=target:#总和大于等于target时
            #左移左边界
            while left<=right and total>=target:
                #记录左右边界
                if res[1]-res[0]>right-left:
                    res=(left,right)
                total-=nums[left]
                left+=1
        right+=1
    return 0 if res[1]>n else res[1]-res[0]+1

无重复字符的最长子串

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例 4:
输入: s = ""
输出: 0

思路

依然使用双指针的方式定义窗口的左右边界,使用hash来保存窗口内的元素,当新元素在hash里面的话,移动左边界并逐步删除hash里面的元素,直到不存在重复的元素位置,并计算dic的长度

import collections
def lengthOfLongestSubstring(s):
    dic={}#保存窗口内的元素
    left=0#左右移动的窗口
    n=len(s)
    res=0#最后的结果
    q=collections.deque()
    for right in range(n):
        c=s[right]
        #如果在窗口里面,从左到右逐个判断是否相等,相等则删除
        while c in dic and left<right:
            dic.pop(s[left])
            left+=1
        dic[c]=right
        res=max(res,len(dic))
    return res

滑动窗口最大值

题目

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2:
输入:nums = [1], k = 1
输出:[1]
示例 3:
输入:nums = [1,-1], k = 1
输出:[1,-1]
示例 4:
输入:nums = [9,11], k = 2
输出:[11]
示例 5:
输入:nums = [4,-2], k = 2
输出:[4]

思路

使用一个递减队列保存里面的元素,队列的头和尾的元素差小于k就是保证窗口的大小,因为是递减的,最左侧的元素就是最大元素,新来一个元素,如果比队尾元素小则正常入队,如果比队尾元素大,则从队尾删除,知道遇到一个比自己大,或空队列了,在加入队列中

import collections
def maxSlidingWindow(nums, k):
    q=collections.deque()
    res=[]#保存最后的结果
    for i,v in enumerate(nums):
        #新加入的元素和最后一个元素比较,如果小于则加入,如果大于从未到头逐个删除
        while q and nums[q[-1]]<v:
            q.pop()#删除最后一个
        q.append(i)#加入新元素
        # print("---")
        while i>=k and q[0]<=i-k:#维护窗口的大小
            q.popleft()#移除超出做边界的元素
        # print(q,"===")
        if i>=k-1:#当形成固定窗口后
            res.append(nums[q[0]])
    return res

最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:
输入:s = "a", t = "a"
输出:"a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

思路

依然使用双指针定义窗口的边界,逐渐扩大窗口,使其包括所有的t,然后在逐步缩小窗口,为了快速的判断是否包括所有的t,用一个tmp遍历记录t字符长度,用dic记录t中每个字符个数,当dic中存在,且字符个数大于0时,则tmp-1,并从dic中减小字符个数,当tmp=0时,就是找到了包含t中全部的字符了。

def minWindow(s, t):
    left,right=0,0#窗口的边界
    #记录字符串t中每个字符的个数
    need=collections.defaultdict(int)
    for c in t:
        need[c]+=1
    tmp=len(t)#是否找到全部的标记
    n=len(s)
    res=(0,float('inf'))
    while right<n:
        if need[s[right]]>0:
            tmp-=1
        need[s[right]]-=1
        # print(tmp)
        if tmp==0:#如果找到了全部的字符,左移left
            #need[s[left]]<0为不在字符t中的字符
            while left<right and need[s[left]]<0:
                need[s[left]]+=1
                left+=1#左移
            #此时的left和right是包含t的最小字符串
            if res[1]-res[0]>right-left:
                res=(left,right)
            #找到在字典中的字符位置
            # print(need,tmp)
            need[s[left]]+=1
            tmp+=1
            left+=1
            # print(need,tmp)
        right+=1
    # print(res)
    return "" if res[1]>len(s) else s[res[0]:res[1]+1]

版权声明
本文为[Hitechr]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/hitechr/p/15120088.html

Scroll to Top