class049 滑动窗口技巧与相关题目【算法】

package class049;
// 累加和大于等于target的最短子数组长度
// 给定一个含有 n 个正整数的数组和一个正整数 target
// 找到累加和 >= target 的长度最小的子数组并返回其长度
// 如果不存在符合条件的子数组返回0
// 测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/
public class Code01_MinimumSizeSubarraySum {
  public static int minSubArrayLen(int target, int[] nums) {
    int ans = Integer.MAX_VALUE;
    for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
      sum += nums[r];
      while (sum - nums[l] >= target) {
        // sum : nums[l....r]
        // 如果l位置的数从窗口出去，还能继续达标，那就出去
        sum -= nums[l++];
      }
      if (sum >= target) {
        ans = Math.min(ans, r - l + 1);
      }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
  }
}

package class049;
import java.util.Arrays;
// 无重复字符的最长子串
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
// 测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/
public class Code02_LongestSubstringWithoutRepeatingCharacters {
  public static int lengthOfLongestSubstring(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    // char -> int -> 0 ~ 255
    // 每一种字符上次出现的位置
    int[] last = new int[256];
    // 所有字符都没有上次出现的位置
    Arrays.fill(last, -1);
    // 不含有重复字符的 最长子串 的长度
    int ans = 0;
    for (int l = 0, r = 0; r < n; r++) {
      l = Math.max(l, last[s[r]] + 1);
      ans = Math.max(ans, r - l + 1);
      // 更新当前字符上一次出现的位置
      last[s[r]] = r;
    }
    return ans;
  }
}

package class049;
// 最小覆盖子串
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
// 测试链接 : https://leetcode.cn/problems/minimum-window-substring/
public class Code03_MinimumWindowSubstring {
  public static String minWindow(String str, String tar) {
    if (str.length() < tar.length()) {
      return "";
    }
    char[] s = str.toCharArray();
    char[] t = tar.toCharArray();
    int[] cnts = new int[256];
    for (char cha : t) {
      cnts[cha]--;
    }
    // 最小覆盖子串的长度
    int len = Integer.MAX_VALUE;
    // 从哪个位置开头，发现的这个最小覆盖子串
    int start = 0;
    for (int l = 0, r = 0, debt = t.length; r < s.length; r++) {
      // s[r] 当前字符 -> int
      // cnts[s[r]] : 当前字符欠债情况，负数就是欠债，正数就是多给的
      if (cnts[s[r]]++ < 0) {
        debt--;
      }
      if (debt == 0) {
        // r位置结尾，真的有覆盖子串！
        // 看看这个覆盖子串能不能尽量短
        while (cnts[s[l]] > 0) {
          // l位置的字符能拿回
          cnts[s[l++]]--;
        }
        // 从while里面出来，
        // l....r就是r位置结尾的最小覆盖子串
        if (r - l + 1 < len) {
          len = r - l + 1;
          start = l;
        }
      }
    }
    return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);
  }
}

package class049;
// 加油站
// 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
// 你从其中的一个加油站出发，开始时油箱为空。
// 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周
// 则返回出发时加油站的编号，否则返回 -1
// 如果存在解，则 保证 它是 唯一 的。
// 测试链接 : https://leetcode.cn/problems/gas-station/
public class Code04_GasStation {
  public static int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    // 车辆尝试从0~n-1出发，看能不能走一圈，l
    // r : 窗口即将进来数字的位置
    // len : 窗口大小
    // sum : 窗口累加和
    for (int l = 0, r = 0, len = 0, sum = 0; l < n; l++) {
      while (sum >= 0) {
        // 当前窗口累加和>=0，尝试扩
        if (len == n) {
          return l;
        }
        // r : 窗口即将进来数字的位置
        r = (l + (len++)) % n;
        sum += gas[r] - cost[r];
      }
      // sum < 0，此时l位置无法转一圈
      len--;
      sum -= gas[l] - cost[l];
    }
    return -1;
  }
}

package class049;
// 替换子串得到平衡字符串
// 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
// 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
// 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
// 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
// 请返回待替换子串的最小可能长度。
// 如果原字符串自身就是一个平衡字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
public class Code05_ReplaceTheSubstringForBalancedString {
  // Q W E R
  // 0 1 2 3
  // "W Q Q R R E"
  // 1 0 0 3 3 2
  // cnts[1] = 1;
  // cnts[0] = 2;
  // cnts[2] = 1;
  // cnts[3] = 2;
  public static int balancedString(String str) {
    int n = str.length();
    int[] arr = new int[n];
    int[] cnts = new int[4];
    for (int i = 0; i < n; i++) {
      char c = str.charAt(i);
      arr[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
      cnts[arr[i]]++;
    }
    // str : 长度是4的整数倍，n
    // 每种字符出现的个数 : n/4
    int require = n / 4;
    // 至少要修改多长的子串，才能做到四种字符一样多
    int ans = n;
    // 自由变化的窗口l....r
    for (int l = 0, r = 0; l < n; l++) {
      // l = 0, r= 0, 窗口0长度
      // l...r-1 : [l,r)
      while (!ok(cnts, r - l, require) && r < n) {
        // cnts : 窗口之外的统计
        cnts[arr[r++]]--;
      }
      // 1) l...r-1 [l,r) ，做到了！
      // 2) r == n，也没做到
      if (ok(cnts, r - l, require)) {
        ans = Math.min(ans, r - l);
      }
      // [l,r)，不被cnts统计到的
      //   l+1
      cnts[arr[l]]++;
    }
    return ans;
  }
  // cnts : l...r范围上的字符不算！在自由变化的窗口之外，每一种字符的词频统计
  // len : 自由变化窗口的长度
  // require : 每一种字符都要达到的数量
  // 返回值 : 请问能不能做到
  public static boolean ok(int[] cnts, int len, int require) {
    for (int i = 0; i < 4; i++) {
      // 0 1 2 3
      if (cnts[i] > require) {
        return false;
      }
      // require - cnts[i] : 20 - 16 = 4
      len -= require - cnts[i];
    }
    return len == 0;
  }
}

package class049;
import java.util.Arrays;
// K个不同整数的子数组
// 给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
// 如果 nums 的某个子数组中不同整数的个数恰好为 k
// 则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
// 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
// 子数组 是数组的 连续 部分。
// 测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/
public class Code06_SubarraysWithKDifferentIntegers {
  public static int subarraysWithKDistinct(int[] arr, int k) {
    return numsOfMostKinds(arr, k) - numsOfMostKinds(arr, k - 1);
  }
  public static int MAXN = 20001;
  public static int[] cnts = new int[MAXN];
  // arr中有多少子数组，数字种类不超过k
  // arr的长度是n，arr里的数值1~n之间
  public static int numsOfMostKinds(int[] arr, int k) {
    Arrays.fill(cnts, 1, arr.length + 1, 0);
    int ans = 0;
    for (int l = 0, r = 0, collect = 0; r < arr.length; r++) {
      // r(刚进)
      if (++cnts[arr[r]] == 1) {
        collect++;
      }
      // l.....r    要求不超过3种，已经4种，l往右（吐数字）
      while (collect > k) {
        if (--cnts[arr[l++]] == 0) {
          collect--;
        }
      }
      // l.....r不超过了
      // 0...3
      // 0~3
      // 1~3
      // 2~3
      // 3~3
      ans += r - l + 1;
    }
    return ans;
  }
}

package class049;
import java.util.Arrays;
// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
public class Code07_LongestSubstringWithAtLeastKRepeating {
  public static int longestSubstring(String str, int k) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[] cnts = new int[256];
    int ans = 0;
    // 每次要求子串必须含有require种字符，每种字符都必须>=k次，这样的最长子串是多长
    for (int require = 1; require <= 26; require++) {
      Arrays.fill(cnts, 0);
      // collect : 窗口中一共收集到的种类数
      // satisfy : 窗口中达标的种类数(次数>=k)
      for (int l = 0, r = 0, collect = 0, satisfy = 0; r < n; r++) {
        cnts[s[r]]++;
        if (cnts[s[r]] == 1) {
          collect++;
        }
        if (cnts[s[r]] == k) {
          satisfy++;
        }
        // l....r 种类超了！
        // l位置的字符，窗口中吐出来！
        while (collect > require) {
          if (cnts[s[l]] == 1) {
            collect--;
          }
          if (cnts[s[l]] == k) {
            satisfy--;
          }
          cnts[s[l++]]--;
        }
        // l.....r : 子串以r位置的字符结尾，且种类数不超的，最大长度！
        if (satisfy == require) {
          ans = Math.max(ans, r - l + 1);
        }
      }
    }
    return ans;
  }
}