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 。
超时解：
思路：
采用双指针，一头一尾，每旋转一次，两个指针左移便是旋转后的切片。
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 }
提交结果：
