题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

import java.util.*;
class Main{
public static void main(String[] args) {
// 使用排序 简单无脑 跟据back-diagonal i + j 之和 如果elem1的坐标(i1, j1) elem2的坐标（i2, j2)
// 如果 i1 + j1 < i2 + j2 elem1 一定在elem2之前 如果i1 + j1 == i2 + j2 我们观察到i + j如果是偶数那么i越大 越靠前 因为从下到上
// 如果是奇数 i越大越靠后因为从上到小 所以a[2] > b[2] 必须要reverse b[2]在之前需要positive return a[2] - b[2]
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
PriorityQueue[HTML_REMOVED] queue = new PriorityQueue[HTML_REMOVED](new Comparator[HTML_REMOVED]() {
public int compare(int[] a, int[] b) {
if (a[1] != b[1]) return a[1] - b[1];
if (a[1] % 2 == 0) { // [2, 0] [0, 2] [2, 0] -> [0, 2] negative remain this order positive reverse
return b[2] - a[2]; // - 2
}
return a[2] - b[2];
}
});
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
matrix[i][j] = sc.nextInt();
queue.offer(new int[]{matrix[i][j], i + j, i});
}
}
while (!queue.isEmpty()) {
int[] x = queue.poll();
System.out.print(x[0]);
System.out.print(‘ ‘);
}
}
}

import java.util.Scanner;
class Main{// 本题除了可以排序做还可以加一个下半部分 右半部分 row + col = val 是偶数的从下到上面知道起始点(val, 0) -> (0, val)
// 如果row + col = val 是奇数 从上面到下面知道 起始点是(0, val) -> (val, 0) 如果遍历过程中发现不满足row < n && col < n就不管
// 0 1 2 3 4 5 6 7 8 我们可以观察除了本身的 0 1 2 3 4
// 1 2 3 4 5 6 7 8 1 2 3 4 5
// 2 3 4 5 6 7 8 2 3 4 5 6
// 3 4 5 6 7 8 3 4 5 6 7
// 4 5 6 7 8 4 5 6 7 8 除了这个其他都是补的我们可以看出在反对角线上row + col = 定值
// 5 6 7 8 第一个反对角线上row + col =0 第二个反对角线上row + col = 1 同理第三个
// 6 7 8 我把数据标记为row + col= 值的了
// 7 8
// 8
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
matrix[i][j] = sc.nextInt();
}
}
for (int i = 0; i <= 2 * n - 2; i) {
if (i % 2 == 0) {
for (int j = 0; j <= i; j) { // row is
int row = i - j, col = j;
if (row < n && col < n) {
System.out.print(matrix[row][col]);
System.out.print(‘ ‘);
}
}
} else {
for (int j = i; j >= 0; j–) {
int row = i - j, col = j;
if (row < n && col < n) {
System.out.print(matrix[row][col]);
System.out.print(‘ ‘);
}
}
}
}

    // 另外一种写法可以说是上面的优化
    int index = 0;
    int[] res = new int[n * n];
    for (int d = 0; d <= 2 * n - 2; d++) {
        LinkedList<Integer> list = new LinkedList<>();
        int row = d < n? 0 : d - n + 1;
        int col = d < n? d : n - 1;
        while (row < n && col >= 0) {
            if (d % 2 == 0) {
                list.addFirst(matrix[row][col]);
            } else {
                list.addLast(matrix[row][col]);
            }
            row++;
            col--;
        }
        for (int elem : list) res[index++] = elem; 
    }
    for (int elem : res) {
        System.out.print(elem);
        System.out.print(' ');
    }

}
}

}