对于第234场的周赛的个人题解

前言

本次周赛难度依旧是很舒适的难度了,让人有了安心感(并不)觉得自己又行了

字符串中不同整数的数目

给你一个字符串 word ,该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如,”a123bc34d8ef34” 将会变成 “ 123 34 8 34” 。注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):”123”、”34”、”8” 和 “34” 。

返回对 word 完成替换后形成的 不同 整数的数目。

只有当两个整数的 不含前导零 的十进制表示不同, 才认为这两个整数也不同。

示例 1:

输入:word = “a123bc34d8ef34”
输出:3
解释:不同的整数有 “123”、”34” 和 “8” 。注意,”34” 只计数一次。
示例 2:

输入:word = “leet1234code234”
输出:2
示例 3:

输入:word = “a1b01c001”
输出:1
解释:”1”、”01” 和 “001” 视为同一个整数的十进制表示,因为在比较十进制值时会忽略前导零的存在。

提示:

1 <= word.length <= 1000
word 由数字和小写英文字母组成

这个题简单来说就是分类+去重,去重用的是unordered_set,分类主要注意两点:

  • 数字不止一位
  • 去掉前置0

所以剩下的就是暴力就完事儿了

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
/**
* author: xmmmmmovo
* generation time: 2021/03/28
* filename: 5713. 字符串中不同整数的数目.cpp
* language & build version : C 11 & C++ 17
*/
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
int numDifferentIntegers(string word) {
int n = word.size();
unordered_set<string> set;

for (int i = 0; i < n; i++) {
char c = word[i];

if (isdigit(c)) {
int j = i;
string tmp;
while (j < n && isdigit(word[j])){
if(tmp.size() == 0 && word[j] == '0'){
j++;
continue;
}
tmp += word[j++];
}
set.insert(tmp);
i = j - 1;
}
}

return set.size();
}
};

时间复杂度:$\mathcal{O}(N)$

空间复杂度:根据数据分布规律计算

还原排列的最少操作步数

给你一个偶数 n ,已知存在一个长度为 n 的排列 perm ,其中 perm[i] == i(下标 从 0 开始 计数)。

一步操作中,你将创建一个新数组 arr ,对于每个 i :

如果 i % 2 == 0 ,那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ,那么 arr[i] = perm[n / 2 + (i - 1) / 2]
然后将 arr 赋值给 perm 。

要想使 perm 回到排列初始值,至少需要执行多少步操作?返回最小的 非零 操作步数。

示例 1:

输入:n = 2
输出:1
解释:最初,perm = [0,1]
第 1 步操作后,perm = [0,1]
所以,仅需执行 1 步操作
示例 2:

输入:n = 4
输出:2
解释:最初,perm = [0,1,2,3]
第 1 步操作后,perm = [0,2,1,3]
第 2 步操作后,perm = [0,1,2,3]
所以,仅需执行 2 步操作
示例 3:

输入:n = 6
输出:4

提示:

2 <= n <= 1000
n 是一个偶数

这个题看数据量$10^3$所以大概$\mathcal{O}(N^3)$才很危险,所以直接暴力算了:

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
/**
* author: xmmmmmovo
* generation time: 2021/03/28
* filename: 5715. 还原排列的最少操作步数.cpp
* language & build version : C 11 & C++ 17
*/
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stack>
#include <string>
#include <vector>

using namespace std;

bool check(vector<int> &vec) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] != i)
return false;
}
return true;
}

class Solution {
public:
int reinitializePermutation(int n) {
int cnt = 0;
vector<int> arr(n, 0);
vector<int> perm(n, 0);

for (int i = 0; i < n; i++) {
perm[i] = i;
}

do {
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
arr[i] = perm[i / 2];
else
arr[i] = perm[(n / 2) + (i - 1) / 2];
}
copy(arr.begin(), arr.end(), perm.begin());
cnt++;
cout << perm[0] << perm[1] << endl;
} while (!check(perm));

return cnt;
}
};

时间复杂度:$\mathcal{O}(N^2)$

空间复杂度:$\mathcal{O}(2N)$

后记

这个题看数据量的确是可以暴力的,但是我后面还是看了一下题解,好帅的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int reinitializePermutation(int n) {
if (n == 2) {
return 1;
}
int k = 1;
int pow2 = 2;
while (pow2 != 1) {
k++;
pow2 = pow2 * 2 % (n - 1);
}
return k;
}
};

替换字符串中的括号内容

给你一个字符串 s ,它包含一些括号对,每个括号中包含一个 非空 的键。

比方说,字符串 “(name)is(age)yearsold” 中,有 两个 括号对,分别包含键 “name” 和 “age” 。
你知道许多键对应的值,这些关系由二维字符串数组 knowledge 表示,其中 knowledge[i] = [keyi, valuei] ,表示键 keyi 对应的值为 valuei 。

你需要替换 所有 的括号对。当你替换一个括号对,且它包含的键为 keyi 时,你需要:

将 keyi 和括号用对应的值 valuei 替换。
如果从 knowledge 中无法得知某个键对应的值,你需要将 keyi 和括号用问号 “?” 替换(不需要引号)。
knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。

请你返回替换 所有 括号对后的结果字符串。

示例 1:

输入:s = “(name)is(age)yearsold”, knowledge = [[“name”,”bob”],[“age”,”two”]]
输出:”bobistwoyearsold”
解释:
键 “name” 对应的值为 “bob” ,所以将 “(name)” 替换为 “bob” 。
键 “age” 对应的值为 “two” ,所以将 “(age)” 替换为 “two” 。
示例 2:

输入:s = “hi(name)”, knowledge = [[“a”,”b”]]
输出:”hi?”
解释:由于不知道键 “name” 对应的值,所以用 “?” 替换 “(name)” 。
示例 3:

输入:s = “(a)(a)(a)aaa”, knowledge = [[“a”,”yes”]]
输出:”yesyesyesaaa”
解释:相同的键在 s 中可能会出现多次。
键 “a” 对应的值为 “yes” ,所以将所有的 “(a)” 替换为 “yes” 。
注意,不在括号里的 “a” 不需要被替换。
示例 4:

输入:s = “(a)(b)”, knowledge = [[“a”,”b”],[“b”,”a”]]
输出:”ba”

提示:

1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s 只包含小写英文字母和圆括号 ‘(‘ 和 ‘)’ 。
s 中每一个左圆括号 ‘(‘ 都有对应的右圆括号 ‘)’ 。
s 中每对括号内的键都不会为空。
s 中不会有嵌套括号对。
keyi 和 valuei 只包含小写英文字母。
knowledge 中的 keyi 不会重复。

这个题看数据量两个$10^5$,如果直接根据原来的二维数组肯定暴时间了,所以先利用一个unordered_map存一下数据然后暴力就完事儿了:

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
/**
* author: xmmmmmovo
* generation time: 2021/03/28
* filename: 5714. 替换字符串中的括号内容.cpp
* language & build version : C 11 & C++ 17
*/
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
string evaluate(string s, vector<vector<string>> &knowledge) {
string tmp;
bool f = false;
string res;
unordered_map<string, string> k;

for(auto &&kn: knowledge){
k[kn[0]] = kn[1];
}

for (auto &&c : s) {
if (c == '(') {
tmp = "";
f = true;
} else if (c == ')') {
f = false;
if(k.count(tmp) == 0){
res += '?';
} else {
res += k[tmp];
}
} else {
if (f) {
tmp += c;
} else {
res += c;
}
}
}

return res;
}
};

时间复杂度:$\mathcal{O}(N)$

空间复杂度:$\mathcal{O}(N)$

好因子的最大数目

给你一个正整数 primeFactors 。你需要构造一个正整数 n ,它满足以下条件:

n 质因数(质因数需要考虑重复的情况)的数目 不超过 primeFactors 个。
n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除,我们称这个因子是 好因子 。比方说,如果 n = 12 ,那么它的质因数为 [2,2,3] ,那么 6 和 12 是好因子,但 3 和 4 不是。
请你返回 n 的好因子的数目。由于答案可能会很大,请返回答案对 109 + 7 取余 的结果。

请注意,一个质数的定义是大于 1 ,且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子,且它们的乘积为 n 。

示例 1:

输入:primeFactors = 5
输出:6
解释:200 是一个可行的 n 。
它有 5 个质因子:[2,2,2,5,5] ,且有 6 个好因子:[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子,且同时有更多的好因子。
示例 2:

输入:primeFactors = 8
输出:18

提示:

1 <= primeFactors <= 109

这个题目看上去花里胡哨的,但其实主要是想清楚两件事情:

  • primeFactors真正代表什么

  • n真正代表什么

首先看数据量,哇塞$10^9$,看来只能$\mathcal{O}(\log{N})$级别的了($\mathcal{O}(N)$都不怎么稳),所以根据上面两个问题来考虑这个题了。

首先我们来思考primeFactors代表什么,根据题意,此变量代表质因数个数,这就说明假设总共有k种质因数,可以设每一种质因数数量为$a_i$,可以推导出:
$$
primeFactors = a_1 + a_2 + … + a_k
$$
所以参考得出好因子个数计算公式为:
$$
n_{tmp} = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}
$$
因为这里对于$a_i$来说每一个都有$(1..a_i)$种选择,所以为了得到最大值需要$a_1 * a_2 * … * a_k$取最大值。

这里分析完了之后就是剑指 Offer 14- I. 剪绳子这道题了。具体就是可以得到这里面$a_i$除了3,就是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
/**
* author: xmmmmmovo
* generation time: 2021/03/28
* filename: 5716. 好因子的最大数目.cpp
* language & build version : C 11 & C++ 17
*/
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

const int M = 1e9 + 7;

ll qmi(ll a, ll k, int p) {
ll res = 1;
while (k) {
if (k & 1)
res = res * a % p;
k >>= 1;
a = a * a % p;
}

return res;
}

class Solution {
public:
int maxNiceDivisors(int primeFactors) {
if (primeFactors <= 3)
return primeFactors;

if (primeFactors % 3 == 0)
return qmi(3, primeFactors / 3, M);
if (primeFactors % 3 == 1)
return qmi(3, (primeFactors - 4) / 3, M) * 4 % M;
return qmi(3, (primeFactors - 2) / 3, M) * 2 % M;
}
};

快速幂模板用的y总的。

时间复杂度:$\mathcal{O}(\log{N})$

空间复杂度:$\mathcal{O}(1)$