Elixir求解螺旋矩阵问题

题目是构造一个 n 维的顺时针螺旋矩阵，那么什么是螺旋矩阵呢？就是从左上角开始按顺时针方向从外向内依次递增的二维矩阵。一个3维螺旋矩阵示例如下：

我们是在 elixir 中求解，没有变量，没有循环，但是我们有递归。首先我们要先确定可重复的计算是什么，以 3x3 的螺旋矩阵为例，我们沿着顺时针方向用不同颜色标注出每次递归的内容，如下图所示。

首先我们把矩阵分成第一行和剩余部分，第一行很好生成，就是一个长度为 n 的递增数组，如果递归能构造出剩余部分，那么问题就解决了。可问题是这个规律能成立吗？这么看不太好看，不妨每次拆分后把矩阵逆时针旋转90度。

将矩阵旋转之后，我们发现的确是可以将它拆分成递增的第一行和剩余部分。不过先别急，我们还有一个问题需要解决。第一行很好构建，剩余部分来自下一次递归调用，但是它的结果我们却不能直接使用。

观察上图中的第3和第4幅图，它们分别是第3次和第4次迭代的状态。第3次迭代中，我们需要构造的第一行是 [6,7] ，剩余部分来自第4次迭代。我们期望的是 [9, 8] ，但是实际第4次迭代的结果是 [[8], [9]] 。

这不完了吗？但是先别急，矩阵是可以变换的。矩阵[[8], [9]] 先反转，再转置结果就是 [9, 8] 了，这样看不太明显，我们以第3次迭代结果为例看下转换过程。

不得不说，秒，实在是秒！

# 生成旋转矩阵
def matrix(0), do: []
def matrix(dimension), do: do_matrix(dimension, dimension, 1)defp do_matrix(_, 0, _), do: [[]]
defp do_matrix(rows, cols, min) dotop_row = Enum.to_list(min .. (min + cols - 1))other_rows = do_matrix(cols, rows - 1, min + cols) |> rotate_right[top_row | other_rows]
enddefp rotate_right(rows), do: rows |> Enum.reverse |> transpose# 矩阵转置
defp transpose(rows), do: rows |> Enum.zip |> Enum.map(&Tuple.to_list/1)

在 elixir 中，矩阵转置也很秒，优雅，实在是优雅。

另一种递归思路是拆分成中心和外圈，如下图：

虽然这样磕磕绊绊也能将矩阵构造出来，但是没有第一种方式优雅，所以就不贴代码了。

说到这里，leetcode上也有一道类似的题目，但它是反过来，按顺时针方向螺旋输出矩阵，这不是巧了嘛这不，通过反转和转置，我们只需要每次将矩阵的第一行拼接到结果数组中就行了。贴下代码：

defmodule Solution do@spec spiral_order(matrix :: [[integer]]) :: [integer]def spiral_order([]), do: []def spiral_order([h|t]) dotail = t |> transpose |> Enum.reverse |> spiral_orderEnum.concat(h, tail)enddefp transpose(rows), do: rows |> Enum.zip() |> Enum.map(&Tuple.to_list/1)
end

---