题目来源:https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/

标记难度:Hard

提交次数:1/1

代码效率:

  • 递推:47.81%
  • 数学:100.00%

题意

给定数字集合D(即D是集合{'1','2','3','4','5','6','7','8','9'}的子集)和正整数N,问用这些数字共能组成多少<=N的数。

分析

我想,第一个问题是,这到底是一个统计问题,还是一个计算问题。考虑到N的范围,显然不能直接遍历所有数进行统计,而是需要进行某种程度的计算。也许会涉及到组合数。(虽然事实是没有)

第二个问题是正着做还是反着做——计算包含这些数字的数的个数,还是计算不只包含这些数字的数的个数?显然我比赛的时候完全没有想清楚这一点,但就这道题来说,大概计算包含更简单一点。

最后一个问题是怎么算。显然我比赛的时候懵逼了,没想出来。“包含X数字的数”也许不算是一种常见的题型,但用非统计的方法计算在某个范围内符合某条件的数的数量似乎还挺常见的(如Leetcode 866)。但我觉得这些题目之间的共性并不大。


递推方法

如何寻找<=N的合法的数?显然可以根据数的长度进行分类讨论。[1]对于长度小于len(N)的那些,显然D中数字的任意组合均是合法的(这一点我之前居然没有意识到……);对于长度和len(N)相等的那些,则需要分类讨论:

  • 如果该数首位比N的首位小,则之后的数字可以任意组合;如果该数首位和N的首位相等(当然前提是N的首位也是一个合法数字),则需要继续讨论第2位
  • 如果该数第2位比N的第2位小,则之后的数字可以任意组合;如果该数第2位和N的第2位相等(当然前提是N的第2位也是一个合法数字),则需要继续讨论第3位
  • 以此类推……

于是我们就得到了一个递推算法:令f[i]表示<= N[i:]的数的数量(i从1开始编号),则

1
f[i] = (number of digits < N[i]) * (D.size)^(len - i) + (N[i] in D) * f[i + 1]

且最终的结果为

1
f[1] + (D.size)^(len - 1) + (D.size)^(len - 2) + ... + D.size

数学方法

这是一种很神奇的方法。我们不妨把D中的数字看成是一种新的进位表示。比如,当D = {1, 3, 5}时,就可以把[11, 13, 51, 53]这类的数写成[11, 12, 31, 32]。如果能够知道<= N的最大的这种进位表示,就可以直接计算合法的数的数量了。所以剩下的问题就是怎么找到这个进位表示。

一种方法是根据N的位,从高位到低位分别进行讨论。令B表示所需的进位表示,1 <= B[i] <= D.size, 1 <= i <= len(N)

  • 如果N[i] in D && N[i] = D[j],则B[i] = j
  • 如果N[i] > min(D),则B[i] = lower_bound(D, N[i])B[i+1:] = len(D),结束
  • 如果N[i] < min(D),则B[i] = 0,并对之前的数执行类似于退位的操作,B[i+1:] = len(D),结束

其他情况是比较显然的。一个需要退位的例子:D = {2, 4, 6, 8}N = 41265

  1. B[1] = 2, "4"
  2. B[2] = 0;执行退位操作后,B[1] = 1, B[2] = 4, B[3:5] = 4, "28888"

找到这个进位表示之后就可以直接计算出比它小的数的数量了。事实上这种表示方法类似于Leetcode 171,同样没有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
class Solution {
private:
// 递归快速幂
long long quickpow(long long a, int x) {
if (x == 0) return 1;
long long int b = quickpow(a, x >> 1);
return x % 2 == 0 ? b * b : b * b * a;
}

public:
int atMostNGivenDigitSet(vector<string>& D, int N) {
bool valid[10];
memset(valid, 0, sizeof(valid));
for (string str: D)
valid[str[0] - '0'] = true;

int x = 0;
for (int i = 0; i < 10; i++)
if (valid[i]) x++;

// 递推过程
long long int f = 1;
int digits = 0;
while (N > 0) {
if (!valid[N % 10])
f = 0;
int y = 0;
for (int i = 0; i < N % 10; i++)
if (valid[i]) y++;
f += y * quickpow(x, digits);

N /= 10;
digits++;
}

for (int i = 1; i < digits; i++)
f += quickpow(x, i);

return f;
}
};

数学

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
class Solution {
public:
int atMostNGivenDigitSet(vector<string>& D, int N) {
vector<int> digits;
while (N > 0) {
digits.push_back(N % 10);
N /= 10;
}
reverse(digits.begin(), digits.end());
vector<int> digSet;
for (string str: D)
digSet.push_back(stoi(str));

int n = digits.size();
int B = D.size();
vector<int> b(n, 0);
for (int i = 0; i < digits.size(); i++) {
int k;
// 本来用的是set,后来我实在搞不明白lower_bound和distance那套理论了
// 反正数据量比较小……
for (k = 0; k < digSet.size(); k++)
if (digits[i] < digSet[k])
break;

// digit[i] < min(D)
if (k == 0) {
b[i] = 0;
// 退位
for (int j = i; j > 0; j--) {
if (b[j] == 0) {
b[j-1]--;
b[j] = B;
}
else break;
}
for (int j = i + 1; j < n; j++)
b[j] = B;
break;
}
// digit[i] > min(D) with no match
else if (digSet[k - 1] < digits[i]) {
b[i] = k;
for (int j = i + 1; j < n; j++)
b[j] = B;
break;
}
// find match
else if (digSet[k - 1] == digits[i])
b[i] = k;
}

long long int cnt = 0;
for (int d: b) {
cnt = cnt * B + d;
}
return cnt;
}
};

  1. Leetcode 902 Solution

题目来源:https://leetcode.com/problems/decode-string/description/

标记难度:Medium

提交次数:1/1

代码效率:

  • 递归版本:100.00%
  • 栈版本:100.00%
  • 正则表达式版本:0.00%

题意

给定一个形如"3[a2[c]]"的字符串,要求将其展开为accaccacc格式。

分析

递归寻找[]中间的字符串,将其递归展开后,将返回的字符串重复规定的次数。大致就是这么一个思路。我觉得需要注意的细节包括:

  • 注意一些不需要递归展开的部分
  • 注意字符串操作中的边界

用递归的方法相当于用栈。也许用栈直接做会更直接和节省时间一些。[1]

另一种神奇的做法是用正则表达式,直接找出形如cnt[str]的字符串并展开。[2]我尝试用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
class Solution {
private:
bool isDigit(char x) {
return '0' <= x && x <= '9';
}

public:
string decodeString(string s) {
if (s.length() == 0)
return "";
int leftBrackets = 0, rightBrackets = 0, k = 0, start = -1, end = -1;
string startStr, multStr, addStr;
int i = 0, n = s.length();
while (!isDigit(s[i]) && s[i] != '[' && i < n)
i++;
if (i >= n) return s;
startStr = s.substr(0, i);
while (isDigit(s[i]) && i < n) {
k = k * 10 + s[i] - '0';
i++;
}
start = i;
while ((leftBrackets == 0 || leftBrackets != rightBrackets) && i < n) {
if (s[i] == '[')
leftBrackets++;
if (s[i] == ']')
rightBrackets++;
i++;
}
end = i - 1;

// cout << "s=" << s << " k=" << k << " startStr=" << startStr << " start=" << start << " end=" << end << endl;

multStr = s.substr(start + 1, end - start - 1);
addStr = s.substr(i, n - i);
multStr = decodeString(multStr);
addStr = decodeString(addStr);

string str(startStr);
for (int i = 0; i < k; i++)
str += multStr;
str += addStr;
return str;
}
};

栈版本

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
class Solution {
public:
string decodeString(string s) {
// 把这两个栈分开的思路不错
stack<int> cntStack;
stack<string> strStack;
int cnt = 0;
string str;
for (char ch: s) {
if ('0' <= ch && ch <= '9') {
cnt = cnt * 10 + ch - '0';
// 把之前不在重复范围内的字符串入栈
if (str.length() != 0) {
strStack.push(str);
str = "";
}
}
else if (ch == '[') {
cntStack.push(cnt);
cnt = 0;
strStack.push("["); // 需要了解右括号对应的范围
}
else if (ch == ']') {
// 把范围内的字符串都弹出来,可能有不止一块
while (true) {
if (strStack.top() == "[") {
strStack.pop();
break;
}
str = strStack.top() + str;
strStack.pop();
}
cnt = cntStack.top();
cntStack.pop();
string rep;
for (int i = 0; i < cnt; i++) rep += str;

cnt = 0;
str = "";
strStack.push(rep);
}
else
str += ch;
}

while (!strStack.empty()) {
str = strStack.top() + str;
strStack.pop();
}
return str;
}
};

正则表达式版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
string decodeString(string s) {
smatch m;
regex r("(\\d+)\\[([^\\[^\\]]*)\\]");
while (regex_search(s, m, r)) {
int cnt = stoi(m.format("$1"));
string str = m.format("$2");
string rep;
for (int i = 0; i < cnt; i++)
rep += str;
s = m.prefix().str() + rep + m.suffix().str();
}
return s;
}
};

  1. Simple Java Solution using Stack

  2. 3 lines Python, 2 lines Ruby, regular expression