In the school enrollment, I carefully savor these questions… | the nuggets technical essay
January 18, 2024
by Kevin Rodriguez
No Comments
I Beijing a college computer master, always feel undergraduate graduation or not long ago, in a twinkling of an eye graduate students also want to graduate, in July began to put into the school to recruit army, so far also accumulated some interview writing questions and personal learning summary, now share a wave, I hope to be helpful to everyone. SKR ~ ~ π
Toutiao back end direction pen questions
Problem 1: character swapping
The title
The string S consists of lowercase letters with length N. Defines an operation that can swap any two adjacent letters in a string each time. Ask how many consecutive positions in a string have the same letter after swapping at most m times. Input description:
The first behavior is a string S and a non-negative integer m. (1 <= |S| <= 1000, 1 <= m <= 1000000)
Output description:
A non-negative integer representing the longest number of consecutive letters of the same character after an operation.
Enter Example 1:
abcbaa 2
Output Example 1:
2
Example Description 1: At least three operations are required to make two letters a appear consecutively. So you move a from position 1 to position 4. So in the case of at most two operations, at most two B’s or two A’s can occur consecutively.
Train of thought
Dynamic programming. Taking the a character as an example, let dp[I][j] represent the number of switches that move all the A characters together from the ith a character (inclusive) to the JTH A character (inclusive), we can know that the cost of moving all the characters to the middle is minimal. At the same time, assuming that all the characters a from the I + 1 a character to the J-1 A character have been moved together, regardless of their position, it is only necessary to move the a character in the I position and the J position between them. The minimum number of operations to put together the i-th a character (including) to the th, The number of operations must be the subscript of the JTH a character minus the subscript of the ith a character plus the number of all characters a between the I + 1 A character and the j-1 A character.
package exam.q3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import static java.lang.Math.max;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String str = sc.next();
int m = sc.nextInt();
int len = str.length();
HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
for(int i = 0 ; i < len; i ++) {
ArrayList<Integer> index = map.getOrDefault(str.charAt(i), new ArrayList<>());
index.add(i);
map.put(str.charAt(i), index);
}
int ans = 0;
for(char k: map.keySet()){
ArrayList<Integer> index = map.get(k);
int lenOfIndex = index.size();
int[][] dp = new int[lenOfIndex][lenOfIndex];
for(int i = 0; i < lenOfIndex - 1; i++) {
dp[i][i + 1] = index.get(i + 1) - 1 - index.get(i);
}
for(int num = 2; num <= lenOfIndex; num++) {
for(int i = 0; i < lenOfIndex - num + 1; i++) {
dp[i][i + num - 1] = dp[i + 1][i + num - 2] + index.get(i + num - 1) - index.get(i) + 1 - num;
if(dp[i][i + num - 1] <= m) {
//System.out.println(k + "" + index.get(i) + "" + index.get(i + num - 1) + "" + num + ""+ dp[i][i + num - 1]); ans = max(ans, num); } } } } System.out.println(ans); sc.close(); }}Copy the code
Second problem: second order Rubik’s cube
The title
The second order rubik’s cube is also called the small Rubik’s cube, which is a cube structure of 2*2*2. There are 4 blocks on each side for a total of 24 blocks. Each operation can rotate any side by 90Β° counterclockwise or clockwise. For example, rotate the top side by 90Β° counterclockwise as follows.
Nero made some changes to the cube, replacing the color on each block with a number, called the Digital Cube. The beauty of each face of a Rubik’s cube is the product of the four numbers on the face, and the total beauty of the cube is the sum of the six faces. Now Nero has a numerical rubik’s cube, and he wants to know how graceful it can be in no more than five manipulations. The serial number of each piece after the rubik’s cube is expanded is shown below:
Input description:
Enter 24 numbers in a row and give the number on each cube in sequence. All values range from -100,100.
Input description:
The output line contains a number indicating maximum elegance.
Enter Example 1:
2-3-2 3 7-6-6-7 9-5-9-3-2 1 4-9-1-10-5 5-10-4 8 2
Output Example 1:
8281
Train of thought
Originally, I wanted to use classes to abstract each face of the Rubik’s cube, and then simulate the rotation of the Cube, but it was too complicated, not only to store the upper and lower sides of each face, but also to abstract out each grid of each face, because the adjacent grid of different grids is not the same, and change its adjacent grid when rotating.
Later I looked up the solution and found a very clever way, using the permutation group method.
Each rotation, as long as the rotation way is the same, the fixed position of the grid will be replaced to another fixed position, as long as the kind of rotation with the displacement group to figure out, a total of six rotation, vertical up and down, horizontal left and right rotation and vertical left and right rotation.
There is a game of pushing boxes, which starts out as follows:
In the figure above, ‘. ‘represents reachable position,’ # ‘represents unreachable position, where S represents your starting position, 0 represents the initial box position, and E represents the expected box position. You can walk up, down, left, or right to any side of the box and push it to the other side. Push the box one space to the right as shown below;
. S0.. – >… S0.
Note that you cannot push boxes onto ‘#’ or out of bounds;
Now, to give you the initial look of the game, you need to output at least a few steps to complete the game, or -1 if not. Input description: The first act of two numbers,n, m, indicating that the game disk size has N rows and m columns (5< n, m < 50); Followed by n lines of string, each line of string has m characters, representing the game board; Output description: a number indicating the minimum number of steps to complete the game, if not, output -1;
Enter Example 1:
3 6 .S#.. E .#.0.. …
Output Example 1:
11
Train of thought
Simple 4-d BFS, note both the person’s position and the box’s position
code
package exam1.q3;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
private static class Status{
int x, y;
int bx, by;
int st;
public Status(int x, int y, int bx, int by, int st) {
super();
this.x = x;
this.y = y;
this.bx = bx;
this.by = by;
this.st = st;
}
}
private static final int[][] step = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private static int n, m;
private static int pushBox(char[][] map) {
int px = -1, py = -1;
int bx = -1, by = -1;
boolean[][][][] visited = new boolean[n][m][n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(map[i][j] == 'S') {
px = i;
py = j;
}
elseif(map[i][j] == '0') {
bx = i;
by = j;
}
}
}
int st = 0;
Status s = new Status(px, py, bx, by, st);
LinkedList<Status> queue = new LinkedList<>();
queue.addLast(s);
visited[px][py][bx][by] = true;
while(! queue.isEmpty()) { s = queue.pollFirst(); px = s.x; py = s.y; bx = s.bx; by = s.by; st = s.st;for(int i = 0; i< 4; i++) {
int nextx = px + step[i][0];
int nexty = py + step[i][1];
if(nextx >= 0 && nextx < n && nexty >= 0 && nexty < m) {
if(! (map[nextx][nexty] ==The '#') && !visited[nextx][nexty][bx][by]) {
if(nextx == bx && nexty == by) {
int nextbx = bx + step[i][0], nextby = by + step[i][1];
if(nextbx >= 0 && nextbx < n && nextby >= 0 && nextby < m && ! (map[nextbx][nextby] ==The '#')){
Status news = new Status(nextx, nexty, nextbx, nextby, st + 1);
queue.addLast(news);
visited[nextx][nexty][nextbx][nextby] = true;
if(map[nextbx][nextby] == 'E') {
returnst + 1; }}}else{
Status news = new Status(nextx, nexty, bx, by, st + 1);
queue.addLast(news);
visited[nextx][nexty][bx][by] = true;
}
}
}
}
}
return- 1; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); char[][] map = new char[n][m];for(int i = 0; i < n; i++) { String tmp = sc.next(); map[i] = tmp.toCharArray(); } System.out.println(pushBox(map)); sc.close(); }}Copy the code
Question 4: Room allocation
The title
There are n rooms, and now the people in room I need to be reassigned. The rules of allocation are as follows: First let all the people in room I out, and then follow the rules of I +1, I +2, I +3… Put one person in each of these rooms in that order, and the next room in n is room 1, until all the people have been reassigned.
Now, if I tell you the number of people in each room after the assignment and the number of room x to which the last person was assigned, you have to figure out the number of people in each room before the assignment. Data guarantee there must be a solution, if there are multiple solutions output any one solution. Input description: The first line of two integers n, x (2<=n<=10^5, 1<=x<=n), representing the number of rooms in the room and the room number assigned to the last person; The second line contains n integers a_i(0<=a_i<=10^9), representing the number of people in each room after allocation.
Enter Example 1:
3, 1, 6, 5, 1
Output Example 1:
4 April 4
Train of thought
Figure out the number of the last assigned person’s room x, find the number of the last assigned person’s original room num, set the last assigned person’s original room number as startx,
If (x + n) % – startx = num % n
The original room must be one of the smallest currently, because it was set to 0 before the last allocation, and must be num/n after the allocation.
But the room with the fewest numbers is not necessarily unique, because there may be other rooms with zero numbers before the last allocation. You also need to determine whether all rooms between the current location and startx are larger than the minimum.
code
package exam1.q4;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n, x;
n = sc.nextInt();
x = sc.nextInt();
long[] a = new long[n];
long min = Long.MAX_VALUE;
int startx = -1;
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
if(a[i] < min) {
min = a[i];
}
}
x--;
sc.close();
for(int i = 0; i < n; i++) {
if(a[i] == min) {
int tmp = x - i;
if(tmp < 0)
tmp += n;
boolean f = true;
for(int j = 1; j <= tmp; j++) {
if(a[(i + j) % n] < min + 1){
f = false;
break; }}if(f){
startx = i;
break;
}
}
}
long remain = 0;
if(x < startx)
remain = x + n - startx;
else
remain = x - startx;
long round = min;
for(int i = 0; i < n; i++)
a[i] -= round;
for(int i = 1; i <= remain; i++)
a[(startx + i) % n] -= 1;
a[startx] = round * n + remain;
for(int i = 0; i < n; i++)
System.out.print(a[i] + ""); System.out.println(); }}Copy the code
Number five: Hopscotch
The title
There are n + 1 rooms, each of which is room 1, room 2, room 3… I, there is A portal in each room, and the portal in room I can send people to room PI (1<= PI <= I). Now passer-by A starts from room 1 (the current room 1 is the first visit), and he has two movement strategies each time he moves: A. If the current room I is visited an even number of times, then the next move is to room I +1; B. If the current room I has been visited an odd number of times, then move to room PI; Now passer-by a wants to know how many moves it takes to get to room n+1; Input description: The first line contains a number n(30% data 1 <= n <= 100, 100% data 1 <= n <= 1000), which indicates the number of rooms. The next line contains n numbers PI (1 <= PI <= I), which indicates that room I can be sent to room PI. Output description: Output a line of numbers, indicating the number of final moves. The final result needs to be modulo 1000000007 (10E9 + 7).
Enter Example 1:
2 1 2
Output Example 1:
4
Example 1:
So I’m only going to go from room 1 once so I can only go to p1, room 1, and then I’m going to use strategy A to go to room 2, so I’m going to use strategy B to go to room 2, and then I’m going to use strategy A to go to room 3, so it takes 4 steps to get to room 3.
Ideas:
Note that PI (1 <= PI <= I), which means that you can only jump to the room in front of you the odd time, also means that to jump to some room I that has never been reached, you must pass an even number of times i-1, and all the rooms before i-1 must pass an even number of times.
This condition guarantees that the optimal solution of substructure can be used
Let dp[I] represent the steps taken to get to room I the second time. First of all, if we arrive at room I for the first time, we must have passed through room I — 1 twice, that is, the number of steps is dp[I — 1] + 1.
Also, since this is the first time to room I, the next step will be PI, and the number of steps will be updated to dp[I — 1] + 2. To get to room I again, you must pass through room I-1 twice more. At this time, the state of the former I-1 room is:
Except for the odd number of times that room PI has passed through, all the other rooms have an even number of times, which is the same as when room PI was first reached. The number of steps taken when reaching PI for the first time is dp[PI — 1] + 1.
At this time again want to reach the room, I must again twice after I – 1, from the state to a state of twice after I – 1 the required steps, equal to arrive from initial state to a second room I – 1 when the state of the steps needed to subtract from initial state to a state of the room for the first time PI steps needed, That is, dp[I — 1] — (dp[PI — 1] + 1), take another step and reach room I for the second time.
To sum up, the state transition equation of the number of steps to room I for the second time is:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
long mod = 1000000007;
int n = sc.nextInt();
int[] next = new int[n + 1];
for(int i = 1; i <= n; i++) {
next[i] = sc.nextInt();
}
long[] dp = new long[n + 1];
if(n == 1)
System.out.println(1);
else {
for(int i = 1; i <= n; i++) { dp[i] = ((dp[i - 1] * 2) % mod - dp[next[i] - 1] + 2) % mod; } } System.out.println((dp[n]) % 1000000007); sc.close(); }}Copy the code
Netease school recruitment programming questions
1. Tidy your room
The title
It was the weekend again, and Xiao Yi’s room was in a mess. He wanted the clutter on the floor to look a little more compact and less cluttered. There are n masses of clutter on the floor, and each mass contains 4 objects. The coordinates of item I are denoted by (ai,bi), and Yi can rotate it 90Β° counterclockwise around (xi, yi) each time, which will cost him one move. If the four points of a mass form a square with non-zero area, we say it is compact. Since Yi is lazy, he would like you to help him calculate the minimum number of moves needed to make each blob of clutter compact. Input description: In the first line, a number n(1 <= n <= 100) represents the number of blobs of clutter. The next 4n lines, each 4 lines represents a mess, each 4 numbers ai, bi, xi, yi, (-104 <= xi, yi, ai, bi <= 104), indicating the coordinates of the rotation of the ith object itself and the coordinates of the center point. Output description: N lines, one number for each line, indicating the minimum number of moves.
For the first mess, we can rotate the second or third item once.
Train of thought
Since there are four points in total, each point has only four states, so there are 16 states in total, which can be searched. As it is the minimum number of moves, breadth first search is used.
Note how one point is rotated 90 degrees clockwise around another point.
If we draw it on scratch paper, we can simply obtain the formula for rotating point A(x1, y1) 90 degrees counterclockwise about point B(x2, y2) :
X1 = x2 — y1 + y2; Y2 = x1 — x2 + Y2;
But at the same time, we can summarize the formula for rotation of A by any Angle around B, so that we don’t have to rederive it when we have similar problems.
Rotation of point A(x1, y1) clockwise about point B(x2, y2) ΞΈ degrees:
X = (x1 – x2) cos theta – (y1 – y2) sin theta + x2 y = (y1 – y2) cos theta +(x1 – x2) sin theta + y2
code
package tideTheRoom;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
private static class Point implements Cloneable {
long x;
long y;
long a;
long b;
int cnt;
public Point(long x, long y, long a, long b, int cnt) {
super();
this.x = x;
this.y = y;
this.a = a;
this.b = b;
this.cnt = cnt;
}
public void rotate() {
if (this.cnt == 3)
return;
long tx = a - y + b;
long ty = x - a + b;
this.x = tx;
this.y = ty;
this.cnt++;
}
@Override
public Point clone() {
Object o = null;
try {
o = super.clone();
} catch (CloneNotSupportedException e) {
}
return (Point) o;
}
}
private static boolean check(Point[] p) {
long[] dist = new long[6];
int cnt = 0;
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 4; j++) {
dist[cnt++] = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
}
}
Arrays.sort(dist);
if(dist[0] == dist[1] && dist[0] == dist[2] && dist[0] == dist[3] && dist[4] == dist[5] && ! (dist[0] == dist[4]))returntrue;
returnfalse;
}
private static int bfs(Point[] p) {
boolean[][][][] visited = new boolean[4][4][4][4];
LinkedList<Point[]> que = new LinkedList<>();
que.addLast(p);
visited[0][0][0][0] = true;
if (check(p))
return 0;
while(! que.isEmpty()) { Point[] f = que.pollFirst();for (int i = 0; i < 4; i++) {
Point[] tmp = new Point[4];
for (int j = 0; j < 4; j++) {
tmp[j] = f[j].clone();
}
tmp[i].rotate();
if (visited[tmp[0].cnt][tmp[1].cnt][tmp[2].cnt][tmp[3].cnt])
continue;
if (check(tmp)) {
return tmp[0].cnt + tmp[1].cnt + tmp[2].cnt + tmp[3].cnt;
}
que.addLast(tmp);
visited[tmp[0].cnt][tmp[1].cnt][tmp[2].cnt][tmp[3].cnt] = true; }}return- 1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();while((n--) ! = 0) { Point[] p = new Point[4];for(int i = 0; i < 4; i++) { long x = sc.nextLong(); long y = sc.nextLong(); long a = sc.nextLong(); long b = sc.nextLong(); p[i] = new Point(x, y, a, b, 0); } System.out.println(bfs(p)); } sc.close(); }}Copy the code
The second problem: Xiao Yi’s dictionary
Topic:
After learning the theory of strings in school, Yi completed a dictionary project based on it. Yi’s dictionary is very strange. Each word in the dictionary contains n ‘a’ and m ‘z’, and all words are arranged in lexicographical order. Now Yi wants you to help him figure out what the KTH word is. Input description: The input line consists of three integers n, m, k(1 <= n, m <= 100, 1 <= k <= 109), separated by Spaces. Output description: Output the KTH dictionary string, if there is no solution, output -1.
Enter Example 1:
2 2 6
Example 1:
zzaa
Example description:
The characters in the dictionary are aazz azaz azza zaaz zaza zzaa
Train of thought
The whole idea is dichotomy.
First, all of the total number of combinations for πΆ π π + π, starting from the highest level, the first character is a or z could be divided into two parts, the whole string if the first one is a, the entire string in the former πΆ π – 1 π + π – part 1, otherwise, the πΆ π – 1 π + π – 1 + 1 to πΆ π π + π part. So, to find the first k string, first determines the first character, if π < = πΆ π – 1 π + π – 1, shows the first character of a, in the former π > πΆ π – 1 π + π – part 1 lookup by π a and π z component of the first k a string, Namely in the π – 1 string search have π – 1 a and π z string, otherwise, the πΆ π – 1 π + π – 1 + 1 to πΆ π π + π part search, Namely in the π – a character string to find by a and π π – 1 z component first π – πΆ π – 1 π + π – a string, it is found the molecular problem. Follow this method until n or m is 0, indicating that the remaining characters are z or A.
Here to find the number of combinations need certain skills, specific reference to find the number of combinations
code
package dictionary; import java.util.Scanner; import static java.lang.Math.log; import java.math.BigInteger; import static java.lang.Math.exp; Public class Main {public static long comb(int m, int n, long target) {// Calculate the number of perpositions after aif (m == 0 || n == 0)
return1; long sum = m + n; long k = 1; n = Math.min(m, n); // C(m+n) n=C(m+nfor (int i = 0; i < n; i++) {
k *= sum - i;
k /= (i + 1);
if(k > target)// Prevent large numbers. If k>target, only list.add("a") and m--// the number of a minus 1. // No target -= k; So it doesn't affectbreak;
}
return k;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int tn = n, tm = m;
StringBuilder sb = new StringBuilder();
while (tn > 0 && tm > 0) {
long c = comb(tn - 1, tm, k);
// System.out.println(c);
if (k <= c) {
sb.append('a');
tn--;
} else {
sb.append('z'); k -= c; tm--; }}if(k ! = 1) System.out.println(-1);else {
while (tn > 0) {
sb.append('a');
tn--;
}
while (tm > 0) {
sb.append('z'); tm--; } System.out.println(sb.toString()); } sc.close(); }}Copy the code
Brushed some LeetCode problems
LeetCode 42 Trapping Rain Water LeetCode 407 Trapping Rain Water II
First, LeetCode 407 was scanned in 3d. Later, it was found that LeetCode 42 was two-dimensional
At the beginning of 407, the method of constantly cutting the bottom and traversing the area with a height of 0 after each cutting was used. It was found that although this problem could be solved, the time complexity was very high and the worst was
Since I spent a lot of time thinking and writing the above methods, I went to find the solution if I could think of other good methods.
In the process of finding the solution to the problem, I found a simplified version of the problem, which will inspire the solution of 407.
The title
LeetCode 42
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Represented by array [0,1,0,2,1, 1,3,2,1,2,1]. 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input,1,0,2,1,0,1,3,2,1,2,1: [0]
Output6:
The question
Give n columns as partitions and ask how much water can be stored between the columns
Train of thought
According to the barrel effect, how much water can be held is determined by the lowest of the tallest poles on either side.
I started by noting the tallest column to the left of location I and the tallest column to the right by using two arrays, maxHeightLeft and maxHeightRight, respectively. And then go from one to n minus two,
For example, in the example of maxHeightLeft[I], maxHeightLeft[I], maxHeightRight[I]) > height[I], ans += min(maxHeightLeft[I], maxHeightRight[I]) — height[I]
Time complexity is
code
import java.lang.Math;
public class Solution {
public int trap(int[] height) {
int len = height.length;
int[] maxHeightLeft = new int[len];
int[] maxHeightRight = new int[len];
for(int i = 1; i < len; i ++){
if(height[i - 1] > maxHeightLeft[i - 1])
maxHeightLeft[i] = height[i - 1];
else
maxHeightLeft[i] = maxHeightLeft[i - 1];
}
for(int i = len - 2; i >= 0; i --) {
if(height[i + 1] > maxHeightRight[i + 1])
maxHeightRight[i] = height[i + 1];
else
maxHeightRight[i] = maxHeightRight[i + 1];
}
int sum = 0;
for(int i = 1; i < len - 1; i ++){
int shortEdge = Math.min(maxHeightLeft[i], maxHeightRight[i]);
if(shortEdge > height[i])
sum += shortEdge - height[i];
}
returnsum; }}Copy the code
LeetCode 407 Trapping Rain Water II
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note: Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example: Given the following 3Γ6 height map: [[1,4,3,1,3,2], [2,3,3,2, 4]] Return 4
The above image represents the elevation map ,4,3,1,3,2 [[1], [3,2,1,3,2,4], [2,3,3,2,3,1]]before the rain.
After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
Priority queue (small top heap)
First, all the columns on the edge are grouped, and the whole matrix is surrounded by the centering elements as the outermost layer. The capacity of the secondary outer layer, if it can hold water, must be related to the height of the column in the immediate outer layer
Each time the element in the priority queue surrounding the matrix is extended from the smallest element in, and the height of the extended position updates the maximum height of the traversed outer position
code
import java.util.Comparator;
import java.util.PriorityQueue;
import static java.lang.Math.max;
public class Solution1 {
private final static int[][] steps = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
private class Point {
int x;
int y;
int height;
public Point(int x, int y, int height) {
super();
this.x = x;
this.y = y;
this.height = height;
}
}
private class Comparator1 implements Comparator<Point> {
@Override
public int compare(Point o1, Point o2) {
if (o1.height > o2.height)
return 1;
return- 1; } } public inttrapRainWater(int[][] heightMap) {
int ans = 0;
int lenx = heightMap.length;
if (lenx < 3)
return 0;
int leny = heightMap[0].length;
if (leny < 3)
return 0;
boolean[][] visited = new boolean[lenx][leny];
PriorityQueue<Point> que = new PriorityQueue<>(new Comparator1());
for (int i = 0; i < lenx; i++) {
que.add(new Point(i, 0, heightMap[i][0]));
visited[i][0] = true;
que.add(new Point(i, leny - 1, heightMap[i][leny - 1]));
visited[i][leny - 1] = true;
}
for (int i = 1; i < leny - 1; i++) {
que.add(new Point(0, i, heightMap[0][i]));
visited[0][i] = true;
que.add(new Point(lenx - 1, i, heightMap[lenx - 1][i]));
visited[lenx - 1][i] = true;
}
int maxHeight = -1;
while(! que.isEmpty()) { Point cur = que.poll(); maxHeight = max(maxHeight, cur.height);for (int i = 0; i < 4; i++) {
int nextX = cur.x + steps[i][0];
int nextY = cur.y + steps[i][1];
if(nextX >= 0 && nextX < lenx && nextY >= 0 && nextY < leny && ! visited[nextX][nextY]) { //System.out.println(nextX +"" + "" + nextY + "" + maxHeight + "" + heightMap[nextX][nextY]);
if (heightMap[nextX][nextY] < maxHeight) {
ans += maxHeight - heightMap[nextX][nextY];
}
visited[nextX][nextY] = true; que.add(new Point(nextX, nextY, heightMap[nextX][nextY])); }}}returnans; }}Copy the code
Leetcode 207 Course Schedule
The title
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.
Train of thought
Obviously topological sort, review, incidentally review a picture of the chain forward star representation
code
package leetcode_207_course_schedule; import java.util.HashSet; import java.util.Stack; public class Solution { private class Edge { int next; int to; public Edge(int next, int to) { super(); this.next = next; this.to = to; }}; int[] head; Edge[] edges; int cntE; public void add(int u, int v) { Edge e = new Edge(head[u], v); edges[++cntE] = e; head[u] = cntE; Public Boolean canFinish(int numCourses, int[][] prerequisites) {Stack<Integer> Stack = new Stack<>(); int len = prerequisites.length; HashSet<Integer>set = new HashSet<>();
int[] indegree = new int[numCourses];
head = new int[numCourses];
edges = new Edge[len + 1];
for (int i = 0; i < len; i++) {
indegree[prerequisites[i][1]]++;
add(prerequisites[i][0], prerequisites[i][1]);
}
for (int i = 0; i < numCourses; i++) {
set.add(i);
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0)
stack.add(i);
}
while(! stack.empty()) { int cur = stack.pop(); set.remove(cur);for(int i = head[cur]; i ! = 0; i = edges[i].next) { indegree[edges[i].to]--;if(indegree[edges[i].to] == 0) stack.push(edges[i].to); }}if (set.size() == 0)
returntrue;
elsereturnfalse; }}Copy the code
LeetCode 871 Minimum Number of Refueling Stops
Before the interview a Baidu question, roughly is: drive from the starting point to the end, there are a number of gas stations in the middle, the car’s oil tank capacity is infinite, to reach the end of the minimum number of refueling; If there is no way to reach the destination, output -1. I found a similar topic on the Internet, which is LeetCode 871.
The title
A car travels from a starting position to a destination which is target miles east of the starting position.
Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.
When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
Example 1:
Input: target = 1, startFuel = 1, stations = [] Output: 0 Explanation: We can reach the target without refueling.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]] Output: -1 Explanation: We canβt reach the target (or even the first gas station).
Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation: We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.
If you need to come on, if it can be anticipated before where a gas station arrive lack of oil, must be approved in the gas station before the biggest medium oil filling station of gas station is the most cost-effective (a gas and more), all with a pile of maintaining all stations, ensure the pile head element must be have been but no oil in the station and the amount of oil is most of the gas station. When there is a shortage of oil before a station, take the gas station from the pile head and increase the number of refueling by one; When all the gas stations that have passed by have finished picking up and filling up, but still cannot reach the next gas station, it means that the oil quantity of all the previous gas stations plus the initial oil quantity cannot support to reach the next gas station, return -1.
code
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Solution {
public class GasStation {
public int pos;
public int gas;
public GasStation(int pos, int gas) {
super();
this.pos = pos;
this.gas = gas;
}
}
class GasStationComparator1 implements Comparator<GasStation> {
@Override
public int compare(GasStation o1, GasStation o2) {
return o1.pos - o2.pos;
}
}
class GasStationComparator2 implements Comparator<GasStation> {
@Override
public int compare(GasStation o1, GasStation o2) {
return o2.gas - o1.gas;
}
}
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int num_GS = stations.length;
List<GasStation> list = new ArrayList<>();
for (int[] gs : stations) {
list.add(new GasStation(gs[0], gs[1]));
}
list.add(new GasStation(target, 0));
list.sort(new GasStationComparator1());
int gas = startFuel;
PriorityQueue<GasStation> heap = new PriorityQueue<>(new GasStationComparator2());
int cnt = 0;
for (int i = 0; i < num_GS + 1; i++) {
GasStation gs = list.get(i);
if (gs.pos > gas) {
while(gs.pos > gas && ! heap.isEmpty()) { //System.out.println(heap.peek().pos +"" + heap.peek().gas);
gas += heap.poll().gas;
cnt++;
}
if (gs.pos > gas && heap.isEmpty()) {
return- 1; } } heap.add(gs); }returncnt; }}Copy the code
conclusion
The above is my this period of time in the accumulation of some questions in the school, the recent cold is serious, temporarily update these. Friends refueling, there is no fight for the place also welcome everyone correction.
My essay in the nuggets technology, activities, please stamp π (15) autumn when recruiting job, with a gifts | the nuggets skill in writing essay
