[Leetcode][396. 旋转函数] 3种方法:暴力法,动态规划,前缀和 + 滑动窗口

By Long Luo

Leetcode 396. 旋转函数 题解。

方法一: 暴力法

思路与算法

很容易想到的方法是遍历,使用 22 个循环,很明显最多只能有 lenlen 次旋转,因为对称性,所以数组下标可能会 >=len>= len,所以要取余 (i+j)modlen(i+j) \mod len

每次旋转更新最大值,时间复杂度为 O(N2)O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// BF time: O(n^2) space: O(1)
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;
}

复杂度分析:

  • 时间复杂度:O(N2)O(N^2),其中 NN 是数组 nums\textit{nums} 的长度。

  • 空间复杂度:O(1)O(1)

方法二: 动态规划

思路与算法:

方法一会超时,其实观察旋转数组的变化:

F(0)=0×nums[0]+1×nums[1]++(n1)×nums[n1]F(0) = 0 \times nums[0] + 1 \times nums[1] + \ldots + (n-1) \times nums[n-1]

F(1)=1×nums[0]+2×nums[1]++0×nums[n1]=F(0)+i=0n1nums[i]n×nums[n1]F(1) = 1 \times nums[0] + 2 \times nums[1] + \ldots + 0 \times nums[n-1] = F(0) + \sum_{i=0}^{n-1}nums[i] - n \times nums[n-1]

我们很容易发现相邻旋转的递推关系:

F(k+1)=F(k)+i=0n1nums[i]n×nums[nk],0k<nF(k+1) = F(k) + \sum_{i=0}^{n-1}nums[i]-n \times nums[n-k], 0 \le k \lt n

F(0)F(0)出发,迭代计算出不同的F(k)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
// DP time: O(n) space: O(n)
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)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
// DP Opt time: O(n) space: O(1)
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;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中 NN 是数组的长度。

  • 空间复杂度:O(1)O(1)

方法三: 前缀和 + 滑动窗口

思路与算法:

因为需要旋转数组,可以将 numsnums 进行复制拼接,得到长度为 2n2n 的新数组,在新数组上任意一个长度为 nn 的滑动窗口都对应了一个旋转数组。

考虑在窗口的滑动过程中,计算结果会如何变化,假设当前我们处理到下标为 [i,i+n1][i, i+n-1] 的滑动窗口,当前结果为:

cur=nums[i]×0+nums[i+1]×1+...+nums[i+n1]×(n1)cur = nums[i] \times 0 + nums[i+1] \times 1 + ... + nums[i+n-1] \times (n-1)

当窗口往后移动一位,也就是窗口的右端点来到 i+ni+n 的位置,左端点来到 i+1i+1 的位置。

我们需要增加新右端点的值,即增加 nums[i+n]×(n1)nums[i+n] \times (n-1),同时减去旧左端点的值,即减少 nums[i]×0nums[i] \times 0,然后更新新旧窗口的公共部分 [i+1,i+n1][i + 1, i + n - 1]

不难发现,随着窗口的逐步右移,每一位公共部分的权值系数都会进行减一。

nums[i+1]×1+nums[i+2]×2+...+nums[i+n1]×(n1)nums[i+1] \times 1 + nums[i+2] \times 2 + ... + nums[i+n-1] \times (n-1)

变为

nums[i+1]×0+nums[i+2]×1+...+nums[i+n1]×(n2)nums[i+1] \times 0 + nums[i+2] \times 1 + ... + nums[i+n-1] \times (n-2)

因此,公共部分的差值为 idx=i+1i+n1nums[idx]\sum_{idx=i+1}^{i+n-1}nums[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;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中 NN 是数组的长度。

  • 空间复杂度:O(1)O(1)


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. 😉😃💗