h5网站网站建设中国搜索引擎网站排名

h5网站网站建设,中国搜索引擎网站排名,小米果怎么做视频网站,昆明网站建设推荐q479185700上墙(200分)- 寻找符合要求的最长子串#xff08;Java JS Python#xff09;题目描述给定一个字符串s#xff0c;找出这样一个子串#xff1a;该子串中任意一个字符最多出现2次该子串不包含指定某个字符请你找出满足该条件的最长子串的长度输入描述第一行为#x…(200分)- 寻找符合要求的最长子串Java JS Python题目描述给定一个字符串s找出这样一个子串该子串中任意一个字符最多出现2次该子串不包含指定某个字符请你找出满足该条件的最长子串的长度输入描述第一行为要求不包含的指定字符为单个字符取值范围[0-9a-zA-Z]第二行为字符串s每个字符范围[0-9a-zA-Z]长度范围[1, 10000]输出描述一个整数满足条件的最长子串的长度如果不存在满足条件的子串则返回0用例输入DABC132输出6说明无输入DABACA123D输出7说明无题目解析简单的滑窗应用。我们以用例2画图解释由于本题描述中说字符串s每个字符范围[0-9a-zA-Z]以及屏蔽字符取值范围[0-9a-zA-Z]因此我们统计滑窗内部字符数量时可以使用长度为128的数组来作为容器因为要统计的字符的ASCII码必然在0~128范围中。JavaScript算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; rl.on(line, (line) { lines.push(line); if (lines.length 2) { console.log(getResult(lines[1], lines[0])); lines.length 0; } }); /** * param {*} s 字符串s * param {*} ex 要求不包含的指定字符 * returns 满足条件的最长子串的长度 */ function getResult(s, ex) { ex ex.charCodeAt(); const count new Array(128).fill(0); let l 0; // 滑窗左边界 let r 0; // 滑窗右边界 let ans 0; // 记录满足条件的最长子串的长度 // 滑窗右边界不越界的话可以继续右移 while (r s.length) { // r指针指向的字符是滑窗新增的字符 const add_c s[r].charCodeAt(); if (ex add_c) { // 如果新增字符是屏蔽字符那么滑窗不能包含此字符为了让滑窗不能包含此字符只能让滑窗的左边界l移动到此字符的右边一个位置 ans Math.max(ans, r - l); // 但是在具体移动之前需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 l r; // 滑窗左边界l要移动到屏蔽字符的右边即r1位置而滑窗的右边界r又不能落后于左边界l因此相当于同时移动 count.fill(0); // 此时滑窗为空因此清空统计的字符的数量 } else { // 如果新增字符不是屏蔽字符那么就纳入滑窗 count[add_c]; // 如果此时新增字符的数量超过了2那么我们应该让滑窗的左边界l右移直到该新增字符的数量等于2时停止 if (count[add_c] 2) { ans Math.max(ans, r - l); // 但是在具体移动之前我们需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 } while (count[add_c] 2) { const remove_c s[l].charCodeAt(); count[remove_c]--; l; } r; } } return Math.max(ans, r - l); // 对最后一次滑窗位置进行记录 }Java算法源码import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String exclude sc.next(); String s sc.next(); System.out.println(getResult(s, exclude.charAt(0))); } public static int getResult(String s, char ex) { // 记录滑窗内部每个字符出现的次数 int[] count new int[128]; // 滑窗左边界,右边界 int l 0, r 0; // 记录满足条件的最长子串的长度 int ans 0; // 滑窗右边界不越界的话可以继续右移 while (r s.length()) { // r指针指向的字符是滑窗新增的字符 char add_c s.charAt(r); if (ex add_c) { // 如果新增字符是屏蔽字符那么滑窗不能包含此字符为了让滑窗不能包含此字符只能让滑窗的左边界l移动到此字符的右边一个位置 ans Math.max(ans, r - l); // 但是在具体移动之前需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 l r; // 滑窗左边界l要移动到屏蔽字符的右边即r1位置而滑窗的右边界r又不能落后于左边界l因此相当于同时移动 Arrays.fill(count, 0); // 此时滑窗为空因此清空统计的字符的数量 } else { // 如果新增字符不是屏蔽字符那么就纳入滑窗 count[add_c]; // 如果此时新增字符的数量超过了2那么我们应该让滑窗的左边界l右移直到该新增字符的数量等于2时停止 if (count[add_c] 2) { ans Math.max(ans, r - l); // 但是在具体移动之前我们需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 } while (count[add_c] 2) { char remove_c s.charAt(l); count[remove_c]--; l; } r; } } return Math.max(ans, r - l); // 对最后一次滑窗位置进行记录 } }Python算法源码# 输入获取 ex ord(input()) # 要求不包含的指定字符 s input() # 字符串s # 算法入口 def getResult(): # 记录滑窗内部每个字符出现的次数 count [0]*128 l 0 # 滑窗左边界 r 0 # 滑窗右边界 ans 0 # 记录满足条件的最长子串的长度 # 滑窗右边界不越界的话可以继续右移 while r len(s): # r指针指向的字符是滑窗新增的字符 add_c ord(s[r]) if ex add_c: # 如果新增字符是屏蔽字符那么滑窗不能包含此字符为了让滑窗不能包含此字符只能让滑窗的左边界l移动到此字符的右边一个位置 ans max(ans, r - l) # 但是在具体移动之前需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 r 1 # 滑窗左边界l要移动到屏蔽字符的右边即r1位置而滑窗的右边界r又不能落后于左边界l因此相当于同时移动 l r count [0]*128 # 时滑窗为空因此清空统计的字符的数量 else: # 如果新增字符c是目标子串可以包含的字符 count[add_c] 1 # 那么就纳入滑窗 if count[add_c] 2: # 如果此时新增字符的数量超过了2那么我们应该让滑窗的左边界l右移直到该新增字符的数量等于2时停止 ans max(ans, r - l) # 但是在具体移动之前我们需要将上一个状态的滑窗长度和统计的最大长度进行比较保留最大的 while count[add_c] 2: remove_c ord(s[l]) count[remove_c] - 1 l 1 r 1 # 对最后一次滑窗位置进行记录 return max(ans, r - l) # 算法调用 print(getResult())