拼多多笔试真题-对角线遍历矩阵(C++/Py/Java /Js/Go)

对角线遍历矩阵拼多多技术岗 7月3号笔试 第一题题目内容给你一个大小为mmm×nnn的矩阵matmatmat请以对角线遍历的顺序用一个数组返回这个矩阵中的所有元素对角线遍历的顺序如图所示。输入描述第一行包含两个整数mmm和nnn表示矩阵的行数和列数1≤m,n≤1001 \le m,n \le 1001≤m,n≤100。接下来的mmm行每行包含nnn个整数表示矩阵的元素整数范围在[−10000,10000][-10000, 10000][−10000,10000]之间。输出描述输出一行包含按对角线遍历顺序排列的矩阵元素元素之间用空格隔开。样例1输入3 3 1 2 3 4 5 6 7 8 9输出7 4 8 9 5 1 2 6 3题解和思路思路实现思路模拟按照题目给出的示例进行模拟即可主要考虑边界情况。当走反对角时,走到j0时移动规律当i0时需要将j--当i ! 0需要将i--当走对角走到jm-1时移动规律当i n -1, 需要将j当j m -1 需要将i--总体时间复杂度为On * mC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;vectorvectorintgrid(n,vectorint(m));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}vectorintans(n*m);intindex0;// 0 反对角 1对角intflag0;intin-1,j0;while(indexn*m){ans[index]grid[i][j];if(flag0){if(i0){j;flag1;}elseif(j0){i--;flag1;}else{i--;j--;}}else{if(in-1){j;flag0;}elseif(jm-1){i--;flag0;}else{i;j;}}}//输出结果for(inti0;in*m;i){if(i0){cout ;}coutans[i];}return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringBuildersbnewStringBuilder();Stringline;while((linebr.readLine())!null){sb.append(line).append( );}String[]inputsb.toString().trim().split(\\s);intidx0;intnInteger.parseInt(input[idx]);intmInteger.parseInt(input[idx]);int[][]gridnewint[n][m];for(inti0;in;i){for(intj0;jm;j){grid[i][j]Integer.parseInt(input[idx]);}}int[]ansnewint[n*m];intindex0;// 0 反对角 1对角intflag0;intin-1,j0;while(indexn*m){ans[index]grid[i][j];if(flag0){if(i0){j;flag1;}elseif(j0){i--;flag1;}else{i--;j--;}}else{if(in-1){j;flag0;}elseif(jm-1){i--;flag0;}else{i;j;}}}// 输出结果StringBuilderoutnewStringBuilder();for(intk0;kn*m;k){if(k0){out.append( );}out.append(ans[k]);}System.out.print(out.toString());}}pythonimportsys datalist(map(int,sys.stdin.read().split()))idx0ndata[idx]idx1mdata[idx]idx1grid[[0]*mfor_inrange(n)]foriinrange(n):forjinrange(m):grid[i][j]data[idx]idx1ans[0]*(n*m)index0# 0 反对角 1对角flag0in-1j0whileindexn*m:ans[index]grid[i][j]index1ifflag0:ifi0:j1flag1elifj0:i-1flag1else:i-1j-1else:ifin-1:j1flag0elifjm-1:i-1flag0else:i1j1# 输出结果print(*ans)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,(line){input.push(...line.trim().split(/\s/));});rl.on(close,(){letidx0;constnNumber(input[idx]);constmNumber(input[idx]);constgridArray.from({length:n},()Array(m));for(leti0;in;i){for(letj0;jm;j){grid[i][j]Number(input[idx]);}}constansnewArray(n*m);letindex0;// 0 反对角 1对角letflag0;letin-1,j0;while(indexn*m){ans[index]grid[i][j];if(flag0){if(i0){j;flag1;}elseif(j0){i--;flag1;}else{i--;j--;}}else{if(in-1){j;flag0;}elseif(jm-1){i--;flag0;}else{i;j;}}}// 输出结果console.log(ans.join( ));});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,n,m)grid:make([][]int,n)fori:0;in;i{grid[i]make([]int,m)forj:0;jm;j{fmt.Fscan(in,grid[i][j])}}ans:make([]int,n*m)index:0// 0 反对角 1对角flag:0i,j:n-1,0forindexn*m{ans[index]grid[i][j]indexifflag0{ifi0{jflag1}elseifj0{i--flag1}else{i--j--}}else{ifin-1{jflag0}elseifjm-1{i--flag0}else{ij}}}// 输出结果out:bufio.NewWriter(os.Stdout)deferout.Flush()fork:0;kn*m;k{ifk0{fmt.Fprint(out, )}fmt.Fprint(out,ans[k])}}