赞
踩
疫情期间课堂的座位进行了特殊的调整,不能出现两个同学紧挨着,必须隔至少一个空位。
给你一个整数数组 desk
表示当前座位的占座情况,由若干 0
和 1
组成,其中 0
表示没有占位,1
表示占位。在不改变原有座位秩序情况下,还能安排坐几个人?
第一行是个子数组表示作为占座情况,由若干 0
和 1
组成,其中 0
表示没有占位,1
表示占位
输出数值表示还能坐几个人
1 <= desk.length <= 2 * 10^4
1,0,0,0,1
1
0,0,0,0,0
3
只有 desk[2]
的位置可以坐一个人
注意,本题和LC605. 种花问题几乎完全一致。
# 题目:2023B-座位调整 # 分值:100 # 作者:许老师-闭着眼睛学数理化 # 算法:贪心 # 代码看不懂的地方,请直接在群上提问 # 输入的座位数组 lst = input().split(",") # 能坐下的总人数 ans = 0 # 遍历数组,在遍历过程中,采取贪心的思路,并不需要【每个位置】都去查看是否可以坐下 # 1、当前位置已经有人坐下,那么后一个位置明显不能坐下,可以跳过去 # 2、当前位置没有人坐下,需要考虑后面一个位置是否种花 # 初始化座位索引为0 i = 0 while i < len(lst): # 1、当前位置已经有人坐下,lst[i] == "1",那么后一个位置明显不能坐下,可以跳过去 # 所以让 i 执行加 2 操作,跳过了加 1 后的那个位置 if lst[i] == "1": # 让 i 执行加 2 操作 i += 2 # 2、否则说明当前位置没有人坐下 lst[i] == "0" else: # 3、如果这个位置【是】数组的最后一个位置,说明后一个位置不存在,没有限制,说明 lst[i] 可以坐下 # 4、如果这个位置【不是】数组的最后一个位置,那么只有当后一个位置【没人坐下】,才有资格在 lst[i] 位置坐下 # 这两种条件都可以在 lst[i] 位置坐下 if i == len(lst) - 1 or lst[i + 1] == "0": # 成功之后,坐下人数ans + 1 ans += 1 # 在 lst[i] 位置种花之后,i + 1 位置不需要去考虑了,因为它明显不能种花,可以跳过去 # 让 i 执行加 2 操作 i += 2 # 5、当前位置没有人坐下 lst[i] == "0" # 6、但是后一个位置已经有人坐下了,那么当前位置无法坐下 # i + 1 位置已经坐下,不用再去访问一遍 # i + 2 位置考虑到 i + 1 位置已经有人坐下,所以也无法坐下,不用再去访问 # 让 i 执行加 3 操作 else: i += 3 print(ans)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] lst = scanner.nextLine().split(","); int ans = 0; int i = 0; while (i < lst.length) { if (lst[i].equals("1")) { i += 2; } else { if (i == lst.length - 1 || lst[i + 1].equals("0")) { ans += 1; i += 2; } else { i += 3; } } } System.out.println(ans); } }
#include <iostream> #include <sstream> #include <vector> using namespace std; int main() { string line; getline(cin, line); istringstream iss(line); vector<string> lst; string val; while (getline(iss, val, ',')) { lst.push_back(val); } int ans = 0; int i = 0; while (i < lst.size()) { if (lst[i] == "1") { i += 2; } else { if (i == lst.size() - 1 || lst[i + 1] == "0") { ans += 1; i += 2; } else { i += 3; } } } cout << ans << endl; return 0; }
时间复杂度:O(NlogN)
。排序时间复杂度
空间复杂度:O(1)
。仅需要用到若干常数变量。
在一个大型体育场内举办了一场大型活动,由于疫情防控的需要,要求每位观众的必须间隔至少一个空位才允许落座。现在给出一排观众座位分布图,座位中存在已落座的观众,请计算出,在不移动现有观众座位的情况下,最多还能坐下多少名观众。
一个数组,用来标识某一排座位中,每个座位是否已经坐人。0
表示该座位没有坐人,1
表示该座位已经坐人。 1<=数组长度<=10000
整数,在不移动现有观众座位的情况下,最多还能坐下多少名观众。
10001
1
0101
0
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336
了解更多
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。