Weekly Contest 189

https://leetcode.com/contest/weekly-contest-189

Number of Students Doing Homework at a Given Time

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:
Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn’t doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn’t doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

LeetCodeleetcode.com/problems/number-of-students-doing-homework-at-a-given-time

Solution

public int busyStudent(int[] startTime, int[] endTime, int queryTime) {        
    int res = 0;
    for (int i = 0; i < startTime.length; i++) {
        if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
            res++;
        }
    }
    return res;
}

Rearrange Words in a Sentence

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.
Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = “Leetcode is cool”
Output: “Is cool leetcode”
Explanation: There are 3 words, “Leetcode” of length 8, “is” of length 2 and “cool” of length 4.
Output is ordered by length and the new first word starts with capital letter.

LeetCodeleetcode.com/problems/rearrange-words-in-a-sentence

Solution

public String arrangeWords(String text) {
    if (text.length() == 0) {
        return text;
    }
    
    text = (char)(text.charAt(0) + 32) + text.substring(1,text.length());
    String[] str = text.split(" ",0);
    
    Arrays.sort(str, (o1,o2) ->o1.length() - o2.length());
    
    StringBuilder res = new StringBuilder();
    for (String s: str) {
        res.append(s);
        res.append(" ");
    }
    text = res.toString().substring(0,res.length()-1);
    text = (char)(text.charAt(0) - 32) + text.substring(1,text.length());
    return text;
}

People Whose List of Favorite Companies Is Not a Subset of Another List

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

Example 1:
Input:favoriteCompanies = [[“leetcode”,”google”,”facebook”],[“google”,”microsoft”],[“google”,”facebook”],[“google”],[“amazon”]]
Output: [0,1,4]
Explanation:
Person with index=2 has favoriteCompanies[2]=[“google”,”facebook”] which is a subset of favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] corresponding to the person with index 0.
Person with index=3 has favoriteCompanies[3]=[“google”] which is a subset of favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] and favoriteCompanies[1]=[“google”,”microsoft”].
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

LeetCodeleetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list

Solution

/*
brute force: O(n^3)
*/
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
    List<Integer> res = new ArrayList<>();
    if (favoriteCompanies.size() == 0 || favoriteCompanies.get(0).size() == 0) {
        return res;
    }
    int size = favoriteCompanies.size();
    Map<Integer, Set<String>> map = new HashMap<>();
    
    for (int i = 0; i < favoriteCompanies.size(); i++) {
        map.put(i, new HashSet<String>());
    }
    
    for (int i = 0; i < size; i++) {
        Set<String> set = map.get(i);
        for (int j = 0; j < favoriteCompanies.get(i).size(); j++) {
            set.add(favoriteCompanies.get(i).get(j));
        }
    }
    
    boolean exist = false;
    for (int i = 0; i < size; i++) {
        exist = false;
        for (int j = 0; j < size; j++) {
            if (i == j) {
                continue;
            }
            boolean temp = true;
            Set<String> cur = map.get(j);
            for (int k = 0; k < favoriteCompanies.get(i).size(); k++) {                    
                if (!cur.contains(favoriteCompanies.get(i).get(k))) {
                    temp = false;
                    break;
                }
            }
            exist = exist | temp;
            if (exist) {
                break;
            }
        }
        if (!exist) {
            res.add(i);
        }
    }
    return res;
}

Maximum Number of Darts Inside of a Circular Dartboard

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:
Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

LeetCodeleetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard

Solution

先考虑了求三个点构成的三角形的外心，以这个点为圆心，遍历其他点，到外心的距离小于半径则记录count。
发现只过了40多个case，解法有问题。学习了一下，见以下解法。

/*
参考：https://seattler.io/thread-1163.htm?from=groupmessage&isappinstalled=0
@param: int[][] points 点的坐标, r 半径
@return: int 最大覆盖圆的数
算法：假设有一个大圆可以覆盖所有的点，然后将这个大圆压缩，直到有两个点在圆上，然后根据这两个点和给定的半径确定一个圆。遍历其他点，是否在这个圆中。
即枚举所有的两点组合，然后结合半径求出圆心坐标，遍历其他点，与圆心的距离小于r，则count++，求max count；
*/
class Point {
    double x;
    double y;
    Point() {}
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
final double precision = 1e-6;
int max = 1;
public int numPoints(int[][] points, int r) {
    if (points.length == 1) {
        return 1;
    }
    
    if (points.length == 2) {
        if (distance(points[0][0], points[0][1], points[1][0], points[1][1]) - r * r < precision) {
            return 2;
        }
    }
    for (int i = 0; i < points.length-1; i++) {
        for (int j = i+1; j < points.length; j++) {
            help(new Point(points[i][0],points[i][1]), new Point(points[j][0], points[j][1]), r, points);
        }
    }
    return max;
}

public void help(Point a, Point b, int r, int[][] points) {
        double x1 = a.x;
        double y1 = a.y;
        double x2 = b.x;
        double y2 = b.y;
    
        double mx = (x1 + x2) / 2.0;
        double my = (y1 + y2) / 2.0;
        double dx = x1 - x2;
        double dy = y1 - y2;
        double dis = Math.sqrt(dx * dx + dy * dy);
        double disR = Math.sqrt(r * r - dis * dis / 4);
        double dxR = -dy / dis;
        double dyR = dx / dis;
        double x = mx + (-dy/dis) * disR;
        double y = my + (dx/dis) * disR;
        check(new Point(x, y), r, points);
        x = mx - dxR * disR;
        y = my - dyR * disR;
        check(new Point(x, y), r, points);
}

public void check(Point pr, int r, int[][] points) {
    int count = 0;
    for (int[] p : points) {
        double dx = pr.x - p[0];
        double dy = pr.y - p[1];
        double d = dx*dx + dy*dy - r*r;
        if (d <= precision) {
            count++;
        }
    }
    max = Math.max(max, count);
}

public double distance(int x1, int y1, int x2, int y2) {
    double d= (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
    return d;
}