dustfree's blog
0%

Weekly Contest 193

Posted on In ,

Question

  1. Running Sum of 1d Array

    Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

    Return the running sum of nums.

    Example 1:
    Input: nums = [1,2,3,4]
    Output: [1,3,6,10]
    Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Solution

1
2
3
4
5
6
public int[] runningSum(int[] n) {        
    for (int i = 1; i < n.length; i++) {
        n[i] = n[i-1]+n[i];
    }
    return n;
}

Question

  1. Least Number of Unique Integers after K Removals

    Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

    Example 1:

    Input: arr = [5,5,4], k = 1
    Output: 1
    Explanation: Remove the single 4, only 5 is left.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
public int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int n : arr) map.put(n, map.getOrDefault(n, 0) + 1);
    List<Integer> l = new ArrayList<>(map.keySet());
    Collections.sort(l, (a, b) -> map.get(a) - map.get(b));
    int n = map.size(), remove = 0, idx = 0;
    while (k >= 0 && idx < n) {
        k -= map.get(l.get(idx++));
        if (k >= 0) remove++;
    }
    return n - remove;
}

Question

  1. Minimum Number of Days to Make m Bouquets

    Given an integer array bloomDay, an integer m and an integer k.

    We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

    The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

    Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

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
/*
Algorithm: 这题关键在于找一个最小的bloomDay，从0开始暴力检索会TLE
所以要用二分答案法
*/
public int minDays(int[] b, int m, int k) {
    int l = b.length;
    if (l < m * k) return -1;                
    
    int start = 0, end = 1000000000;
    while (start+1<end) {
        int mid = start+(end-start)/2;
        if (help(b, m, k, mid)) {
            end = mid;
        }else {
            start = mid;
        }
    }
    
    if (help(b, m, k, start)) return start;
    else return end;            
}

private boolean help(int[] b, int m, int k, int d) {        
    int count = 0, sum = 0;
    for (int i = 0; i < b.length; i++) {
        if (b[i] > d) count = 0;
        else if (++count == k){                
            if (++sum == m) return true;
            count = 0;
        }
    }
    return sum >= m;
}

Question

  1. Kth Ancestor of a Tree Node

    You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.

    Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

    The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

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
/*
Algorithm: 一步一步query会TLE，这里涉及到新的算法倍增算法，即按2的幂次查询
fa[i][j]表示node i在2^j的祖先
状态转移方程fa[i][j] = fa[fa[i][j-1]][j-1];
这样就可以将k分解成二进制,看里面有多少个bit 1，做多少次query。
*/
Map<Integer, List<Integer>> children;
int[][] fa;
public TreeAncestor(int n, int[] parent) {
    children = new HashMap<>();
    fa = new int[n][17];
    initiate(n, parent);  
    dfs(0);
}

private void initiate(int n, int[] parent) {         
    for (int i = 0; i < n; i++) {
        Arrays.fill(fa[i], -1);
        children.put(i, new ArrayList<>());
    }
    for (int i = 1; i < n; i++) {
        children.get(parent[i]).add(i);
        fa[i][0] = parent[i];
    }
}

private void dfs(int cnt) {
    for (int i = 1; fa[cnt][i-1] >= 0; i++) {
        fa[cnt][i] = fa[fa[cnt][i-1]][i-1];
    }
    for (int nxt : children.get(cnt)) {
        dfs(nxt);
    }
}

public int getKthAncestor(int node, int k) {
    for (int i = 0; k > 0; i++) {
        if ((k & 1) > 0) {
            node = fa[node][i];
            if (node < 0) return -1;
        }
        k = k >> 1;
    }
    return node;
}