396. 旋转函数
题目描述：
给定一个长度为 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(k) = 0 * arrk[0] 1 * arrk[1] … (n - 1) * arrk[n - 1]
// k=0 顺时针旋转0个位置 arr0=[4,3,2,6]
F(0) = (0 * 4) (1 * 3) (2 * 2) (3 * 6) = 0 3 4 18 = 25
// k=1 顺时针旋转1个位置 arr1=[6,4,3,2]
F(1) = (0 * 6) (1 * 4) (2 * 3) (3 * 2) = 0 4 6 6 = 16
// k=2 顺时针旋转2个位置 arr2=[2,6,4,3]
F(2) = (0 * 2) (1 * 6) (2 * 4) (3 * 3) = 0 6 8 9 = 23
// k=3 顺时针旋转3个位置 arr3=[3,2,6,4]
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 。
超时解：
思路：
代码语言：javascript复制采用双指针，一头一尾，每旋转一次，两个指针左移便是旋转后的切片。
func maxRotateFunction(nums []int) int {
length := len(nums)
if length==1 {
return 0
}
// 每轮两指针左移一位
pointHead := 0
pointTail := length - 1
ans := math.MinInt64
for i := 0; i < length; i {
f := 0
head := pointHead
for j := 0; j < length; j {
f = j*nums[head] f
head = (head 1) % length
}
// 如果头指针后推,为负,就指向队列末尾
pointHead--
if pointHead < 0 {
pointHead = length - 1
}
pointTail--
ans = int(math.Max(float64(ans),float64(f)))
}
return ans
}正解：
思路：
观察F(0), …, F(k)的规律可得： 每旋转一次数组，都是最后一个值的系数变为了0，而其他值的系数都是 1 所以定义sum用来存放数组和, 而
F(k) sum就等于所有系数都 1, 再减去最后一个变化后的值去掉就就是F(k 1)的值了 以示例1为例：
- sum就是切片内所有元素的和,你每加一次sum,就相当于F(k)的每个系数都 1
例如：
sum = 4 3 2 6 = 15
F(0) = (0 * 4) (1 * 3) (2 * 2) (3 * 6) = 0 3 4 18 = 25
F(0) sum = (0 * 4) (1 * 3) (2 * 2) (3 * 6) 4 3 2 6
= (1 * 4) (2 * 3) (3 * 2) (4 * 6) = 40
而由上面观察到的规律：每旋转一次数组，都是最后一个值的系数变为了0，而其他值的系数都是 1
那么我们观察F(1)相对与F(0) sum哪里有差别：
F(1) = (1 * 4) (2 * 3) (3 * 2) (0 * 6)F(0) sum = (1 * 4) (2 * 3) (3 * 2) (4 * 6)可以看到原本最后一个值应该对应的是0*6 而F(0) sum里却是4*6 所以我们可以得出： F(1) = F(0) sum - 最后一个变化后的值 = 25 15 - 24 = 16
func maxRotateFunction(nums []int) int {
// sum: 数组内所有元素的和
// curSum: F(k) 就是每次旋转数组后，代入F(k)公式求的那个
sum, curSum, ans := 0, 0, 0
for i := 0; i < len(nums); i {
// 求数组和
sum = sum nums[i]
// 求F(0)
curSum = curSum i*nums[i]
}
ans = curSum
for i := len(nums) - 1; i > 0; i-- {
// F(K 1) = F(K) sum - 最后一个变化后的值
curSum = curSum sum - len(nums)*nums[i]
ans = max(ans, curSum)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}提交结果：
