顺时针打印矩阵

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > &matrix) {
        int row = matrix.size(), col = matrix[0].size();
        int lr = col, ud = row-1;
        vector<int> ret( row*col );
        int i = 0, j = -1, k = 0;
        while( k < row*col ) {
            if( lr > 0 && k < row*col ) { for( int m = 0; m < lr; ++m ) { ret[k++] = matrix[i][++j]; } --lr; } // right
            if( ud > 0 && k < row*col ) { for( int m = 0; m < ud; ++m ) { ret[k++] = matrix[++i][j]; } --ud; } // down
            if( lr > 0 && k < row*col ) { for( int m = 0; m < lr; ++m ) { ret[k++] = matrix[i][--j]; } --lr; } // left
            if( ud > 0 && k < row*col ) { for( int m = 0; m < ud; ++m ) { ret[k++] = matrix[--i][j]; } --ud; } // up
        }
        return ret;
    }
};

import java.util.ArrayList;
public class Solution {
    ArrayList  a=new ArrayList();   new一个数组 以便下面函数能调用 
    public ArrayList printMatrix(int [][] matrix) {
       int tR=0;
       int tC=0;
       int dR=matrix.length-1;
       int dC=matrix[0].length-1;
        while(tR<=dR&&tC<=dC){ 左上边界最多到达右下边界 用于判断是否还是剥圈打印
       printEdge(matrix,tR++,tC++,dR--,dC--); 
        }
      return a;
    }
    public  void printEdge(int [][] m,int tR,int tC,int dR,int dC){
        if(tR==dR){    先判断是否只是一横行 如果是 打印该横行的列（通常用于内圈）
            for(int i=tC;i<=dC;i++){
                a.add(m[tR][i]);
            }
        }
        else if(tC==dC){  再判断是否只是一竖列 如果是 打印该横行的列（通常用于内圈
            for(int i=tR;i<=dR;i++){
                a.add(m[i][tC]);
            }
        }
        else {
            int curC=tC;用2个变量储存 用于判断当前位置
            int curR=tR;
            while(curC!=dC){      当前位置未到达当前行的最右列 --》往右去
                a.add(m[tR][curC]);
            curC++;
            }
            while(curR!=dR){      当前位置未到达当前列的最底行 --》往下去
                a.add(m[curR][dC]);
                curR++;
            }
            while(curC!=tC){      当前位置未到达当前行的最左列 --》往左去
                a.add(m[dR][curC]);
                curC--;
            }
            while(curR!=tR){      当前位置未到达当前列的最顶行 --》往上去
                a.add(m[curR][tC]);
                curR--;
            }
        }
    }
}

这个思路个人觉得看起来比上面的都要清晰 虽然较长 但是其实分析起来很简单 ，就是一个剥圈的函数，这个函数 核心就是 左上点和右下点 每次走完剥圈函数之后 左上角坐标++，右下角-- 往圈内移 如果觉得好 可以点点顶上去 让别人也看到

//借鉴的二楼的代码，对二楼的代码进行了部分判断条件的修改
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
		int row = matrix.size();
        int col = matrix[0].size();
        vector<int> result;
        
        // 输入的二维数组非法，返回空的数组
        if (row == 0 || col == 0)  return result;
        
        int top = 0, left = 0, right = col-1, bottom = row-1;
        
        while(top <= bottom && left<= right){
            //left to right
            for(int i = left; i <= right; ++i) result.push_back(matrix[top][i]);
            //top tp bottom
            for(int i = top+1; i <= bottom; ++i) result.push_back(matrix[i][right]);
            //right to left
            for(int i = right-1; i >= left && top < bottom; --i) result.push_back(matrix[bottom][i]);
            //bottom to top
            for(int i = bottom-1; i > top && right > left; --i) result.push_back(matrix[i][left]);
            ++top; ++left; --right; --bottom;
        }
        return result;
    }
};

/*
		 * 采用旋转魔方的方式 一次取一行，然后旋转
		 */
		public ArrayList<Integer> printMatrix_2(int[][] matrix) {
			ArrayList<Integer> al = new ArrayList<>();
			int row = matrix.length;
			while (row != 0) {
				for (int i = 0; i < matrix[0].length; i++) {
					al.add(matrix[0][i]);
				}
				if (row == 1)
					break;
				matrix = turn(matrix);
				row = matrix.length;
			}
			return al;
		}

		private int[][] turn(int[][] matrix) {
			// TODO 自动生成的方法存根
			int col = matrix[0].length;
			int row = matrix.length;
			int[][] newMatrix = new int[col][row - 1];
			for (int j = col - 1; j >= 0; j--) {
				for (int i = 1; i < row; i++) {
					newMatrix[col - 1 - j][i - 1] = matrix[i][j];
				}
			}
			return newMatrix;
		}



public ArrayList<Integer> printMatrix_1(int[][] matrix) {
			ArrayList<Integer> al = new ArrayList<>();
			int row = matrix.length;
			if (row == 0)
				return al;
			int col = matrix[0].length;
			// 短的边/2，向上取整
			int circle = ((row > col ? col : row) + 1) / 2;
			for (int i = 0; i < circle; i++) {

				// 从左向右打印，j=i; j<col-i,
				// 这一行的前i个已经在第i圈从下往上被打印，故j=i
				// 倒数i个都已经在第i圈从上往下被打印，故j=col-i-1<col-i
				for (int j = i; j < col - i; j++)
					al.add(matrix[i][j]);

				// 从上往下打印，j=i+1;j<row-i,
				// 这一列的前i+1个已经在从左向右打印时被打印,故j=i+1
				// 倒数i个已经在第i圈从右往左被打印,故j=row-i-1<row-i
				for (int j = i + 1; j < row - i; j++)
					al.add(matrix[j][col - i - 1]);

				// 从右往左打印，j=col-i-2;j>=i&&row-i-1!=i;，
				// 这一行倒数i个已经在第i圈从上往下被打印
				// 这一行倒数第i+1个已经在从上往下时被打印，故j=col-1-(i+1)=col-i-2
				// 这一行的前i个已经在从下往上时被打印，故j=i>=i
				// 当第i圈为0时即从未由上往下打印时，col有多列时，会造成重复打印，故判断row-i-1!=i以避免
				for (int j = col - i - 2; j >= i && row - i - 1 != i; j--)
					al.add(matrix[row - i - 1][j]);

				// 从下往上打印，j=row-i-2;j>i&&col-i-1!=i，
				// 这一列倒数i个已经在第i圈从右往作被打印
				// 这一列倒数第i+1个已经在从右往左时被打印，故j=row-1-(i+1)=row-i-2
				// 这一列的前i个已经在第i圈从左往右时被打印，
				// 这一列的第i+1个已经在本圈从左往右被打印，故j=i+1>i
				// 当第i圈为0时即从未由右向左打印时，row有多行时，会造成重复打印，故判断col-i-1!=i以避免
				for (int j = row - i - 2; j > i && col - i - 1 != i; j--)
					al.add(matrix[j][i]);
			}
			return al;
		}

/*
* 1.选坐标为(0,0),(1,1)...的点记为(start,start)为开始坐标,下一圈开始坐标为(start+1,start+1)
* 2.判断是否进入下一圈(即是否打印完成)的条件是row>start*2 && column>start*2
* 3.打印一圈的左上角坐标为(start,start)，右下角的坐标为(column-start-1,row-start-1)
* 4.根据一圈左上角和右下角坐标判断“从左到右”，“从上到下”，“从右到左”，“从下到上”哪些用打印，哪些不用
*/

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        if (matrix.empty()) {
            return matrix[0];
        }
        int row = static_cast<int>(matrix.size()) ;
        int column = static_cast<int>(matrix[0].size()) ;
        int start = 0;
        vector<int> result;
        result.clear();
        
        while (column > start*2 && row > start*2) {
            int endX = column - 1 - start;
            int endY = row - 1 - start;
            //从左到右打印一行
            for (int i=start; i<=endX; i++) {
                result.push_back(matrix[start][i]);
            }
            //从上到下打印一行
            if (start <endY) {
                for (int i=start+1; i<=endY; i++) {
                    result.push_back(matrix[i][endX]);
                }
            }
            //从右到左打印一行
            if (start < endX && start < endY) {
                for (int i=endX-1; i>=start; i--) {
                    result.push_back(matrix[endY][i]);
                }
            }
            //从下到上打印一行
            if (start<endX && start<endY-1) {
                for (int i=endY-1; i>=start+1; i--) {
                    result.push_back(matrix[i][start]);
                }
            }
            start++;
        }
        return result;
    }
};

/**
 * @description 顺时针打印矩阵
 * @author GongchuangSu
 * @since 2016.09.03
 * @explain 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 
 *                    1 2 3 4 
 *                    5 6 7 8 
 *                    9 10 11 12 
 *                    13 14 15 16 
 *          则依次打印出数字
 *                    1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
 */
import java.util.*;

public class Solution{
	ArrayList<Integer> list = new ArrayList<>();
	
    public ArrayList<Integer> printMatrix(int [][] matrix) {
    	int rows = matrix.length;
		int columns = matrix[0].length;
		int start = 0;
		while(rows > start*2 && columns > start*2){
			printMatrixInCircle(matrix, rows, columns, start);
			start++;
		}
        return list;
    }
	
	/**
	 * 功能：打印一圈
	 */
	public void printMatrixInCircle(int [][] matrix, int rows, int columns, int start){
		// 从左到右打印一行
		for(int i = start; i < columns - start; i++)
			list.add(matrix[start][i]);
		// 从上到下打印一列
		for(int j = start + 1; j < rows - start; j++)
			list.add(matrix[j][columns - start - 1]);
		// 从右到左打印一行
		for(int m = columns - start - 2; m >= start && rows - start - 1 > start; m--)
			list.add(matrix[rows - start - 1][m]);
		// 从下到上打印一列
		for(int n = rows - start - 2; n >= start + 1 && columns - start - 1 > start; n--)
			list.add(matrix[n][start]);
	}
}

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        if not matrix:
            return []
        columns = len(matrix[0])
        rows = len(matrix)
        
        def printMatrixCircle(start):
            endRow = rows - 1 - start
            endColumn = columns - 1 - start
            
            # 从左到右打印一行
            for y in range(start, endColumn + 1):
                result.append(matrix[start][y])
                
            # 从上到下打印一列
            if endRow > start:
                for x in range(start + 1, endRow + 1):
                    result.append(matrix[x][endColumn])
                    
            # 从右到左打印一行
            if endColumn > start and endRow > start:
                for y in range(endColumn - 1, start - 1, -1):
                    result.append(matrix[endRow][y])
            
            # 从下到上打印
            if endRow > start + 1 and endColumn > start:
                for x in range(endRow - 1, start, -1):
                    result.append(matrix[x][start])
        
        start = 0
        result = []
        while columns > start * 2 and rows > start * 2:
            printMatrixCircle(start)
            start += 1
       	
        
        return result

# -*- coding:utf-8 -*-
class Solution:
    def printMatrix(self, matrix):
        result = []
        while matrix:
            result += matrix.pop(0)
            if matrix:
                matrix = [[row[col] for row in matrix] for col in reversed(range(len(matrix[0])))]    # 逆时针旋转
        return result  

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {		
        vector<int> v;         
        if(matrix.size()==0||matrix[0].size()==0)return v;
        int a=0,x=matrix.size()-1,y=matrix[0].size()-1,i,j;        
        do{
        for(i=a,j=a;j<=y;j++) v.push_back(matrix[i][j]);
        for(i=a+1,j=y;i<=x;i++) v.push_back(matrix[i][j]);
        if(a!=x)for(i=x,j=y-1;j>=a;j--) v.push_back(matrix[i][j]);
        if(a!=y)for(i=x-1,j=a;i>=a+1;i--) v.push_back(matrix[i][j]);
        }while(++a<=--x&&a<=--y);
        return v; 
    }
};

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> ls = new ArrayList<Integer>();
		int colStart = 0;
		int colEnd = matrix[0].length;

		int lineStart = 0;
		int lineEnd = matrix.length;
		int count = lineEnd * colEnd;
		if (matrix == null)
			return ls;
		while (count != 0) {
			for(int i = colStart;i<colEnd;i++){
				ls.add(matrix[lineStart][i]);
				count--;
			}
			lineStart++;
			if(count==0)
				break;
			for(int i = lineStart;i<lineEnd;i++){
				ls.add(matrix[i][colEnd-1]);
				count--;
			}
			colEnd--;
			if(count==0)
				break;
			for(int i = colEnd-1;i>=colStart;i--){
				ls.add(matrix[lineEnd-1][i]);
				count--;
			}
			lineEnd--;
			if(count==0)
				break;
			for(int i = lineEnd-1;i>=lineStart;i--){
				ls.add(matrix[i][colStart]);
				count--;
			}
			colStart++;
			if(count==0)
				break;
		}
		return ls;
    }
}

//很惭愧，编译了多次才通过的代码。。
/*
    思想，用左上和右下的坐标定位出一次要旋转打印的数据，一次旋转打印结束后，往对角分别前进和后退一个单位。
    提交代码时，主要的问题出在没有控制好后两个for循环，需要加入条件判断，防止出现单行或者单列的情况。
 */
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
		int row = matrix.size();
        int col = matrix[0].size();
        vector<int> res;
        
        // 输入的二维数组非法，返回空的数组
        if (row == 0 || col == 0)  return res;
        
        // 定义四个关键变量，表示左上和右下的打印范围
        int left = 0, top = 0, right = col - 1, bottom = row - 1;
        while (left <= right && top <= bottom)
        {
            // left to right
            for (int i = left; i <= right; ++i)  res.push_back(matrix[top][i]);
            // top to bottom
            for (int i = top + 1; i <= bottom; ++i)  res.push_back(matrix[i][right]);
            // right to left
            if (top != bottom)
            for (int i = right - 1; i >= left; --i)  res.push_back(matrix[bottom][i]);
            // bottom to top
            if (left != right)
            for (int i = bottom - 1; i > top; --i)  res.push_back(matrix[i][left]);
            left++,top++,right--,bottom--;
        }
        return res;
    }
};

将最外层的四个边看成一个环，每成功'削'一个环，就接着削内层的环，直到削环失败

每次削环，按照上、右、下、左的顺序依次削边，每削一次边，检查一下环的完整性，若环不完整了，便认为是消环失败，返回false并退出

class Solution {
public:
    vector<int> *out;
    int top, bottom, left, right;
    bool printRing(vector<vector<int> > &m) {
        for (int i = left; i <= right; i++)
            out->push_back(m[top][i]);
        if (++top > bottom) return false;
        for (int i = top; i <= bottom; i++)
            out->push_back(m[i][right]);
        if (left > --right) return false;
        for (int i = right; i >= left; i--)
            out->push_back(m[bottom][i]);
        if (top > --bottom) return false;
        for (int i = bottom; i >= top; i--)
            out->push_back(m[i][left]);
        if (++left > right) return false;
        return true;
    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ret;
        out = &ret;
        if (matrix.size()) {
            top = 0, bottom = matrix.size() - 1;
            left = 0, right = matrix[0].size() - 1;
            while (printRing(matrix));
        }
        return ret;
    }
};

暴力 4个方向 右 下 左 上 依次循环

class Solution {
public:
    int dp[1000][1000];
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row = matrix.size(), col = matrix[0].size();
        int rs[] = {0, 1, 0, -1};
        int cs[] = {1, 0, -1, 0};
        memset(dp, 0, sizeof(dp));
        vector<int> ans;
        int dir = 0, r = 0, c = 0, step = row * col;
        while(step){
            step--; dp[r][c] = 1;
            ans.push_back(matrix[r][c]);
            if(r + rs[dir] >= row || r + rs[dir] < 0 || 
               c + cs[dir] >= col || c + cs[dir] < 0 ||
               dp[r + rs[dir]][c + cs[dir]]) dir = (dir + 1) % 4;
            r = r + rs[dir]; c = c + cs[dir];
        }
        return ans;
    }
};

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int n = matrix.length * matrix[0].length;
        ArrayList<Integer> ans = new ArrayList<>();
        int top = 0, bottom = matrix.length-1;
        int left = 0, right = matrix[0].length-1;
        while(top <= bottom && left <= right && ans.size() < n) {
            for(int i = left; i <= right && ans.size() < n; i++) {
                ans.add(matrix[top][i]);
            }
            for(int j = top+1; j < bottom && ans.size() < n; j++) {
                ans.add(matrix[j][right]);
            }
            for(int i = right; i >= left && ans.size() < n; i--) {
                ans.add(matrix[bottom][i]);
            }
            for(int j = bottom-1; j > top && ans.size() < n; j--) {
                ans.add(matrix[j][left]);
            }
            top++;
            left++;
            right--;
            bottom--;
        }
        return ans;
    }
}

Java 记忆化搜索解法: 时间O(nm), 空间O(nm)

import java.util.ArrayList;
public class Solution {
    int n, m;
    boolean [][] f;
    int [][] pre;

    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return list;
        n = matrix.length;
        m = matrix[0].length;

        f = new boolean[n + 5][m + 5];
        pre = new int[n + 5][m + 5];

        dfs(list, matrix, 0, 0);
        return list;
    }

    public void dfs(ArrayList<Integer> list, 
                    int [][] matrix, 
                    int x, int y) {
        if (f[x][y]) return;

        f[x][y] = true;
        list.add(matrix[x][y]);

        // 定义方向顺时针: 右->下->左->上
        int [] dx = {0, 1, 0, -1};
        int [] dy = {1, 0, -1, 0};

        // 尝试按原来的方向走
        int prev = pre[x][y];
        int a = x + dx[prev];
        int b = y + dy[prev];

        if (a >= 0 && a < n && b >= 0 && b < m) {
            // 可以走记录上一步走过的方向
            pre[a][b] = prev;
            dfs(list, matrix, a, b);
        }

        // 尝试别的走法
        for (int i = 0; i < 4; i++) {
            a = x + dx[i];
            b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m) {
                // 可以走记录上一步走过的方向
                pre[a][b] = i;
                dfs(list, matrix, a, b);
            }      
        }
    }
}

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here,可以模拟魔方逆时针旋转的方法，一直做取出第一行的操作
        result = []
        while matrix:
            result += matrix.pop(0)   # 取出第一行
            matrix = list(zip(*matrix)[::-1])
        return result