復(fù)盤|第290場(chǎng)周賽
多個(gè)數(shù)組求交集
【哈希表】統(tǒng)計(jì)每個(gè)整數(shù)的出現(xiàn)次數(shù),在nums中所有數(shù)組都出現(xiàn)過的元素的freq = len(nums),返回排序后的元素集合。
統(tǒng)計(jì)圓內(nèi)格點(diǎn)數(shù)目
【枚舉】枚舉所有點(diǎn),找圓。優(yōu)化一下,先按半徑從小到大排序,可以更早地碰到包含當(dāng)前枚舉點(diǎn)的圓。
統(tǒng)計(jì)包含每個(gè)點(diǎn)的矩形數(shù)目
【按縱坐標(biāo)排序】對(duì)每個(gè)(x,y)統(tǒng)計(jì)橫坐標(biāo)≥x且縱坐標(biāo)≥y的矩形的個(gè)數(shù),將縱坐標(biāo)≥y_i的矩形的橫坐標(biāo)加入一個(gè)有序列表xs,由于縱坐標(biāo)范圍只有[1,200],可以暴力地在每次插入完橫坐標(biāo)后對(duì)xs排序,排序的次數(shù)不會(huì)超過100次,在xs中二分即可算出橫坐標(biāo)不小于x_i的矩形個(gè)數(shù)。
如果縱坐標(biāo)范圍10^9,用名次樹來做(Treap,python的SortedList).
【按橫坐標(biāo)排序】按橫坐標(biāo)從大到小排序,對(duì)于點(diǎn)(x_i,y_i),統(tǒng)計(jì)橫坐標(biāo)不小于x_i的矩形個(gè)數(shù),高度不超過100,可以用數(shù)組存每個(gè)高度有多少個(gè)矩形,累加高度≥y_i的矩形個(gè)數(shù),實(shí)現(xiàn)時(shí)可以暴力累加或樹狀數(shù)組。
【按行統(tǒng)計(jì) + 二分查找】縱坐標(biāo)至多100種,看成100行數(shù)據(jù),統(tǒng)計(jì)這100行的矩陣橫坐標(biāo),對(duì)于每個(gè)(x_i, y_i),從第y_i行遍歷到第100行,每一行,二分求出多少個(gè)矩陣的橫坐標(biāo)≥x_i,累加為ans。
花期內(nèi)花的數(shù)目
【差分】flower_i是區(qū)間[start_i, end_i]的每個(gè)時(shí)間點(diǎn)都增加一朵花,對(duì)于第i個(gè)人,算person_i時(shí)間點(diǎn)上有多少朵花。(不超過person_i時(shí)間點(diǎn)變化量的累計(jì)值)python用defaultdict或sorteddict都行。
【轉(zhuǎn)換 + 二分】第i個(gè)人能看到花的數(shù)目,等價(jià)于star≤person_i的花的數(shù)目 減去 end<person_i的數(shù)目,即開花數(shù)減凋落數(shù)。單獨(dú)統(tǒng)計(jì)開花時(shí)間和凋落時(shí)間,排序后二分就得到ans.