Leetcode 第159场周赛解题报告

字数统计: 2.4k阅读时长: 11 min

 2019/04/21 

本周做完比赛收获比较大，对二分查找还有滑动窗口有了更新的认识。也深深感到要想达到一定的高度，刻意练习是一定要做的。有些题目别人两分钟写完代码，但是不会的即使一天也没思路。看看排名前面的，十几分钟搞定四道题，一定是经过了不少练习，再加上先天智商达到的。

第三题可以用二分查找在Nlog(N)解答，还可以用滑动窗口在O(N)情况下解答。赛后看别人代码，理解好半天才看明白滑动窗口解答，想到的证明感觉也不太严谨。通过这个题目拓宽了思路，以后遇到类似问题，应该能解答的好一些。

第一题是判定三点共线，之前比赛有遇到。所以很快就搞定了。也算是练习有点成果。

现在做题还是靠灵感，做多了，思考多了才能靠经验。靠灵感发挥是不稳定的，靠经验稳定性要比靠灵感强。高手和普通人之间的差别，就是在稳定性上。

比赛的地址 Weekly Contest 159

https://leetcode-cn.com/contest/weekly-contest-159

1. 缀点成线

题目：

缀点成线(Check If It Is a Straight Line)

地址：

https://leetcode-cn.com/contest/weekly-contest-159/problems/check-if-it-is-a-straight-line/

题意：

直角坐标系上有一堆点，判断这些点是否在同一条直线上。

思路：

两点确定一条直线，任意找两个点A、B。然后遍历判断其他点，是否和A、B共线即可。
判断方法利用向量叉乘，参考之前写的135场文章解法。

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& c) {
        int x1 = c[0][0];
        int y1 = c[0][1];
        int x2 = c[1][0];
        int y2 = c[1][1];
        for(int i = 2; i < c.size(); ++i)
        {
            int x3 = c[i][0];
            int y3 = c[i][1];
            int cross = (y2-y1)*(x3-x1)-(y3-y1)*(x2-x1);
            if(cross != 0)
                return false;
        }
        return true;
    }
};

2. 删除子文件夹

题目：

删除子文件夹(Remove Sub-Folders from the Filesystem)

地址：

https://leetcode-cn.com/contest/weekly-contest-159/problems/remove-sub-folders-from-the-filesystem/

题意：

输入是一个文件名绝对路径的字符串数组，要求输出所有父目录。

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b/" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

思路：

对字符串数组排序，父目录和其子目录一定是相邻的，并且父目录在最前面。

从前往后遍历，判断目录是否是已有的最后一个父目录的子目录，如果不是子目录，则为新的父目录。

也可以用trie树，先全部插入到树中。然后深度优先遍历，遍历到某个节点有结尾符，就不再遍历它为/的子节点。

class Solution {
public:
    bool isSubDir(string& sub, string & str)
    {
        sub.push_back('/');
        int len = sub.size();
        bool isSub = str.substr(0, len) == sub;
        sub.pop_back();
        return isSub;
    }
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> ans;
        ans.push_back(folder[0]);
        for(int i = 1; i < folder.size(); ++i)
        {
            if(isSubDir(ans.back(), folder[i]) == false)
            {
                ans.push_back(folder[i]);
            }
        }
        return ans;
    }
};

3. 替换子串得到平衡字符串

题目：

替换子串得到平衡字符串(Replace the Substring for Balanced String)

地址：

https://leetcode-cn.com/contest/weekly-contest-159/problems/replace-the-substring-for-balanced-string/

题意：

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

思路：

如何判断一段字串替换后是否已能平衡？

由于子串内的字符可以任意变换。整个字符串的长度n又是4的倍数。

所以，子串外的四个字符，每个的个数都不大于n/4就能变换成功。

如何找到哪段子串能替换是难点。

有两种方法：

方法一：二分枚举替换字符串长度，然后验证每个长度的替换子串，是否能满足提议。

如果满足，则减少最大值。

如果不满足，则增大最小值。

最后左右区间会落在满足的最小值上。

方法二：滑动窗口，在滑动的过程中找到最小值。

以0为最左侧窗口边缘，然后枚举最右侧边缘。如果满足条件，则不断缩小左侧。

假设i1<j1, i2<j2, j1<j2, i2<j1,[i1,j1],[i2,j2]两条线段有交集有，他们两个是最接近的满足条件的区间。

如果[i2, j2]是最优解，那么一定i1 < i2。因为[i1,j1]一定比[i2,j2]短。

当在[i1, j1]的时候成立时，移动i1的时候，一定会移动到i1+1的位置让条件不成立。这时再扩大右侧时，

在(j1, j2)过程中，不会有满足条件的，到右侧达到j2的时候，会满足条件，而且会逐步缩小到i2。

就是在枚举右侧边际的时候，左侧边缘不会再减小，只会逐渐增大。

方法一代码：

class Solution
{
public:
    int balancedString(string s)
    {
        unordered_map<char, int> count;
        string letter = "QWER";
        for(auto &ch : s)
            count[ch]++;
        int n = s.length();
        auto isBalance = [&]()->bool {
            for(auto &ch : letter)
                if(count[ch] > n / 4)
                    return false;
            return true;
        };

        int l = 0;
        int r = n;
        while(l < r) {
            unordered_map<char, int> bak = count;
            int mid = l + (r - l) / 2;
            bool isOk = false;
            for(int i = 0; i < n; ++i) {
                char ch = s[i];
                count[ch]--;
                if(i >= mid)
                    count[s[i - mid]]++;
                if(i >= mid - 1) {
                    if(isBalance()) {
                        isOk = true;
                        break;
                    }
                }
            }
            if(isOk) {
                r = mid;
            } else
                l = mid + 1;
            count = bak;
        }
        return l;
    }
};

方法二代码：

class Solution
{
public:
    int balancedString(string s)
    {
        unordered_map<char, int> count;
        string letter = "QWER";
        for(auto &ch : s)
            count[ch]++;
        int n = s.length();
        auto isBalance = [&]()->bool
        {
            for(auto &ch : letter)
            {
                if(count[ch] > n / 4)
                    return false;
            }
            return true;
        };
        int l = 0;
        int ans = n;
        for(int r = 0; r < n; ++r)
        {
            count[s[r]]--;
            while(isBalance() && l < n)
            {
                ans = min(ans, r - l + 1);
                count[s[l]]++;
                ++l;
            }
        }
        return ans;
    }
};

4. 规划兼职工作

题目：

规划兼职工作(Maximum Profit in Job Scheduling)

地址：

https://leetcode-cn.com/contest/weekly-contest-159/problems/maximum-profit-in-job-scheduling/

题意：

有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：
我们选出第 1 份和第 4 份工作，
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。

思路：

先给工作按结束时间排序。每项工作，要么做，要么不做。

动态规划公式dp[n]表示前n项工作的最优解。v[n]表示第n份工作的价值。

再算dp[n+1]时，分两种情况。

不选择第n+1份工作，则dp[n+1]=dp[n];
选择第n+1份工作，则dp[n+1]=v[n]+dp[j];(做完第j份工作，就做第n份工作。所以j的选取从小于等于第n+1份工作开始时间中，最大的工作序号)

两种情况的最大值，就为dp[n+1]的值。

class Solution {
public:
    struct Job{
        int start;
        int end;
        int cost;
        bool operator < (Job &other) const
        {
            return end < other.end;
        }
    };
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<Job> v;
        for(int i = 0; i < startTime.size(); ++i)
            v.push_back({startTime[i], endTime[i], profit[i]});
        sort(v.begin(), v.end());
        int n = v.size();
        vector<int> dp(n, 0);
        dp[0] = v[0].cost;
        Job job{0, 0, 0};
        for(int i = 1; i < n; ++i)
        {
            int not_with = dp[i-1];
            int with = v[i].cost;
            job.end = v[i].start;
            int j = upper_bound(v.begin(), v.begin() + i, job) - v.begin() - 1;
            if(j>=0)
                with += dp[j];
            dp[i] = max(with, not_with);
        }
        return dp[n-1];
    }
};

第三题

class Solution
{
public:
    int balancedString(string str)
    {
        int n = str.size();
        unordered_map<char, int> cnt, slide;
        for(auto &ch : "QWER")
            cnt[ch] = 0;
        for(auto &ch : str)
            cnt[ch]++;
        for(auto &ch : "QWER")
            cnt[ch] -= n / 4;
            
        int s = 0;
        int t = 0;
        int ret = n;
        auto isOk = [&]()
        {
            for(auto ch : "QWER")
            {
                if(slide[ch] < cnt[ch])
                    return false;
            }
            return true;
        };
        //if(isOk())
            //return 0;
        
        //s,t是左闭右开区间[s, t)，所以for循环要判断s不能超过n，但是循环里要判断isOk是否不满足
        //不能判断t==n退出循环
        for( ; s < n; ) {
            //cout << s << " " << t << " " << n <<  endl;
            while(t < n && !isOk()) {
                slide[str[t++]]++;
            }
            //bool ok = isOk();
            //cout << s << " " << t << " " << n << " " << ok << endl;
            if(!isOk())
                break;
            ret = min(t - s, ret);
            slide[str[s++]]--;
        }
        return ret;
    }
};

/*
"QWER"
"QQWE"
"QQQW"
"QQQQ"
"WQWRQQQW"
*/

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC159%E5%9C%BA%E5%91%A8%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

发表日期：April 21st 2019, 10:00:03 am

更新日期：April 21st 2019, 10:00:03 am

Next Post

Leetcode 第158场周赛解题报告
Previous Post

一些微信功能的观察与想法

CATALOG

1. 1. 缀点成线
2. 2. 删除子文件夹
3. 3. 替换子串得到平衡字符串
4. 4. 规划兼职工作