dustfree's blog
0%

Weekly Contest 192

Posted on In ,

Question

  1. Shuffle the Array

    Given the array nums consisting of 2n elements in the form [x1,x2,…,xn,y1,y2,…,yn].

    Return the array in the form [x1,y1,x2,y2,…,xn,yn].

    Example 1:
    Input: nums = [2,5,1,3,4,7], n = 3
    Output: [2,3,5,4,1,7]
    Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] shuffle(int[] num, int n) {
    int l = num.length;
    
    int[] res = new int[l];
    int k = 0;
    boolean sign = true;
    for (int i = 0, j = l/2; k < l;) {
        if (sign) {
            res[k++] = num[i++];
        }else {
            res[k++] = num[j++];
        }
        sign = !sign;
    }
    return res;
}

Question

  1. The k Strongest Values in an Array

    Given an array of integers arr and an integer k.

    A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m| where m is the median of the array.
    If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].

    Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] getStrongest(int[] arr, int k) {
    Arrays.sort(arr);
    int l = arr.length;
    
    int m = l % 2 == 0 ? arr[l/2-1] : arr[l/2];
            
    int[] res = new int[k];
    int index = 0;
    int i = 0, j = l-1;
    while (index < k) {
        if (Math.abs(arr[j]- m) >= Math.abs(m - arr[i])) {
            res[index++] = arr[j--];                
        }else {
            res[index++] = arr[i++];
        }
    }
    return res;        
}

Question

  1. Design Browser History

    You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

    Implement the BrowserHistory class:

    BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
    void visit(string url) visits url from the current page. It clears up all the forward history.
    string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.

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
Stack<String> s1 = new Stack<>();
Stack<String> s2 = new Stack<>();
public BrowserHistory(String homepage) {
    s1.push(homepage);
}

public void visit(String url) {
    s1.push(url);
    s2.clear();
}

public String back(int steps) {
    while (s1.size() > 1 && steps > 0 ) {
        s2.push(s1.pop());
        steps--;
    }
    return s1.peek();
}

public String forward(int steps) {
    while (s2.size() > 0 && steps > 0 ) {
        s1.push(s2.pop());
        steps--;
    }
    return s1.peek();
}

Question

  1. Paint House III

    There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

    A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

    Given an array houses, an m * n matrix cost and an integer target where:

    houses[i]: is the color of the house i, 0 if the house is not painted yet.
    cost[i][j]: is the cost of paint the house i with the color j+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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
Algorithm: 开始写了一个dfs剪枝的解法，只过了24个case。以后应该在考虑brute force之前先看下数据量。

DP解法int[i][j][k] i: house, j:neighborhoods总数，k:当前house的颜色
dp[i][j][k]存放当前neighbor数量下的最小cost;

状态转移方程： if (houses[i] != 0有颜色k) 无需染色 
dp[i][j][k] = Math.min(dp[i-1][j][k], All(dp[i - 1][j - 1][l]));
else {
    dp[i][j][k] = dp[i - 1][j][k] + cost[i - 1][k];
    dp[i][j][k] = Math.min(dp[i - 1][j - 1][l] + cost[i - 1][k], dp[i][j][k]); 
}
*/
public int minCost(int[] houses, int[][] cost, int m, int n, int target) { 
    int[][][] dp = new int[m + 1][target + 1][n]; 
    for (int i = 1; i <= m; i++) { 
        for (int j = 0; j <= target; j++) { 
            Arrays.fill(dp[i][j], 1000000); 
        } 
    } 
    for (int i = 1; i <= m; i++) { 
        if (houses[i - 1] != 0) { // 已经被染色, k 为固定值, 无需枚举 
            int k = houses[i - 1] - 1; 
            // j > i 也是无效状态 (街区数量不能超过房子数量) 
            for (int j = 1; j <= Math.min(target, i); j++) { 
                dp[i][j][k] = dp[i - 1][j][k]; // 加入最后一个街区 
                for (int l = 0; l < n; l++) { // 开始新街区 
                    if (l != k) { 
                        dp[i][j][k] = Math.min(dp[i - 1][j - 1][l], dp[i][j][k]); 
                    } 
                } 
            } 
        } else { // 尚未被染色 
            for (int j = 1; j <= Math.min(target, i); j++) { 
                for (int k = 0; k < n; k++) { 
                    dp[i][j][k] = dp[i - 1][j][k] + cost[i - 1][k]; // 加入最后一个街区 
                    for (int l = 0; l < n; l++) { // 开始新街区 
                        if (l != k) { 
                            dp[i][j][k] = Math.min(dp[i - 1][j - 1][l] + cost[i - 1][k], dp[i][j][k]); 
                        } 
                    } 
                } 
            } 
        } 
    } 

    int res = 1000000; 
    for (int i : dp[m][target]) { 
        res = Math.min(res, i); 
    } 
    return res < 1000000 ? res : -1; 
}