力扣314周赛_leetcode周赛分数预测

总结：相比于上周排名，这周排名提高了，估计竞赛积分也会提高。

这次也是只做了俩道题目

 第一题

class Solution {
public:
    int hardestWorker(int n, vector<vector<int>>& log) {
        int fmax=log[0][1];
        int k=log[0][0];
        int end=log[0][1];
        for(int i=1;i<log.size();i++)
        {
            if(fmax<log[i][1]-end)
            {
                fmax=log[i][1]-end;
                k=log[i][0];
            }
            else
                if(fmax==log[i][1]-end)
                {
                     if(k>log[i][0])
                         k=log[i][0];
                }
            end=log[i][1];
        }
        return k;
        
    }
};

错了俩次。才交对，明明是简单题目。

我第一次错在没有看到在同等时长下，优先小编号，就是只有>的情况

我第二次错在忘记写进行比较小编号了,在==的情况下，我忘记判断了

非常可惜

 第二题

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        vector<int>res;
        res.push_back(pref[0]);
        if(pref.size()<=1)
            return res;
        for(int i=1;i<pref.size();i++)
        {
            int a=pref[i];
            int b=pref[i-1];
            res.push_back(a^b);
        }
        return res;
        
    }
};

这个一次过，但是想了很久。

根据性质，a^b 相同为0，不相同为1，a^*=c ;即使

当c为0的部分，a为1的部分，*里面也有为1.要不然就是a为0的部分，*也有为0.

当c为1的部分，a为1的部分，*为0，a为0的部分，a为1.

综上所述。发现正好也符合a^b=*的思路

 虽然很菜但是还是想贴一下排名，督促自己进步

  

 争取早日回到自己的巅峰时刻

---

然后对其他没有做出来的题目理解

第三题

我看的题解

解法：贪心

本题是经典贪心：求出栈序列的最小字典序。

我们首先将题目描述进行转化：有一个初始为空的栈，给定字符的入栈顺序，求字典序最小的出栈序列。

当一个字符入栈后，我们持续检查栈顶元素 ccc。设还未入栈的字符中，字典序最小的字符是 mmm，有以下两种情况。

    c≤mc \le mc≤m：此时弹出 ccc 最优。如果此时按兵不动，下一个出栈的将会是大等于 ccc 的字符，答案不会变优。
    c>mc > mc>m：此时不弹出 ccc，等待后续更小的字符入栈。

所有字符都入栈后，栈内的剩余字符按顺序弹出即可。复杂度 O(n)\mathcal{O}(n)O(n)。

作者：tsreaper
链接：https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/solution/by-tsreaper-sx1s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者的题解讲述

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<char> f(n + 1);
        f[n] = 'z' + 1;
        for (int i = n - 1; i >= 0; i--) f[i] = min(f[i + 1], s[i]);
 
        string ans;
        stack<char> stk;
        for (int i = 0; i < n; i++) {
            stk.push(s[i]);
            while (!stk.empty() && stk.top() <= f[i + 1]) ans.push_back(stk.top()), stk.pop();
        }
        return ans;
    }
};
 
 

然后说一下我对题解的理解。首先我也是第一次接触字典序这个说法

字典序：字典序字典序是指按照字典中出现的先后顺序进行排序。

然后个根据贪心思想，我们要尽可能把数字最小的放在前面

题目是说把s前面的数字，放到t后面，然后t从后面再放在我的结果里面

我们一定要保证我们的结果是最优解。那么我们必须让最小的数字优先输出。所以我们从后面开始遍历，前后比，这样子到了最前面，就一定是最小的字符，后面都是除了前面的字符，那么他就是最小的字符了。

 然后后面就很栈的思路一样，先进后出，如果我这个数不是当前里面最小的数字

至于为什么是<f[i+1]里面的f[i+1]我也不懂为什么。希望有评论区大佬可以教教我