题目来源:https://leetcode.com/problems/add-to-array-form-of-integer/description/

标记难度:Easy

提交次数:1/1

代码效率:144ms

题意

给定一个自然数的各个数位从左到右的数组表示和另一个自然数,求这两个数的和的数组表示。

分析

很简单的加法题的一个小变形。题解的做法跟我差不多:开一个新的数组(因为原来的表示方法不符合一般从右往左表示的规律),从最后一位开始加,最后再把数组倒过来。

代码

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
class Solution {
public:
vector<int> addToArrayForm(vector<int>& A, int K) {
vector<int> a;
a.push_back(0);
for (int i = A.size() - 1; i >= 0; i--) {
a.back() += A[i];
a.back() += K % 10;
K /= 10;
int x = a.back() / 10;
a.back() %= 10;
a.push_back(x);
}
while (K > 0) {
a.back() += K % 10;
K /= 10;
int x = a.back() / 10;
a.back() %= 10;
a.push_back(x);
}
while (a.size() > 1 && a.back() == 0) a.pop_back();
reverse(a.begin(), a.end());
return a;
}
};

题目来源:https://leetcode.com/problems/sum-of-even-numbers-after-queries/description/

标记难度:Easy

提交次数:1/1

代码效率:96ms

题意

给定一个数组A,对其中的数做以下操作:

  • 更新:A[index] += val
  • 查询:问A中所有偶数的和

分析

首先预处理出A中所有偶数的和,然后在每次更新的时候,对这个和相应地进行更新。总的来说是道水题……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
int n = A.size();
int sum = 0;
for (int i = 0; i < n; i++)
if (A[i] % 2 == 0)
sum += A[i];
vector<int> ans;
for (int i = 0; i < queries.size(); i++) {
int x = queries[i][0], k = queries[i][1];
if (A[k] % 2 == 0) {
if (x % 2 == 0) sum += x;
else sum -= A[k];
}
else {
if (x % 2 != 0) sum += A[k] + x;
}
A[k] += x;
ans.push_back(sum);
}
return ans;
}
};

题目来源:https://leetcode.com/problems/longest-turbulent-subarray/description/

标记难度:Easy

提交次数:1/1

代码效率:124ms

题意

给定一个正整数数组A,求其中满足turbulent性质的最长子数组的长度:

  • 满足A[i] > A[i+1] < A[i+2] > ... A[j]
  • A[i] < A[i+1] > A[i+2] < ... A[j]

(其实就是要上下波动。)

分析

我比赛时的想法很简单:维护两个数组updownup[i]表示以i为结尾且A[i-1]<A[i]的turbulent子数组最大长度,down[i]表示以i为结尾且A[i-1]>A[i]的turbulent子数组最大长度,然后交替进行递推。

其实这种做法有一些冗余,因为显然只有A[i-1]<A[i]up[i]才有意义(否则肯定只能取1);down[i]同理。题解里给出了一种维护这些关系的方法:把原来的数组丢掉,只留下两个数之间的相对关系。对于数组A = [9,4,2,10,7,8,8,1,9],令B为比较的结果,记大于号为1,小于号为-1,等号为0。因为A[0]=9 > 4=A[1],因此B[0]=1;因为A[1]=4 > 2=A[2],因此B[1]=1;因为A[2]=2 < 10=A[3],因此B[2]=-1;……[1]

以此类推,得到B = [1, 1, -1, 1, -1, 0, -1, 1]。此时我们只需要贪心地尝试把B分成若干个最长的1和-1交替的子序列即可,如[1], [1, -1, 1, -1], [0], [-1, 1]。因为此时B中的每个数表示的是A中两个数的关系,所以边缘处(重复)的数得到了比较好的处理:如[1]代表[9, 4][1, -1, 1, -1]代表[4, 2, 10, 7, 8][0]代表[8, 8][-1, 1]代表[8, 1, 9]

代码

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 maxTurbulenceSize(vector<int>& A) {
int n = A.size();
int up[n], down[n];
int ans = 0;
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
up[i] = down[i] = 1;
if (A[i] > A[i-1])
up[i] = down[i-1] + 1;
if (A[i] < A[i-1])
down[i] = up[i-1] + 1;
}
for (int i = 0; i < n; i++) {
ans = max(ans, up[i]);
ans = max(ans, down[i]);
}
return ans;
}
};

  1. Leetcode Offical Solution for 978. Longest Turbulent Subarray

题目来源: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://codeforces.com/contest/1102/problem/E

提交次数:1/1

题意

给定一个长度为n的数组a,要求为a生成一个对应的数组b,满足:

  • b[0] = 0
  • 对于任意0 <= i < j <= n,如果满足a[i] == a[j],必有b[i] == b[j](不过a[i] != a[j]时也可能有b[i] == b[j]
  • 任取0 <= i < n - 1,必有b[i] = b[i+1]b[i] + 1 = b[i+1]

问共有多少种可能的b

分析

显然b[i]是一个递增序列,因此可以自然推出,若a[i] == a[j],则必有b[i] == b[i+1] == ... = b[j],也就是说,对于a中任意位置两个相等的元素,它们在b中对应的是一整段相等的元素。显然这种元素相等是可能会发生重叠的,因此一个自然的想法就是,把重复的元素建模成线段,然后合并发生overlap的线段以得到相等元素的最长长度。

我的做法是,从后向前遍历a,如果发现当前元素和后面的元素重复了,则取index最靠后的元素,组成一条线段,插入到栈中与其他元素合并;否则把它自己的index作为一条线段插入到栈中。最后栈中留下的就是几条互不相交(且并组成了整个区间)的线段。

对于(除了第一条之外)每条线段,我们可以选择让它的值和前一条相等,也可以选择让它的值是前一条+1。每种选择都会导致生成一种新的b。于是结果是2^{线段数-1}

例子:对于a = {1, 2, 1, 2, 3},1对应的线段是[0, 2],2对应的线段是[1, 3],3对应的线段是[4, 4];合并之后得到两条线段,[0, 3][1, 4];只有两种b,分别是{0, 0, 0, 0, 0}{0, 0, 0, 0, 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int a[200005];
int n;

typedef long long int LL;
const LL P = 998244353;

LL pow2(LL x) {
LL pow = 2, ans = 1;
while (x > 0) {
if (x & 1)
ans = (ans * pow) % P;
pow = (pow * pow) % P;
x >>= 1;
}
return ans;
}

int main() {
map<int, int> indMap;
vector<pair<int, int>> s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (indMap.find(a[i]) == indMap.end()) {
indMap[a[i]] = i;
}
}
for (int i = n - 1; i >= 0; i--) {
pair<int, int> interval;
if (indMap.find(a[i]) != indMap.end() && indMap[a[i]] < i) {
interval = make_pair(indMap[a[i]], i);
}
else {
interval = make_pair(i, i);
}
if (!s.empty() && s.back().first <= interval.first && s.back().second >= interval.second)
continue;
if (!s.empty() && interval.second >= s.back().first) {
interval.second = s.back().second;
s.pop_back();
s.push_back(interval);
}
if (s.empty() || interval.second < s.back().first)
s.push_back(interval);
}


int cnt = 0;
if (!s.empty() && s.front().second < n - 1) cnt++;
if (!s.empty() && s.back().first > 0) cnt++;
for (int i = 0; i < s.size(); i++) {
cnt++;
// 本条线段和前一条线段之间的间隔
if (i > 0 && s[i - 1].second < s[i].first - 1)
cnt++;
}
cout << pow2(cnt - 1) << endl;
return 0;
}

题目来源:https://leetcode.com/problems/subarray-sums-divisible-by-k/description/

标记难度:Medium

提交次数:1/1

代码效率:60.00%(36ms)

题意

给定整数数组A,求所有满足和模K余0的子数组的数量。

分析

比赛的时候,我的做法是:依次扫描数组,求前缀和之后模N,从map里读出这个余数对应的前缀和数量,加到ans里,然后余数对应前缀和数量+1。原理非常简单,子数组和可以用前缀和之差来表示。需要注意的是,0也代表没有前缀时的和。

不过这么做其实并不本质。首先,前缀和模K是一个比较小的数,可以用数组来做(而不一定需要map)。其次,实际上求每种余数对应前缀和里取两个的结果就可以了!也就是直接用组合数去算。[1]

显然这么做更加本质。

(以及这让我发现了$\binom{n}{2} = \frac{n(n-1)}{2} = 1 + 2 + \cdots + (n-1)$这个事实,我火星了)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
map<int, int> cntMap;
int sum = 0, ans = 0;
cntMap[0]++;
for (int i = 0; i < A.size(); i++) {
sum += A[i];
int mod = (sum % K + K) % K;
if (cntMap[mod] > 0) ans += cntMap[mod];
cntMap[mod]++;
}
return ans;
}
};

  1. Leetcode Official Solution for 974

题目来源:https://leetcode.com/problems/pancake-sorting/description/

标记难度:Medium

提交次数:1/1

代码效率:8ms

题意

给定一个数组A(其中的元素是[1, 2, ..., A.length]的排列),定义pancake flip操作为翻转A中前k个数,其中k <= A.length。要求通过最多10 * A.length词操作将A排序。求操作序列。

分析

比赛的时候我的想法很简单:因为每次操作影响的只有前k个数,所以不妨考虑先排好A中靠后的数,这样之后的操作就不会影响它们。于是就可以得到一个很显然的思路:需要把i放到i位置时,就找到i,先通过一次操作把它flip到数组开头,再通过一次操作把它flip到i位置。这样,操作次数最多为2 * A.length,符合要求。

以序列[3, 1, 5, 2, 4]为例:

  • 将5放到第5位:
    • flip 3:[5, 1, 3, 2, 4]
    • flip 5:[4, 2, 3, 1, 5]
  • 将4放到第4位:
    • flip 1(不需要)
    • flip 4:[1, 3, 2, 4, 5]
  • 将3放到第3位:
    • flip 2:[3, 1, 2, 4, 5]
    • flip 3:[2, 1, 3, 4, 5]
  • 将2放到第2位:
    • flip 1(不需要)
    • flip 2:[1, 2, 3, 4, 5]
  • 将1放到第1位(已经在第1位了)

这是一种非常straightforward的方法,题解也是这么做的。

而且显然上述方法已经说明,flip操作能够将任意排列变换成其他任意排列。

我的问题是:

  1. 直接模拟的复杂度为O(N^2)(因为每次翻转操作的复杂度是O(N)),能否降低复杂度?
  2. 这样得到的是否为最优解?

第二个问题的答案是,显然不是,这种做法只是给出了一个上界(至多2*N - 3次翻转必然可以完成排序,至于为什么少了3次,请考虑只剩1和2时的情形)。而且找到最优解是一个NP-难问题。那么我就不再耗费我可怜的脑细胞在这个问题上了。顺便一提,比尔·盖茨证明了这个问题的上界是5(N+5) / 3;目前最优的结果是18N / 11[1]

经过一些思考和查找资料,我认为我目前无法回答第一个问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
vector<int> ans;
void flip(int k, vector<int>& A) {
for (int i = 0; i < k - i - 1; i++)
swap(A[i], A[k - i - 1]);
ans.push_back(k);
}

public:
vector<int> pancakeSort(vector<int>& A) {
int n = A.size();
for (int i = n; i >= 1; i--) {
// put i on place i
int index = 0;
while (A[index] != i && index < n) index++;
if (index == i - 1) continue;
flip(index + 1, A);
flip(i, A);
}
return ans;
}
};

  1. 原来Pancake Sorting这个名字并不是乱起的!wikipedia - Pancake sorting

题目来源:https://leetcode.com/problems/n-repeated-element-in-size-2n-array/description/

标记难度:Easy

提交次数:4/4

代码效率:

  • 排序:36ms
  • 计数:32ms
  • reduce:40ms
  • 随机:40ms

题意

有一个长度为2N的数组,其中有N+1个不同元素,且只有一个元素出现了N次。返回这个元素。

分析

比赛时我用的是最简单的方法,排序:排序之后直接比较前后的数是否相等。


排序可以说是最low的方法了(复杂度高达O(N^2)),但在比赛时根据KISS原则,这么写也是合理的。

用哈希表显然也可以做,方法十分简单,不多说了。

下一种方法基于一种有趣的观察,我称之为reduce:把一个整个数组的性质(N个重复数字,不妨设为x;其他N个数字都是不重复的)缩小到其中一部分元素的性质。在所有的长度为4的子序列中,其中必然至少有一个出现了两个x。原因是这样的:考虑把这个子序列分成两个长度为2的子序列:由鸽巢原理,其中必然至少有一个数字是x。但是单看长度为2的子序列是无法判断的(因为x只会出现N次,无法保证一定会出现包含两个x的子序列),所以只能看长度为4的子序列。如果至少有一个出现了两个x的长度为2的子序列,则包含这个子序列的长度为4的子序列必然也至少包含两个x;如果每个长度为2的子序列都只有一个x,那么仍然至少存在一个出现了两个x的长度为4的子序列。[1]

最后一种不太有趣的解法是随机。每次随机取两个元素,然后判断它们是否相等,不相等则继续找。

代码

排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
sort(A.begin(), A.end());
for (int i = 1; i < A.size(); i++) {
if (A[i-1] == A[i])
return A[i];
}
return -1;
}
};

计数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
unordered_set<int> s;
for (int x: A) {
if (s.find(x) != s.end()) return x;
s.insert(x);
}
return -1;
}
};

reduce

感觉还是写得有点复杂。不需要用这么多判断。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
for (int i = 0; i < A.size() - 3; i++) {
if (A[i] == A[i+1] || A[i] == A[i+2] || A[i] == A[i+3]) return A[i];
if (A[i+1] == A[i+2] || A[i+1] == A[i+3]) return A[i+1];
if (A[i+2] == A[i+3]) return A[i+2];
}
return -1;
}
};

随机

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
int N = A.size();
while (true) {
int i1 = rand() % N, i2 = rand() % N;
if (i1 == i2) continue;
if (A[i1] == A[i2]) return A[i1];
}
return -1;
}
};

  1. LeetCode Official Solution - 961. N-Repeated Element in Size 2N Array

题目来源:https://leetcode.com/problems/reveal-cards-in-increasing-order/description/

标记难度:Medium

提交次数:2/2

代码效率:8ms

题意

有一叠卡片,每张卡片上写着各不相同的数字。对卡片叠重复进行如下操作:

  • 拿出叠顶卡片,记录上面的值
  • (如果卡片叠非空)把下一张叠顶的卡片放到叠底

问把卡片以什么顺序叠放,才能使得记录的值是顺序递增的?

分析

其实这道题只要仔细想并不难。用映射的方法来解释比较好。不妨先假设我们拿的是一摞从上到下是1, 2, 3, 4, 5, 6, 7的卡片。进行操作(操作过程略)后,得到的值为1, 3, 5, 7, 4, 2, 6。因此,我们可以得到一张卡片在原来的叠中的index -> 卡片在记录的值中的index的映射表$\sigma$:

1 2 3 4 5 6 7
1 3 5 7 4 2 6

不妨假设我们的卡片开始时已经排好序了,也就是说,我们期望所有卡片在记录的值中的index顺序是1, 2, ..., 7。此时只需应用上述映射表的逆映射$\sigma^{-1}$,即可得到满足这种性质的卡片在原来的叠中应有的index顺序:

1 2 3 4 5 6 7
1 6 2 5 3 7 4

以及,我本来以为是要返回卡片index的一个order的——也就是说,我们还需要记录卡片排序前后的index映射表——吓死我了。原来直接返回卡片的值就好了。不过,这也不过是多加一个映射而已……

代码

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:
vector<int> deckRevealedIncreasing(vector<int>& deck) {
// get the mapping
queue<int> q;
int n = deck.size();
int ord2rev[n];
for (int i = 0; i < n; i++)
q.push(i);
for (int i = 0; i < n; i++) {
int x = q.front();
q.pop();
ord2rev[x] = i;
if (!q.empty()) {
x = q.front();
q.pop();
q.push(x);
}
}
// sort
sort(deck.begin(), deck.end());
// apply reversed mapping
vector<int> ans;
for (int i = 0; i < n; i++)
ans.push_back(deck[ord2rev[i]]);
return ans;
}
};

题目来源:https://leetcode.com/problems/minimum-increment-to-make-array-unique/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 排序:104ms
  • 计数:44ms

题意

给定一个数组A,可以对其中的数进行+1操作,返回能够使得A中所有元素两两不同的操作数量。

分析

这次比赛的题全都很简单,但是第三题我没有想出来……所以最后排名是248 / 3194。基本上彻底是拼手速了。


比赛的时候我的思路就是,先把A排序,然后按顺序判断当前的数是否还没被用过……如果没被用过就记录“下一个没被用的数”;否则将它设置为“下一个没被用的数”,并将这个数+1。然后这样想还是有些复杂;事实上直接和上一个数进行比较就可以了……(因为排序了)。[1]如果用类似于计数排序可以更快一些。[2]我感觉这有一点贪心的思路。

代码

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
if (A.size() == 0) return 0;
sort(A.begin(), A.end());
int minn = A[0] + 1;
long long int ans = 0;
for (int i = 1; i < A.size(); i++) {
if (A[i] < minn) {
ans += minn - A[i];
A[i] = minn++;
}
else
minn = A[i] + 1;
}
return ans;
}
};

计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int cnt[80005];
memset(cnt, 0, sizeof(cnt));
for (int x: A)
cnt[x]++;
long long int ans = 0;
for (int i = 0; i < 80003; i++) {
if (cnt[i] > 1) {
cnt[i]--;
ans += cnt[i];
cnt[i + 1] += cnt[i];
cnt[i] = 1;
}
}
return ans;
}
};

  1. lee215's solution for Leetcode 945 - [C++/Java/Python] Straight Forward

  2. official solution for Leetcode 945