復(fù)盤(pán)|第87場(chǎng)雙周賽
2409. 統(tǒng)計(jì)共同度過(guò)的日子數(shù)?https://leetcode.cn/problems/count-days-spent-together/
【模擬】把字符串日期轉(zhuǎn)換成這一年的第幾天,然后二者交集區(qū)間end的一年第幾天 減去 start的一年第幾天就是答案。
【調(diào)庫(kù)】用datetime.datetime的days算天數(shù)。
【調(diào)庫(kù)】用datetime.date的days算天數(shù)。
2410. 運(yùn)動(dòng)員和訓(xùn)練師的最大匹配數(shù)?https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/
【排序 + 貪心】每個(gè)運(yùn)動(dòng)員都應(yīng)該找能力值大于等于且最接近自己的訓(xùn)練師。
2411. 按位或最大的最小子數(shù)組長(zhǎng)度?https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/
【逆序遍歷】題意是找每個(gè)以i為起點(diǎn)的最短子數(shù)組,滿足或運(yùn)算結(jié)果最大,那么需要使得二進(jìn)制表示的1盡可能多??梢杂靡粋€(gè)32位的數(shù)組記錄每一位1最早出現(xiàn)的位置。逆序遍歷,枚舉每個(gè)數(shù),如果同一二進(jìn)制位存在 1 的話,保留最小的下標(biāo),如果第j位存在1,更新pos - i + 1。
【優(yōu)化后的逆序遍歷】正序遍歷nums[i],從i-1逆序遍歷nums[j],如果num[j] | nums[i] != nums[j],說(shuō)明num[j]變大了,更新nums[j],如果num[j] | nums[i] == nums[j],說(shuō)明nums[i]是nums[j]和nums[k] (k < j)的子集。
2412. 完成所有交易的初始最少錢(qián)數(shù)?https://leetcode.cn/problems/minimum-money-required-before-transactions/
【貪心】題意要求至少多少啟動(dòng)資金能完成所有交易,所以要從最壞情況考慮,即對(duì)于每一次交易,都先把所有虧錢(qián)交易進(jìn)行之后在進(jìn)行本次交易,對(duì)于一次賺錢(qián)交易,初始資金至少為此前全部虧錢(qián)+本次交易入場(chǎng)費(fèi);對(duì)于一次虧錢(qián)交易,初始資金至少為此前全部虧錢(qián)+當(dāng)前交易將要凈虧的錢(qián)(以保證本次交易后結(jié)束后不會(huì)破產(chǎn))。代碼中,total_lose為所有虧的錢(qián),total_lose = sum(cost - cashback),對(duì)于cost _i<= cashback_i的交易,初始資金 = total_lose + cost_i,對(duì)于cost_i > cashback_i的交易,初始資金 = total_lose + cost_i - (cost_i - cashback_i) = total_lose + cashback_i。遍歷每次交易,記錄max(total_lose + cashback, total_lose + cost)。
不用python的max函數(shù),速度會(huì)更快。