The 27th biweekly game

20200530

1460. Make two arrays equal by flipping the subarrays

Topic Description 1

You are given two arrays of integers of the same length, target and arr.

In each step, you can select any non-empty subarray of ARR and flip it. You can perform this procedure as many times as you like.

Return True if you can make arR identical to Target; Otherwise, return False.

Example 1:

Enter: target = [1.2.3.4], arr = [2.4.1.3]
Output: true,Explanation: You can make arR a target by following these steps:1-invert subarray [2.4.1], arR becomes [1.4.2.3]
2-invert subarray [4.2], arR becomes [1.2.4.3]
3-invert subarray [4.3], arR becomes [1.2.3.4] The above approach is not unique; there are several ways to turn an ARR into a target.Copy the code

Example 2:

Enter: target = [7], arr = [7]
Output: true,Explanation: ARR does not need to do any rollover to already be equal to target.Copy the code

Example 3:

Enter: target = [1.12], arr = [12.1]
Output:true
Copy the code

Example 4:

Enter: target = [3.7.9], arr = [3.7.11]
Output:false
Explanation: ARR has no numbers9", so it can't be target in any way.Copy the code

Example 5:

Enter: target = [1.1.1.1.1], arr = [1.1.1.1.1]
Output:true
Copy the code

❝

Tip:

  • target.length == arr.length
  • 1 <= target.length <= 1000
  • 1 <= target[i] <= 1000
  • 1 <= arr[i] <= 1000

Answer 1

To determine whether each element has the same number, use the hash table to store the target element, and use the iterator to determine whether each element is the same.

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        int len = target.length;
        Map<Integer, Integer> map =new HashMap<>();
        for(int i = 0; i < len; i++){
 map.put(target[i], map.getOrDefault(target[i], 0) + 1);  }  for(int i = 0; i < len; i++){  map.put(arr[i], map.getOrDefault(arr[i], 0) - 1);  }  Iterator iter = map.entrySet().iterator();  while(iter.hasNext()){  Map.Entry entry = (Map.Entry) iter.next();  Integer val =(Integer) entry.getValue();  if(val ! =0) { return false;  }  }  return true;   } } Copy the code

1461. Checks if a string contains all binary substrings of length K

2.

You are given a binary string S and an integer K.

Return True if all binary strings of length K are substrings of S, False otherwise.

Example 1:

Enter: s ="00110110", k = 2
Output:true
Explanation: The length is2The binary string includes"00"."01"."10" 和 "11". They are s with the subscript theta0.1.3.2The initial length is zero2The substring.Copy the code

Example 2:

Enter: s ="00110", k = 2
Output:true
Copy the code

Example 3:

Enter: s ="0110", k = 1
Output:true
Explanation: The length is1The binary string includes"0" 和 "1"And obviously they're all substrings of S.Copy the code

Example 4:

Enter: s ="0110", k = 2
Output:false
Explanation: The length is2Binary string of"00"It doesn't appear in s.Copy the code

Example 5:

Enter: s ="0000000001011100", k = 4
Output:false
Copy the code

❝

Tip:

  • 1 <= s.length <= 5 * 10^5
  • S only has 0’s and 1’s in it.
  • 1 <= k <= 20

Answer 2

  1. Creates an array that stores the decimal representation of all substrings, with subscripts corresponding to the numeric size. Array [I]++ = array[I]+ = array[I]++
class Solution {
    public boolean hasAllCodes(String s, int k) {
        int num = (int) Math.pow(2, k) - 1;
        int[] array = new int [num + 1];
        Arrays.fill(array, -1);
 int len = s.length();  String kString = Integer.toBinaryString(k);  int temp = 0;  for(int i = 0; i <= len - k; i++){  temp = Integer.parseInt(s.substring(i, i+k), 2);  array[temp]++;  }  for(int i = 0; i <= num; i++){  if(array[i] < 0) { return false;  }  }  return true;  } } Copy the code
  1. You can determine if the number of non-repeating substrings is one. Omit the increment time, use Set.
class Solution {
    public boolean hasAllCodes(String s, int k) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0, w = 0; i < s.length(); i++ ){
            w = w * 2 + s.charAt(i) - '0';
 if(i >= k){  w -= s.charAt(i - k) - '0' << k;  }  if(i >= k - 1) { set.add(w);  }  }  return set.size() == 1 << k;  } } Copy the code

1462. Course Arrangement IV

3.

You need to take a total of n courses, numbered from 0 to N-1.

Some courses have direct prerequisite courses. For example, if you want to take course 0, you must take course 1 first, then the number of prerequisite courses is given in the form of [1,0] pairs.

You are given the total number of courses N and one list of prerequisite courses and one list of prerequisite courses.

For each pair of queries[I], please determine whether queries[I][0] are pre-courses for queries[I][1].

Return a list of Boolean values. Each element in the list corresponds to the judgment result of each query pair.

Note: If course A is a prerequisite for course B and course B is a prerequisite for course C, then course A is also a prerequisite for course C.

Example 1:

Enter n =2, prerequisites = [[1.0]], queries = [[0.1], [1.0]]
Output:false.true]
Explanation: Courses0Is not a course1The prerequisite course, but the course1Is the course0Pre-requisite courses.Copy the code

Example 2:

Enter n =2, prerequisites = [], queries = [[1.0], [0.1]]
Output:false.false]
Explanation: There are no prerequisite courses, so each course is independent of the other.Copy the code

Example 3:

Enter n =3, prerequisites = [[1.2], [1.0], [2.0]], queries = [[1.0], [1.2]]
Output:true.true]
Copy the code

Example 4:

Enter n =3, prerequisites = [[1.0], [2.0]], queries = [[0.1], [2.0]]
Output:false.true]
Copy the code

Example 5:

Enter n =5, prerequisites = [[0.1], [1.2], [2.3], [3.4]], queries = [[0.4], [4.0], [1.3], [3.0]]
Output:true.false.true.false]
Copy the code

❝

Tip:

  • 2 <= n <= 100
  • 0 <= prerequisite.length <= (n * (n – 1) / 2)
  • 0 <= prerequisite[i][0], prerequisite[i][1] < n
  • prerequisite[i][0] ! = prerequisite[i][1]
  • There are no rings in the ap chart.
  • There are no duplicated edges in the ap chart.
  • 1 <= queries.length <= 10^4
  • queries[i][0] ! = queries[i][1]

Answer 3

Folyd algorithm, three layers1~nCycles, time complexity.

For (int m = 0; int m = 0; m < len; M++) and for(int[] q: queries).

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        int len = prerequisites.length;
        boolean[][] flag = new boolean[n][n];
        for(int m = 0; m < len; m++ ){
 flag[prerequisites[m][0]][prerequisites[m][1]] = true;  }  for(int k = 0; k < n; k++ ){  for(int i = 0; i < n; i++ ){  for(int j = 0; j < n; j++ ){  if(flag[i][k] && flag[k][j]){  flag[i][j] = true;  }   }  }  }  List<Boolean> res = new LinkedList<>();  for(int[] q : queries){  res.add(flag[q[0]][q[1]]);  }  return res;  } } Copy the code

1463. Cherry Picking II

4.

You are given a Grid of Rows X COLs to represent a cherry field. The number of cherries you can get in each cell of the grid.

You have two robots collecting cherries for you, robot 1 starting from the upper-left grid (0,0) and robot 2 starting from the upper-right grid (0, Cols-1).

Please return the maximum number of cherries that two robots can collect according to the following rules:

Starting from the cell (I,j), the robot can move to the cell (I +1, J-1), (I +1, j) or (I +1, j+1). When a robot passes by a cell, it picks all the cherries in the cell, and then the position becomes a blank, a cell with no cherries. When two robots arrive at the same cell at the same time, only one of them can pick a cherry. Neither robot can move outside the grid at any time. Both robots end up in the bottom row of the grid. Example 1:

Input: grid = [[3.1.1], [2.5.1], [1.5.5], [2.1.1]]
Output:24
Explanation: Robots1With the robot2The paths of are shown in green and blue respectively in the figure above.The robot1The number of cherries picked was (3 + 2 + 5 + 2) = 12 。
The robot2The number of cherries picked was (1 + 5 + 5 + 1) = 12 。
The total number of cherries:12 + 12 = 24 。 Copy the code

Example 2:

Input: grid = [[3.1.1], [2.5.1], [1.5.5], [2.1.1]]
Output:24
Explanation: Robots1With the robot2The paths of are shown in green and blue respectively in the figure above.The robot1The number of cherries picked was (3 + 2 + 5 + 2) = 12 。
The robot2The number of cherries picked was (1 + 5 + 5 + 1) = 12 。
The total number of cherries:12 + 12 = 24 。 Copy the code

Example 3:

Input: grid = [[1.0.0.3], [0.0.0.3], [0.0.3.3], [9.0.3.3]]
Output:22
Copy the code

Example 4:

Input: grid = [[1.1], [1.1]]
Output:4
Copy the code

❝

Tip:

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

Answer 4

In dynamic programming, dp[k][I][j] represents the maximum value of cherry harvesting by the first robot in column I and the second robot in column J in row I. So I minus one, I, I plus one times j minus one,j,j plus one in the k minus one row.

class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][][] dp = new int[rows][cols][cols];

 int res = 0;  for(int i = 0; i < rows; i++){  for(int j = 0; j < cols; j++){  Arrays.fill(dp[i][j], -1);  }  }  dp[0] [0][cols - 1] = grid[0] [0] + grid[0][cols - 1];   for(int k = 1; k < rows; k++){  for(int i = 0; i < cols; i++){  for(int j = 0; j < cols; j++){  for(int a = i - 1; a <= i + 1; a++){  for(int b = j - 1; b <= j + 1; b++){  if(a < 0 || a >= cols || b < 0 || b >= cols){  continue;  }  int t = dp[k -1][a][b];  if(t == -1) continue;  if(i == j) t += grid[k][j];  else t += grid[k][i] + grid[k][j];  dp[k][i][j] = Math.max(dp[k][i][j], t);   res = Math.max(res, dp[k][i][j]);  }  }  }  }  }   return res;  } } Copy the code

This article is formatted using MDNICE