题目描述

这题有好多规律

i - j + 1, 上三角矩阵 下三角矩阵, 字符串右移……

$\color{#FF0000}{用矩阵的知识去做，时间复杂度是O(N²)}$
$\color{#FF0000}{而采用字符串右移的方式，时间复杂度是O(N)}$

字符串右移规律

• 将上一行字符串右移一个元素， 即删除最后一位元素
• 将这一行的行数拼接在字符串开头
• 需要注意的是，最后一位元素以及空格的长度并不是固定的：如: ” 5” 和 ” 20”

样例

为方便理解，这里用竖线将每行第一个元素隔开

 1 | 2 3 4 5 // 
 2 | 1 2 3 4 // 上一行向右移同时删除最后一个元素：1 2 3 4
 3 | 2 1 2 3 // 上一行向右移同时删除最后一个元素：2 1 2 3
 4 | 3 2 1 2 // 上一行向右移同时删除最后一个元素：3 2 1 2
 5 | 4 3 2 1 // 上一行向右移同时删除最后一个元素：4 3 2 1

算法

Java 代码

import java.io.*;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
import java.lang.StringBuilder;

public class Main {

    // 这里使用了快速输入输出

    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static PrintWriter out;

    static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static void println(String string) {
        out.println(string);
        out.flush();
    }

    // 以上是快速输入输出

    /**
     * 读取输入到集合
     */
    static void input(List<Integer> list) throws IOException {
        int x;
        while (true) {
            x = nextInt();
            if (x == 0) {
                break;
            }
            list.add(x);
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        List<Integer> list = new ArrayList<>();
        input(list);

        list.forEach((n)->{
            // 初始化并输出第一行
            StringBuilder builder = new StringBuilder("1");
            for (int i = 1; i < n; i++) {
                builder.append(' ');
                builder.append(i + 1);
            }
            println(builder.toString());
            // 每一行右移并输出
            for (int i = 1; i < n; i++) {
                builder.delete(builder.lastIndexOf(" "), builder.length());
                builder.insert(0, i + 1 + " ");
                println(builder.toString());
            }
            println("");
        });

    }
}