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

对角线遍历矩阵

拼多多技术岗 7月3号笔试 第一题

题目内容

给你一个大小为 $m$ × $n$ 的矩阵 $mat$，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素，对角线遍历的顺序如图所示。

输入描述

第一行包含两个整数 $m$ 和 $n$，表示矩阵的行数和列数（$1\le m,n\le 100$）。
接下来的 $m$ 行，每行包含 $n$ 个整数，表示矩阵的元素（整数范围在 $[-10000,10000]$ 之间）。

输出描述

输出一行，包含按对角线遍历顺序排列的矩阵元素，元素之间用空格隔开。

样例1

输入

3 3
1 2 3
4 5 6
7 8 9

输出

7 4 8 9 5 1 2 6 3

题解和思路

思路

实现思路：模拟

C++

#include<bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<int> ans(n * m);
int index = 0;
// 0 反对角 1对角
int flag = 0;
int i = n – 1, j = 0;
while (index < n * m) {
ans[index++] = grid[i][j];
if (flag == 0) {
if (i == 0) {
j++;
flag = 1;
} else if (j == 0) {
i—;
flag = 1;
} else {
i—;
j—;
}
} else {
if (i == n –1) {
j++;
flag = 0;
} else if (j == m – 1) {
i—;
flag = 0;
} else {
i++;
j++;
}
}

}
//输出结果
for (int i = 0; i < n * m; i++) {
if (i > 0) {
cout << " ";
}
cout << ans[i];
}
return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String line;
while ((line = br.readLine()) != null) {
sb.append(line).append(" ");
}

String[] input = sb.toString().trim().split("\\\\s+");
int idx = 0;

int n = Integer.parseInt(input[idx++]);
int m = Integer.parseInt(input[idx++]);

int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = Integer.parseInt(input[idx++]);
}
}

int[] ans = new int[n * m];
int index = 0;

// 0 反对角 1对角
int flag = 0;
int i = n – 1, j = 0;

while (index < n * m) {
ans[index++] = grid[i][j];

if (flag == 0) {
if (i == 0) {
j++;
flag = 1;
} else if (j == 0) {
i—;
flag = 1;
} else {
i—;
j—;
}
} else {
if (i == n – 1) {
j++;
flag = 0;
} else if (j == m – 1) {
i—;
flag = 0;
} else {
i++;
j++;
}
}
}

// 输出结果
StringBuilder out = new StringBuilder();
for (int k = 0; k < n * m; k++) {
if (k > 0) {
out.append(" ");
}
out.append(ans[k]);
}
System.out.print(out.toString());
}
}

python

import sys

data = list(map(int, sys.stdin.read().split()))
idx = 0

n = data[idx]
idx += 1
m = data[idx]
idx += 1

grid = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
grid[i][j] = data[idx]
idx += 1

ans = [0] * (n * m)
index = 0

# 0 反对角 1对角
flag = 0
i = n – 1
j = 0

while index < n * m:
ans[index] = grid[i][j]
index += 1

if flag == 0:
if i == 0:
j += 1
flag = 1
elif j == 0:
i -= 1
flag = 1
else:
i -= 1
j -= 1
else:
if i == n – 1:
j += 1
flag = 0
elif j == m – 1:
i -= 1
flag = 0
else:
i += 1
j += 1

# 输出结果
print(*ans)

Javascript

const readline = require("readline");

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const input = [];

rl.on("line", (line) => {
input.push(…line.trim().split(/\\s+/));
});

rl.on("close", () => {
let idx = 0;

const n = Number(input[idx++]);
const m = Number(input[idx++]);

const grid = Array.from({ length: n }, () => Array(m));

for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
grid[i][j] = Number(input[idx++]);
}
}

const ans = new Array(n * m);
let index = 0;

// 0 反对角 1对角
let flag = 0;
let i = n – 1, j = 0;

while (index < n * m) {
ans[index++] = grid[i][j];

if (flag === 0) {
if (i === 0) {
j++;
flag = 1;
} else if (j === 0) {
i—;
flag = 1;
} else {
i—;
j—;
}
} else {
if (i === n – 1) {
j++;
flag = 0;
} else if (j === m – 1) {
i—;
flag = 0;
} else {
i++;
j++;
}
}
}

// 输出结果
console.log(ans.join(" "));
});

Go

package main

import (
"bufio"
"fmt"
"os"
)

func main() {
in := bufio.NewReader(os.Stdin)

var n, m int
fmt.Fscan(in, &n, &m)

grid := make([][]int, n)
for i := 0; i < n; i++ {
grid[i] = make([]int, m)
for j := 0; j < m; j++ {
fmt.Fscan(in, &grid[i][j])
}
}

ans := make([]int, n*m)
index := 0

// 0 反对角 1对角
flag := 0
i, j := n–1, 0

for index < n*m {
ans[index] = grid[i][j]
index++

if flag == 0 {
if i == 0 {
j++
flag = 1
} else if j == 0 {
i—
flag = 1
} else {
i—
j—
}
} else {
if i == n–1 {
j++
flag = 0
} else if j == m–1 {
i—
flag = 0
} else {
i++
j++
}
}
}

// 输出结果
out := bufio.NewWriter(os.Stdout)
defer out.Flush()

for k := 0; k < n*m; k++ {
if k > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, ans[k])
}
}