Transform to Chessboard

Transform to Chessboard

问题

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

解决方案

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

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

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 11,121评论 0 19
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 136,159评论 19 139
  • 第二章 选择器 1、p.warning (没有空格)其class属性包含warning的p段落 区别于 p .wa...
    风色透明阅读 3,258评论 0 1
  • 当居民在进行骚乱时 他们正反对着不公 为正义呐喊 响声如轰雷一般 降临在地面之上 我们正看着他们 遭受无情的对待 ...
    昆悠阅读 2,166评论 0 5
  • 第14期第17篇 最近两年买了好多书,不知不觉,书柜里已经装满了书。还有些书,散落在房间各处。 有许多要读而没有读...
    兰若echo阅读 1,603评论 0 0

友情链接更多精彩内容