On the shoulders of giants.

weekly-contest-189

在既定时间做作业的学生人数

给你两个整数数组 startTime(开始时间)和 endTime(结束时间),并指定一个整数 queryTime 作为查询时间。

已知,第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上,返回能够使 queryTime 处于区间 [startTime[i], endTime[i]](含)的学生人数。

示例 1:

输入:startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出:1
解释:一共有 3 名学生。
第一名学生在时间 1 开始写作业,并于时间 3 完成作业,在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业,并于时间 2 完成作业,在时间 4 没有处于做作业的状态。
第二名学生在时间 3 开始写作业,预计于时间 7 完成作业,这是是唯一一名在时间 4 时正在做作业的学生。

示例 2:

输入:startTime = [4], endTime = [4], queryTime = 4
输出:1
解释:在查询时间只有一名学生在做作业。

示例 3:

输入:startTime = [4], endTime = [4], queryTime = 5
输出:0

示例 4:

输入:startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出:0

示例 5:

输入:startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出:5

提示:

  • startTime.length == endTime.length
  • 1 <= startTime.length <= 100
  • 1 <= startTime[i] <= endTime[i] <= 1000
  • 1 <= queryTime <= 1000
题解

直接遍历判断即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int total = 0, n = startTime.size();
        for(int i = 0; i < n; i++) {
            total += (startTime[i] <= queryTime && queryTime <= endTime[i]);
        }
        return total;
    }
};

重新排列句子中的单词

「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :

  • 句子的首字母大写
  • text 中的每个单词都用单个空格分隔。

请你重新排列 text 中的单词,使所有单词按其长度的升序排列。如果两个单词的长度相同,则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

示例 1:

输入:text = "Leetcode is cool"
输出:"Is cool leetcode"
解释:句子中共有 3 个单词,长度为 8 的 "Leetcode" ,长度为 2 的 "is" 以及长度为 4 的 "cool" 。
输出需要按单词的长度升序排列,新句子中的第一个单词首字母需要大写。

示例 2:

输入:text = "Keep calm and code on"
输出:"On and keep calm code"
解释:输出的排序情况如下:
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母,因为存在长度相同的其他单词,所以它们之间需要保留在原句子中的相对顺序。
"calm" 4 个字母。
"code" 4 个字母。

示例 3:

输入:text = "To be or not to be"
输出:"To be or to be not"

提示:

  • text 以大写字母开头,然后包含若干小写字母以及单词间的单个空格。
  • 1 <= text.length <= 10^5
题解

分割出字符串然后按长度为第一关键字,位置为第二关键字排序。

记得改变初始串头大小写,结果串头大小写。

时间复杂度:\(O(n+m\log m)\)

class Solution {
public:
    struct Inform {
        string s;
        int p;
        bool operator < (const Inform& tmp) const {
            return s.length() < tmp.s.length() || (s.length() == tmp.s.length() && p < tmp.p);
        }
    };
    string arrangeWords(string text) {
        vector<Inform> str;
        string result = "";
        int n = text.length();
        for(int i = 0, p = 0; i < n; i++) {
            p = i;
            while(p < n && text[p] == ' ') p++;
            i = p;
            while(i + 1 < n && text[i + 1] != ' ') i++;
            str.push_back((Inform){text.substr(p, i - p + 1), p});
        }
        if(str[0].s[0] < 'a') str[0].s[0] = str[0].s[0] + ('a' - 'A');
        sort(str.begin(), str.end());
        if('a' <= str[0].s[0]) str[0].s[0] = str[0].s[0] - ('a' - 'A');
        for(int i = 0; i < str.size(); i++) {
            result += str[i].s;
            if(i + 1 != str.size()) result += " ";
        }
        return result;
    }
};

收藏清单

给你一个数组 favoriteCompanies ,其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单(下标从 0 开始)。

请找出不是其他任何人收藏的公司清单的子集的收藏清单,并返回该清单下标下标需要按升序排列

示例 1:

输入:favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出:[0,1,4] 
解释:
favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集,因此,答案为 [0,1,4] 。

示例 2:

输入:favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
输出:[0,1] 
解释:favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集,因此,答案为 [0,1] 。

示例 3:

输入:favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
输出:[0,1,2,3]

提示:

  • 1 <= favoriteCompanies.length <= 100
  • 1 <= favoriteCompanies[i].length <= 500
  • 1 <= favoriteCompanies[i][j].length <= 20
  • favoriteCompanies[i] 中的所有字符串 各不相同
  • 用户收藏的公司清单也 各不相同 ,也就是说,即便我们按字母顺序排序每个清单, favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
  • 所有字符串仅包含小写英文字母。
题解

字符串数组有序的情况下,判断包含关系可以降至 \(O(n)\)。

另外对原数组按字符串数组个数排序,为了不必要的遍历。

最后记录出有包含关系的标号。

时间复杂度:\(O(nm\log m + n\log n + n^2)\)

class Solution {
public:
    struct Inform {
        vector<string> s;
        int position;
        bool operator < (const Inform& tmp) const {
            return s.size() < tmp.s.size();
        }
    };
    static bool cmp(vector<string>& a, vector<string>& b) {
        return a.size() < b.size();
    }
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        for(auto& list_ : favoriteCompanies) {
            sort(list_.begin(), list_.end());
        }
        int n = favoriteCompanies.size();
        vector<Inform> inform;
        vector<bool> vis(n);
        for(int i = 0; i < n; i++) {
            inform.push_back((Inform){favoriteCompanies[i], i});
        }
        sort(inform.begin(), inform.end());
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(includes(inform[j].s.begin(), inform[j].s.end(),
                    inform[i].s.begin(), inform[i].s.end())) 
                    vis[i] = true;
            }
        }
        vector<int> result;
        for(int i = 0; i < n; i++) {
            if(!vis[i]) result.push_back(inform[i].position);
        }
        sort(result.begin(), result.end());
        return result;
    }
};

圆形靶内的最大飞镖数量

墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。

投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r

请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。

示例 1:

输入:points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出:4
解释:如果圆形的飞镖靶的圆心为 (0,0) ,半径为 2 ,所有的飞镖都落在靶上,此时落在靶上的飞镖数最大,值为 4 。

示例 2:

输入:points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出:5
解释:如果圆形的飞镖靶的圆心为 (0,4) ,半径为 5 ,则除了 (7,8) 之外的飞镖都落在靶上,此时落在靶上的飞镖数最大,值为 5 。

示例 3:

输入:points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
输出:1

示例 4:

输入:points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
输出:4

提示:

  • 1 <= points.length <= 100
  • points[i].length == 2
  • -10^4 <= points[i][0], points[i][1] <= 10^4
  • 1 <= r <= 5000
题解

枚举两个点,假定都在弦上,可以计算出该圆的圆心坐标。

之后通过圆心坐标,遍历每一个点,然后更新最大值,注意精度误差。

时间复杂度:\(O(n^3)\)

const double EPS = 1E-8;
class Solution {
public:
    double dis(vector<int> a, vector<int> b) {
        double dx = a[0] - b[0], dy = a[1] - b[1];
        return sqrt(dx * dx + dy * dy);
    }
    double dis(double x, double y, vector<int> p) {
        double dx = x - p[0], dy = y - p[1];
        return sqrt(dx * dx + dy * dy);
    }
    int cmp(double x) {
        if(fabs(x) < EPS) return 0;
        else return x < 0 ? -1 : 1;
    }
    int numPoints(vector<vector<int>>& points, int r) {
        int result = 1, n = points.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                double d = dis(points[i], points[j]);
                if(i == j || cmp(2.0 * r - d) < 0) continue;
                double cth = d / 2.0 / r, sth = sqrt(1 - cth * cth);
                double vx = (points[j][0] - points[i][0]) / d * r;
                double vy = (points[j][1] - points[i][1]) / d * r;
                double x = points[i][0] + vx * cth - vy * sth;
                double y = points[i][1] + vx * sth + vy * cth;
                int count = 0;
                for(int k = 0; k < n; k++) {
                    if(cmp(dis(x, y, points[k]) - r) <= 0) count++;
                }
                result = max(result, count);
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注