美文网首页leetcode articles
Transform to Chessboard

Transform to Chessboard

作者: gattonero | 来源:发表于2018-02-11 22:55 被阅读143次

Transform to Chessboard

问题

N*N矩阵由0和1组成,判断是否能通过行与行或者列与列的交换,达到国际象棋棋盘的样子(任意相邻元素不同),如果能,求出最小交换步数

解决方案

  • 问题的分析和转化
  • 算法的简化

1.交换整行或整列的位置不会使相同的行和相同的列的数量减少
2.符合要求的矩阵有且仅有两种不同的行(列)
3.通过0,1表示这两种行(列),到达目标状态所需的最小交换步骤,就是这个状态序列与理想状态序列的差异位数(相同的位不需要交换)
4.通过 xor 和 Integer.bitCount 可以高效地求出二进制上的差异位数,除以2就是所需的最小交换步数

相关文章

网友评论

    本文标题:Transform to Chessboard

    本文链接:https://www.haomeiwen.com/subject/rniltftx.html