华为OD机试真题 新系统【小学英语老师批改作文】
小学英语老师批改作文(C/C++/Py/Java/Js/Go)
华为OD机试新系统真题 华为OD上机考试新系统真题 5月20号 100分题型
华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解
题目描述
你是一名小学英语老师，正在批改学生的英语作文。由于学生在书写单词时常常会出现一些小问题，比如多余的空格，作文批改过程中需要纠正问题，包括前后多余空格去除，中间重复的空格应该删除多余空格，单词间最多只保留一个空格。
为了简化查找过程，重复字符比较忽略字符大小写，am等于Am、AM和aM。
输入描述
输入一个仅包含 ASCII 字符的文本字符串 story
输出描述
请你找出批改后的作文中，最长的不包含重复字符的子串长度。
约束
0 ≤ s t o r y . l e n g t h ≤ 1000 0 \le story.length \le 10000≤story.length≤1000
story 仅包含 ASCII 字符（0-127）。
样例1
输入
Hello World!输出
7说明
最长子串为World!，长度为 7。
样例2
输入
hi, jIn输出
5说明
先对空格和大小写做处理，输入串等价为Hi, Jin，最长子串是", Jin"，长度为5 55。
题解
思路：滑动窗口
- 预处理，将输入字符串中
首尾空格去除，大写字母统一转换为小写，两个单词分割间多余一个的空格去除，从而得到真正要处理的字符串。这一步处理过程中主要注意空字符串和全为空格和正确处理连续空格边界情况就行。 - 得到真正要处理的字符串
str, 如果str为空直接返回0就行。对于非空字符串求最长连续不重复子串长度采用滑动窗口进行处理。具体处理逻辑如下：- 初始定义
left = 0, 表示合法子串的左边界，定义index[128]用于保存离右边界最近指定字符的坐标。定义res = 0, 存储最长连续不重复子串长度 - 接下来right从前进行枚举，当前字符为
c = str[right]的处理逻辑为:- 如果
index[c] >= left, 如果窗口中出现重复字符串，左边界需要移动到left = index[c] + 1才能保证子串不重复。 index[c] < left不做处理，[left, right]字符不重复。- 尝试更新结果
res = max(res, right - left + 1) - 并更新
index[c] = right
- 如果
- 按照2的逻辑进行处理，即可得到正确结果。
- 初始定义
算法时间复杂度为O(n)
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 大写转换为小写并去除首尾空格和中间多余空格 string handleStr(string& story) { string tmp; int n = story.size(); // 确定不包含首尾空格的起始和结束点 int begin = 0; int end = n - 1; while (begin < n - 1&& story[begin] == ' ') { begin++; } while (end >= 0 && story[end] == ' ') { end--; } // 全空格情况 if (begin > end) { return ""; } for (int i = begin; i <= end; i++) { char c = story[i]; // 大写转小写 if ('A' <= c && c<='Z') { c = c + 32; } //去除连续空格 if (c == ' ' && tmp.back() == ' ') { continue; } tmp.push_back(c); } return tmp; } int getLengthSubStr(string& story) { string str = handleStr(story); vector<int> index(128, -1); int left = 0; int res = 0; // 滑动窗口求最大不重复子串长度 for (int right = 0; right < str.size(); right++) { char c = str[right]; if (index[c] != -1) { if (left <= index[c]) { left = index[c] + 1; } } index[c] = right; res = max(res, right - left + 1); } return res; } int main() { string story; getline(cin, story); int res = getLengthSubStr(story); cout << res; return 0; }JAVA
import java.util.*; public class Main { // 大写转换为小写并去除首尾空格和中间多余空格 public static String handleStr(String story) { StringBuilder tmp = new StringBuilder(); int n = story.length(); // 确定不包含首尾空格的起始和结束点 int begin = 0; int end = n - 1; while (begin < n - 1 && story.charAt(begin) == ' ') { begin++; } while (end >= 0 && story.charAt(end) == ' ') { end--; } // 全空格情况 if (begin > end) { return ""; } for (int i = begin; i <= end; i++) { char c = story.charAt(i); // 大写转小写 if ('A' <= c && c <= 'Z') { c = (char)(c + 32); } // 去除连续空格 if (c == ' ' && tmp.length() > 0 && tmp.charAt(tmp.length() - 1) == ' ') { continue; } tmp.append(c); } return tmp.toString(); } public static int getLengthSubStr(String story) { String str = handleStr(story); int[] index = new int[128]; Arrays.fill(index, -1); int left = 0; int res = 0; // 滑动窗口求最大不重复子串长度 for (int right = 0; right < str.length(); right++) { char c = str.charAt(right); if (index[c] != -1) { if (left <= index[c]) { left = index[c] + 1; } } index[c] = right; res = Math.max(res, right - left + 1); } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String story = sc.nextLine(); int res = getLengthSubStr(story); System.out.print(res); } }Python
# 大写转换为小写并去除首尾空格和中间多余空格defhandleStr(story):tmp=[]n=len(story)# 确定不包含首尾空格的起始和结束点begin=0end=n-1whilebegin<n-1andstory[begin]==' ':begin+=1whileend>=0andstory[end]==' ':end-=1# 全空格情况ifbegin>end:return""foriinrange(begin,end+1):c=story[i]# 大写转小写if'A'<=c<='Z':c=chr(ord(c)+32)# 去除连续空格ifc==' 'andlen(tmp)>0andtmp[-1]==' ':continuetmp.append(c)return''.join(tmp)defgetLengthSubStr(story):s=handleStr(story)index=[-1]*128left=0res=0# 滑动窗口求最大不重复子串长度forrightinrange(len(s)):c=s[right]ifindex[ord(c)]!=-1:ifleft<=index[ord(c)]:left=index[ord(c)]+1index[ord(c)]=right res=max(res,right-left+1)returnres story=input()res=getLengthSubStr(story)print(res)JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});// 大写转换为小写并去除首尾空格和中间多余空格functionhandleStr(story){lettmp="";constn=story.length;// 确定不包含首尾空格的起始和结束点letbegin=0;letend=n-1;while(begin<n-1&&story[begin]===' '){begin++;}while(end>=0&&story[end]===' '){end--;}// 全空格情况if(begin>end){return"";}for(leti=begin;i<=end;i++){letc=story[i];// 大写转小写if('A'<=c&&c<='Z'){c=c.toLowerCase();}// 去除连续空格if(c===' '&&tmp.length>0&&tmp[tmp.length-1]===' '){continue;}tmp+=c;}returntmp;}functiongetLengthSubStr(story){conststr=handleStr(story);constindex=newArray(128).fill(-1);letleft=0;letres=0;// 滑动窗口求最大不重复子串长度for(letright=0;right<str.length;right++){constc=str[right];if(index[c.charCodeAt(0)]!==-1){if(left<=index[c.charCodeAt(0)]){left=index[c.charCodeAt(0)]+1;}}index[c.charCodeAt(0)]=right;res=Math.max(res,right-left+1);}returnres;}rl.on("line",function(line){constres=getLengthSubStr(line);console.log(res);rl.close();});Go
packagemainimport("bufio""fmt""os")// 大写转换为小写并去除首尾空格和中间多余空格funchandleStr(storystring)string{tmp:=make([]byte,0)n:=len(story)// 确定不包含首尾空格的起始和结束点begin:=0end:=n-1forbegin<n-1&&story[begin]==' '{begin++}forend>=0&&story[end]==' '{end--}// 全空格情况ifbegin>end{return""}fori:=begin;i<=end;i++{c:=story[i]// 大写转小写if'A'<=c&&c<='Z'{c=c+32}// 去除连续空格ifc==' '&&len(tmp)>0&&tmp[len(tmp)-1]==' '{continue}tmp=append(tmp,c)}returnstring(tmp)}funcgetLengthSubStr(storystring)int{str:=handleStr(story)index:=make([]int,128)fori:=0;i<128;i++{index[i]=-1}left:=0res:=0// 滑动窗口求最大不重复子串长度forright:=0;right<len(str);right++{c:=str[right]ifindex[c]!=-1{ifleft<=index[c]{left=index[c]+1}}index[c]=rightifright-left+1>res{res=right-left+1}}returnres}funcmain(){reader:=bufio.NewReader(os.Stdin)story,_:=reader.ReadString('\n')// 去掉换行iflen(story)>0&&story[len(story)-1]=='\n'{story=story[:len(story)-1]}res:=getLengthSubStr(story)fmt.Print(res)}C语言
#include<stdio.h>#include<string.h>chartmp[1005];// 大写转换为小写并去除首尾空格和中间多余空格voidhandleStr(char*story){intn=strlen(story);// 确定不包含首尾空格的起始和结束点intbegin=0;intend=n-1;while(begin<n-1&&story[begin]==' '){begin++;}while(end>=0&&story[end]==' '){end--;}// 全空格情况if(begin>end){tmp[0]='\0';return;}intidx=0;for(inti=begin;i<=end;i++){charc=story[i];// 大写转小写if('A'<=c&&c<='Z'){c=c+32;}// 去除连续空格if(c==' '&&idx>0&&tmp[idx-1]==' '){continue;}tmp[idx++]=c;}tmp[idx]='\0';}intgetLengthSubStr(char*story){handleStr(story);intindex[128];for(inti=0;i<128;i++){index[i]=-1;}intleft=0;intres=0;// 滑动窗口求最大不重复子串长度for(intright=0;tmp[right]!='\0';right++){charc=tmp[right];if(index[(int)c]!=-1){if(left<=index[(int)c]){left=index[(int)c]+1;}}index[(int)c]=right;if(right-left+1>res){res=right-left+1;}}returnres;}intmain(){charstory[1005];fgets(story,sizeof(story),stdin);intlen=strlen(story);// 去掉换行符if(len>0&&story[len-1]=='\n'){story[len-1]='\0';}intres=getLengthSubStr(story);printf("%d",res);return0;}