問題
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ù)