WeeklyContest159

发表于 分类于

力扣159场周赛[链接][https://leetcode-cn.com/contest/weekly-contest-159/]

一次和大佬打比赛的周日，程序员的周末娱乐活动。HHHH

第一题：签到题

5230. 缀点成线

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

示例 1：

img

1
2
输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：

img

1
2
输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

  • 2 <= coordinates.length <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates 中不含重复的点

算法分析

做这题时，要注意的就是要注意细节，刚做的时候害怕精度会卡，没有直接计算斜率存进变量中,让后直接推出方程y=kx+b就可以了；就这样就可以了！哈哈哈，当时没有特判斜率为0的情况，没想到数据没有卡请两个点的数据，逃过一劫；（某位大佬踩坑了！手动滑稽）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& c) {
        double x1=c[0][0],x2=c[1][0],y1=c[0][1],y2=c[1][1];
        if(!(x1-x2)){
            for(int i=2;i<c.size();i++){
                if(c[i][0]==x1)continue;
                else return false;
            }
        }
        for(int i=2;i<c.size();i++){
            double a=c[i][0],b=c[i][1];
            if(b==(y1-y2)/(x1-x2)*a+(y1-(y1-y2)/(x1-x2)*x1))continue;
               else return false;
        }
        return true;
    }
};

第二题：set的应用、字符串应用

5231. 删除子文件夹

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

我们这样定义「子文件夹」：

  • 如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：

  • / 后跟一个或者多个小写英文字母。

例如，/leetcode 和 /leetcode/problems 都是有效的路径，而空字符串和 / 不是。

示例 1：

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

示例 2：

1
2
3
输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d/" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

1
2
输入：folder = ["/a/b/c","/a/b/d","/a/b/ca"]
输出：["/a/b/c","/a/b/ca","/a/b/d"]

提示：

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 /
  • folder[i] 总是以字符 / 起始
  • 每个文件夹名都是唯一的

算法分析

考察的知识点：

  • sort的重载，即自定义排序
  • 按字符串长度排序
  • 字符串的切割
  • set容器的应用

基本思路：首先，将给出的字符串数组进行排序操作；然后读取字符串，遇到/的时候判断，在set中是否含有s.substring(0,j)子串，有直接跳过当前字符串，直到最后，没有包含就插入set中，最后返回set容器中的元素就完事了；多亏大佬指点才过；主要卡在按字符串长度排序;

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        unordered_set<string> set;
        sort(folder.begin(),folder.end(),[](const string &a,const string &b){return a.length()<b.length();});
        for(int i=0;i<folder.size();i++){
            int j;
            for(j=0;j<folder[i].size();j++){
                if(folder[i][j]=='/'){
                    string s = folder[i].substr(0,j);
                    if(set.count(s)){
                        break;
                    }
                }
            }
            if(set.count(folder[i]))continue;
            if(j==folder[i].size()){
                set.insert(folder[i]);
            }
        }
        vector<string> ans;
        for(auto s:set){
            ans.push_back(s);
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Set<String> set = new HashSet<>();
        Arrays.sort(folder,new Comparator<String>() { 

			@Override
			public int compare(String o1, String o2) {
				int ans=0;
                if(o1.length()>o2.length())ans=1;
                if(o1.length()<o2.length())ans=-1;
                return ans;
			}
			
		});
        for(int i=0;i<folder.length;i++){
            int j;
            for(j=0;j<folder[i].length();j++){
                if(folder[i].charAt(j)=='/'){
                    String s = folder[i].substring(0,j);
                    if(set.contains(s)){
                        break;
                    }
                }
            }
            if(set.contains(folder[i])){
                    continue;
            }
            if(j==folder[i].length())
                set.add(folder[i]);
        }
        return new ArrayList<String>(set);
    }
    
}

第三题：滑动窗口、双指针

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

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

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

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

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

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

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

示例 1：

1
2
3
输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：

1
2
3
输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

1
2
3
输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：

1
2
3
输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

提示：

  • 1 <= s.length <= 10^5
  • s.length 是 4 的倍数
  • s 中只含有 'Q', 'W', 'E', 'R' 四种字符

算法描述

按照几步进行：

  • 遍历字符串记录'Q','W','E','R'字符的个数
  • 计算平衡时各个字符的个数，找到要替换哪几个字符以及个数
  • 找到包含上面字符的最小窗口

基本思路：首先字符串遍历，计数字符个数，计算目标字符的个数，找到满足条件的窗口，一直遍历到字符串尾部，满足条件时更新最小窗口的大小；我刚开始做的时候没有思路，然后大佬一句点醒，抬手就来；哈哈哈

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int balancedString(string s) {
        if(s.length()==0)return 0;
        int sum[4];
        int a[4];
        memset(sum,0,sizeof(sum));
        memset(a,0,sizeof(a));
        for(int i=0;i<s.length();i++){
            if(s[i]=='Q')sum[0]++;
            else if(s[i]=='W')sum[1]++;
            else if(s[i]=='E')sum[2]++;
            else sum[3]++;
        }
        int n=s.length()/4;
        for(int i=0;i<4;i++){
            if(sum[i]>n)sum[i]-=n;
            else sum[i]=0;
        }
        if(sum[0]==0&&sum[1]==0&&sum[2]==0&&sum[3]==0)return 0;
        int l=0,r=0;
        int ans = s.length();
        for(;r<s.length();r++){
            if(s[r]=='Q')a[0]++;
            else if(s[r]=='W')a[1]++;
            else if(s[r]=='E')a[2]++;
            else a[3]++;
            while(r>=l&&a[0]>=sum[0]&&a[1]>=sum[1]&&a[2]>=sum[2]&&a[3]>=sum[3]){
                ans = min(ans,r-l+1);
                if(s[l]=='Q')a[0]--;
                else if(s[l]=='W')a[1]--;
                else if(s[l]=='E')a[2]--;
                else a[3]--;
                l++;
            }
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int balancedString(String s) {
        if(s.length()==0)return 0;
        int[] sum = new int[4];
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='Q'){
                sum[0]++;
            }else if(s.charAt(i)=='W'){
                sum[1]++;
            }else if(s.charAt(i)=='E'){
                sum[2]++;
            }else {
                sum[3]++;
            }
        }
        int t = s.length()/4;
        for(int i=0;i<4;i++){
            if(sum[i]>t)sum[i]=sum[i]-t;
            else sum[i]=0;
        }
        if(sum[0]==0&&sum[1]==0&&sum[2]==0&&sum[3]==0)return 0;
        int l=0,r=0;
        int ans = s.length();
        int[] a = new int[4];
        for(;r<s.length();r++){
             if(s.charAt(r)=='Q'){
                a[0]++;
            }else if(s.charAt(r)=='W'){
                a[1]++;
            }else if(s.charAt(r)=='E'){
                a[2]++;
            }else {
                a[3]++;
            }
            while(r>=l&&a[0]>=sum[0]&&a[1]>=sum[1]&&a[2]>=sum[2]&&a[3]>=sum[3]){
                ans = Math.min(ans,r-l+1);
                if(s.charAt(l)=='Q'){
                    a[0]--;
                }else if(s.charAt(l)=='W'){
                    a[1]--;
                }else if(s.charAt(l)=='E'){
                    a[2]--;
                }else a[3]--;
                l++;
            }
        }
        return ans;
    }
}

第四题：树状数组、离散化、动态规划（DP）

太难了

这一题一脸懵逼，自己太菜了，汉奇大佬tql,只想说一句:LHQ牛逼；下面看大佬表演（手动滑稽）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int maxn=1e6+10;
class Solution {
public:
    typedef pair<int,int> P;
    vector<int> v;
    int h[maxn],ne[maxn],idx;
    P e[maxn];
    int tree[maxn],dp[maxn],n=0;
    inline int lowbit(int x){
        return x&(-x);
    }
    void add(int x,int val){
        for(int i=x;i<=n;i+=lowbit(i))
            tree[i]=max(tree[i],val);
    }
    void add_pair(int a,P b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    int get(int x){
        int ans=0;
        for(int i=x;i;i-=lowbit(i))
            ans=max(ans,tree[i]);
        return ans;
    }
    int getid(int x){
        return (int)(lower_bound(v.begin(),v.end(),x)-v.begin()+1);
    }
    int jobScheduling(vector<int>& st, vector<int>& ed, vector<int>& val) {
        memset(h,-1,sizeof h);
        memset(dp,0,sizeof dp);
        memset(tree,0,sizeof tree);
        for(auto x:st) v.push_back(x);
        for(auto x:ed) v.push_back(x);
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        n=v.size();
        for(int i=0;i<st.size();i++) st[i]=getid(st[i]);
        for(int i=0;i<ed.size();i++) {
            ed[i]=getid(ed[i]);
            add_pair(ed[i],{st[i],val[i]});
        }
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1];
            for(int j=h[i];j!=-1;j=ne[j]){
                dp[i]=max(dp[i],get(e[j].first)+e[j].second);
            }
            add(i,dp[i]);
        }
        return dp[n];
    }
};