road-of-leetcode
0048. 图像旋转
解法 1 (axis.js)
答案为经过多次优化后的版本, 理解成本较高, 为了能够更清楚地领会解法原理, 请对照 axis-origin.js 阅读以下解析:
本题说白了, 就是一个中心旋转问题, 为了方便计算, 我们可以把坐标原点移动到矩阵的中心 (就是 (length - 1) / 2, 因为数组下标从零开始, 所以需要额外 -1 来直接取得目的地下标).
而后通过图形旋转方程:
d(x`, y`) = (x * cos(-d) - y * sin(-d) , x * sin(-d) + y * cos(-d))
得:
d90(x`, y`) = (y, -x)
(其实不看公式, 靠自己画图摸一下, 也能搞出来).
而后我们从内而外地处理原图形, 从左上角位置开始 (如下图 6):
1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,14,15,16,
计算这个位置的数字该被旋转到哪里 (7 的位置).
交换过去, 并计算该位置数字应该被旋转到哪里 (11 的位置).
如此循环直至 6 本来的位置也被填上了新的数字.
处理比较大的外圈时 (如第一行), 会自左往右不停处理, 直至最后一项 (1 -> 2 -> 3, 4 不处理是因为已经在 1 时处理过一次了).
这个循环直至最外层一圈也被处理过了为止.
优化点
因为是在原图上改, 所以在函数体中会多次使用上层的 matrix 等变量, 为优化原型链寻值的效率, 直接将内部处理循环封装成一个函数供外层循环调用, 提高寻值效率.
^= 交换值这种东西用处不大, 就不说了.
