企业官网建设流程全解析

对接网站建设是什么意思,html5网站上线模版,做网站seo优化的公司,免费高清无专码区直接看(新卷,100分)- 关联子串#xff08;Java JS Python C#xff09;题目描述给定两个字符串str1和str2#xff0c;如果字符串str1中的字符#xff0c;经过排列组合后的字符串中#xff0c;只要有一个字符串是str2的子串#xff0c;则认为str1是str2的关联…(新卷,100分)- 关联子串Java JS Python C题目描述给定两个字符串str1和str2如果字符串str1中的字符经过排列组合后的字符串中只要有一个字符串是str2的子串则认为str1是str2的关联子串。若str1是str2的关联子串请返回子串在str2的起始位置若不是关联子串则返回-1。输入描述输入两个字符串分别为题目中描述的str1、str2。输出描述若str1是str2的关联子串请返回子串在str2的起始位置若不是关联子串则返回-1。若str2中有多个str1的组合子串请返回最小的起始位置。备注输入的字符串只包含小写字母两个字符串的长度范围[1, 100000]之间用例输入abc efghicbaiii输出5说明str2包含str1的一种排列组合cab)此组合在str2的字符串起始位置为5从0开始计数输入abc efghiccaiii输出-1说明“abc”字符串中三个字母的各种组合abc、acb、bac、bca、cab、cbastr2中均不包含因此返回-1题目解析本题看上去是要求解全排列但是题目描述数量级为两个字符串的长度范围[1, 100000]之间因此str1的全排列肯定会超时。本题可以使用尺取法来求解尺取法其实就是高级一点的滑动窗口常用于解决最小覆盖子串问题大家可以认真看下上面这个博客对尺取法有个大致了解。尺取法通常是有一个子串str1和一个父串str2我们需要在父串str2中找到包含str1子串所有字符的目标串target不在意字符顺序。解决方案很固定预处理动作统计出子串str1中各字符的数量记录到count中这里的count容器通常选择128长度的数组因为字符串中的字符通常都是ASCII码表的字符而ASCII码只有128个因此选择128长度的数组就可以涵盖到所有字符。定义一个total变量来记录str1字符的总数即str1的长度滑窗动作初始滑窗即父串str2的0~str1.length-1范围的滑窗。此时滑窗只有新增字符的过程即滑窗左边界保持在0而滑窗右边界从0运动到str1.length-1位置。后续滑窗即父串str2的 i ~ i str1.length - 1其中 i 1每次滑窗整体向右移动一格即相较于上一个滑窗会失去 str2[i-1]字符以及新增 str2[i str1.length - 1] 字符。滑窗的意义滑窗其实就是一个str2的子串我们可以基于滑窗来统计滑窗内子串各字符的数量如果滑窗内各字符的数量与str1各字符数量一致则说明滑窗内子串就是一个目标子串滑窗处理新增字符当滑窗新增一个字符c时我们应该count[c] - 1表示滑窗子串和str1的差别缩小了此时total是否也需要-1吗total是str1的字符总数此时需要细化讨论如果字符c不是str1内的字符则total不需要-1如果字符c是str1内的字符此时又需要细化讨论字符c虽然是str1内的字符但是滑窗内c字符的数量完全有可能超过str1内的字符数量即滑窗内存在多余的字符c那么此时滑窗新增了一个c并不会缩小和str1的差距即total不需要-1。那么此时就需要搞清楚如何判断滑窗内字符c是否是str1的字符以及是str1字符的情况下是否为超标字符上面两个判断可以用一句话实现count[c] 0如果滑窗新增的字符c不是str1字符则必然count[c] 0如果滑窗新增的字符c是str1字符但是超标了则经过count[c]--动作超过的c字符必然count[c] 0滑窗处理移除字符当滑窗移除一个字符c是我们应该count[c]表示滑窗子串和str1的差别扩大了此时total是否也需要1吗total是str1的字符总数此时需要细化讨论如果字符c不是str1内的字符则total不需要1如果字符c是str1内的字符此时又需要细化讨论字符c虽然是str1内的字符但是滑窗内c字符的数量完全有可能超过str1内的字符数量即滑窗内存在多余的字符c那么此时滑窗移除一个c并不会扩大和str1的差距即不需要total1那么此时就需要搞清楚如何判断滑窗内字符c是否是str1的字符以及是str1字符的情况下是否为超标字符上面两个判断可以用一句话实现count[c]0如果滑窗移除的字符c不是str1字符则移除之前必然count[c] 0如果滑窗移除的字符c是str1字符但是超标了则移除之前必然count[c] 0Java算法源码import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String str1 sc.next(); String str2 sc.next(); System.out.println(getResult(str1, str2)); } public static int getResult(String str1, String str2) { // count用于统计str1中各字符的数量 int[] count new int[128]; for (int i 0; i str1.length(); i) { char c str1.charAt(i); count[c]; } // total统计str1总共字符个数 int total str1.length(); // 初始滑窗滑窗范围内容就是一个子串 for (int i 0; i str1.length(); i) { // 滑窗子串新增的字符 char add str2.charAt(i); // 如果新增字符是str1的字符即count[add] 0时则说明滑窗子串已找到一个目标字符此时剩余add字符数量count[add]--,剩余目标字符总数total-- if (count[add]-- 0) { total--; } } // 如果total 0则说明滑窗内所有字符都是str1内的字符由于限定了滑窗的长度就是str1的长度因此滑窗内字符和str1完全匹配 if (total 0) return 0; // 下一个滑窗范围是 i ~ i str1.length() - 1 for (int i 1; i str1.length() - 1 str2.length(); i) { // 相较于上一个滑窗失去的字符remove char remove str2.charAt(i - 1); // 相较于上一个滑窗新增的字符add char add str2.charAt(i str1.length() - 1); // 本轮滑窗remove字符在上一轮是被add的字符我们假设此字符为c此时可以分两种情况讨论 // 1、c是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮count[c]是有可能0或者0的 // 1.1、如果本轮count[c]0则说明上轮滑窗并没有找到所有的c字符因此本轮移除的c字符可以还原total数量 // // 1.2、如果本轮count[c]0这说明上轮滑窗内的c字符超标了即c字符是目标字符但是滑窗内包含的c字符数量超过了str1中c字符的数量因此本轮移除c字符是超标部分不会还原total // 2、c不是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮必然count[c]0因此c字符的移除并不会还原total if (count[remove] 0) { total; } if (count[add]-- 0) { total--; } if (total 0) { return i; } } return -1; } }JS算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { let [str1, str2] line.split( ); console.log(getResult(str1, str2)); }); function getResult(str1, str2) { // count用于统计str1中各字符的数量 const count {}; for (let i 0; i str1.length; i) { const c str1[i]; count[c] (count[c] ?? 0) 1; } // total统计str1总共字符个数 let total str1.length; // 初始滑窗滑窗范围内容就是一个子串 for (let i 0; i str1.length; i) { // 滑窗子串新增的字符 const add str2[i]; // 如果新增字符是str1的字符即count[add] 0时则说明滑窗子串已找到一个目标字符此时剩余add字符数量count[add]--,剩余目标字符总数total-- if (count[add]-- 0) { total--; } } // 如果total 0则说明滑窗内所有字符都是str1内的字符由于限定了滑窗的长度就是str1的长度因此滑窗内字符和str1完全匹配 if (total 0) return 0; // 下一个滑窗范围是 i ~ i str1.length() - 1 for (let i 1; i str1.length - 1 str2.length; i) { // 相较于上一个滑窗失去的字符remove const remove str2[i - 1]; // 相较于上一个滑窗新增的字符add const add str2[i str1.length - 1]; // 本轮滑窗remove字符在上一轮是被add的字符我们假设此字符为c此时可以分两种情况讨论 // 1、c是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮count[c]是有可能0或者0的 // 1.1、如果本轮count[c]0则说明上轮滑窗并没有找到所有的c字符因此本轮移除的c字符可以还原total数量 // 1.2、如果本轮count[c]0这说明上轮滑窗内的c字符超标了即c字符是目标字符但是滑窗内包含的c字符数量超过了str1中c字符的数量因此本轮移除c字符是超标部分不会还原total // 2、c不是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮必然count[c]0因此c字符的移除并不会还原total if (count[remove] 0) { total; } if (count[add]-- 0) { total--; } if (total 0) return i; } return -1; }Python算法源码# 输入获取 str1, str2 input().split() # 算法入口 def getResult(): # count用于统计str1中各字符的数量 count {} for c in str1: count[c] count.get(c, 0) 1 # total统计str1总共字符个数 total len(str1) # 初始滑窗滑窗范围内容就是一个子串 for i in range(len(str1)): # 滑窗子串新增的字符 add str2[i] # 如果新增字符是str1的字符即count[add] 0时则说明滑窗子串已找到一个目标字符此时剩余add字符数量count[add]--,剩余目标字符总数total-- if count.get(add) is not None: if count[add] 0: total - 1 count[add] - 1 # 如果total 0则说明滑窗内所有字符都是str1内的字符由于限定了滑窗的长度就是str1的长度因此滑窗内字符和str1完全匹配 if total 0: return 0 # 下一个滑窗范围是 i ~ i str1.length() - 1 for i in range(1, len(str2) - len(str1) 1): # 相较于上一个滑窗失去的字符remove remove str2[i-1] # 相较于上一个滑窗新增的字符add add str2[i len(str1) - 1] # 本轮滑窗remove字符在上一轮是被add的字符我们假设此字符为c # 1、c是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮count[c]是有可能0或者0的 # 1.1、如果本轮count[c]0则说明上轮滑窗并没有找到所有的c字符因此本轮移除的c字符可以还原total数量 # 1.2、如果本轮count[c]0这说明上轮滑窗内的c字符超标了即c字符是目标字符但是滑窗内包含的c字符数量超过了str1中c字符的数量因此本轮移除c字符是超标部分不会还原total if count.get(remove) is not None: if count[remove] 0: total 1 count[remove] 1 if count.get(add) is not None: if count[add] 0: total - 1 count[add] - 1 if total 0: return i return -1 # 算法调用 print(getResult())C算法源码#include stdio.h #include string.h #define MAX_LEN 100000 int getResult(char *str1, char *str2); int main() { char str1[MAX_LEN], str2[MAX_LEN]; scanf(%s %s, str1, str2); printf(%d\n, getResult(str1, str2)); return 0; } int getResult(char *str1, char *str2) { // count用于统计str1中各字符的数量 int count[128] {0}; for (int i 0; i strlen(str1); i) { char c str1[i]; count[c]; } // total统计str1总共字符个数 int total strlen(str1); // 初始滑窗滑窗范围内容就是一个子串 for (int i 0; i strlen(str1); i) { // 滑窗子串新增的字符 char add str2[i]; // 如果新增字符是str1的字符即count[add] 0时则说明滑窗子串已找到一个目标字符此时剩余add字符数量count[add]--,剩余目标字符总数total-- if (count[add]-- 0) { total--; } } // 如果total 0则说明滑窗内所有字符都是str1内的字符由于限定了滑窗的长度就是str1的长度因此滑窗内字符和str1完全匹配 if (total 0) return 0; // 下一个滑窗范围是 i ~ i str1.length() - 1 for (int i 1; i strlen(str1) - 1 strlen(str2); i) { // 相较于上一个滑窗失去的字符remove char remove str2[i - 1]; // 相较于上一个滑窗新增的字符add char add str2[i strlen(str1) - 1]; // 本轮滑窗remove字符在上一轮是被add的字符我们假设此字符为c此时可以分两种情况讨论 // 1、c是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮count[c]是有可能0或者0的 // 1.1、如果本轮count[c]0则说明上轮滑窗并没有找到所有的c字符因此本轮移除的c字符可以还原total数量 // // 1.2、如果本轮count[c]0这说明上轮滑窗内的c字符超标了即c字符是目标字符但是滑窗内包含的c字符数量超过了str1中c字符的数量因此本轮移除c字符是超标部分不会还原total // 2、c不是str1的字符则初始统计时count[c]0上一轮滑窗加入c字符则count[c]--此轮必然count[c]0因此c字符的移除并不会还原total if (count[remove] 0) { total; } if (count[add]-- 0) { total--; } if (total 0) { return i; } } return -1; }