科大讯飞笔试-算法(8.30)

1. 大小为 n 的数组 a,下标是 [1, n],这n个数初始值都为0, 有 p 次操作,每次操作会取反 a[p] ,也就是0变1,1变0。给定 x 和 y( x 和 y 是最开始的输入,操作过程中是不变的),问每次操作后区间 [1, x] 和 [y, n] 中分别有多少个0?【10分】

模拟就行,注意y <= x的情况

2. 有1-n n个数,每次移动选择[l, r]子区间移动到数组末尾,有q次移动,问最终所有的数字 i (1 <=i <= n) 在几个不同的索引位置上出现过?【15分】

n 和 q 范围只有3e3,O(n*n)模拟就行

3. 给定一个01字符串,定义得分是所有连续1子串的长度的平方和,有k次将0修改为1的机会,问修改后最大得分?【25分】

第三题没想出来最优的情况TAT,写了两种

第一种将0子串按照长度排序之后修改k个0为1,再计算得分,过了15%。这样肯定是不对,因为没考虑合并后1子串的长度。

第二种就无脑把前k个0改为1,过了23%

全部评论
好好好,看了其他人的思路,原来第3题是滑动窗口在保证0的个数不大于k的情况下维护最长的子串
点赞 回复 分享
发布于 08-30 21:30 四川
算法题咋不一样,没有取快递那题吗?
点赞 回复 分享
发布于 08-30 21:36 北京
麦吉太文
校招火热招聘中
官网直投
同是算法岗,题目咋不完全一样,科大讯飞的题是随机的吗
点赞 回复 分享
发布于 08-30 21:49 上海
考试时间是一个小时吗
点赞 回复 分享
发布于 09-03 11:51 孟加拉国
有选择题吗,老哥。
点赞 回复 分享
发布于 09-03 22:56 广东

相关推荐

08-30 21:19
东北大学 Java
投递科大讯飞等公司10个岗位
点赞 评论 收藏
分享
难度挺大的,做完不能回头看一、单选:1、float==double:float会被转成double,即便如此,仍有可能返回false2、AdaBoost算法确实会加大此前决策树(或其他弱分类器)分类错误的权重,使下一个模型尽可能正确,所以依赖之前的模型;3、GBDT(Gradient&nbsp;Boosting&nbsp;Decision&nbsp;Tree,梯度提升决策树)是一种集成学习方法,它通过迭代地构建决策树来优化损失函数,从而组合成一个强学习器。其核心思想是通过计算损失函数在当前模型上的梯度(或近似梯度),来定位模型的不足之处,并基于这些梯度信息来构建新的决策树模型,以逐步减少损失函数的值。4、AdaBoost和GBDT都属于决策树模型boosting方法5、生成式预训练(Generative&nbsp;Pre-Training)是一种在自然语言处理(NLP)和计算机视觉等领域广泛使用的技术,其核心思想是通过在大规模无标签数据上进行预训练,使模型学习到数据的内在规律和表示,从而能够更好地适应下游任务,生成式预训练本身并不直接与目标函数绑定,有助于缓解过拟合问题,不一定直接保证有助于鉴别的精细化;6、鉴别性预训练通常指的是那些直接针对特定任务(如分类或回归)进行优化的预训练方法,分类准则可以用交叉熵,回归准则可以用最小均方误差7、鉴别性训练通常应用在机器学习,特别是语音识别和自然语言处理等领域中,是一种通过最小化目标函数来优化模型性能的训练方法。在最小化目标函数的过程中,可能会导致底层权重向最终目标过多调整,从而忽略了隐藏层的重要性;8、DNN(深度神经网络)参数确实可以使用鉴别性预训练(Discriminative&nbsp;Pre-Training,简称DPT)来进行鉴别初始化。9、状态模式实际上很好地体现了封装性;10、状态模式通过将状态逻辑分散到多个状态类中来解决复杂的逻辑问题,但这确实可能导致类的数量增加;11、状态模式非常适合处理包含大量分支判断语句的代码12、在状态模式中,通常会有一个抽象状态角色(State&nbsp;interface或抽象类),它定义了所有状态类共有的接口。这个接口包括了一些方法,这些方法对应于环境类在不同状态下可能需要执行的行为13、Adam结合了动量法和RMSProp算法的思想,使得Adam能够适应不同参数的更新需求,加快收敛速度;14、SGD容易受到数据噪声的影响,导致训练过程不稳定,可能更容易达到全局最优解;15、处理大规模数据集和复杂模型时,Adam通常是一个不错的选择;而在处理小规模数据集或需要精细调整模型时,SGD或RMSProp可能更加合适16、稀疏数据是指数据集中包含大量零值或缺失值的数据。对于这类数据,使用学习率自适应的优化算法确实是一种有效的策略。学习率自适应算法能够根据数据的特性和训练过程中的梯度变化动态调整学习率,从而在稀疏数据上获得更好的训练效果17、2个长度为N的vector进行swap操作时间复杂度是O(1)18、5g的磁盘,2kb一个的簇,共有2621440个簇,使用位图法,2kb有2048字节,也就是16384位,一位标识一个簇,那么需要2621440&nbsp;/&nbsp;16384=&nbsp;160个簇19、贝叶斯是先验推后验二、编程题:1道栈,2道图论,对应难度:简单、中等、困难,各15分
查看5道真题和解析 投递科大讯飞等公司10个岗位
点赞 评论 收藏
分享
4 5 评论
分享
牛客网
牛客企业服务