360算法岗笔试 9.28

一小时速通
考试时间结束更新解析
休息会儿晚饭后继续盒马笔试🫠

---------------------更新------------------------------

选择题考的很杂，计网、概率论、Cpp什么都有

2道算法：

1.给一个正整数数组，可以进行如下操作：取其中两个元素x,y，将其转化为x, x+y。
   目标：O(n)计算最少操作次数使得数组内所有元素互异
   又是思维题，最佳策略就是取当前数组内最大值，左脚踩右脚升天（最大值加数组内任何一个元素，所得到的新值一定没有出现过）。只需要开个哈希表记录一下每个重复元素出现的次数-1，求和即可

2.给一个正整数数组，定义该数组区间的权重和sum[l,r]为：区间[l,r]内去重后的总和。要求将数组划分为k个子区间使得所有区间的权重和之和最大。
    暴力dp就能过，数据量允许O(n^3)，可以先枚举预处理一下所有区间[l,r]的权重和sum[l,r]
    定义状态f[i][j]：区间[1,i]划分j次的最大权重和
    状态转移方程：max(sum[pos][i] + f[pos - 1][j - 1])

#秋招#  #算法岗#  #计算机#  #笔试#  #360#