网站源码模板,上海远程教育网站设计与开发公司,佛山市南海区建设局网站,软件外包题目
原题链接#xff1a;76. 最小覆盖子串 1- 思路
利用两个哈希表解决分为 #xff1a;① 初始化哈希表、②遍历 s#xff0c;处理当前元素#xff0c;判断当前字符是否有效、③收缩窗口、④更新最小覆盖子串 2- 实现
⭐76. 最小覆盖子串——题解思路 class Solution …题目
原题链接76. 最小覆盖子串 1- 思路
利用两个哈希表解决分为 ① 初始化哈希表、②遍历 s处理当前元素判断当前字符是否有效、③收缩窗口、④更新最小覆盖子串 2- 实现
⭐76. 最小覆盖子串——题解思路 class Solution {public String minWindow(String s, String t) {// 定义两个 HashMapHashMapCharacter,Integer hs new HashMap();HashMapCharacter,Integer ht new HashMap();// 定义 int cnt 0;String res ;// 初始化 htfor(int i 0 ; i t.length();i){char c t.charAt(i);ht.put(c,ht.containsKey(c) ? ht.get(c)1:1);}// 遍历 sfor(int i 0, j 0 ; i s.length();i){char c s.charAt(i);hs.put(c, hs.containsKey(c) ? hs.get(c)1 : 1);// 判断 i 合法if(ht.containsKey(c) hs.get(c) ht.get(c)) cnt;// 缩小区间while (j i (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) ht.get(s.charAt(j)))) {hs.put(s.charAt(j), hs.get(s.charAt(j )) - 1);}// 3 收集结果// 首先是必须等于 cnt (hs.length() (i-j1) || res.length()1)if(cntt.length() ( res.length() (i-j1) || res.length()1)){res s.substring(j,i1);}}return res;}
}3- ACM 实现
public class minWindow {public static String minWindow(String s,String t){// 1.数据结构HashMapCharacter,Integer ht new HashMap();HashMapCharacter,Integer window new HashMap();int cnt 0;String res ;// 2.遍历 t 初始化 htfor(int i 0 ; i t.length();i){char c t.charAt(i);ht.put(c,ht.containsKey(c)? ht.get(c)1:1);}// 3.遍历 sfor(int i 0,j0 ; i s.length();i){char cc s.charAt(i);window.put(cc,window.containsKey(cc)? window.get(cc)1:1);// 判 cc 断有效性// 在 ht 中if(ht.containsKey(cc) window.get(cc) ht.get(cc)) cnt;// 窗口收缩while(ji (!ht.containsKey(s.charAt(j)) || window.get(s.charAt(j)) ht.get(s.charAt(j)))){window.put(s.charAt(j),window.get(s.charAt(j))-1);}// 更行 resif(cnt t.length() (res.length()(i-j1) || res.length()1)){res s.substring(j,i1);}}return res;}public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println(输入字符串1);String s sc.nextLine();System.out.println(输入字符串2);String t sc.nextLine();String res minWindow(s,t);System.out.println(结果是 res);}
}
