dustfree's blog
0%

Weekly Contest 191

Posted on In ,

Question

  1. Maximum Product of Two Elements in an Array

    Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

    Example 1:

    Input: nums = [3,4,5,2]
    Output: 12
    Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12.

Solution

1
2
3
4
public int maxProduct(int[] nums) {        
    Arrays.sort(nums);
    return (nums[nums.length-1]-1) * (nums[nums.length-2]-1);
}

Question

  1. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

    Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

    Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Solution

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
/*
坑点在于mod一个值
*/
int M = (int)1e9+7;
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
    Arrays.sort(verticalCuts);
    Arrays.sort(horizontalCuts);
    
    long x = 0, y = 0;
    for (int i = 0; i < horizontalCuts.length; i++) {
        if (i == 0) {
            x = horizontalCuts[0];
        }else {
            x = Math.max(x, horizontalCuts[i]- horizontalCuts[i-1]);
        }
    }
    x = Math.max(x, h - horizontalCuts[horizontalCuts.length-1]);
    
    for (int i = 0; i < verticalCuts.length; i++) {
        if (i == 0) {
            y = verticalCuts[0];
        }else {
            y = Math.max(y, verticalCuts[i]- verticalCuts[i-1]);
        }
    }
    y = Math.max(y, w - verticalCuts[verticalCuts.length-1]);
    
    return (int)(x*y % M);
}
}

Question

  1. Reorder Routes to Make All Paths Lead to the City Zero

    There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

    Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

    This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

    Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

    It’s guaranteed that each city can reach the city 0 after reorder.

Solution

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
int res = 0;
public int minReorder(int n, int[][] connections) {
    List<Integer>[] graph = new ArrayList[n];
    
    for(int i = 0; i < n; i++){
        graph[i] = new ArrayList<>();
    }
            
    for(int[] cur : connections){
        graph[cur[0]].add(cur[1]);
    }
    
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            continue;
        }
        dfs(graph, i, visited);
    }
    return res;
}

public void dfs(List<Integer>[] graph, int cur, boolean[] visited) {
    visited[cur] = true;
    for (int next : graph[cur]) {
        if (visited[next]) {
            continue;
        }
        res++;
        dfs(graph, next, visited);
    }
}

Question

  1. Probability of a Two Boxes Having The Same Number of Distinct Balls

    Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i.

    All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).

    Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).

    We want to calculate the probability that the two boxes have the same number of distinct balls.

Solution

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
50
51
/*
Algorithm:只想到了dfs暴力解法，求出所有的answer/combination，后来超时。
学习了一下https://seattler.io/thread-1351.htm?from=groupmessage&isappinstalled=0。
需要用到排列组合公式来优化。
*/
private int sum;
public double getProbability(int[] balls) {
    sum = 0;
    for (int ball : balls) {
        sum += ball;
    }
    return 1.0 * dfs(0, 0, 0, 0, 0, 1, balls) / C(sum / 2, sum);
}

// i 表示枚举到哪种球了
// j1, j2 表示两个盒子中球的数量, 最终两个盒子中球的数量都是 sum / 2
// k1, k2 表示两个盒子中颜色的数量, 最终 k1 == k2
// cnt 表示走到当前这一种状态的方案数量
private long dfs(int i, int j1, int j2, int k1, int k2, long cnt, int[] balls) {
    if (j1 > sum / 2 || j2 > sum / 2) {
        return 0;
    }
    if (i == balls.length) {
        return k1 == k2 ? cnt : 0;
    }
    long res = 0;
    // 考虑 balls[i] 有多少个球放进了盒子 1
    // 把 j 个球放进盒子 1 的方案数为 C(j, balls[i])
    // 乘法原理
    res += dfs(i + 1, j1, j2 + balls[i], k1, k2 + 1, cnt * 1, balls);
    res += dfs(i + 1, j1 + balls[i], j2, k1 + 1, k2, cnt * 1, balls);
    for (int j = 1; j < balls[i]; j++) {
        res += dfs(i + 1, j1 + j, j2 + balls[i] - j, k1 + 1, k2 + 1, 
                cnt * C(j, balls[i]), balls);
    }
    return res;
}

private long[][] memC = new long[25][50];

// 公式C(n,m) = C(n-1,m-1) + C(n,m-1);
private long C(int a, int b) {
    if (a == b || a == 0) {
        return 1;
    }
    if (memC[a][b] > 0) {
        return memC[a][b];
    }
    memC[a][b] = C(a - 1, b - 1) + C(a, b - 1);
    return memC[a][b];
}