martin0621
martin0621
全部文章
分类
题解(12)
归档
标签
去牛客网
登录
/
注册
martin0621的博客
全部文章
(共6篇)
题解 | #单链表的排序#
Merge-Sort/合并排序python代码: # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode...
2021-09-10
0
312
题解 | #合唱队#
优化了一下别人的代码,应该更易读些 import bisect as bi def ldp(h): # 动态规划 L=len(h) dp=[1]*L # 若左边没有比自己小的数,则为自己本身,所以初始值为1 for i in range(L): # 从左往右遍历 ...
2021-09-09
0
315
题解 | #我们的距离#
方法零:用边的信息构造邻接矩阵,用floyd算法求节点间的最短距离,求和输出。这个方法用python实现超时,floyd算法对于边相对稀疏的树效率不高。(C++这么做可以通过,代码略)方法一:遍历所有边,更新连通分量(Connected Component)和每个连通分量内的节点两两之间距离,最后求...
2021-08-25
0
616
题解 | #能被多个质数整除的第K长子段#
注意到,如果对于给定的区间左边界l,若满足题目条件的区间右边界最大为r,那么显然(l,r)的任意子区间也是满足条件的,也即固定区间左边界为(l,r)中任取的i,区间右边界至少为r。因此不需要记录每一个满足条件的区间对(i,j)再进行排序,而只需要对于左边界l从0到n-1遍历,查找并记录满足条件的最大...
2021-08-20
0
337
题解 | #牛牛组数#
基本是抄了别人的算法,但有一点改进:显然两颗星星之间的距离d关于时间t的函数d(t)是一个下凸函数,因而最小值唯一,从t=0开始逐步搜索的话,那么在遇到某个t满足d(t+1)≥d(t)的情况就可以终止本轮搜索,此时有d(t+1)≥d(t)>d(t-1)。根据下凸函数的特性,最小值一定属于区间(...
2021-08-16
1
337
题解 | #牛牛组数#
首先容易得知,和最大的k个数一定是k-1个1位数和1个n-k+1位数,且输入的x中的n个数字应如下分布:k个最小的数字填充到k个数的个位,其他数字从小到大依次填充到十位往上,构成最后的n-k+1位数。由于输入的数字只能是1到9,可以不用对x中数字排序,而是直接查找x中有多少个i(i=1,...,9)...
2021-08-13
0
358