记一道有意思的算法题Rotate Image（旋转图像）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了记一道有意思的算法题Rotate Image（旋转图像），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1738字，纯文字阅读大概需要3分钟。
内容图文
题出自https://leetcode.com/problems/rotate-image/ 内容为：
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
简单的说就是给出一个n*n的二维数组，然后把这个数组进行90度顺时针旋转，而且不能使用额外的存储空间。
最初拿到这道题想到的就是找出每个坐标的旋转规律。假设我们是2*2的矩阵：
a b
c d
进行旋转后，那么就变成了：
c a
d b
所以就转换成对4个数字进行轮换，而不使用额外空间的问题。最常用的交换数值而不使用额外空间的算法就是异或，比如要交换a,b的值，那么可以写为：
a
=
a^b
;
b
=
a^b
;
a
=
a^b
;
现在是对4个数字进行轮换,轮换后的结果为a=c,b=a,c=d,d=b；
所以改写成异或的算法，那么就是：
a
=
a ^ b ^ c ^ d
;
b
=
a ^ b ^ c ^ d
;
d
=
a ^ b ^ c ^ d
;
c
=
a ^ b ^ c ^ d
;
a
=
a ^ b ^ c ^ d
;
接下来就是找出二维数组中角标与a,b,c,d的关系，这个其实不难。另外，我们在进行旋转处理时，我们只需要处理1/4的区域即可，因为处理一次就是调整了4个数，所以我们只处理二维数组中左上角的数值。
下面就是具体的代码：
public
void
Rotate(
int
[,] matrix)
{
int
n
=
matrix.GetLength (
0
);
for
(var i
=
0
; i
<
(n
+
1
)
/
2
; i
++
)
{
for
(var j
=
0
; j
<
n
/
2
; j
++
)
{
//
var a = matrix[i, j];
//
var b = matrix[j, n - i - 1];
//
var d = matrix[n - i - 1, n - j - 1];
//
var c = matrix[n - j - 1, i];
matrix[i, j]
=
matrix[i, j]
^
matrix[j, n
-
i
-
1
]
^
matrix[n
-
i
-
1
, n
-
j
-
1
]
^
matrix[n
-
j
-
1
, i];
matrix[j, n
-
i
-
1
]
=
matrix[i, j]
^
matrix[j, n
-
i
-
1
]
^
matrix[n
-
i
-
1
, n
-
j
-
1
]
^
matrix[n
-
j
-
1
, i];
matrix[n
-
i
-
1
, n
-
j
-
1
]
=
matrix[i, j]
^
matrix[j, n
-
i
-
1
]
^
matrix[n
-
i
-
1
, n
-
j
-
1
]
^
matrix[n
-
j
-
1
, i];
matrix[n
-
j
-
1
, i]
=
matrix[i, j]
^
matrix[j, n
-
i
-
1
]
^
matrix[n
-
i
-
1
, n
-
j
-
1
]
^
matrix[n
-
j
-
1
, i];
matrix[i, j]
=
matrix[i, j]
^
matrix[j, n
-
i
-
1
]
^
matrix[n
-
i
-
1
, n
-
j
-
1
]
^
matrix[n
-
j
-
1
, i];
}
}
}
使用异或并不是很直观，另外一个比较直观的交换两个数据的方法是加减法：
a
=
a
+
b;
b
=
a
-
b;
a
=
a
-
b;
我们使用异或而不使用更直观的加减法是因为a+b的时候可能溢出，那么接下来的结果就不对了，所以不能用加减法而应该用异或。
原文：http://www.cnblogs.com/studyzy/p/4406436.html
内容总结
以上是互联网集市为您收集整理的记一道有意思的算法题Rotate Image（旋转图像）全部内容，希望文章能够帮你解决记一道有意思的算法题Rotate Image（旋转图像）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。