Exawizards的OA解题思路
0. 前言
在5.24号的时候，赶在Exawizards（后面简称E社）的实习报名的deadline前一天提交了ES并成功通过了，申请的岗位是MLE（CV相关）。ES包含了介绍自己的为什么能够胜任这份工作，目前拥有的技能以及简单介绍一下自己的研究。提交完ES后还需要提交一份日语能力证明，我提交的是在大学闲暇时间考的N2证书。
1. Modify the string
在这一题中，你需要根据给定的字符串，找出能够使得字母顺序最大的，不重复字符组成的字符串。 例子：”aabcb” 输出：”acb” 解释：在这个字符串中因为第二个a字符后还有一个字符，所以第一个a从原有的字符串中删除得到”abcb”。然后a在这个字符串中就是不重复的字符，因此会保留下来。找到第二个字符b，因为b在结尾处也有，因此只需要二选一，那么选择的标准就是使得字符串的顺序最大。什么是顺序最大呢，就是按照英文字母的顺序，越到后面，排序越大。那么因为第一个b后面的字母是c，所以第一个b要删除，保留最后一个b，从而保证字符串的顺序最大。结果就是”acb”
1.1 解题方法和思路
这道题可以使用贪心+栈的思路。首先使用counter来统计字符串中的所有字母的个数，和使用一个集合来存储已经看过的字符确保字符串的独特性。 贪心的公式就是：通过遍历每一个字符，如果这个字符在集合中，那么来判断它是否比集合中最后一个字符大，而且最后一个字符后面还有，就删除最后一个，如果不在集合中，那么做存储操作。在例如在例子中，会先将第二个和第三个字符存储到集合中就是”a”, “b”,当遍历到第四个字符的时候，发现”c”比集合中最后一个字符 “b” 要大，并且 “b”在后续的字符串中仍存在，因此将 “b”删除，存 “c”。
1.2 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import Counter
def getString(input_str):
counter = Counter(input_str)
seen = set()
res = []
for i, ch in enumerate(input_str):
counter[ch] -= 1
if ch in seen:
continue
# 如果当前字符比最后一个字符大，而且最后一个字符后面还有，就删除最后一个
while res and ch > res[-1] and counter[res[-1]] > 0:
seen.remove(res.pop())
res.append(ch)
seen.add(ch)
return ''.join(res)
1.3 时间复杂度和空间复杂度
空间复杂度
- Counter: 最多存储26个英文字母 -> O(1)
- seen: 最多存储26个英文字母 -> O(1)
- res: 最多保留n个字符 -> O(n)
- 一共O(n)
时间复杂度
- Counter: 统计每一个字符出现的次数 -> O(n)
- for 循环 -> O(n)
- while 循环中: 每一个字符最多只会进出栈一次，所以总共最多 O(n) 次 pop + push
- join操作 -> O(n)
- 一共O(n)
2 Count binary strings
在这一题中，给定的字符串中只有包含0和1，找到所有的子串的数量，使得子串中的0和1的数量要相同，并且0和1需要组合在一起. 例子: “011001” 输出: 4 解释: 满足条件的所有子串有: “01” “1100” “00” “10” 这里面的 “1001”因为 “1”不是组合在一起的，没有满足条件。
2.1 解体方法和思路
这道题使用的是 贪心+数组遍历。 首先我们可以对字符串进行分块，通过计算连续相同字符的数目来分块。具体来说就是对于一个形如字符串 “011001”, 对其分块的操作[1, 2, 2, 1]，列表中的数字就表示字符重复的数量。 这题的贪心公式: 比较相邻两个组的最小值，累加得到最终结果。
所以res = min(1,2) + min(2, 2) + min(2,1) = 1 + 2 + 1 = 4
2.2 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def count_binary_string(s: str) -> int:
count = 1
group = []
# 对字符串分块
for i in range(1, len(s)):
if s[i] == s[i - 1]:
count += 1
else:
group.append(count)
count = 1
group.append(count)
#统计符合条件的子串
res = 0
for j in range(1, len(group)):
res += min(group[j], group[j - 1 ])
return res
2.3 时间和空间复杂度
空间复杂度
- group: O(n)
时间复杂度:
- 第一个for循环: O(n)
- 第二个for循环: O(n)
- min函数: 常数操作 O(1)
- 总计: O(n)