LEETCODE总结(第189周赛)
本文最后更新于:6 个月前
🏆 第 189 场力扣周赛
题目列表:
3 分 - 在既定时间做作业的学生人数
4 分 - 重新排列句子中的单词
5 分 - 收藏清单
7 分 - 圆形靶内的最大飞镖数量
在既定时间做作业的学生人数
一道送分题,统计出在时间范围内的人数即可!
public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
int count = 0;
for (int i = 0; i < startTime.length; i++) {
if (queryTime >= startTime[i] || queryTime <= endTime[i]) {
count++;
}
}
return count;
}
重新排列句子中的单词
- 先将句子中的单词分割出来
- 按单词长短放入到
Map
中,其中key
为单词长度,value
为相同长度单词的集合 - 按单词长度排序
Map
- 从
Map
中取出,组合成结果句子
public String arrangeWords(String text) {
// 先将句子中的单词分割出来
String[] strings = text.split(" ");
HashMap<Integer, List<Integer>> listHashMap = new HashMap<>(text.length());
for (int i = 0; i < strings.length; i++) {
String string = strings[i];
// 按单词长短放入到 `Map` 中,其中 `key` 为单词长度,`value` 为相同长度单词的集合
List<Integer> orDefault = listHashMap.getOrDefault(string.length(), new ArrayList<>());
orDefault.add(i);
listHashMap.put(string.length(), orDefault);
}
// 按单词长度排序 `Map`
TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>(listHashMap);
StringBuilder builder = new StringBuilder();
// 从 `Map` 中取出,组合成结果句子
for (Map.Entry<Integer, List<Integer>> entry : treeMap.entrySet()) {
Integer key = entry.getKey();
// System.out.println(key);
List<Integer> value = entry.getValue();
for (Integer index : value) {
String string = strings[index].toLowerCase();
builder.append(string).append(" ");
}
}
char charAt = Character.toUpperCase(builder.charAt(0));
return builder.replace(0, 1, String.valueOf(charAt)).deleteCharAt(builder.length() - 1).toString();
}
收藏清单
- 将每个用户的收藏清单按照字母顺序排序 (不排序也可以)
- 再利用
containsAll()
函数循环判断是否是子集即可
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
List<Integer> ret = new ArrayList<>();
if (favoriteCompanies.size() == 1) {
ret.add(0);
return ret;
}
Set<Integer> hashSet = new TreeSet<>();
// 将每个用户的收藏清单按照字母顺序排序 (不排序也可以)
favoriteCompanies.forEach(Collections::sort);
// favoriteCompanies.sort(Comparator.comparingInt(List::size));
for (int i = 0; i < favoriteCompanies.size(); i++) {
List<String> favoriteCompany = favoriteCompanies.get(i);
hashSet.add(i);
// System.out.println(Arrays.toString(favoriteCompany.toArray()));
for (int j = 0; j < favoriteCompanies.size(); j++) {
if (j == i) {
continue;
}
List<String> list = favoriteCompanies.get(j);
// 再利用 `containsAll()` 函数循环判断是否是子集即可
// 注意此处若直接用 list.containsAll() 会超时,可以通过查看源码得知 HasnSet 的 containsAll() 时间复杂度更低
HashSet<String> stringHashSet = new HashSet<>(list);
if (stringHashSet.containsAll(favoriteCompany)) {
hashSet.remove(i);
break;
}
}
}
ret.addAll(hashSet);
return ret;
}
圆形靶内的最大飞镖数量
- 将点都构建出来
- 对所有点依次两两枚举,确定所有的圆
- 分别求出各个圆的圆心
- 再枚举所有的点,求出被圆包住的点的个数的最大值
class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
private final double eps = 1e-8;
public int numPoints(int[][] points, int r) {
Point[] pointsArr = new Point[101];
// 将点都构建出来
for (int i = 0; i < points.length; i++) {
pointsArr[i] = new Point(points[i][0], points[i][1]);
}
int ans = 1;
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
// 对所有点依次两两枚举,确定所有的圆
if (dist(pointsArr[i], pointsArr[j]) > 2.0 * r) {
continue;
}
// 分别求出各个圆的圆心
Point center = getCircle(pointsArr[i], pointsArr[j], r);
int count = 0;
// 再枚举所有的点,求出被圆包住的点的个数的最大值
for (int k = 0; k < points.length; k++) {
if (dist(center, pointsArr[k]) < 1.0 * r + eps) {
count++;
}
}
ans = Math.max(ans, count);
}
}
return ans;
}
private double dist(Point p1, Point p2) {
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
private Point getCircle(Point p1, Point p2, int r) {
Point mid = new Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
double angle = Math.atan2(p1.x - p2.x, p2.y - p1.y);
double d = Math.sqrt(r * r - Math.pow(dist(p1, mid), 2));
return new Point(mid.x + d * Math.cos(angle), mid.y + d * Math.sin(angle));
}
本次排名:
继续加油!!
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!