尺取法,顾名思义像尺子那样一段一段取,该算法是滑动窗口的一种,其大思路为首先以某种策略移动右边界,再移动左边界。其效果很像毛毛虫蠕动过程,头先往前跑跑到一定位置,亦巴再往前跑。因此该算法又被称为毛毛虫算法。如下图小姐姐那样
先来几道经典的例子,
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例:
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
这题前几天字节跳动面试就让我写这个….
对于该问题,首先right右移直到当前窗口中元素和不小于s,然后left也右移使得窗口中元素之和小于s(右移过程中获得以right结尾的最短长度)。该方法正确的原因是该子数组是全正的,对于存在负值的问题可以参考我之前写的这篇文章:链接
代码如下:
java
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int right = 0;
int sum = 0;
int ans = nums.length + 1;
for(; right < nums.length; right++){
sum += nums[right];
while(sum >= s){
ans = Math.min(ans, right - left + 1);
sum -= nums[left++];
}
}
return ans == nums.length + 1 ? 0 : ans;
}
}
同leetcode1004
牛牛从牛毕那里拿了一根长度为n的白木板,木板被等分成了n段(没有被切割,只是虚拟划分成了n段),其中有些段被牛毕用颜料染成了黑色。
牛牛非常不喜欢黑色,它找来了一桶清洗剂决定对木板进行清洗,但是牛牛发现自己的清洗剂最多只能清洗m段。清洗完后,牛牛会把木板锯成纯色的几段。例如假设木板是 (黑黑黑白白白白黑黑黑 ),就会被锯成(黑黑黑)(白白白白)(黑黑黑)三段。牛牛想知道,它足够聪明地清洗木板,能获得的纯白色木板的最大长度是多少。
输入:
给定n,m两个整数
和一个长度为n的数组a,为1表示白色,为0表示黑色
1 <= n <= 1e6, 1 <= m <= n
输出:
一行一个数字表示能获得的纯白色木板的最大长度是多少。
链接:https://ac.nowcoder.com/acm/contest/6779/B
来源:牛客网
示例1
输入
6,1, [1,0,0,1,1,1]
输出
4
说明
染成了[1,0,1,1,1,1]
示例2
输入
6,2, [1,0,0,1,1,1]
输出
6
说明
染成了[1,1,1,1,1,1]
该问题有m段颜料,想获得最长的连成一片的白色,首先需要知道该部分颜料一定染的是相邻位置的黑色区域,这有这样才会得到最长的一块白色。例如如下案例
a = [1,0,1,0,1,0,1]
m = 2
若有两块颜料,最优解一定在染的是第一个0和第二个0或者是第二个0和第三个0这两种情况之中,一定不会出现染第一0和第三个0的情况。
定义左边界为left,右边界为right,count统计当前窗口中黑色块的数目。
移动right,直到count刚好 大于 m,然后移动left使得count等于m即可,然后重复上述过程即可。
代码如下:
java
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @param a int整型一维数组
* @return int整型
*/
public int solve (int n, int m, int[] a) {
int left = 0;
int ans = 0;
int count = 0; // 统计区间内0的数目
for(int i = 0; i < n; i++){
if(a[i] == 0){
count++;
}
while(count > m){
if(a[left] == 0){
count--;
}
left++;
}
ans = Math.max(ans, i - left + 1);
}
return ans;
}
}
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
对于该问题之前都是利用动态规划以O(N^2)的时间复杂度求解的,现在发现该问题也可以使用尺取法。
为了不喧宾夺主,只写出动态规划的转移方程和baseline,定义dpi 为以i结尾的最长无重复子串的长度,转移方程如下:
dpi={dpi−1+1,stri∉[str[i−dpi−1]….stri−1] i−indexOf(stri),else
baseline:
dp0=1
尺取法求解如下:
定义left为窗口左边界,right为右边界,使用一Map存储当前窗内每个元素出现的次数。
首先right右移,统计窗内各元素数目直到有一个元素出现重复,然后右移left使得没有重复元素。重复上述操作即可。
java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> count = new HashMap<>();
int ans = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
count.put(s.charAt(right), count.getOrDefault(s.charAt(right), 0) + 1);
while(count.get(s.charAt(right)) > 1){
count.put(s.charAt(left), count.get(s.charAt(left)) - 1);
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}