)
多多的灰度发布
拼多多技术岗 7月19号笔试 第一题
题目内容
多多在维护一批编号1 , 2 , … , n 1,\ 2,\ \dots,\ n1,2,…,n排列的实例。每个实例只有两种状态：0 00表示使用旧版本，1 11表示使用新版本。
多多在灰度发布平台执行了一次操作：
- 选择一个非空连续区间[ L , R ] [L,\ R][L,R]
- 选择一个目标状态v vv，其中v vv为0 00或1 11
- 把区间内所有实例的状态都设为v vv
区间中可以包含原本就已经处于状态v vv的实例，但这次操作必须至少改变一个实例的状态。发布前后的实例状态串A AA和B BB被完整保留，但操作日志丢失了，保证至少存在一种操作，可以把A AA变为B BB。
请判断这次操作能否被唯一确定。若合法的三元组( L , R , V ) (L,\ R,\ V)(L,R,V)恰好只有一个，输出它，否则输出− 1 -1−1。 注意：只要L 、 R L、RL、R或V VV中有任意一项不同，就视为不同的操作，即使它们得到的发布后状态完全相同。
输入描述
第一行包含一个正整数T TT，表示测试用例的数量。
对于每个测试用例：
第一行包含一个整数n nn，表示实例数量。
第二行包含一个长度为n nn的01 0101串A AA，表示发布前的状态。
第三行包含一个长度为n nn的01 0101串B BB，表示发布后的状态。
输出描述
对于每个测试用例：
如果操作唯一，输出一行三个整数L R V L\ R\ VLRV。
如果不存在唯一操作，输出一行− 1 -1−1。
补充说明：
- 1 ≤ T ≤ 10 1 \le T \le 101≤T≤10
- A AA和B BB均为长度恰好为n nn的01 0101串；
- 单个输入文件中，所有测试用例的n nn之和不超过2 ∗ 10 5 2 * 10^52∗105；
- 保证每组数据至少存在一种合法操作。
样例1
输入
6 5 00000 01110 5 01000 01110 6 111111 100001 7 0001000 0111110 1 0 1 5 00010 01110输出
2 4 1 -1 2 5 0 2 6 1 1 1 1 -1题解和思路
思路
实现思路：逻辑分析
- 对于每组输入，通过遍历发布前/后字符串找到对应
start 第一个不同位置和end 最后一个不同的位置 - 根据第一步得出start和end可以完成一下判断
- start = -1,说明发布前/后字符串完全相同，不存在唯一解。
- 将发布前变更为发布后，唯一可能的v就是`B[start], 判断[start, end]是否全为v,不全为v说明根本无法通过一次操作将发布前变更为发布后。
- 由于区间中可以包含原本就已经处于状态v vv的实例，通过上面判断之后，可以得知[start, end, v]肯定是一个合法操作。要保证是否唯一，主要看是否能够进行区间左右扩展。
B[start - 1] == v说明能往左侧扩展，答案不唯一B[end-+1] == v说明能往右侧扩展，答案不唯一
- 算法平均时间复杂度为
O（n）
C++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;string A,B;cin>>A;cin>>B;// 不同的开始和结束位置intstart=-1;intend=-1;for(inti=0;i<n;i++){if(A[i]!=B[i]){if(start==-1){start=i;}end=i;}}// 没有变化，不存在合法操作if(start==-1){cout<<-1<<endl;continue;}// 确定vintv=B[start]-'0';boolok=true;// 判断B [start,end]是否都为v v肯定为B[start]for(inti=start;i<=end;i++){if(B[i]!=B[start]){ok=false;break;}}// 左右扩展，判断是否唯一if(ok&&start>0&&B[start-1]==B[start]){ok=false;}if(ok&&end<n-1&&B[end+1]==B[start]){ok=false;}// 不唯一if(!ok){cout<<-1<<endl;}else{cout<<start+1<<" "<<end+1<<" "<<B[start]-'0'<<endl;}}return0;}Java
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intT=sc.nextInt();while(T-->0){intn=sc.nextInt();StringA=sc.next();StringB=sc.next();// 不同的开始和结束位置intstart=-1;intend=-1;for(inti=0;i<n;i++){if(A.charAt(i)!=B.charAt(i)){if(start==-1){start=i;}end=i;}}// 没有变化，不存在合法操作if(start==-1){System.out.println(-1);continue;}// 确定vintv=B.charAt(start)-'0';booleanok=true;// 判断B[start,end]是否都为v，v肯定为B[start]for(inti=start;i<=end;i++){if(B.charAt(i)!=B.charAt(start)){ok=false;break;}}// 左右扩展，判断是否唯一if(ok&&start>0&&B.charAt(start-1)==B.charAt(start)){ok=false;}if(ok&&end<n-1&&B.charAt(end+1)==B.charAt(start)){ok=false;}// 不唯一if(!ok){System.out.println(-1);}else{System.out.println((start+1)+" "+(end+1)+" "+v);}}}}python
T=int(input())for_inrange(T):n=int(input())A=input().strip()B=input().strip()# 不同的开始和结束位置start=-1end=-1foriinrange(n):ifA[i]!=B[i]:ifstart==-1:start=i end=i# 没有变化，不存在合法操作ifstart==-1:print(-1)continue# 确定vv=int(B[start])ok=True# 判断B[start,end]是否都为v，v肯定为B[start]foriinrange(start,end+1):ifB[i]!=B[start]:ok=Falsebreak# 左右扩展，判断是否唯一ifokandstart>0andB[start-1]==B[start]:ok=Falseifokandend<n-1andB[end+1]==B[start]:ok=False# 不唯一ifnotok:print(-1)else:print(start+1,end+1,v)Javascript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{letidx=0;constT=Number(input[idx++]);constans=[];for(lett=0;t<T;t++){constn=Number(input[idx++]);constA=input[idx++];constB=input[idx++];// 不同的开始和结束位置letstart=-1;letend=-1;for(leti=0;i<n;i++){if(A[i]!==B[i]){if(start===-1){start=i;}end=i;}}// 没有变化，不存在合法操作if(start===-1){ans.push("-1");continue;}// 确定vconstv=Number(B[start]);letok=true;// 判断B[start,end]是否都为v，v肯定为B[start]for(leti=start;i<=end;i++){if(B[i]!==B[start]){ok=false;break;}}// 左右扩展，判断是否唯一if(ok&&start>0&&B[start-1]===B[start]){ok=false;}if(ok&&end<n-1&&B[end+1]===B[start]){ok=false;}// 不唯一if(!ok){ans.push("-1");}else{ans.push(`${start+1}${end+1}${v}`);}}console.log(ans.join("\n"));});Go
packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)for;T>0;T--{varnintfmt.Fscan(in,&n)varA,Bstringfmt.Fscan(in,&A)fmt.Fscan(in,&B)// 不同的开始和结束位置start:=-1end:=-1fori:=0;i<n;i++{ifA[i]!=B[i]{ifstart==-1{start=i}end=i}}// 没有变化，不存在合法操作ifstart==-1{fmt.Println(-1)continue}// 确定vv:=int(B[start]-'0')ok:=true// 判断B[start,end]是否都为v，v肯定为B[start]fori:=start;i<=end;i++{ifB[i]!=B[start]{ok=falsebreak}}// 左右扩展，判断是否唯一ifok&&start>0&&B[start-1]==B[start]{ok=false}ifok&&end<n-1&&B[end+1]==B[start]{ok=false}// 不唯一if!ok{fmt.Println(-1)}else{fmt.Println(start+1,end+1,v)}}}
