OPPO笔试真题 - 最长锚定片段(C++/Py/Java /Js/Go)

最长锚定片段OPPO技术岗 8月8号笔试 第一题题目内容在文字定位算法中小写字母ooo、大写字母OOO和数字000由于形态相近常被用作视觉锚点anchor。如果一个非空字符串的第一个字符和最后一个字符都属于锚点字符则称该字符串为“锚定片段”。现在给定一个长度为nnn的字符串sss你可以从sss中截取一个连续子串请求出其中最长的锚定片段的长度。如果找不到任何锚定片段则输出000。数据范围字符串长度nnn满足1≤n≤1200001 \le n \le 1200001≤n≤120000。字符串仅由大小写英文字母和数字组成。输入描述第一行包含一个整数nnn(1≤n≤1200001 \le n \le 1200001≤n≤120000)表示字符串sss的长度。 第二行包含一个长度为nnn的字符串sss仅由大小写英文字母和数字组成。输出描述输出一个整数表示最长锚定片段的长度。样例1输入5 oabcO输出5说明字符串为oabcO其中包含两个锚点字符开头的o和结尾的O。最左锚点位置为000最右锚点位置为444最长锚定片段的长度为4−0154 - 0 1 54−015即整个字符串本身。样例2输入3 a0b输出1说明字符串a0b中仅有一个锚点字符0位于位置111。最左和最右锚点均为该位置片段0本身满足首尾均为锚点的条件长度为1−1111 - 1 1 11−111。样例3输入4 abcd输出0说明字符串abcd中没有任何锚点字符o、O、0无法构成锚定片段因此输出000。样例4输入6 0oooOO输出6说明字符串0oooOO中的每一个字符都是锚点。最左锚点为开头的0位置000最右锚点为结尾的O位置555最长锚定片段覆盖整个字符串长度为5−0165 - 0 1 65−016。题解和思路思路实现思路模拟很容易就能分析出来最长锚定片段为第一个锚定字符到最后一个锚定字符的长度。定义first记录第一个锚定字符位置last记录最后一个锚定字符位置初始设置first last -1然后从前往后遍历输入字符串更新first和last对应位置。根据last和first值输出结果first -1时说明不存在锚定字符输出0first ! -1,输出对应长度last - first 1算法平均时间复杂度为OnC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;string s;cinn;cins;// 描点第一位和最后一位位置intfirst,last;firstlast-1;for(inti0;in;i){if(s[i]0||s[i]O||s[i]o){if(first-1){firsti;}lasti;}}// 不存在锚点字符if(first-1){cout0;}else{coutlast-first1;}return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();Stringssc.next();// 描点第一位和最后一位位置intfirst-1,last-1;for(inti0;in;i){if(s.charAt(i)0||s.charAt(i)O||s.charAt(i)o){if(first-1){firsti;}lasti;}}// 不存在锚点字符if(first-1){System.out.print(0);}else{System.out.print(last-first1);}}}pythonnint(input())sinput()# 描点第一位和最后一位位置firstlast-1foriinrange(n):ifs[i]0ors[i]Oors[i]o:iffirst-1:firsti lasti# 不存在锚点字符iffirst-1:print(0)else:print(last-first1)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line.trim());});rl.on(close,(){constnNumber(input[0]);constsinput[1];// 描点第一位和最后一位位置letfirst-1;letlast-1;for(leti0;in;i){if(s[i]0||s[i]O||s[i]o){if(first-1){firsti;}lasti;}}// 不存在锚点字符if(first-1){console.log(0);}else{console.log(last-first1);}});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varnintvarsstringfmt.Fscan(in,n)fmt.Fscan(in,s)// 描点第一位和最后一位位置first,last:-1,-1fori:0;in;i{ifs[i]0||s[i]O||s[i]o{iffirst-1{firsti}lasti}}// 不存在锚点字符iffirst-1{fmt.Println(0)}else{fmt.Println(last-first1)}}