怎么快速搭建网站,怎样在亚马逊网上开店,logo设计公司在线生成,个人网站毕业设计例题#xff1a; 分析:
比如现在有字符串#xff08;s#xff09;#xff0c;s ADOBECODEBANC, 给出目标字符串 t ABC, 题目就是要从原始字符串#xff08;s#xff09;中找到一个子串#xff08;res#xff09;可以覆盖目标字符串 t 分析:
比如现在有字符串ss ADOBECODEBANC, 给出目标字符串 t ABC, 题目就是要从原始字符串s中找到一个子串res可以覆盖目标字符串 t 子串 BANC恰能覆盖 字符串t 且长度最短符合题目要求。
我们可以结合下图来分析 先定义两个变量ij一开始i 和 j 都指向原始字符串的0索引处看看此时 i ~ j 范围内的字符串是否满足目标字符串t如果不满足则 j 指针往后移动ji 指针先不动扩大 i ~ j 的范围直至i ~ j 范围内的字符串满足目标字符串t此时记录i 和 j 的位置。 然后 j 指针不动i在满足目标字符串的情况下不断缩小范围找到最小覆盖子串。 核心思想 1.统计目标串需要的各种字符个数统计原始串 i ~ j 范围内各种字符个数。 2.如果原始串 i ~ j 范围内不满足条件j 扩大范围直到满足条件 j 停下来。 3.一旦满足条件 i 缩小范围直到再次不满足条件。 4.重复 2、3 两步 直至 j 到达原始串末尾。 代码实现
public class MinWindowLeetcode76 {/** 1.统计目标串需要的各种字符个数统计原始串i~j范围内各种字符个数* 2.如果原始串i~j范围内不满足条件j扩大范围直到满足条件j停下来* 3.一旦满足条件i缩小范围直到再次不满足条件* 4.重复2、3两步直至j到达原始串末尾* *///定义一个结果类用来记录最小覆盖子串的左右边界static class Result{int i;int j;public Result(int i, int j) {this.i i;this.j j;}}public static String minWindow(String s, String t) {//统计目标字符串中各种字符个数char[] target t.toCharArray();int[] targetCount new int[128]; //因为题目说了给出的目标字符串是英文字母大小写都有128位足矣int passTotal 0; //需要满足的条件目标字符串中的一个字符代表一个条件for (char ch : target) {targetCount[ch];}for (int count : targetCount) {if(count 0){passTotal;}}//统计原始字符串i~j中各种字符个数char[] source s.toCharArray();int[] sourceCount new int[128];int i 0;int j 0;int passed 0; //已经通过的条件个数Result res null;while(j source.length){//扩大 j 范围更新范围内字符计数 和 通过条件数char right source[j];sourceCount[right];if(sourceCount[right] targetCount[right]){passed;}//表示已经找到一个覆盖子串缩小 i 范围j停止i同时改变通过条件数while(passed passTotal i j){if(res null){res new Result(i, j);}else{if(j - i res.j - res.i){res new Result(i, j);}}char left source[i];sourceCount[left]--;if(sourceCount[left] targetCount[left]){passed--;}i;}j;}return res null ? : new String(source, res.i, res.j - res.i 1);}public static void main(String[] args) {System.out.println(minWindow(ADOBECODEBANC, ABC)); // BANC//System.out.println(minWindow(aaabbbbbcdd, abcdd)); // abbbbbcdd}
}
