编程知识 cdmana.com

[daily algorithm] algorithm review I

Hash

There are duplicate elements II

subject

 Given an array of integers and an integer  k, Determine if there are two different indexes in the array  i  and  j, bring  nums[i]=nums[j], also  i  and  j  It's bad   The absolute value   At most  k.

 Example  1:
 Input : nums = [1,2,3,1], k = 3
 Output : true
 Example  2:
 Input : nums = [1,0,1,1], k = 1
 Output : true
 Example  3:
 Input : nums = [1,2,3,1,2,3], k = 2
 Output : false

Ideas

def containsNearbyDuplicate(nums, k):
    # Definition   One map, To record the index of each element in the array 
    dic={}
    for i,v in enumerate(nums):
        if v in dic:
            # Judge   The absolute value of whether the index difference is satisfied is at most  k
            # print(dic[v],i,dic[v]-i)
            if i-dic[v]<=k:
                return True
        dic[v]=i
    return False

There are duplicate elements III

subject

 Give you an array of integers  nums  And two integers  k  and  t . Please judge whether there is   Two different subscripts  i  and  j, bring  abs(nums[i]-nums[j])<=t , At the same time, they are satisfied with abs(i-j) <= k .
 Return if present  true, There is no return  false.
 Example  1:
 Input :nums = [1,2,3,1], k = 3, t = 0
 Output :true
 Example  2:
 Input :nums = [1,0,1,1], k = 1, t = 2
 Output :true
 Example  3:
 Input :nums = [1,5,9,1,5,9], k = 2, t = 3
 Output :false

Ideas

Yes abs(i-j)=k You know , Window size is k+1 when , The index difference of elements in the window will be less than k, Then compare the newly added element with other elements in the window to see if the difference meets abs(nums[i]-nums[j])<=t that will do

def containsNearbyAlmostDuplicate(nums, k, t):
    #abs(i-j)<=t, The size of the window is k+1
    q=collections.deque()
    # print(q)
    for i,v in enumerate(nums):
        q.append(i)
        # If the maximum value of the window is exceeded , Then remove the element on the left 
        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

But when you submit the test , Display timeout , Time complexity len(nums)*k, Obviously, the solution of sliding window is not appropriate , Then use bucket sorting

The idea of bucket sorting : Because the difference is t, So we need to t+1 A barrel , Then the difference of each element in the bucket is <=t, If there are no elements in the current bucket , Then look in the next bucket , If it's worth it , also <=u-t, Or look in the next bucket , also >=u+t To meet the conditions , also k To maintain the total number of barrels

def containsNearbyAlmostDuplicate(nums, k, t):
    def getIdx(u):
        return u//(t+1)
    buckets={}# Define a set 
    for i,v in enumerate(nums):
        # print(buckets)
        idx=getIdx(v)# Find the bucket of the element data 
        # If you save this element in the collection , If the conditions are met, it will directly return to 
        if idx in buckets:
            return True
        # Find the last one , The next bucket 
        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
        # Save the current element 
        buckets[idx]=v
        if len(buckets)>k:
            buckets.pop(getIdx(nums[i-k]))
    return False

The sliding window

Subarray with the smallest length

subject

 Given a containing  n  An array of positive integers and a positive integer  target .
 Find the sum of the array  ≥ target  The smallest length of   Continuous subarray  [numsl, numsl+1, ..., numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return  0 .
 Input :target = 7, nums = [2,3,1,2,4,3]
 Output :2
 explain : Subarray  [4,3]  Is the smallest subarray in this condition .
 Input :target = 4, nums = [1,4,4]
 Output :1

Ideas

Use variable windows , First, expand the window , Expand the sum in the window , When and >=target when , Record the value of the left and right boundaries of the window , Then narrow the window , Until less than target when , Record the left and right boundaries , And compare with before , Record the smallest one ; Then repeat the above steps , Until the end of the array .

def minSubArrayLen(target, nums):
    # Record the left and right boundaries respectively , And in the window and 
    left,right,total=0,0,0
    res=(left,float('inf'))
    n=len(nums)
    while right<n:
        total+=nums[right]
        if total>=target:# The sum is greater than or equal to target when 
            # Move left left boundary 
            while left<=right and total>=target:
                # Record the left and right boundaries 
                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

Longest substring without repeating characters

subject

 Given a string  s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .
 Example  1:
 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.
 Example  2:
 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.
 Example  3:
 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .
 Example  4:
 Input : s = ""
 Output : 0

Ideas

Still use double pointers to define the left and right boundaries of the window , Use hash To save the elements in the window , When the new element is hash What's in it , Move the left boundary and gradually delete hash The elements inside , Until there are no duplicate element positions , And calculate dic The length of

import collections
def lengthOfLongestSubstring(s):
    dic={}# Save the elements in the window 
    left=0# Window moving left and right 
    n=len(s)
    res=0# The final result 
    q=collections.deque()
    for right in range(n):
        c=s[right]
        # If it's in the window , Judge whether they are equal one by one from left to right , If equal, delete 
        while c in dic and left<right:
            dic.pop(s[left])
            left+=1
        dic[c]=right
        res=max(res,len(dic))
    return res

Maximum sliding window

subject

 Give you an array of integers  nums, There is a size of  k  The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see... In the sliding window  k  A digital . The sliding window moves only one bit to the right at a time .
 Returns the maximum value in the sliding window .
 Example  1:
 Input :nums = [1,3,-1,-3,5,3,6,7], k = 3
 Output :[3,3,5,5,6,7]
 explain :
 Position of sliding window                  Maximum 
---------------               -----
[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
 Example  2:
 Input :nums = [1], k = 1
 Output :[1]
 Example  3:
 Input :nums = [1,-1], k = 1
 Output :[1,-1]
 Example  4:
 Input :nums = [9,11], k = 2
 Output :[11]
 Example  5:
 Input :nums = [4,-2], k = 2
 Output :[4]

Ideas

Use a decrement queue to save the elements inside , The element difference between the head and tail of the queue is less than k Is to ensure the size of the window , Because it's decreasing , The leftmost element is the largest element , A new element , If it is smaller than the tail element, you can join the team normally , If it's bigger than the tail element , Delete... From the end of the team , Know to meet someone older than yourself , Or an empty queue , In the queue

import collections
def maxSlidingWindow(nums, k):
    q=collections.deque()
    res=[]# Save the final results 
    for i,v in enumerate(nums):
        # The newly added element is compared with the last element , If less than, add , If it's larger than never, delete it one by one 
        while q and nums[q[-1]]<v:
            q.pop()# Delete the last one 
        q.append(i)# Add new elements 
        # print("---")
        while i>=k and q[0]<=i-k:# Maintain window size 
            q.popleft()# Remove elements beyond the boundary 
        # print(q,"===")
        if i>=k-1:# When a fixed window is formed 
            res.append(nums[q[0]])
    return res

Minimum cover substring

subject

 Give you a string  s 、 A string  t . return  s  Covered by  t  The smallest string of all characters . If  s  There is no coverage in  t  Substring of all characters , Returns an empty string  "" .
 Be careful :
 about  t  Duplicate characters in , The number of characters in the substring we are looking for must not be less than  t  The number of characters in the .
 If  s  There is such a substring in , We guarantee that it is the only answer .
 Example  1:
 Input :s = "ADOBECODEBANC", t = "ABC"
 Output :"BANC"
 Example  2:
 Input :s = "a", t = "a"
 Output :"a"
 Example  3:
 Input : s = "a", t = "aa"
 Output : ""
 explain : t  Two characters in  'a'  Shall be included in  s  In the string of ,
 Therefore, there is no qualified substring , Returns an empty string .

Ideas

Still use double pointers to define the boundary of the window , Gradually expand the window , Make it include all t, And then gradually shrink the window , In order to quickly determine whether to include all t, Use one tmp Traversing records t Character length , use dic Record t The number of characters in the , When dic in , And the number of characters is greater than 0 when , be tmp-1, And from dic Reduce the number of characters in , When tmp=0 when , Is to find something that contains t All the characters in .

def minWindow(s, t):
    left,right=0,0# Window boundary 
    # Record string t The number of characters in the 
    need=collections.defaultdict(int)
    for c in t:
        need[c]+=1
    tmp=len(t)# Find all the tags 
    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:# If you find all the characters , Move left left
            #need[s[left]]<0 Is not a character t The characters in 
            while left<right and need[s[left]]<0:
                need[s[left]]+=1
                left+=1# Move left 
            # At this time left and right Is included t The smallest string of 
            if res[1]-res[0]>right-left:
                res=(left,right)
            # Find the character position in the dictionary 
            # 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://cdmana.com/2021/08/20210809190452508R.html

Scroll to Top