leetcode contest 295
leetcode contest 295
第三题难度竟然超过第四题的难度。第四题确实是简单题目。
2287. 重排字符形成目标字符串
题目
给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。
从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。
示例 1：1
2
3
4
5
6
7输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。
示例 2：1
2
3
4
5
6输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。
示例 3：1
2
3
4
5输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。
提示：
1 <= s.length <= 1001 <= target.length <= 10s和target由小写英文字母组成
地址
https://leetcode.cn/problems/rearrange-characters-to-make-target-string/
题意
直接遍历即可
思路
- 直接统计即可，每次从字符串 $s$ 中减去 $target$ 覆盖的字符即可，统计可以减去的次数即可。
- 复杂度分析：
- 时间复杂度：$O(n + m)$, 其中 $n,m$ 分别为两个字符串的长度。
- 空间复杂度：$O(\Sigma)$。
代码
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
31class Solution {
public:
int rearrangeCharacters(string s, string target) {
vector<int> cnt1(26);
vector<int> cnt2(26);
for(auto c : target) {
cnt1[c - 'a']++;
}
for (auto c: s) {
cnt2[c - 'a']++;
}
int res = 0;
while(true) {
bool valid = true;
for (int i = 0; i < 26; i++) {
if (cnt2[i] >= cnt1[i]) {
cnt2[i] -= cnt1[i];
} else {
valid = false;
break;
}
}
if (valid){
res++;
}else{
break;
}
}
return res;
}
};
2288. 价格减免
题目
句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 ‘$’ 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。
例如"$100"、"$23" 和 "$6.75"表示价格，而 "100"、"$"和"2$3" 不是。
注意：本题输入中的价格均为整数。
给你一个字符串 sentence 和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。
返回表示修改后句子的字符串。
示例 1：1
2
3
4
5
6输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
输出："there are $0.50 $1.00 and 5$ candies in the shop"
解释：
表示价格的单词是 "$1" 和 "$2" 。
- "$1" 减免 50% 为 "$0.50" ，所以 "$1" 替换为 "$0.50" 。
- "$2" 减免 50% 为 "$1" ，所以 "$1" 替换为 "$1.00" 。
示例 2：1
2
3
4
5
6输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
解释：
任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。
每个单词都替换为 "$0.00"。
提示：
1 <= sentence.length <= 105sentence由小写英文字母、数字、’ ‘ 和 ‘$’ 组成sentence不含前导和尾随空格sentence的所有单词都用单个空格分隔- 所有价格都是 正 整数且不含前导零
- 所有价格 最多 为
10位数字 0 <= discount <= 100
地址
https://leetcode.cn/problems/apply-discount-to-prices
题意
字符串变换
思路
- 分出所有的单词，然后将其中的价格按照题意进行变换即可，不过
C++写起来稍微复杂一些，可以用 $\texttt{sprintf, stringstream, setprecision }$ 等库函数实现，确实没啥好说的。 - 复杂度分析：
- 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
- 空间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
代码
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
61class Solution {
public:
vector<string> split(string sentence) {
vector<string> res;
int n = sentence.size();
int pos = 0;
while (pos < n) {
while(pos < n && sentence[pos] == ' ') {
pos++;
}
int curr = pos;
while(pos < n && sentence[pos] != ' '){
pos++;
}
if (curr < n) {
res.emplace_back(sentence.substr(curr, pos - curr));
}
}
return res;
}
bool checkvalid(string s) {
if(s[0] != '$') {
return false;
}
if(s.size() == 1) {
return false;
}
for(int i = 1; i < s.size(); i++) {
if(!isdigit(s[i])){
return false;
}
}
return true;
}
string discountPrices(string sentence, int discount) {
vector<string> words = split(sentence);
for (int i = 0; i < words.size(); i++) {
if (checkvalid(words[i])){
string curr;
curr.push_back('$');
long long num = 0;
for(int j = 1; j < words[i].size(); j++) {
num = num * 10 + words[i][j] - '0';
}
num = num * (100 - discount);
long long prefix = num / 100;
long long suffix = num % 100;
curr.append(to_string(prefix) + "." + (suffix < 10 ? ("0" + to_string(suffix)) : (to_string(suffix))));
words[i] = curr;
}
}
string res;
for (int i = 0; i < words.size() - 1; i++) {
res.append(words[i] + " ");
}
res.append(words.back());
return res;
}
};
2289. 使数组按非递减顺序排列
题目
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
示例 1：1
2
3
4
5
6
7输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：3
解释：执行下述几个步骤：
- 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
- 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
- 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：1
2
3输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
地址
https://leetcode.cn/problems/steps-to-make-array-non-decreasing
题意
思路
- 参考单调栈的做法，当时确实没有想到更好的解法, 确实比较难的解法，但是线段树真心是各种无敌，掌握了线段树，可以掌握一大波各种复杂问题的处理。
- 复杂度分析：
- 时间复杂度：$O(n)$, 其中 $n$ 为数组的长度。
- 空间复杂度：$O(n)$, 其中 $n$ 为数组的长度。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int totalSteps(vector<int> &nums) {
int ans = 0;
stack<pair<int, int>> st;
for (int num : nums) {
int maxT = 0;
while (!st.empty() && st.top().first <= num) {
maxT = max(maxT, st.top().second);
st.pop();
}
maxT = st.empty() ? 0 : maxT + 1;
ans = max(ans, maxT);
st.emplace(num, maxT);
}
return ans;
}
};
2290. 到达角落需要移除障碍物的最小数目
题目
给你一个下标从 0 开始的二维整数数组grid ，数组大小为 m x n。每个单元格都是两个值之一：
0表示一个 空 单元格，1表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。
示例 1：1
2
3
4
5输入：grid = [[0,1,1],[1,1,0],[1,1,0]]
输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。
示例 2：1
2
3输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出：0
解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j]为0或1grid[0][0] == grid[m - 1][n - 1] == 0
地址
https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner
题意
BFS 或者 dijkstra
思路
- 感觉这个题目只能算是简单题目，感觉没什么好说的，标准的模板题目。
- 复杂度分析：
- 时间复杂度：$O(m \times n)$, 其中 $m, n$ 为矩阵的行数与列数。
- 空间复杂度：$O(m \times n)$, 其中 $m, n$ 为矩阵的行数与列数。
代码
- dijkstra
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
35class Solution {
public:
int minimumObstacles(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int res = INT_MAX;
vector<vector<int>> cost(m, vector<int>(n, m * n));
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
/* dijistra */
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.emplace(0, 0);
cost[0][0] = 0;
while(!pq.empty()) {
auto [c, p] = pq.top();
pq.pop();
int x = p / n;
int y = p % n;
if(x == m - 1 && y == n - 1) {
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
if (grid[x][y] + c < cost[nx][ny]) {
pq.emplace(grid[x][y] + c, nx * n + ny);
cost[nx][ny] = grid[x][y] + c;
}
}
}
}
return cost[m - 1][n - 1];
}
}; - BFS
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
27class Solution {
public:
int minimumObstacles(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> cost(m, vector<int>(n, INT_MAX));
queue<pair<int,int>> qu;
qu.emplace(0, 0);
cost[0][0] = 0;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!qu.empty()) {
auto [x, y] = qu.front();
qu.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
if (cost[x][y] + grid[nx][ny] < cost[nx][ny]) {
qu.emplace(nx, ny);
cost[nx][ny] = cost[x][y] + grid[nx][ny];
}
}
}
}
return cost[m - 1][n - 1];
}
};
#
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://mikemeng.org/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
