题目来源:https://leetcode.com/problems/interval-list-intersections/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 奇怪的做法:28ms
  • 正常的合并:24ms

题意

AB两个闭区间数组,它们分别都是排过序的,且每个数组里的区间之间互不相交。请求出两个数组中闭区间的交。

分析

这道题的数据范围并不大(1000),所以我比赛的时候随便乱做了一下,也就过了。

不过正解是这样的:首先考虑最小的两个闭区间A[0]B[0],不失一般性,假设A[0]的右端点小于等于B[0]的右端点。由于B中的区间是互不相交的,因此A[0]只有可能与B[0]相交,不可能与B中其他的端点相交。因此我们可以在判断完后将A[0]丢掉,然后重新考虑新的AB的相交情况。于是就得到了一个O(N)的算法。[1]

代码

奇怪的做法

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
class Solution {
private:
bool intersect(Interval x1, Interval x2) {
if (x1.end < x2.start || x2.end < x1.start) return false;
return true;
}

pair<int, int> getIntsc(Interval x1, Interval x2) {
return make_pair(max(x1.start, x2.start), min(x1.end, x2.end));
}

public:
vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {
int start = 0;
int n = A.size(), m = B.size();
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
while (start < m && B[start].end < A[i].start && !intersect(A[i], B[start])) start++;
if (start >= m) break;
for (int j = start; j < m; j++)
if (intersect(A[i], B[j]))
a.push_back(getIntsc(A[i], B[j]));
else break;
}
sort(a.begin(), a.end());
vector<Interval> ans;
for (int i = 0; i < a.size(); i++)
ans.emplace_back(a[i].first, a[i].second);
return ans;
}
};

正常的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {
int i = 0, j = 0;
vector<Interval> ans;
while (i < A.size() && j < B.size()) {
if (A[i].end < B[j].start) i++;
else if (B[j].end < A[i].start) j++;
else {
ans.emplace_back(max(A[i].start, B[j].start), min(A[i].end, B[j].end));
if (A[i].end < B[j].end) i++;
else j++;
}
}
return ans;
}
};

  1. Leetcode Official Solution for 986

题目来源:https://leetcode.com/problems/squares-of-a-sorted-array/description/

标记难度:Easy

提交次数:2/3

代码效率:

  • 排序:124ms
  • 双指针:104ms

题意

给定一组已经排序了的整数,返回它们的平方排序后的结果。

分析

最简单的方法就是直接平方之后排序,复杂度是O(N^log(N))

复杂一点的话,就是利用这些整数已经排序了的条件,找到中间最靠近0的数,然后分别“合并”两边平方的大小。举个例子:对于[-3, -2, -1, 4, 5, 6],这么做相当于合并[-1, -2, -3][4, 5, 6]平方的结果。具体的实现方法也是用两个指针。[1]

代码

排序

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
vector<int> B;
for (int x: A)
B.push_back(x*x);
sort(B.begin(), B.end());
return B;
}
};

双指针

实现的时候需要稍微注意一下判断条件……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int n = A.size();
int i = 0;
while (i < n - 1 && A[i] < 0) i++;
if (A[i] > 0) i--;
int j = i + 1;
vector<int> ans;
while (i >= 0 || j < n) {
if (i < 0 || j < n && abs(A[i]) >= abs(A[j])) {
ans.push_back(A[j] * A[j]);
j++;
}
else if (j >= n || i >= 0 && abs(A[i]) <= abs(A[j])) {
ans.push_back(A[i] * A[i]);
i--;
}
}
return ans;
}
};

  1. Leetcode official solution for 977. Squares of a Sorted Array

题目来源:https://leetcode.com/problems/validate-stack-sequences/description/

标记难度:Medium

提交次数:1/1

代码效率:4ms

题意

你有两个属性:power和points(初始为0),并且有一些token,每个token自己有一个值(token[i])。你可以对一个token做如下两种操作之一(或者可以什么都不做):

  • face up:如果你的power >= token[i],则可以令power -= token[i],且points++
  • face down:如果你的points > 0,则可以令power += token[i],且points--

问你可以用这些token达到的最大points数量是多少。

分析

我当时想了好久,怎么平衡两类token的数量(并得到一个合法的操作序列)之类的。但总的来说肯定是这样的:为了最大化points,肯定face up的token的数量越多越好,face down的token的数量越少越好。那么显然需要face up的token的值尽可能小,face down的token的值尽可能大。虽然不知道贪心是不是对的,但不妨先写一个看看……嗯,过了。

贪心的思路就很直接,先把token排序,然后小token从小到大尝试置为face up,直到power不够位置;然后尝试把一个最大的token置为face down,再接着试剩下的小token,以此类推……

每次Leetcode出这样的题,题解里也不给个形式证明,就很烦。(事实上我感觉贪心几乎是所有算法题里唯一需要形式化证明算法正确性的。)我觉得这可以用stay ahead[1]方法:记算法的每一步操作为$A = {a_1, a_2, ..., a_k}$,最优解的每一步操作为$O = {o_1, o_2, ..., o_k}$;令$f(\cdot) = (points, power)$为量度函数,规定

$$(points_A, power_A) > (points_B, power_B) \iff \begin{cases} points_A > points_B \\ points_A = points_B, \quad power_A > power_B \end{cases} $$

(就是规定了一个std::pair出来……)

下面用数学归纳法证明$f(a_1, ..., a_r) \geq f(o_1, ..., o_r)$。对于第一步操作,由于贪心算法会尝试选择最小的token进行face down,如果能成功,则point数量会+1,且power数量减小最少,必然有$f(a_1) > f(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
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int P) {

int maxPoints = 0;

int n = tokens.size();
sort(tokens.begin(), tokens.end());
int i = 0, j = n - 1;
int power = P, points = 0;
while (i <= j) {
bool moved = false;
// small face up
while (tokens[i] <= power && i <= j) {
power -= tokens[i];
points++;
i++;
moved = true;
}
maxPoints = max(maxPoints, points);
if (i > j) break;
// big face down
if (points > 0) {
power += tokens[j];
points--;
j--;
moved = true;
}
if (!moved) break;
}
return maxPoints;
}
};

  1. CS 482 2003 - Proof Techniques: Greedy Stays Ahead

题目来源:https://leetcode.com/problems/3sum-with-multiplicity/description/

标记难度:Medium

提交次数:3/7

代码效率:

  • 计数:8ms
  • 2Sum:4ms

题意

给定整数数组Atarget,返回满足i < j < k, A[i] + A[j] + A[k] == target(i, j, k)数量。其中3 <= A.length <= 30000 <= A[i] <= 1000 <= target <= 300

分析

比赛的时候这道题挂了三次:

  • 没有判断k是否在[0, 100]范围内,所以RE了
  • 忘记A[i]的下限是0了,所以WA了
  • 数量计算的时候爆int了,所以又WA了

……


显然最暴力的做法就是直接枚举,时间复杂度是O(N^3)。当然,这样太暴力了。有两个主要的优化方向:

  • 根据0 <= A[i] <= 100进行去重
  • 根据2Sum或者3Sum的思路进行指针优化

由于数据规模的原因,去重的思路是很容易想到的。至于指针优化,它的思路大概是这样的:如果已经确定了(i, j),在i不变,j递增的情况下,如果合法的k存在,则k必然是递减的。所以只需要枚举(i, j)并通过这一方法确定k即可。当然,在本题使用去重的情况下,只要在hash表中直接查找target - i - j元素是否存在即可;不过这一思路仍然很有趣。[1]

代码

计数

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
class Solution {
public:
int threeSumMulti(vector<int>& A, int target) {
int n = A.size();
long long int cnt[101];
memset(cnt, 0, sizeof(cnt));
for (int i: A) cnt[i]++;
long long int ans = 0, MOD = 1000000007;
// different: i <= j <= k
for (int i = 0; i <= min(100, target); i++) {
if (!cnt[i]) continue;
for (int j = i; j <= 100 && i + j <= target && j <= target - i - j; j++) {
int k = target - i - j;
if (k > 100) continue;
if (!cnt[j] || !cnt[k]) continue;
if (i != j && j != k)
ans = (ans + cnt[i] * cnt[j] * cnt[k]) % MOD;
else if (i != j && j == k && cnt[j] >= 2)
ans = (ans + cnt[i] * cnt[j] * (cnt[j] - 1) / 2) % MOD;
else if (i == j && j != k && cnt[i] >= 2)
ans = (ans + cnt[i] * (cnt[i] - 1) * cnt[k] / 2) % MOD;
else if (i == j && j == k && cnt[i] >= 3)
ans = (ans + cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6) % MOD;
}
}
return ans;
}
};

2Sum

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
class Solution {
public:
int threeSumMulti(vector<int>& A, int target) {
int n = A.size();
int cnt[101];
long long int value[101];
int key[101], m;
memset(cnt, 0, sizeof(cnt));
for (int i: A) cnt[i]++;

m = 0;
for (int i = 0; i <= 100; i++) {
if (cnt[i]) {
key[m] = i;
value[m++] = cnt[i];
}
}

long long int ans = 0, MOD = 1000000007;
// different: i <= j <= k
for (int i = 0; i < m; i++) {
int k = m - 1;
for (int j = i; j <= k; j++) {
while (j <= k && key[i] + key[j] + key[k] > target) k--;
if (j > k) break;
if (key[i] + key[j] + key[k] < target) continue;
if (i < j && j < k) ans += value[i] * value[j] * value[k] % MOD;
else if (i == j && j < k) ans += (value[i] * (value[i] - 1) * value[k] / 2) % MOD;
else if (i < j && j == k) ans += (value[i] * value[j] * (value[j] - 1) / 2) % MOD;
else if (i == j && j == k) ans += (value[i] * (value[i] - 1) * (value[i] - 2) / 6) % MOD;
ans %= MOD;
}
}
return ans;
}
};

  1. Leetcode 923 - Official Solution

题目来源:https://leetcode.com/problems/sort-array-by-parity-ii/description/

标记难度:Easy

提交次数:2/2

代码效率:

  • 额外空间:96ms
  • 双指针:68ms

题意

有一个数组A,其中奇元素和偶元素的数量相等。请把A排序,使得奇元素位于奇数位置,偶元素位于偶数位置。任何满足上述条件的排序都是合法的。

分析

额外空间

需要额外空间的做法是非常简单的:再开一个数组B,维护evenodd指针,对于每一个A[i],根据它的奇偶性放到B中对应的位置。

双指针

事实上并不需要额外的空间,而仍然可以采用类似于快排的做法:用两个指针分别维护合法的奇序列和合法的偶序列的结束位置,将元素交换,直到排序完成。[1]

代码

额外空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
vector<int> B(A);
int odd = 1, even = 0;
for (int i = 0; i < A.size(); i++) {
if (A[i] % 2 == 1) {
B[odd] = A[i];
odd += 2;
}
else {
B[even] = A[i];
even += 2;
}
}
return B;
}
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int odd = 1, even = 0, n = A.size();
while (odd < n && even < n) {
while (odd < n && A[odd] % 2 == 1) odd += 2;
while (even < n && A[even] % 2 == 0) even += 2;
if (odd >= n || even >= n) break;
swap(A[odd], A[even]);
odd += 2;
even += 2;
}
return A;
}
};

  1. Leetcode 922 - Official Solution

题目来源:https://leetcode.com/problems/reverse-only-letters/description/

标记难度:Easy

提交次数:2/2

代码效率:

  • 双指针:0ms
  • 栈:4ms

题意

给定字符串S,将S中的字母逆序排列,其他部分保持不变。

分析

这次的排名是270 / 3528。我觉得这次题目的难度排序是1 < 3 < 2 < 4(为什么老有这种第3题比第2题简单的情况出现),而且第4题还比较简单(我感觉到是DP了,虽然不会做)。做出4道题的人一共67个(而且还真有做出来第4题而没做出第2题的人),比上次多一些。


本题显然很水。比赛时我的做法是直接用两个指针分别指向两侧的字母。另一种做法需要额外的空间,开一个栈,把字母顺序放进去再弹出。[1]

代码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
bool isAlpha(char c) {
return ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z');
}

public:
string reverseOnlyLetters(string S) {
int i = 0, j = S.length() - 1;
while (i < j) {
while (!isAlpha(S[i]) && i < j) i++;
while (!isAlpha(S[j]) && i < j) j--;
if (i >= j) break;
swap(S[i], S[j]);
i++, j--;
}
return S;
}
};

(非常简洁的写法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
bool isAlpha(char c) {
return ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z');
}

public:
string reverseOnlyLetters(string S) {
stack<char> s;
for (char c: S)
if (isAlpha(c))
s.push(c);
for (char& c: S)
if (isAlpha(c)) {
c = s.top();
s.pop();
}
return S;
}
};

  1. Leetcode 917 - Reverse Only Letters - Solution

题目来源:https://leetcode.com/problems/fruit-into-baskets/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 分块扫描:148ms
  • 滑动窗口:192ms

题意

给定数组tree,求其中最长的只包含两种元素的连续子序列的长度。

分析

分块扫描

比赛的时候我就是这么写的。


首先显然可以把这个数组按连续相同的元素分块。这样,相邻的两块所表示的元素必然就是不同的了。然后再考虑怎么求这种子序列。

以样例中的序列[3,3,3,1,2,1,1,2,3,3,4]为例,分块之后,即可得到

1
[(3, 3), (1, 1), (2, 1), (1, 2), (2, 1), (3, 2), (4, 1)]

首先尝试从(3, 3)开始寻找最长子序列。显然我们能够找到的是[(3, 3), (1, 1)]。此时下一个块对应的元素必然既不是3也不是1(或者也可能没有下一个块)。一个事实是,如果从这个最长子序列中的任意非最后一个元素开始寻找最长子序列,都必然会结束在当前的最后一个元素。所以下一次搜寻只需从当前最长子序列的最后一个元素开始。

于是之后从(1, 1)开始寻找,找到了[(1, 1), (2, 1), (1, 2), (2, 1)];再从(2, 1)开始寻找,找到了[(2, 1), (3, 2)];从(3, 2)开始寻找,找到了[(3, 2), (4, 1)];最后找到了[(4, 1)]。其中最长的子序列是从(1, 1)开始的。

滑动窗口

看了题解之后,我反而觉得这种想法更容易想。简单来说,令opt(j)表示以j结尾的最长合法子序列的首位坐标,则显然opt(j)是随j单调递增的。也就是说,[opt(j), j]形成了一个滑动窗口。

因此我们可以在遍历j的同时维护滑动窗口中各元素的数量,当元素种类超过2时,则将窗口下沿向前滑,并相应地删除元素,直到元素种类回到2。[1]

代码

分块扫描

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
class Solution {
public:
int totalFruit(vector<int>& tree) {
// 分块
vector<pair<int, int>> subs; // cnt, ele
int cnt = 0;
for (int i = 0; i < tree.size(); i++) {
if (i != 0 && tree[i - 1] != tree[i]) {
subs.emplace_back(cnt, tree[i - 1]);
cnt = 0;
}
cnt++;
}
if (cnt != 0)
subs.emplace_back(cnt, tree.back());

// 进行扫描
// eleSet中存储的是当前找到的元素
unordered_set<int> eleSet;
int i = 0;
int curSum = 0;
int ans = -1;
while (i < subs.size()) {
while (i < subs.size() && eleSet.size() <= 2) {
int cnt = subs[i].first;
int ele = subs[i].second;

if (eleSet.find(ele) == eleSet.end() && eleSet.size() == 2)
break;
if (eleSet.find(ele) == eleSet.end())
eleSet.insert(ele);
curSum += cnt;
i++;
}
ans = max(ans, curSum);
curSum = 0;
eleSet.clear();
// 如果扫描已经完成则不再回退
if (i >= subs.size())
break;
// 回退1,重新开始扫描
i--;
}
return ans;
}
};

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int totalFruit(vector<int>& tree) {
int start = 0; // 窗口前沿
unordered_map<int, int> cntMap;
int maxn = -1;
// 遍历窗口后沿
for (int i = 0; i < tree.size(); i++) {
cntMap[tree[i]]++;
// 维护窗口中元素种类
while (cntMap.size() > 2) {
cntMap[tree[start]]--;
if (cntMap[tree[start]] == 0)
cntMap.erase(tree[start]);
start++;
}
maxn = max(maxn, i - start + 1);
}
return maxn;
}
};

  1. Leetcode 904 Solution

题目来源:https://leetcode.com/problems/sort-array-by-parity/description/

标记难度:Easy

提交次数:3/3

代码效率:

  • 平凡的遍历:44ms
  • 平凡的排序:36ms
  • 不平凡的双指针:28ms

题意

给定整数数组A,要求将A中元素重排,使得所有偶数元素在前,奇数元素在后。

分析

这次比赛的题目整体又比较简单。所以我的排名又变高了,变成了271 / 4385(最近几次比赛人好像越来越多了,是错觉吗?)。做出来三道题;最后一题我也想出了几乎正确的做法,就是懒得写了。


一种平凡的做法:两次遍历

比赛的时候我就是这么写的。新开一个vector,先遍历A一次,把偶数元素都插入到里面;再遍历A一次,这次只插入奇数元素。时间复杂度是O(n),额外空间复杂度是O(n)

另一种平凡的做法:重写排序比较器

好吧,这种做法倒也没有那么平凡。重写一个排序的比较器,使得偶数都小于奇数,而偶数之间都相等。然后就可以直接把A排序了。时间复杂度是O(n * log(n)),额外空间复杂度是O(1)[1]

不太平凡的做法:双指针

仍然和快排的想法是类似的。不过我的代码里似乎仍然写了太多的特判,还是这份代码比较好。[2]

代码

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
vector<int> ans;
for (int x: A)
if (x % 2 == 0)
ans.push_back(x);
for (int x: A)
if (x % 2 != 0)
ans.push_back(x);
return ans;
}
};

排序

再一次回到了如何使用自己的比较器进行std::sort的这个问题中。此时你不止需要一个函数,还需要一个函数对象,把这个函数放到重载的()运算符中。[3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
struct {
bool operator()(const int& x, const int& y) const
{
return x % 2 < y % 2;
}
} Cmp;

public:
vector<int> sortArrayByParity(vector<int>& A) {
// https://en.cppreference.com/w/cpp/algorithm/sort
sort(A.begin(), A.end(), Cmp);
return A;
}
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
int i = 0, j = 0;
int n = A.size();

while (i < n && A[i] % 2 == 0) i++;
j = i;
while (j < n && A[j] % 2 != 0) j++;

while (i < n && j < n) {
swap(A[i], A[j]);
while (i < n && A[i] % 2 == 0) i++;
while (j < n && A[j] % 2 != 0) j++;
}

return A;
}
};

  1. Leetcode 905 Solution

  2. [C++/Java] In Place Swap

  3. Cpp Reference: std::sort

题目来源:https://leetcode.com/problems/boats-to-save-people/description/

标记难度:Medium

提交次数:1/1

代码效率:25.56%

题意

给定若干个人的重量,以及一条船的载重限制,一条船上最多载两个人,且总重量不能超过载重限制,问至少需要多少条船运载所有人。

分析

一种证明贪心算法正确的方法

一道非常简单(经典)的贪心问题,但我却被这样的一个问题困扰住了:对于当前重量最大的人,为何我们寻找的匹配是当前重量最小的人,而不是所有可能的匹配中重量最大的人?

当然,寻找当前重量最小的匹配方法是正确的。6 lines Java O(nlogn) code, sorting + greedy, with greedy algorithm proof. 中提供了一份形式化的证明,翻译如下(作为贪心算法证明方法的参考):

S表示一种最优解(显然,由于优化目标只是船的数量,最优解可能不止有一种),O表示我们的算法输出的解。

  1. 贪心选择性质(greedy choice property):选择只需依赖于当前情形,不需要依赖于未来的选择和子问题的其他解。

从最沉的人hi开始,有2种可能的情况:

(a) 如果hi不能和其他任何人进入同一艘船,则在SO中,hi都独自处于一艘船中。显然,在这种情况下,我们的这一选择是最优的,贪心选择性质维持不变。

(b) 如果hi可以和其他某一个人进入一艘船,则在O中,根据我们的算法,hi和最轻的人lo必然位于同一条船上。

S中,如果他们也在同一条船上,则我们的这一步骤是最优的,贪心选择性质保持不变;如果他们不在同一条船上,则我们可以把hilo在船上的同伴m交换一下。显然,m <= hi,因此交换是可以进行的。因为交换没有导致船变多,我们得到了一个新的最优解T,且在这种解中,hilo在同一条船上。这表明,我们的第一个步骤——把hilo放进同一条船中——是一个最优步骤,贪心选择性质也维持不变。

  1. 最优子结构性质(optimal substructure property):对原问题的最优解必然包含对子问题的最优解

P表示规模为n的原问题,其中n = people.length。从上述推导中,可以看出,在第一步之后,我们得到了一个子问题P',规模为n'(如果hi独自占据一艘船,则n' = n - 1,否则n' = n - 2)。我们可以相似地对P'中的hi'lo'进行和刚才一样的操作。

由于我们已经证明了,T也是一种最优解,且P'的解(不妨称之为O')包含在T内,也是一种最优解,所以这一问题具有最优子结构性质。

综上,我们的算法符合贪心选择性质和最优子结构性质,证毕。


好吧,我之前并不知道贪心算法的这两种性质。按照算法导论上的说法,这两种性质实际上是用来分析问题的——只有证明问题具有这两种性质时,才能确定可以应用贪心算法。而在此处的证明里,作者把实际的解法也混在证明过程中了。而“证明问题符合贪心的两种性质”和“证明贪心算法的正确性”本质上是两个问题。事实上,此处作者的证明策略应该叫做“exchange arguments”。Proof methods and greedy algorithms这篇文章中包含了对两种策略的详细论述。

对于上述贪心算法的另一种理解

在开始查找这些资料之前,我尝试从直觉上去理解这种算法的重要性,并且确实找到了一种理解方法。

由于有一条船上最多坐两个人的限制,在这种算法下,实际上,我们是在为那些weight > floor(limit/2)的人寻找配对的,能坐在同一条船里的人;结束寻找之后,那些weight <= floor(limit/2)的人之间则可以随意组合。

把所有的人按重量排序,记mid = floor(limit/2)+1

1
| 0 | 1 | ... | mid-1 | mid | ... | n-1 |

显然,此时最重的人能够配对的人是最少的,次重的人能够配对的人可能会稍微多一些。记最重的人能够配对的人的位置区间为[0, r_1],次重的人能够配对的人的位置区间为[0, r_2]……直到[0, r_mid]。显然,r_1 <= r_2 <= ... <= r_mid

现在我们实际上是在做这样一件事:从上述整数区间中选择一些点,使得它们具有这样的性质:

  • 每个人只能在自己对应的区间中选点
  • 点不能重复选择

我们的目的是最大化能选到点的人的数量。

此时,将最重的人与最轻的人匹配(假如他们能够匹配)的做法就很好理解了:我们实际上是为他选择了对应的线段中(还没被选择过的)最靠前的一个点。而“所有可能的匹配中重量最大的人”相当于是选择了线段上(还没被选择过的)最靠后的一个点。

对于这两种算法,不能找到匹配的情况都满足r_i < i。所以这两种算法本质上是一样的。


我感觉我的证明能力不是很强。以后再遇到贪心问题的时候,我也会尝试去做一下问题的贪心性质和贪心算法的正确性这两种证明的。

在Leetcode上的英文回答

https://leetcode.com/problems/boats-to-save-people/discuss/156748/Python-short-2-pointer-solution-and-some-thoughts/166286

In short: I think both "smallest" and "possibly maximum" methods are correct, and they are in some way equivalent.

Another person has provided a formal proof for the "smallest" selection method. (6 lines Java O(nlogn) code, sorting + greedy, with greedy algorithm proof. ) Of course, that method is correct, but this might not be immediately obvious. So I'd like to share my understanding of this problem with you. (So it's not a formal proof.)

Let mid = floor(limit/2), and divide those people into two groups: 'heavy' people, whose weight > mid; and 'light' people, whose weight <= mid. Minimizing the number of boats is equivalent to maximizing the number of boats with two people in them. It is obvious that, if a 'heavy' person wants to sit in a boat with another person, the other person must be a 'light' one; on the other hand, a 'light' person can certainly sit with another 'light' person, and maybe some of the 'heavy' people.

Now, a solution is at hand: we first try to pair each 'heavy' person with a 'light' person, and put them in a boat; when a 'heavy' person can't find a pair, we put him alone in a boat; finally, if there are any 'light' person left, we can arbitrarily pair them together. The biggest question is, how can we maximize these 'heavy'-'light' pairs?

Sort all the people in ascending order. Let n = people.length, and suppose there are altogether m heavy people, denoted by people[n-m], people[n-m+1], ... people[n-1]. After sorting, the 'light' people that a 'heavy' person can pair with will form a interval. Denote these intervals by [0, r_{n-m}), [0, r_{n-m+1}), ..., [0, r_{n-1}). (Intervals might be empty)

Example: limit = 8, people = [2, 3, 3, 5, 6, 7]

In this example, heavy = [5, 6, 7], light =[2, 3, 3]`.

  • For 7, the interval is [0, 0) (no one can sit with 7);
  • For 6, the interval is [0, 1) (2 can sit with 6);
  • For 5, the interval is [0, 3) ([2, 3, 3] can all sit with 5).

And it is obvious that r_{n-m} >= r_{n-m+1} >= ... >= r_{n-1} >= 0. So these intervals are all overlapping, and the left endpoints are all zero.

Now we can analyze the difference between "smallest" and "possibly maximum" methods. When we choose the "smallest" person, we are choosing the leftmost point of the interval (which hasn't be chosen yet); when we choose the "possibly maximum" person, we are choosing the rightmost point of the interval (which hasn't be chosen yet).

Because all intervals has 0 as the left endpoint, when we start from the heaviest person, only when r_k < k (k is the number of 'heavy' people we have considered or is considering) can this 'heavy' person not find a 'light' person to pair. So, in these two methods, we find different 'light' people for the 'heavy' people to pair, but the set of 'heavy' people who cannot find a pair is the same.

Example: limit = 8, people = [1, 2, 2, 2, 3, 4, 5, 6, 7, 7]

people[i] k interval "smallest" pair "possibly maximum" pair
people[9] = 7 1 [0, 1) 1 1
people[8] = 7 2 [0, 1) - -
people[7] = 6 3 [0, 4) 2 2
people[6] = 5 4 [0, 5) 2 3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int i = 0, j = people.size() - 1, sum = 0;
while (i < j) {
while (i < j && people[i] + people[j] > limit) {
j--;
sum++;
}
i++;
j--;
sum++;
}
if (i == j)
sum++;
return sum;
}
};

题目来源:https://leetcode.com/problems/merge-sorted-array/description/

标记难度:Easy

提交次数:1/1

代码效率:

  • 非原地版本:98.65%
  • 原地版本:98.65%

题意

合并两个已排序的数组,把排序结果存放到第一个数组中(保证空间足够)。

分析

这是一道水题。不过其实需要一点点的思考。非原址的合并方法完全不需要思考。但是如果要求原址合并,那么从前向后合并会导致合并结果会覆盖第一个数组的数据。那么从后向前合并就可以了。被覆盖的数据必然是已经移动过的。这种操作数组的思路倒是有点类似于快排。

代码

非原地版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 不知道怎么进行原址merge,干脆新开一个vector
// 从后向前应该可以保证不冲突?
vector<int> nums3;
int i = 0, j = 0;
while (i < m && j < n) {
if (nums1[i] < nums2[j])
nums3.push_back(nums1[i++]);
else
nums3.push_back(nums2[j++]);
}
while (i < m)
nums3.push_back(nums1[i++]);
while (j < n)
nums3.push_back(nums2[j++]);
for (int k = 0; k < nums3.size(); k++)
nums1[k] = nums3[k];
}
};

原地版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums3;
int i = m - 1, j = n - 1, end = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j])
nums1[end--] = nums1[i--];
else
nums1[end--] = nums2[j--];
}
while (j >= 0)
nums1[end--] = nums2[j--];
}
};