京东算法2023/3/4机试编程题目
投票
#京东##京东笔试##春招##23年春招##23届找工作##笔试##笔试经验#第一题送分题,第二题遍历即可。第三题没通过全部用例,卡住了,分享一下
输入一个数N,求数组大小为n, 数字范围为1~n数组的权值和。(权值代表数组最大值的数字的个数)
示例:2
输出:6
数组包括
[1,2]权值为1
[1,1]权值为2
[2,2]权值为2
[2,1]权值为1.
权值和6。
分享出来,看大家有没有好见解。
输入一个数N,求数组大小为n, 数字范围为1~n数组的权值和。(权值代表数组最大值的数字的个数)
示例:2
输出:6
数组包括
[1,2]权值为1
[1,1]权值为2
[2,2]权值为2
[2,1]权值为1.
权值和6。
分享出来,看大家有没有好见解。
全部评论
那个全过的大佬出来指导一下啊,这题咋做呢。
蹲
M
mark一下,首先全排列就是N^N,那么对于N,出现在第一位的次数就是N^(N-1),一共会出现1-N,因此最大值为N的时候,权值和为N*N^(N-1),同理,当最大值为N-1的时候,N*(N-1)^(N-1),所以结果就是N*(N^(N-1)+(N-1)^(N-1).....1^(N-1)), 比如2就是2*(2^1+1^1)2*(2+1)为6,3就是3*(3^2+2^2+1^2) 3*(9+4+1)为42
1. 首先单独考虑最大值为1.此时只能是[1, 1, 1,...,1](共n个),其权值为n。
2. 下面考虑最大值不为1。枚举最大值为max,枚举其出现次数为cnt(显然,此时cnt即为权值)
--- 2.1 首先,从n个位置中选择cnt个位置填入当前最大值max,这是一个组合问题,其次数为C(n, cnt),记为t1
--- 2.2 然后,考虑剩余的n-cnt个位置。显然每个位置可以填入1~max-1共max-1种可能的取值。因此为pow(max-1,n-cnt),记为t2
--- 2.3 上述两步之间是乘法关系,对总答案有cnt*t1*t2的贡献,把全部加到最终答案上即可。
3. 综合1,2,得到解。复杂度为O(n^2),由于带模,需要用杨辉三角或乘法逆元提前处理一下组合数。
相关推荐
11-15 00:37
南京大学 FAE 经历了无数测评和宣讲会,拒信是一封又一封,努力却没有回应,真让我感到很累啊。似乎明白自己投了简历也会被刷,面试也毫无意义,渐渐开始懒得再投、再测、再面。求求了,给我一个offer,让我重新燃起斗志吧!
牛客84762733号:南✌,你不是没有offer,你是没有让你满意的offer,而身为双非鼠鼠的我,连面试都没有
点赞 评论 收藏
分享
11-19 16:07
浙江大学 采购 点赞 评论 收藏
分享