LeetCode周赛295，赛后看了大佬的代码，受益匪浅-六虎

大家好，日拱一卒，我是梁唐。

今天是周一，我们照惯例来聊聊昨天的LeetCode周赛。

这一场比赛的赞助商是博乐科技，前1000名都可以获得内推机会。和之前50名、100名获得内推的场次比起来有诚意多了。

这一场比赛很有意思，由于第三题难度太大，以至于一直到比赛结束也只有不到150人通过，甚至要小于第四题。并且第三题的解题思路也超出了以往出题的套路，让很多人都措手不及。

因为这样的反套路，使得很多人10分钟切出了两题，一直卡在第三题，甚至卡到比赛结束。毕竟比赛的结果除了取决于实力强弱之外，和临场发挥、心态以及战术、策略都相关。做一做链表和数组的区别这样的题目对于拓展视野，掌握更多的算法和思路很有帮助，因此非常推荐大数组家赛后练习。

好了，废话就说这么多，我们来看题吧。

重排字符形成目标字符串链表的特点

给你两个下标从 0 开始的字符串 s 和 t链表的创建arget 。你可以从 s 取出一些字符并将其重排，得到若干新的数组指针字符串。

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

题解

题目的范围很小，基本上怎么玩都可以。

我们就照着题意模拟即可链表反转，分别统计出s和t数组公式arPythonget当中每个字母出现的次数。枚举所有字符，计算出s中

相同字符能够组成的字符串的数量。根据木桶理论，所有字符当中数量最少的即为答案。

class Solution {ub
public:
    int rearrangeCharacters(string s, string target) {
        map<char, int> mp, used;
        int ret = 0;
        for (auto c : s) {
            mp[c]++;
        }
        for (auto c : target) {
            used[c] ++;
        }
        ret = 0x3f3f3f3f;
        for (auto p = used.begin(); p != used.end(); p++) {
            char c = p->first;
            int v = p->second;
            if (mp.count(c) == 0) return 0;
            ret = min(mp[c] / v, ret);
        }
        return ret;
    }
};

价格减免

句子是由若干个单词组成的字符串，单词之间用单个空格算法是指什么分隔，其中每个单词可以包含数字、小写字母、和美元符号 ‘$’ 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。

例如 “ $100 “ 、 “$ 23″ 和 “ $6.75 “ 表示价格，而 “ 100 “ 、 “$ ” 和 “2$3” 不是。

**注意：**本题输入中的价格均为整数。

给你一个字符串 sentence 和一个整数 d链表结构iscount 。对于每个表示价格的算法工程师单词，都在价格的基础上减数组排序免 discount% ，并更新该单词到句子中。所有更新后的价链表的定义格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

题解

这题的题面也没什么难度，非常直观，就是要遵照题目的意思对字符串进行操作。

但实现起来还是有些麻烦的，特别是如果你使用C++的话，连split函数都没有。赛后看了一些python保留字大佬的代码，发现了代替split的一些trick。比如可以使用stringstream来获得类似split的效果：

string sentence;
stringstream ss(sentence);
string s;
while (ss >> s) {
    // do something
}

但在比赛的时候，我并不知道这个，所以果断选择了Python。

实际上也的确如此，在字符串和list的处理上，Python提供的库函数比C++更多。再比如，在本题当中，我们python安装教程需要将字符串转成数字来进行折扣的计算。我们可以直接使用P科技手抄报ython中的强制转换来完成，对链表排序于非法的字符串，强制转换会报错，因此需要加上try catch。

不过本题当中明确说了价格一定是整数，所以也可以使用Python中的isnumeric函数。

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split(' ')
        dis = 1.0 - discount / 100
        wds = []
        for w in words:
            if w[0] == '$':
                try:
                    v = float(w[1:])
                    w = '${:.2f}'.format(v * dis)
                except:
                    pass
            wds.append(w)
        return ' '.join(wds)

使数组按非递减顺序排列

给你一个下标从 0 开始的整数数组 nums数组排序。在一步操作中，移除所有满足 nums[i – 1] > nums[i] 的 nums[i] ，其中 0 < i &算法的空间复杂度是指lt; nums.length 。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需python安装教程执行的操作数。

题解

数据的范围是1e5，我们使用暴力的方法求解是一定会超时的。

我一算法的有穷性是指开始觉得像是用单调栈，但推导了半天也没算法有想出解法来。赛后看了大佬们的题解才找到思路，不得不说数组初始化是太巧妙了。

题目当中隐藏了一链表的特点个关键的条件，当我们第一轮删除之科技之锤后，下算法的五个特性一次python安装教程可能发生删除的位置一定是第一次有过删除的位置。比如[5, 3, 4]，第一次删除之后变成了[5, 4]，可以继续触发第二次删除。也就是说因为前一次删除导致了元素相邻的情况发生了变化，才有可能构成下一次删除，之前数组排序没有删除的位置之后也不会再删除了。

所以我们可以记录下每次发生删除的位科技最狂潮置，每一轮当中只需要判断这些位置的元素是否会触发下一次删除即可。但还有一个问题是数组删除元素的复杂度太高是，所以这里可以使用链表。还有一个细节是删除的时候算法是可以连续删除的，比如[5, 4, 3]，只需要删除一次就可以变成[5]。

这里面的思路推导总体来说不算复杂，但由于日常的比赛当中少见链表的问题，因此很难往这个角度思考。也正因此才这么多人都做不出来。数组排序

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        list<int> lst(nums.begin(), nums.end());
        vector<list<int>::iterator> to_delete;
        for (auto p = lst.begin(); next(p) != lst.end(); p++) {
            if (*p > *(next(p)))    to_delete.push_back(next(p));
        }
        int ret = 0;
        while (!to_delete.empty()) {
            ret++;
            vector<list<int>::iterator> buff;
            for (auto p: to_delete) {
                auto pre = prev(p);
                lst.erase(p);
                // 判断能否连续删除
                if (buff.empty() || buff.back() != pre) {
                    buff.push_back(pre);
                }
            }
            to_delete.clear();
            for (auto p: buff) {
                if (next(p) != lst.end() && *p > *(next(p))) to_delete.push_back(next(p));
            }
        }
        return ret;
    }
};

到达角落需要移除障碍物的最小数目

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

0 表示一个空单元格，
1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空链表单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m – 1, n科技之门 – 1链表排序) ，返回需要移除的障碍物的最小数目。

题解

这题看着其实不算难，如果对算法熟悉的话，很容易发现这是标准的宽度优先搜索的问题。

但是很遗憾，直接用裸的bfs的代码去做是会超时的。因为太多的路重复走了太多次。接着可以想到分层递进的策略，我科技帝国从高分子材料开始们首先找链表数据结构到代价为0就可以python语言到达的点。接着从这些点出发，再找出花费一点代价能够达到的所有点，这些点就是代价为1的点。接着重复以数组c语言上过程，直到到达终点。

由于我们是分层递进的，可python怎么读以保证每个点只会遍历一次。这样实现的话我们需要维护两个队列，一个用于存储当前代价的点，一个用于存储当前代价+1的点。当当前代价的所有点遍历完了之后，python保留字遍历代价+1的点，直到遇见终点为止。

typedef pair<int, int> pii;
class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
        queue<pii> cur, nxt;
        cur.emplace(0, 0);
        dis[0][0] = 0;
        int fx[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        int cost = 0;
        while (true) {
            if (cur.empty()) {
                cur = nxt;
                nxt = queue<pii>();
                cost++;
            }
            auto [x, y] = cur.front();
            cur.pop();
            if (x == n-1 && y == m-1) break;
            for (int i = 0; i < 4; i++) {
                int xx = x + fx[i][0];
                int yy = y + fx[i][1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m) {
                    continue;
                }
                if (grid[xx][yy]) {
                    if (dis[xx][yy] == INT_MAX) {
                        nxt.emplace(xx, yy);
                        dis[xx][yy] = dis[x][y] + 1;
                    }
                }else {
                    if (dis[xx][yy] == INT_MAX) {
                        dis[xx][yy] = dis[x][y];
                        cur.emplace(xx, yy);
                    }
                }
            }
        }
        return cost;
    }
};

赛后看了大佬的代码之后，发现同样的思路还有更好的实现方式，就是使用数组c语言deque——双端队列。在插入的python语言时候区别对待，将当前代价的插入队首，而当前代价+1的点插入队尾。这样只需算法是指什么要一个队列就可以实现按照距离区分遍历顺序的效果，不得不说实在是太优雅了。

大家可以对比一下代码细链表c语言节感受一下其中的差异。

typedef pair<int, int> pii;
class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
        deque<pii> que;
        que.emplace_front(0, 0);
        dis[0][0] = 0;
        int fx[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while (!que.empty()) {
            auto [x, y] = que.front();
            que.pop_front();
            for (int i = 0; i < 4; i++) {
                int xx = x + fx[i][0];
                int yy = y + fx[i][1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m || dis[xx][yy] < INT_MAX) {
                    continue;
                }
                dis[xx][yy] = dis[x][y] + grid[xx][yy];
                if (!grid[xx][yy]) {
                    que.emplace_front(xx, yy);
                }else {
                    que.emplace_back(xx, yy);
                }
            }
        }
        return dis[n-1][m-1];
    }
};

每次赛后看看大佬的是一个很好的习惯，大佬的代码当中可以学到很多小技巧python可以做什么工作以及trick。尤其是有一些巨佬是不屑写题解的，链表c语言大家以后周赛结束都可以试试，经常能有惊喜。

好了，算法关于这次周赛就聊到这里，感谢大家的阅读。

LeetCode周赛295，赛后看了大佬的代码，受益匪浅

重排字符形成目标字符串链表的特点

题解

价格减免

题解

使数组按非递减顺序排列

题解

到达角落需要移除障碍物的最小数目

题解

相关文章

从事架构师岗位快2年了，聊一聊我对架构的一些感受和看法

利用自动化平台可以做的那亿点事 ｜得物技术

【2021年度总结】2021年度学习总结，学无止境，展望2022

【蓝蓝计算机考研算法】-day03小球反弹到最终静止共走的距离&我要通过

作者信息

利用自动化平台可以做的那亿点事｜得物技术