关于‘优质日期’判定的原问题优化及后续问题求解咨询

原问题描述 #

YYYY/MM/DD格式由补零的4位年份、补零的2位月份、补零的2位日期组成，以斜杠分隔。
“优质日期”指该格式中包含的不同数字不超过2个。
给定一个YYYY/MM/DD格式的日期S（范围：2001年1月1日至2999年12月31日），输出第一个不早于S的优质日期，格式为YYYY/MM/DD。
示例：

• 输入2022/01/01，输出2022/02/02
• 输入2999/12/31，输出3000/03/03

后续问题（当前困境） #

寻找与S最接近的优质日期，该日期可以早于或晚于S。

我的疑问 #

1. 有没有更优的方法解决原问题？我目前用的是三重循环...
2. 如何解决后续问题？我只能想到找出所有优质日期后与S逐一比较...

我的原问题解决方案 #

class Solution:
    @staticmethod
    def good_date(s: str) -> str:
        s = ''.join(s.split("/"))
        starting_year = eval(s + ' // 10000')

        for yyyy in range(starting_year, 3001):
            for mm in range(1, 13):
                for dd in range(1, 32):

                    date = str(yyyy) + f"{mm:02}" + f"{dd:02}"

                    if len(set(date)) == 2 and s <= date:
                        return date[:4] + "/" + date[4:6] + "/" + date[6:]


if __name__ == '__main__':
    S = input()
    print(Solution.good_date(S))

1. 原问题的优化方案 #

你的三重循环虽能解决问题，但效率偏低——会遍历大量无效日期（比如2月30日），做很多无用检查。更优思路是先生成所有合法的优质日期候选，排序后用二分查找快速定位目标，具体步骤：

• 枚举仅含1-2个不同数字的4位年份（年份是优质日期的核心组成）
• 对每个符合条件的年份，生成仅使用年份数字的合法月份（01-12）
• 对每个合法年月，生成仅使用年份数字的合法日期（需考虑平闰年、月份天数限制）
• 将所有有效优质日期排序，用二分查找找到第一个不早于S的日期

这种方法的候选量远少于三重循环的遍历量，且避免了无效日期的检查。另外你原代码中eval(s + ' // 10000')存在安全风险，换成int(s) // 10000更稳妥。

优化后的代码示例：

from datetime import datetime
import bisect

def is_valid_date(date_str):
    try:
        datetime.strptime(date_str, "%Y/%m/%d")
        return True
    except ValueError:
        return False

def generate_good_dates():
    good_dates = []
    # 生成2001-2999之间的优质日期
    for yyyy in range(2001, 3001):
        y_digits = set(str(yyyy))
        if len(y_digits) > 2:
            continue
        for mm in range(1, 13):
            mm_str = f"{mm:02}"
            if not set(mm_str).issubset(y_digits):
                continue
            for dd in range(1, 32):
                dd_str = f"{dd:02}"
                if not set(dd_str).issubset(y_digits):
                    continue
                date_str = f"{yyyy}/{mm_str}/{dd_str}"
                if is_valid_date(date_str):
                    good_dates.append(date_str)
    # 补充2999之后的第一个优质日期（比如3000/03/03）
    yyyy = 3000
    while True:
        y_digits = set(str(yyyy))
        if len(y_digits) <= 2:
            for mm in range(1, 13):
                mm_str = f"{mm:02}"
                if set(mm_str).issubset(y_digits):
                    for dd in range(1, 32):
                        dd_str = f"{dd:02}"
                        if set(dd_str).issubset(y_digits):
                            date_str = f"{yyyy}/{mm_str}/{dd_str}"
                            if is_valid_date(date_str):
                                good_dates.append(date_str)
                                break
                    else:
                        continue
                    break
        yyyy += 1
        if yyyy > 3100:
            break
    good_dates.sort()
    return good_dates

# 预生成所有优质日期（仅需执行一次）
all_good_dates = generate_good_dates()

def find_next_good_date(s):
    idx = bisect.bisect_left(all_good_dates, s)
    return all_good_dates[idx]

if __name__ == '__main__':
    S = input().strip()
    print(find_next_good_date(S))

2. 后续问题的解决方案 #

要找最接近的优质日期，基于预生成的排序后优质日期列表，步骤如下：

1. 将输入日期S转换为可计算差值的格式（比如转换为距固定日期的天数）
2. 用二分查找找到S在列表中的插入位置idx
3. 对比插入位置前后的候选日期（如果存在），计算与S的天数差，选择差值最小的；若差值相同，可按需求选择更早或更晚的日期

代码示例（基于上面预生成的all_good_dates）：

def date_to_days(date_str):
    dt = datetime.strptime(date_str, "%Y/%m/%d")
    return (dt - datetime(2000, 1, 1)).days

def find_closest_good_date(s):
    s_days = date_to_days(s)
    idx = bisect.bisect_left(all_good_dates, s)
    candidates = []
    if idx < len(all_good_dates):
        candidates.append(all_good_dates[idx])
    if idx > 0:
        candidates.append(all_good_dates[idx-1])
    
    # 找差值最小的日期
    closest = min(candidates, key=lambda d: abs(date_to_days(d) - s_days))
    # 差值相同时选更早的日期
    if len(candidates) == 2 and abs(date_to_days(candidates[0])-s_days) == abs(date_to_days(candidates[1])-s_days):
        return min(candidates)
    return closest

if __name__ == '__main__':
    S = input().strip()
    print(find_closest_good_date(S))

补充说明 #

符合条件的优质日期总数仅几百个，预生成的开销极小，这种方法既高效又易维护，比逐个遍历靠谱得多。

内容的提问来源于stack exchange，提问作者KORIN