经典算法面试题目-矩阵旋转90度(1.6)-阿里云开发者社区

开发者社区> 谙忆> 正文

经典算法面试题目-矩阵旋转90度(1.6)

简介: 题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
+关注继续查看

题目

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。 你能原地进行操作吗?(即不开辟额外的存储空间)

解答

我们假设要将图像逆时针旋转90度,顺时针是一个道理。如果原图如下所示:

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16

那么逆时针旋转90度后的图应该是:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13

我们要如何原地进行操作以达到上面的效果呢?可以分两步走。 第一步交换主对角线两侧的对称元素,第二步交换第i行和第n-1-i行,即得到结果。 看图示:(如果是顺时针, 第一步交换/对角线两侧的对称元素,第二步交换第i行和第n-1-i行,即得到结果。)

原图:           第一步操作后:   第二步操作后:
1 2 3 4         1 5 9 13        4 8 12 16
5 6 7 8         2 6 10 14       3 7 11 15
9 10 11 12      3 7 11 15       2 6 10 14
13 14 15 16     4 8 12 16       1 5 9 13

顺时针90度与逆时针90度的代码如下:

#include <iostream>
using namespace std;

void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}
//这2个交换函数,选一个就行了,我只是为了演示它们实现的结果是一样
void swap2(int &a,int &b){
    int t = a;
    a = b;
    b = t;
}


//顺时针
void clockwise(int a[][4],int n){
     for(int i=0; i<n; ++i)
        for(int j=0; j<n-i; ++j)
            swap(a[i][j], a[n-1-j][n-1-i]);

    for(int i=0; i<n/2; ++i)
        for(int j=0; j<n; ++j)
            swap(a[i][j], a[n-1-i][j]);
}

//逆时针
void transpose(int a[][4], int n){
    for(int i=0; i<n; ++i)
        for(int j=i+1; j<n; ++j)
            swap(&a[i][j], &a[j][i]);
    for(int i=0; i<n/2; ++i)
        for(int j=0; j<n; ++j)
            swap(&a[i][j], &a[n-1-i][j]);
}
int main(){
    int a[4][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    for(int i=0; i<4; ++i){
        for(int j=0; j<4; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    transpose(a, 4);
    cout<<"逆时针转90度"<<endl;
    for(int i=0; i<4; ++i){
        for(int j=0; j<4; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    a = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    for(int i=0; i<4; ++i){
        for(int j=0; j<4; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    clockwise(a,4);
    cout<<endl;
    cout<<"顺时针转90度"<<endl;
    for(int i=0; i<4; ++i){
        for(int j=0; j<4; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

输出结果:

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
高明!OpenAI提出HER算法,AI系统学会从错误中学习
OpenAI在利用增强学习训练人工智能系统任务上不断地取得进步。他们发布的新平台显示,可以允许人工智能系统从错误中吸取教训,并将错误视为系统的目标而非失败。
4000 0
数据分析与挖掘的经典算法
最近看到一篇文章介绍了数据分析与挖掘的十大经典算法:C4.5,K-Means,SVM,Apriori,EM,PageRank,AdaBoost,KNN,Native Bayes,CART。
2365 0
任务调度:时间轮算法经典案例解析及应用实现
平时大家的工作中应该会遇到较多需要在某个时间点执行某个任务,比如对运维来说,定时数据库的备份,日志和监控信息的抓取;比如业务系统,某个时间点给某个人群用户发放优惠券,甚至从操作系统角度,人机交互进程、视频播放的实时进程、批处理的后台进程等进程间的调度。。。 所以如何将这些任务高效、精准的调度?是任务调度系统中最重要的命题,当然在业务系统中一个完善的任务调度系统是很复杂的,需要具备能调度、可视化管理、过程可追溯、结果可分析、持久化、高可用等特性,这篇文章主要讨论任务调度逻辑,其余的内容我们后面文章探讨。
124 0
经典算法面试题目-判断两个字符串是否是变位词(1.4)
题目 Write a method to decide if two strings are anagrams or not. 写一个函数判断两个字符串是否是变位词。 解答 变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词。
1082 0
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2225 0
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
193 0
经典算法详解(10)图中有多少个三角形
题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。 C++版本 1 #include 2 3 using namespace std; 4 5 const char NO_POINT = '0'; 6 7 //任意的一条线 8 const char *map[]...
3703 0
+关注
谙忆
GitHub: https://github.com/chenhaoxiang
714
文章
40
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载