2023-09-09 20:35 苏州大学 算法工程师
关注
笔试算法题-day07
题目：给定一个整数n，和一个长度为n的列表的数组l，给定一个公式f(x)=1*l[0]+2*l[2]+...+n*l[n-1]，现在需要求解数组l所有子数组的对应公式的值的和？
样例：给定[1,2]，输出8，8=1*1+2*2+1*1+2*1
解题思路：直接求子数组O(n^2)，时间复杂度高，找规律，使用一维dp，直接100%；
思路：8=2*(1+2)+1*1+(2*1)，dp[0]=1*1=1，dp[1]=dp[0]+2*((1+2)*2)//2，res=dp[0]+dp[1]=8；
样例：给定[1,2]，输出8，8=1*1+2*2+1*1+2*1
解题思路：直接求子数组O(n^2)，时间复杂度高，找规律，使用一维dp，直接100%；
思路：8=2*(1+2)+1*1+(2*1)，dp[0]=1*1=1，dp[1]=dp[0]+2*((1+2)*2)//2，res=dp[0]+dp[1]=8；
全部评论
HsiuQin 楼主
楼主 苏州大学 算法工程师
浅浅记录一下，首次笔试AC三道，分别是day07，day08，day09，加油！
相关推荐
不愿透露姓名的神秘牛友
06-19 17:02
水中水之下水道的鼠鼠：接了再说，不图转正的话混个实习经历也不错
投递拼多多集团-PDD等公司10个岗位 > 点赞 评论 收藏
分享
06-03 03:20
河北农业大学 人力资源专员/助理 
点赞 评论 收藏
分享
查看6道真题和解析