LEETCODE总结(第189周赛)

本文最后更新于:10 个月前

🏆 第 189 场力扣周赛

题目列表:

3 分 - 在既定时间做作业的学生人数
4 分 - 重新排列句子中的单词
5 分 - 收藏清单
7 分 - 圆形靶内的最大飞镖数量

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

一道送分题,统计出在时间范围内的人数即可!

1
2
3
4
5
6
7
8
9
10
11
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 中取出,组合成结果句子
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
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() 函数循环判断是否是子集即可
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
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;
}

圆形靶内的最大飞镖数量

  • 将点都构建出来
  • 对所有点依次两两枚举,确定所有的圆
  • 分别求出各个圆的圆心
  • 再枚举所有的点,求出被圆包住的点的个数的最大值
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 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));
}

本次排名:

189-rank.png

继续加油!!