By Long Luo
Leetcode 396. 旋转函数 题解。
方法一: 暴力法
思路与算法
很容易想到的方法是遍历,使用 2 个循环,很明显最多只能有 len 次旋转,因为对称性,所以数组下标可能会 >=len,所以要取余 (i+j)modlen。
每次旋转更新最大值,时间复杂度为 O(N2)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| public int maxRotateFunction(int[] nums) { int len = nums.length; if (len <= 1) { return 0; }
int ans = Integer.MIN_VALUE; for (int i = 0; i < len; i++) { int sum = 0; for (int j = 0; j < len; j++) { sum += j * nums[(i + j) % len]; }
ans = Math.max(ans, sum); }
return ans; }
|
复杂度分析:
方法二: 动态规划
思路与算法:
方法一会超时,其实观察旋转数组的变化:
F(0)=0×nums[0]+1×nums[1]+…+(n−1)×nums[n−1]
F(1)=1×nums[0]+2×nums[1]+…+0×nums[n−1]=F(0)+i=0∑n−1nums[i]−n×nums[n−1]
我们很容易发现相邻旋转的递推关系:
F(k+1)=F(k)+i=0∑n−1nums[i]−n×nums[n−k],0≤k<n
从F(0)出发,迭代计算出不同的F(k),并求出最大值。
很容易使用DP写出如下代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| public int maxRotateFunction_dp(int[] nums) { int len = nums.length; if (len <= 1) { return 0; }
int[] dp = new int[len]; int sum = 0; for (int i = 0; i < len; i++) { dp[0] += i * nums[i]; sum += nums[i]; }
int ans = dp[0]; for (int i = 1; i < len; i++) { dp[i] = dp[i - 1] + sum - len * nums[(len - i) % len]; ans = Math.max(ans, dp[i]); }
return ans; }
|
观察上述代码,我们发现dp[]
数组只是记录数值,实际上可以将空间复杂度优化到O(1)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public int maxRotateFunction_dp_opt(int[] nums) { int len = nums.length; if (len <= 1) { return 0; }
int ans = 0; int sum = 0; for (int i = 0; i < len; i++) { ans += i * nums[i]; sum += nums[i]; }
int pre = ans; for (int i = 1; i < len; i++) { int curr = pre + sum - len * nums[len - i]; ans = Math.max(ans, curr); pre = curr; }
return ans; }
|
复杂度分析:
方法三: 前缀和 + 滑动窗口
思路与算法:
因为需要旋转数组,可以将 nums 进行复制拼接,得到长度为 2n 的新数组,在新数组上任意一个长度为 n 的滑动窗口都对应了一个旋转数组。
考虑在窗口的滑动过程中,计算结果会如何变化,假设当前我们处理到下标为 [i,i+n−1] 的滑动窗口,当前结果为:
cur=nums[i]×0+nums[i+1]×1+...+nums[i+n−1]×(n−1)
当窗口往后移动一位,也就是窗口的右端点来到 i+n 的位置,左端点来到 i+1 的位置。
我们需要增加新右端点的值,即增加 nums[i+n]×(n−1),同时减去旧左端点的值,即减少 nums[i]×0,然后更新新旧窗口的公共部分 [i+1,i+n−1]。
不难发现,随着窗口的逐步右移,每一位公共部分的权值系数都会进行减一。
nums[i+1]×1+nums[i+2]×2+...+nums[i+n−1]×(n−1)
变为
nums[i+1]×0+nums[i+2]×1+...+nums[i+n−1]×(n−2)
因此,公共部分的差值为 ∑idx=i+1i+n−1nums[idx],我们可以使用前缀和进行优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public int maxRotateFunction(int[] nums) { int len = nums.length; if (len <= 1) { return 0; }
int[] sum = new int[2 * len + 1]; for (int i = 1; i <= 2 * len; i++) { sum[i] = sum[i - 1] + nums[(i - 1) % len]; }
int ans = 0; for (int i = 0; i < len; i++) { ans += i * nums[i]; }
int curr = ans; for (int i = len + 1; i < 2 * len; i++) { curr += nums[(i - 1) % len] * (len - 1); curr -= sum[i - 1] - sum[i - len]; ans = Math.max(ans, curr); }
return ans; }
|
复杂度分析:
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗