第一题：螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
示例 3:
输入:
[
[1]
]
输出: [1]
示例 4:
输入:
[
[2, 3, 4],
[5, 6, 7],
[8, 9, 10],
[11, 12, 13]
]
输出: [2,3,4,7,10,13,12,11,8,5,6,9]
public IList<int> SpiralOrder(int[][] matrix)
{
IList<int> result = new List<int>();
if (matrix == null || matrix.Length == 0)
return result;
int start = 0;
int end1 = matrix[start].Length - 1 - start;
int end2 = matrix.Length - 1 - start;
// 只有横着的情况
if (start == end2)
{
LeftToRight(start, end1, start, matrix, result);
return result;
}
//只有竖着的情况
if (start == end1)
{
TopToBottom(start, end2, start, matrix, result);
return result;
}
while (start < end1 && start < end2)
{
LeftToRight(start, end1, start, matrix, result);
TopToBottom(start + 1, end2, end1, matrix, result);
RightToLeft(end1 - 1, start, end2, matrix, result);
BottomToTop(end2 - 1, start + 1, start, matrix, result);
start++;
end1 = matrix[start].Length - 1 - start;
end2 = matrix.Length - 1 - start;
}
// 只剩下横着的情况
if (start == end2)
{
LeftToRight(start, end1, start, matrix, result);
}
else if (start == end1)
{
//只剩下竖着的情况
TopToBottom(start, end2, start, matrix, result);
}
return result;
}
private void LeftToRight(int start, int end, int rowIndex, int[][] matrix, IList<int> lst)
{
for (int i = start; i <= end; i++)
{
lst.Add(matrix[rowIndex][i]);
}
}
private void TopToBottom(int start, int end, int colIndex, int[][] matrix, IList<int> lst)
{
for (int i = start; i <= end; i++)
{
lst.Add(matrix[i][colIndex]);
}
}
private void RightToLeft(int start, int end, int rowIndex, int[][] matrix, IList<int> lst)
{
for (int i = start; i >= end; i--)
{
lst.Add(matrix[rowIndex][i]);
}
}
private void BottomToTop(int start, int end, int colIndex, int[][] matrix, IList<int> lst)
{
for (int i = start; i >= end; i--)
{
lst.Add(matrix[i][colIndex]);
}
}
第二题：螺旋矩阵 II
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入:3输出:[ [1,2,3], [8,9,4], [7,6,5]]
public class Solution
{
public int[][] GenerateMatrix(int n)
{
int[][] matrix = new int[n][];
for (int i = 0; i < n; i++)
{
matrix[i] = new int[n];
}
int start = 0;//起始位置
int end1 = n - 1;//最左边位置
int end2 = n - 1;//最下边位置
int count = 1;
while (start < end1 && start < end2)
{
LeftToRight(start, end1, start, matrix, ref count);
TopToBottom(start + 1, end2, end1, matrix, ref count);
RightToLeft(end1 - 1, start, end2, matrix, ref count);
BottomToTop(end2 - 1, start + 1, start, matrix, ref count);
start++;
end1 = n - 1 - start;
end2 = n - 1 - start;
}
if (n%2 == 1)
{
matrix[start][start] = count;
}
return matrix;
}
private void LeftToRight(int start, int end, int rowIndex, int[][] matrix, ref int from)
{
for (int i = start; i <= end; i++)
{
matrix[rowIndex][i] = from;
from++;
}
}
private void TopToBottom(int start, int end, int colIndex, int[][] matrix, ref int from)
{
for (int i = start; i <= end; i++)
{
matrix[i][colIndex] = from;
from++;
}
}
private void RightToLeft(int start, int end, int rowIndex, int[][] matrix, ref int from)
{
for (int i = start; i >= end; i--)
{
matrix[rowIndex][i] = from;
from++;
}
}
private void BottomToTop(int start, int end, int colIndex, int[][] matrix, ref int from)
{
for (int i = start; i >= end; i--)
{
matrix[i][colIndex] = from;
from++;
}
}
}
第三题：不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m =3, n =2输出:3解释:从左上角开始，总共有3条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
示例 2:
输入: m =7, n =3输出:28
示例 3:
输入: m =23, n =12输出:193536720
public class Solution
{
private int _m;
private int _n;
public int UniquePaths(int m, int n)
{
_m = m;
_n = n;
int count = 0;
RecordPaths(0, 0, ref count);
return count;
}
private void RecordPaths(int i, int j, ref int count)
{
if (i == _m - 1 && j == _n - 1)
{
count++;
return;
}
if (i < _m)
{
RecordPaths(i + 1, j, ref count);
}
if (j < _n)
{
RecordPaths(i, j + 1, ref count);
}
}
}
