当前位置: 面试刷题>> 最短休息日 (经典算法题500道)


题目描述补充

题目:最短休息日

假设你是一名公司员工,公司规定每周需要工作五天,休息两天。给定一个连续的工作日列表(从周一到周日,用数字1到7表示),你需要找出最短的连续休息日序列(即连续的两天休息日)。在大多数情况下,默认的休息日是周六(7)和周日(1),但公司可能会因为特殊原因调整这个规则。

输入

  • 一个数组 days,其中每个元素是一个长度为7的数组(或列表),表示一周中每天的安排。如果第 i 个元素为 true,则表示第 i 天(从1到7对应周一到周日)需要工作;如果为 false,则表示该天休息。

输出

  • 一个数组,包含最短连续休息日序列的起始和结束日期(按1到7表示)。如果有多个最短连续休息日序列长度相同,则返回任意一个。

注意

  • 如果不存在连续休息日,返回空数组或相应的表示。

示例

输入:

days = [
    [True, True, True, True, True, False, False],  # 周一到周五工作,周六周日休息
    [True, True, True, True, False, True, False],  # 假设某周调整了休息日
    [True, True, True, True, True, True, True]     # 假设某周全部需要工作
]

输出:

[6, 7]  # 第一个输入中,周六和周日是最短的连续休息日序列

PHP 示例代码

function findShortestRestDays($days) {
    $minLength = PHP_INT_MAX;
    $result = [];

    foreach ($days as $week) {
        $currentLength = 0;
        $start = 0;
        for ($i = 0; $i < 7; $i++) {
            if (!$week[$i]) { // 如果当前天休息
                if ($currentLength == 0) {
                    $start = $i + 1; // 转换为1-7的表示
                }
                $currentLength++;
            } else {
                if ($currentLength >= 2) { // 如果之前累积了至少2天休息
                    if ($currentLength < $minLength) {
                        $minLength = $currentLength;
                        $result = [$start, $start + $currentLength - 1];
                    }
                }
                $currentLength = 0;
            }
        }
        // 检查最后一周的情况
        if ($currentLength >= 2 && $currentLength < $minLength) {
            $result = [$start, $start + $currentLength - 1];
        }
    }

    return $minLength < PHP_INT_MAX ? $result : [];
}

// 示例输入
$days = [
    [true, true, true, true, true, false, false],
    [true, true, true, true, false, true, false],
    [true, true, true, true, true, true, true]
];

// 调用函数并打印结果
print_r(findShortestRestDays($days));

Python 示例代码

def find_shortest_rest_days(days):
    min_length = float('inf')
    result = []

    for week in days:
        current_length = 0
        start = 0
        for i, is_workday in enumerate(week, 1):
            if not is_workday:  # 如果当前天休息
                if current_length == 0:
                    start = i
                current_length += 1
            else:
                if current_length >= 2:  # 如果之前累积了至少2天休息
                    if current_length < min_length:
                        min_length = current_length
                        result = [start, start + current_length - 1]
                current_length = 0

        # 检查最后一周的情况
        if current_length >= 2 and current_length < min_length:
            result = [start, start + current_length - 1]

    return result if min_length < float('inf') else []

# 示例输入
days = [
    [True, True, True, True, True, False, False],
    [True, True, True, True, False, True, False],
    [True, True, True, True, True, True, True]
]

# 调用函数并打印结果
print(find_shortest_rest_days(days))

JavaScript 示例代码

function findShortestRestDays(days) {
    let minLength = Infinity;
    let result = [];

    days.forEach(week => {
        let currentLength = 0;
        let start = 0;
        for (let i = 0; i < 7; i++) {
            if (!week[i]) { // 如果当前天休息
                if (currentLength === 0) {
                    start = i + 1; // 转换为1-7的表示
                }
                currentLength++;
            } else {
                if (currentLength >= 2) { // 如果之前累积了至少2天休息
                    if (currentLength < minLength) {
                        minLength = currentLength;
                        result = [start, start + currentLength - 1];
                    }
                }
                currentLength = 0;
            }
        }

        // 检查最后一周的情况
        if (currentLength >= 2 && currentLength < minLength) {
            result = [start, start + currentLength - 1];
        }
    });

    return minLength < Infinity ? result : [];
}

// 示例输入
const days = [
    [true, true, true, true, true, false, false],
    [true, true, true, true, false, true, false],
    [true, true, true, true, true, true, true]
];

// 调用函数并打印结果
console.log(findShortestRestDays(days));

码小课:在码小课网站上,你可以找到更多关于算法和数据结构的详细讲解和实战练习,帮助你提升编程技能,掌握更多高效解决问题的方法。

推荐面试题