Transform to Chessboard

Transform to Chessboard

問題

N*N矩陣由0和1組成,判斷是否能通過行與行或者列與列的交換,達到國際象棋棋盤的樣子(任意相鄰元素不同),如果能,求出最小交換步數(shù)

解決方案

  • 問題的分析和轉(zhuǎn)化
  • 算法的簡化

1.交換整行或整列的位置不會使相同的行和相同的列的數(shù)量減少
2.符合要求的矩陣有且僅有兩種不同的行(列)
3.通過0,1表示這兩種行(列),到達目標狀態(tài)所需的最小交換步驟,就是這個狀態(tài)序列與理想狀態(tài)序列的差異位數(shù)(相同的位不需要交換)
4.通過 xor 和 Integer.bitCount 可以高效地求出二進制上的差異位數(shù),除以2就是所需的最小交換步數(shù)

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 第一章 緒論 什么是數(shù)據(jù)結構? 數(shù)據(jù)結構的定義:數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。 第二章...
    SeanCheney閱讀 6,003評論 0 19
  • Spring Cloud為開發(fā)人員提供了快速構建分布式系統(tǒng)中一些常見模式的工具(例如配置管理,服務發(fā)現(xiàn),斷路器,智...
    卡卡羅2017閱讀 136,554評論 19 139
  • 第二章 選擇器 1、p.warning (沒有空格)其class屬性包含warning的p段落 區(qū)別于 p .wa...
    風色透明閱讀 489評論 0 1
  • 當居民在進行騷亂時 他們正反對著不公 為正義吶喊 響聲如轟雷一般 降臨在地面之上 我們正看著他們 遭受無情的對待 ...
    昆悠閱讀 310評論 0 5
  • 第14期第17篇 最近兩年買了好多書,不知不覺,書柜里已經(jīng)裝滿了書。還有些書,散落在房間各處。 有許多要讀而沒有讀...
    蘭若echo閱讀 253評論 0 0

友情鏈接更多精彩內(nèi)容