题目样例
示例 1
输入
startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出
1
解释
一共有 3 名学生。
示例 2
输入
startTime = [4], endTime = [4], queryTime = 4
输出
1
解释
在查询时间只有一名学生在做作业。
示例 3
输入
startTime = [4], endTime = [4], queryTime = 5
输出
0
题目思考
解决方案
思路
复杂度
代码
Python 3
class Solution:
def busyStudent(self, startTime: List[int], endTime: List[int],
queryTime: int) -> int:
# 简单的区间判断
res = 0
for i in range(len(startTime)):
if startTime[i] <= queryTime <= endTime[i]:
res += 1
return res
C++
class Solution {
public:
int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
int res = 0;
for (int i = 0; i < startTime.size(); ++i) {
if (startTime[i] <= queryTime && queryTime <= endTime[i]) {
++res;
}
}
return res;
}
};
[1451] 重新排列句子中的单词
题目描述
「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 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"
解释
输出的排序情况如下：
示例 3
输入
text = "To be or not to be"
输出
"To be or to be not"
题目思考
解决方案
思路
复杂度
代码
Python 3
class Solution:
def arrangeWords(self, text: str) -> str:
a = text.split()
a[0] = a[0].lower()
d = collections.defaultdict(list)
for s in a:
d[len(s)].append(s)
res = []
for k in sorted(d.keys()):
res.extend(d[k])
res[0] = res[0].title()
return ' '.join(res)
C++
class Solution {
public:
string arrangeWords(string text) {
string substr;
multimap<int, string> len2str;
transform(text.begin(), text.end(), text.begin(),::tolower);
istringstream stream(text);
while (getline(stream, substr, ' ')) {
len2str.emplace(substr.size(), substr);
}
string res;
for_each(len2str.begin(), len2str.end(), [&](const pair<int, string>& entry "&"){ res += entry.second + ' '; });
res.pop_back();
res[0] = toupper(res[0]);
return res;
}
};
[1452] 收藏清单
题目描述
给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
题目样例
示例 1
输入
favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出
[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]
题目思考
解决方案
思路
复杂度
代码
Python 3
class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
res = []
n = len(favoriteCompanies)
favoriteCompanies = list(set(f) for f in favoriteCompanies)
for i in range(n):
for j in range(n):
if i != j and favoriteCompanies[i].issubset(
favoriteCompanies[j]):
break
else:
res.append(i)
return res
C++
class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
vector<int> res;
auto& v = favoriteCompanies;
for_each(v.begin(), v.end(), [](vector<string>& vec "") { sort(vec.begin(), vec.end()); });
for(int i = 0; i < v.size(); ++i) {
bool isSubset = false;
for (int j = 0; j < v.size(); ++j) {
isSubset = i != j && includes(v[j].begin(), v[j].end(), v[i].begin(), v[i].end());
if (isSubset) {
break;
}
}
if (!isSubset) {
res.push_back(i);
}
}
return res;
}
};
[1453] 圆形靶内的最大飞镖数量
题目描述
墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。
投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 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
题目思考
解决方案
思路
复杂度
代码
Python 3
import math
class Solution:
def numPoints(self, points: List[List[int]], r: int) -> int:
n = len(points)
def getinsidecount(cx, cy):
res = 0
for p in points:
x, y = p
if (x - cx)**2 + (y - cy)**2 <= r**2:
res += 1
return res
res = 1
for i in range(n):
for j in range(i + 1, n):
x1, y1 = points[i]
x2, y2 = points[j]
d2 = (x1 - x2)**2 + (y1 - y2)**2
if d2 > (2 * r)**2:
continue
px, py = (x1 + x2) / 2, (y1 + y2) / 2
dx, dy = x1 - x2, y1 - y2
h = math.sqrt(r**2 - d2 / 4)
for fx, fy in ((1, -1), (-1, 1)):
# 解有两个, 符号正好相反
cx = fx * h * dy / math.sqrt(dx**2 + dy**2) + px
cy = fy * h * dx / math.sqrt(dx**2 + dy**2) + py
res = max(res, getinsidecount(cx, cy))
return res
C++
class Solution {
public:
int numPoints(vector<vector<int>>& points, int r) {
int rSquare = r * r;
int rSquare4 = 4 * rSquare;
auto middle = [](const vector<int>& lhs, const vector<int>& rhs "") {
vector<double> res(2);
res[0] = 1.0 * (lhs[0] + rhs[0]) / 2;
res[1] = 1.0 * (lhs[1] + rhs[1]) / 2;
return res;
};
auto difference = [](const vector<int>& lhs, const vector<int>& rhs "") {
vector<double> res(2);
res[0] = lhs[0] - rhs[0];
res[1] = lhs[1] - rhs[1];
return res;
};
auto getDistance = [](const vector<double>& lhs "") {
return lhs[0] * lhs[0] + lhs[1] * lhs[1];
};
auto getInsideCount = [&](double cx, double cy "&") {
int res = 0;
for_each(points.begin(), points.end(), [&](vector<int>& p "&") {
double dx = p[0] - cx;
double dy = p[1] - cy;
if (dx * dx + dy * dy <= rSquare) {
++res;
}
});
return res;
};
int res = 1;
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
auto diff = difference(points[i], points[j]);
double distance = getDistance(diff);
if (distance > rSquare4) {
continue;
}
auto mid = middle(points[i], points[j]);
double h = sqrt(1.0 * rSquare - 1.0 * distance / 4);
double dx = h * diff[1] / sqrt(1.0 * distance);
double dy = h * diff[0] / sqrt(1.0 * distance);
res = max(res, getInsideCount(mid[0] + dx , mid[1] - dy));
res = max(res, getInsideCount(mid[0] - dx , mid[1] + dy));
}
}
return res;
}
};
参考资料
本文分享自微信公众号 - 每日精选算法题（DailyAlgorithm）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。