当前位置:网站首页>LeetCode 练习——396. 旋转函数
LeetCode 练习——396. 旋转函数
2022-04-23 14:48:00 【SK_Jaco】
1.题目描述
给定一个长度为 n 的整数数组 nums 。
假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组,我们定义 nums 的 旋转函数 F 为:
F(k) = 0 * arrk[0] + 1 * arrk[1] + … + (n - 1) * arrk[n - 1]
返回 F(0), F(1), …, F(n-1)中的最大值 。
生成的测试用例让答案符合 32 位 整数。
示例 1:
输入: nums = [4,3,2,6]
输出: 26
解释:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
示例 2:
输入: nums = [100]
输出: 0
2.思路
2.1 代码
这道题挺有趣,如果使用暴力循环会提示超时,因此需要对公式进行分析。以题目示例进行分析,
进一步观察推导,在每一步中补上一个元素可以得到整个数组的和,即
F ( 0 ) = 0 ∗ n u m s [ 0 ] + 1 ∗ n u m s [ 1 ] + 2 ∗ n u m s [ 2 ] + 3 ∗ n u m s [ 3 ] F ( 1 ) = 0 ∗ n u m s [ 3 ] + 1 ∗ n u m s [ 0 ] + 2 ∗ n u m s [ 1 ] + 3 ∗ n u m s [ 2 ] = F ( 0 ) + n u m s [ 0 ] + n u m s [ 1 ] + n u m s [ 2 ] − 3 ∗ n u m s [ 3 ] = F ( 0 ) + ( n u m s [ 0 ] + n u m s [ 1 ] + n u m s [ 2 ] + n u m s [ 3 ] ) − 4 ∗ n u m s [ 3 ] F ( 2 ) = 0 ∗ n u m s [ 2 ] + 1 ∗ n u m s [ 3 ] + 2 ∗ n u m s [ 0 ] + 3 ∗ n u m s [ 1 ] = F ( 1 ) + n u m [ 0 ] + n u m [ 1 ] + n u m [ 3 ] − 3 ∗ n u m [ 2 ] = F ( 1 ) + ( n u m [ 0 ] + n u m s [ 2 ] + n u m [ 1 ] + n u m [ 3 ] ) − 4 ∗ n u m [ 2 F ( 3 ) = 0 ∗ n u m s [ 1 ] + 1 ∗ n u m s [ 2 ] + 2 ∗ n u m s [ 3 ] + 3 ∗ n u m s [ 0 ] = F ( 2 ) + n u m [ 1 ] + n u m [ 2 ] + n u m [ 3 ] − 3 ∗ n u m [ 0 = F ( 2 ) + ( n u m s [ 0 ] + n u m [ 1 ] + n u m [ 2 ] + n u m [ 3 ] ) − 4 ∗ n u m [ 0 ] \begin{aligned} F(0)&=0*nums[0]+1*nums[1]+2*nums[2]+3*nums[3]\\ \\ F(1)&=0*nums[3]+1*nums[0]+2*nums[1]+3*nums[2]\\ &=F(0)+nums[0]+nums[1]+nums[2]-3*nums[3]\\ &=F(0)+(nums[0]+nums[1]+nums[2]+nums[3])-4*nums[3]\\ \\ F(2)&=0*nums[2]+1*nums[3]+2*nums[0]+3*nums[1]\\ &=F(1)+num[0]+num[1]+num[3]-3*num[2]\\ &=F(1)+(num[0]+nums[2]+num[1]+num[3])-4*num[2\\ \\ F(3)&=0*nums[1]+1*nums[2]+2*nums[3]+3*nums[0]\\ &=F(2)+num[1]+num[2]+num[3]-3*num[0\\ &=F(2)+(nums[0]+num[1]+num[2]+num[3])-4*num[0]\\ \end{aligned} F(0)F(1)F(2)F(3)=0∗nums[0]+1∗nums[1]+2∗nums[2]+3∗nums[3]=0∗nums[3]+1∗nums[0]+2∗nums[1]+3∗nums[2]=F(0)+nums[0]+nums[1]+nums[2]−3∗nums[3]=F(0)+(nums[0]+nums[1]+nums[2]+nums[3])−4∗nums[3]=0∗nums[2]+1∗nums[3]+2∗nums[0]+3∗nums[1]=F(1)+num[0]+num[1]+num[3]−3∗num[2]=F(1)+(num[0]+nums[2]+num[1]+num[3])−4∗num[2=0∗nums[1]+1∗nums[2]+2∗nums[3]+3∗nums[0]=F(2)+num[1]+num[2]+num[3]−3∗num[0=F(2)+(nums[0]+num[1]+num[2]+num[3])−4∗num[0]
因此得到推导公式,其中 i 为公式中待减去的角标
F i ( n ) = F i ( n − 1 ) + ∑ i = 0 n n u m s − n u m s . L e n g t h ∗ n u m s [ i ] F_{i}(n)=F_{i}(n-1)+ \sum_{i=0}^n nums-nums.Length*nums[i] Fi(n)=Fi(n−1)+i=0∑nnums−nums.Length∗nums[i]
代码如下:
class Solution {
public int maxRotateFunction(int[] nums) {
int sum = 0;
int max = Integer.MIN_VALUE;
int curr = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
curr += nums[i] * i;
}
max = Math.max(max,curr);
for (int i = nums.length - 1; i > 0; i--) {
curr += sum - nums.length * nums[i];
max = Math.max(max,curr);
}
return max;
}
}
2.2 测试结果
通过测试
3.总结
- 暴力循环解决会超时
- 观察示例进行公式推导即可
版权声明
本文为[SK_Jaco]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_38550836/article/details/124342109
边栏推荐
- [proteus simulation] automatic range (range < 10V) switching digital voltmeter
- I/O复用的高级应用之一:非阻塞 connect———使用 select 实现(也可以用 poll 实现)
- On the insecurity of using scanf in VS
- SHT11传感器的温度湿度监控报警系统单片机Proteus设计(附仿真+论文+程序等)
- QT interface optimization: double click effect
- Matrix exchange row and column
- GIS数据处理-cesium中模型位置设置
- [servlet] detailed explanation of servlet (use + principle)
- Don't you know the usage scenario of the responsibility chain model?
- Detailed explanation of C language knowledge points -- first knowledge of C language [1]
猜你喜欢
GIS数据处理-cesium中模型位置设置
QT actual combat: Yunxi chat room
Swift: entry of program, swift calls OC@_ silgen_ Name, OC calls swift, dynamic, string, substring
LM317的直流可调稳压电源Multisim仿真设计(附仿真+论文+参考资料)
利用 MATLAB 编程实现最速下降法求解无约束最优化问题
8.2 文本预处理
eolink 如何助力远程办公
1 - first knowledge of go language
I thought I could lie down and enter Huawei, but I was confused when I received JD / didi / iqiyi offers one after another
UML project example -- UML diagram description of tiktok
随机推荐
Mds55-16-asemi rectifier module mds55-16
The art of automation
Swift - Literal,字面量协议,基本数据类型、dictionary/array之间的转换
冰冰学习笔记:一步一步带你实现顺序表
Svn detailed use tutorial
【Servlet】Servlet 详解(使用+原理)
面试官:说一下类加载的过程以及类加载的机制(双亲委派机制)
在游戏世界组建一支AI团队,超参数的多智能体「大乱斗」开赛
Master in minutes --- ternary operator (ternary operator)
你还不知道责任链模式的使用场景吗?
go基础 反射
Don't you know the usage scenario of the responsibility chain model?
数组模拟队列进阶版本——环形队列(真正意义上的排队)
51 MCU flowers, farmland automatic irrigation system development, proteus simulation, schematic diagram and C code
【工厂模式详解】工厂方法模式
First acquaintance with STL
Multisim Simulation Design of DC adjustable regulated power supply of LM317 (with simulation + paper + reference)
Sword finger offer II 019 Delete at most one character to get palindrome (simple)
QT actual combat: Yunxi chat room
Set up an AI team in the game world and start the super parametric multi-agent "chaos fight"