算法leetcode

力扣1388-3n块披萨

字数统计: 2.8k字   |   阅读时长: 12分
, , ,

摘要: 一个困难题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一下第 22 场双周赛 D 题。本题通过猜想和证明，可以规约为打家劫舍问题：从 n 个元素的环上选最优的 n / 3 个不相邻的元素。

此外从 n 个点选不相邻的 k 个，最优解是贪心的做法，用堆维护每个时刻最大的点，在双向循环链表上进行贪心模拟，但是证明比较难难。

$1 题目

1388. 3n 块披萨

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

  • 你挑选 任意 一块披萨。
  • Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
  • Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
  • 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

1
2
3
1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000

示例 1：
输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：
输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

示例 3：
输入：slices = [4,1,2,5,8,3,1,9,7]
输出：21

示例 4：
输入：slices = [3,1,2]
输出：3

$2 题解

问题规约：环形数组上取不相邻子序列

有两条显然的事实：

  1. 你拿的块数一定是 n / 3，因为 n % 3 == 0。
  2. 无论何时，你无法拿相邻的两块。

在以上两条的基础上，可以猜想一个比较大胆的结论：在 n 块中任意 n / 3 个不相邻的块均可以做得到。

证明方法可以用构造性证明，即对应任意 n / 3 个不相邻块，实实在在举出一个可以拿到的办法。从而拿到任意 n / 3 个不相邻快的办法一定存在。

有一串长为 n 的 01 串，其中有 n / 3 个不相邻的 1，下面构造一种方法将这 n / 3 个 1 全都拿到。

  • 首先根据两条显然事实，这个 01 串一定可以划分成若干个 01 交替的串，且边界一定是 0。
  • 其次在边界是 0 的情况下，始终取走边上的 1，取走后，相邻的 1 旁边一定还是 0，该 0 可能属于划分好的另一段(此时两段合并成了1段)，也可能不属于任何一段，如图

构造方法

始终取走边上的 1 的取法可以持续进行下去，直到所有段合并成了1个段并且取完。

因此 n 个当中一定能取到任何不相邻的 n / 3 个。

问题变成了：n 个元素的环上取 n / 3 个不相邻元素，如何取到最大。取不相邻元素如何取到最大，可以参考 打家劫舍：不相邻子序列最大和问题。

算法1：动态规划

在环上处理取不相邻元素取到最大的问题，可以参考 环形 DP。类似地，因为首尾不可同时取，本题也可以先将尾去掉，然后做一次非环上问题，再将头去掉，再做一次非环上问题，两次做的结果取最大。

对于非环上问题，状态定义为 $dp[i][k]$ 表示考虑到 $i$，$num[0..i]$ 上选取 $k$ 个不相邻元素，可以渠道的最大值。

其中 $i$ 是阶段，$k$ 为附加信息。这样定义的话，目标为 $dp[n - 1][n / 3]$，边界值为 $dp[0][0] = 0, dp[0][1] = nums[0], dp[1][0] = 0, dp[1][1] = \max(nums[0], nums[1])$，当 k > (i + 2) / 2 时，dp[i][k] = 0。

下面考虑状态转移方程，依然分为选和不选 $nums[i]$ 来考虑：

  • 如果选 $nums[i]$，那么 $nums[i - 1]$ 就不能选，且附加信息 $k$ 会加 1，$dp[i][k] = nums[i] + dp[i - 2][k - 1]$。
  • 如果不选 $nums[i]$，那么 $nums[i - 1]$ 可选可不选，且附加信息 $k$ 保持不变，$dp[i][k] = dp[i - 1][k]$

综合考虑，状态转移方程如下：

代码(C++)

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
26
class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        int ans1 = solve(slices, 0, n - 2, n / 3);
        int ans2 = solve(slices, 1, n - 1, n / 3);
        return max(ans1, ans2);
    }

private:
    int solve(const vector<int>& nums, int left, int right, int K)
    {
        int n = right - left + 1;
        vector<vector<int>> dp(n, vector<int>(K + 1, 0));
        dp[0][1] = nums[left];
        dp[1][1] = max(nums[left], nums[left + 1]);
        for(int i = 2; i < n; ++i)
        {
            for(int k = 1; k <= min((i + 2) / 2, K); ++k)
            {
                dp[i][k] = max(nums[left + i] + dp[i - 2][k - 1], dp[i - 1][k]);
            }
        }
        return dp[n - 1][K];
    }
};

算法2：贪心、模拟、堆+双向循环链表

N 个点取不相邻的最优的 K 个，贪心的做法可以到 $O(N\log N)$，比 DP 的 $O(NK)$ 好，但是证明比较难。

首先考虑 $K = 2$。基本的贪心想法是取最大的两个，如果最大的两个不相邻，则直接取最大的两个是对的，但是两个最大的相邻时就错了，因为不能取相邻的，

所以直接取最大的两个这个贪心做法是错的。但是以此为起点可以进一步往下考虑。

假如是在数组 a 中选最大的两个，记最大的数的位置是 $i$。结论：两个数的和最大的位置有两种情况：

  1. $i$ 和另一个不相邻的 $j$ (虽然 $a[j]$ 不一定是次大，但是 a[j] > a[i-1] + a[i+1] - a[i])。
    2, $i + 1$ 和 $i - 1$ (虽然 $a[i]$ 最大，但次大与 $$hi 相邻, 且其余的元素中没有比 a[i-1] + a[i+1] - a[i] 更大的了`)。

若两数和不是上面两种情况之一，记和最大的两个数为 $a[k], a[l]$。

  • 若 $k, l$ 均与 $i$ 不相邻，则将 $i$ 和任意一个互换，结果都不会更差。
  • 若 $k, l$ 其中之一与 $i$ 不相邻，则将 $i$ 和不相邻的那个互换，结果也不会更差。

因此 2 个数和最大的位置的两种情况的结论正确。2 可以推广到 k，这个的证明比较难。

基于上述结论，在 n 个中选不相邻的 n / 3 个可以有以下算法：

  1. 选 $n / 3$ 次，每次选最大的点 $i$，同时将 $i - 1, i + 1$ 也取出。
  2. 在 $i$ 位置放回一个新点，值为 a[i-1] + a[i+1] - a[i]，参考结论第 2 条。下一步若选了放回的点，则相当于选了 $i - 1$ 和 $i + 1$，这可以理解为一种后悔机制，先选最大的 $i$，一般是对的，但是如果 $i - 1$ 和 $i + 1$ 更好，下一步就可以后悔。

维护以上贪心模拟过程的要点如下：

  • 每次取出 3 个点，放回 1 个点，需要 O(1) 插入删除。因此可以用双向循环链表，堆中放节点指针，删除的时候需要标记已删，因为堆中可能还有指针指向那个节点。
  • 每次选择最大的 $i$，用一个最大堆维护，在弹出时需要判断弹出的指针是否已经被删。
  • i 位置的点可以不做删除，只修改值，i - 1 和 i + 1 需要删掉，并且标记已删。

代码(C++)

链表部分与 【模板】双向链表 中的代码模板完全一样。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
// 链表

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;

struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
private:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(DLTypeNULL);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    bool insertHead(DLType val)
    {
        if(isFull())
            return false;
        insert(head, val);
        return true;
    }

    bool insertTail(DLType val)
    {
        if(isFull())
            return false;
        insert(tail, val);
        return true;
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};

// 堆

struct HeapNode
{
    int x;
    DLNode* it;
    HeapNode(){}
    HeapNode(int x, DLNode* it):x(x),it(it){}
};

struct Cmp
{
    bool operator()(const HeapNode& a1, const HeapNode& a2) const
    {
        return a1.x < a2.x;
    }
};

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();

        DoubleCircleList dclist;
        for(int i: slices) 
            dclist.insertTail(i);

        priority_queue<HeapNode, vector<HeapNode>, Cmp> pq;
        DLNode *it = dclist.get_head();
        for(int i = 0; i < n; ++i)
        {
            it = dclist.get_next(it);
            pq.push(HeapNode(it -> val, it));
        }

        unordered_set<DLNode*> deletelist; // 标记删除
        int result = 0;
        for(int i = 0; i < n / 3; ++i)
        {
            // 堆头的 DLNode 可能已经被删除
            while(deletelist.count(pq.top().it) > 0)
            {
                pq.pop();
            }

            DLNode *cur = pq.top().it;
            pq.pop();

            result += cur -> val;

            int new_val = - cur -> val;
            DLNode *it_left = dclist.get_prev(cur), *it_right = dclist.get_next(cur);
            if(dclist.is_head(it_left)) 
                it_left = dclist.get_prev(it_left);
            if(dclist.is_head(it_right)) 
                it_right = dclist.get_next(it_right);
            new_val += it_left -> val + it_right -> val;

            dclist.remove(it_left);
            deletelist.insert(it_left);
            dclist.remove(it_right);
            deletelist.insert(it_right);
            dclist.change(cur, new_val);
            //dclist.traverse();
            pq.push(HeapNode(new_val, cur));
        }
        return result;
    }
};
Share