題目描述與示例

題目描述

疫情期間課堂的座位進行了特殊的調整，不能出現兩個同學緊挨著，必須隔至少一個空位。

給你一個整數數組 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. 種花問題幾乎完全一致。

代碼

Python

# 題目：2023B-座位調整
# 分值：100
# 作者：許老師-閉著眼睛學數理化
# 算法：貪心
# 代碼看不懂的地方，請直接在群上提問# 輸入的座位數組
lst = input().split(",")
# 能坐下的總人數
ans = 0# 遍歷數組，在遍歷過程中，采取貪心的思路，并不需要【每個位置】都去查看是否可以坐下
# 1、當前位置已經有人坐下，那么后一個位置明顯不能坐下，可以跳過去
# 2、當前位置沒有人坐下，需要考慮后面一個位置是否種花# 初始化座位索引為0
i = 0while 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 + 1ans += 1# 在 lst[i] 位置種花之后，i + 1 位置不需要去考慮了，因為它明顯不能種花，可以跳過去# 讓 i 執行加 2 操作i += 2# 5、當前位置沒有人坐下 lst[i] == "0"# 6、但是后一個位置已經有人坐下了，那么當前位置無法坐下# i + 1 位置已經坐下，不用再去訪問一遍# i + 2 位置考慮到 i + 1 位置已經有人坐下，所以也無法坐下，不用再去訪問# 讓 i 執行加 3 操作else:i += 3print(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(NlogN)。排序時間復雜度

空間復雜度：O(1)。僅需要用到若干常數變量。

相同問題不同描述

2023C-找座位

題目描述

在一個大型體育場內舉辦了一場大型活動，由于疫情防控的需要，要求每位觀眾的必須間隔至少一個空位才允許落座。現在給出一排觀眾座位分布圖，座位中存在已落座的觀眾，請計算出，在不移動現有觀眾座位的情況下，最多還能坐下多少名觀眾。

輸入描述

一個數組，用來標識某一排座位中，每個座位是否已經坐人。0 表示該座位沒有坐人，1 表示該座位已經坐人。 1<=數組長度<=10000

輸出描述

整數，在不移動現有觀眾座位的情況下，最多還能坐下多少名觀眾。

示例一

輸入

10001

輸出

1

示例二

輸入

0101

輸出

0

---

華為OD算法/大廠面試高頻題算法練習沖刺訓練

• 華為OD算法/大廠面試高頻題算法沖刺訓練目前開始常態化報名！目前已服務100+同學成功上岸！

• 課程講師為全網50w+粉絲編程博主@吳師兄學算法 以及小紅書頭部編程博主@閉著眼睛學數理化

• 每期人數維持在20人內，保證能夠最大限度地滿足到每一個同學的需求，達到和1v1同樣的學習效果！

• 60+天陪伴式學習，40+直播課時，300+動畫圖解視頻，300+LeetCode經典題，200+華為OD真題/大廠真題，還有簡歷修改、模擬面試、專屬HR對接將為你解鎖

• 可上全網獨家的歐弟OJ系統練習華子OD、大廠真題

• 可查看鏈接 大廠真題匯總 & OD真題匯總(持續更新)

• 綠色聊天軟件戳 od1336了解更多