首页
登录 | 注册

牛客面试算法题精讲【个人总结】-矩阵的转圈、旋转90度、“之”字形打印

题目一: 转圈打印二维数组

要求:

额外空间复杂度为O(1)

代码:

	// 实现方法 打印一圈
	private static void printCircle(int[][] matrix, int startX, int startY, int endX, int endY) {  
	    // 矩阵只有一行时 
	    if (startY == endY) {  
	        for (int i = startX; i <= endX; i++ ) {  
	            System.out.println(matrix[i][endY]);  
	        }  
	        return;  
	    }  
	    //  矩阵只有一列时 
	    if (startX == endX) {  
	        for (int i = startY; i <= endY; i++ ) {  
	            System.out.println(matrix[startX][i]);  
	        }  
	        return;  
	    }  
	    //正常情况,打印一圈
	    for (int i = startY; i < endY; i++ ) {  
	        System.out.println(matrix[startX][i]);  
	    }  
	    for (int i = startX; i < endX; i++ ) {  
	        System.out.println(matrix[i][endY]);  
	    }  
	    for (int i = endY; i > startY; i-- ) {  
	        System.out.println(matrix[endX][i]);  
	    }  
	    for (int i = endX; i > startX; i-- ) {  
	        System.out.println(matrix[i][startY]);  
	    }  
	  
	}  
	      
	private static void printMatrix(int[][] matrix) {  
	      
	    if (matrix == null) {  
	        return;  
	    }  
	    int startX = 0;  
	    int startY = 0;  
	    int endY = matrix[0].length - 1;  
	    int endX = matrix.length - 1;  
	      
	    while ((startX <= endX) && (startY <= endY)) {  
	      printCircle(matrix, startX++, startY++, endX--, endY--);  
	    }    
	} 

测试:

	public static void main(String[] args) {
		int[][] m = {  
	            {1, 2, 3, 4},  
	            {5, 6, 7, 8},  
	            {9, 10, 11, 12},  
	            {13, 14, 15, 16},  
	    };  
		printMatrix(m);
		
	}
牛客面试算法题精讲【个人总结】-矩阵的转圈、旋转90度、“之”字形打印


题目二: 顺时针转圈90度打印二维数组

要求:

额外空间复杂度为O(1)

代码:

      
	private static void printMatrix(int[][] matrix) {  
	      
	    if (matrix == null) {  
	        return;  
	    }  
	    int startX = 0;  
	    int startY = 0;  
	    int endY = matrix[0].length - 1;  
	    int endX = matrix.length - 1;  
	      
	    while ((startX <= endX) && (startY <= endY)) {  
	        rotateEdge(matrix, startX++, startY++, endX--, endY--);  
	    } 
	    print(matrix);
	}

	private static void rotateEdge(int[][] m, int i, int j, int k, int l) {
		int times = k - i;
		int tem = 0;
		for (int n = 0; n < times; n++) {
			tem = m[i][j+n];
			m[i][j+n] = m[k-n][j];
			m[k-n][j] = m[k][l-n];
			m[k][l-n] = m[i+n][l];
			m[i+n][l] = tem;
		}
	} 
	private static void print(int[][] m) {
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m.length; j++) {
				System.out.print(m[i][j]+" ");
			}
			System.out.println();
		}
	}

测试:

	public static void main(String[] args) {
		int[][] m = {  
	            {1, 2, 3, 4},  
	            {5, 6, 7, 8},  
	            {9, 10, 11, 12},  
	            {13, 14, 15, 16},  
	    };  
		printMatrix(m);
	}
牛客面试算法题精讲【个人总结】-矩阵的转圈、旋转90度、“之”字形打印

题目三:“之”字形打印矩阵

要求:

额外空间复杂度为O(1)

代码:

	private static void  printMatrix(int [][] matrix) {
	    int start1X = 0;  
	    int start1Y = 0;  
	    int start2X = 0;  
	    int start2Y = 0;  
	    int endY = matrix[0].length - 1;  
	    int endX = matrix.length - 1;  
	    //判断方向 
	    boolean dir = false;
	    while (start1X <= endX) {
			printLevel(matrix,start1X,start1Y,start2X,start2Y,dir);
			//第一点 水平移动 ,到边界后向下移动
			start1X = start1Y == endY ? start1X + 1: start1X;
			start1Y = start1Y == endY ? start1Y : start1Y + 1;
			//第二点 竖直移动 ,到边界后向右移动
			start2Y = start2X == endX ? start2Y + 1: start2Y;
			start2X = start2X == endX ? start2X : start2X + 1;
			// 换方向			
			dir = !dir ;
			System.out.println();
		}
	}
		// 根据两点坐标 打印两点间的元素 dir决定方向  
	private static void printLevel(int[][] matrix, int start1x, int start1y, int start2x, int start2y, boolean dir) {
		if (!dir) {
			while (start1x <= start2x) {
				System.out.print(matrix[start1x++][start1y--]+" ");
			}
		}else {
			while (start2x >= start1x) {
				System.out.print(matrix[start2x--][start2y++]+" ");
			}
		}
	}

测试:

public static void main(String args[]) {
		int[][] m = {  
	            {1, 2, 3, 4},  
	            {5, 6, 7, 8},  
	            {9, 10, 11, 12}
	    };  
		printMatrix(m);
	}
牛客面试算法题精讲【个人总结】-矩阵的转圈、旋转90度、“之”字形打印






2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号