1. 從星座與癌癥的邊界說起這道題到底在算什么第一次看到Cancer or Scorpio這個(gè)標(biāo)題很多人會(huì)愣一下——癌癥還是天蝎座這倆有什么關(guān)系其實(shí)這正是題目命名的巧妙之處。在西方占星學(xué)里Cancer巨蟹座和Scorpio天蝎座都是黃道十二宮里的星座名稱而Cancer這個(gè)詞在醫(yī)學(xué)語境下又指癌癥。題目用這個(gè)雙關(guān)暗示了核心任務(wù)給定一個(gè)受孕日期推算預(yù)產(chǎn)期然后判斷寶寶出生時(shí)對應(yīng)的星座是巨蟹還是天蝎或者別的什么座。這道題來自在線評測平臺編號11947。它的本質(zhì)是一道日期計(jì)算題但包裝得很有意思。你需要處理的核心邏輯鏈條是這樣的輸入一個(gè)受孕日期格式通常是MMDDYYYY或者類似的加上280天的妊娠期得到預(yù)產(chǎn)期再根據(jù)預(yù)產(chǎn)期落在哪個(gè)日期區(qū)間來判斷星座。聽起來簡單但里面藏著不少日期處理的坑比如閏年、月份天數(shù)、跨年計(jì)算以及星座邊界的精確判定。為什么值得單獨(dú)寫一篇因?yàn)槿掌谟?jì)算是編程里最容易被低估的領(lǐng)域。很多人覺得不就是加減天數(shù)嗎結(jié)果一提交就WAWrong Answer。我見過太多人在閏年2月29日、跨世紀(jì)年份、星座分界日這些地方翻車。這道題恰好把這些坑都串起來了是一個(gè)非常好的練習(xí)樣本。這篇文章適合誰如果你正在刷算法題尤其是日期模擬類題目這篇能幫你建立一套可靠的日期處理框架。如果你只是好奇星座計(jì)算背后的邏輯也能從中看到工程化思維如何把一個(gè)看似簡單的問題拆解清楚。我會(huì)從題目理解、核心算法、邊界處理、代碼實(shí)現(xiàn)到測試驗(yàn)證一步步拆開講并且補(bǔ)充很多官方題解不會(huì)告訴你的實(shí)操細(xì)節(jié)。2. 妊娠期280天背后的醫(yī)學(xué)常識與計(jì)算模型2.1 為什么是280天而不是300天題目里默認(rèn)的妊娠期是280天這個(gè)數(shù)字不是隨便定的。醫(yī)學(xué)上人類的平均妊娠周期大約是40周也就是280天從末次月經(jīng)第一天開始計(jì)算。注意這里有個(gè)容易混淆的點(diǎn)受孕日期和末次月經(jīng)日期是兩回事。受孕通常發(fā)生在末次月經(jīng)后約14天所以如果從受孕日算起實(shí)際妊娠期大約是266天。但題目明確說了是受孕日期加280天那我們就按題目來不要自作聰明去減14天。這個(gè)細(xì)節(jié)很重要因?yàn)楹芏嗳嗽谧瞿M題時(shí)會(huì)帶入現(xiàn)實(shí)世界的醫(yī)學(xué)知識結(jié)果反而算錯(cuò)。題目說什么就是什么這是做算法題的第一原則。我當(dāng)初做這道題的時(shí)候第一反應(yīng)也是280天不是從末次月經(jīng)算的嗎差點(diǎn)去調(diào)整。后來仔細(xì)讀題發(fā)現(xiàn)題目已經(jīng)簡化了模型直接給定受孕日期加280天那就老老實(shí)實(shí)加。2.2 日期加法的核心邏輯拆解日期加法的本質(zhì)是把日期轉(zhuǎn)換成從某個(gè)基準(zhǔn)點(diǎn)開始的總天數(shù)加上偏移量再轉(zhuǎn)換回日期。這個(gè)思路比逐月逐日去加要可靠得多。具體來說先把輸入日期轉(zhuǎn)換成從公元1年1月1日到該日的總天數(shù)或者用儒略日數(shù)加上280再把總天數(shù)轉(zhuǎn)換回年-月-日格式這樣做的好處是避免了手動(dòng)處理每個(gè)月多少天、閏年怎么算的麻煩。你只需要寫兩個(gè)函數(shù)一個(gè)把日期轉(zhuǎn)成天數(shù)一個(gè)把天數(shù)轉(zhuǎn)成日期。這兩個(gè)函數(shù)寫對了整個(gè)問題就解決了一大半。但這里有個(gè)陷阱轉(zhuǎn)換的基準(zhǔn)點(diǎn)選擇。如果你用公元1年1月1日作為基準(zhǔn)需要處理公元1年之前的情況嗎不需要因?yàn)轭}目給的日期都是現(xiàn)代日期。但你需要確保閏年規(guī)則正確能被4整除但不能被100整除的年份是閏年能被400整除的年份也是閏年。這個(gè)規(guī)則在跨世紀(jì)的時(shí)候特別容易出錯(cuò)比如1900年不是閏年2000年是閏年。2.3 星座日期區(qū)間的精確劃分星座的日期劃分是固定的但不同來源可能有細(xì)微差異。常見的劃分如下星座英文名起始日期結(jié)束日期摩羯座Capricorn12月22日1月19日水瓶座Aquarius1月20日2月18日雙魚座Pisces2月19日3月20日白羊座Aries3月21日4月19日金牛座Taurus4月20日5月20日雙子座Gemini5月21日6月21日巨蟹座Cancer6月22日7月22日獅子座Leo7月23日8月22日處女座Virgo8月23日9月22日天秤座Libra9月23日10月23日天蝎座Scorpio10月24日11月22日射手座Sagittarius11月23日12月21日題目標(biāo)題提到Cancer和Scorpio但實(shí)際輸出可能需要判斷所有星座。你需要把預(yù)產(chǎn)期的月和日拿出來對照這個(gè)表。注意邊界日期的處理比如6月22日到底是巨蟹還是雙子按照上表6月22日是巨蟹座的開始所以應(yīng)該輸出Cancer。這種邊界一定要嚴(yán)格按題目給定的規(guī)則來如果題目沒有明確就按最常見的劃分。3. 閏年與跨年日期計(jì)算里最容易翻車的兩個(gè)地方3.1 閏年判斷的完整邏輯與常見錯(cuò)誤閏年判斷看起來簡單但寫錯(cuò)的人非常多。我見過有人寫成year % 4 0就完事了結(jié)果1900年這種整百年份就錯(cuò)了。正確的邏輯是def is_leap(year): if year % 400 0: return True if year % 100 0: return False if year % 4 0: return True return False或者更簡潔的寫法def is_leap(year): return year % 400 0 or (year % 4 0 and year % 100 ! 0)為什么要有% 100 ! 0這個(gè)條件因?yàn)榈厍蚶@太陽一圈的實(shí)際時(shí)間不是精確的365.25天而是約365.2422天。如果每4年加一天400年下來會(huì)多加3天左右。所以規(guī)則規(guī)定整百年份必須是400的倍數(shù)才是閏年這樣400年里有97個(gè)閏年平均每年365.2425天更接近實(shí)際值。在日期加法中閏年影響的是2月的天數(shù)。如果你用逐月加的方式必須根據(jù)年份判斷2月是28天還是29天。但如果你用總天數(shù)轉(zhuǎn)換的方式閏年規(guī)則只需要在轉(zhuǎn)換函數(shù)里寫一次更不容易出錯(cuò)。3.2 跨年計(jì)算的陷阱從12月到次年1月當(dāng)受孕日期在年末加上280天后很可能跨到第二年甚至第三年。比如輸入12月31日加280天大約是次年10月初。跨年本身不難難的是跨年時(shí)閏年判斷要用哪一年的答案是每個(gè)年份單獨(dú)判斷。你在把總天數(shù)轉(zhuǎn)換回日期時(shí)會(huì)逐年減去該年的天數(shù)365或366所以每減一年都要用那一年的閏年?duì)顟B(tài)。我踩過的一個(gè)坑是在寫轉(zhuǎn)換函數(shù)時(shí)先算出一個(gè)平均年天數(shù)來估算年份結(jié)果在閏年附近偏差一天。正確做法是老老實(shí)實(shí)循環(huán)減或者用更精確的數(shù)學(xué)公式。對于這道題的數(shù)據(jù)規(guī)模循環(huán)減完全夠用不需要優(yōu)化。另一個(gè)坑是輸入格式。題目可能給的日期格式是MMDDYYYY比如01012000表示2000年1月1日。你需要正確解析出月、日、年。有些題目會(huì)給1 1 2000這種帶空格的格式要看清楚。解析錯(cuò)了后面全錯(cuò)。3.3 日期轉(zhuǎn)換的兩種實(shí)現(xiàn)方案對比實(shí)現(xiàn)日期加法有兩種主流方案方案一逐月逐日累加從受孕日期開始一天一天往后加每加一天檢查是否超過當(dāng)月天數(shù)超過就進(jìn)入下個(gè)月。這種方案直觀但效率低280天要循環(huán)280次。對于單組數(shù)據(jù)沒問題但如果題目有多組測試數(shù)據(jù)可能會(huì)慢。方案二總天數(shù)轉(zhuǎn)換先把日期轉(zhuǎn)成從基準(zhǔn)點(diǎn)開始的總天數(shù)加280再轉(zhuǎn)回日期。這種方案效率高邏輯清晰推薦使用。轉(zhuǎn)換函數(shù)只需要處理一次閏年規(guī)則。對比項(xiàng)逐月逐日累加總天數(shù)轉(zhuǎn)換代碼復(fù)雜度低中執(zhí)行效率低O(n)高O(1)閏年處理每次都要判斷集中處理出錯(cuò)概率高邊界多低推薦度不推薦強(qiáng)烈推薦我個(gè)人的經(jīng)驗(yàn)是只要涉及日期加減一律用總天數(shù)轉(zhuǎn)換。這套方法在各類日期題里都通用寫一次可以復(fù)用很久。4. 從輸入到輸出完整代碼實(shí)現(xiàn)與逐行解析4.1 輸入解析與數(shù)據(jù)預(yù)處理假設(shè)輸入格式是每行一個(gè)日期格式為MMDDYYYY比如01012000。第一行可能是測試用例數(shù)量T。我們需要讀取T然后循環(huán)處理每個(gè)日期。import sys def parse_date(s): # s format: MMDDYYYY month int(s[0:2]) day int(s[2:4]) year int(s[4:8]) return year, month, day注意這里用字符串切片而不是split因?yàn)槿掌谑沁B續(xù)數(shù)字。如果輸入是1 1 2000這種就要用split?？搭}目具體格式。4.2 日期轉(zhuǎn)總天數(shù)的實(shí)現(xiàn)細(xì)節(jié)選擇一個(gè)基準(zhǔn)點(diǎn)比如公元1年1月1日。計(jì)算從基準(zhǔn)點(diǎn)到給定日期的天數(shù)def date_to_days(year, month, day): days 0 # 累加整年的天數(shù) for y in range(1, year): days 366 if is_leap(y) else 365 # 累加當(dāng)年整月的天數(shù) month_days [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] for m in range(1, month): days month_days[m-1] if m 2 and is_leap(year): days 1 # 加上當(dāng)月天數(shù) days day return days這個(gè)函數(shù)的時(shí)間復(fù)雜度是O(year)對于年份不大的情況沒問題。如果年份很大比如幾百萬年需要優(yōu)化但算法題通常不會(huì)給那么大的年份。4.3 總天數(shù)轉(zhuǎn)日期的逆向操作def days_to_date(days): year 1 while True: year_days 366 if is_leap(year) else 365 if days year_days: break days - year_days year 1 month_days [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] month 1 while True: md month_days[month-1] if month 2 and is_leap(year): md 1 if days md: break days - md month 1 day days return year, month, day注意這里的邊界days year_days而不是因?yàn)閐ays是從1開始計(jì)數(shù)的。如果days等于year_days說明是這一年的最后一天應(yīng)該留在這一年。4.4 星座判斷的查表實(shí)現(xiàn)把星座區(qū)間存成一個(gè)列表然后遍歷判斷zodiacs [ (Capricorn, 12, 22, 1, 19), (Aquarius, 1, 20, 2, 18), (Pisces, 2, 19, 3, 20), (Aries, 3, 21, 4, 19), (Taurus, 4, 20, 5, 20), (Gemini, 5, 21, 6, 21), (Cancer, 6, 22, 7, 22), (Leo, 7, 23, 8, 22), (Virgo, 8, 23, 9, 22), (Libra, 9, 23, 10, 23), (Scorpio, 10, 24, 11, 22), (Sagittarius, 11, 23, 12, 21), ] def get_zodiac(month, day): for name, sm, sd, em, ed in zodiacs: if sm em: if (month sm and day sd) or (month em and day ed) or (sm month em): return name else: # 跨年星座如摩羯座 if (month sm and day sd) or (month em and day ed) or (month sm or month em): return name return Unknown摩羯座是跨年的從12月22日到1月19日需要特殊處理。其他星座都是同年內(nèi)的。5. 測試用例設(shè)計(jì)怎么驗(yàn)證你的代碼真的對了5.1 基礎(chǔ)功能測試先測最簡單的輸入一個(gè)日期加280天看結(jié)果對不對。比如輸入010120002000年1月1日加280天是2000年10月7日。2000年是閏年2月有29天。手動(dòng)算一下1月剩30天2月29天3月31天4月30天5月31天6月30天7月31天8月31天9月30天到9月底是302931303130313130273天還差7天所以是10月7日。代碼應(yīng)該輸出這個(gè)日期然后判斷星座是天秤座9月23日到10月23日。5.2 邊界測試閏年2月29日輸入022919961996年2月29日1996是閏年加280天。1996年2月29日之后3月31天4月30天5月31天6月30天7月31天8月31天9月30天10月31天11月30天到11月底是1313031303131303130276天還差4天所以是12月4日。星座是射手座。5.3 跨年測試12月31日加280天輸入12311999加280天。2000年是閏年所以2000年有366天。從1999年12月31日加1天是2000年1月1日再加279天。2000年1月到9月是312931303130313130274天還差5天所以是10月6日。星座是天秤座。5.4 星座邊界測試測試每個(gè)星座的起始日和結(jié)束日確保判斷正確。比如6月22日應(yīng)該是巨蟹座6月21日應(yīng)該是雙子座。10月24日是天蝎座10月23日是天秤座。這些邊界日期一定要測因?yàn)樽钊菀壮鲥e(cuò)。我建議寫一個(gè)測試腳本把所有邊界日期都跑一遍對比預(yù)期結(jié)果。這樣能快速發(fā)現(xiàn)邏輯錯(cuò)誤。6. 那些年我踩過的日期計(jì)算坑6.1 閏年規(guī)則記反了有一次我把閏年規(guī)則寫成了year % 4 0 and year % 100 ! 0 or year % 400 0運(yùn)算符優(yōu)先級搞錯(cuò)了結(jié)果1900年變成了閏年。正確的寫法要加括號或者用if-else結(jié)構(gòu)。這種錯(cuò)誤很隱蔽因?yàn)榇蟛糠帜攴荻际菍Φ闹挥姓倌攴莶疟┞丁?.2 月份天數(shù)數(shù)組下標(biāo)越界月份從1開始但數(shù)組下標(biāo)從0開始。我見過有人寫month_days[month]當(dāng)month12時(shí)就越界了。正確是month_days[month-1]。這種錯(cuò)誤在測試數(shù)據(jù)少的時(shí)候不容易發(fā)現(xiàn)一旦遇到12月就崩。6.3 跨年星座判斷遺漏摩羯座是唯一跨年的星座從12月22日到次年1月19日。如果只判斷sm month em摩羯座永遠(yuǎn)匹配不上。必須單獨(dú)處理跨年情況。我當(dāng)初就是漏了這個(gè)導(dǎo)致12月底和1月初的日期判斷錯(cuò)誤。6.4 輸入格式解析錯(cuò)誤有些題目給的日期格式是MMDDYYYY有些是YYYYMMDD還有些是MM/DD/YYYY。一定要仔細(xì)讀題確認(rèn)格式。我因?yàn)榭村e(cuò)格式把月份和年份搞反了調(diào)了半天才發(fā)現(xiàn)。6.5 輸出格式要求嚴(yán)格題目可能要求輸出Case #1: October 7, 2000, Libra這種格式月份要英文全稱星座要英文名。如果你輸出數(shù)字月份或者中文星座就會(huì)WA。這種格式錯(cuò)誤最冤但最容易避免——仔細(xì)看樣例輸出。7. 從這道題延伸出的通用日期處理框架7.1 封裝一個(gè)可復(fù)用的日期類如果你經(jīng)常做日期題建議封裝一個(gè)Date類包含以下方法from_string(s, format)解析字符串to_days()轉(zhuǎn)總天數(shù)from_days(days)從總天數(shù)構(gòu)造add_days(n)加n天__str__()格式化輸出這樣以后遇到日期題直接調(diào)用就行不用每次重寫。7.2 處理時(shí)區(qū)和夏令時(shí)的注意事項(xiàng)雖然這道題不涉及但實(shí)際工程中日期計(jì)算要考慮時(shí)區(qū)和夏令時(shí)。比如某些國家在夏季會(huì)把時(shí)鐘撥快一小時(shí)導(dǎo)致某一天只有23小時(shí)。如果按天加結(jié)果會(huì)偏。處理方法是使用UTC時(shí)間或者專門的日期庫。算法題通常簡化了這些但知道有這些坑對寫實(shí)際項(xiàng)目有幫助。7.3 性能優(yōu)化大年份范圍的快速計(jì)算如果年份范圍很大比如到100000年逐月累加會(huì)超時(shí)。這時(shí)可以用公式法先算出從基準(zhǔn)年到目標(biāo)年的總天數(shù)用365 * (year-1) leap_count其中l(wèi)eap_count是閏年數(shù)量可以用(year-1)//4 - (year-1)//100 (year-1)//400快速算。這樣O(1)就能得到年數(shù)對應(yīng)的天數(shù)。月份和日期部分再單獨(dú)處理。這個(gè)優(yōu)化在競賽中很有用但日常刷題不一定需要。知道有這個(gè)方法就行需要的時(shí)候再查。8. 寫在最后日期計(jì)算的心法做了這么多日期題我最大的體會(huì)是不要相信自己的心算要相信代碼。人腦處理閏年、跨月、跨年很容易出錯(cuò)但代碼只要邏輯寫對了就永遠(yuǎn)可靠。所以每次寫完日期處理代碼一定要用邊界數(shù)據(jù)測試不要憑感覺覺得應(yīng)該對了。另外日期題的輸入輸出格式往往很嚴(yán)格多一個(gè)空格、少一個(gè)逗號都可能WA。建議先把樣例輸入輸出復(fù)制下來逐字符對比。我習(xí)慣把樣例輸出存成文件然后用diff命令對比自己的輸出這樣能快速發(fā)現(xiàn)格式問題。最后這道題雖然叫Cancer or Scorpio但實(shí)際要判斷所有星座。不要被標(biāo)題誤導(dǎo)以為只需要判斷兩個(gè)星座。讀題要仔細(xì)這是所有算法題的通則。