Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP)

2023-12-26 06:45

本文主要是介绍Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
  • 思路
    • Java + 按行状压暴力 + DP:
    • 第 1 步:
    • 第 2 步:
    • 第 3 步:
    • 第 4 步:
  • 复杂度
  • Code

题目

  • Problem: 1349. 参加考试的最大学生数
  • 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的(不可用),就用 ‘#’ 表示;否则,用 ‘.’ 表示。
  • 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。
  • 学生必须坐在状况良好的座位上。
  • seats 只包含字符 ‘.’ 和’#’
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

思路

Java + 按行状压暴力 + DP:

第 1 步:

  • 首先思考每个好座位选或不选的 DFS 暴力求解,会超时
  • 其次分析题意可知,仅有相邻两行之间有限制,
  • 因此可以想到将行拆开,仅每一行去暴力所有可能,使用 DP 判断相邻两行的限制即可

第 2 步:

  • 每行暴力:
  • 每行遍历从 0 到 (2 ^ n) - 1 的数字 seat,seat 转化为二进制、1 代表有人,
  • isRowUsableSeat 行内满足要求:遍历每个 1 相邻左侧没有 1 且 每个 1 均是好座位,
  • 此 seat 代表该行内部满足条件,

第 3 步:

  • DP 判断两行的限制:
  • 定义状态:dp[i][seat] 代表前 i 行中,第 i 行座位为 seat 时的最大学生数
  • 初始化:dp[0][isRowUsableSeat(seat)] = countOne(seat)(seat 中 1 个个数),代表第一行没有限制
  • 状态转移方程:
    • dp[i][isRowUsableSeat(seat)] = countOne(seat) + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , … , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)
  • 其中 isCrossUsableSeat(seat1, seat2) 代表两行(seat1-上一行、seat2-下一行)是否满足要求,即 seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1

第 4 步:

  • 预处理所有 isCrossUsableSeat,
  • 由于 i 仅与 i-1 相关,因此使用滚动数组即可

复杂度

时间复杂度:

时间复杂度: O ( ( m + n ) ∗ 2 2 n ) O((m + n) * 2 ^ {2n}) O((m+n)22n)

空间复杂度:

空间复杂度: O ( n ∗ 2 2 n ) O(n * 2 ^ {2n}) O(n22n)

Code

class Solution {/*** Java + 按行状压暴力 + DP:** 第 1 步:* 首先思考每个好座位选或不选的 DFS 暴力求解,会超时* 其次分析题意可知,仅有相邻两行之间有限制,* 因此可以想到将行拆开,仅每一行去暴力所有可能,使用 DP 判断相邻两行的限制即可** 第 2 步:* 每行暴力:* 每行遍历从 0 到 (2 ^ n) - 1 的数字 seat,seat 转化为二进制、1 代表有人,* isRowUsableSeat 行内满足要求:遍历每个 1 相邻左侧没有 1 且 每个 1 均是好座位,* 此 seat 代表该行内部满足条件,** 第 3 步:* DP 判断两行的限制:* 定义状态:dp[i][seat] 代表前 i 行中,第 i 行座位为 seat 时的最大学生数* 初始化:dp[0][isRowUsableSeat(seat)] = countOne(seat)(seat 中 1 个个数),代表第一行没有限制* 状态转移方程:dp[i][isRowUsableSeat(seat)] = countOne(seat) * + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , ... , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)* 其中 isCrossUsableSeat(seat1, seat2) 代表两行(seat1-上一行、seat2-下一行)是否满足要求,即 seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1** 第 4 步:* 预处理所有 isCrossUsableSeat,* 由于 i 仅与 i-1 相关,因此使用滚动数组即可* 时间复杂度:O((m + n) * 2 ^ 2n),空间复杂度:O(n * 2 ^ 2n)**/public int maxStudents(char[][] seats) {int m = seats.length;int n = seats[0].length;int seatTotal = 1 << n;// 预处理所有 isCrossUsableSeatboolean[][] crossUsableSeat = preCrossUsableSeat(seatTotal);int[][] dp = new int[2][seatTotal];// 初始化for (int j = 0; j < seatTotal; j++) {// 第 0 行满足 isRowUsableSeatif (isRowUsableSeat(seats[0], j)) {dp[0][j] = countOne(j);}}// 状态转移方程:dp[i][isRowUsableSeat(seat)] = countOne(seat) // + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , ... , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)for (int i = 1; i < m; i++) {for (int j = 0; j < seatTotal; j++) {// 第 i 行内满足条件if (isRowUsableSeat(seats[i], j)) {int countOneJ = countOne(j);for (int k = 0; k < seatTotal; k++) {// 第 i 行与 i-1 行满足条件if (crossUsableSeat[j][k]) {dp[i & 1][j] = Math.max(dp[i & 1][j], dp[(i - 1) & 1][k] + countOneJ);}}}}}int res = 0;for (int j = 0; j < seatTotal; j++) {res = Math.max(res, dp[(m - 1) & 1][j]);}return res;}/*** 遍历每个 1:相邻左侧没有 1 且 每个 1 均是好座位*/private boolean isRowUsableSeat(char[] seats, int seat) {for (int i = 0; (1 << i) <= seat; i++) {if (((1 << i) & seat) > 0) {if (seats[i] == '#' || ((1 << i + 1) & seat) > 0) {return false;}}}return true;}/*** 预处理所有 isCrossUsableSeat,*/private boolean[][] preCrossUsableSeat(int seatTotal) {boolean[][] crossUsableSeat = new boolean[seatTotal][seatTotal];// seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1for (int seat1 = 0; seat1 < seatTotal; seat1++) {for (int seat2 = 0; seat2 < seatTotal; seat2++) {if (isCrossUsableSeat(seat1, seat2)) {crossUsableSeat[seat1][seat2] = true;}}}return crossUsableSeat;}private boolean isCrossUsableSeat(int seat1, int seat2) {for (int bitNum = (seat2 & -seat2); bitNum > 0; bitNum = (seat2 & -seat2)) {if ((bitNum != 1 && (seat1 & (bitNum >> 1)) > 0) || ((seat1 & (bitNum << 1)) > 0)) {return false;}seat2 -= bitNum;}return true;}/*** 二进制 1 的个数*/private int countOne(int seat) {int res = 0;while (seat > 0) {seat &= seat - 1;res++;}return res;}
}

这篇关于Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/538444

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ