leetcode contest 295

第三题难度竟然超过第四题的难度。第四题确实是简单题目。

2287. 重排字符形成目标字符串

题目

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

提示：

• 1 <= s.length <= 100
• 1 <= target.length <= 10
• s 和 target 由小写英文字母组成

地址

https://leetcode.cn/problems/rearrange-characters-to-make-target-string/

题意

直接遍历即可

思路

1. 直接统计即可，每次从字符串 $s$ 中减去 $target$ 覆盖的字符即可，统计可以减去的次数即可。
2. 复杂度分析：

• 时间复杂度：$O(n + m)$, 其中 $n,m$ 分别为两个字符串的长度。
• 空间复杂度：$O(\Sigma)$。

代码

class 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：

输入：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：

输入：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 <= 105
• sentence 由小写英文字母、数字、’ ‘ 和 ‘$’ 组成
• sentence 不含前导和尾随空格
• sentence 的所有单词都用单个空格分隔
• 所有价格都是 正 整数且不含前导零
• 所有价格 最多 为  10 位数字
• 0 <= discount <= 100

地址

https://leetcode.cn/problems/apply-discount-to-prices

题意

字符串变换

思路

1. 分出所有的单词，然后将其中的价格按照题意进行变换即可，不过 C++ 写起来稍微复杂一些，可以用 $\texttt{sprintf, stringstream, setprecision }$ 等库函数实现，确实没啥好说的。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
• 空间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。

代码

class 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：

输入：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：

输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/steps-to-make-array-non-decreasing

题意

思路

1. 参考单调栈的做法，当时确实没有想到更好的解法, 确实比较难的解法，但是线段树真心是各种无敌，掌握了线段树，可以掌握一大波各种复杂问题的处理。
2. 复杂度分析：

• 时间复杂度：$O(n)$, 其中 $n$ 为数组的长度。
• 空间复杂度：$O(n)$, 其中 $n$ 为数组的长度。。

代码

class 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：

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]
输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

示例 2：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出：0
解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 2 <= m * n <= 105
• grid[i][j] 为 0 或 1
• grid[0][0] == grid[m - 1][n - 1] == 0

地址

https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner

题意

BFS 或者 dijkstra

思路

1. 感觉这个题目只能算是简单题目，感觉没什么好说的，标准的模板题目。
2. 复杂度分析：

• 时间复杂度：$O(m \times n)$, 其中 $m, n$ 为矩阵的行数与列数。
• 空间复杂度：$O(m \times n)$, 其中 $m, n$ 为矩阵的行数与列数。

代码

• dijkstra

  class 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

  class 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
• 关注我的微信公众号: 公务程序猿