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

Catalog

# 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-res>right-left:
res=(left,right)
total-=nums[left]
left+=1
right+=1
return 0 if res>n else res-res+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 = , k = 1
Output ：
Example 3：
Input ：nums = [1,-1], k = 1
Output ：[1,-1]
Example 4：
Input ：nums = [9,11], k = 2
Output ：
Example 5：
Input ：nums = [4,-2], k = 2
Output ：
``````

### 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
# print("---")
while i>=k and q<=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])
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-res>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>len(s) else s[res:res+1]
``````