(C卷,100分)- 考勤信息（Java & JS & Python & C）

题目描述

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

• absent：缺勤
• late：迟到
• leaveearly：早退
• present：正常上班

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

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

输入描述

用户的考勤数据字符串

• 记录条数 >= 1；
• 输入字符串长度 < 10000；
• 不存在非法输入；

如：

2
present
present absent present present leaveearly present absent

输出描述

根据考勤数据字符串，如果能得到考勤奖，输出”true”；否则输出”false”，
对于输入示例的结果应为：

true false

用例

题目解析

本题需要注意下

没有连续的迟到/早退；

根据考友反馈，连续的迟到/早退，应该指：本次是迟到或早退，上次也是迟到或早退。

比如，本次是迟到，上次是早退，则也算是：连续的迟到/早退

本题主要难点在于如果统计”任意连续7次考勤“中的缺勤/迟到/早退次数。

这里我们可以使用滑动窗口，且滑窗窗口的长度最大为7

• 当滑窗右边界索引R < 7 时，则滑窗长度 = R + 1
• 当滑窗右边界索引R >= 7时，则滑窗长度 = 7，同时能推导出滑窗左边界索引L为 = R – 6

如下图所示

 我们只要计算出滑窗内部 present 次数，即可通过：

滑窗长度  – present次数 = 任意连续7次考勤中的缺勤/迟到/早退次数

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
void (async function () {
  const n = parseInt(await readline());
  const records = [];
 
  for (let i = 0; i < n; i++) {
    records.push((await readline()).split(" "));
  }
 
  getResult(records);
})();
 
function getResult(records) {
  for (let record of records) console.log(isAward(record));
}
 
function isAward(record) {
  // 总缺勤次数
  let absent = 0;
 
  // 滑窗内正常上班的次数
  let present = 0;
 
  // 记录前一次的考勤记录
  let preRecord = "";
 
  for (let i = 0; i < record.length; i++) {
    // 滑窗长度最大为7，如果超过7，则滑窗的左边界需要右移, 滑窗失去的部分record[i - 7]
    // 如果失去部分是present，则更新滑窗内present次数
    if (i >= 7) {
      if ("present" == record[i - 7]) present--;
    }
 
    // 当前的考勤记录
    const curRecord = record[i];
 
    switch (curRecord) {
      case "absent":
        // 缺勤不超过一次
        if (++absent > 1) return false;
        break;
      case "late":
      case "leaveearly":
        // 没有连续的迟到/早退
        if ("late" == preRecord || "leaveearly" == preRecord) return false;
        break;
      case "present":
        present++;
        break;
    }
 
    preRecord = curRecord;
 
    // 任意连续7次考勤，缺勤/迟到/早退不超过3次, 相当于判断： 滑窗长度 - present次数 <= 3
    const window_len = Math.min(i + 1, 7);
    if (window_len - present > 3) return false;
  }
 
  return true;
}

Java算法源码

import java.util.Scanner;

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

    int n = Integer.parseInt(sc.nextLine());

    String[][] records = new String[n][];
    for (int i = 0; i < n; i++) {
      records[i] = sc.nextLine().split(" ");
    }

    getResult(n, records);
  }

  public static void getResult(int n, String[][] records) {
    for (int i = 0; i < n; i++) {
      System.out.println(isAward(records[i]));
    }
  }

  public static boolean isAward(String[] record) {
    // 总缺勤次数
    int absent = 0;

    // 滑窗内正常上班的次数
    int present = 0;

    // 记录前一次的考勤记录
    String preRecord = "";

    for (int i = 0; i < record.length; i++) {
      if (i >= 7) {
        // 滑窗长度最大为7，如果超过7，则滑窗的左边界需要右移, 滑窗失去的部分record[i - 7]
        // 如果失去部分是present，则更新滑窗内present次数
        if ("present".equals(record[i - 7])) present--;
      }

      // 当前的考勤记录
      String curRecord = record[i];

      switch (curRecord) {
        case "absent":
          // 缺勤不超过一次
          if (++absent > 1) return false;
          break;
        case "late":
        case "leaveearly":
          // 没有连续的迟到/早退
          if ("late".equals(preRecord) || "leaveearly".equals(preRecord)) return false;
          break;
        case "present":
          present++;
          break;
      }

      preRecord = curRecord;

      // 任意连续7次考勤，缺勤/迟到/早退不超过3次, 相当于判断： 滑窗长度 - present次数 <= 3
      int window_len = Math.min(i + 1, 7); // 滑窗长度
      if (window_len - present > 3) return false;
    }

    return true;
  }
}

Python算法源码

# 输入获取
n = int(input())
records = [input().split() for _ in range(n)]


def isAward(record):
    # 总缺勤次数
    absent = 0

    #  滑窗内正常上班的次数
    present = 0

    late_leaveearly = ("late", "leaveearly")

    # 前一次的考勤记录
    preRecord = ""

    for i in range(len(record)):
        # 滑窗长度最大为7，如果超过7，则滑窗的左边界需要右移, 滑窗失去的部分record[i - 7]
        # 如果失去部分是present，则更新滑窗内present次数
        if i >= 7:
            if "present" == record[i-7]:
                present -= 1

        # 当前的考勤记录
        curRecord = record[i]

        if "absent" == curRecord:
            absent += 1
            # 缺勤超过1次，则拿不到全勤奖
            if absent > 1:
                return "false"
        elif curRecord in late_leaveearly and preRecord in late_leaveearly:
            # 连续的迟到/早退，则拿不到全勤奖
            return "false"
        elif "present" == curRecord:
            present += 1

        preRecord = curRecord

        # 任意连续7次考勤，缺勤/迟到/早退不超过3次, 相当于判断： 滑窗长度 - present次数 <= 3
        window_len = min(i+1, 7)  # 滑窗长度
        if window_len - present > 3:
            return "false"

    return "true"


# 算法入口
def getResult():
    for record in records:
        print(isAward(record))


# 算法调用
getResult()

C算法源码

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

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int isAward(char records[][15], int records_size);
int eq(char *a, char *b);

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        char records[10000][15];
        int records_size = 0;

        while(scanf("%s", records[records_size++])) {
            if(getchar() != ' ') break;
        }

        puts(isAward(records, records_size) ? "true" : "false");
    }

    return 0;
}

int isAward(char records[][15], int records_size) {
    // 总缺勤次数
    int absent = 0;

    // 滑窗内正常上班的次数
    int present = 0;

    // 记录前一次的考勤记录
    char *preRecord = "";

    for (int i = 0; i < records_size; i++) {
        // 滑窗长度最大为7，如果超过7，则滑窗的左边界需要右移, 滑窗失去的部分record[i - 7]
        // 如果失去部分是present，则更新滑窗内present次数
        if (i >= 7) {
            if(eq("present", records[i-7])) {
                present--;
            }
        }

        // 当前的考勤记录
        char *curRecord = records[i];

        if (eq(curRecord, "absent")) {
            // 缺勤不超过一次
            if (++absent > 1) return 0;
        } else if (eq(curRecord, "late") || eq(curRecord, "leaveearly")) {
            // 没有连续的迟到/早退
            if (eq(preRecord, "late") || eq(preRecord, "leaveearly")) return 0;
        } else if (eq(curRecord, "present")) {
            present++;
        }

        preRecord = curRecord;

        // 任意连续7次考勤，缺勤/迟到/早退不超过3次, 相当于判断： 滑窗长度 - present次数 <= 3
        int window_len = MIN(i + 1, 7);
        if (window_len - present > 3) return 0;
    }

    return 1;
}

int eq(char *a, char *b) {
    return strcmp(a, b) == 0 ? 1 : 0;
}