淘客网站怎么做 知乎,大连html5网站建设,专业网站建设网站,长春做网站大公司目录 1.前言
2.题目解析
3.算法原理
4.代码实现 1.前言
首先我打算介绍一下#xff0c;我对滑动窗口的理解。 滑动窗口可以分为四个步骤#xff1a; 进窗口#xff1a; 在这一步骤中#xff0c;我们决定了要在窗口中维护的信息。例如#xff0c;在这个问题中#xff…目录 1.前言
2.题目解析
3.算法原理
4.代码实现 1.前言
首先我打算介绍一下我对滑动窗口的理解。 滑动窗口可以分为四个步骤 进窗口 在这一步骤中我们决定了要在窗口中维护的信息。例如在这个问题中我们需要维护字符种类的个数。只要字符种类个数不超过2个窗口就是合法的我们就可以继续向右移动窗口。 判断 在进入窗口后我们需要检查窗口是否变得非法。如果窗口不再合法我们就需要执行出窗口的操作。 出窗口 出窗口的过程是从一个非法窗口恢复到合法窗口的过程。我们通过移动左边界指针来实现这一点。 更新结果 在每个合法窗口中我们可能需要更新问题的最优解。这可能会发生在进窗口、判断或出窗口的任何阶段。 滑动窗口算法的核心思想是使用两个同向指针通常是左右指针来定义一个窗口并根据问题的要求移动窗口的位置以达到解决问题的目的。这种算法通常能够有效地减少重复计算并在线性时间内解决许多问题。 2.题目解析 包含不超过两种字符的最长子串_牛客题霸_牛客网 窗口中的元素不大于2为合法窗口求最长的合法窗口。 3.算法原理 使用滑动窗口 采用滑动窗口算法来解决问题。通过维护一个窗口窗口内的字符种类个数不超过两个来找到满足条件的最长子串。 初始化窗口和变量 定义两个指针 left 和 right分别指向窗口的左右边界。初始化一个大小为 26 的整型数组 hash用于记录窗口内每种字符出现的次数。另外定义一个变量 flag 用于记录窗口内不同字符的个数初始值为 0定义一个变量 max 用于记录最长子串的长度初始值为 -1。 移动右指针 右指针向右移动进入窗口。每次移动右指针更新窗口内字符的出现次数并根据情况更新 flag 的值。 判断窗口合法性 判断窗口是否合法即窗口内不同字符的个数是否超过两个。如果超过两个需要移动左指针缩小窗口直到窗口重新合法。 更新最长子串长度 在每次窗口合法的情况下更新 max 的值记录当前最长子串的长度。 返回结果 循环结束后返回 max即最终的结果即最长子串的长度。 4.代码实现
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNext()) { // 注意 while 处理多个 caseString str in.next();//1.通过hash表 flag变量来判断窗口是否合法int[] hash new int[26];int flag 0, max -1;int left 0,right 0;char[] chs str.toCharArray();int n chs.length;while(right n){//2.进窗口if (hash[chs[right] - a] 0){flag;}hash[chs[right] - a];right;while(flag 2){//违法窗口//3.出窗口hash[chs[left] - a]--;if (hash[chs[left] - a] 0){flag--;}left;}//4.更新结果max Math.max(max,right - left);}System.out.println(max);}}
}
