旋轉圖像

旋轉圖像

  給定一個N×N的二維矩陣表示圖像,90度順時針旋轉圖像。

看個例子

          

算法1:

  如上圖所示,設一個N階二維矩陣,則將矩陣從外向里可以分成N/2個圈,例如(1 2 3 4 8 12 16 15 14 13 9 5)這是最外邊的圈,設圈的維度是n(最外圈有n=N=4),而(6 7 11 10)這是里邊的一個圈(n=2), 旋轉90度之后,每個數字是按照順時針的方向移動了n-1個位置。

找到數字該去的位置:

pair<int, int> getNextPos(int i, int j, int top, int left, int down, int right){//(top, left) (down, right)標示這個圈的范圍,即左上角坐標和右下角坐標int n = down-top+1;//得到這個圈的維度int move = n-1;//轉過move個位置while(move--){if(i==top && j>=left && j<right)++j;else if(i>=top && i<down && j==right)++i;else if(i==down && j<=right && j>left)--j;else if(i<=down && i>top && j==left)--i;}return make_pair(i, j);
}

旋轉過程:

  由上圖可見,1到4的位置,4到16的位置,16到13的位置,13到1的位置,結束循環。接著數字2和數字3按照同樣的步驟,完成了整個圈的旋轉操作。

void rotate(vector<vector<int> > &matrix) {// write your code here//方法1:轉圈法,從外圈到里圈,設圈的維度是n,圖像旋轉90度后,數字順時針移動n-1個位置int circle = matrix.size()/2;//得到圈的個數int top=0, left=0, down=matrix.size()-1, right=matrix.size()-1;//最外圈的維度for(int cir=0; cir<circle; ++cir){int ttop = top+cir;int lleft = left+cir;int rright = right-cir;int ddown = down-cir;
       //(ttop, lleft) (ddown, rright)標示這個圈
for(int j=lleft; j<rright; ++j){pair<int, int> org = make_pair(ttop, j);//原始位置,如果再次到這個位置,說明交換完畢pair<int, int> cur = org;int cur_val = matrix[cur.first][cur.second];//當前數的值while(true){pair<int, int> _next = getNextPos(cur.first, cur.second, ttop, lleft, ddown, rright);swap(matrix[_next.first][_next.second], cur_val);if(_next==org) break;cur = _next;}}}
}

算法2:

  通過兩次折疊,先上下對換,再根據對角線對換,即可得到目標圖像。

void rotate(vector<vector<int> > &matrix) {int n = matrix.size();for(int i=0; i<n/2; ++i)for(int j=0; j<n; ++j)swap(matrix[i][j], matrix[n-i-1][j]);//上下對換for(int i=0; i<n; ++i)for(int j=0; j<i; ++j)swap(matrix[i][j], matrix[j][i]);//主對角線兩側交換
}

?

題目鏈接:

  http://www.lintcode.com/zh-cn/problem/rotate-image/

?

轉載于:https://www.cnblogs.com/hujunzheng/p/5048300.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/531367.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/531367.shtml
英文地址,請注明出處:http://en.pswp.cn/news/531367.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

嵌入式開發板模擬器:QEMU

前兩天看微信公眾號時發現了一個嵌入式模擬器&#xff0c;感覺很不錯&#xff0c;自己動手安裝了一個&#xff0c;折騰了幾天&#xff0c;下載一直是個問題&#xff0c;特此記錄如下 模擬器大家應該都聽說過&#xff0c;有的小伙伴打游戲也會安裝模擬器&#xff0c;今天我們介紹…

gcc: weak_alias如何使用

本文主要說明weak和alias是什么和如何使用它 __attribute__是用來說明函數的屬性&#xff0c;weak和alias分別是兩個屬性。 &#xff08;一&#xff09;強符號和弱符號&#xff1a; 強符號&#xff1a;已經初始化的全局變量和未被weak修飾的函數弱符號&#xff1a;未初始化的全…

靜態Include和動態Include測試并總結

主要代碼 hjzgg.css .center-div{width:auto;margin-left: 40%;margin-right: 40%;display: block;position: absolute;top:0px;left:0px; }.text-div{margin-top: 80px; }.hjzgg-div{color:transparent;font-size:20px;font-weight: bold;letter-spacing:2px;-webkit-animatio…

linux終端常用快捷鍵

CTRLALTT 打開終端 CTRLD 關閉終端 CTRL SHIFT "" 放大終端字體 CTRL “-” 縮小終端字體 CTRL r 查找歷史命令 CTRLu 刪除光標前面所有內容 CTRLw 刪除光標左邊的單詞 CTRL k 刪除光標后面的所有內容 CTRLL 清除當前屏幕內容 CTRLa 光標移到開始位置 CTRLe 光標移到…

ueditor的配置和使用

ueditor下載好之后直接復制到項目的WebContent目錄下&#xff0c;并將ueditor\jsp\lib下的jar包復制或者剪切到項目的lib目錄下。先看一下效果&#xff0c;如下&#xff1a; 1.文件的上傳 首先在ueditor/jsp目錄下找到config.json文件&#xff0c;就拿Image上傳來說吧。 "…

windows上搭建NFS服務器

在進行嵌入式開發的時候&#xff0c;我們常用的做法是搭建NFS服務器&#xff0c;然后使把文件系統、調試程序放在NFS服務器上&#xff0c;這樣可以方便調試&#xff0c;以前都是在linux里面開啟NFS服務器&#xff0c;今天來說下window里的nfs服務器–haneWin 一、軟件安裝和使…

計算機是如何啟動的?從未上電到操作系統啟動

計算機是如何啟動的&#xff0c;網絡上很多博文1都從 BIOS 程序的加載開始說起&#xff0c;有的也跳到 BIOS 程序加載 Bootloader 階段。個人認為把這個過程稱為操作系統是如何被加載并啟動應該更加貼切一點。同時&#xff0c;也有計算機硬件大神的文章[1][5]詳細分析計算機加電…

Hibernate注解

前言&#xff1a; 最近正在學習Hibernate通過注解&#xff08;annotation&#xff09;來管理映射關系&#xff0c;以前都是通過XML映射文件。下面拿個小例子說一下。 數據庫物理模型&#xff1a; 數據庫的描述&#xff1a; 一篇博客隨筆可以分到不同的類中&#xff0c;一個類中…

js表單動態添加數據并提交

情景1&#xff1a;已經存在form對象了&#xff0c;動態為form增加對象并提交 function formAppendSubmit(){var myform$(#newArticleForm); //得到form對象var tmpInput$("<input typetext nameblogArticleForm.articleContent/>");tmpInput.attr("value&…

*++p和*p++的區別

首先你應該明白* 和 的優先級是相同的&#xff0c;而且他們的結合性是從又往左的 #include <stdio.h>int main(int argc ,char * argv[]) {int str[]{1,2,3,4,5,6,7,8,9,10};int *p str;int a *p;//a*p ,pp1即a1&#xff0c;p&str[1]int b *p;//pp1,b*p即p&s…

zyUpload+struct2完成文件上傳

前言&#xff1a; 最近在寫自己的博客網站&#xff0c;算是強化一下自己對s2sh框架的理解。期間遇到了很多問題&#xff0c;這些問題在寫之前都考慮過&#xff0c;感覺也就是那樣吧。但正真遇到了&#xff0c;也挺讓人難受的。就利用zyUpload這個js插件實現文件的上傳&#xff…

gbd的簡單使用(一)

這篇文章將gdb的簡單使用&#xff0c;通過此篇文章你能學習到使用gdb進行調試程序 在Linux中編寫程序時&#xff0c;如何進行程序的debug工作呢&#xff1f;今天來介紹下gdb這個工具&#xff0c;可以在Linux下直接man gdb查看幫助信息 &#xff08;一&#xff09;gdb命令介紹 …

java發送內嵌圖片郵件

前言&#xff1a; 博客系統中需要郵件服務的功能&#xff0c;以前寫過類似的功能&#xff0c;不過功能太簡單了&#xff0c;僅僅是發送文本內容&#xff0c;現在嘗試一下發送內嵌圖片郵件&#xff01; 準備工作&#xff1a; 請參考&#xff1a;http://www.cnblogs.com/hujunzhe…

調試跟蹤利器---strace

通過這篇文章你會學習到strace的用法&#xff0c;strace可以幫助你高效地定位進程中的一些錯誤&#xff0c;關于strace的用處有很多&#xff0c;可以自行發掘 前面我們講解了gdb調試程序,這篇文章介紹另一個調試跟蹤工具strace&#xff0c;同樣你可以在linux下執行man strace查…

MBR、DBR、FAT32基礎小知識

MBR-------主引導記錄 1.創建時間&#xff1a;由分區軟件&#xff08;Fdisk/PartitionMagic/Windows 2000/Windows XP安裝 工具等&#xff09;給 硬盤分區時建立的。 2.功能 &#xff1a;存放硬盤分區信息和引導系統時檢查分區。 3.作用范圍&#xff1a;MBR和虛擬MBR控制著整個…

java使用Executor(執行器)管理線程

一.一個實現了Runnable接口的類 class MyThread implements Runnable{private static int num 0;Overridepublic void run() {while(true){synchronized(MyThread.class){num;try{Thread.sleep(500);} catch(Exception e){System.out.println(e.toString());}System.out.print…

JMM和happens-before原則

JMM&#xff1a; Java Memory Model(Java內存模型)&#xff0c;圍繞著在并發過程中如何處理可見性、原子性、有序性這三個特性而建立的模型。 可見性&#xff1a; JMM提供了volatile變量定義、final、synchronized塊來保證可見性。  例如&#xff1a;線程a在將共享變量x1寫入…

SD卡移植FAT32文件系統無MBR

問題&#xff1a;在研究SD卡和FAT32文件系統的時候&#xff0c;發現SD卡有的有MBR&#xff0c;有的沒有MBR&#xff0c;這個為什么呢&#xff1f; 分析&#xff1a;MBR是主引導記錄&#xff0c;是在給磁盤分區的時候建立的&#xff0c;我們的SD卡沒有這個可能就是沒有進行過分區…

java獲取類的信息

關鍵技術剖析 1.java.lang.reflect包實現了java的反射機制&#xff0c;在使用反射機制時&#xff0c;需要導入該包。 2.Class類的forName方法能夠根據類名加載類&#xff0c;獲得類的Class對象。 Class類的getSuperclass方法獲得父類的Class對象&#xff1b;getDeclaredFields方…

FAT32文件系統介紹

FAT32文件系統&#xff08;一&#xff09;為什么要有文件系統&#xff08;二&#xff09;FAT32文件系統組成&#xff08;三&#xff09;分步介紹各部分(1) 首先介紹一下MBR(2)DBR介紹(3)FAT表介紹(4) 數據區&#xff08;一&#xff09;為什么要有文件系統 文件系統是操作系統用…