1. 元素值数量的数组的最小增删距离:以非递减数组a=[1,1,3,4,4,4]为例,a中2个1,1个3,3个4,问最少几步插入数或删除数的操作,使得a中元素e的数量等于e的大小。用类型为map<int,int>的cnt记录e的数量,min(|e-cnt[e]|, cnt[e])即为e变化的最小编辑距离,注意0个e的情况可以接受。
2. 3x3格子上9个石子均匀分布的最小移动步数:3x3的格子上有9个石子,A[i][j]表示第i行第j列格子上石子的数量,问上下左右移动格子上的石子最少几步使得每个格子上1个石子。最后没做出来,思路是回溯加深搜,遍历A[i][j],若A[i][j]==0,依次访问A[i][j]一步、两步。。。到达的格子,若访问的格子中A[i][j]>1,题解为这次的步数加匀过来一个石子后A的题解;并讨论先往这个格子匀一个石子或不匀两种情况,即回溯,找最小值。
3. 涵盖数组所有种类元素的最小窗口长度:以a=[2,1,1,3,2,1,2]为例,a有三种元素,问包含三种元素的最短子序列长度。双指针框选包含三种元素的子序列,并讨论框选下子序列的最小值。
1."...xxx..xx.x.",替换连续k个x为.需要k+1元,给定B元,求最大可替换的x数量。贪心,先选最长的连续x,用优先队列维护,优先队列见优先队列
2.01数组,将1聚到一起的最少移动次数,原题在1703. 得到连续 K 个 1 的最少相邻交换次数,解法分析在滑动窗口-字符连续1移动最少次数,本题k=1的总数,不用滑动,统计包含的连续0区间的情况,乘区间移到1外面的代价即可。
3.n个病人,S个医生,每个病人有两个医生可选,问每个病人能否看到医生,思路:二分图最大匹配
1.从数组取一个数拿出一半放回称为一次操作,问最少操作数使得拿出的部分大于等于原数组和的一半。优先队列,最大堆,取一半放回优先队列。
2.X存储分数的分子,Y存储分数的分母,X和Y对应位置构成的分数a满足0<a<1,问这些分数两分数之和为1的对数。求分子和分母的最大公因数约分,然后以分母为键构建相同分母下的分子数组,分别求数组和为分母值的对数
3.数组范围内从某位置连续(X-1)次Y远跳的数值和的最小值,滑动窗口。