企业官网建设流程全解析

珠海精品网站建设,小红书营销,和拓者设计吧类似的网站,丽水网站建设公司(新卷,200分)- 最长子字符串的长度(二)#xff08;Java JS Python C#xff09;题目描述给你一个字符串 s#xff0c;字符串 s 首尾相连成一个环形#xff0c;请你在环中找出 l、o、x 字符都恰好出现了偶数次最长子字符串的长度。输入描述输入是一串小写…(新卷,200分)- 最长子字符串的长度(二)Java JS Python C题目描述给你一个字符串 s字符串 s 首尾相连成一个环形请你在环中找出 l、o、x 字符都恰好出现了偶数次最长子字符串的长度。输入描述输入是一串小写的字母组成的字符串输出描述输出是一个整数备注1 ≤ s.length ≤ 5 * 10^5s 只包含小写英文字母用例输入alolobo输出6说明最长子字符串之一是 alolob它包含 lo 各2个以及 0 个 x。输入looxdolx输出7说明最长的子字符串是oxdolxl由于是首尾连接在一起的所以最后一个 x 和开头的 l 是连接在一起的此字符串包含 2 个 l2个o2个x输入bcbcbc输出6说明这个示例中字符串 bcbcbc 本身就是最长的因为 l、o、x 都出现了 0 次。题目解析本题其实就是看本题前需要先把上面题目搞懂否则本题解法看不懂。本题与上面题目的区别在于本题的主串s是环即当遍历到s串尾部时可以继续环动到s串头部。如下图所示上图中黑色部分是不可使用的绿色黄色的部分总是对应一个完整的字符串s。本题如果继续按照前面leetcode那题的思路解题则会发现使用哈希表时不能只单单记录某个状态的最早出现位置。而是需要记录某个状态的出现的所有位置需要按照先后顺序依次记录。因为本题随着绕环运动黑色部分会逐渐侵蚀掉一些位置而这些被侵蚀的位置可能就是某个状态最早出现的位置当该位置被侵蚀后我们需要更新对应状态到新的最早出现位置。如果使用队列记录某个状态出现的所有位置按照先后顺序依次记录那么队列头部记录的就是该状态的最早出现位置如果该位置被侵蚀那么我们就弹出队头使用新的队头元素作为对应状态的最早出现位置。JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const s await readline(); console.log(getResult(s)); })(); function getResult(s) { let status 0b000; // map[i] 用于记录 状态i 出现的过的所有位置 const map new Array(8).fill(0).map(() []); map[0].push(-1); let maxLen 0; for (let i 0; i s.length * 2; i) { // 第二轮时is.length此时i需要对s.length求余避免后面越界 const c s[i % s.length]; switch (c) { case l: status ^ 0b100; break; case o: status ^ 0b010; break; case x: status ^ 0b001; break; } if (i s.length) { // 第一轮时i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 map[status].push(i); } while (map[status].length 0) { // status状态最早出现的位置 const earliest map[status][0]; // i 是当前位置和 earliest 位置的状态相同 if (i - earliest s.length) { // 如果 [earliest, i] 范围子串长度超过s串长度则说明earliest左越界应该尝试更大一点的earliest map[status].shift(); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度则该范围子串就是一个符合要求的子串记录此时子串长度 maxLen Math.max(maxLen, i - earliest); break; } } } return maxLen; }Java算法源码import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine(); System.out.println(getResult(s)); } public static int getResult(String s) { int status 0b000; // map.get(i) 用于记录 状态i 出现的过的所有位置 ArrayListLinkedListInteger map new ArrayList(); for (int i 0; i 8; i) { map.add(new LinkedList()); } map.get(0).add(-1); int maxLen 0; for (int i 0; i s.length() * 2; i) { // 第二轮时is.length()此时i需要对s.length()求余避免后面越界 char c s.charAt(i % s.length()); switch (c) { case l: status ^ 0b100; break; case o: status ^ 0b010; break; case x: status ^ 0b001; break; } if (i s.length()) { // 第一轮时i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 map.get(status).add(i); } while (map.get(status).size() 0) { // status状态最早出现的位置 int earliest map.get(status).getFirst(); // i 是当前位置和 earliest 位置的状态相同 if (i - earliest s.length()) { // 如果 [earliest, i] 范围子串长度超过s串长度则说明earliest左越界应该尝试更大一点的earliest map.get(status).removeFirst(); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度则该范围子串就是一个符合要求的子串记录此时子串长度 maxLen Math.max(maxLen, i - earliest); break; } } } return maxLen; } }Python算法源码# 输入获取 s input() # 算法入口 def getResult(): status 0b000 # dic[i] 用于记录 状态i 出现的过的所有位置 dic [[] for _ in range(8)] dic[0].append(-1) maxLen 0 for i in range(2 * len(s)): # 第二轮时is.length此时i需要对s.length求余避免后面越界 c s[i % len(s)] if c l: status ^ 0b100 elif c o: status ^ 0b010 elif c x: status ^ 0b001 if i len(s): # 第一轮时i ∈ [0, s.length()), 左闭右开 # 记录该状态出现过的所有位置 dic[status].append(i) while len(dic[status]) 0: # status状态最早出现的位置 earliest dic[status][0] # i 是当前位置和 earliest 位置的状态相同 if i - earliest len(s): # 如果 [earliest, i] 范围子串长度超过s串长度则说明earliest左越界应该尝试更大一点的earliest dic[status].pop(0) else: # 如果 [earliest, i] 范围子串长度未超过s串长度则该范围子串就是一个符合要求的子串记录此时子串长度 maxLen max(maxLen, i - earliest) break return maxLen # 算法调用 print(getResult())C算法源码#include stdio.h #include stdlib.h #include string.h #include math.h #define MAX_SIZE 500000 char s[MAX_SIZE]; typedef struct ListNode { int ele; struct ListNode *next; } ListNode; typedef struct LinkedList { int size; ListNode *head; ListNode *tail; } LinkedList; LinkedList *new_LinkedList() { LinkedList *link (LinkedList *) malloc(sizeof(LinkedList)); link-size 0; link-head NULL; link-tail NULL; return link; } void addLast_LinkedList(LinkedList *link, int ele) { ListNode *node (ListNode *) malloc(sizeof(ListNode)); node-ele ele; node-next NULL; if (link-size 0) { link-head node; link-tail node; } else { link-tail-next node; link-tail node; } link-size; } int removeFirst_LinkedList(LinkedList *link) { if (link-size 0) exit(-1); ListNode *removed link-head; if (link-size 1) { link-head NULL; link-tail NULL; } else { link-head link-head-next; } link-size--; int res removed-ele; free(removed); return res; } int getResult() { int status 0b000; // map[i] 用于记录 状态i 出现的过的所有位置 LinkedList *map[8]; for (int i 0; i 8; i) { map[i] new_LinkedList(); } addLast_LinkedList(map[0], -1); int maxLen 0; int n (int) strlen(s); for (int i 0; i n * 2; i) { // 第二轮时is.length()此时i需要对s.length()求余避免后面越界 char c s[i % n]; if (c l) { status ^ 0b100; } else if (c o) { status ^ 0b010; } else if (c x) { status ^ 0b001; } if (i n) { // 第一轮时i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 addLast_LinkedList(map[status], i); } while (map[status]-size 0) { // status状态最早出现的位置 int earliest map[status]-head-ele; // i 是当前位置和 earliest 位置的状态相同 if (i - earliest n) { // 如果 [earliest, i] 范围子串长度超过s串长度则说明earliest左越界应该尝试更大一点的earliest removeFirst_LinkedList(map[status]); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度则该范围子串就是一个符合要求的子串记录此时子串长度 maxLen (int) fmax(maxLen, i - earliest); break; } } } return maxLen; } int main() { gets(s); printf(%d\n, getResult()); return 0; }