题目描述与示例
题目描述
疫情期间课堂的座位进行了特殊的调整，不能出现两个同学紧挨着，必须隔至少一个空位。
给你一个整数数组 desk 表示当前座位的占座情况，由若干 0 和 1 组成，其中 0 表示没有占位，1 表示占位。在不改变原有座位秩序情况下，还能安排坐几个人？
输入
第一行是个子数组表示作为占座情况，由若干 0 和 1 组成，其中 0 表示没有占位，1 表示占位
输出
输出数值表示还能坐几个人
说明
1 <= desk.length <= 2 * 10^4
示例一
输入
1,0,0,0,1
输出
1
说明
只有 desk[2] 的位置可以坐一个人
示例二
输入
0,0,0,0,0
输出
3
解题思路
注意，本题和LC605. 种花问题几乎完全一致。
代码
Python
# 题目：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)
Java
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);
}
}
C++
#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(N)。仅需一次遍历数组
空间复杂度：O(1)。仅需要用到若干常数变量。
相同问题不同描述
2023C-找座位
题目描述
在一个大型体育场内举办了一场大型活动，由于疫情防控的需要，要求每位观众的必须间隔至少一个空位才允许落座。现在给出一排观众座位分布图，座位中存在已落座的观众，请计算出，在不移动现有观众座位的情况下，最多还能坐下多少名观众。
输入描述
一个数组，用来标识某一排座位中，每个座位是否已经坐人。0 表示该座位没有坐人，1 表示该座位已经坐人。 1<=数组长度<=10000
输出描述
整数，在不移动现有观众座位的情况下，最多还能坐下多少名观众。
示例一
输入
10001
输出
1
示例二
输入
0101
输出
0
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
