The 192nd game of the week

20200607

1470. Rearrange arrays

Difficulty: Easy

Topic Description 1

Give you an array nums, 2 n elements in the array, according to the [x1, x2,…, xn, y1, y2,…, yn] the format of the array.

Please rearrange the array in [x1,y1,x2,y2,… xn,yn] format and return the rearranged array.

Example 1:

Enter: 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[A].2.3.5.4.1.7]
Copy the code

Example 2:

Enter: nums = [1.2.3.4.4.3.2.1], n = 4
Output:1.4.2.3.3.2.4.1]
Copy the code

Example 3:

Enter: nums = [1.1.2.2], n = 2
Output:1.2.1.2]
Copy the code

❝

Tip:

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

Solution1

traverse

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;  } } Copy the code

This 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;  } } Copy the code

1471. K strongest values in array

Difficulty: Medium

2.

I give you an integer array arr and an integer k.

If m is the median of the array, we can determine that the value of arr[I] is stronger than the value of arr[j] as long as one of the following two conditions is satisfied:

| arr [I] m | – > | arr [j] – m | | arr [I] – m | = = | arr [j] – m |, and arr [I] > arr [j] please return by the strongest k values in the array of list. 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 at (n-1) / 2 in the ordered list (subscripts start at 0).

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

Example 1:

Input: arr = [1.2.3.4.5], k = 2
Output:5.1]
Explanation: The median is3, sorted in order from strong to weak, the array becomes [5.1.4.2.3]. The two strongest elements are [5.1]. [1.5[is the correct answer.Note that although |5 - 3| = = |1 - 3|, but5 比 1Stronger because5 > 1 。
Copy the code

Example 2:

Input: arr = [1.1.3.5.5], k = 2
Output:5.5]
Explanation: The median is3, sorted in order from strong to weak, the array becomes [5.5.1.1.3]. The two strongest elements are [5.5].Copy the code

Example 3:

Input: arr = [6.7.11.7.6.8], k = 5
Output:11.8.6.6.7]
Explanation: The median is7, sorted in order from strong to weak, the array becomes [11.8.6.6.7.7].[11.8.6.6.7Any permutation of] is the correct answer.Copy the code

Example 4:

Input: arr = [6.- 3.7.2.11], k = 3
Output:- 3.11.2]
Copy the code

Example 5:

Input: arr = [7 -.22.17.3], k = 2
Output:22.17]
Copy the code

❝

Tip:

  • 1 <= arr.length <= 10^5
  • -10^5 <= arr[i] <= 10^5
  • 1 <= k <= arr.length

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;  } } Copy the code

Top K problem, you can also use priority queue

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;  }  }  });  // Iterate through the ARR array and put the subscript into 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;  } } Copy the code

1472. Design browser history

Difficulty: Medium

3.

You have a browser that supports a single TAB, and you start with a page in a homepage. You can access other urls and take steps backwards or forwards in your browser history.

Implement the BrowserHistory class:

  • BrowserHistory(string homepage)Initialize the browser class with homepage.
  • void visit(string url)Jumps from the current page to the corresponding page of the URL. This operation deletes all browsing history progress.
  • string back(int steps)Step back in your browsing history. If you can only go back a maximum of x steps in your browsing history andsteps > xSo you only take x steps backwards. Please return to the URL that is a few steps backward.
  • string forward(int steps)Step forward in your browsing history. If you can only advance up to x steps in browsing history andsteps > xSo you only take x steps forward. Return to the URL at most steps forward.

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". access"google.com" browserHistory.visit("facebook.com"); // You were browsing"google.com". access"facebook.com" browserHistory.visit("youtube.com"); // You were browsing"facebook.com". access"youtube.com" browserHistory.back(1); // You were browsing"youtube.com", back to the"facebook.com"And return"facebook.com" browserHistory.back(1); // You were browsing"facebook.com", back to the"google.com"And return"google.com" browserHistory.forward(1); // You were browsing"google.com"And forward to"facebook.com"And return"facebook.com" browserHistory.visit("linkedin.com"); // You were browsing"facebook.com". access"linkedin.com" browserHistory.forward(2); // You were browsing"linkedin.com"You can't take any steps forward.browserHistory.back(2); // You were browsing"linkedin.com"Take two steps back and get there first"facebook.com"And then to"google.com"And return"google.com" browserHistory.back(7); // You were browsing"google.com"You can only take one step back"leetcode.com"And return"leetcode.com" Copy the code

❝

Tip:

  • 1 <= homepage.length <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • The homepage and URL contain only ‘.’ or lowercase letters.
  • Call the visit, back, and forward functions up to 5000 times.

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); * / Copy the code

Paint the house with color III

Difficulty: difficulty

4.

In a small city, there are m houses in a row, and you need to paint each house with one of n colors (color numbers 1 to N). Some of the houses were painted last summer, so they don’t need to be repainted.

We call a block as many consecutive houses of the same color as possible. (say into =,2,2,3,3,2,1,1 [1], it contains five blocks [{1}, {2}, {3}, {2}, {1, 1}].)

You are given an array houses, an m * n matrix cost and an integer target, where:

  • houses[i]: it is the firstiThe color of the house,0It means the house has not been painted.
  • cost[i][j]: it is the firstiThe houses are paintedj+1The cost of.

Please return the minimum total cost of the house coloring scheme so that each house is painted exactly after the target block. If no coloring scheme is available, return -1.

Example 1:

Enter: 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 color scheme is [1.2.2.1.1]
This scenario contains target =3Each block is [{1}, {2.2}, {1.1}].The total cost of coloring is (1 + 1 + 1 + 1 + 5) = 9.Copy the code

Example 2:

Enter: 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 color scheme is [2.2.1.2.2]
This scenario contains target =3Each block is [{2.2}, {1}, {2.2}].The cost of painting the first and last houses is (10 + 1) = 11.Copy the code

Example 3:

Enter: 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
Copy the code

Example 4:

Enter: houses = [3.1.2.3], cost = [[1.1.1], [1.1.1], [1.1.1], [1.1.1]], m = 4, n = 3, target = 3
Output:- 1
Explanation: The house has been painted and formed4Each block is [{3}, {1}, {2}, {3}], cannot form target =3A block.Copy the code

Tip:

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 Copy the code

Soluion4

Three dimensional dynamic programming

Refer to the answer key

  • State definition: DP [I][j][k] represents the minimum cost of the ith house painted k color with J blocks

  • Boundary:

    For the first house:

    • If already colored, i.ehouses[0] ! = 0, the corresponding cost is 0
    • If it’s not colored,houses[0] == 0, there are n colors to be painted

  • State transition:

    • The ith house has already been painted
      • If house I is the same color as house I-1, then the number of blocks is the same
      • If the two houses are different colors, then the ith house is a block by itself
    • The ith house is not painted
class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // dp[I][j][k] after the first I house is painted, there are j blocks at present, and the cost of all schemes with the color of the I house is K is the smallest.
        // House starts at 0, block starts at 1, color starts at 1
        final int INF = (int)Math.pow(10.8);// If set to integer. MAX_VALUE, an error will occur and overflow should occur.
 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 the 0th house  // House 0 has been painted  if(houses[0] > 0) { dp[0] [1][houses[0]] = 0;  }else{  // The 0th house is not colored, initialize cost  for(int i = 1; i <= n; i++){  dp[0] [1][i] = cost[0][i - 1];  }  }  // Finish the I house color when the state is transferred.  for(int i = 1; i < m; i++){  // Target blocks at most  for(int j = 1; j <= target; j++){  // Divide into the ith house whether to paint  if(houses[i] > 0) { int temp = houses[i];  for(int k = 1; k <= n; k++){  // Divide into house I and house I-1  // If two houses are of the same color, the number of blocks is the same  // If the two houses are different colors, then the ith house is 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;  // 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;  } } Copy the code

❝

  • My public number: daily share LeetCode, let you walk on the road sitting in the car can also see the algorithm, welcome everyone scan code attention.

This article is formatted using MDNICE