统计数量

数组directions中有“L”、“R”、“S”三种字符分别表示当前位置的车辆向左转、向右转、静止不动,车辆运动一次后若产生碰撞则静止不动,求运动一次后碰撞的次数,注向左转和向右转的车辆碰撞记为两次,若产生碰撞的其中一辆汽车在碰撞前静止不动,则记碰撞次数为一次。[1]解法:ans=0,x=0,y=0;ans+=x if c=='L' for c in directions else x=1;directions.reverse();ans+=y if c=='R' for c in directions else y=1;只有最靠左的“L”和最靠右的“R”不会产生碰撞,其他位置的“L”和“R”的数量即碰撞次数,解法抽解出多种情况碰撞次数的计算模式,且没在意c第一次不等于“R”时设置y为1,其他时候不用重设,删繁就简的想法很棒,这样做不用多声明一个变量结果这个变量每次遍历的时候还得判断,画蛇添足

pattern是含有两个字符的字符串,求任意位置插入pattern的一个字符text中含有的pattern子序列的个数。[2]pattern[0]插到位置0或pattern[1]插到位置n时pattern子序列个数的最大值即结果。我们需要统计text中有多少个pattern[0]和pattern[1],以及有多少个pattern子序列。遍历text,a表示遍历时访问过多少个pattern[0],b表示遍历时访问过多少个pattern[1],如果pattern[0]==pattern[1],res+=(t==pattern[1])*(a-1);else res+=(t==pattern[i])*a;结果为res+max(a,b)

从数组中拿出一个数,减半,再放回去,求使得数组总和小于等于起初一半的最少减半次数。[3]最多减半n次——起初的每个数各减半一次。拿出数组中的最大值减半,即得结果。注意数据类型的声明,防止截断,且sum声明为double,防止int加和溢出。题解见白云悠远题解,手动优先级队列

01字符串中“010”子序列的个数[4]:遍历01字符串,初始化a、b、c分别为0,for(char e:s){if(e=='0')c+=b;if(e=='1')b+=a;if(e=='0')a+=1;}return c

[x,h]表示水平方向最左边的边在x的边长为h的正方形,不一定有序的多个正方形从无限高处依次落下,如同俄罗斯方块般,整个正方形落到h为0的水平线过程中遇到障碍,停止下落,求所有正方形落下后最高点的高度。[5]对每个正方形来说,判断它可能碰到的已落的正方形,算出这个正方形的高度。

nums中拿出多个子序列,每个子序列满足最大值-最小值不大于k,求划分的子序列的最小个数[6]。排序加贪心,先排序,分区段找到子序列中的最小值,潜在的最大值是这个最小值+k,分出的段对应一个子序列。

参考链接:[1].2211. 统计道路上的碰撞次数
[2].2207. 字符串中最多数目的子字符串
[3].2208. 将数组和减半的最少操作次数
[4].6035. 选择建筑的方案数
[5].699. 掉落的方块
[6].6091. 划分数组使最大差为 K

创建于2022.3.21/16.44,修改于2022.6.5/22.54