LEETCODE总结(第189周赛)

🏆 第 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));
}

本次排名：

继续加油！！