Leetcode 第275场周赛题解

记 s 里字母 c 出现的次数是 cnt1[c]，target 里字母 c 出现的次数是 cnt2[c]。枚举所有在 target 里出现的字母 c，那么 s 里的 c 最多只能凑出 floor(cnt1[c] / cnt2[c]) 个 target。答案就是 floor(cnt1[c] / cnt2[c]) 的最小值。

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector c(26, 0);
        for(auto x : s){
            c[x-'a']++;
        }
        vector y(26, 0);
        for(auto x : target){
            y[x-'a']++;
        }
        int ret = 0x3f3f3f3f;
        for(int i=0; i<26; ++i){
            if(y[i]){
                ret = min(ret, c[i] / y[i]);
            }
        }
        return ret;
    }
};

WAn发， 呜呜呜， 如果有大佬希望指导一下哈

class Solution {    
public:
    string discountPrices(string sentence, int discount) {
        string ss="", sss="";
        //存储原单词
	    vector str;
	    //存储处理后单词
        vector str1;
        int temp=-1;
      	// 单词划分 
	    for(int i=0;i=0&&(s[i]-'0')<=9||i&&s[i]=='.'){
                    continue;
                }
                else{
                    flag=true;
                }
            }
            if(flag){
                str1.push_back(s);
            }
            else{
            	//整数部分位数
                int a=to_string((stoll(s.substr(1))*(100-discount)*1/100)).size();
                //整数部分位数+保留位数
                str1.push_back("$"+(to_string((stoll(s.substr(1))*(100.0-discount*1.0)*1.0/100.0))).substr(0, a+3));
            }
        }
        // 以字符形式输出
        for(int i=0;i 
2289. 使数组按非递减顺序排列 
原题链接 
思路 
① 若当前元素需要被删除， 则位于其左边且小于该元素的要全被删除， 故当前元素删除时间为位于其左边且小于该元素的要全被删除时间加一
 ②若序列为单调递减增序列，则该序列一定是被依次删除， 即该序列尾部元素(最大值)覆盖前面较小值的状态
 因此，我们可以用一个单调递减栈存储元素及其被删除的时刻，当遇到一个不小于栈顶的元素 x 时，就不断弹出栈顶元素，并取弹出元素被删除时刻的最大值，
 这样就得到了所需要计算的时刻的最大值
 然后将 x 及 maxT+1入栈。注意如果此时栈为空，说明前面没有比 x 大的元素，x 无法被删除，即 maxT=0，这种情况需要将 x 及 0 入栈。
 
算法标签 构造 单调栈 
代码 
class Solution {
public:
    int totalSteps(vector &nums) {
        int ans = 0;
        stack> 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. 到达角落需要移除障碍物的最小数目 
原题链接 
思路 
① 把障碍物当作可以经过的单元格，经过它的代价为 1，空单元格经过的代价为 0
 ② 问题转化成从起点到终点的最短路。
 可以用 0-1 BFS 来将时间复杂度优化至 O(mn)
 
算法标签 图论 BFS 
代码 
class Solution {
    static constexpr int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public:
    int minimumObstacles(vector> &grid) {
        int m = grid.size(), n = grid[0].size();
        int dis[m][n];
        memset(dis, 0x3f, sizeof(dis));
        dis[0][0] = 0;
        deque> q;
        q.emplace_front(0, 0);
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop_front();
            for (auto &[dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                    int g = grid[nx][ny];
                    if (dis[x][y] + g < dis[nx][ny]) {
                        dis[nx][ny] = dis[x][y] + g;
                        // 遇到 0 就该点放入队头，优先走短路，利用双端队列的性质极大地优化了时间复杂度
                        g == 0 ? q.emplace_front(nx, ny) : q.emplace_back(nx, ny);
                    }
                }
            }
        }
        return dis[m - 1][n - 1];
    }
};
 
3， 4题解主要参考灵神
 原创不易
 转载请标明出处
 如果对你有所帮助 别忘啦点赞支持哈