Week 192

20200607

1470. Rearranging arrays

Difficulty: simple

Title Description 1

Give you an array nums, there are 2n elements in the array, press [x1,x2 ,xn,y1,y2,… , yn].

Please press [x1,y1,x2,y2 , xn,yn] format rearrangement, return the rearranged array.

Example 1:

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

Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4
 Output: [1,4,2,3,3,2,4,1]

Example 3:

Input: nums = [1,1,2,2], n = 2
 Output: [1,2,1,2]

Tips:

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

Solution1

ergodic

class Solution {
    public int[] shuffle(int[] nums, int n) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            list.add(nums[i]);
            list.add(nums[i+n]);
        }
        int[] ans = new int[2*n];
        ans = list.stream().mapToInt(Integer::valueOf).toArray();
        return ans;
    }
}

It should be faster

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int len = nums.length;
        int[] res = new int[len];
        for(int i = 0; i < n; i++){
            res[2 * i] = nums[i];
            res[2*i + 1] = nums[n + i];
        }
        return res;
    }
}

1471. k strongest values in the array

Difficulty: medium

Title Description 2

Here's an arr ay of integers, AR, and k.

If m is the median of the array, the value of arr[i] is stronger than that of arr[j] as long as one of the following two premises is satisfied:

|arr[i] - m| > |arr[j] - m|
|arr[i] - m| == |arr[j] - m|, and arr [i] > arr [J]
Please return a list of the strongest k values in the array. The answers can be returned in any order.

The median is the value in the middle of an ordered list of integers. Formally, if the length of the list is n, then the median is the element in the (n - 1) / 2) sequence table (the subscript starts from 0).

• For example, arr = [6, -3, 7, 2, 11], n = 5: after array sorting, arr = [-3, 2, 6, 7, 11], the middle position of array is m = ((5-1) / 2) = 2, and the value of median arr[m] is 6.
• For example, arr = [-7, 22, 17,   3], n = 4: after the array is sorted, arr = [-7, 3, 17, 22], the middle position of the array is m = ((4-1) / 2) = 1, and the value of the median arr[m] is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
 Output: [5,1]
Explanation: the median is 3. After sorting from strong to weak, the array becomes [5,1,4,2,3]. The two strongest elements are [5, 1]. [1, 5] is also the right answer.
Note that although | 5 - 3| = | 1 - 3|, 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
 Output: [5,5]
Explanation: the median is 3. After sorting from strong to weak, the array becomes [5,5,1,1,3]. The two strongest elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
 Output: [11,8,6,6,7]
Explanation: the median is 7. After sorting from strong to weak, the array becomes [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is the correct answer.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
 Output: [- 3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
 Output: [22,17]

Solution2

Sort + double pointer

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        Arrays.sort(arr);
        int len = arr.length;
        if(k == len){
            return arr;
        }
        int mid = arr[(len - 1) / 2];
        int[] res = new int[k];
        int i = 0, j = len - 1;
        while(k > 0 &&i < j){
            if(compare(arr[i], arr[j], mid)){
                res[k - 1] = arr[i];
                i++;
                k--;
            }else{
                res[k - 1] = arr[j];
                j--;
                k--;
            }
        }
        return res;

    }
    public boolean compare(int a, int b,int m){
        boolean flag = false;
        if(Math.abs(a - m) > Math.abs(b - m) ||(Math.abs(a - m) == Math.abs(b - m) && a > b)){
            flag = true;
        }
        return flag;
    }
}

For top K problem, priority queue can also be used

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        int m = arr[(n - 1) / 2];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int a = Math.abs(arr[o1] - m);
                int b = Math.abs(arr[o2] - m);
                if (a == b) {
                    return arr[o1] - arr[o2];
                } else {
                    return a - b;
                }
            }
        });
        // Traverse the arr array and put the subscript in the priority queue
        for (int i = 0; i < arr.length; i++) {
            queue.add(i);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < result.length; i++) {
            result[i] = arr[queue.poll()];
        }
        return result;
    }
}

1472. Design browser history

Difficulty: medium

Title Description 3

You have a browser that only supports a single tab. The first page you browse is homepage. You can visit other website URLs, or step back or step forward in browsing history.

Please implement BrowserHistory class:

• BrowserHistory(string homepage), initialize the browser class with homepage.
• void visit(string url) jumps from the current page to visit the page corresponding to the url. Performing this operation will delete all records of browsing history advance.
• string back(int steps) step back in browsing history. If you can only go back up to x steps in browsing history and steps > x, then you only go back x steps. Please go back to the url after the most steps step.
• string forward(int steps) steps forward in browsing history. If you can only advance up to x steps in browsing history and steps > x, then you only advance x steps. Please go back to the url after the most steps.

Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
//Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

//Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You were browsing“ leetcode.com " .  Visit“ google.com "
browserHistory.visit("facebook.com");     // You were browsing“ google.com " .  Visit“ facebook.com "
browserHistory.visit("youtube.com");      // You were browsing“ facebook.com " .  Visit“ youtube.com "
browserHistory.back(1);                   // You were browsing“ youtube.com ", back to" facebook.com "And back" facebook.com "
browserHistory.back(1);                   // You were browsing“ facebook.com ", back to" google.com "And back" google.com "
browserHistory.forward(1);                // You were browsing“ google.com ", forward to" facebook.com "And back" facebook.com "
browserHistory.visit("linkedin.com");     // You were browsing“ facebook.com " .   Visit“ linkedin.com "
browserHistory.forward(2);                // You were browsing“ linkedin.com ", you can't go any further.
browserHistory.back(2);                   // You were browsing“ linkedin.com "First in two steps" facebook.com ", and then to" google.com ", and return" google.com "
browserHistory.back(7);                   // You were browsing“ google.com ", you can only step back to" leetcode.com ", and return" leetcode.com "

Solution3

Double stack

class BrowserHistory {
    Stack<String> stack1;
    Stack<String> stack2;

    public BrowserHistory(String homepage) {
        stack1 = new Stack<String>();
        stack2 = new Stack<String>();
        stack1.push(homepage);
    }

    public void visit(String url) {
        stack1.push(url);
        if(!stack2.isEmpty()){
            stack2 = new Stack<String>();
        }
    }

    public String back(int steps) {
        if(steps > stack1.size()-1){
            steps = stack1.size()-1;
        }
        for(int i = 1; i <= steps; i++){
            String tmp = stack1.pop();
            stack2.push(tmp);
        }
        return stack1.peek();
    }

    public String forward(int steps) {
        if(steps > stack2.size()){
            steps = stack2.size();
        }
        for(int i = 1; i <= steps; i++){
            String tmp = stack2.pop();
            stack1.push(tmp);
        }
        return stack1.peek();
    }
}

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory obj = new BrowserHistory(homepage);
 * obj.visit(url);
 * String param_2 = obj.back(steps);
 * String param_3 = obj.forward(steps);
 */

1473. Color the house III

Difficulty: difficulty

Title Description 4

In a small city, there are m houses in a row. You need to paint each house with one of N colors (color number is 1 to n). Some houses have been painted last summer, so they don't need to be repainted.

We call houses of the same color as many as possible one block in a row. (for example, houses = [1,2,2,3,3,2,1,1], which contains five blocks [{1}, {2,2}, {3,3}, {2}, {1,1}].)

I'll give you an array houses, a matrix cost of m * n and an integer target, where:

• houses[i]: it's the color of the ith house. 0 means the house hasn't been painted yet.
• cost[i][j]: the cost of painting the ith house with color j+1.

Please go back to the minimum total cost of the house coloring scheme, so that each house is painted and just constitutes a target block. If no color scheme is available, return to - 1.

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10], [10,1], [10,1], [1,10], [5,1], M = 5, n = 2, target = 3
 Output: 9
 Explanation: the house painting scheme is [1,2,2,1,1]
This scheme includes target = 3 blocks, namely [{1}, {2,2}, {1,1}].
The total cost of coloring is (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10], [10,1], [10,1], [1,10], [5,1], M = 5, n = 2, target = 3
 Output: 11
 Explanation: some houses have been painted. On this basis, the painting scheme is [2,2,1,2,2]
This scheme includes target = 3 blocks, namely [{2,2}, {1}, {2,2}].
The cost of painting the first and last house is (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10], [10,1], [1,10], [10,1], [1,10], M = 5, n = 2, target = 5
 Output: 5

Example 4:

Input: houses = [3,1,2,3], cost = [[1,1,1], [1,1,1], [1,1,1], M = 4, n = 3, target = 3
 Output: - 1
 Explanation: the house has been painted and made up of 4 blocks, namely [{3}, {1}, {2}, {3}], unable to form target = 3 blocks.

Tips:

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Soluion4

3D dynamic planning

Reference questions

• Status definition: dp[i][j][k] represents the ith house painted with K color, with the minimum cost of j blocks

• Boundary:

  For the first house:

  • If the color has been painted, i.e. houses [0]! = 0, the corresponding cost is 0
  • If there is no coloring, houses[0] == 0, there are n colors to be painted

• State transition:

  • The ith house has been painted
    • If the color of house i and house i-1 are the same, the number of blocks is the same
    • If the two houses are of different colors, the i house will be a block by itself
  • House i is not painted

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // I house before dp[i][j][k] painting, there are j blocks at present, and the color of the I house is k, all schemes cost the least.
        // The house starts from 0, the block starts from 1, and the color starts from 1
        final int INF = (int)Math.pow(10, 8);//If set to Integer.MAX_VALUE will fail, it should overflow.
        int[][][] dp = new int [m+1][target+1][n+1];
        for(int i = 0; i < m + 1; i++){
            for(int j = 0; j < target + 1; j++){
                for(int k = 0; k < n + 1; k++){
                    dp[i][j][k] = INF;
                }
            }
        }
        // Initialize house 0
        // House 0 has been painted
        if(houses[0] > 0){
            dp[0][1][houses[0]] = 0;
        }else{
            // House 0 is not painted, initialize cost
            for(int i = 1; i <= n; i++){
                dp[0][1][i] = cost[0][i - 1];
            }
        }
        // Finish painting the ith house when the state changes.
        for(int i = 1; i < m; i++){
            // target blocks at most
            for(int j = 1; j <= target; j++){
                // Is the house i painted
                if(houses[i] > 0){
                    int temp = houses[i];
                    for(int k = 1; k <= n; k++){
                        // Divided into house i and house i-1
                        // If the two houses are the same color, the blocks will be the same
                        // If the two houses are of different colors, the i house will be a block by itself
                        if(temp == k){
                            dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j][k]);
                        }else{
                            dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j - 1][k]);
                        }
                    }
                }else{
                    for(int k = 1; k <= n; k++){
                        for(int s = 1; s <= n; s++){
                            if(k == s){
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][s] + cost[i][k - 1]);
                            }else{
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][s] + cost[i][k - 1]);
                            }
                        }
                    }

                }
            }
        }
        int res = INF;
        // Go through it and find the minimum target for the m-1 house block.
        for(int i = 1; i <= n; i++){
            res = Math.min(res, dp[m-1][target][i]);
        }
        if(res == INF) return -1;
        return res;
    }
}