拼多多笔试真题 9.22 - 工位等量连搬(C++/Py/Java /Js/Go)

工位等量连搬拼多多 9月22号 笔试真题 第一题拼多多真题目录点击查看: 拼多多笔试真题题库目录笔试题库 算法考点详解题目内容装配车间里今晚要处理的工位排成一行一共m mm个。第t tt个工位待下线的零件个数是x t x_txt​。夹具每次勾取时只能框住下标连续的一段[ L , R ] [L,R][L,R]并且这段里各个工位的零件个数必须彼此相等对不齐就不能勾。被勾中的工位只是零件清零工位仍留在原处因此左右两段不会贴合。每个工位上的零件必须整批勾走不能拆成两次。请给出清空整行所需的最少勾取次数。输入描述首行给出询问条数q qq1 ≤ q ≤ 10 1 1\le q\le 10^{1}1≤q≤101。接下来q qq行每行开头是工位数m mm1 ≤ m ≤ 100000 1\le m\le 1000001≤m≤100000后面紧跟m mm个整数x 1 , x 2 , … , x m x_1,x_2,\dots,x_mx1​,x2​,…,xm​1 ≤ x t ≤ 100000 1\le x_t\le 1000001≤xt​≤100000。输出描述把q qq个答案写在同一行两两之间用一个空格分开。从左到右第k kk个数就是第k kk组询问的最少勾取次数。样例1输入2 7 4 4 4 1 1 9 9 4 8 8 8 8输出3 1说明第一组分成[ 4 , 4 , 4 ] [4,4,4][4,4,4]、[ 1 , 1 ] [1,1][1,1]、[ 9 , 9 ] [9,9][9,9]要勾3 33次。第二组四个工位零件个数都是8 88勾1 11次即可。样例2输入1 6 5 5 7 7 5 5输出3说明三段是[ 5 , 5 ] [5,5][5,5]、[ 7 , 7 ] [7,7][7,7]、[ 5 , 5 ] [5,5][5,5]。左右两段零件个数同为5 55但中间隔着7 77工位不会贴合不能并成一次。题解和思路思路实现思路模拟本质是求数组中连续相同元素的连续段数量。要求上述连段数量只需要求出1 相邻位置不同的次数即可算法时间复杂度为OmqC#includebits/stdc.husingnamespacestd;intmain(){intq;cinq;vectorintans(q);for(intk0;kq;k){intm;cinm;intcount0;intprev-1;for(inti0;im;i){intx;cinx;// 新连续片段起点if(i0||x!prev){count;}prevx;}ans[k]count;}for(inti0;iq;i){if(i0)cout ;coutans[i];}return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intqsc.nextInt();int[]ansnewint[q];for(intk0;kq;k){intmsc.nextInt();intcount0;intprev-1;for(inti0;im;i){intxsc.nextInt();// 新连续片段起点if(i0||x!prev){count;}prevx;}ans[k]count;}for(inti0;iq;i){if(i0){System.out.print( );}System.out.print(ans[i]);}}}pythonimportsys datalist(map(int,sys.stdin.read().split()))index0qdata[index]index1ans[]forkinrange(q):mdata[index]index1count0prev-1foriinrange(m):xdata[index]index1# 新连续片段起点ifi0orx!prev:count1prevx ans.append(count)print( .join(map(str,ans)))Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varqintfmt.Fscan(in,q)ans:make([]int,q)fork:0;kq;k{varmintfmt.Fscan(in,m)count:0prev:-1fori:0;im;i{varxintfmt.Fscan(in,x)// 新连续片段起点ifi0||x!prev{count}prevx}ans[k]count}fori:0;iq;i{ifi0{fmt.Fprint(out, )}fmt.Fprint(out,ans[i])}}Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(...line.trim().split(/\s/).filter(Boolean));});rl.on(close,(){letindex0;constqNumber(input[index]);constans[];for(letk0;kq;k){constmNumber(input[index]);letcount0;letprev-1;for(leti0;im;i){constxNumber(input[index]);// 新连续片段起点if(i0||x!prev){count;}prevx;}ans.push(count);}console.log(ans.join( ));});