题目:Spiral Matrix
螺旋输出一个数组。
思路:
螺旋的方式遍历这个数组,一次外循环,遍历数组一圈,直到全部遍历完。
/*************************************************************************************************** Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. ***************************************************************************************************/ #include<stdio.h> /** * Note: The returned array must be malloced, assume caller calls free(). */ int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize) { int *array = (int *)malloc(matrixRowSize*matrixColSize*sizeof(int)); int rowUp = 0,rowLow = matrixColSize - 1,columnUp = 0,columnLow = matrixRowSize - 1; int i,index = 0; while(rowUp < rowLow && columnUp < columnLow){ for(i = rowUp;i < rowLow;i++){//行的上下界 array[index++] = matrix[columnUp][i]; } for(i = columnUp;i < columnLow;i++){//列的上下界 array[index++] = matrix[i][rowLow]; } for(i = rowLow;i > rowUp;i--){ array[index++] = matrix[columnLow][i]; } for(i = columnLow;i > columnUp;i--){ array[index++] = matrix[i][rowUp]; } columnUp++; rowUp++; columnLow--; rowLow--; } if(rowUp == rowLow){//还剩一列 for(i = columnUp;i <= columnLow;i++) array[index++] = matrix[i][rowUp]; }else if(columnUp == columnLow){//还剩一行 for(i = rowUp;i <= rowLow;i++) array[index++] = matrix[columnUp][i]; } return array; } void main(){ int num = 5; int **a = (int **)malloc(num*sizeof(int *)); for(int i = 0;i < num;i++){ a[i] = (int *)malloc(num*sizeof(int)); for(int j = 0;j < num;j++){ a[i][j] = i*num + j + 1; printf("%d ",a[i][j]); } printf("\n"); } int *ret = spiralOrder(a,num,num); for(int i = 0;i < num*num;i++){ printf("%d ",ret[i]); } free(ret); for(int i = 0;i < num;i++){ free(a[i]); } free(a); }
题目:Spiral MatrixII
给定一个数字n,则有n^2个数字,螺旋的形式将这些数字分布到n单元的数组中。
思路:
和上面类似一圈为一个周期,但是这个数组是nxn的不会有行列不等的情况。
package com.example.medium; /** * Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. *For example, *Given n = 3, *You should return the following matrix: *[ * [ 1, 2, 3 ], * [ 8, 9, 4 ], * [ 7, 6, 5 ] *] * @author FuPing * */ public class GenerateMatrix { public static int[][] generateMatrix(int n){ if(n < 0)return null; int [][]matrix = new int[n][n]; int up = 0,low = n - 1,i,index = 1;//index数字的值 while(up < low){ for(i = up;i < low;i++){//up表示行标下界,low表示列标的上界 matrix[up][i] = index++; } for(i = up;i < low;i++){ matrix[i][low] = index++; } for(i = low;i > up;i--){ matrix[low][i] = index++; } for(i = low;i > up;i--){ matrix[i][up] = index++; } up++; low--; } if(up == low)matrix[up][up] = index++;//n为奇数时 return matrix; } public static void main(String args[]){ int n = 0; int [][]a = generateMatrix(n); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ System.out.print(a[i][j] + " "); } System.out.println(); } } }