今天也要加油啊江同学

刷题日记

刷题日记

LeetCode 第 48场双周赛 

1798. 你能构造出连续值的最大数目

解法:

智力题,实际是动态规划思想。

先对硬币排序,已知前i个硬币能组成0-n,则第i+1个硬币只要满足值<=n+1,则这前i+1个硬币就可以组成0-n+coins[i](第i+1个硬币下标是i)。

拿dfs整了一通结果第9个就超时。。。这种偏智力的题目感觉曾经是做得出来的,这个故事告诉我们刷题不能让思维僵化,要能屈能伸。。。

LeetCode 第 232场周赛 

1792. 最大平均通过率

解法:

最小堆

使用一个最小堆来维护每个班级加上extraStudents后与原本的差值。每次pop出来差距最大的那个,时间复杂度O(mlogn),m为extraStudents的数量

1793. 好子数组的最大分数

解法:

双指针+贪心

相似题目:

11. 盛最多水的容器

84. 柱状图中最大的矩形

LeetCode 第 231 场周赛 

1787. 使所有区间的异或结果为零

解法:
贪心+枚举
要达到题目要求需要满足两个条件:
1. a_1 = a_(k+1) = …
    a_2 = a_(k+2) = …
    a_k = a(2k) = …
也就是说数组的周期为k。
2. a_1^a_2^…a_k = 0
为达成条件1,最小需要改变的次数为n-各组(这里组的概念是竖着的,也就是a_1,a_(k+1),…形成一组)最大出现次数之和
为达成条件2,如果在条件1的基础上,这k个各组的最大值的异或恰好为0,则不需要额外代价。否则,需要额外修改一组数(可以证明,修改两个数肯定没有修改一个数代价小。因此只要考虑额外修改一组数的情况),来满足a_i = a_1^ … a_(i-1) ^ a_(i+1) ^ … a_k
枚举来找到这个最小的额外代价即可。
 
其它:python中collections.Counter的使用。与dict类似。
cnts = [collections.Counter() for _ in range(k)] 建立k个计数器。
 

1786. 从第一个节点出发到最后一个节点的受限路径数

解法:

dijkstra+dp

首先不能使用floyd,因为我们只需要找到单个点(n)到其余所有点的距离,所以采用dijkstra(floyd时间复杂度n3方,Dijkstra是n方)。另外,邻接表的存储不使用二维数组,而采用字典(defaultdict)来实现。

其次,Dijkstra的使用也有trick,需要使用堆优化。使用python中的heapq来实现堆,minHeap是我们想要的堆,初始化为:minHeap=[(0, n)],然后每次heappop弹出堆中的最小值,如果这个最小值已经被访问过了,那么继续;否则,更新它周围的点的距离值,将周围的点放入minHeap,并将其本身放入visited表示已经被访问过。堆空为止更新完成。我们得到了一个dist数组。

dp时,对dist进行升序排序,并初始化一个长度为n+1的dp,dp[n]=1,从最靠近n的点往外层进行dp。若dist[node]>dist[next],则dp[node] += dp[next],以此进行dp。另外当node=1时就不需要再继续了,因为此时右边的点到n的距离都比1到n要远。

其它:

python中defaultdict的使用:

edge = defaultdict(dict) 表示建立一个dict,这个dict的value也是一个dict
更多参考:
 
python中heapq的使用:
 
另外看了别人的答案,使用了0x3f3f3f3f代表无穷大,但因为这里edge到10的5次方,n到2*10的4次方,0x3f3f3f3f大概是10的9次方多一点,是不够的。所以要更大一些。
 

1785. 构成特定和需要添加的最少元素

用//代替int(a/b)绕过溢出问题

LeetCode 第47场双周赛

1781. 所有子字符串美丽值之和

解法:

滑动窗口+哈希表

设置长度从3到l的滑动窗口+哈希表即可。

其它:

python中求ASCII码:ord(‘s’)

1782. 统计点对的数目

解法:

容斥原理

暴力方法:用二维数组存储点对信息,时间复杂度max(O(ExN),O(NxN)),会TLE。

点对的值实际上等于与e(a)+e(b)-c(a,b)>q[i]所在的边,所以其实一维数组存储下来单个点的边信息e就够了,但是查询的时候还是要扫两遍,这样的时间复杂度就是O(NxN),还是会TLE。

改进:由于瓶颈出现在查询的时候,所以试图优化查询。查询为什么要扫两遍,是因为e(a)+e(b)。这里,可以将问题拆分成先求出e(a)+e(b)>q[i]的点对的数量res1,再求出同时满足e(a)+e(b)>q[i],e(a)+e(b)-c(a,b)<=q[i]的点对的数量res2,res1-res2就是我们想要的结果。

res1可以通过经典的双指针解决。

求res2的时候要注意,无需遍历所有点对,因为满足这样条件的点对一定在edges数组中。因此只需要再遍历一次edges数组。这样的时间复杂度是O(E)+O(NlogN)

其它:

python中构造MxN的二维数组:

list = [[0]*N for i in range(M)],时间复杂度为O(MxN)

注意,list=[[0]*N]*M不行,这只是对[0]*N的引用,修改一个值会对其它列的值也产生影响。

 

xinyu