從數(shù)量最多的堆取走禮物

【SortedList】math.isqrt(x) 方法返回 x 的平方根，并將平方根數(shù)向下舍入到最接近的整數(shù)。

【最大堆模擬】原地堆化可以做到 O(1) 額外空間。先乘-1轉(zhuǎn)成負(fù)數(shù)

統(tǒng)計(jì)范圍內(nèi)的元音字符串?dāng)?shù)

【前綴和】先預(yù)處理words，判斷是否符合要求，符合視為1，不符合視為0，求前綴和，ans就是s[r + 1] - s[l]。

打家劫舍 IV

【二分 + DP】“最大化最小值”、”最小化最大值“想到二分。設(shè)二分的最大金額為mx，定義f[i]表示前i個(gè)房屋中偷取金額不超過(guò)mx的房屋的最大個(gè)數(shù)。不選第i個(gè)房屋，f[i] = f[i - 1]，選第i個(gè)房屋(前提是金額不超過(guò)mx)，f[i] = f[i - 2] + 1，這兩者取最大值: f[i] = max(f[i - 1], f[i - 2] + 1)。代碼里i全部加2，避免負(fù)數(shù)。

用滾動(dòng)數(shù)組優(yōu)化。

重排水果

【貪心 + 構(gòu)造】先把兩個(gè)數(shù)組中都有的數(shù)去掉，每個(gè)剩余數(shù)字出現(xiàn)次數(shù)必須為偶數(shù)，可用哈希表統(tǒng)計(jì)。設(shè)處理后的剩余數(shù)組為a和b，貪心：如果要交換a中最小的數(shù)，找一個(gè)b中最大的數(shù)是最合適的，對(duì)于b中最小的數(shù)也同理。那么把a(bǔ)升序排序、b降序排序，兩兩匹配。還有一種情況，basket1和basket2中最小值mn當(dāng)中介，對(duì)于a[i]和b[i]的交換，分別和mn交換一次，每次交換代價(jià)為min(a[i], b[i], 2×mn)，累加代價(jià)就是答案。sort換成快速選擇能達(dá)到O(n)。