复盘|第301场周赛
装满杯子需要的最短总时长
【贪心 + 模拟】每次取最大的两个减一,直到其中一个为 0 为止。
【数学】尽可能多的使用装满2被不同类型的水,此时最小秒数是向上取整,存在一种水的类型远超其他两种类型时,最小秒数为max(amount)。
无限集中的最小数字
【有序数组】模拟。
移动片段得到字符串
【双指针】无论怎么移动,L和R无法互相穿过对方,那么去掉_后的剩余字符应该是相同的,否则返回false。然后用双指针遍历start[i]和target[j],分类讨论:如果当前字符为L且ij,那么这个R由于无法向左移动,返回false。遍历完,若中途没有返回false就返回true。
统计理想数组的数目
【组合数学 + 质因数分解】用隔板法:把n个盒子当做n-1个隔板,隔板加上球总共有n-1+k个位置,从中选择一1个位置放隔板,k个位置放球,两个隔板之间的球(球可以有零个,一个,或者多个)放入对应盒子中(最两侧的隔板同理)因此方案数为C(n+k-1,n-1)=C(n+k-1,k)。对于多个不同的质因数,互相之间无影响,可以采用乘法原理计算。枚举所有[1,maxValue]的x,计算对应的组合数,累加即为答案。代码中,ks[x] 为 x 分解质因数后,每个质因数的个数列表。