企业官网建设流程全解析

最长锚定片段

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−0+1=54 - 0 + 1 = 54−0+1=5，即整个字符串本身。

样例2

输入

3 a0b

输出

1

说明
字符串a0b中仅有一个锚点字符0，位于位置111。最左和最右锚点均为该位置，片段0本身满足首尾均为锚点的条件，长度为1−1+1=11 - 1 + 1 = 11−1+1=1。

样例3

输入

4 abcd

输出

0

说明
字符串abcd中没有任何锚点字符（o、O、0），无法构成锚定片段，因此输出000。

样例4

输入

6 0oooOO

输出

6

说明
字符串0oooOO中的每一个字符都是锚点。最左锚点为开头的0（位置000），最右锚点为结尾的O（位置555），最长锚定片段覆盖整个字符串，长度为5−0+1=65 - 0 + 1 = 65−0+1=6。

题解和思路

思路

实现思路：模拟

1. 很容易就能分析出来最长锚定片段为第一个锚定字符到最后一个锚定字符的长度。
2. 定义first记录第一个锚定字符位置，last记录最后一个锚定字符位置，初始设置first = last = -1然后从前往后遍历输入字符串，更新first和last对应位置。
3. 根据last和first值输出结果
   • first == -1时，说明不存在锚定字符，输出0
   • first != -1,输出对应长度last - first + 1
4. 算法平均时间复杂度为O（n）

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;string s;cin>>n;cin>>s;// 描点第一位和最后一位位置intfirst,last;first=last=-1;for(inti=0;i<n;i++){if(s[i]=='0'||s[i]=='O'||s[i]=='o'){if(first==-1){first=i;}last=i;}}// 不存在锚点字符if(first==-1){cout<<0;}else{cout<<last-first+1;}return0;}

Java

importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();Strings=sc.next();// 描点第一位和最后一位位置intfirst=-1,last=-1;for(inti=0;i<n;i++){if(s.charAt(i)=='0'||s.charAt(i)=='O'||s.charAt(i)=='o'){if(first==-1){first=i;}last=i;}}// 不存在锚点字符if(first==-1){System.out.print(0);}else{System.out.print(last-first+1);}}}

python

n=int(input())s=input()# 描点第一位和最后一位位置first=last=-1foriinrange(n):ifs[i]=='0'ors[i]=='O'ors[i]=='o':iffirst==-1:first=i last=i# 不存在锚点字符iffirst==-1:print(0)else:print(last-first+1)

Javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on('line',line=>{input.push(line.trim());});rl.on('close',()=>{constn=Number(input[0]);consts=input[1];// 描点第一位和最后一位位置letfirst=-1;letlast=-1;for(leti=0;i<n;i++){if(s[i]==='0'||s[i]==='O'||s[i]==='o'){if(first===-1){first=i;}last=i;}}// 不存在锚点字符if(first===-1){console.log(0);}else{console.log(last-first+1);}});

Go

packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varnintvarsstringfmt.Fscan(in,&n)fmt.Fscan(in,&s)// 描点第一位和最后一位位置first,last:=-1,-1fori:=0;i<n;i++{ifs[i]=='0'||s[i]=='O'||s[i]=='o'{iffirst==-1{first=i}last=i}}// 不存在锚点字符iffirst==-1{fmt.Println(0)}else{fmt.Println(last-first+1)}}