У меня есть степень магистра компьютерных наук в университете в Пекине. Я всегда чувствую, что выпуск бакалавриата не так давно. Аспирант тоже закончит в мгновение ока. В июле я начал набирать школу. Итак, далеко, я накопил несколько вопросов для интервью и личное резюме обучения. Теперь поделитесь волной, я надеюсь, что это может помочь всем. скр~~😊
Письменные тестовые вопросы сегодняшнего заголовка.
Вопрос 1: Замена персонажа
тема
Строка S состоит из строчных букв и имеет длину n. Определите операцию, которая может каждый раз выбирать любые две соседние буквы в строке для замены. Спросите, сколько последовательных позиций в строке имеют одну и ту же букву после не более чем m перестановок? Введите описание:
Первая строка — это строка S и неотрицательное целое число m. (1
Описание выхода:
Неотрицательное целое число, указывающее операцию и количество непрерывных и самых длинных алфавитов.
Введите пример 1:
abcbaa 2
Пример вывода 1:
2
Пример Описание 1: Чтобы 2 буквы а появились подряд, требуется как минимум 3 операции. То есть переместите a с первой позиции на четвертую позицию. Таким образом, в случае не более чем 2 операций непрерывно может появляться не более 2 b или 2 a.
идеи
динамическое программирование.
Взяв в качестве примера символ a, пусть dp[i][j] обозначает количество перестановок, чтобы переместить все символы a вместе с i-го символа (включительно) на j-й символ (включительно), мы можем узнать стоимость перемещение всех символов в середину минимально. В то же время, предполагая, что все символы a от i + 1-го символа до j - 1-го символа были перемещены вместе, независимо от их позиций, просто переместите символы a на позиции i и j. Если вы забыли переместить посередине можно получить минимальное количество операций для объединения всех i-го символа (включительно) до i-го, причем количество операций на этом шаге должно быть индексом j-го символа минус i -th Нижний индекс символа а складывает и вычитает количество всех символов а между i + 1-м символом а и j - 1-м символом а.
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();
}
}
Вопрос 2: Кубик Рубика второго порядка
тема
Кубик Рубика второго порядка также называют Маленьким кубиком Рубика.2*2*2кубическая структура. Каждая сторона имеет 4 блока, всего 24 блока. Каждая операция может повернуть любую сторону на 90° против часовой стрелки или по часовой стрелке, например, повернуть верхнюю часть на 90° против часовой стрелки следующим образом.
Неро внес некоторые изменения в маленький куб, заменив цвет на каждом блоке числом, которое называется цифровым кубом. Грациозность каждой грани куба является произведением 4 чисел на этой грани, а общая грациозность куба является суммой грациозности 6 граней.
Теперь у Неро есть цифровой куб, и он хочет знать, какой максимальной грации может достичь куб, не выполняя его более 5 раз.
После того, как куб развернут, порядковый номер каждой части выглядит следующим образом:Введите описание: Введите строку, содержащую 24 числа, и укажите числа на каждой части куба в последовательном порядке. Все числа находятся в диапазоне [-100,100]. Введите описание: Выходная строка содержит число, представляющее максимальную изящность.
Первоначально я хотел использовать класс для абстрагирования каждой грани кубика Рубика, а затем имитировать вращение кубика Рубика, но это было слишком сложно, не только для хранения верхней, нижней, левой и правой каждой грани, но и абстрагировать каждую сетку каждой грани, потому что разные сетки Смежные сетки разные, и соседние сетки должны меняться при вращении.
Позже я проверил решение и нашел очень остроумный метод, использующий метод групп перестановок.
Каждый раз, когда вы поворачиваете, если метод вращения один и тот же, сетка в фиксированном положении будет заменена другим фиксированным положением.Вам нужно только выяснить метод вращения с группой перестановок.Всего 6 вращений методы, вертикальное вращение вверх и вниз, горизонтальное вращение влево и вправо, вращение и вертикальное вращение влево и вправо.
Есть игра толкания ящиков, и ситуация в начале такова:
На приведенном выше рисунке '.' означает достижимую позицию, '#' означает недоступную позицию, где S означает вашу начальную позицию, 0 означает начальную позицию коробки, E означает ожидаемую позицию коробки, вы можете дойти до коробки вверх, вниз, влево или вправо и сдвиньте коробку на другую сторону. Сдвиньте коробку вправо на один квадрат, как показано на рисунке ниже;
..S0.. -> …S0.
Обратите внимание, что вы не можете подтолкнуть поле к '#', и вы не можете вытолкнуть поле за границу;
Теперь, чтобы дать вам первоначальный вид игры, вам нужно вывести минимальное количество ходов, чтобы завершить игру, или -1, если нет. введите описание: Первая строка содержит 2 числа, n, m, указывающие на то, что размер игрового поля состоит из n строк и m столбцов (5
выходное описание: Число, обозначающее минимальное количество шагов для прохождения игры, если нет, выведите -1;
Введите пример 1:
3 6
.S#..E
.#.0.. ...
Пример вывода 1:
11
идеи
Простой четырехмерный BFS, обратите внимание на поле при записи местоположения и положения человека
код
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;
}
else if(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] == '#') && !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] == '#')){
Status news = new Status(nextx, nexty, nextbx, nextby, st + 1);
queue.addLast(news);
visited[nextx][nexty][nextbx][nextby] = true;
if(map[nextbx][nextby] == 'E') {
return st + 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();
}
}
Вопрос 4: Распределение номеров
тема
Есть n комнат, и теперь нужно переназначить людей в комнате I. Правило распределения следующее: сначала выпустить всех людей в комнате i, затем следуют i+1, i+2, i+3, . .. расположите людей в этих комнатах по порядку, при этом комната n будет следующей комнатой в комнате 1, пока все люди не будут переназначены.
Теперь скажите вам количество людей в каждой комнате после распределения и номер комнаты x последнего выделенного человека, вам нужно найти количество людей в каждой комнате до распределения. Данные гарантируют, что решение должно быть, и если решений несколько, будет выведено любое решение. Введите описание: Первая строка из двух целых чисел n, x (2
Описание выхода: Выведите n целых чисел, представляющих количество человек до того, как будет выделена каждая комната.
Введите пример 1:
3 1
6 5 1
Пример вывода 1:
4 4 4
идеи
Знайте номер комнаты x последнего назначенного человека, найдите количество людей в исходной комнате последнего назначенного лица num, установите исходный номер комнаты последнего назначенного лица как startx,
но(x + n) % – startx = num % n
Исходная комната должна быть одной из наименее заполненных комнат, потому что ее население было установлено равным 0 перед последним назначением, а после завершения назначения ее население должно быть num/n.
Но комната с наименьшим количеством людей не обязательно будет единственной, потому что до последнего распределения могут быть другие комнаты с 0 людьми. Также необходимо определить, превышает ли количество людей во всех комнатах между текущей локацией и startx минимальное значение.
код
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();
}
}
Вопрос 5: Классики
тема
Есть n + 1 комнат, каждая комната это комната 1 2 3...i, в каждой комнате есть портал, портал в комнате i может отправить людей в комнату pi (1A. Если текущую комнату i посетили четное количество раз, в следующий раз перейти в комнату i+1; B. Если текущую комнату i посетили нечетное количество раз, то перейти в комнату pi; Теперь прохожий А хочет знать, сколько ходов потребуется, чтобы перебраться в комнату n+1; введите описание: В первой строке записано число n (30 % данных 1
выходное описание: Выведите строку чисел, указывающую количество последних ходов, и окончательный результат должен быть по модулю 1000000007 (10e9 + 7).
Введите пример 1:
2
1 2
Пример вывода 1:
4
Пример Описание 1:
Сначала зайдите из комнаты 1 только один раз, поэтому вы можете прыгнуть только в p1, то есть в комнату 1, а затем используйте стратегию A, чтобы перейти в комнату 2, комната 2 посещается один раз в это время, поэтому используйте стратегию B, чтобы прыгнуть в комнату. 2, а затем используйте стратегию A, чтобы прыгнуть в комнату 3, так что потребуется 4 шага, чтобы добраться до комнаты 3.
Идеи:
Обратите внимание, что pi (1
Это условие гарантирует, что в оптимальном решении могут быть использованы подконструкции
Пусть dp[i] обозначает шаги, предпринятые для достижения комнаты i во второй раз. Сначала рассмотрим достижение i-й комнаты в первый раз, тогда она должна пройти через комнату i – 1 дважды, то есть число шагов равно dp[i – 1] + 1;
В то же время, поскольку это первый раз, когда мы достигаем комнаты i, она перейдет к pi следующей, и количество шагов в это время обновится до dp[i – 1] + 2. Чтобы снова попасть в комнату i, вы должны пройти через комнату i – 1 еще два раза. В это время состояние первой i – 1 комнаты таково:
За исключением пи-й комнаты, которая прошла нечетное количество раз, все остальные комнаты имеют четные номера, что согласуется с состоянием, когда пи-я комната впервые достигнута. А количество шагов, пройденных при первом достижении pi, равно dp[pi – 1] + 1;
В этот момент, чтобы снова попасть в i-ю комнату, нужно снова дважды пройти i – 1. Количество шагов, необходимых для перехода из этого состояния в состояние i – 1 дважды, равно количеству шагов, необходимых для перейти из начального состояния во второй раз, чтобы добраться до комнаты i – 1. Количество шагов, необходимых для состояния в 1 минус количество шагов, необходимых для перехода из начального состояния в состояние первой достигающей комнаты pi, т. е. dp [i – 1] – (dp[pi – 1] + 1), а затем сделайте один шаг, второй раз, чтобы добраться до комнаты i.
Подводя итог, можно сказать, что уравнение перехода состояния для количества шагов, необходимых для достижения комнаты i во второй раз, выглядит следующим образом:
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();
}
}
Вопросы по программированию в школе Netease
Вопрос 1: Прибраться в комнате
тема
Снова выходные, и в комнате Сяои беспорядок.
Он надеется немного разобрать беспорядок на земле, чтобы каждый комок беспорядка выглядел более компактным и менее беспорядочным.
На земле лежат n комочков, в каждом из которых по 4 предмета. Координаты i-го предмета представлены (ai, bi), и Сяо И может каждый раз поворачивать его на 90° против часовой стрелки вокруг (xi, yi), что потребует одного из его ходов. Если 4 точки капли образуют квадрат с ненулевой площадью, мы говорим, что она компактна.
Поскольку Сяойи ленив, он хочет, чтобы вы помогли ему рассчитать минимальное количество ходов, необходимых для каждого комка, чтобы сделать его компактным. Введите описание: Первая строка содержит число n (1
Описание выхода: n строк, по 1 числу в каждой строке, указывающее минимальное количество ходов.
Для первого комка мы можем повернуть второй или третий элемент 1 раз.
идеи
Так как всего четыре точки, каждая точка имеет только четыре состояния, поэтому всего 16 состояний, просто выполните поиск. Так как это наименьшее количество ходов, используется поиск в ширину.
Следует отметить, как рассчитывается, что одна точка поворачивается на 90 градусов по часовой стрелке вокруг другой точки.
Давайте нарисуем это на бумаге для заметок, мы можем просто получить формулу для точки A(x1, y1), чтобы повернуться на 90 градусов против часовой стрелки вокруг точки B(x2, y2):
Х1 = х2 – у1 + у2; Y2 = x1 – x2 + y2;
Но в то же время мы также можем обобщить формулу поворота A вокруг B на любой угол, что может предотвратить повторный вывод при столкновении с аналогичными проблемами.
Поверните точку A(x1, y1) по часовой стрелке вокруг точки B(x2, y2) на θ градусов:
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]))
return true;
return false;
}
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();
}
}
Вопрос 2: Словарь Сяои
тема:
Сяойи узнал о теории струн в школе, поэтому он завершил проект словаря, основанный на ней.
Словарь Сяои очень своеобразен.Каждое слово в словаре содержит n 'a' и m 'z', и все слова расположены в лексикографическом порядке.
Теперь Сяойи надеется, что вы поможете ему узнать, что такое k-е слово. Введите описание: Ввод включает в себя строку из трех целых чисел N, M, K (1 Описание выхода: Выведите строку из k-го словаря, если решения нет, выведите -1.
Пример ввода 1:
2 2 6
Пример вывода 1:
zzaa
Пример описания:
Строки в словаре в порядке aazz azaz azza zaaz zaza zzaa
идеи
Это дихотомическая идея в целом.
Во-первых, общее количество всех комбинаций равно 𝐶𝑛𝑚+𝑛, начиная со старшего бита, независимо от того, является ли первый символ a или z, вся строка делится на две части, если первым является a, вся строка находится перед 𝐶𝑛 — 1𝑚+𝑛−1 часть, иначе от 𝐶𝑛−1𝑚+𝑛−1+1 до 𝐶𝑛𝑚+𝑛 части. Итак, чтобы найти k-ю строку, сначала оцените первый символ, если 𝑘𝐶𝑛−1𝑚+𝑛−1 Найдите k- строка, состоящая из 𝑛 a и 𝑚 z, то есть найти строку, состоящую из 𝑛–1 a и 𝑚 z в последних 𝑛–1 строках, иначе в 𝐶𝑛−1𝑚+ Частичный поиск от 𝑛−1+1 до 𝐶𝑛𝑚 +𝑛, то есть найти 𝑘–𝐶𝑛−1𝑚+𝑛−1-ю строку, состоящую из 𝑛 a и 𝑚–1 z в строке, состоящей из последней строки из 𝑛–1 символов, которая находит способ разделить подзадачи. Следуйте этому методу для пошагового поиска в обратном направлении до тех пор, пока n или m не станет равным 0, что указывает на то, что оставшиеся символы — это z или a.
Здесь для нахождения количества комбинаций требуются определенные навыки, конкретная справкаНайдите количество комбинаций
код
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) {// 计算假设a确定之后，a之后的部分排列组合数
if (m == 0 || n == 0)
return 1;
long sum = m + n;
long k = 1;
n = Math.min(m, n);// C(m+n) n=C(m+n) m 取最小即可
for (int i = 0; i < n; i++) {
k *= sum - i;
k /= (i + 1);
if (k > target)// 防止大数。如果k>target 则只进行list.add("a")和m--//a的个数减1。
// 没有target -= k;因此不影响
break;
}
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();
}
}
Почистил некоторые вопросы LeetCode
Вопрос 1: LeetCode 42 Улавливание дождевой воды и LeetCode 407 Улавливание дождевой воды II
Первый обработанный LeetCode 407 представляет собой трехмерную ситуацию, а позже я обнаружил, что LeetCode 42 представляет собой двухмерную ситуацию.
При выполнении 407 в начале я использовал метод непрерывного подрезания дна и обхода после каждого подрезания области с высотой 0. Я обнаружил, что хотя эту проблему можно решить, временная сложность очень высока, а самое худшее —
, что приводит к отсутствию переменного тока
Так как я потратил много времени в процессе обдумывания и написания вышеперечисленных методов, если я думал о других хороших методах, я переходил к решению следующей задачи.
В процессе поиска решения я нашел упрощенную версию проблемы, которая вдохновит на решение 407.
тема
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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
смысл названия
Учитывая n столбцов в качестве разделителей, спросите, сколько воды можно хранить не более чем между столбцами.
идеи
Согласно эффекту бочки, сколько воды может удержаться, определяется самой короткой из самых высоких колонн слева и справа.
Сначала я использовал два массива maxHeightLeft и maxHeightRight для записи самого высокого бара слева от позиции i и самого высокого бара справа соответственно. Затем пройти от 1 до n - 2,
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];
}
return sum;
}
}
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],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
The above image represents the elevation map[[1,4,3,1,3,2],[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.
идеи Использовать приоритетную очередь (маленькая верхняя куча)
Во-первых, все столбцы на краю ставятся в очередь, а центральный элемент окружает всю матрицу как самый внешний слой. Если место во втором внешнем слое может удерживать воду, его вместимость должна быть связана с высотой столба в ближайшем к нему положении внешнего слоя.
Таким образом, каждый раз, когда элементы в очереди приоритетов, окружающей матрицу, расширяются от наименьшего элемента внутрь, а высота расширенной позиции используется для обновления самой высокой высоты пройденной внешней позиции.
код
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 int trapRainWater(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]));
}
}
}
return ans;
}
}
Вопрос 2: Расписание курсов Leetcode 207
тема
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.
идеи
Очевидная топологическая сортировка, просмотрите ее, кстати, просмотрите цепочное прямое звездообразное представление графа
код
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)
return true;
else
return false;
}
}
Вопрос 3: Минимальное количество заправок по LeetCode 871
Ранее я отвечал на вопрос Baidu, который примерно таков: «Движение из начальной точки в конечную, посередине есть несколько заправок, а емкость топливного бака автомобиля не ограничена. Найдите минимальное количество заправок». добраться до конечной точки; если нет возможности добраться до конечной точки, выведите -1. Нашел похожую тему в интернете, это LeetCode 871.
тема
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:Мы не можем добраться до цели (или даже до первой заправки).
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.
Note:
1 <= target, startFuel, stations[i][1] <= 10^9 0
идеи
Если вам нужно заправиться, если вы можете предсказать, на какой заправке закончится бензин до его прибытия, это должна быть заправка с наибольшим количеством газа среди заправок, прошедших до заправки. прохождение заправочных станций, следя за тем, чтобы оголовком сваи была заправочная станция с наибольшим количеством пройденного, но не заправленного топлива на этой заправке. Когда перед какой-то заправкой будет нехватка топлива, заправка берется из оголовка сваи, а количество заправок увеличивается на единицу, когда все пройденные заправки взяты и газ заправлен , до следующей заправки по-прежнему невозможно добраться. Это означает, что объем топлива всех предыдущих заправок плюс начальный объем топлива не могут обеспечить достижение следующей заправки, возврат -1.
код
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);
}
return cnt;
}
}
Эпилог
Выше приведены некоторые из вопросов, которые у меня накопились в процессе набора в школу.Недавно у меня была серьезная простуда, поэтому я обновлю их на данный момент. Ну же, друзья мои, если есть что-то, к чему вы не стремитесь, можете меня поправить.