Jam*_*amy 5 ruby arrays algorithm traversal multidimensional-array
给定2D矩阵:
matrix = [
[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]
]
我们如何逆时针旋转矩阵,以便像这样推动值？
matrix = [
[ 2, 3, 4, 8 ]
[ 1, 7, 11, 12 ]
[ 5, 6, 10, 16 ]
[ 9, 13, 14, 15 ]
]
这个问题不是重复this&this因为我想要做到的,是在逆时针旋转时尚的值.
我当前的实现仅以逆时针方式打印出值,但它不会旋转值.
layers = [_rows, _cols].min / 2
r1, r2, c3, c4 = 0, _rows, _cols, _cols
new_matrix = Array.new(_rows + 1) { Array.new(_cols + 1) }
(0..layers).each do |layer|
row_top_left, row_bottom_left, col_top_right, col_bottom_right = r1, r2, c3, c4
result = []
while row_top_left < row_bottom_left
result << matrix[row_top_left][layer]
row_top_left += 1
end
row_bottom_left = layer
while row_bottom_left < col_bottom_right
result << matrix[row_top_left][row_bottom_left]
row_bottom_left += 1
end
temp_col_bottom_right = col_bottom_right
temp_col_top_right = layer
while col_bottom_right > temp_col_top_right
result << matrix[col_bottom_right][temp_col_bottom_right]
col_bottom_right -= 1
end
# p row_top_left
tmp_row_top_left = layer
while col_top_right > tmp_row_top_left
result << matrix[tmp_row_top_left][col_top_right]
col_top_right -= 1
end
p result.cycle
r1 += 1
r2 -= 1
c3 -= 1
c4 -= 1关键的想法是矩阵需要以正确的方式旋转.例如,假设我们的矩阵需要2次旋转.因此:
matrix_rotation(
matrix.length - 1, # rows
matrix[0].length - 1, # columns
2, # Nom. of rotation
matrix # The matrix
)
matrix = [
# Original Iter: 1 Iter: 2
[ 1, 2, 3, 4 ], # [ 2, 3, 4, 8 ] # [ 3, 4, 8, 12 ]
[ 5, 6, 7, 8 ], # [ 1, 7, 11, 12 ] # [ 2, 11, 10, 16 ]
[ 9, 10, 11, 12 ], # [ 5, 6, 10, 16 ] # [ 1, 7, 6, 15 ]
[ 13, 14, 15, 16 ] # [ 9, 13, 14, 15 ] # [ 5, 9, 13, 14 ]
]
数组的维度表示为:NxM其中N和M可以是任何数字,偶数或奇数.例如5x4,4,4,4x8等.
没有"空方块"这样的东西.
如果您想直接跳到解决方案代码，请跳到此答案的底部部分。
\n\n你需要分解问题并独立解决每一个问题。
\n\n让我们分别讨论每一点：
\n\n您需要一种方法来获取层数。下面的矩阵有 2 层。如何？
\n\n给定一个矩阵：
\n\n matrix layers\n --------------------------------\n | 1, 2, 3, 4 | 0 0 0 0 |\n | 5, 6, 7, 8 | 0 1 1 0 |\n | 9, 10, 11, 12 | 0 1 1 0 |\n | 13, 14, 15, 16 | 0 0 0 0 |\n --------------------------------\n要查找层数，只需执行以下操作：
\n\n[rows, cols].min / 2\n这样第一个问题就解决了。
\n\n这部分需要很多思考。让我们想象一下：
\n\n matrix layers\n --------------------------------\n | 1, 2, 3, 4 | \xe2\x86\x93 \xe2\x86\x90 \xe2\x86\x90 \xe2\x86\xb0 | 0 0 0 0 |\n | 5, 6, 7, 8 | \xe2\x86\x93 1 1 \xe2\x86\x91 | 0 \xe2\x86\x93 \xe2\x86\xb0 0 |\n | 9, 10, 11, 12 | \xe2\x86\x93 1 1 \xe2\x86\x91 | 0 \xe2\x86\xb3 \xe2\x86\x92 0 |\n | 13, 14, 15, 16 | \xe2\x86\xb3 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 | 0 0 0 0 |\n --------------------------------\n这是可以实现的。我们将有 4 个for循环。每个循环将处理：
在进入循环之前，我们需要一些容器以螺旋形式存储我们的值。
\n\n让我们有一个临时数组来存储值：
\n\n matrix layers\n --------------------------------\n | 1, 2, 3, 4 | 0 0 0 0 |\n | 5, 6, 7, 8 | 0 1 1 0 |\n | 9, 10, 11, 12 | 0 1 1 0 |\n | 13, 14, 15, 16 | 0 0 0 0 |\n --------------------------------\n为了便于解释，我们只研究最外层。（即第0层：
\n\n[rows, cols].min / 2\n注： 0表示第0层。
matrix layers\n --------------------------------\n | 1, 2, 3, 4 | \xe2\x86\x93 \xe2\x86\x90 \xe2\x86\x90 \xe2\x86\xb0 | 0 0 0 0 |\n | 5, 6, 7, 8 | \xe2\x86\x93 1 1 \xe2\x86\x91 | 0 \xe2\x86\x93 \xe2\x86\xb0 0 |\n | 9, 10, 11, 12 | \xe2\x86\x93 1 1 \xe2\x86\x91 | 0 \xe2\x86\xb3 \xe2\x86\x92 0 |\n | 13, 14, 15, 16 | \xe2\x86\xb3 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 | 0 0 0 0 |\n --------------------------------\n# this array will get us the output of borders of the layer\nrow = []\n# this loop will output the top-left side of the matrix\n# ==============================\n# \xe2\x86\x93 [ 1, 2, 3, 4 ]\n# \xe2\x86\x93 [ 5, 6, 7, 8 ]\n# \xe2\x86\x93 [ 9, 10, 11, 12 ]\n# \xe2\x86\x93 [ 13, 14, 15, 16 ]\n# Output: [[1, 5, 9], [6] ]\n# ==============================\n(0...rows - 1 - layer).each do |i|\n row << matrix[i][layer]\nend\n现在，我们得到了螺旋形式的值。但这个问题最重要的地方就在这一段。一个人如何转变价值观？有趣的是，我们将使用模。
\n\n模数将在这里完成主要任务。它将允许我们根据旋转来移动值。但也给我们数组中正确的索引来开始移位。例如，如果我们要旋转 2 次：最外层为 2 % 12 = 2。
\n\n# this loop will output the bottom side of the matrix\n# ==============================\n# \xe2\x86\x93 [ 1, 2, 3, 4 ]\n# \xe2\x86\x93 [ 5, 6, 7, 8 ]\n# \xe2\x86\x93 [ 9, 10, 11, 12 ]\n# \xe2\x86\x93 [ 13, 14, 15, 16 ]\n# \xe2\x86\xaa \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92\n# Output: [[1, 5, 9, 13, 14, 15], [6, 10]]\n# ==============================\n(0...cols - 1 - layer).each do |i|\n row << matrix[rows - 1 - layer][i]\nend\n在移动值之前，让我们创建另一个包含正确值的矩阵：
\n\n# this loop will output the right side of the matrix\n# ==============================\n# \xe2\x86\x93 [ 1, 2, 3, 4 ] \xe2\x86\x91\n# \xe2\x86\x93 [ 5, 6, 7, 8 ] \xe2\x86\x91\n# \xe2\x86\x93 [ 9, 10, 11, 12 ] \xe2\x86\x91\n# [ 13, 14, 15, 16 ] \xe2\x86\x91\n# \xe2\x86\xaa \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 \xe2\xa4\xbb\n# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8], [6, 10, 11]]\n# ==============================\n(rows - 1 - layer).step(0 + 1, -1).each do |i|\n row << matrix[i][cols - 1 - layer]\nend\n我们将以相同的方式再次循环，但从 中的 idx 获取值row。例如：
# this loop will output the top side of the matrix\n# ==============================\n# \xe2\x86\x90 \xe2\x86\x90 \xe2\x86\x90 \xe2\x86\x90 \xe2\x86\xb0\n# \xe2\x86\x93 [ 1, 2, 3, 4 ] \xe2\x86\x91\n# \xe2\x86\x93 [ 5, 6, 7, 8 ] \xe2\x86\x91\n# \xe2\x86\x93 [ 9, 10, 11, 12 ] \xe2\x86\x91\n# [ 13, 14, 15, 16 ] \xe2\x86\x91\n# \xe2\x86\xaa \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x92 \xe2\xa4\xbb\n# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2], [6, 10, 11, 7]]\n# ==============================\n(cols - 1 - layer).step(0 + 1, -1).each do |i|\n row << matrix[layer][i]\nend\n注： 0是第0层（为了解释起见）
# row = [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]\nshift = rotate % row.size\n# if we negate shift variable, we can get correct index\n# i.e. row[-2] = 3\nidx = -shift\n