存在重复元素 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" false < code></=k:>
存在重复元素 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: 3: 输出:false code></=t>
有 abs(i-j)=k
可知,窗口大小为 k+1
时,窗口内的元素索引差都会小于 k
,然后在用新增的元素与窗口内的其他元素进行比较差值是否满足 abs(nums[i]-nums[j])<=t< code>即可<!--=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</=t,可知窗口的大小为k+1>
可是在提交测试时,显示超时,时间复杂度len(nums)*k,显然滑动窗口的解法不合适,那使用桶排序吧
桶排序的思路:因为差值为 t
,所以需要 t+1
个桶,则桶内每个元素的差值都 <=t< code>,如果当前桶内没有元素,则往前一个桶查找,如果有值,并且<code><=u-t< code>,或者往下一个桶找,并且<code>>=u+t</code>为满足条件,并且k去维护桶的总个数<!--=u-t<--></code><!--=t<-->
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
</=v+t:>
长度最小的子数组
给定一个含有 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
</=right></n:>
无重复字符的最长子串
给定一个字符串 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 < code></right:>
滑动窗口最大值
`
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
Original: https://www.cnblogs.com/hitechr/p/15120088.html
Author: Hitechr
Title: 【每日算法】算法复习一
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/590441/
转载文章受原作者版权保护。转载请注明原作者出处!