Персональный технический блог: www.zhenganwen.top
Следующие темы отсортированы в соответствии с онлайн-программированием Niuke.com, и все примеры кода прошли проверку Niuke.com OJ.
Найдите двумерный массив
Описание темы
В двумерном массиве (каждый одномерный массив имеет одинаковую длину) каждая строка сортируется в порядке возрастания слева направо, а каждый столбец сортируется в порядке возрастания сверху вниз. Пожалуйста, завершите функцию, введите такой двумерный массив и целое число и определите, содержит ли массив целое число.
public boolean Find(int target, int [][] arr) {
}
Разобрать
Метод грубой силы состоит в том, чтобы пройти по двумерному массиву и найтиtargetпросто вернисьtrue, временная сложностьO(M * N)(Для M строки N столбцов).
Из вопроса, который можно увидеть, что образцы входных данных имеют высокую степень регулярности (данные в единой строке заказываются, и данные в одном столбце также заказываются), поэтому подумайте о том, есть ли сравнительный тариф на Сравнение на основе упорядоченного устранения числа, которые не должны проходить для сравнения.аккуратный,найти, нетрудно придумать бинарный поиск, мы можем учиться на идее бинарного поиска, каждый раз выбирать число в качестве эталона сравнения, а затем исключать некоторые числа, которые не нужно сравнивать. Разделить - это выбрать медиану массива в качестве эталона сравнения, чтобы гарантировать, что каждый раз будет исключаться половина числа. Есть ли число с этой характеристикой в этом вопросе? Давайте рассмотрим пример:
Нетрудно обнаружить, что число по диагонали на приведенном выше рисунке является медианой последовательности, образованной его строкой и столбцом.Мы могли бы также выбрать число в правом верхнем углу в качестве эталона сравнения.Если это не так равно, то мы можем исключить все левые единицы числа или все его числа ниже, например дляtarget = 6,так как(0,3)На месте4 < 6,следовательно(0,3)Все числа слева от позиции и той же строки меньше 6, поэтому их можно исключить напрямую.После исключения проблема состоит в том, чтобы найти оставшиеся три строки.target, что похоже на исходную задачу, то есть каждый раз, когда данные в правом верхнем углу выбираются в качестве эталона сравнения, а затем удаляется строка или столбец до тех пор, пока число, выбранное в определенном раунде, не будетtargetЛибо результат можно получить, когда останется только одно число, поэтому временная сложность равна сумме количества удаляемых строк и столбцов, т. е.O(M + N), после анализа не сложно написать следующий код:
public boolean Find(int target, int [][] arr) {
//input check
if(arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0){
return false;
}
int i = 0, j = arr[0].length - 1;
while(i != arr.length - 1 && j != 0){
if(target > arr[i][j]){
i++;
}else if(target < arr[i][j]){
j--;
}else{
return true;
}
}
return target == arr[i][j];
}
Стоит отметить, что число, выбираемое каждый раз, является последним числом в первой строке, поэтому посылка состоит в том, что в первой строке есть число, тогда оно соответствует проверке ввода.arr[0] == null || arr[0].length == 0, который легче игнорировать.
Резюме: После анализа нетрудно обнаружить, что эта задача представляет собой вариант использования элементов бинарного поиска в одномерном упорядоченном массиве.Мы должны в полной мере использовать регулярность самих данных для поиска идей решения проблемы.
заменить пробелы
Описание темы
Пожалуйста, реализуйте функцию, которая заменяет каждый пробел в строке на "%20". Например, если строка We Are Happy., замененная строка будет We%20Are%20Happy.
public String replaceSpace(StringBuffer str) {
}
В этом вопросе рассматриваются связанные операции реализации массива (соответствующей реализации связанного списка) строковой структуры данных.
Разобрать
String.replace простой и грубый
если вы можете использоватьAPI, то вы можете легко написать следующий код:
public String replaceSpace(StringBuffer str) {
//input check
//null pointer
if(str == null){
return null;
}
//empty str or not exist blank
if(str.length() == 0 || str.indexOf(" ") == -1){
return str.toString();
}
for(int i = 0 ; i < str.length() ; i++){
if(str.charAt(i) == ' '){
str.replace(i, i + 1, "%20");
}
}
return str.toString();
}
Время O(n), пространство O(n)
Но если интервьюер говорит нам не использовать инкапсулированную функцию замены, то цель состоит в том, чтобы проверить наше понимание строкиреализация массиваоперации, связанные с методом. Так как это непрерывное хранилище пространства, вам необходимо указать размер при создании экземпляра, так как каждое пространство используется%20Заменить, поэтому замененная строка должна быть больше, чем исходная строка.空格数 * 2длина, реализованная следующим образом:
public String replaceSpace(StringBuffer str) {
//input check
//null pointer
if(str == null){
return null;
}
//empty str or not exist blank
if(str.length() == 0 || str.indexOf(" ") == -1){
return str.toString();
}
char[] source = str.toString().toCharArray();
int blankCount = 0;
for(int i = 0 ; i < source.length ; i++){
blankCount = (source[i] == ' ') ? blankCount + 1 : blankCount;
}
char[] dest = new char[source.length + blankCount * 2];
for(int i = source.length - 1, j = dest.length - 1 ; i >=0 && j >=0 ; i--, j--){
if(source[i] == ' '){
dest[j--] = '0';
dest[j--] = '2';
dest[j] = '%';
continue;
}else{
dest[j] = source[i];
}
}
return new String(dest);
}
Время O(n), пространство O(1)
Если нет дополнительного пробела, то нам нужно подумать, как повторно использовать входную строку.Если мы встретим пробелы спереди назад, замените пробелы и две позиции после них на%20, который обязательно перезапишет два символа после пробела, например.hello worldбудет заменен наhello%20rld, поэтому нам нужно определить символы в каждом индексе от конца к началу в новой строке, длина которой была увеличена. Например, используяoriginalIndexЧтобы указать на последний индекс символа в исходной строке, используйтеnewIndexуказывает на последний индекс новой строки каждый раз, когдаoriginalIndexскопируйте символы наnewIndexвверх и оба указателя продвигаются вперед, еслиoriginalIndexсимвол выше пробел, это будетnewIndexзаполнить по порядку0,2,%, затем оба продвигаются вперед, пока оба не достигнут первой индексной позиции.
public String replaceSpace(StringBuffer str) {
//input check
//null pointer
if(str == null){
return null;
}
//empty str or not exist blank
if(str.length() == 0 || str.indexOf(" ") == -1){
return str.toString();
}
int blankCount = 0;
for(int i = 0 ; i < str.length() ; i++){
blankCount = (str.charAt(i) == ' ') ? blankCount + 1 : blankCount;
}
int originalIndex = str.length() - 1, newIndex = str.length() - 1 + blankCount * 2;
str.setLength(newIndex + 1); //需要重新设置一下字符串的长度，否则会报越界错误
while(originalIndex >= 0 && newIndex >= 0){
if(str.charAt(originalIndex) == ' '){
str.setCharAt(newIndex--, '0');
str.setCharAt(newIndex--, '2');
str.setCharAt(newIndex, '%');
}else{
str.setCharAt(newIndex, str.charAt(originalIndex));
}
originalIndex--;
newIndex--;
}
return str.toString();
}
Резюме: сделать открытый разум для работы массива до нашего привычного
for(int i = 0 ; i < arr.length ; i++)Манипулируйте массивом от начала до конца в виде , но не игнорируйте уникальность перехода от конца к началу.
обратно связанный список
Описание темы
Введите связанный список, после обращения связанного списка выведите заголовок нового связанного списка.
public ListNode ReverseList(ListNode head) {
}
Разобрать
Сложность этой задачи в том, что невозможно получить его узел-предшественник через узел односвязного списка, поэтому нам нужно не только сохранить узел-предшественник текущего узла перед обращением указателя, но и сохранить узел-преемник текущего узла. node, и в следующий раз обновите оба указателя перед реверсированием.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode pre = null, p = head, next;
while(p != null){
next = p.next;
p.next = pre;
pre = p;
p = next;
}
return pre;
}
Перечислите печатающую головку из хвоста
Описание темы
Введите связанный список, верните ArrayList в порядке значений связанного списка от конца до конца.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
}
Разобрать
Сложность этой проблемы заключается в том, что односвязный список имеет только указатель на последующий узел, поэтому мы не можем получить узел-предшественник через текущий узел, поэтому не пытайтесь сначала пройти по связанному списку, чтобы найти хвостовой узел. а затем печатать сзади наперед.
Рекурсивный, лаконичный и элегантный
Поскольку мы обычно проходим по связанному списку от начала до конца, а заголовок требует, чтобы узлы печатались от конца к началу, что согласуется с логикой перемотки вперед и назад, для сохранения узлов можно использовать стек. пройденный во время обхода, а затем пройти Функция «последний вошел первым вышел» реализует печать узлов от конца к началу, но мы также можем использовать рекурсию, чтобы помочь нам протолкнуть стек.Поскольку рекурсия проста и легко сделать ошибки, рекурсия можно максимально использовать в интервью: пока текущий узел не пуст, затем рекурсивно пройти узел-преемник, когда узел-преемник пуст, рекурсия заканчивается, и «текущий узел» добавляется в набор в свою очередь во время рекурсивного возврата
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList();
//input check
if(listNode == null){
return res;
}
recursively(res, listNode);
return res;
}
public void recursively(ArrayList<Integer> res, ListNode node){
//base case
if(node == null){
return;
}
//node not null
recursively(res, node.next);
res.add(node.val);
return;
}
}
обратно связанный список
Другой способ — перевернуть указатель связанного списка, что и является результатом. Следует отметить, что мы не должны изменять структуру хранимых данных при доступе к пользовательским данным, поэтому я, наконец, не забываю об обратном:
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList();
//input check
if(listNode == null){
return res;
}
return unrecursively(listNode);
}
public ArrayList<Integer> unrecursively(ListNode node){
ArrayList<Integer> res = new ArrayList<Integer>();
ListNode newHead = reverse(node);
ListNode p = newHead;
while(p != null){
res.add(p.val);
p = p.next;
}
reverse(newHead);
return res;
}
public ListNode reverse(ListNode node){
ListNode pre = null, cur = node, next;
while(cur != null){
//save predecessor
next = cur.next;
//reverse pointer
cur.next = pre;
//move to next
pre = cur;
cur = next;
}
//cur is null
return pre;
}
Резюме: Интервью может быть рекурсивным, когда использовать рекурсию, конечно, если интервьюер - проверить указатель своих навыков, который вы можете
just so soнет
Восстановить бинарное дерево
Описание темы
Введите результаты обхода в прямом и обратном порядке двоичного дерева и восстановите двоичное дерево. Предполагается, что результаты входного обхода в прямом и обратном порядке не содержат повторяющихся чисел. Например, введите последовательность обхода в прямом порядке {1,2,4,7,3,5,6,8} и последовательность обхода в неупорядоченном порядке {4,2,7,1,5,3,8,6}, затем перестройте бинарное дерево и возврат.
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
}
Разобрать
Последовательность предварительной заставки характеризуется тем, что первое число является корневым узлом, за которым следует последовательность предварительного заказа левого поддерева и последовательность предварительного заказа правого поддерева, в то время как последовательность внешнего порядка характеризуется неправильной последовательностью левого поддерева, а также. Затем предварительная последовательность левого поддерева. Корневой узел и, наконец, последовательность внешнего порядка правого поддерева. Следовательно, мы можем получить корневой узел через последовательность предварительного заказа, а затем получить количество узлов в левом поддеревере и правом поддереве, глядя вверх по индексу корневого узла в последовательности Inforder. Затем две последовательности могут быть разделены на три части, а корневой узел может быть непосредственно реконструирован, а затем левый поддерева и правый поддельный узел из корневого узла может быть рекурсивно рекурсивно рекурсифицирован в соответствии с соответствующими подпоследовательностью. Это типичный пошаговый процесс деления сложной задачи в подпроставления.
Определение рекурсивного тела, как показано на рисунке выше, представляет собой последовательность левого поддерева последовательности предварительного порядка.2,3,4соответствующий индекс1,2,3, а последовательность левого поддерева неупорядоченной последовательности равна3,2,4соответствующий индекс0,1,2, поэтому параметры, полученные рекурсивным телом, должны указывать диапазоны индексов подпоследовательностей, которые необходимо рекурсивно реконструировать в двух массивах в дополнение к массивам, содержащим две последовательности:TreeNode rebuild(int[] pre, int i, int j, int[] in, int m, int n). Тогда рекурсивное тело основано наpreизi~jПоследовательность предварительного заказа, образованная диапазоном индексов иinизm~nНеупорядоченная последовательность, сформированная диапазоном индексов, перестраивает дерево и возвращает корневой узел.
Во-первых, корневой узел — это первый номер последовательности предварительного заказа, т. е.pre[i],следовательноTreeNode root = new TreeNode(pre[i])можно определить непосредственно, тоinизm~nвыяснитьpre[i]индекс чего-либоindexКоличество узлов в левом поддереве можно найтиleftNodes = index - m, количество узлов в правом поддеревеrightNodes = n - index, если количество узлов в левом (правом) поддереве равно 0, это означает, что левое (правое) поддеревоnull, иначе пройтиroot.left = rebuild(pre, i' ,j' ,in ,m' ,n')Перестроить левое (правое) поддерево можно.
Вот в чем трудность этого вопроса, т.i',j',m',n'Определение стоимостиleftNodes,rightNodesиi,j,m,nЧтобы быть уверенным: (В настоящее время не думайте о соответствии между этими нижними индексами в уме!! Обязательно нарисуйте на бумаге, чтобы обеспечить точность и общность)
Таким образом, легко получить следующий код:
if(leftNodes == 0){
root.left = null;
}else{
root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1);
}
if(rightNodes == 0){
root.right = null;
}else{
root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n);
}
Однажды автор использовал индекс корневого узла упорядоченной последовательности, чтобы определитьi',j',m',n'Напишите следующую корреспонденцию междукод ошибки:
if(leftNodes == 0){
root.left = null;
}else{
root.left = rebuild(pre, i + 1, index, in, m, index - 1);
}
if(rightNodes == 0){
root.right = null;
}else{
root.right = rebuild(pre, index + 1, j, in, index + 1, n);
}
Это соответствие на первый взгляд выглядит правильным, но не является общим (т.е. охватывает все случаи), например, для последовательностей2,3,4,3,2,4При перестроении:
Посмотрите на эту ситуацию, все еще актуален приведенный выше код ошибки? Причина в том, чтоindexвinизm~nВыбирается, и массивinсвязан, иpreПрямой связи нет, поэтому, если вы используетеindexПредставлятьi',j'Естественно это неразумно.
Правильный полный код для этого вопроса выглядит следующим образом:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length){
return null;
}
return rebuild(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
public TreeNode rebuild(int[] pre, int i, int j, int[] in, int m, int n){
int rootVal = pre[i], index = findIndex(rootVal, in, m, n);
if(index < 0){
return null;
}
int leftNodes = index - m, rightNodes = n - index;
TreeNode root = new TreeNode(rootVal);
if(leftNodes == 0){
root.left = null;
}else{
root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1);
}
if(rightNodes == 0){
root.right = null;
}else{
root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n);
}
return root;
}
public int findIndex(int target, int arr[], int from, int to){
for(int i = from ; i <= to ; i++){
if(arr[i] == target){
return i;
}
}
return -1;
}
}
Суммировать:
- Для сложных проблем он должен быть разделен на несколько подпроставок и решен один за другим. Например, двоичная проблема дерева, мы обычно разделяем ее в головной узел, левый поддерева и правый поддерева.
- Для рекурсивных параметров переменных процесса соответствующие отношения, а не напрямую связанные с образцом данных, чтобы использовать свои собственные для представления. Таким образом, вопрос должен быть выбран, чем
leftNodesиrightNodesвычислятьi',j',m',n'не следует использовать нижний индекс головного узла в упорядоченной последовательностиindex(это иinсвязано, то это может быть правдойpreНе применять).
Реализация очереди с двумя стеками
Описание темы
Используйте два стека для реализации очереди для выполнения операций Push и Pop в очереди. Элементы в очереди имеют тип int.
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
}
public int pop() {
}
Разобрать
Просто запомните следующие моменты для этого вопроса:
- стек (напр.
stack1) Может использоваться только для сохранения другого стека (например,stack2) можно использовать только для извлечения - При извлечении элемента сначала проверьте
stack2Пусто ли оно, если не пусто напрямуюstack2.pop(), иначеstack1элементы ввылить всеstack2, если после заливкиstack2Еще пусто, надо выкинуть, иначеstack2.pop().
Пример кода выглядит следующим образом:
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
if(stack2.empty()){
throw new IllegalStateException("no more element！");
}
return stack2.pop();
}
}
Резюме: Пока стек для выборки элементов не пуст, верхний элемент стека может быть извлечен непосредственно при выборке элементов.Только когда он пуст, рассмотрите возможность залить в него стек для хранения элементов, и он должен быть завершен в один раз.
Минимальное число для вращения массива
Описание темы
поставить начало массиванемногоПеремещение элементов в конец массива, мы называем это вращением массива. введитесортировка по неубываниюПоворот массива , выводящий наименьший элемент повернутого массива. Например, массив {3,4,5,1,2} представляет собой поворот {1,2,3,4,5}, а минимальное значение массива равно 1. ПРИМЕЧАНИЕ. Все указанные элементы больше 0, если размер массива равен 0, верните 0.
public int minNumberInRotateArray(int [] arr) {
}
Разобрать
Этот вопрос должен быть тщательно рассмотрен в первую очередь:
- Несколько, охватывающих случай, когда один элемент не перемещается.В это время массив представляет собой неубывающую отсортированную последовательность, поэтому первый элемент является наименьшим элементом массива.
- Неубывающий порядок, не означает возрастающий, может встречаться несколько соседних элементов одной и той же ситуации, крайний пример - все элементы такие же, как и весь массив
Отсюда нетрудно вывести следующееinput check:
public int minNumberInRotateArray(int [] arr) {
//input check
if(arr == null || arr.length == 0){
return 0;
}
//if only one element or no rotate
if(arr.length == 1 || arr[0] < arr[arr.length - 1]){
return arr[0];
}
//TODO
}
вышеупомянутыйarr[0] < arr[arr.length - 1]нельзя записать какarr[0] <= arr[arr.length - 1], например, может быть[1,2,3,3,4] -> [3,4,1,2,3]случае, когда вы не можете вернутьсяarr[0]=3.
Если вы пришли на программуTODO, можно рассмотреть общую ситуацию, массив можно разделить на две части: больше или равноarr[0]Левая половина суммы меньше или равнаarr[arr.length - 1]В правой половине мы можем использовать два указателя для приближения к середине из головы и хвоста массива, чтобы мы могли использовать идею дихотомии для быстрого перемещения указателя и исключения некоторых чисел, которые не учитываются.
Как показано на рисунке, мы не можем напрямую передатьarr[mid]иarr[l](илиarr[r])Сравнение(arr[mid] >= arr[l]) решить ходlвсе ещеrприбытьmidВкл, т.к. в массиве может быть несколько одинаковых и смежных чисел, нам также необходимо добавить ограничение:arr[l + 1] >= arr[l] && arr[mid] >= arr[l](заrс точки зренияarr[r - 1] <= arr[r] && arr[mid] <= arr[r]), то есть когда в левой половине (правой половине) более одного числа, мы можем двигатьсяl(r)указатель. Полный код выглядит следующим образом:
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] arr) {
//input check
if(arr == null || arr.length == 0){
return 0;
}
//if only one element or no rotate
if(arr.length == 1 || arr[0] < arr[arr.length - 1]){
return arr[0];
}
//has rotate, left part is big than right part
int l = 0, r = arr.length - 1, mid;
//l~r has more than 3 elements
while(r > l && r - l != 1){
//r-l >= 2 -> mid > l
mid = l + ((r - l) >> 1);
if(arr[l + 1] >= arr[l] && arr[mid] >= arr[l]){
l = mid;
}else{
r = mid;
}
}
return arr[r];
}
}
Резюме: при рассмотрении вопросов следует полностью учитывать экстремальные условия образцов данных, чтобы писать надежный код.
Последовательность Фибоначчи
Описание темы
Все знают последовательность Фибоначчи.Теперь вас просят ввести целое число n.Выведите n-й элемент последовательности Фибоначчи (начиная с 0, и 0-й элемент равен 0). n
public int Fibonacci(int n) {
}
Разобрать
рекурсивный путь
для формулыf(n) = f(n-1) + f(n-2), очевидно, является рекурсивным вызовом, поэтому согласноf(0) = 0иf(1) = 1Мы можем легко написать следующий код:
public int Fibonacci(int n) {
if(n == 0 || n == 1){
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
динамическое программирование
В приведенном выше рекурсивном процессе вы обнаружите, что многие вычислительные процессы повторяются:
Динамическое программирование обнаружило, что существует множество подпроцессов с повторными расчетами во время процесса преобразования сверху вниз с использованием рекурсивных вызовов, поэтому каждое подкрепление кэшируется снизу вверх, чтобы только результаты подпроцессов необходимы для Верхний слой - это рассчитывается только один раз, когда он не находится в кэше, поэтому каждый подпроцесс будет рассчитан только один раз.
public int Fibonacci(int n) {
if(n == 0 || n == 1){
return n;
}
//n1 -> f(n-1), n2 -> f(n-2)
int n1 = 1, n2 = 0;
//从f(2)开始算起
int N = 2, res = 0;
while(N++ <= n){
//每次计算后更新缓存，当然你也可以使用一个一维数组保存每次的计算结果，只额外空间复杂度就变为O(n)了
res = n1 + n2;
n2 = n1;
n1 = res;
}
return res;
}
Многие люди могут написать приведенный выше код, но они не понимают, что это динамическое программирование.
Резюме: Когда вы анализируете рекурсию сверху вниз и обнаруживаете, что многие подпроцессы вычисляются повторно, вам следует подумать, можно ли кэшировать результаты вычислений каждого подпроцесса снизу вверх.
прыгающие шаги
Описание темы
Лягушка может подпрыгнуть на 1 шаг за раз или на 2 шага за раз. Найдите общее количество способов прыжка, которое лягушка должна совершить, чтобы подняться на ступеньку n-го уровня (разные последовательности считаются разными результатами).
public int JumpFloor(int target) {
}
Разобрать
Рекурсивная версия
Разложение сложных проблем: сложные проблемыtargetВычтите 1 или 2 (соответствует одному шагу и двум шагам), покаtargetКогда оно становится равным 1 или 2 (соответствующим оставшимся одному или двум шагам), мы можем легко получить результат. Следовательно, для текущей лягушки она может выбрать переход на один уровень или два уровня, а также сколько методов прыжка есть для решения оставшихся шагов подпроцесса:
public int JumpFloor(int target) {
//input check
if(target <= 0){
return 0;
}
//base case
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
Вы обнаружите, что на самом деле это последовательность Фибоначчи, просто начиная сf(1) = 1,f(2) = 2Только начало последовательности Фибоначчи. Естественно, вы также должны быть в состоянии написать версию для динамического программирования.
сложные вопросы
Лягушка может подпрыгнуть на 1 шаг за раз, она может подпрыгнуть на 2 шага... она также может подпрыгнуть на n шагов. Найдите, сколькими способами лягушка может запрыгнуть на n-ступенчатую лестницу.
Разобрать
рекурсивная версия
По сути, он все еще декомпозируется, но предыдущий декомпозируется на два шага, а этот — на n шагов:
public int JumpFloorII(int target) {
if(target <= 0){
return 0;
}
//base case，当target=0时表示某个分解分支跳完了所有台阶，这个分支就是一种跳法
if(target == 0){
return 1;
}
//本过程要收集的跳法的总数
int res = 0;
for(int i = 1 ; i <= target ; i++){
//本次选择，选择跳i阶台阶，剩下的台阶交给子过程，每个选择就代表一个分解分支
res += JumpFloorII(target - i);
}
return res;
}
динамическое программирование
Это динамическое программирование немного сложнее.Убедимся, что целевой кеш, Номер Фибоначчи из-заf(n)зависеть только отf(n-1)иf(n-2)Итак, мы реализовали динамическое программирование только с двумя переменными кэша, но здесьf(n)зависит отf(0),f(1),f(2),...,f(n-1), поэтому нам нужно передать порядок длиныnКэш таблицы назадnгосударство (int arr[] = new int[target + 1],arr[target]выражатьf(n)).Тогда по рекурсивному варианту (обычноbase case) чтобы определить, какие значения состояния являются непосредственно определяемыми, например,if(target == 0){ return 1 }Шоуarr[0] = 1,отf(N = 1)Все состояния, начинающиеся с обязательных зависимостей до (f(n < N)) для всех состояний:
int res = 0;
for(int i = 1 ; i <= target ; i++){
res += JumpFloorII(target - i);
}
return res
Таким образом, мы можем вычислить значение каждого подсостояния снизу вверх:
public int JumpFloorII(int target) {
if(target <= 0){
return 0;
}
int arr[] = new int[target + 1];
arr[0] = 1;
for(int i = 1 ; i < arr.length ; i++){
for(int j = 0 ; j < i ; j++){
arr[i] += arr[j];
}
}
return arr[target];
}
Но это все же не оптимальное решение, потому что глядя на тело цикла вы обнаружите, что каждый разf(n)рассчитываются изf(0)добавить кf(n-1), мы можем полностью кэшировать это накопленное значениеpreSum, каждый раз вычисляетсяf(N)Затем обновите кеш доpreSum += f(N). Таким образом, получается оптимальное решение:
public int JumpFloorII(int target) {
if(target <= 0){
return 0;
}
int arr[] = new int[target + 1];
arr[0] = 1;
int preSum = arr[0];
for(int i = 1 ; i < arr.length ; i++){
arr[i] = preSum;
preSum += arr[i];
}
return arr[target];
}
наложение прямоугольника
Описание темы
мы можем использовать2*1Маленькие прямоугольники располагаются горизонтально или вертикально, чтобы закрыть большие прямоугольники. Пожалуйста, используйте н2*1из маленьких прямоугольников, покрывающих2*nСколько всего методов?
public int RectCover(int target) {
}
Разобрать
рекурсивная версия
Имея предыдущий опыт, мы можем быстро написать рекурсивную версию: сначала поставить одну по вертикали или две по горизонтали, а остальные отдать на рекурсивную обработку:
//target 大矩形的边长，也是剩余小矩形的个数
public int RectCover(int target) {
if(target <= 0){
return 0;
}
if(target == 1 || target == 2){
return target;
}
return RectCover(target - 1) + RectCover(target - 2);
}
динамическое программирование
Осталосьf(1)=1,f(2)=2Последовательность Фибоначчи в начале:
//target 大矩形的边长，也是剩余小矩形的个数
public int RectCover(int target) {
if(target <= 0){
return 0;
}
if(target == 1 || target == 2){
return target;
}
//n_1->f(n-1), n_2->f(n-2)，从f(N=3)开始算起
int n_1 = 2, n_2 = 1, N = 3, res = 0;
while(N++ <= target){
res = n_1 + n_2;
n_2 = n_1;
n_1 = res;
}
return res;
}
количество единиц в двоичном формате
Описание темы
Введите целое число и выведите количество единиц в двоичном представлении числа. Отрицательные числа представлены в дополнении.
public int NumberOf1(int n) {
}
Разобрать
Проблема упростила для нас задачу: отрицательные числа представлены дополнительным кодом (инверсия плюс 1), чтобы указать, что все входные параметры являются положительными числами, нам нужно только подсчитать количество единиц в его двоичном представлении и рассматривать только беззнаковые смены во время операций Вот и все.
Типичный способ определить, является ли двоичная цифра 1, состоит в том, чтобы сдвинуть двоичное число вправо до самой младшей цифры двоичной цифры, а затем выполнить И с 1.&, поскольку только самый младший бит в двоичном представлении 1 равен 1, а остальные равны 0, результат фазы и результат совпадают с числом в двоичном бите. В соответствии с этим несложно написать следующий код:
public int NumberOf1(int n) {
int count = 0;
for(int i = 0 ; i < 32 ; i++){
count += ((n >> i) & 1);
}
return count;
}
Конечно, есть более элегантное решение — использоватьn = n & (n - 1)будетnСамая нижняя позиция 1 в двоичных битах - 0 (покаnЕсли он не равен 0, это означает, что есть биты, двоичная система которых равна 1, поэтому, сколько раз можно выполнить такую операцию, показывает, сколько битов равны 1 в двоичной системе):
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
count++;
n &= (n - 1);
}
return count;
}
целая степень чисел
Описание темы
Дана база с плавающей запятой типа double и целочисленный показатель типа int. Найдите показатель степени основания.
public double Power(double base, int exponent) {
}
Разобрать
Это опасный вопрос, и соискатели могут без колебаний написать следующий код:
public double Power(double base, int exponent) {
double res = 1;
for(int i = 1 ; i <= exponent ; i++){
res *= base;
}
return res;
}
Но вы когда-нибудь думали о базеbaseи силаexponentВсе могут быть положительными, отрицательными или 0. Если степень отрицательна, то основание не должно быть равно 0, иначе должно быть выдано арифметическое исключение:
//是否是负数
boolean minus = false;
//如果存在分母
if(exponent < 0){
minus = true;
exponent = -exponent;
if(base == 0){
throw new ArithmeticException("/ by zero");
}
}
Если мощность равна 0, то от 0-го до 0 в соответствии с любой степенью не неопределенного числа 1,0 0, тут следует судить следующим образом:
//如果指数为0
if(exponent == 0){
if(base != 0){
return 1;
}else{
throw new ArithmeticException("0^0 is undefined");
}
}
Осталось только вычислить результат степени, но не забудьте инвертировать результат, если мощность отрицательна:
//指数不为0且分母也不为0，正常计算并返回整数或分数
double res = 1;
for(int i = 1 ; i <= exponent ; i++){
res *= base;
}
if(minus){
return 1/res;
}else{
return res;
}
Может быть, вы можете добавить глазурь на торт, введя расчет пополам для расчета мощности (когда мощность даже2^n = 2^(n/2) * 2^(n/2)):
public double binaryPower(double base, int exp){
if(exp == 1){
return base;
}
double res = 1;
res *= (binaryPower(base, exp/2) * binaryPower(base, exp/2));
return exp % 2 == 0 ? res : res * base;
}
Переупорядочить массив так, чтобы нечетные числа стояли перед четными числами
Описание темы
Введите массив целых чисел, реализуйте функцию для корректировки порядка чисел в массиве, чтобы все нечетные числа находились в первой половине массива, а все четные — во второй половине массива, и убедитесь, что нечетные и нечетные, четные и четные числа междуОтносительная позиция не меняется.
public void reOrderArray(int [] arr) {
}
Разобрать
Прочитав вопрос, я обнаружил, что это похоже на быструю сортировку.partitionИдея очень похожа, это выбор эталона сравнения для разделения массива на две части.Конечно, вы также можете использоватьarr[i] % 2 == 0Для эталона поместите нечетные числа в первую половину и четные числа в первую половину, но толькоO(n)Временная сложность , но относительное положение между нечетными и четными числами после корректировки не может быть гарантировано:
public void reOrderArray(int [] arr) {
if(arr == null || arr.length == 0){
return;
}
int odd = -1;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i] % 2 == 1){
swap(arr, ++odd, i);
}
}
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Когда дело доходит до устойчивости сортировки, мы можем, естественно, думать о сортировке вставками, начиная со второго элемента массива и определяя позицию каждого элемента по очереди.Логика определения такова: сравнить число с предыдущим числом, если Небольшое число меняет местами позиции с предыдущим числом и продолжает сравниваться с предыдущим числом после замены позиций до тех пор, пока предыдущее число не станет меньше или равно числу или не достигнет начала массива и не остановится.
Этот вопрос как раз для того, чтобы изменить логику сравнения с размера значения на: является ли текущее число нечетным, а предыдущее число четным, то рекурсивно переключать позиции вперед. Пример кода выглядит следующим образом:
public void reOrderArray(int [] arr) {
if(arr == null || arr.length == 0){
return;
}
int odd = -1;
for(int i = 1 ; i < arr.length ; i++){
for(int j = i ; j >= 1 ; j--){
if(arr[j] % 2 == 1 && arr[j - 1] % 2 == 0){
swap(arr, j, j - 1);
}
}
}
}
K-й узел снизу в связанном списке
Описание темы
Введите связанный список и выведите k-й узел снизу связанного списка.
public ListNode FindKthToTail(ListNode head,int k) {
}
Разобрать
взаимный, это другая логика обхода от конца к началу, а связанный список чувствителен к обходу от конца к началу. Ранее мы реализовали эту логику обхода, проталкивая стек/рекурсию и реверсируя связанный список.Естественно, то же самое относится к этой проблеме, но это было бы слишком большой проблемой, мы можем добиться этого, используя два указателя на связанный список, разнесенные (k-1) узлами друг от друга.
public ListNode FindKthToTail(ListNode head,int k) {
//input check
if(head == null || k <= 0){
return null;
}
ListNode tmp = new ListNode(0);
tmp.next = head;
ListNode p1 = tmp, p2 = tmp;
while(k > 0 && p1.next != null){
p1 = p1.next;
k--;
}
//length < k
if(k != 0){
return null;
}
while(p1 != null){
p1 = p1.next;
p2 = p2.next;
}
tmp = null; //help gc
return p2;
}
Используемый здесь трюк заключается в создании временного узлаtmpкак начальная точка двух указателей для имитацииp1иди первыйkПосле шага,p2Логика пребывания в исходном положении, когда вы не ходите, помогает нам разобраться в значении указателя в соответствующем положении, так что, когдаp1Пошел головой (p1=null),p2является предпоследнимkузел.
Еще одна проблема заключается в том, что слой автора пытается упростить код, комбинируя вышеперечисленное.9 ~ 12Строка пишется в ленивом режиме следующим образом, что приводит к длинной отладочной ошибке:
while(k-- > 0 && p1.next != null){
p1 = p1.next;
}
Причина в том, чтобыk--писать наwhile()В, независимо от того, судят ли об этомk = k - 1, поэтому код всегда будет вif(k != 0)возвращениеnull, надеюсь, читатели не будут такими беспечными, как автор.
Резюме: при столкновении со сложными операциями с указателями мы могли бы попытаться ввести еще несколько указателей или временных узлов, чтобы облегчить сортировку наших идей и усилить логику кода.
O(1)операции обычно не влияют на производительность.
Объединить два отсортированных связанных списка
Описание темы
Введите два монотонно возрастающих связанных списка и выведите связанный список после объединения двух связанных списков.Конечно, нам нужно, чтобы объединенный связанный список удовлетворял правилу монотонно неубывающего.
public ListNode Merge(ListNode list1,ListNode list2) {
}
Разобрать
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null || list2 == null){
return list1 == null ? list2 : list1;
}
ListNode newHead = list1.val < list2.val ? list1 : list2;
ListNode p1 = (newHead == list1) ? list1.next : list1;
ListNode p2 = (newHead == list2) ? list2.next : list2;
ListNode p = newHead;
while(p1 != null && p2 != null){
if(p1.val <= p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
while(p1 != null){
p.next = p1;
p = p.next;
p1 = p1.next;
}
while(p2 != null){
p.next = p2;
p = p.next;
p2 = p2.next;
}
return newHead;
}
подструктура дерева
Описание темы
Введите два бинарных дерева A и B и определите, является ли B подструктурой A. (ps: мы согласны с тем, что пустое дерево не является подструктурой любого дерева)
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return process(root1, root2);
}
Разобрать
这是一道典型的分解求解的复杂问题。典型的二叉树分解：遍历头结点、遍历左子树、遍历右子树。 Сначала подпишитесьroot1иroot2Равенство значений делится на два случая:
- Значения двух головных узлов равны, и
root2.leftСлишкомroo1.leftподструктура (рекурсивная),root2.rightСлишкомroot1.rightПодструктура (рекурсивная), затем возвратtrue. - В противном случае видеть только тогда, когда
root2заroot1.leftподструктураroot2заroot1.rightможет быть возвращен только тогда, когда подструктураtrue
Согласно двум приведенным выше пунктам легко нарисовать следующую рекурсивную логику:
if(root1.val == root2.val){
if(process(root1.left, root2.left) && process(root1.right, root2.right)){
return true;
}
}
return process(root1.left, root2) || process(root1.right, root2);
Далее определите мертвое состояние рекурсивного, если дочерний процессroot2=nullТогда объяснение находится в процессе сравнения сверху внизroot2Узлы были перечислены и сравнены, независимо отroot1Этоnull, подпроцедура должна вернутьtrue:
if(root2 == null){
return true;
}
но еслиroot2 != nullиroot1 = null, он должен вернутьсяfalse
if(root1 == null && root2 != null){
return false;
}
Полный код выглядит следующим образом:
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return process(root1, root2);
}
public boolean process(TreeNode root1, TreeNode root2){
if(root2 == null){
return true;
}
if(root1 == null && root2 != null){
return false;
}
if(root1.val == root2.val){
if(process(root1.left, root2.left) && process(root1.right, root2.right)){
return true;
}
}
return process(root1.left, root2) || process(root1.right, root2);
}
}
зеркальное отображение бинарного дерева
Описание темы
Управляет заданным бинарным деревом, преобразовывая его в зеркальное отображение исходного бинарного дерева.
public void Mirror(TreeNode root) {
}
Разобрать
Из рисунка видно, что получение зеркального отображения бинарного дерева заключается в том, чтобы поменять местами левого и правого потомков каждой вершины исходного дерева (это правило надо найти), то есть нам нужно только для обхода каждого узла и обменаleft,rightРеференс указывает на него, и у нас есть полноценный предзаказный обход:
public void Mirror(TreeNode root) {
if(root == null){
return;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
Mirror(root.left);
Mirror(root.right);
}
печатать матрицу по часовой стрелке
Описание темы
Введите матрицу и напечатайте каждое число по часовой стрелке снаружи внутрь.Например, если вы введете следующую матрицу 4 X 4: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 распечатайте Числа 1,2 ,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
public ArrayList<Integer> printMatrix(int [][] matrix) {
}
Разобрать
Пока идеи печати четко проанализированы (траектория печати может быть определена в верхнем левом и нижнем правом углах), этот вопрос в основном исследует понимание условного контроля. Просто поставьте точку в левом верхнем углу(i,j)и точка в правом нижнем углу(m,n), печать этого круга можно разбить на четыре этапа:
Однако, если точки в верхнем левом и нижнем правом углах находятся на строке или столбце, нет необходимости разлагать ее, просто распечатать строку или столбец напрямую.Логика печати следующая:
public void printEdge(int[][] matrix, int i, int j, int m, int n, ArrayList<Integer> res){
if(i == m && j == n){
res.add(matrix[i][j]);
return;
}
if(i == m || j == n){
//only one while will be execute
while(i < m){
res.add(matrix[i++][j]);
}
while(j < n){
res.add(matrix[i][j++]);
}
res.add(matrix[m][n]);
return;
}
int p = i, q = j;
while(q < n){
res.add(matrix[p][q++]);
}
//q == n
while(p < m){
res.add(matrix[p++][q]);
}
//p == m
while(q > j){
res.add(matrix[p][q--]);
}
//q == j
while(p > i){
res.add(matrix[p--][q]);
}
//p == i
}
Затем мы передаем в функцию верхний левый и нижний правый углы каждого круга:
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
return res;
}
int i = 0, j = 0, m = matrix.length - 1, n = matrix[0].length - 1;
while(i <= m && j <= n){
printEdge(matrix, i++, j++, m--, n--, res);
}
return res;
}
стек, содержащий функцию min
Описание темы
Определите структуру данных стека, пожалуйста, реализуйте функцию min в этом типе, которая может получить наименьший элемент, содержащийся в стеке (временная сложность должна быть O (1)).
public class Solution {
public void push(int node) {
}
public void pop() {
}
public int top() {
}
public int min() {
}
}
Разобрать
Самая прямая идея состоит в том, чтобы использовать переменную для сохранения минимального значения существующих элементов в стеке, но это допустимо только для стеков, которые только сохраняют, но не извлекают.Когда извлекаемое значение не является минимальным значением, это не имеет никакого эффекта. , но когда минимальное значение извлекается, мы не можем получить минимальное значение в текущем стеке. Решение состоит в том, чтобы использовать стек минимального значения. Вершина стека всегда сохраняет минимальное значение в текущем стеке. Каждый раз, когда стек данных сохраняет данные, стек минимального значения будет соответственно помещать сохраненное минимальное значение на вершину стека. :
private Stack<Integer> dataStack = new Stack();
private Stack<Integer> minStack = new Stack();
public void push(int node) {
dataStack.push(node);
if(!minStack.empty() && minStack.peek() < node){
minStack.push(minStack.peek());
}else{
minStack.push(node);
}
}
public void pop() {
if(!dataStack.empty()){
dataStack.pop();
minStack.pop();
}
}
public int top() {
if(!dataStack.empty()){
return dataStack.peek();
}
throw new IllegalStateException("stack is empty");
}
public int min() {
if(!dataStack.empty()){
return minStack.peek();
}
throw new IllegalStateException("stack is empty");
}
последовательность нажатия и выталкивания стека
Описание темы
Введите две целочисленные последовательности, первая последовательность представляет собой последовательность выталкивания стека, оцените, может ли вторая последовательность быть последовательностью всплывающих окон стека. Предположим, нажатие на стекВсе числа не равны. Например, последовательность 1, 2, 3, 4, 5 — это последовательность проталкивания стека, последовательность 4, 5, 3, 2, 1 — это последовательность извлечения, соответствующая последовательности стека, а 4, 3, 5, 1, 2 Это не может быть последовательность выталкивания последовательности нажатия. (Примечание: две последовательностидлина равнаиз)
public boolean IsPopOrder(int [] arr1,int [] arr2) {
}
Разобрать
Можно использовать два указателяi,j, изначальноiуказывает на первый в последовательности нажатия,jУкажите на первую последовательность извлечения, пытаясь поместить последовательность push в стек по порядку:
- если
arr1[i] != arr2[j]Такarr1[i]нажать на стек и двигаться назадi(Выражатьarr1[i]Не время всплывать) - если сдвиг назад
iпозже узналarr1[i] == arr2[j], то токarr1[i]После нажатия должен быть немедленно выброшен, и всплывает, производя заданную последовательность, поэтому не нажимаетсяarr1[i](указывает на то, что нажато и выскочило) и сдвинуто назадi,jТакже двигайтесь назад (указывая на всплывающую последовательностьarr2[j]Запись была сгенерирована, а затем может быть сгенерирована возможная всплывающая запись). - Поскольку оба шага 2 и 3 сдвинуты назад
iпоэтому условие завершения петлиiприбытьarr1.length, если в этот момент в стеке еще есть элементы, то последовательность, формируемая от вершины стека к низу стека, должна быть такой же, какarr2серединаjПоследовательность после этого такая же, чтобы вернутьсяtrue.
public boolean IsPopOrder(int [] arr1,int [] arr2) {
//input check
if(arr1 == null || arr2 == null || arr1.length != arr2.length || arr1.length == 0){
return false;
}
Stack<Integer> stack = new Stack();
int length = arr1.length;
int i = 0, j = 0;
while(i < length && j < length){
if(arr1[i] != arr2[j]){
stack.push(arr1[i++]);
}else{
i++;
j++;
}
}
while(j < length){
if(arr2[j] != stack.peek()){
return false;
}else{
stack.pop();
j++;
}
}
return stack.empty() && j == length;
}
Распечатайте бинарное дерево сверху вниз
Описание темы
Каждый узел бинарного дерева печатается сверху вниз, а узлы одного уровня печатаются слева направо.
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
}
Разобрать
Используйте очередь, чтобы сохранить дочерние узлы текущего пройденного узла, сначала добавьте корневой узел в очередь, а затем выполните непустой цикл очереди:
- Возьмите узел из головы очереди и напечатайте значение узла
- Если левый дочерний элемент выбранного узла не пуст, поместите его левый дочерний элемент в конец очереди.
- Если правый дочерний элемент выбранного узла не пуст, поместите его правый дочерний элемент в конец очереди.
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null){
return res;
}
LinkedList<TreeNode> queue = new LinkedList();
queue.addLast(root);
while(queue.size() > 0){
TreeNode node = queue.pollFirst();
res.add(node.val);
if(node.left != null){
queue.addLast(node.left);
}
if(node.right != null){
queue.addLast(node.right);
}
}
return res;
}
Последовательность обхода бинарного дерева поиска в обратном порядке
Описание темы
Введите целочисленный массив, чтобы определить, является ли массив результатом обхода двоичного дерева поиска в обратном порядке. Если да, выведите Yes, иначе выведите No. Предположим, что любые два числа входного массива отличны друг от друга.
public boolean VerifySquenceOfBST(int [] sequence) {
}
Разобрать
Для последовательности пост-порядка бинарного дерева мы можем определить, что последнее число является корневым узлом, и мы также можем определить, что первая половина является последовательностью пост-порядка левого поддерева, а последняя часть является пост-узлом. -порядковая последовательность правого поддерева.
Столкнувшись с такими сложными проблемами, мы все же можем принять трехэтапную стратегию (корневой узел, левое поддерево, правое поддерево):
- Если левый подметку текущего корневого узлалучшее время годаИ его правое поддерево тоже BST, тогда оно может быть BST
- При условии 1, если левое поддеревомаксимальное значениеменьше, чем корень и правое поддеревоминимумбольше, чем корневой узел, то дерево является BST
В соответствии с этим нам нужно определить рекурсивное тело, информация, которую необходимо собрать рекурсивному телу, выглядит следующим образом: нижний слой должен вернуть мне свое максимальное значение, минимальное значение и является ли он BST
class Info{
boolean isBST;
int max;
int min;
Info(boolean isBST, int max, int min){
this.isBST = isBST;
this.max = max;
this.min = min;
}
}
Рекурсивное тело определяется следующим образом:
public Info process(int[] arr, int start, int end){
if(start < 0 || end > arr.length - 1 || start > end){
throw new IllegalArgumentException("invalid input");
}
//base case : only one node
if(start == end){
return new Info(true, arr[end], arr[end]);
}
int root = arr[end];
Info left, right;
//not exist left child
if(arr[start] > root){
right = process(arr, start, end - 1);
return new Info(root < right.min && right.isBST,
Math.max(root, right.max), Math.min(root, right.min));
}
//not exist right child
if(arr[end - 1] < root){
left = process(arr, start, end - 1);
return new Info(root > left.max && left.isBST,
Math.max(root, left.max), Math.min(root, left.min));
}
int l = 0, r = end - 1;
while(r > l && r - l != 1){
int mid = l + ((r - l) >> 1);
if(arr[mid] > root){
r = mid;
}else{
l = mid;
}
}
left = process(arr, start, l);
right = process(arr, r, end - 1);
return new Info(left.isBST && right.isBST && root > left.max && root < right.min,
right.max, left.min);
}
Резюме: Задача сбора информации о бинарном дереве делится на этапы:
- Информация для сбора для анализа текущего состояния
- По информации нижнего уровня обрабатывается информация о текущем состоянии
- Определить условие завершения рекурсии
Путь в бинарном дереве, который суммируется со значением
Описание темы
Введите корневой узел бинарного дерева и целое число и выведите все пути в бинарном дереве, сумма значений узлов которых является входным целым числом. Путь определяется как начинающийся от корня дерева и идущий вниздо листового узлаПройденные узлы образуют путь. (Примечание: в списке возвращаемых значений первым идет массив с наибольшей длиной массива)
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
}
Разобрать
Из обзора мы видим, что нам нужна идея обхода сверху вниз от корневого узла к каждому конечному узлу, и можно просто использовать обход в предварительном порядке Нам нужно только изменить значение текущего узла, когда мы придем к текущий узел.Добавьте его в стек, а затем извлеките значение текущего узла, сохраненное в стеке, при выходе из текущего узла, вы можете использовать симуляцию стека для сохранения узлов, которые проходят сверху вниз, так что, когда вы приходят к каждому листовому узлу, только надо определить, равна ли сумма значений в стекеtargetВот и все.
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
if(root == null){
return res;
}
Stack<Integer> stack = new Stack<Integer>();
preOrder(root, stack, 0, target, res);
return res;
}
public void preOrder(TreeNode root, Stack<Integer> stack, int sum, int target,
ArrayList<ArrayList<Integer>> res){
if(root == null){
return;
}
stack.push(root.val);
sum += root.val;
//leaf node
if(root.left == null && root.right == null && sum == target){
ArrayList<Integer> one = new ArrayList();
one.addAll(stack);
res.add(one);
}
preOrder(root.left, stack, sum, target, res);
preOrder(root.right, stack, sum, target, res);
sum -= stack.pop();
}
Репликация сложных связанных списков
Описание темы
Введите сложный связанный список (в каждом узле есть значение узла и два указателя, один указывает на следующий узел, а другой специальный указатель указывает на любой узел), а возвращаемый результат является заголовком сложного связанного списка после репликация. (Обратите внимание, пожалуйста, не возвращайте ссылку на узел в параметре выходного результата, иначе программа решения проблемы сразу вернет пустое значение)
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
}
}
Разобрать
Основная трудность этой задачи состоит в том, чтоrandomОбработка указателей.
Способ 1: использовать хэш-таблицу, дополнительное пространство O(n)
Узлы могут иметь копию списка с хеш-таблицей для сохранения,keyявляется исходным узлом,valueявляется узлом реплики, а затем пройтиkeyвыньте каждый соответствующийvalueкопировать узелnextуказатель иrandomНабор указателей:
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null){
return null;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap();
RandomListNode p = pHead;
//copy
while(p != null){
RandomListNode cp = new RandomListNode(p.label);
map.put(p, cp);
p = p.next;
}
//link
p = pHead;
while(p != null){
RandomListNode cp = map.get(p);
cp.next = (p.next == null) ? null : map.get(p.next);
cp.random = (p.random == null) ? null : map.get(p.random);
p = p.next;
}
return map.get(pHead);
}
Способ 2: добавление узлов, дополнительное пространство O(1)
Сначала сделайте копию каждого узла и вставьте его после соответствующего узла, затем пройдитесь по связанному списку, чтобы скопировать узел узла.randomУказатель установлен, и, наконец, исходный узел и узел копии разделены на два связанных списка.
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null){
return null;
}
RandomListNode p = pHead;
while(p != null){
RandomListNode cp = new RandomListNode(p.label);
cp.next = p.next;
p.next = cp;
p = p.next.next;
}
//more than two node
//link random pointer
p = pHead;
RandomListNode cp;
while(p != null){
cp = p.next;
cp.random = (p.random == null) ? null : p.random.next;
p = p.next.next;
}
//split source and copy
p = pHead;
RandomListNode newHead = p.next;
//p != null -> p.next != null
while(p != null){
cp = p.next;
p.next = p.next.next;
p = p.next;
cp.next = (p == null) ? null : p.next;
}
return newHead;
}