题目描述与示例

题目描述

公司用一个字符串来表示员工的出勤信息:

absent：缺勤

late：迟到

leaveearly：早退

present：正常上班

现需根据员工出勤信息，判断本次是否能获得出勤奖，能获得出勤奖的条件如下：

• 缺勤不超过一次
• 没有连续的迟到/早退
• 任意连续7次考勤，缺勤/迟到/早退不超过3次

题目练习网址：https://www.algomooc.com/problem/P3255

输入描述

用户的考勤数据字符串，记录条数>=1;输入字符串长度<10000;不存在非法输入

如：

2
present
present absent present present leaveearly present absent

输出描述

根据考勤数据字符串，如果能得到考勤奖，输出"true"，否则输出"false"

对于输入示例的结果应为true false

示例

输入

2
present
present absent present present leaveearly present absent

输出

true false

解题思路

每个人的考勤都是独立的，所以可以构建一个check()函数来判断每一个人的情况，记录某一个特定的人是否可以获得全勤奖。

check()函数的构建包含如下步骤

• 判断是否存在1天以上的缺勤
• 判断任意连续的2天，是否均为迟到/早退
• 判断任意连续的7天，是否存在3天以上的迟到/早退/缺勤

这三个只要有一个条件成立，直接返回False，否则返回True。

整体而言，题目难度并不高，只是需要对每一个条件进行较为细致的分类讨论和处理。

另外要注意取哈希表的key的时候，字符串单词一定不要拼错。

缺勤数量的判断

缺勤天数的判断非常好做，用哈希表计数器Counter()即可完成。

def check(s):
    lst = s.split()
    
    cnt = Counter(lst)
    if cnt["absent"] > 1:
        return "false"
    
    pass

连续两天的判断

仅需遍历整个lst数组，考虑连续的两个元素lst[i]和lst[i+1]，查看是否均为早退/迟到即可。

def check(s):
    lst = s.split()
    
    pass

    n = len(lst)
    for i in range(n-1):
        if lst[i] in {"leaveearly", "late"} and lst[i+1] in {"leaveearly", "late"}:
            return "false"
            
    pass

连续七天的判断

这是这道题里面稍微有点难度的地方，显然我们需要考虑所有的长度为7的连续区间，统计其中早退/迟到/缺席的天数的和是否超过3。

很容易想到应该使用固定滑窗来实现。构建一个新的哈希表cnt_win，来表示窗口中各个元素出现的次数。

在滑窗过程中，仅需判断cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"]是否大于3即可。如果是，则可以直接返回"false"

def check(s):
    lst = s.split()
    
    pass

    # 第一个窗口
    cnt_win = Counter(lst[:7])
    if cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3:
        return "false"

    # 滑窗过程
    for right, info_right in enumerate(lst[7:], 7):
        cnt_win[info_right] += 1

        left = right-7
        info_left = lst[left]
        cnt_win[info_left] -= 1

        if cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3:
            return "false"

如果嫌判断cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3的写法太麻烦，还可以换一个角度来写，考虑正常上班的天数是否小于4天，即判断cnt_win["present"] < 4，这样也可以大大缩短代码量。

PS：由于在Python的切片比较灵活，当某个人的考勤总天数不足7天时，cnt_win = Counter(lst[:7])并不会产生越界报错。

但对于使用其他语言的同学来说，是需要考虑越界的，可以将遍历的右边界从7改为取7和n之间的较小值，这样就不会出现越界操作。

当n <= 7时，也自然不会进入后续的固定滑窗过程了。

HashMap<String, Integer> cnt_win = new HashMap<>();
for (int i = 0; i < Math.min(7, n); ++i) {
    cnt_win.put(lst[i], cnt_win.getOrDefault(lst[i], 0) + 1);
}
unordered_map<string, int> cnt_win;
for (int i = 0; i < min(7, n); ++i) {
    cnt_win[lst[i]]++;
}

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


from collections import Counter


# 检查某一个人是否可以拿全勤奖的函数check
def check(s):
    # 对s根据空格进行分割，得到数组lst
    lst = s.split()

    # 构建哈希表计数器，统计缺席次数
    cnt = Counter(lst)

    # 如果缺席次数超过1次，直接返回"false"
    if cnt["absent"] > 1:
        return "false"

    # 计算这个人的天数
    n = len(lst)
    # 遍历lst，考虑连续的两天
    for i in range(n-1):
        # 如果lst[i]和lst[i+1]均为迟到/早退，则直接返回"false"
        if lst[i] in {"leaveearly", "late"} and lst[i+1] in {"leaveearly", "late"}:
            return "false"

    # 固定滑窗过程：考虑任意连续的7天是否存在3天以上的迟到/早退/缺席
    # 考虑第一个窗口
    cnt_win = Counter(lst[:7])
    if cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3:
        return "false"

    # 滑窗过程
    for right, info_right in enumerate(lst[7:], 7):
        # A1
        cnt_win[info_right] += 1
        # A2
        left = right-7
        info_left = lst[left]
        cnt_win[info_left] -= 1
        # A3
        if cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3:
            return "false"

    # 如果经过上述判断，都没有退出函数返回"false"，则返回"true"
    return "true"


# 输入人数n
n = int(input())

# 构建答案列表
ans = list()
# 循环n次，输入每一个人的情况
for _ in range(n):
    s = input()
    res = check(s)
    ans.append(res)

# 输出结果
print(*ans)

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    // 检查某一个人是否可以拿全勤奖的函数check
    public static String check(String s) {
        // 对s根据空格进行分割，得到数组lst
        String[] lst = s.split(" ");

        // 构建哈希表计数器，统计缺席次数
        HashMap<String, Integer> cnt = new HashMap<>();
        for (String info : lst) {
            cnt.put(info, cnt.getOrDefault(info, 0) + 1);
        }

        // 如果缺席次数超过1次，直接返回"false"
        if (cnt.containsKey("absent") && cnt.get("absent") > 1) {
            return "false";
        }

        // 计算这个人的天数
        int n = lst.length;
        // 遍历lst，考虑连续的两天
        for (int i = 0; i < n - 1; ++i) {
            // 如果lst[i]和lst[i+1]均为迟到/早退，则直接返回"false"
            if ((lst[i].equals("leaveearly") || lst[i].equals("late")) &&
                    (lst[i + 1].equals("leaveearly") || lst[i + 1].equals("late"))) {
                return "false";
            }
        }

        // 固定滑窗过程：考虑任意连续的7天是否存在3天以上的迟到/早退/缺席
        // 考虑第一个窗口
        HashMap<String, Integer> cnt_win = new HashMap<>();
        // 需要总天数考虑不足7天的情况，所以取右区间为Math.min(7, n)
        for (int i = 0; i < Math.min(7, n); ++i) {
            cnt_win.put(lst[i], cnt_win.getOrDefault(lst[i], 0) + 1);
        }
        if (cnt_win.getOrDefault("leaveearly", 0) + cnt_win.getOrDefault("late", 0) + cnt_win.getOrDefault("absent", 0) > 3) {
            return "false";
        }

        // 滑窗过程
        for (int right = 7; right < n; ++right) {
            // A1
            cnt_win.put(lst[right], cnt_win.getOrDefault(lst[right], 0) + 1);
            // A2
            int left = right - 7;
            cnt_win.put(lst[left], cnt_win.getOrDefault(lst[left], 0) - 1);
            // A3
            if (cnt_win.getOrDefault("leaveearly", 0) + cnt_win.getOrDefault("late", 0) + cnt_win.getOrDefault("absent", 0) > 3) {
                return "false";
            }
        }

        // 如果经过上述判断，都没有退出函数返回"false"，则返回"true"
        return "true";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入人数n
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        // 构建答案列表
        ArrayList<String> ans = new ArrayList<>();
        // 循环n次，输入每一个人的情况
        for (int i = 0; i < n; ++i) {
            String s = scanner.nextLine();
            String res = check(s);
            ans.add(res);
        }

        // 输出结果
        for (String result : ans) {
            System.out.print(result + " ");
        }
        System.out.println();
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

// 检查某一个人是否可以拿全勤奖的函数check
string check(string s) {
    // 对s根据空格进行分割，得到数组lst
    vector<string> lst;
    string word = "";
    for (char ch : s) {
        if (ch == ' ') {
            lst.push_back(word);
            word = "";
        } else {
            word += ch;
        }
    }
    lst.push_back(word);

    // 构建哈希表计数器，统计缺席次数
    unordered_map<string, int> cnt;
    for (string info : lst) {
        cnt[info]++;
    }

    // 如果缺席次数超过1次，直接返回"false"
    if (cnt.find("absent") != cnt.end() && cnt["absent"] > 1) {
        return "false";
    }

    // 计算这个人的天数
    int n = lst.size();
    // 遍历lst，考虑连续的两天
    for (int i = 0; i < n - 1; ++i) {
        // 如果lst[i]和lst[i+1]均为迟到/早退，则直接返回"false"
        if ((lst[i] == "leaveearly" || lst[i] == "late") &&
            (lst[i + 1] == "leaveearly" || lst[i + 1] == "late")) {
            return "false";
        }
    }

    // 固定滑窗过程：考虑任意连续的7天是否存在3天以上的迟到/早退/缺席
    // 考虑第一个窗口
    unordered_map<string, int> cnt_win;
    // 需要总天数考虑不足7天的情况，所以取右区间为min(7, n)
    for (int i = 0; i < min(7, n); ++i) {
        cnt_win[lst[i]]++;
    }
    if (cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3) {
        return "false";
    }

    // 滑窗过程
    for (int right = 7; right < n; ++right) {
        // A1
        cnt_win[lst[right]]++;
        // A2
        int left = right - 7;
        cnt_win[lst[left]]--;
        // A3
        if (cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3) {
            return "false";
        }
    }

    // 如果经过上述判断，都没有退出函数返回"false"，则返回"true"
    return "true";
}

int main() {
    // 输入人数n
    int n;
    cin >> n;
    cin.ignore(); // 消耗换行符

    // 构建答案列表
    vector<string> ans;
    // 循环n次，输入每一个人的情况
    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s);
        string res = check(s);
        ans.push_back(res);
    }

    // 输出结果
    for (string result : ans) {
        cout << result << " ";
    }
    cout << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义常量
#define MAX_DAYS 1000
#define MAX_LEN 20

// 哈希表结构
typedef struct {
    char key[MAX_LEN];
    int value;
} HashEntry;

typedef struct {
    HashEntry entries[MAX_DAYS];
    int size;
} HashMap;

// 初始化哈希表
void initHashMap(HashMap *map) {
    map->size = 0;
}

// 在哈希表中查找键
int find(HashMap *map, const char *key) {
    for (int i = 0; i < map->size; ++i) {
        if (strcmp(map->entries[i].key, key) == 0) {
            return i;
        }
    }
    return -1;
}

// 插入或更新键值
void put(HashMap *map, const char *key, int value) {
    int idx = find(map, key);
    if (idx != -1) {
        map->entries[idx].value = value;
    } else {
        strcpy(map->entries[map->size].key, key);
        map->entries[map->size].value = value;
        map->size++;
    }
}

// 获取键对应的值
int get(HashMap *map, const char *key) {
    int idx = find(map, key);
    if (idx != -1) {
        return map->entries[idx].value;
    }
    return 0;
}

// 删除键
void removeKey(HashMap *map, const char *key) {
    int idx = find(map, key);
    if (idx != -1) {
        for (int i = idx; i < map->size - 1; ++i) {
            map->entries[i] = map->entries[i + 1];
        }
        map->size--;
    }
}

// 检查某一个人是否可以拿全勤奖的函数
const char *check(const char *s) {
    // 将字符串分割为单词数组
    char lst[MAX_DAYS][MAX_LEN];
    int lstSize = 0;

    char temp[MAX_LEN];
    int tempIdx = 0;

    for (int i = 0; s[i] != '\0'; ++i) {
        if (s[i] == ' ') {
            temp[tempIdx] = '\0';
            strcpy(lst[lstSize++], temp);
            tempIdx = 0;
        } else {
            temp[tempIdx++] = s[i];
        }
    }
    temp[tempIdx] = '\0';
    strcpy(lst[lstSize++], temp);

    // 统计缺席次数
    HashMap cnt;
    initHashMap(&cnt);

    for (int i = 0; i < lstSize; ++i) {
        put(&cnt, lst[i], get(&cnt, lst[i]) + 1);
    }

    // 如果缺席次数超过1次，直接返回 "false"
    if (get(&cnt, "absent") > 1) {
        return "false";
    }

    // 检查连续两天迟到或早退
    for (int i = 0; i < lstSize - 1; ++i) {
        if ((strcmp(lst[i], "leaveearly") == 0 || strcmp(lst[i], "late") == 0) &&
            (strcmp(lst[i + 1], "leaveearly") == 0 || strcmp(lst[i + 1], "late") == 0)) {
            return "false";
        }
    }

    // 固定滑窗检查 7 天内的迟到/早退/缺席
    HashMap cntWin;
    initHashMap(&cntWin);

    for (int i = 0; i < 7 && i < lstSize; ++i) {
        put(&cntWin, lst[i], get(&cntWin, lst[i]) + 1);
    }
    if (get(&cntWin, "leaveearly") + get(&cntWin, "late") + get(&cntWin, "absent") > 3) {
        return "false";
    }

    for (int right = 7; right < lstSize; ++right) {
        put(&cntWin, lst[right], get(&cntWin, lst[right]) + 1);

        const char *left = lst[right - 7];
        put(&cntWin, left, get(&cntWin, left) - 1);
        if (get(&cntWin, left) == 0) {
            removeKey(&cntWin, left);
        }

        if (get(&cntWin, "leaveearly") + get(&cntWin, "late") + get(&cntWin, "absent") > 3) {
            return "false";
        }
    }

    // 如果经过上述判断，都没有退出函数返回 "false"，则返回 "true"
    return "true";
}

int main() {
    // 输入人数
    int n;
    scanf("%d", &n);
    getchar(); // 清除换行符

    char ans[n][6];
    for (int i = 0; i < n; ++i) {
        char s[MAX_DAYS * MAX_LEN];
        fgets(s, sizeof(s), stdin);
        s[strcspn(s, "\n")] = '\0'; // 去掉换行符

        strcpy(ans[i], check(s));
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        printf("%s ", ans[i]);
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require("readline");

// 检查某一个人是否可以拿全勤奖的函数 check
function check(s) {
    // 对 s 根据空格进行分割，得到数组 lst
    const lst = s.split(" ");

    // 构建哈希表计数器，统计缺席次数
    const cnt = {};
    for (const status of lst) {
        cnt[status] = (cnt[status] || 0) + 1;
    }

    // 如果缺席次数超过 1 次，直接返回 "false"
    if ((cnt["absent"] || 0) > 1) {
        return "false";
    }

    // 计算这个人的天数
    const n = lst.length;
    // 遍历 lst，考虑连续的两天
    for (let i = 0; i < n - 1; i++) {
        // 如果 lst[i] 和 lst[i+1] 均为迟到/早退，则直接返回 "false"
        if (
            (lst[i] === "leaveearly" || lst[i] === "late") &&
            (lst[i + 1] === "leaveearly" || lst[i + 1] === "late")
        ) {
            return "false";
        }
    }

    // 固定滑窗过程：考虑任意连续的 7 天是否存在 3 天以上的迟到/早退/缺席
    const cntWin = {};
    for (let i = 0; i < 7 && i < n; i++) {
        cntWin[lst[i]] = (cntWin[lst[i]] || 0) + 1;
    }
    if (
        (cntWin["leaveearly"] || 0) +
            (cntWin["late"] || 0) +
            (cntWin["absent"] || 0) >
        3
    ) {
        return "false";
    }

    // 滑窗过程
    for (let right = 7; right < n; right++) {
        const infoRight = lst[right];
        cntWin[infoRight] = (cntWin[infoRight] || 0) + 1;

        const left = right - 7;
        const infoLeft = lst[left];
        cntWin[infoLeft] -= 1;
        if (cntWin[infoLeft] === 0) delete cntWin[infoLeft];

        if (
            (cntWin["leaveearly"] || 0) +
                (cntWin["late"] || 0) +
                (cntWin["absent"] || 0) >
            3
        ) {
            return "false";
        }
    }

    // 如果经过上述判断，都没有退出函数返回 "false"，则返回 "true"
    return "true";
}

// 读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
    input.push(line.trim());
}).on("close", () => {
    const n = parseInt(input[0]);
    const ans = [];
    for (let i = 1; i <= n; i++) {
        ans.push(check(input[i]));
    }
    console.log(ans.join(" "));
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strings"
)

// 检查某一个人是否可以拿全勤奖的函数 check
func check(s string) string {
        // 对 s 根据空格进行分割，得到数组 lst
        lst := strings.Split(s, " ")

        // 构建哈希表计数器，统计缺席次数
        cnt := make(map[string]int)
        for _, status := range lst {
                cnt[status]++
        }

        // 如果缺席次数超过 1 次，直接返回 "false"
        if cnt["absent"] > 1 {
                return "false"
        }

        // 计算这个人的天数
        n := len(lst)
        // 遍历 lst，考虑连续的两天
        for i := 0; i < n-1; i++ {
                // 如果 lst[i] 和 lst[i+1] 均为迟到/早退，则直接返回 "false"
                if (lst[i] == "leaveearly" || lst[i] == "late") &&
                        (lst[i+1] == "leaveearly" || lst[i+1] == "late") {
                        return "false"
                }
        }

        // 固定滑窗过程：考虑任意连续的 7 天是否存在 3 天以上的迟到/早退/缺席
        cntWin := make(map[string]int)
        for i := 0; i < 7 && i < n; i++ {
                cntWin[lst[i]]++
        }
        if cntWin["leaveearly"]+cntWin["late"]+cntWin["absent"] > 3 {
                return "false"
        }

        // 滑窗过程
        for right := 7; right < n; right++ {
                infoRight := lst[right]
                cntWin[infoRight]++

                left := right - 7
                infoLeft := lst[left]
                cntWin[infoLeft]--
                if cntWin[infoLeft] == 0 {
                        delete(cntWin, infoLeft)
                }

                if cntWin["leaveearly"]+cntWin["late"]+cntWin["absent"] > 3 {
                        return "false"
                }
        }

        // 如果经过上述判断，都没有退出函数返回 "false"，则返回 "true"
        return "true"
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        writer := bufio.NewWriter(os.Stdout)
        defer writer.Flush()

        // 输入人数 n
        var n int
        fmt.Fscanln(reader, &n)

        // 构建答案列表
        ans := make([]string, n)
        for i := 0; i < n; i++ {
                line, _ := reader.ReadString('\n')
                line = strings.TrimSpace(line)
                ans[i] = check(line)
        }

        // 输出结果
        fmt.Fprintln(writer, strings.Join(ans, " "))
}

时空复杂度

时间复杂度：O(NM)。M为每一个字符串数组的长度

空间复杂度：O(M)。