[daily algorithm] algorithm review I
Hitechr 2021-08-09 19:06:00

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]
Please bring the original link to reprint ,thank
Similar articles

2021-08-09

2021-08-09