题解 | #蛇形矩阵#

蛇形矩阵

http://www.nowcoder.com/practice/649b210ef44446e3b1cd1be6fa4cab5e

描述

题目描述

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

例如，当输入5时，应该输出的三角形为：

1 3 6 10 15

2 5 9 14

4 8 13

7 12

输入描述：

输入正整数N（N不大于100）

输出描述：

输出一个N行的蛇形矩阵。

示例

知识点：模拟，数组

难度：⭐⭐⭐

题解

方法一：最暴力的规律

图解：

解题思路：

观察任意字符的右边和下边元素值的变化，找出规律

算法流程：

从多个例子中找出规律即可，如输入4
- 第一行：[1 3 6 10]
- 第二行：去掉第一行的第一列，然后将后面的[3 6 10]分别减1得到的。
先构造第一行，根据规律可知，第一行每一列之间的递增大小逐次加一
开始构造第二行时，忽略第一行的第一列，然后将后面的[3 6 10]分别减1得到的。
每一行处理后封装结果到 StringBuilder，注意空格和换行符

Java 版本代码如下：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int len = in.nextInt();
            solution(len);
        }
    }

    private static void solution(int len) {
    	int[] nums = new int[len];
    	StringBuilder res = new StringBuilder();
    	for(int i = 0; i < len; i++) {
    		// 先构造第一行
    		if(i == 0) {
    			int addVal = 2;
    			nums[0] = 1;
    			for(int j = 1; j < len; j++) {
    				nums[j] = nums[j - 1] + addVal;
    				addVal++;
    			}
    		} else {
    			// 从第二行开始构造每一列，遍历次数：(len-i)
    			for(int j = 1; j <= len - i; j++) {
    				nums[j - 1] = nums[j] - 1;
    			}
    		}
			
			for(int k = 0; k < len - i; k++) {
				res.append(nums[k] + " ");
			}    		
			res.append("\n");
    	}
    	System.out.println(res.toString().substring(0, res.length() - 1));
    }

}

复杂度分析：

时间复杂度： $O (N^{2})$ ，遍历处理每一行每一列所需要的时间复杂度

空间复杂度： $O (N)$ ，维护了大小为N 的数组和结果字符串

方法二：构造数组

解题思路：

通过几个例子找出数组的递增规律来构造数组

算法流程：

维护一个二维数组，构造数组时，从左下到右上的斜顺序构造数组
封装结果为字符串即可

Java 版本代码如下：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int num = in.nextInt();
            solution(num);
        }
    }

    private static void solution(int num) {
        StringBuilder res = new StringBuilder();
        int[][] arr = new int[num][num];
        int count = 1;
        for(int i = 0; i < num; i++) {
            // 从左下到右上的斜顺序构造数组
            for(int j = i; j >= 0; j--) {
                arr[j][i - j] = count++;
            }
        }
        // 封装结果
        for(int i = 0; i < arr.length; i++) {
        	// 只需要遍历非0的元素
            for(int j = 0; j < arr.length - i; j++) {
            	res.append(arr[i][j] + " ");
            }
            // 对每一行最后添加换行符
            if(i != num - 1) {
                res.append("\n");
            }
        }
        System.out.println(res);
    }
}

复杂度分析：

时间复杂度： $O (N^{2})$ ，从二维数组封装结果、以及构造数组数组时需要循环遍历元素