交替放置的玻璃杯题解

题目1: 交替放置的玻璃杯#

有2n个玻璃杯挨个排成一排，前n个装满苏打水，其余n个杯子为空。交换杯子的位置，使之按照满—空—满—空的模式排列，而且杯子移动的次数要最少

这道题目不在力扣里哦，提示：用分治法求解。

题目理解#

我们可以发现：

目标状态的下标存在规律
- 杯满为偶数，杯空为奇数
要达到目标状态，只需要交换绿色线连着的两个杯子
两端的杯子必定在正确的位置，从1和 $2n-2$ 开始，每隔一个杯子就不在正确的位置
最少的交换次数为 $\lfloor n/2 \rfloor$

Method 1 双指针#

使用左右指针分别从两边向中间逼近，交换杯子

伪代码#

1
1. 初始化l=1, r=2n-2
2
2. 不断循环交换杯子，记录交换次数，l+=2,r+=2
3
3. return 交换次数

时空复杂度分析#

时间复杂度：实际上两个指针相遇即可退出循环，循环次数为 $n/2$ ，所以时间复杂度为 $O(n)$
空间复杂度：只需维护一个string数组，大小为 $2n$ ，所以空间复杂度也为 $O(n)$

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 20010;
4
string cups[N];// full的index应该为偶数，empty的index应该为奇数
5
int n;
6
int swap_cups()
7
{
8
    int res = 0;
9
    int l = 1, r = 2 * n - 2;
10
    while (l < n && r >= n)
11
    {
12
        swap(cups[l], cups[r]);
13
        l += 2, r -= 2;
14
        res ++ ;
15
    }
16
    return res;
17
}
18
int main()
19
{
20
    int res;
21
    cin >> n;
22
    for (int i = 0; i < n; i ++ )   cups[i] = "full";
23
    for (int i = n; i < 2 * n; i ++ ) cups[i] = "empty";
24

25
    res = swap_cups();
26
    cout << res << endl;
27
    for (int i = 0; i < 2 * n; i ++ )
28
        cout << cups[i] << " ";
29
    return 0;
30
}

Method 2 分治#

base case#

n = 1时自动满足满-空
n = 2时只需交换中间两个杯子

general#

T(n) = \begin{cases} 0 & n = 0\\ 1 & n = 1\\ T(n - 2)+1 & n \geq 2 \end{cases}

时空复杂度分析#

时间复杂度： $O(n)$
空间复杂度： $O(n)$

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 20010;
6
string cups[N];// full的index应该为偶数，empty的index应该为奇数
7

8
int n;
9

10
int swap_cups_divide(int l, int r)
11
{
12
    if (l >= r) return 0;
13

14
    swap(cups[l], cups[r]);
15
    return swap_cups_divide(l + 2, r - 2) + 1;
16
}
17

18
int main()
19
{
20
    int res;
21
    cin >> n;
22
    for (int i = 0; i < n; i ++ )   cups[i] = "full";
23
    for (int i = n; i < 2 * n; i ++ ) cups[i] = "empty";
24

25
    res = swap_cups_divide(1, 2 * n - 2);
26
    cout << res << endl;
27
    for (int i = 0; i < 2 * n; i ++ )
28
        cout << cups[i] << " ";
29
    return 0;
30
}

音乐

Lovely firefly!

音乐

交替放置的玻璃杯题解

题目1: 交替放置的玻璃杯#

题目理解#

Method 1 双指针#

伪代码#

时空复杂度分析#

代码#

Method 2 分治#

base case#

general#

时空复杂度分析#

代码#

文章分享

评论区

音乐

目录