题目来源:https://leetcode.com/problems/number-of-squareful-arrays/description/

标记难度:Hard

提交次数:1/1

代码效率:36.82%(12ms)

题意

给定数组A,问有多少种A的排列,使得任意两个相邻元素的和都是平方数。认为两种排列不等当且仅当存在某个位置的元素不等(而不是把不同index的相同元素认为是不同的)。

分析

这又是一道“虽然看起来好像应该用状态DP做但因为数据量太小了所以不如直接DFS搜索”的题。既然我都写了DP了,现在实在懒得去写DFS,就这样好了。

代码

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
class Solution {
private:
bool isSquare(int x) {
int s = (int) sqrt(x);
if (s*s == x) return true;
return false;
}

int f[1 << 12][12];
vector<int> A;
bool ok[12][12];
int n;

int calc(int state, int end) {
if (f[state][end] != -1) return f[state][end];
if (!(state & (1 << end))) {
f[state][end] = 0;
return 0;
}
if (__builtin_popcount(state) == 1) {
f[state][end] = 1;
return 1;
}
f[state][end] = 0;
for (int i = 0; i < n; i++) {
if (i == end || !ok[i][end] || !(state & (1 << i))) continue;
f[state][end] += calc(state ^ (1 << end), i);
}
return f[state][end];
}

int factorial(int x) {
int ans = 1;
while (x > 0) {
ans *= x;
x--;
}
return ans;
}

public:
int numSquarefulPerms(vector<int>& A) {
sort(A.begin(), A.end());
this->A = A;
n = A.size();
for (int i = 0; i < n; i++) {
ok[i][i] = false;
for (int j = i + 1; j < n; j++) {
if (isSquare(A[i] + A[j]))
ok[i][j] = ok[j][i] = true;
else
ok[i][j] = ok[j][i] = false;
}
}

memset(f, -1, sizeof(f));
int ans = 0;
for (int i = 0; i < n; i++)
ans += calc((1 << n) - 1, i);

map<int, int> cnt;
for (int x: A) cnt[x]++;
for (auto p: cnt) ans /= factorial(p.second);

return ans;
}
};

题目来源:https://leetcode.com/problems/generate-parentheses/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • DFS:100.00%(0ms)
  • DP:100.00%(0ms)

题意

生成所有括号对数为n的合法小括号组合。

分析

我最开始以为用普通的迭代就可以解决(每次在已经生成的组合之后加一对括号或者套上一对括号),后来发觉好像不太对,所以就改为用DFS(或者说回溯):记录已经添加的左括号和右括号的数量,然后加上左括号,或者在右括号总数不超过左括号总数的前提下加上右括号。这样就可以不重不漏地生成所有结果了。

另一种比较有趣的方法类似于递推(大概也更容易计算数量):对于每个合法括号序列,考虑和左侧第一个左括号配对的右括号的位置。这对括号内部一定是一个合法括号序列,后面跟着的也是一个合法括号序列。然后枚举就可以了。[1]

这样肯定可以推导出合法括号序列的数量的……好像就是卡特兰数。Leetcode 894. All Possible Full Binary Trees的思路和这道题很类似,而且确实是卡特兰数……

代码

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
void dfs(int left, int right, string s, vector<string>& ans, int& n) {
if (left == n && right == n) {
ans.push_back(s);
return;
}
if (left < n) dfs(left + 1, right, s + '(', ans, n);
if (right < left) dfs(left, right + 1, s + ')', ans, n);
}

public:
vector<string> generateParenthesis(int n) {
if (n == 0) return {};
vector<string> ans;
dfs(0, 0, "", ans, n);
return ans;
}
};

DP

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:
map<int, vector<string>> pMap;

public:
vector<string> generateParenthesis(int n) {
if (pMap.find(n) != pMap.end()) return pMap[n];
if (n == 0) {
pMap[n] = {""};
return pMap[n];
}
vector<string> a;
for (int i = 0; i <= n - 1; i += 1) {
vector<string> in = generateParenthesis(i);
vector<string> back = generateParenthesis(n - i - 1);
for (string x: in)
for (string y: back)
a.push_back("(" + x + ")" + y);
}
pMap[n] = a;
return a;
}
};

  1. [https://leetcode.com/problems/generate-parentheses/solution/](Leetcode Official Solution for 22. Generate Parentheses)

题目来源:https://leetcode.com/problems/binary-watch/description/

标记难度:Easy

提交次数:1/1

代码效率:100%

题意

有一个二进制LED表,用6个LED灯(1, 2, 4, 8, 16, 32)表示分钟(0-59),4个LED灯(1, 2, 4, 8)表示小时(0-11)。给定共有多少个LED灯是亮的,求所有可能表示的时间。

分析

显然我们可以用搜索来解决这个问题:枚举小时表示中有多少个LED灯是亮的,然后找出所有可能的组合,最后拼在一起。3ms Java Solution Using Backtracking and Idea of "Permutation and Combination"使用的就是这一解法,非常直接。

但是由于时间表示本身的性质(就像在Leetcode 539中说的那样,一天其实只有24*60=1440分钟,24*600*60=86400秒),我们可以写出一种更简单的枚举方法:直接枚举每天的所有时间,然后计算该时间表示中1的数量是否符合要求就可以了。

于是我们又可以用__builtin_popcount了。除此之外,在Straight-forward 6-line c++ solution, no need to explain中,我看到了另一种计算方法:

1
int num = bitset<10>(x).count();

类模板bitset表示一个N位的固定大小序列。可以用标准逻辑运算符操作位集,并将它与字符串和整数相互转换。[1]

这也是个不错的方法(特别是记不住__builtin_popcount的全名的时候),不过我猜测效率会慢一些,毕竟是STL。

代码

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<string> readBinaryWatch(int num) {
if (num > 8)
return {};

int hours[4] = {1, 2, 4, 8};
int minutes[6] = {1, 2, 4, 8, 16, 32};

vector<string> times;
for (int hour = 0; hour < 12; hour++)
for (int minute = 0; minute < 60; minute++) {
if (__builtin_popcount(hour) + __builtin_popcount(minute) == num) {
string time = to_string(hour) + ":";
if (minute < 10)
time += "0";
time += to_string(minute);
times.push_back(time);
}
}

return times;
}
};

  1. std::bitset

题目来源:https://leetcode.com/problems/subsets-ii/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 直接回溯:100.00%
  • 迭代:23.82%

题意

找出一个数组中所有可能的子集。(可能有重复元素)

分析

这道题无论怎样都能搞出来,但是有一些做法比其他做法更加巧妙。我开始时的做法是这样的:先统计重复元素的个数,然后直接DFS。但事实上根本没有这样做的必要:把数组排序之后,重复元素会自动聚合在一起;由于所有的结果都是必须的,DFS也不一定必要。事实上我们可以迭代地构造这些子集:[a_1, a_m]的所有子集必然分为两种,一种是[a1, a_{m-1}]的所有子集,另一种是[a1, a_{m-1}]的所有子集中加上a_m。(C++ solution and explanation

另一种思路甚至更加有趣。显然我们在这个问题中需要避免的是重复的子集;那么何时会出现重复的子集呢?在迭代式的构造方法中,当之前添加过的元素和当前元素相同时,就会出现重复。但我们可以直接在迭代过程中规避这个问题:当前元素和前一元素重复时,我们只对当前集合中添加了前一元素的一半继续进行复制和添加操作,不再重复对前一半进行相同的操作。(Simple iterative solution

最后,如果数组为空,按照标准答案,我们应该返回一个空集。但实际上我认为应该返回一个含有空集的集合……所以我在题目中报了个错

代码

直接回溯

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
class Solution {
private:
vector<vector<int>> ans;
vector<pair<int, int>> diverseNum;

void dfs(int i, vector<int>& u) {
if (i >= diverseNum.size()) {
ans.push_back(u);
return;
}
for (int j = 0; j <= diverseNum[i].second; j++) {
for (int k = 1; k <= j; k++)
u.push_back(diverseNum[i].first);
dfs(i + 1, u);
for (int k = 1; k <= j; k++)
u.pop_back();
}
}

public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
// 这道题的复杂度可以说是比较高了
// 既然可能有duplicate,就先用map统计元素个数,然后枚举subset

// 空集的子集?
if (nums.size() == 0)
return ans;

map<int, int> freq;
for (int num: nums)
freq[num]++;

for (auto const& i: freq)
diverseNum.push_back(make_pair(i.first, i.second));

vector<int> u;
dfs(0, u);

return ans;
}
};

迭代

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 {

public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> subsets;
if (nums.size() == 0)
return subsets;
subsets.push_back(vector<int>());
sort(nums.begin(), nums.end());
int lastIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (i == 0 || nums[i] != nums[i - 1])
lastIndex = 0;
int size = subsets.size();
for (int j = lastIndex; j < size; j++) {
subsets.push_back(subsets[j]);
subsets.back().push_back(nums[i]);
}
lastIndex = size;
}
return subsets;
}
};

题目来源:https://leetcode.com/problems/permutations/description/

标记难度:Medium

提交次数:3/4

代码效率:

  • next_permutation版本:99.91%
  • 回溯法:99.92%
  • Heap算法:99.92%
  • Steinhaus–Johnson–Trotter算法:……懒得写了

题意

计算若干整数全排序,整数两两不同。

分析

STL版本

直接用STL中提供的next_permutation可能是最简单的一种方式了。但是,值得注意的是,在开始使用这个函数之前,需要把数组排序。

回溯法版本

用回溯法直接做也是一种思路,而且并不太难。

显然我基本已经把我的C++忘光了(或者说我就没有好好学过STL和模板)。C++ vector的push_back函数使用的是相应的拷贝构造函数,所以不需要再单独复制一次vector。

Heap算法

可能是效率最高的排列算法之一。好吧,我一时搞不清楚这个算法了,但是按照维基百科的思路,应该很好写……

Steinhaus–Johnson–Trotter算法

之前读《组合数学》的时候曾经看到过这个算法,是一种很有趣的思路——虽然在开始做这道题之前,我已经把具体的算法给忘光了。……算了,现在懒得写了。

代码

STL版本

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end()); // 如果使用next_permutation(),是需要排序的
do {
vector<int> x(nums);
ans.push_back(x);
} while (next_permutation(nums.begin(), nums.end()));
return ans;
}
};

回溯法版本

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
class Solution {
private:
vector<vector<int>> ans;

void dfs(vector<int>& perm, vector<int>& nums, vector<bool> used) {
if (perm.size() == nums.size()) {
vector<int> tmp(perm); // 事实上没有必要
ans.push_back(tmp);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) {
used[i] = true;
perm.push_back(nums[i]);
dfs(perm, nums, used);
perm.pop_back();
used[i] = false;
}
}
}

public:
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
vector<int> perm;
dfs(perm, nums, used);
return ans;
}
};

Heap算法

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 {
private:
vector<vector<int>> ans;

void generate(int n, vector<int>& nums) {
if (n == 1) {
ans.push_back(nums);
return;
}
for (int i = 0; i < n - 1; i++) {
generate(n-1, nums);
if (n % 2 == 0)
swap(nums[i], nums[n-1]);
else
swap(nums[0], nums[n-1]);
}
generate(n - 1, nums);
}

public:
vector<vector<int>> permute(vector<int>& nums) {
generate(nums.size(), nums);
return ans;
}
};

题目来源:https://leetcode.com/problems/restore-ip-addresses/description/

标记难度:Medium

提交次数:1/3

代码效率:9.95%

题意

把一个数字串用小数点分隔成4段,问共能形成多少个合法的IP地址。

分析

这就是一个简单的搜索题,但是需要注意两个边界条件:

  • 每一段的数字必须在0-255之间
  • 数字不能有前导0

以及,做题过程中大概会用到两个函数:

代码

我这个代码实在写得太繁琐了。与其用4层循环,还不如稍微简化一下……

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
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
// 看起来像是简单的搜索问题。一个IP地址的一段只能是0-255,因此长度最多为3
// 中间可以进行剪枝
// 不知道有没有什么奇怪的边界情况
// 果然是有的,比如不应该有前导0
// 以及是否需要去重?
// 事实说明不需要。
vector<string> ans;
int len[4], byte[4];

// 因为模板的原因,必须cast成int?
for (len[0] = 1; len[0] <= min(3, (int) s.length()); len[0]++) {
byte[0] = stoi(s.substr(0, len[0]));
if (byte[0] > 255)
continue;
// 考虑前导0问题
if (len[0] > 1 && s[0] == '0')
continue;

for (len[1] = 1; len[1] <= min(3, (int) s.length() - len[0]); len[1]++) {
byte[1] = stoi(s.substr(len[0], len[1]));
if (byte[1] > 255)
continue;
if (len[1] > 1 && s[len[0]] == '0')
continue;

for (len[2] = 1; len[2] <= min(3, (int) s.length() - len[0] - len[1]); len[2]++) {
byte[2] = stoi(s.substr(len[0] + len[1], len[2]));
if (byte[2] > 255)
continue;
if (len[2] > 1 && s[len[0]+len[1]] == '0')
continue;

len[3] = s.length() - len[0] - len[1] - len[2];
// 除了要考虑位数不够的情况,也要考虑位数太多的情况,这也是不合法的
if (len[3] <= 0 || len[3] > 3)
continue;
byte[3] = stoi(s.substr(len[0] + len[1] + len[2], len[3]));
if (byte[3] > 255)
continue;
if (len[3] > 1 && s[len[0]+len[1]+len[2]] == '0')
continue;

string ip = s.substr(0, len[0]) + "." + s.substr(len[0], len[1]) + "." +
s.substr(len[0] + len[1], len[2]) + "." + s.substr(len[0] + len[1] + len[2], len[3]);
ans.push_back(ip);
// cout << ip << endl;
}
}
}

return ans;
}
};