跳转至

4116. 下雨天安排伞

难度简单

题目描述

给你一个长度为 n 的 二进制数组 rain,其中 rain[i] == 1 表示第 i 天下雨,rain[i] == 0 表示第 i 天不下雨。

Alice 和 Bob 在这 n 天里共用 一把伞。在每一天 i:

  • 对于 0 <= i < n - 1,如果 rain[i] == rain[i + 1] == 1,则 Alice 在第 i 天需要伞。
  • 如果 rain[i] == 1,则 Bob 需要伞。
  • 他们之中 至多一人 可以得到伞。
  • 如果只有一个人需要伞,则由这个人得到伞。
  • 如果 两人 都需要伞,则伞归目前为止得到伞次数 较少 的人。如果次数 相同,则伞归 Alice。
  • 如果两人都不需要伞,则没有人得到伞。

一个人的计数只有在其得到伞的那一天才会 增加。初始时,两人的计数均为 0。

返回一个长度为 n 的字符串数组 answer,其中 answer[i] 为 "Alice"、"Bob" 或 "None",表示第 i 天得到伞的人。

二进制数组 是只包含 0 和 1 的数组。

 

示例 1:

输入: rain = [1,1,0,1,1]

输出: ["Alice","Bob","None","Alice","Bob"]

解释:

  • 第 0 天:rain[0] == 1 且 rain[1] == 1,所以两人都需要伞。计数相同,所以 Alice 得到伞。
  • 第 1 天:rain[1] == 1,所以 Bob 需要伞,但 rain[2] == 0,所以 Alice 不需要伞。因此 Bob 得到伞。
  • 第 2 天:没有下雨,所以没有人得到伞。
  • 第 3 天:rain[3] == 1 且 rain[4] == 1,所以两人都需要伞。计数均为 1,相同,所以 Alice 得到伞。
  • 第 4 天:最后一天,所以只有 Bob 需要伞,由他得到伞。
  • 因此,answer = ["Alice", "Bob", "None", "Alice", "Bob"]。

示例 2:

输入: rain = [0,1,0,1]

输出: ["None","Bob","None","Bob"]

解释:

  • 从未出现连续两天下雨的情况,所以 Alice 从不需要伞。
  • Bob 在第 1 天和第 3 天得到伞,第 0 天和第 2 天没有人得到伞。
  • 因此,answer = ["None", "Bob", "None", "Bob"]。

 

提示:

  • 1 <= n == rain.length <= 100
  • rain[i] 为 0 或 1。

解法

方法一:模拟

思考

\(n\) 不超过 \(100\),按天决定伞给谁即可。次数只在真正拿到伞时增加,两人同时需要时要比此前的次数,所以必须从左往右扫描。

Alice 需要伞,当且仅当当天和后一天都下雨。当天已经下雨,Bob 也一定需要,Alice 不会单独需要。

因此只维护已经拿到伞的次数 \(a\) 和 \(b\)。先用当前次数判断归属,再给拿到伞的人加一,后一天是否下雨决定 Alice 会不会进入这次比较。

我们用 \(a\) 和 \(b\) 分别记录 Alice 与 Bob 已经拿到伞的次数,初始都为 \(0\),并从左到右扫描 \(\textit{rain}\)。

第 \(i\) 天若 \(\textit{rain}[i]=0\),没有人需要伞,答案为 \(\text{None}\)。若 \(\textit{rain}[i]=1\),Bob 需要伞。当 \(i<n-1\) 且 \(\textit{rain}[i+1]=1\) 时 Alice 也需要伞;若此时 \(a\le b\),伞给 Alice, \(a\) 加一,否则伞给 Bob, \(b\) 加一。后一天不下雨,或当天已是最后一天时,只有 Bob 需要伞,同样记给 Bob。

时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def assignUmbrella(self, rain: list[int]) -> list[str]:
        n = len(rain)
        a = b = 0
        ans = [None] * n
        for i, x in enumerate(rain):
            if x == 0:
                ans[i] = "None"
            elif a <= b and i < n - 1 and rain[i + 1] == 1:
                ans[i] = "Alice"
                a += 1
            else:
                ans[i] = "Bob"
                b += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String[] assignUmbrella(int[] rain) {
        int n = rain.length;
        int a = 0, b = 0;
        String[] ans = new String[n];
        for (int i = 0; i < n; i++) {
            int x = rain[i];
            if (x == 0) {
                ans[i] = "None";
            } else if (a <= b && i < n - 1 && rain[i + 1] == 1) {
                ans[i] = "Alice";
                a++;
            } else {
                ans[i] = "Bob";
                b++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> assignUmbrella(vector<int>& rain) {
        int n = rain.size();
        int a = 0, b = 0;
        vector<string> ans(n);
        for (int i = 0; i < n; i++) {
            int x = rain[i];
            if (x == 0) {
                ans[i] = "None";
            } else if (a <= b && i < n - 1 && rain[i + 1] == 1) {
                ans[i] = "Alice";
                a++;
            } else {
                ans[i] = "Bob";
                b++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func assignUmbrella(rain []int) []string {
    n := len(rain)
    a, b := 0, 0
    ans := make([]string, n)
    for i, x := range rain {
        if x == 0 {
            ans[i] = "None"
        } else if a <= b && i < n-1 && rain[i+1] == 1 {
            ans[i] = "Alice"
            a++
        } else {
            ans[i] = "Bob"
            b++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function assignUmbrella(rain: number[]): string[] {
    const n = rain.length;
    let a = 0,
        b = 0;
    const ans: string[] = new Array(n);
    for (let i = 0; i < n; i++) {
        const x = rain[i];
        if (x === 0) {
            ans[i] = 'None';
        } else if (a <= b && i < n - 1 && rain[i + 1] === 1) {
            ans[i] = 'Alice';
            a++;
        } else {
            ans[i] = 'Bob';
            b++;
        }
    }
    return ans;
}

评论