我在确定"好日期"时遇到编码问题(更多描述如下)。
我解决了最初的问题,但卡在了后续问题上。我将我的问题和解决方案附在下面的原始问题中。提前感谢您的帮助。
原始问题:
YYYY/MM/DD 格式是由零填充的日期表示法 4 位数字年份、零填充的 2 位月份和零填充的 2 位数字日期, 用斜杠分隔。
一个好的日期有两个或更少的不同数字 年/月/日格式。
给定一个日期
S
YYYY/MM/DD 格式。打印第一个美好的一天不早于S
年,采用 YYYY/MM/DD 格式。S
在 2001 年 1 月 1 日至 2999 年 12 月 31 日(含)之间。
前任。
2022/01/01
给2022/02/02
,2999/12/31
给3000/03/03
.
跟进(卡住):
相反,查找最近的好日期;它可以更早或更晚 比
S
.
我的问题:
- 有没有更好的方法来解决原始问题?我使用了三重循环,所以...
- 我该如何解决后续问题?我只能想到找到所有好的日期并将它们与
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))
由于数据量较小,您可以考虑通过蛮力进行测试,它可以解决原始问题和后续问题。
从概念上讲,考虑要使用的数字并形成一组选择:
{0, 1, 2, ...9, 01, 02, 03 ..., 09, 12, 13 ...99 }
集合的大小很小:总共 10 个个位数选择 + 10C2 = 55 个选择。
我们可以使用这些选择形成所有可能的日期,并与给定的日期进行比较。
实现:
个位数是直截了当的,例如:0000/00/00、1111/11/11 .....
对于 2 位数字,例如 0 和 1,您可以简单地使用递归回溯来生成可能的日期,例如 0000/00/01、0000/01/10 ...等。
对于每个日期,检查日期是否为有效日期,并与输入进行比较以获得最接近的答案。
伪代码:
// Generate 2 digit choices by any means ~ O(10^2)
// Method 1: two for-loops
for(int i=0; i<10; i++) for(int j=i+1; j<10; j++) choices.add({i, j});
// Method 2: bitmask
for(int i=0; i<1024; i++)
if( i has exactly 2 one-bit in binary expression )
choices.add({the index of the one-bit });
// Backtracking ~ O(2^8)
void dfs(choice, date, len){
if(len == 8) {
check_if_valid_date(date);
compare_with_input_and_update_answer(date);
return;
}
date += choice_1st_digit;
dfs(choice, date, len+1);
date -= choice_1st_digit;
date += choice_2nd_digit;
dfs(choice, date, len+1);
}
for(all choice in choices){
dfs(choice, "", 0);
}
// Total Complexity ~ O(10^2 * 2^8) which is fast enough in every modern machines
回答コリン的评论: 想想你的"eval"解决方案必须做的工作:
- 连接 2 个字符串
- 在 eval() 中:
- 将字符串拆分为 3 个标记
- 检测它是整数除法
- 将 2 个数字转换为二进制(使用 int)
- 做整数除法
- 返回值
使用会更轻:
starting_year = int( s[0:4])
我提到"坏习惯"是因为在用户输入中使用 eval() 是危险的。例如,如果用户输入"1/(1-1)"作为日期,它将使您的程序崩溃。但他(她)甚至可能做得更糟。每次使用 input() 时,都应该对其进行清理,如果将输入发送到 eval(),这一点至关重要。
这是一个具有单级循环的解决方案.
它负责闰年和不规则days_per_month.
并且您可以轻松修改different_digits和end_date的数量。
from datetime import date, timedelta
def next_good_date( udate:date)->date:
day_duration = timedelta( days=1)
while True:
udate += day_duration
#udate_asc = f"{udate.year}{udate.month}{udate.day}" # use if leading zeros are non-significant
udate_asc = f"{udate.year:04}{udate.month:02}{udate.day:02}" # use if leading zeros are significant
if len( set( udate_asc)) <= 2:
return udate
if udate == date.fromisoformat( '3000-01-01'): return None
if __name__ == '__main__':
udate = date.fromisoformat( input( "date(yyyy/mm/dd)> ").replace('/','-')) # ISO use '-'
udate = next_good_date( udate)
if udate:
print( udate.strftime( "%Y/%m/%d"))
else:
print( "No answer")
指定日期范围内有 88 个good_date,最后一个是 2222/12/22
使用 'next_good_date()' 作为模型创建 'previous_good_date()' 很容易。