找出s中刚好包含t中所有字符串的子字符串,t中的字符串长度都相等,为wordLen,t中有wordNum个字符串。[1]首先构建t中字符串的计数器,然后以0到wordLen-1开头,从头到尾走wordLen的跳数,在跳动的滑动窗口内部讨论可能性,以及维持滑动窗口的边界。如果这一跳遇到的字符串没有在t中出现,更新滑动窗口的左边界到该一跳末尾,滑动窗口的块大小计数恢复为0,滑动窗口内部的计数器清空,因为从原先的left到现在这一跳的滑动窗口无法满足题目条件,有杂质;否则,更新目前滑动窗口内部块的数量和计数器,当滑动窗口内部的计数器和t的计数器匹配且块数量==wordNum,则找到了一个目标子字符串
找出nums乘积小于k的子数组个数。[2]
方法一:滑动窗口。统计以某一元素为结尾的乘积小于k的子数组个数,计算以某一元素为结尾的成绩小于k的最长子数组长度,计算子区间的乘积,维护滑动窗口中的元素积小于k。
方法二:前缀和,使用log函数变相乘运算为相加运算,注意log函数的结果是double,使用upper_bound在logPrefix数组中找logPrefix[i]-log(k)+1e-10的上界的索引,这样找到和小于log(k)的子区间,即乘积小于k的子数组。
nums中三个无重叠长度为k的最大和的子数组起始索引。[3]
方法一:滑动窗口。以第三个子数组的起始坐标i=2*k遍历找最大和,第一个子数组的起始坐标为i-k*2,第二个子数组的起始坐标为i-k,累计滑动窗口和;当i>=3*k-1时,即第一个靠左的三个长度为k的无重叠子数组形成,根据滑动窗口的和更新最大和和区域的起始坐标,三个滑动窗口一起向右走一步,再更新状态。
方法二:动态规划。dp[i][j]表示到索引j位置处前i个互不重叠长度为k的子数组的最大和,面对元素[j]时,可以选择它参与计算最大和,dp[i-1][j-k]+prefix[j]-prefix[j-k],也可以不选择它参与计算最大和,dp[i][j-1],取两者中的最大值,dp[2][n-1]即为最大和,记录计算最大和的转移路径(map[第i个子数组和]=子数组的起始索引,dp[2][i]的最大值是从dp[1][.]转移过来的,不断往前查找),给出答案。注意,计算dp[0][i]时i的取值范围为k-1<=i<n-2*k
包含m个1的01字符串,让k个1在一块的最小交换次数,一次交换指相邻元素的一次互换。
参考链接:[1].30. 串联所有单词的子串
[2].713. 乘积小于 K 的子数组
[3].689. 三个无重叠子数组的最大和
[4].1703. 得到连续 K 个 1 的最少相邻交换次数