C++实现LeetCode(48.旋转图像)

[LeetCode] 48. Rotate Image 旋转图像

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

在计算机图像处理里，旋转图片是很常见的，由于图片的本质是二维数组，所以也就变成了对数组的操作处理，翻转的本质就是某个位置上数移动到另一个位置上，比如用一个简单的例子来分析：

1  2  3　　　 　　 7  4  1　

4  5  6　　-->　　 8  5  2　　

7  8  9 　　　 　　9  6  3

对于90度的翻转有很多方法，一步或多步都可以解，先来看一种直接的方法，这种方法是按顺时针的顺序去覆盖前面的数字，从四个顶角开始，然后往中间去遍历，每次覆盖的坐标都是同理，如下：

(i, j)  <-  (n-1-j, i)  <-  (n-1-i, n-1-j)  <-  (j, n-1-i)

这其实是个循环的过程，第一个位置又覆盖了第四个位置，这里i的取值范围是 [0, n/2)，j的取值范围是 [i, n-1-i)，至于为什么i和j是这个取值范围，为啥i不用遍历 [n/2, n)，若仔细观察这些位置之间的联系，不难发现，实际上j列的范围 [i, n-1-i) 顺时针翻转 90 度，正好就是i行的 [n/2, n) 的位置，这个方法每次循环换四个数字，如下所示：

1  2  3               7  2  1            7  4  1

4  5  6      -->      4  5  6　　 -->  　 8  5  2　　

7  8  9               9  8  3　　　　   　 9  6  3

解法一：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = i; j < n - 1 - i; ++j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
};

还有一种解法，首先以从对角线为轴翻转，然后再以x轴中线上下翻转即可得到结果，如下图所示(其中蓝色数字表示翻转轴)：

1  2  3　　　 　　 9  6  3　　　　　     7  4  1

4  5  6　　-->　　 8  5  2　　 -->   　 8  5  2　　

7  8  9 　　　 　　7  4  1　　　　　     9  6  3

解法二：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - i; ++j) {
                swap(matrix[i][j], matrix[n - 1- j][n - 1 - i]);
            }
        }
        reverse(matrix.begin(), matrix.end());
    }
};

最后再来看一种方法，这种方法首先对原数组取其转置矩阵，然后把每行的数字翻转可得到结果，如下所示（其中蓝色数字表示翻转轴，Github 上可能无法显示颜色，请参见博客园上的帖子）：

1  2  3　　　 　　 1  4  7　　　　　     7  4  1

4  5  6　　-->　　 2  5  8　　 -->  　  8  5  2　　

7  8  9 　　　 　　3  6  9　　　　       9  6  3

解法三：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

到此这篇关于C++实现LeetCode(48.旋转图像)的文章就介绍到这了,更多相关C++实现旋转图像内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(78.子集合)

    [LeetCode] 78. Subsets 子集合 Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is:

  • C++实现LeetCode(112.二叉树的路径和)

    [LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(94.二叉树的中序遍历)

    [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively

  • C++实现LeetCode(47.全排列之二)

    [LeetCode] 47. Permutations II 全排列之二 Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 这道题是之前那道 Permutations 的延伸,由于输入数组有可能出现重复数字,如果按照之前的

  • C++实现LeetCode(41.首个缺失的正数)

    [LeetCode] 41. First Missing Positive 首个缺失的正数 Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your

  • C++实现LeetCode(90.子集合之二)

    [LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example

  • C++实现LeetCode(144.二叉树的先序遍历)

    [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input:  [1,null,2,3] 1 \ 2 / 3 Output:  [1,2,3] Follow up: Recursive solution is trivial, could you do it iterat

  • C++实现LeetCode(48.旋转图像)

    [LeetCode] 48. Rotate Image 旋转图像 You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allo

  • C++实现LeetCode(43.字符串相乘)

    [LeetCode] 43. Multiply Strings 字符串相乘 Given two non-negative integers num1 and num2represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6"

  • C++实现LeetCode(312.打气球游戏)

    [LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • 收集的48个Shell脚本小技巧

    本文收集了一堆的shell脚本技巧,我说过,我写博客主要是作一些学习笔记,方便自己查阅,所以,我会搞出这么一篇文章,也没有什么不可理解的.关于这些技巧的出处,诶,我也忘了,可能来自theunixschool. commandlinefu.酷勤网和igigo.net,当然了,也有部分是我自己的经验心得,管他呢,进了我的脑子就是我的了. 0. shell 调试 复制代码 代码如下: sh -x somefile.sh 在somefile.sh 文件里加上set+x set-x 1. 用 &&

  • 48个英语音标表-附一个flash实现的音标的读音

    48个英语音标表-附一个flash实现的音标的读音

    在网上找了很久,好像都找不到,越基础越难找,经典的东西,献给初学的朋友 为方便需要的朋友特整理一些英语国际音标表.doc版本提供下载 48个英语音标表 26个字母发音表 元音字母和辅音字母分类表  附一个flash实现的音标的读音 http://www.jb51.net/downtools/flash_duyin.swf 英语国际音标 http://www.jb51.net/downtools/flash_enguoji.swf

  • centos6.7安装mysql5.5.48的方法

    本文实例讲述了centos6.7安装mysql5.5.48的方法.分享给大家供大家参考,具体如下: RPM安装mysql 5.5.48 下载对应的MySQL安装包rpm文件,可以去MySQL官方网站找到对应版本,一般需要下载3个文件 MySQL-server MySQL-client MySQL-devel 复制代码 代码如下: wget http://dev.mysql.com/get/Downloads/MySQL-5.5/MySQL-server-5.5.48-1.el6.x86_64.r

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • 在VS2008中编译MYSQL5.1.48的方法

    1. 下载MYSQL5.1.48源码,CMAKE,VS2008 2. 安装CMAKE和VS2008,解压MYSQL5.1.48到D:\mysql 3. 打开CMD:CD D:\mysql 4. 在CMD中运行命令:wscript win\configure.js WITH_INNOBASE_STORAGE_ENGINE WITH_PARTITION_STORAGE_ENGINE MYSQL_SERVER_SUFFIX=-pro 5. 在CMD中运行命令:win\build-vs9.bat 6.

  • python opencv旋转图像（保持图像不被裁减）

    python opencv旋转图像（保持图像不被裁减）

    本文实例为大家分享了python opencv旋转图像的具体代码,保持图像不被裁减,供大家参考,具体内容如下 # -*- coding:gb2312 -*- import cv2 from math import * import numpy as np img = cv2.imread("3-2.jpg") height,width=img.shape[:2] degree=45 #旋转后的尺寸 heightNew=int(width*fabs(sin(radians(degree)

随机推荐