记一道有意思的算法题Rotate Image(旋转图像)

简介:

题出自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,如需转载请自行联系原作者

相关文章
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
3月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
141 63
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
4月前
|
机器学习/深度学习 人工智能 算法
【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA
阿里云人工智能平台 PAI 团队与华南理工大学合作在国际多媒体顶级会议 ACM MM2024 上发表 VICTORIA 算法,这是一种面向 StableDiffusion 的多目标图像编辑算法。VICTORIA 通过文本依存关系来修正图像编辑过程中的交叉注意力图,从而确保关系对象的一致性,支持用户通过修改描述性提示一次性编辑多个目标。
|
4月前
|
算法 数据安全/隐私保护
织物图像的配准和拼接算法的MATLAB仿真,对比SIFT,SURF以及KAZE
本项目展示了织物瑕疵检测中的图像拼接技术,使用SIFT、SURF和KAZE三种算法。通过MATLAB2022a实现图像匹配、配准和拼接,最终检测并分类织物瑕疵。SIFT算法在不同尺度和旋转下保持不变性;SURF算法提高速度并保持鲁棒性;KAZE算法使用非线性扩散滤波器构建尺度空间,提供更先进的特征描述。展示视频无水印,代码含注释及操作步骤。
|
5月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
|
6月前
|
算法 前端开发 计算机视觉
基于均值坐标(Mean-Value Coordinates)的图像融合算法的优化实现
基于均值坐标(Mean-Value Coordinates)的图像融合算法的优化实现
67 0
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
148 68
|
3天前
|
算法
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。

热门文章

最新文章