ChunNote
0%

leetCode-396:Rotate Function

发表于 分类于

问题描述

给定一个数组，定义它的旋转数组为 f(k) = k * a[0] + (k + 1) * a[1] + (k + 2) * a[2] + ... + (n - 1) * a[n - k - 1] + 0 * a[n - k] + 1 * a[n - k + 1] + ... ，比如对于数组 [4,3,2,6]，其旋转数组为：f(0) = 0 * 4 + 1 * 3 + 2 * 2 + 3 * 6 = 25，f(1) = 1 * 4 + 2 * 3 + 3 * 2 + 0 * 6 = 16，f(2) = 2 * 4 + 3 * 3 + 0 * 2 + 1 * 6 = 23，f(3) = 3 * 4 + 0 * 3 + 1 * 2 + 2 * 6 = 26 要求找出最大的旋转数组的值。题目链接：**点我**

样例输入输出

输入：nums = [4,3,2,6]

输出：26

解释：f(0) = 0 * 4 + 1 * 3 + 2 * 2 + 3 * 6 = 25

f(1) = 1 * 4 + 2 * 3 + 3 * 2 + 0 * 6 = 16

f(2) = 2 * 4 + 3 * 3 + 0 * 2 + 1 * 6 = 23

f(3) = 3 * 4 + 0 * 3 + 1 * 2 + 2 * 6 = 26

输入：nums = [100]

输出：0

问题解法

此问题最直接的解法是按照题意循环算出每个旋转函数的值，但是这样太耗时了，优化点的做法是使用动态规划，动态转移方程为 f(k) = f(k - 1) + sumArray - n * nums[n - k]。此方法主要参考：https://leetcode.cn/problems/rotate-function/solution/xuan-zhuan-shu-zu-by-leetcode-solution-s0wd/。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxRotateFunction(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int first = 0;
        for (int i = 0; i < nums.length; i++) {
            first = first + i * nums[i];
        }

        int result = first;
        for (int i = 1; i < nums.length; i++) {
            int current = first + sum - nums.length * nums[nums.length - i];
            result = Math.max(result, current);
            first = current;
        }
        
        return result;
    }
}

参考资料

https://leetcode.cn/problems/rotate-function/solution/xuan-zhuan-shu-zu-by-leetcode-solution-s0wd/