当前位置:网站首页>golang力扣leetcode 396.旋转函数
golang力扣leetcode 396.旋转函数
2022-04-23 09:28:00 【cheems~】
396.旋转函数
题解
题目:给一个数组,计算f,f=下标*值 的累加,并且每次会把数组末尾的数移到前面,求最大的f
思路:
f(0)=0*nums[0]+1*nums[1]+2*nums[2]+...+(n-1)*nums[n-1]
f(1)=0*nums[n-1]+1*nums[0]+2*nums[1]+...+(n-1)*nums[n-2]
f(0)=0*nums[0]+1*nums[1]+2*nums[2]+...+(n-1)*nums[n-1]
f(1)=1*nums[0]+2*nums[1]+3*nums[2]+...+0*nums[n-1]
f(1)-f(0)=nums[0]+nums[1]+nums[2]-(n-1)*nums[n-1]
=nums[0]+nums[1]+nums[2]+nums[n-1]-n*nums[n-1]
设numSum=nums[0]+...+nums[n-1]
得f(1)-f(0)=numSum-n*nums[n-1]
得到通式f(i)-f(i-1)=numSum-n*nums[n-i]
f(i)=f(i-1)+numSum-n*nums[n-k]
代码
func maxRotateFunction(nums []int) int {
numSum, f, n := 0, 0, len(nums)
for i, v := range nums {
numSum += v
f += i * v
}
//numSum=nums[0]+...+nums[n-1]
//f(i)=f(i-1)+numSum-n*nums[n-i]
ans := f
for i := 1; i < len(nums); i++ {
f = f + numSum - n*nums[n-i]
ans = max(ans, f)
}
return ans
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
版权声明
本文为[cheems~]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_42956653/article/details/124341832
边栏推荐
- Applet error: cannot read property'currenttarget'of undefined
- [SQL Server fast track] view and cursor of database
- Two ways for flutter providers to share data
- 2D 01 Backpack
- Vivo, hardware safe love and thunder
- Kettle experiment (III)
- Thread scheduling (priority)
- Set the maximum width of the body, but why does the background color of the body cover the whole page?
- 数据清洗 ETL 工具Kettle的安装
- 小程序报错:Cannot read property 'currentTarget' of undefined
猜你喜欢
Kettle实验 转换案例
[reading notes] Chapter 5 conditional statements, circular statements and block statements of Verilog digital system design tutorial (with answers to thinking questions)
Kettle experiment (III)
高薪程序员&面试题精讲系列91之Limit 20000加载很慢怎么解决?如何定位慢SQL?
Program, process, thread; Memory structure diagram; Thread creation and startup; Common methods of thread
Go language learning notes - structure | go language from scratch
AQS & reentrantlock implementation principle
【SQL server速成之路】数据库的视图和游标
Flink 流批一体在小米的实践
#yyds干货盘点#ubuntu18.0.4安装mysql并解决ERROR 1698: Access denied for user ''root''@''localhost''
随机推荐
Single sign on SSO
JS what is an event? Event three elements and operation elements
Sql1 [geek challenge 2019]
Kettle experiment (III)
错题汇总1
【SQL server速成之路】数据库的视图和游标
What is monitoring intelligent playback and how to use intelligent playback to query video recording
Harbor enterprise image management system
653. 两数之和 IV - 输入 BST
Kettle experiment
Write down the post order traversal of the ~ binary tree
三、6【Verilog HDL】基础知识之门级建模
kernel-pwn学习(3)--ret2user&&kernel ROP&&QWB2018-core
What is augmented reality technology? Where can it be used?
SQL used query statements
Emuelec compilation summary
js 原型链的深入
个人主页软件Fenrus
Enter "net start MySQL" and "system error 5. Access denied" appears. Detailed explanation of the problem
OpenCV中的图像处理 —— 轮廓入门+轮廓特征