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

标记难度:Medium

提交次数:1/2

代码效率:112ms(40.00%)

题意

给定一个wordlist,其中包含了若干个单词(只包含英文字母的字符串),给定一系列query,要求从wordlist中找出匹配单词:

  • 如果wordlist中包含单词与该query相同,则直接返回query
  • 如果在不考虑大小写的情况下,wordlist中包含单词与该query相同(例:"AbC""aBc"是相同的),则返回第一个匹配单词
  • 如果在不考虑大小写和将所有元音字母认为是同一个字母的情况下,wordlist中包含单词与该query相同(例:"Aab""eIb"是相同的),则返回第一个匹配单词

分析

首先一个事实是,O(N*M)N = wordlist.size()M = queries.size())的算法是过不了的,因为N, M <= 5000。那么显然就要用到哈希表了。

  • 首先用一个set<string> exact存储原来的单词
  • 然后用一个map<string, int> lower存储每个单词的lowercase版本到它的索引,如果一个lowercase版本对应多个单词,则只存储第一个出现的单词的索引
  • 然后用一个map<string, int> vowel存储每个单词的lowercase且把所有元音都替换成"a"的版本到它的索引,如果一个替换后的版本对应多个单词,则只存储第一个出现的单词的索引
  • 最后,对于每一个query,分别在这三个结构里查找,如果查到则立刻返回,否则最后返回""

总的来说也不是很难。我WA了一次,主要是因为没看清,替换元音字母的同时也要替换大小写……

代码

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
class Solution {
private:
string toLower(string x) {
string l;
for (char ch: x)
l += 'A' <= ch && ch <= 'Z' ? ch - 'A' + 'a' : ch;
return l;
}

string toVowel(string x) {
string v;
for (char ch: x)
v += ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 'a' : ch;
return v;
}

public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
set<string> exact;
map<string, int> lower;
map<string, int> vowel;
for (int i = 0; i < wordlist.size(); i++) {
exact.insert(wordlist[i]);
string l = toLower(wordlist[i]);
if (lower.find(l) == lower.end())
lower[l] = i;
string v = toVowel(l);
if (vowel.find(v) == vowel.end())
vowel[v] = i;
}

vector<string> ans;
for (string x: queries) {
string l = toLower(x);
string v = toVowel(l);
if (exact.find(x) != exact.end())
ans.push_back(x);
else if (lower.find(l) != lower.end())
ans.push_back(wordlist[lower[l]]);
else if (vowel.find(v) != vowel.end())
ans.push_back(wordlist[vowel[v]]);
else
ans.push_back("");
}
return ans;
}
};

题目来源:https://leetcode.com/problems/stamping-the-sequence/description/

标记难度:Hard

提交次数:1/1

代码效率:36ms

题意

有一个stamp序列,可以通过不断使它覆盖一个序列的某一部分构造新的序列。问某个序列能否以这种方式构造。

分析

比赛的时候我觉得这道题应该用Trie之类的方法来做。没想到正解是贪心……?


题目里限定的是,最多可以进行10 * target.length次stamp,但是事实上每个位置最多只需要进行一次stamp(如果stamp两次,则后来的stamp会彻底覆盖前一次),因此最多需要的stamp次数是source.length - target.length

一种方法是贪心:每次尝试unstamp掉一块序列,直到整个序列被unstamp完为止。[1]不过我不知道怎么证明贪心的正确性……

另一种方法来自lee215,因为他现在转移到简书写中文题解了,所以我就不再在这里赘述了,不过的确是一种很好的做法。[2]

代码

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
class Solution {
bool checkStamp(int index, const string& stamp, const string& target) {
for (int i = 0; i < stamp.size(); i++) {
if (index + i > target.size()) return false;
if (stamp[i] != target[index + i] && target[index + i] != '?') return false;
}
return true;
}

bool checkIsOk(const string& target) {
for (char ch: target)
if (ch != '?')
return false;
return true;
}

public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> ops;
int N = target.size(), M = stamp.size();
int cnt = 0;
bool stamped[N - M + 1];
memset(stamped, 0, sizeof(stamped));
bool found, ok;
while (cnt <= N - M) {
found = false, ok = false;
for (int i = 0; i <= N - M; i++)
if (!stamped[i] && checkStamp(i, stamp, target)) {
for (int j = 0; j < M; j++) target[i + j] = '?';
stamped[i] = true;
ops.push_back(i);
cnt++;
found = true;
if (checkIsOk(target)) {
ok = true;
break;
}
}
if (ok) break;
if (!found) break;
}
if (ok) {
reverse(ops.begin(), ops.end());
return ops;
}
else
return {};
}
};

  1. Leetcode 936 Solution by zym3008 - [Python] Reverse + Greedy O(N^2M) (w/ Explanation)

  2. Leetcode 936 Stamping The Sequence - 题解

题目来源:https://leetcode.com/problems/unique-email-addresses/description/

标记难度:Easy

提交次数:1/1

代码效率:36ms

题意

给定一系列email地址,求满足以下要求的不重复地址数量:

  • 将email地址分成local name和domain name,形如:local-name@domain-name
  • 数据保证每个地址中有且仅有一个@字符
  • local name中的.字符应被忽略
  • local name中的+字符及其后所有字符应被忽略

分析

我这次比赛的最终排名是62 / 3652。但事实上我把前4题都做出来的时候,live排名是三百多名,这听起来就很奇怪了。总之,这次比赛的确比较简单……以及这次比赛第一名是clw


至于这道题……随便用字符串搞一下就可以了,然后去个重,我就不仔细思考了。

代码

搞了个像状态机一样的东西逐字符处理;不过我觉得还是使用find和split更好。事实上我在场上又忘了字符串处理函数具体怎么用了。

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
class Solution {
public:
int numUniqueEmails(vector<string>& emails) {
set<string> uniqueEmails;
for (string email: emails) {
string local;
string domain;
int status = 0;
// 0: not found + / @;
// 1: found +;
// 2: found @
for (char x: email) {
if (x == '+') {
if (status == 0)
status = 1;
else if (status == 2)
domain += x;
}
else if (x == '.') {
if (status == 0 || status == 1) continue;
if (status == 2) domain += x;
}
else if (x == '@')
status = 2;
else {
if (status == 0) local += x;
else if (status == 2) domain += x;
}
}
// cout << local + '@' + domain << endl;
uniqueEmails.insert(local + '@' + domain);
}
return uniqueEmails.size();
}
};

题目来源:https://leetcode.com/problems/long-pressed-name/description/

标记难度:Easy

提交次数:2/2

代码效率:

  • 暴力的做法:4ms
  • 不太暴力的做法:0ms

题意

有一个叫name的字符串,你在把它录入电脑的时候可能会把某个字母连续重复若干遍(相当于你“长按”了那个按键),问typed串是否有可能是这样形成的。

分析

应当庆祝一下,这次比赛中第一次把所有题都做出来了(当然也是因为题水)。最后得到的排名是128 / 3209,充分说明是题太水了。而且我第三题因为MLE的罚时太多了。不过今天不知道Leetcode是不是出了什么问题,现在官方题解仍未出现。

(虽然我知道我还是很菜,但是我很久以前就写过了,要接受自己的菜然后努力去提升,别人怎么样我是不管的。)


我比赛的时候的做法就是把两个字符串都做了一个连续字符的压缩,然后对压缩之后的结果进行比较。这个方法比较暴力。当然,也可以不那么暴力,也就是不把这个过程显式地写出来。[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 {
public:
bool isLongPressedName(string name, string typed) {
vector<pair<char, int>> press1, press2;
for (char ch: name) {
if (press1.size() == 0 || press1.back().first != ch)
press1.emplace_back(ch, 1);
else
press1.back().second++;
}
for (char ch: typed) {
if (press2.size() == 0 || press2.back().first != ch)
press2.emplace_back(ch, 1);
else
press2.back().second++;
}
if (press1.size() != press2.size()) return false;
for (int i = 0; i < press1.size(); i++)
if (press1[i] > press2[i])
return false;
return true;
}
};

不太暴力的做法

参考了[1]中的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool isLongPressedName(string name, string typed) {
int n = name.size(), m = typed.size();
if (n > m) return false;
int i = 0, j = 0;
while (i < n || j < m) {
if (i < n && typed[j] == name[i]) i++, j++;
else if (i > 0 && typed[j] == name[i - 1]) j++;
else break;
}
if (i == n && j == m) return true;
return false;
}
};

  1. Leetcode 925 Solution by votrubac - C++ 2 lines accepted and 5 lines accurate

题目来源: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/word-subsets/description/

标记难度:Medium

提交次数:1/1

代码效率:176ms

题意

给定字符串数组AB,如果字符串b中每个字符的出现次数都<=该字符在a中的出现次数,则称ba的子集。如果对于B中的每个字符串bb都是a的子集,则称a为“universal”。问A中有多少个字符串是“universal”的。

分析

这道题也非常简单。如果a是“universal”的,说明

$$\forall b \in B, \forall char, count_{char}(a) \geq count_{char}(b)$$

$$\forall char, \forall b \in B, count_{char}(a) \geq count_{char}(b)$$

$$\forall char, count_{char}(a) \geq \max_{\forall b \in B}{count_{char}(b)}$$

只要a满足以上条件就可以了。[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
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
int allb[26], b[26], a[26];
memset(allb, 0, sizeof(allb));
for (string bs: B) {
memset(b, 0, sizeof(b));
for (char ch: bs)
b[ch - 'a']++;
for (int i = 0; i < 26; i++)
allb[i] = max(allb[i], b[i]);
}

vector<string> ans;
for (string as: A) {
memset(a, 0, sizeof(a));
for (char ch: as)
a[ch - 'a']++;
bool ok = true;
for (int i = 0; i < 26; i++)
if (a[i] < allb[i]) {
ok = false;
break;
}
if (ok)
ans.push_back(as);
}
return ans;
}
};

  1. Leetcode 916 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