面试题29:顺时针打印矩阵

题目描述

输入一个矩阵，从外到里以顺时针顺序依次打印

思路：将其看作一圈一圈打印

1. 开始：(start, start)坐标，(0, 0), (1, 1),(2,2)…
2. 终止打印一圈的条件：cols>startx2, rows>starty2
3. 如何打印一圈？
   1. 从左到右：总需要
   2. 从上到下：起始行号>终止行号
   3. 从右到左：圈内至少两行两列
   4. 从下到上：至少三行两列

void PrintMatrixClockwisely(int **numbers, int columns, int rows)
{
	if(numbers == nullptr || columns<0 ||rows<0) return;
	int start = 0;
	while(start *2 < rows && start *2 < columns)
	{
		PrintMatixInCircle(numbers, colunmns, rows, start);
		start++;
	}

}
void PrintMatixInCircle(int **numbers,int  columns, int rows, int start)
{
	int endX = columns - 1 - start;
	int endY = rows - 1 - start;
	
	//从左到右
	for(int i=start; i<=endX; ++i)
	{
		int number = numbers[start][i]
		printNumber(number);
	}
	//从上到下
	if(start < endY)
	{
		for(int i=start + 1; i<=endY; i++)
		{
			int number  = numbers[i][endX];
			printNumber(number);
		}
	}
	//从右到左
	if(endX - start >=1 && endY-start >=1)
	{
		for(int i=endX-1; i>=start; i--)
		{
			int number = numbers[endY][i];
			printNumber(number);
		}
	}
	//从下到上
	if(start<endX && start<endY-1)
	{
		for(int i=endY-1; i>=start; i--)
		{
			int number = numbers[i][start];
			printNumber(number);
		}
	}
}

leetcode 螺旋矩阵

54. 螺旋矩阵
    给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int>res;
    int rows = matrix.size();
    if(rows<=0) return res;
    int cols = matrix[0].size();
    if(cols<=0) return res;
    
    
    int start=0;
    
    while(start * 2 <rows && start*2<cols)
    {
        int endX  = cols - 1 - start;
        int endY = rows - 1 - start;
        
        for(int i=start; i<=endX; i++)
        {
            res.push_back(matrix[start][i]);
        }
        
        if(start<endY)
        {
            for(int i=start+1; i<=endY;i++)
            {
                res.push_back(matrix[i][endX]);
            }
        }
        if(start<endX && start<endY)
        {
            for(int i=endX-1; i>=start; i--)
            {
                res.push_back(matrix[endY][i]);
            }
        }
        if(start<endX && start<endY - 1)
        {
            for(int i=endY - 1; i>start; i--)
            {
                res.push_back(matrix[i][start]);
            }
        }
        start ++;
    }
    return res;
    
}

执行用时 : 4 ms, 在Spiral Matrix的C++提交中击败了97.17% 的用户
内存消耗 : 8.8 MB, 在Spiral Matrix的C++提交中击败了17.53% 的用户

leetcode 螺旋矩阵2

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

思路同上

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int >>res(n, vector<int>(n, 0));
    if(n==0) return res;
    int rows = n, cols = n;
    int num=1;
    int start =0;
    while(num<=n*n)
    {
        int endX = cols - start -1;
        int endY = rows - start -1;
        
        for(int i=start; i<=endX; i++)
        {
            res[start][i] = num;
            num++;
        }
        if(start < endY)
        {
            for(int i=start+1; i<=endY; i++)
            {
                res[i][endX] = num;
                num++;
            }
        }
        if(start<endX && start<endY)
        {
            for(int i=endX-1; i>=start; i--)
            {
                res[endY][i] = num;
                num++;
            }
        }
        if(start<endX && start<endY - 1)
        {
            for(int i=endY - 1; i>start; i--)
            {
                res[i][start]=num;
                num++;
            }
        }
        start ++;
    }
    return res;
}

执行用时 : 8 ms, 在Spiral Matrix II的C++提交中击败了95.63% 的用户
内存消耗 : 9 MB, 在Spiral Matrix II的C++提交中击败了50.19% 的用户

leetcode 螺旋矩阵3

885. 螺旋矩阵 III
     在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始
     这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
     现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
     每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
     最终，我们到过网格的所有 R * C 个空间。
     按照访问顺序返回表示网格位置的坐标列表。

思路同上，但是加入了左边界判断

bool legPosition(int R, int C, int r0, int c0)
{
    if(r0 < R && c0 < C && r0>=0 && c0>=0)
        return true;
    return false;
}

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    vector<vector<int> >res(R, vector<int>(C, 0));
    if(R<=0 || C<=0) return res;
    int num = 1;
    int count = 1;
    int circle = 1;
    int startX = c0, startY = r0;
    while(num<=R*C)
    {
        int leftX = startX - 1 ;
        int leftY = startY - 1;
        int rightX = startX + circle*2 - 1;
        int rightY = startY + circle*2 - 1;
        
        for(int i=startX; i<=rightX; i++)
        {
            if(legPosition(R, C, startY, i))
            {
                res[startY][i] = num;
                num++;
            }
        }
        
        if(startY<rightY)
        {
            for(int i=startY+1; i<=rightY; i++)
            {
                if(legPosition(R, C, i, rightX))
                {
                    res[i][rightX] = num;
                    num++;
                }
            }
        }
        if(leftY < rightY && leftX <rightX)
        {
            for(int i=rightX-1; i>=leftX ;i--)
            {
                if(legPosition(R, C, rightY, i))
                {
                    res[rightY][i] = num;
                    num++;
                }
            }
        }
        if(leftX<rightX && leftY<rightY - 1)
        {
            for(int i=rightY - 1; i>leftY; i--)
            {
                if(legPosition(R, C, i, leftX))
                {
                    res[i][leftX] = num;
                    num++;
                }
            }
        }
        
        circle ++;
        startX --;
        startY --;
    }
    return res;
}

执行用时 : 84 ms, 在Spiral Matrix III的C++提交中击败了98.51% 的用户
内存消耗 : 13.8 MB, 在Spiral Matrix III的C++提交中击败了71.88% 的用户

最后

以上就是细心小兔子为你收集整理的面试题29:顺时针打印矩阵的全部内容，希望文章能够帮你解决面试题29:顺时针打印矩阵所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。