Swift - LeetCode - 學生出勤記錄 I

語言: CN / TW / HK

持續創作,加速成長!這是我參與「掘金日新計劃 · 10 月更文挑戰」的第30天,點選檢視活動詳情

題目

給你一個字串 s 表示一個學生的出勤記錄,其中的每個字元用來標記當天的出勤情況(缺勤、遲到、到場)。記錄中只含下面三種字元:

  • 'A':Absent,缺勤
  • 'L':Late,遲到
  • 'P':Present,到場

如果學生能夠 同時 滿足下面兩個條件,則可以獲得出勤獎勵:

  • 總出勤 計,學生缺勤('A'嚴格 少於兩天。
  • 學生 不會 存在 連續 3 天或 連續 3 天以上的遲到('L')記錄。

如果學生可以獲得出勤獎勵,返回 true;否則,返回 false

示例 1:

  • 輸入: s = "PPALLP"
  • 輸出: true
  • 解釋: 學生缺勤次數少於 2 次,且不存在 3 天或以上的連續遲到記錄。

示例 2:

  • 輸入: s = "PPALLL"
  • 輸出: false
  • 解釋: 學生最後三天連續遲到,所以不滿足出勤獎勵的條件。

方法一:一次遍歷

思路及解法

可獎勵的出勤記錄要求缺勤次數少於 2 和連續遲到次數少於 3。判斷出勤記錄是否可獎勵,只需要遍歷出勤記錄,判斷這兩個條件是否同時滿足即可。

遍歷過程中,記錄缺勤次數和連續遲到次數,根據遍歷到的字元更新缺勤次數和連續遲到次數:

  • 如果遇到 $\text{`A'}$,即缺勤,則將缺勤次數加 1,否則缺勤次數不變;

  • 如果遇到 $\text{`L'}$,即遲到,則將連續遲到次數加 1,否則將連續遲到次數清零。

如果在更新缺勤次數和連續遲到次數之後,出現缺勤次數大於或等於 2 或者連續遲到次數大於或等於 3,則該出勤記錄不滿足可獎勵的要求,返回 $\text{false}$。如果遍歷結束時未出現出勤記錄不滿足可獎勵的要求的情況,則返回 $\text{true}$。

程式碼

``` class Solution { func checkRecord(_ s: String) -> Bool { var absents: Int = 0 var lates: Int = 0 for ch: Character in s { if ch == "A" { absents += 1 if absents > 1 { return false } }

        if ch == "L" {
            lates += 1
            if lates > 2 {
                return false
            }
        } else {
            lates = 0
        }
    }
    return true
}

} ```

複雜度分析

  • 時間複雜度:$O(n)$,其中 $n$ 是字串 $s$ 的長度。需要遍歷字串 $s$ 一次。

  • 空間複雜度:$O(1)$。