Эта статья перенесена из личного блога:CyC2018/CS-Notes
3. Повторяющиеся числа в массиве
Описание темы
Все числа в массиве длины n находятся в диапазоне от 0 до n-1. Некоторые числа в массиве повторяются, но я не знаю, сколько чисел повторяется, и я не знаю, сколько раз повторяется каждое число. Найдите любое повторяющееся число в массиве.
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
Идеи решения проблем
Это требует временной сложности O (N) и пространственной сложности O (1). Таким образом, вы не можете использовать отсортированный метод, и вы не можете использовать дополнительный массив маркеров.
Для такой задачи, когда элементы массива находятся в диапазоне [0, n-1], элемент со значением i можно настроить на i-ю позицию для решения.
Взяв (2, 3, 1, 0, 2, 5) в качестве примера, при переходе к позиции 4 число в этой позиции равно 2, но во второй позиции уже есть значение 2, поэтому вы можете знать, что 2 повтора:
public boolean duplicate(int[] nums, int length, int[] duplication) {
if (nums == null || length <= 0)
return false;
for (int i = 0; i < length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
swap(nums, i, nums[i]);
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
4. Найти в 2D-массиве
Описание темы
В двумерном массиве каждая строка сортируется по возрастанию слева направо, а также по возрастанию сверху вниз. Учитывая число, определить, находится ли число в двумерном массиве.
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
Идеи решения проблем
Это требует временной сложности O (M + N) и пространственной сложности O (1). где М — количество строк, а N — количество столбцов.
Число в двумерном массиве, число, меньшее, чем должно быть слева, и число, большее, чем должно быть внизу. Поэтому, начиная с правого верхнего угла, диапазон поиска может быть сужен в соответствии с соотношением размеров между целью и текущим элементом.Диапазон поиска текущего элемента — это все элементы в левом нижнем углу.
public boolean Find(int target, int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int rows = matrix.length, cols = matrix[0].length;
int r = 0, c = cols - 1; // 从右上角开始
while (r <= rows - 1 && c >= 0) {
if (target == matrix[r][c])
return true;
else if (target > matrix[r][c])
r++;
else
c--;
}
return false;
}
5. Замените пробелы
Описание темы
Замените пробелы в строке на "%20".
Input:
"A B"
Output:
"A%20B"
Идеи решения проблем
Дополняет любые символы в конце строки, чтобы длина строки была равна длине после замены. Поскольку пробел необходимо заменить тремя символами (%20), при пересечении пробела в конце необходимо заполнить два произвольных символа.
Пусть P1 указывает на исходный конец строки, а P2 — на текущий конец строки. P1 и P2 проходятся сзади вперед.Когда P1 проходит в пробел, позиция, на которую указывает P2, должна быть заполнена 02% по очереди (обратите внимание, что это в обратном порядке), в противном случае значение указанного символа на P1 заполняется.
Цель перехода от конца к началу состоит в том, чтобы изменить содержимое, на которое указывает P2, не затрагивая содержимое исходной строки, пройденной P1.
public String replaceSpace(StringBuffer str) {
int P1 = str.length() - 1;
for (int i = 0; i <= P1; i++)
if (str.charAt(i) == ' ')
str.append(" ");
int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
char c = str.charAt(P1--);
if (c == ' ') {
str.setCharAt(P2--, '0');
str.setCharAt(P2--, '2');
str.setCharAt(P2--, '%');
} else {
str.setCharAt(P2--, c);
}
}
return str.toString();
}
6. Распечатайте связанный список от начала до конца
Описание темы
Выведите значение каждого узла в обратном порядке от конца к концу.
Идеи решения проблем
использовать рекурсию
Чтобы напечатать связанный список 1->2->3(3,2,1) в обратном порядке, вы можете сначала напечатать связанный список 2->3(3,2) в обратном порядке, а затем напечатать первый узел 1 в конце. Связанный список 2->3 можно рассматривать как новый связанный список.Чтобы напечатать связанный список в обратном порядке, вы можете продолжать использовать функцию решения, то есть вызвать себя в функции решения, которая является рекурсивной функцией.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> ret = new ArrayList<>();
if (listNode != null) {
ret.addAll(printListFromTailToHead(listNode.next));
ret.add(listNode.val);
}
return ret;
}
Использовать метод заголовка
Используйте метод вставки головы, чтобы получить перевернутый связанный список.
Разница между головным узлом и первым узлом:
- Головной узел — это дополнительный узел, используемый в методе заголовка, этот узел не хранит значения;
- Первый узел — это первый узел связанного списка, который фактически хранит значение.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
// 头插法构建逆序链表
ListNode head = new ListNode(-1);
while (listNode != null) {
ListNode memo = listNode.next;
listNode.next = head.next;
head.next = listNode;
listNode = memo;
}
// 构建 ArrayList
ArrayList<Integer> ret = new ArrayList<>();
head = head.next;
while (head != null) {
ret.add(head.val);
head = head.next;
}
return ret;
}
использовать стек
Стек имеет характеристики «последний пришел — первый вышел».
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.add(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> ret = new ArrayList<>();
while (!stack.isEmpty())
ret.add(stack.pop());
return ret;
}
7. Перестроить бинарное дерево
Описание темы
Бинарное дерево восстанавливается по результатам предпорядкового обхода и неупорядоченного обхода бинарного дерева. Предполагается, что результаты входного обхода в прямом и обратном порядке не содержат повторяющихся чисел.
Идеи решения проблем
Первое значение обхода в прямом порядке — это значение корневого узла. Используйте это значение, чтобы разделить результат обхода по порядку на две части. Левая часть — это результат обхода по порядку левого поддерева дерева, а правая часть — обход по порядку правого поддерева дерева.
// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
for (int i = 0; i < in.length; i++)
indexForInOrders.put(in[i], i);
return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
}
private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
if (preL > preR)
return null;
TreeNode root = new TreeNode(pre[preL]);
int inIndex = indexForInOrders.get(root.val);
int leftTreeSize = inIndex - inL;
root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
return root;
}
8. Следующий узел бинарного дерева
Описание темы
Имея бинарное дерево и узел в нем, найдите следующий узел в порядке обхода и вернитесь. Обратите внимание, что узлы в дереве содержат не только левые и правые дочерние узлы, но и указатели на родительские узлы.
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
Идеи решения проблем
① Если правое поддерево узла не пусто, то следующим узлом узла является крайний левый узел правого поддерева;
② В противном случае ищите дерево, на которое указывает первая левая ссылка, содержащая узел-предок этого узла.
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null)
node = node.left;
return node;
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode)
return parent;
pNode = pNode.next;
}
}
return null;
}
9. Реализуйте очередь с двумя стеками
Описание темы
Реализуйте очередь с двумя стеками для выполнения операций отправки и извлечения очереди.
Идеи решения проблем
Стек in используется для обработки операций push, а стек out используется для обработки операций pop. После того, как элемент помещен в стек in, порядок всплывающих окон меняется на обратный. Когда элемент должен быть извлечен, он должен сначала войти в исходящий стек. В это время порядок извлечения элементов снова меняется на обратный, поэтому порядок извлечения такой же, как и в исходной последовательности стека. Элемент, который входит первым, выходит во-первых, это порядок очереди.
Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();
public void push(int node) {
in.push(node);
}
public int pop() throws Exception {
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());
if (out.isEmpty())
throw new Exception("queue is empty");
return out.pop();
}
10.1 Последовательность Фибоначчи
Описание темы
Найдите n-й член последовательности Фибоначчи, где n
Идеи решения проблем
Если используется рекурсивное решение, некоторые подзадачи пересчитываются. Например, вычисление f(4) требует вычисления f(3) и f(2), вычисление f(3) требует вычисления f(2) и f(1), и вы можете видеть, что f(2) вычисляется многократно.
Рекурсия состоит в том, чтобы разделить проблему на несколько подзадач для решения, и то же самое верно для динамического программирования, но динамическое программирование кэширует решения подзадач, чтобы избежать повторяющихся подзадач.
public int Fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}
Учитывая, что i-й элемент связан только с i-1-м и i-2-м элементами, для решения i-го элемента необходимо хранить только значения первых двух элементов, тем самым уменьшая пространственную сложность с от O(N) до O(1).
public int Fibonacci(int n) {
if (n <= 1)
return n;
int pre2 = 0, pre1 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre2 + pre1;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
Поскольку n, которое нужно решить, меньше 40, сначала можно вычислить результаты первых 40 элементов, а затем можно получить значение n-го элемента с временной сложностью O(1).
public class Solution {
private int[] fib = new int[40];
public Solution() {
fib[1] = 1;
for (int i = 2; i < fib.length; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
public int Fibonacci(int n) {
return fib[n];
}
}
10.2 Наложение прямоугольника
Описание темы
Мы можем использовать маленькие прямоугольники 2*1, чтобы покрыть большие прямоугольники по горизонтали или вертикали. Сколько существует способов покрыть большой прямоугольник 2*n n маленькими прямоугольниками 2*1, не перекрывая друг друга?
Идеи решения проблем
Когда n равно 1, есть только один способ переопределения:
Когда n равно 2, есть два способа переопределения:
Чтобы покрыть большой прямоугольник 2*n, вы можете сначала покрыть прямоугольник 2*1, а затем покрыть прямоугольник 2*(n-1); или сначала покрыть прямоугольник 2*2, а затем покрыть прямоугольник из 2*(n-2) . А прямоугольники, покрывающие 2*(n-1) и 2*(n-2), можно рассматривать как подзадачи. Рекурсивная формула для этой задачи выглядит следующим образом:
public int RectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
10.3 Прыжки по лестнице
Описание темы
Лягушка может подпрыгнуть на 1 шаг за раз или на 2 шага за раз. Найдите, сколькими способами лягушка может подпрыгнуть на n ступенек.
Идеи решения проблем
Когда n = 1, есть только один способ прыгнуть:
При n = 2 есть два метода перехода:
Чтобы перепрыгнуть n шагов, вы можете сначала перепрыгнуть на 1 шаг, затем на n-1 шагов или сначала на 2 шага, а затем на n-2 шагов. Метод прыжков из n-1 и n-2 шагов можно рассматривать как подзадачу, и рекурсивная формула этой задачи:
public int JumpFloor(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 1;
for (int i = 2; i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
10.4 Прыжки с ненормальным шагом
Описание темы
Лягушка может подпрыгнуть на 1 шаг за раз, она может подпрыгнуть на 2 шага... она также может подпрыгнуть на n шагов. Найдите, сколькими способами лягушка может подпрыгнуть на n ступенек.
Идеи решения проблем
динамическое программирование
public int JumpFloorII(int target) {
int[] dp = new int[target];
Arrays.fill(dp, 1);
for (int i = 1; i < target; i++)
for (int j = 0; j < i; j++)
dp[i] += dp[j];
return dp[target - 1];
}
Математический вывод
Подпрыгните на n-1 шагов, вы можете прыгнуть на 1 с n-2, или вы можете прыгнуть на 2 с n-3..., тогда
f(n-1) = f(n-2) + f(n-3) + ... + f(0)
Аналогично, подпрыгнув на n шагов, можно перепрыгнуть 1 из n-1, можно также прыгнуть 2 из n-2... , тогда
f(n) = f(n-1) + f(n-2) + ... + f(0)
В конце концов
f(n) - f(n-1) = f(n-1)
который
f(n) = 2*f(n-1)
Итак, f(n) — пропорциональная последовательность
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
11. Поверните наименьшее число массива
Описание темы
Перемещение первых элементов массива в конец массива называется вращением массива. Введите поворот отсортированного по неубыванию массива, выведите наименьший элемент повернутого массива.
Идеи решения проблем
Разделите повернутый массив пополам, чтобы получить новый повернутый массив с наименьшим элементом и массив, отсортированный по неубыванию. Элементы массива нового повернутого массива составляют половину исходного массива, что уменьшает размер задачи вдвое.Временная сложность этого полуалгоритма составляет O(logN) (для удобства log2N записывается как logN).
Ключ к проблеме в настоящее время состоит в том, чтобы определить, какой из двух массивов, полученных путем деления пополам, является повернутым массивом, а какой — неубывающим массивом. Мы легко знаем, что первый элемент неубывающего массива должен быть меньше или равен последнему элементу.
Решите, изменив алгоритм бинарного поиска (l для низкого уровня, m для среднего уровня, h для высокого уровня):
- Когда nums[m]
- В противном случае массив в интервале [m + 1, h] является повернутым массивом, пусть l = m + 1.
public int minNumberInRotateArray(int[] nums) {
if (nums.length == 0)
return 0;
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h])
h = m;
else
l = m + 1;
}
return nums[l];
}
Если элементы массива разрешено повторять, то будет особый случай: nums[l] == nums[m] == nums[h], в это время невозможно определить, в каком интервале находится решение, и необходимо переключиться на последовательный поиск. Например, для массива {1,1,1,0,1} все числа, на которые указывают l, m и h, равны 1. В настоящее время невозможно узнать, в каком интервале находится наименьшее число 0.
public int minNumberInRotateArray(int[] nums) {
if (nums.length == 0)
return 0;
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[l] == nums[m] && nums[m] == nums[h])
return minNumber(nums, l, h);
else if (nums[m] <= nums[h])
h = m;
else
l = m + 1;
}
return nums[l];
}
private int minNumber(int[] nums, int l, int h) {
for (int i = l; i < h; i++)
if (nums[i] > nums[i + 1])
return nums[i + 1];
return nums[l];
}
12. Пути в матрице
Описание темы
Определяет, существует ли в матрице путь, содержащий все символы строки. Путь может начинаться с любой сетки в матрице, и каждый шаг может перемещать одну сетку вверх, вниз, влево и вправо в матрице. Если путь проходит через сетку в матрице, путь больше не может войти в эту сетку.
Например, матрица ниже содержит путь bfce.
Идеи решения проблем
Решите, используя поиск с возвратом, метод грубой силы, который решает проблему путем поиска всех возможных результатов. Метод поиска с возвратом должен выполнять возврат (возврат) в конце поиска и очищать состояние, установленное в этом процессе поиска, тем самым запуская новый процесс поиска. Например, в приведенном ниже примере, начиная с f, на следующем шаге есть 4 возможности поиска.Если вы сначала ищете b, вам нужно пометить b как уже использованный, чтобы предотвратить повторное использование. После того, как этот поиск завершен, вам нужно очистить используемое состояние b и найти c.
Входными данными для этого вопроса является массив, а не матрица (двумерный массив), поэтому вам нужно сначала преобразовать массив в матрицу.
private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int rows;
private int cols;
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
if (rows == 0 || cols == 0) return false;
this.rows = rows;
this.cols = cols;
boolean[][] marked = new boolean[rows][cols];
char[][] matrix = buildMatrix(array);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (backtracking(matrix, str, marked, 0, i, j))
return true;
return false;
}
private boolean backtracking(char[][] matrix, char[] str,
boolean[][] marked, int pathLen, int r, int c) {
if (pathLen == str.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols
|| matrix[r][c] != str[pathLen] || marked[r][c]) {
return false;
}
marked[r][c] = true;
for (int[] n : next)
if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1]))
return true;
marked[r][c] = false;
return false;
}
private char[][] buildMatrix(char[] array) {
char[][] matrix = new char[rows][cols];
for (int r = 0, idx = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
matrix[r][c] = array[idx++];
return matrix;
}
13. Диапазон движения робота
Описание темы
На земле лежит квадрат с m строк и n столбцов. Робот начинает движение с сетки координат (0, 0) и может перемещаться только по одной сетке в четырех направлениях, влево, вправо, вверх и вниз, но не может войти в сетку, где сумма цифр строки и координаты столбца больше k.
Например, когда k равно 18, робот может войти в квадрат (35,37), потому что 3+5+3+7=18. Однако он не может войти в квадрат (35,38), потому что 3+5+3+8=19. Сколько квадратов может достичь робот?
Идеи решения проблем
Решите с помощью метода поиска в глубину (DFS). Поиск с возвратом — это частный случай поиска в глубину, который должен устанавливать некоторые локальные состояния процесса поиска во время процесса поиска и очищать состояние после завершения поиска. Обычный поиск в глубину не требует использования этих локальных состояний, хотя все же можно установить некоторые глобальные состояния.
private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int cnt = 0;
private int rows;
private int cols;
private int threshold;
private int[][] digitSum;
public int movingCount(int threshold, int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.threshold = threshold;
initDigitSum();
boolean[][] marked = new boolean[rows][cols];
dfs(marked, 0, 0);
return cnt;
}
private void dfs(boolean[][] marked, int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])
return;
marked[r][c] = true;
if (this.digitSum[r][c] > this.threshold)
return;
cnt++;
for (int[] n : next)
dfs(marked, r + n[0], c + n[1]);
}
private void initDigitSum() {
int[] digitSumOne = new int[Math.max(rows, cols)];
for (int i = 0; i < digitSumOne.length; i++) {
int n = i;
while (n > 0) {
digitSumOne[i] += n % 10;
n /= 10;
}
}
this.digitSum = new int[rows][cols];
for (int i = 0; i < this.rows; i++)
for (int j = 0; j < this.cols; j++)
this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j];
}
14. Разрежьте веревку
Описание темы
Разрежьте кусок веревки на куски так, чтобы произведение длин каждого куска было наибольшим.
n = 2
return 1 (2 = 1 + 1)
n = 10
return 36 (10 = 3 + 3 + 4)
Идеи решения проблем
жадный
Отрежьте как можно больше веревки длины 3 и не допускайте появления веревки длины 1. Если это так, возьмите кусок веревки длиной 3 из уже отрезанной длины и снова соберите ее с длиной 1 и разрежьте их на две части длиной 2.
Доказательство: когда n >= 5, 3(n - 3) - n = 2n - 9 > 0 и 2(n - 2) - n = n - 4 > 0. Таким образом, в случае n >= 5, разрежьте веревку на 2 или 3 части, произведение будет больше. А поскольку 3(n - 3) - 2(n - 2) = n - 5 >= 0, разрезание на длину 3 дает больший продукт, чем длина 2.
public int integerBreak(int n) {
if (n < 2)
return 0;
if (n == 2)
return 1;
if (n == 3)
return 2;
int timesOf3 = n / 3;
if (n - timesOf3 * 3 == 1)
timesOf3--;
int timesOf2 = (n - timesOf3 * 3) / 2;
return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2));
}
динамическое программирование
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
return dp[n];
}
15. Количество единиц в двоичном коде
Описание темы
Введите целое число и выведите количество единиц в двоичном представлении числа.
n&(n-1)
Эта побитовая операция удаляет младший значащий бит в представлении n на уровне битов.
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000
Временная сложность: O(M), где M представляет количество единиц.
public int NumberOf1(int n) {
int cnt = 0;
while (n != 0) {
cnt++;
n &= (n - 1);
}
return cnt;
}
Integer.bitCount()
public int NumberOf1(int n) {
return Integer.bitCount(n);
}
16. Целые степени чисел
Описание темы
Дана база чисел с плавающей запятой типа double и целочисленный показатель степени типа int, найдите показатель степени базы.
Идеи решения проблем
В последующем обсуждении x обозначает основание, а n обозначает показатель степени.
потому что (х*х)n/2Его можно решить рекурсивно, и каждая рекурсия n уменьшается вдвое, поэтому временная сложность всего алгоритма составляет O(logN).
public double Power(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
boolean isNegative = false;
if (exponent < 0) {
exponent = -exponent;
isNegative = true;
}
double pow = Power(base * base, exponent / 2);
if (exponent % 2 != 0)
pow = pow * base;
return isNegative ? 1 / pow : pow;
}
17. Выведите n цифр от 1 до max
Описание темы
Введите число n и выведите десятичные цифры от 1 до наибольшей по порядку. Например, если вы введете 3, он напечатает 1, 2, 3 до максимум 3 цифр, то есть 999.
Идеи решения проблем
Так как n может быть очень большим, число не может быть представлено непосредственно целым числом, а хранится в массиве символов.
Используйте возврат, чтобы получить все числа.
public void print1ToMaxOfNDigits(int n) {
if (n <= 0)
return;
char[] number = new char[n];
print1ToMaxOfNDigits(number, 0);
}
private void print1ToMaxOfNDigits(char[] number, int digit) {
if (digit == number.length) {
printNumber(number);
return;
}
for (int i = 0; i < 10; i++) {
number[digit] = (char) (i + '0');
print1ToMaxOfNDigits(number, digit + 1);
}
}
private void printNumber(char[] number) {
int index = 0;
while (index < number.length && number[index] == '0')
index++;
while (index < number.length)
System.out.print(number[index++]);
System.out.println();
}
18.1 Удаление узла связанного списка за время O(1)
Идеи решения проблем
① Если узел не является хвостовым узлом, вы можете напрямую присвоить значение следующего узла узлу, затем сделать узел указателем на следующий узел, а затем удалить следующий узел, временная сложность O (1) .
② В противном случае вам нужно сначала пройти по связанному списку, найти предыдущий узел узла, а затем позволить предыдущему узлу указывать на ноль, а временная сложность равна O(N).
Подводя итог, если выполняется N операций, количество операций, необходимых для узла, равно N-1+N=2N-1, где N-1 означает, что каждый узел, не являющийся хвостовым узлом, занимает O(1) времени. общее количество раз, когда узел оперирует сложностью, N представляет общее количество раз, когда хвостовой узел оперирует узлом с временной сложностью O(N). (2N-1)/N ~ 2, поэтому средняя временная сложность этого алгоритма составляет O(1).
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
if (head == null || tobeDelete == null)
return null;
if (tobeDelete.next != null) {
// 要删除的节点不是尾节点
ListNode next = tobeDelete.next;
tobeDelete.val = next.val;
tobeDelete.next = next.next;
} else {
if (head == tobeDelete)
// 只有一个节点
head = null;
else {
ListNode cur = head;
while (cur.next != tobeDelete)
cur = cur.next;
cur.next = null;
}
}
return head;
}
18.2 Удаление повторяющихся узлов в связанном списке
Описание темы
Описание решения проблемы
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null)
return pHead;
ListNode next = pHead.next;
if (pHead.val == next.val) {
while (next != null && pHead.val == next.val)
next = next.next;
return deleteDuplication(next);
} else {
pHead.next = deleteDuplication(pHead.next);
return pHead;
}
}
19. Сопоставление регулярных выражений
Описание темы
Пожалуйста, реализуйте функцию для сопоставления регулярных выражений, включая '.' и '*'. Символ '.' в шаблоне означает один любой символ, а '*' означает, что предшествующий ему символ может встречаться любое количество раз (включая 0).
В этом вопросе совпадение означает, что все символы строки соответствуют всему шаблону. Например, строка «aaa» соответствует шаблонам «a.a» и «ab*ac*a», но ни «aa.a», ни «ab*a».
Идеи решения проблем
Следует отметить, что «.» используется как произвольный символ, а «*» используется для повторения предыдущего символа. Роли этих двух различны, и роль «.» нельзя сравнивать с «*», так что она рассматривается как повторение предыдущего символа один раз.
public boolean match(char[] str, char[] pattern) {
int m = str.length, n = pattern.length;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++)
if (pattern[i - 1] == '*')
dp[0][i] = dp[0][i - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
dp[i][j] = dp[i - 1][j - 1];
else if (pattern[j - 1] == '*')
if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {
dp[i][j] |= dp[i][j - 1]; // a* counts as single a
dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a
dp[i][j] |= dp[i][j - 2]; // a* counts as empty
} else
dp[i][j] = dp[i][j - 2]; // a* only counts as empty
return dp[m][n];
}
20. Строки, представляющие числовые значения
Описание темы
true
"+100"
"5e2"
"-123"
"3.1416"
"-1E-16"
false
"12e"
"1a3.14"
"1.2.3"
"+-5"
"12e+4.3"
Идеи решения проблем
Используйте регулярные выражения для сопоставления.
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1 次
+ ： 重复 1 ~ n 次
* ： 重复 0 ~ n 次
. ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
public boolean isNumeric(char[] str) {
if (str == null || str.length == 0)
return false;
return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}
21. Переупорядочить массив так, чтобы нечетные числа стояли перед четными
Описание темы
Необходимо следить за тем, чтобы относительные положения между нечетными и нечетными числами, четными числами и четными числами оставались неизменными, что отличается от книг.
Идеи решения проблем
Метод 1: Создайте новый массив, временная сложность O (N), пространственная сложность O (N).
public void reOrderArray(int[] nums) {
// 奇数个数
int oddCnt = 0;
for (int x : nums)
if (!isEven(x))
oddCnt++;
int[] copy = nums.clone();
int i = 0, j = oddCnt;
for (int num : copy) {
if (num % 2 == 1)
nums[i++] = num;
else
nums[j++] = num;
}
}
private boolean isEven(int x) {
return x % 2 == 0;
}
Метод 2: используйте идею всплытия, и каждый раз, когда текущее четное число всплывает до текущего крайнего правого. Временная сложность O(N2), пространственная сложность O(1), время для пространства.
public void reOrderArray(int[] nums) {
int N = nums.length;
for (int i = N - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (isEven(nums[j]) && !isEven(nums[j + 1])) {
swap(nums, j, j + 1);
}
}
}
}
private boolean isEven(int x) {
return x % 2 == 0;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
22. Последний K узел в связанном списке
Идеи решения проблем
Пусть длина связанного списка равна N. Установите два указателя P1 и P2, пусть P1 сначала переместит K узлов, затем есть N - K узлов, которые можно переместить. В это время пусть P1 и P2 перемещаются одновременно, вы можете знать, что когда P1 перемещается в конец связанного списка, P2 перемещается к N-K-му узлу, который является последним K-м узлом.
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null)
return null;
ListNode P1 = head;
while (P1 != null && k-- > 0)
P1 = P1.next;
if (k > 0)
return null;
ListNode P2 = head;
while (P1 != null) {
P1 = P1.next;
P2 = P2.next;
}
return P2;
}
23. Вход узла кольца в связанный список
Описание темы
Связанный список содержит кольца, найдите входной узел кольца связанного списка. Просьба не использовать дополнительное пространство.
Идеи решения проблем
С двойными указателями один указатель быстро перемещает два узла за раз, а один медленный указатель перемещает один узел за раз. Поскольку существует кольцо, два указателя должны встретиться в каком-то узле кольца. Предполагая, что точка встречи находится в позиции z1 на следующем рисунке, количество узлов, перемещаемых быстрым, равно x + 2y + z, а медленное — x + y, Поскольку быстрое в два раза быстрее медленного, x + 2y + z = 2(x+y), чтобы получить x=z.
В точке встречи медленному нужно переместить еще на z узлов, чтобы добраться до точки входа в кольцо, а если быстрое перемещается с самого начала и скорость изменяется для перемещения по одному узлу за раз, то ему нужно перемещаться еще на x узлов к точке входа в кольцо. Выше был сделан вывод, что x=z, поэтому быстрый и медленный встретятся в точке входа в кольцо.
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null || pHead.next == null)
return null;
ListNode slow = pHead, fast = pHead;
do {
fast = fast.next.next;
slow = slow.next;
} while (slow != fast);
fast = pHead;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
24. Обратно связанный список
Идеи решения проблем
рекурсия
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode next = head.next;
head.next = null;
ListNode newHead = ReverseList(next);
next.next = head;
return newHead;
}
повторять
Используйте метод заголовка.
public ListNode ReverseList(ListNode head) {
ListNode newList = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newList.next;
newList.next = head;
head = next;
}
return newList.next;
}
25. Объедините два отсортированных связанных списка
Описание темы
Идеи решения проблем
рекурсия
public ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null)
return list2;
if (list2 == null)
return list1;
if (list1.val <= list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
повторять
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if (list1 != null)
cur.next = list1;
if (list2 != null)
cur.next = list2;
return head.next;
}
26. Подструктура дерева
Описание темы
Идеи решения проблем
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null)
return false;
return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;
if (root1.val != root2.val)
return false;
return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
27. Зеркальное отображение бинарного дерева
Описание темы
Идеи решения проблем
public void Mirror(TreeNode root) {
if (root == null)
return;
swap(root);
Mirror(root.left);
Mirror(root.right);
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
28 Симметричное бинарное дерево
Описание темы
Идеи решения проблем
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.val != t2.val)
return false;
return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}
29. Распечатайте матрицу по часовой стрелке
Описание темы
Следующая матрица печатается по часовой стрелке как: 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
Идеи решения проблем
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> ret = new ArrayList<>();
int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int i = c1; i <= c2; i++)
ret.add(matrix[r1][i]);
for (int i = r1 + 1; i <= r2; i++)
ret.add(matrix[i][c2]);
if (r1 != r2)
for (int i = c2 - 1; i >= c1; i--)
ret.add(matrix[r2][i]);
if (c1 != c2)
for (int i = r2 - 1; i > r1; i--)
ret.add(matrix[i][c1]);
r1++; r2--; c1++; c2--;
}
return ret;
}
30. Стек, содержащий функцию min
Описание темы
Чтобы определить структуру данных стека, реализуйте в этом типе функцию min, которая может получить наименьший элемент стека.
Идеи решения проблем
private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int node) {
dataStack.push(node);
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
31. Последовательность нажатия и выталкивания стека
Описание темы
Введите две целочисленные последовательности. Первая последовательность представляет собой последовательность выталкивания стека. Проверьте, является ли вторая последовательность последовательностью всплывающих окон стека. Предположим, что все числа, помещенные в стек, не равны.
Например, последовательность 1, 2, 3, 4, 5 — это последовательность проталкивания стека, последовательность 4, 5, 3, 2, 1 — это последовательность извлечения, соответствующая последовательности стека, а 4, 3, 5, 1, 2 Это не может быть последовательность выталкивания последовательности нажатия.
Идеи решения проблем
Используйте стек для имитации операций push и pop.
public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {
int n = pushSequence.length;
Stack<Integer> stack = new Stack<>();
for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
stack.push(pushSequence[pushIndex]);
while (popIndex < n && !stack.isEmpty()
&& stack.peek() == popSequence[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
32.1 Печать бинарного дерева сверху вниз
Описание темы
Каждый узел бинарного дерева печатается сверху вниз, а узлы одного уровня печатаются слева направо.
Например, результат следующего обхода уровня двоичного дерева: 1,2,3,4,5,6,7
Идеи решения проблем
Используйте очереди для иерархического обхода.
Нет необходимости использовать две очереди для хранения узлов текущего слоя и узлов следующего слоя соответственно, потому что, когда вы начинаете обход узлов одного слоя, количество узлов в текущей очереди равно количеству узлов текущего слоя, если вы контролируете количество пройденных узлов, можно гарантировать, что на этот раз пройдены все узлы текущего слоя.
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> ret = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode t = queue.poll();
if (t == null)
continue;
ret.add(t.val);
queue.add(t.left);
queue.add(t.right);
}
}
return ret;
}
32.2. Печать двоичного дерева в несколько строк
Описание темы
Почти так же, как выше.
Идеи решения проблем
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null)
continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (list.size() != 0)
ret.add(list);
}
return ret;
}
32.3 Печать бинарного дерева в зигзагообразном порядке
Описание темы
Пожалуйста, реализуйте функцию печати бинарного дерева в виде зигзага, то есть первая строка печатается слева направо, второй слой печатается справа налево, третья строка печатается слева -вправо, а остальные строки печатаются слева направо и так далее.
Идеи решения проблем
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
boolean reverse = false;
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null)
continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (reverse)
Collections.reverse(list);
reverse = !reverse;
if (list.size() != 0)
ret.add(list);
}
return ret;
}
33. Последовательность обхода двоичного дерева поиска в обратном порядке
Описание темы
Введите целочисленный массив, чтобы определить, является ли массив результатом обхода двоичного дерева поиска в обратном порядке. Предположим, что любые два числа входного массива отличны друг от друга.
Например, на следующем рисунке показано двоичное дерево поиска, соответствующее последовательности обхода в обратном порядке 1,3,2.
Идеи решения проблем
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence == null || sequence.length == 0)
return false;
return verify(sequence, 0, sequence.length - 1);
}
private boolean verify(int[] sequence, int first, int last) {
if (last - first <= 1)
return true;
int rootVal = sequence[last];
int cutIndex = first;
while (cutIndex < last && sequence[cutIndex] <= rootVal)
cutIndex++;
for (int i = cutIndex; i < last; i++)
if (sequence[i] < rootVal)
return false;
return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1);
}
34. Путь в бинарном дереве, который суммируется со значением
Описание темы
Введите бинарное дерево и целое число, выведите все пути в бинарном дереве, сумма значений узлов которых является входным целым числом. Путь определяется как путь от корневого узла дерева вниз к узлам, пройденным конечными узлами.
Следующее бинарное дерево имеет два пути, сумма которых равна 22: 10, 5, 7 и 10, 12.
Идеи решения проблем
private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
backtracking(root, target, new ArrayList<>());
return ret;
}
private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
if (node == null)
return;
path.add(node.val);
target -= node.val;
if (target == 0 && node.left == null && node.right == null) {
ret.add(new ArrayList<>(path));
} else {
backtracking(node.left, target, path);
backtracking(node.right, target, path);
}
path.remove(path.size() - 1);
}
35. Репликация сложных связанных списков
Описание темы
Введите сложный связанный список (в каждом узле есть значение узла и два указателя, один указывает на следующий узел, а другой специальный указатель указывает на любой узел), а возвращаемый результат является заголовком сложного связанного списка после репликация.
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
Идеи решения проблем
Первый шаг — вставить повторяющийся узел после каждого узла.
Второй шаг — присвоить значение случайной ссылке узла репликации.
Третий шаг, раскол.
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null)
return null;
// 插入新节点
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode clone = new RandomListNode(cur.label);
clone.next = cur.next;
cur.next = clone;
cur = clone.next;
}
// 建立 random 链接
cur = pHead;
while (cur != null) {
RandomListNode clone = cur.next;
if (cur.random != null)
clone.random = cur.random.next;
cur = clone.next;
}
// 拆分
cur = pHead;
RandomListNode pCloneHead = pHead.next;
while (cur.next != null) {
RandomListNode next = cur.next;
cur.next = next.next;
cur = next;
}
return pCloneHead;
}
36. Двоичное дерево поиска и двусвязный список
Описание темы
Введите двоичное дерево поиска, преобразуйте двоичное дерево поиска в отсортированный двусвязный список. Требуется, чтобы нельзя было создавать новые узлы, а можно было регулировать только точку указателя узла в дереве.
Идеи решения проблем
private TreeNode pre = null;
private TreeNode head = null;
public TreeNode Convert(TreeNode root) {
inOrder(root);
return head;
}
private void inOrder(TreeNode node) {
if (node == null)
return;
inOrder(node.left);
node.left = pre;
if (pre != null)
pre.right = node;
pre = node;
if (head == null)
head = node;
inOrder(node.right);
}
37. Сериализация двоичного дерева
Описание темы
Пожалуйста, реализуйте две функции для сериализации и десериализации бинарных деревьев соответственно.
Идеи решения проблем
private String deserializeStr;
public String Serialize(TreeNode root) {
if (root == null)
return "#";
return root.val + " " + Serialize(root.left) + " " + Serialize(root.right);
}
public TreeNode Deserialize(String str) {
deserializeStr = str;
return Deserialize();
}
private TreeNode Deserialize() {
if (deserializeStr.length() == 0)
return null;
int index = deserializeStr.indexOf(" ");
String node = index == -1 ? deserializeStr : deserializeStr.substring(0, index);
deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);
if (node.equals("#"))
return null;
int val = Integer.valueOf(node);
TreeNode t = new TreeNode(val);
t.left = Deserialize();
t.right = Deserialize();
return t;
}
38. Расположение струн
Описание темы
Введите строку и распечатайте все перестановки символов в строке лексикографически. Например, при вводе строки abc будут напечатаны все строки abc, acb, bac, bca, cab и cba, которые могут быть упорядочены по символам a, b, c.
Идеи решения проблем
private ArrayList<String> ret = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if (str.length() == 0)
return ret;
char[] chars = str.toCharArray();
Arrays.sort(chars);
backtracking(chars, new boolean[chars.length], new StringBuilder());
return ret;
}
private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {
if (s.length() == chars.length) {
ret.add(s.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
if (hasUsed[i])
continue;
if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) /* 保证不重复 */
continue;
hasUsed[i] = true;
s.append(chars[i]);
backtracking(chars, hasUsed, s);
s.deleteCharAt(s.length() - 1);
hasUsed[i] = false;
}
}
39. Числа, встречающиеся в массиве более половины раз
Идеи решения проблем
Для решения проблемы голосования большинством можно использовать алгоритм голосования большинства Бойера-Мура, что делает временную сложность O (N).
Используйте cnt для подсчета количества вхождений элемента.Когда пройденный элемент равен подсчитанному элементу, пусть cnt++, иначе пусть cnt--. Если i элементов просматриваются раньше, и cnt == 0, это означает, что первые i элементы не имеют большинства или имеют большинство, но количество вхождений меньше i/2, потому что если больше i/2, cnt будет не быть 0 . В это время в оставшихся n - i элементах число большинства еще больше, чем (n - i)/2, поэтому продолжайте поиск, чтобы найти большинство.
public int MoreThanHalfNum_Solution(int[] nums) {
int majority = nums[0];
for (int i = 1, cnt = 1; i < nums.length; i++) {
cnt = nums[i] == majority ? cnt + 1 : cnt - 1;
if (cnt == 0) {
majority = nums[i];
cnt = 1;
}
}
int cnt = 0;
for (int val : nums)
if (val == majority)
cnt++;
return cnt > nums.length / 2 ? majority : 0;
}
40. Минимальное число К
Идеи решения проблем
быстрый выбор
- Сложность: O(N) + O(1)
- Может использоваться только в том случае, если разрешена модификация элементов массива.
Метод быстрой сортировки partition() возвращает целое число j, такое что a[l..j-1] меньше или равно a[j], а a[j+1..h] больше или равно a[j], то a [j] — j-й по величине элемент массива. Это свойство можно использовать для поиска K-го элемента массива.Такой алгоритм нахождения K-го элемента называется алгоритмом быстрого выбора.
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
ArrayList<Integer> ret = new ArrayList<>();
if (k > nums.length || k <= 0)
return ret;
findKthSmallest(nums, k - 1);
/* findKthSmallest 会改变数组，使得前 k 个数都是最小的 k 个数 */
for (int i = 0; i < k; i++)
ret.add(nums[i]);
return ret;
}
public void findKthSmallest(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k)
break;
if (j > k)
h = j - 1;
else
l = j + 1;
}
}
private int partition(int[] nums, int l, int h) {
int p = nums[l]; /* 切分元素 */
int i = l, j = h + 1;
while (true) {
while (i != h && nums[++i] < p) ;
while (j != l && nums[--j] > p) ;
if (i >= j)
break;
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
минимальная куча размера K
- Сложность: O(NlogK) + O(K)
- Особенно подходит для обработки массивных данных
Большая верхняя куча должна использоваться для поддержания минимальной кучи вместо непосредственного создания маленькой верхней кучи и установки размера в попытке сделать элементы в маленькой верхней куче самыми маленькими элементами.
Процесс поддержания минимальной кучи размером K выглядит следующим образом: после добавления элемента, если размер большой верхней кучи больше K, то необходимо удалить верхний элемент большой верхней кучи.
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
if (k > nums.length || k <= 0)
return new ArrayList<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int num : nums) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
return new ArrayList<>(maxHeap);
}
41.1 Медиана в потоках данных
Описание темы
Как получить медиану в потоке данных? Если из потока данных считывается нечетное количество значений, то медианой является значение в середине после того, как все значения отсортированы. Если из потока данных считывается четное количество значений, то медиана — это среднее двух средних чисел после сортировки всех значений.
Идеи решения проблем
/* 大顶堆，存储左半边元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 当前数据流读入的元素个数 */
private int N = 0;
public void Insert(Integer val) {
/* 插入要保证两个堆存于平衡状态 */
if (N % 2 == 0) {
/* N 为偶数的情况下插入到右半边。
* 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
* 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
41.2 Первый уникальный символ в потоке символов
Описание темы
Пожалуйста, реализуйте функцию для поиска первого единичного символа в потоке символов. Например, когда из потока символов считываются только первые два символа «go», первым символом, который встречается только один раз, является «g». Когда первые шесть символов «google» считываются из этого потока символов, первый символ, который встречается только один раз, — «l».
Идеи решения проблем
private int[] cnts = new int[256];
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch) {
cnts[ch]++;
queue.add(ch);
while (!queue.isEmpty() && cnts[queue.peek()] > 1)
queue.poll();
}
public char FirstAppearingOnce() {
return queue.isEmpty() ? '#' : queue.peek();
}
42. Максимальная сумма смежных подмассивов.
Описание темы
{6, -3, -2, 7, -15, 1, 2, 2}, максимальная сумма последовательных подмассивов равна 8 (начиная с 0-го и заканчивая 3-м).
Идеи решения проблем
public int FindGreatestSumOfSubArray(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int greatestSum = Integer.MIN_VALUE;
int sum = 0;
for (int val : nums) {
sum = sum <= 0 ? val : sum + val;
greatestSum = Math.max(greatestSum, sum);
}
return greatestSum;
}
43. Встречаемость 1 в целых числах от 1 до n
Идеи решения проблем
public int NumberOf1Between1AndN_Solution(int n) {
int cnt = 0;
for (int m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
}
return cnt;
}
44. Цифра в последовательности чисел
Описание темы
Номер сериализуется в строку в формате 0123456789101112131415... и находится порядковый номер строки.
Идеи решения проблем
public int getDigitAtIndex(int index) {
if (index < 0)
return -1;
int place = 1; // 1 表示个位，2 表示 十位...
while (true) {
int amount = getAmountOfPlace(place);
int totalAmount = amount * place;
if (index < totalAmount)
return getDigitAtIndex(index, place);
index -= totalAmount;
place++;
}
}
/**
* place 位数的数字组成的字符串长度
* 10, 90, 900, ...
*/
private int getAmountOfPlace(int place) {
if (place == 1)
return 10;
return (int) Math.pow(10, place - 1) * 9;
}
/**
* place 位数的起始数字
* 0, 10, 100, ...
*/
private int getBeginNumberOfPlace(int place) {
if (place == 1)
return 0;
return (int) Math.pow(10, place - 1);
}
/**
* 在 place 位数组成的字符串中，第 index 个数
*/
private int getDigitAtIndex(int index, int place) {
int beginNumber = getBeginNumberOfPlace(place);
int shiftNumber = index / place;
String number = (beginNumber + shiftNumber) + "";
int count = index % place;
return number.charAt(count) - '0';
}
45. Упорядочить массив до наименьшего числа
Описание темы
Введите массив положительных целых чисел, объедините все числа в массиве в число и выведите наименьшее из всех чисел, которые можно объединить. Например, если массив равен {3, 32, 321}, наименьшее число, которое можно составить из этих трех чисел, равно 321323.
Идеи решения проблем
Это можно рассматривать как задачу сортировки.При сравнении размера двух строк S1 и S2 следует сравнивать размер строк S1+S2 и S2+S1.Если S1+S2
public String PrintMinNumber(int[] numbers) {
if (numbers == null || numbers.length == 0)
return "";
int n = numbers.length;
String[] nums = new String[n];
for (int i = 0; i < n; i++)
nums[i] = numbers[i] + "";
Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
String ret = "";
for (String str : nums)
ret += str;
return ret;
}
46. Перевести числа в строки
Описание темы
Получив число, переведите его в строку по следующим правилам: 1 переводится в «a», 2 переводится в «b»... 26 переводится в «z». Есть много возможных переводов для числа, например, 12258 имеет всего 5 видов, а именно аббех, лбех, авех, абых, лых. Реализуйте функцию, которая подсчитывает, сколько различных методов перевода имеет число.
Идеи решения проблем
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0)
dp[i] += dp[i - 1];
if (s.charAt(i - 2) == '0')
continue;
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26)
dp[i] += dp[i - 2];
}
return dp[n];
}
47. Максимальная стоимость подарков
Описание темы
На каждой клетке шахматной доски m*n есть подарок, и каждый подарок имеет определенное значение (больше 0). Начинайте брать подарки с верхнего левого угла и перемещайтесь на одну клетку вправо или вниз за раз, пока нижний правый угол не закончится. Учитывая шахматную доску, найдите максимальную стоимость подарка. Например, для следующей шахматной доски
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
Максимальная стоимость подарка 1+12+5+7+7+16+5=53.
Идеи решения проблем
Следует использовать динамическое программирование вместо поиска в глубину, который слишком сложен и не оптимален.
public int getMost(int[][] values) {
if (values == null || values.length == 0 || values[0].length == 0)
return 0;
int n = values[0].length;
int[] dp = new int[n];
for (int[] value : values) {
dp[0] += value[0];
for (int i = 1; i < n; i++)
dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
}
return dp[n - 1];
}
48. Самая длинная подстрока без повторяющихся символов
Описание темы
Введите строку (содержащую только символы a~z), найдите длину самой длинной подстроки без повторяющихся символов. Например, для arabcacfr самая длинная подстрока без повторяющихся символов — это acfr длиной 4.
Идеи решения проблем
public int longestSubStringWithoutDuplication(String str) {
int curLen = 0;
int maxLen = 0;
int[] preIndexs = new int[26];
Arrays.fill(preIndexs, -1);
for (int curI = 0; curI < str.length(); curI++) {
int c = str.charAt(curI) - 'a';
int preI = preIndexs[c];
if (preI == -1 || curI - preI > curLen) {
curLen++;
} else {
maxLen = Math.max(maxLen, curLen);
curLen = curI - preI;
}
preIndexs[c] = curI;
}
maxLen = Math.max(maxLen, curLen);
return maxLen;
}
49. Уродливые числа
Описание темы
Число, содержащее только делители 2, 3 и 5, называется уродливым числом. Например, 6 и 8 — уродливые числа, а 14 — не потому, что содержит множитель 7. По соглашению мы относимся к 1 как к первому уродливому числу. Найдите N-е некрасивое число в порядке возрастания.
Идеи решения проблем
public int GetUglyNumber_Solution(int N) {
if (N <= 6)
return N;
int i2 = 0, i3 = 0, i5 = 0;
int[] dp = new int[N];
dp[0] = 1;
for (int i = 1; i < N; i++) {
int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2)
i2++;
if (dp[i] == next3)
i3++;
if (dp[i] == next5)
i5++;
}
return dp[N - 1];
}
50. Первая позиция символа, которая встречается только один раз
Описание темы
Находит первый символ, который встречается в строке только один раз, и возвращает его позицию.
Input: abacc
Output: b
Идеи решения проблем
Наиболее интуитивно понятным решением является использование HashMap для подсчета количества вхождений, но, учитывая ограниченный диапазон подсчитываемых символов, вместо HashMap можно использовать целочисленный массив, тем самым уменьшая пространственную сложность с O(N) до O(1). ).
public int FirstNotRepeatingChar(String str) {
int[] cnts = new int[256];
for (int i = 0; i < str.length(); i++)
cnts[str.charAt(i)]++;
for (int i = 0; i < str.length(); i++)
if (cnts[str.charAt(i)] == 1)
return i;
return -1;
}
Объемная сложность приведенной выше реализации еще не оптимальна. Учитывая, что вам нужно найти только символы, которые появляются только один раз, то количество раз, которое необходимо подсчитать, составляет только 0, 1 и больше, и эта информация может храниться с использованием двух битов.
public int FirstNotRepeatingChar2(String str) {
BitSet bs1 = new BitSet(256);
BitSet bs2 = new BitSet(256);
for (char c : str.toCharArray()) {
if (!bs1.get(c) && !bs2.get(c))
bs1.set(c); // 0 0 -> 0 1
else if (bs1.get(c) && !bs2.get(c))
bs2.set(c); // 0 1 -> 1 1
}
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (bs1.get(c) && !bs2.get(c)) // 0 1
return i;
}
return -1;
}
51. Обратные пары в массивах
Описание темы
Два числа в массиве, если первое число больше второго, два числа образуют обратную пару. Учитывая массив, найдите общее количество обратных пар в массиве.
Идеи решения проблем
private long cnt = 0;
private int[] tmp; // 在这里声明辅助数组，而不是在 merge() 递归函数中声明
public int InversePairs(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return (int) (cnt % 1000000007);
}
private void mergeSort(int[] nums, int l, int h) {
if (h - l < 1)
return;
int m = l + (h - l) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, h);
merge(nums, l, m, h);
}
private void merge(int[] nums, int l, int m, int h) {
int i = l, j = m + 1, k = l;
while (i <= m || j <= h) {
if (i > m)
tmp[k] = nums[j++];
else if (j > h)
tmp[k] = nums[i++];
else if (nums[i] <= nums[j])
tmp[k] = nums[i++];
else {
tmp[k] = nums[j++];
this.cnt += m - i + 1; // nums[i] > nums[j]，说明 nums[i...mid] 都大于 nums[j]
}
k++;
}
for (k = l; k <= h; k++)
nums[k] = tmp[k];
}
52. Первый общий узел двух связанных списков
Описание темы
Идеи решения проблем
Пусть длина A равна a + c, а длина B равна b + c, где c — длина общей части хвоста, мы знаем, что a + c + b = b + c + a.
Когда указатель доступа к связанному списку A получает доступ к концу связанного списка, пусть он начнет доступ к связанному списку B с начала связанного списка B; аналогично, когда указатель доступа к связанному списку B обращается к концу связанного списка, пусть он перезапустится с начало связанного списка A Начать доступ к связанному списку A. Таким образом, указатели, обращающиеся к двум связанным спискам A и B, могут контролироваться для одновременного доступа к пересечению.
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while (l1 != l2) {
l1 = (l1 == null) ? pHead2 : l1.next;
l2 = (l2 == null) ? pHead1 : l2.next;
}
return l1;
}
53. Сколько раз число встречается в отсортированном массиве.
Описание темы
Input:
nums = 1, 2, 3, 3, 3, 3, 4, 6
K = 3
Output:
4
Идеи решения проблем
public int GetNumberOfK(int[] nums, int K) {
int first = binarySearch(nums, K);
int last = binarySearch(nums, K + 1);
return (first == nums.length || nums[first] != K) ? 0 : last - first;
}
private int binarySearch(int[] nums, int K) {
int l = 0, h = nums.length;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= K)
h = m;
else
l = m + 1;
}
return l;
}
54. K-й узел бинарного дерева поиска.
Идеи решения проблем
Воспользуйтесь упорядоченным порядком обхода бинарного дерева поиска.
private TreeNode ret;
private int cnt = 0;
public TreeNode KthNode(TreeNode pRoot, int k) {
inOrder(pRoot, k);
return ret;
}
private void inOrder(TreeNode root, int k) {
if (root == null || cnt >= k)
return;
inOrder(root.left, k);
cnt++;
if (cnt == k)
ret = root;
inOrder(root.right, k);
}
55.1. Глубина бинарных деревьев
Описание темы
Узлы (включая корневой и конечный узлы), которые последовательно проходят от корневого узла к листовому узлу, образуют путь дерева, а длина самого длинного пути является глубиной дерева.
Идеи решения проблем
public int TreeDepth(TreeNode root) {
return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}
55.2 Сбалансированные бинарные деревья
Описание темы
Разница высот между левым и правым поддеревьями сбалансированного бинарного дерева не превышает 1.
Идеи решения проблем
private boolean isBalanced = true;
public boolean IsBalanced_Solution(TreeNode root) {
height(root);
return isBalanced;
}
private int height(TreeNode root) {
if (root == null || !isBalanced)
return 0;
int left = height(root.left);
int right = height(root.right);
if (Math.abs(left - right) > 1)
isBalanced = false;
return 1 + Math.max(left, right);
}
56. Числа, встречающиеся в массиве только один раз
Описание темы
За исключением двух чисел в массиве целых чисел, все остальные числа встречаются дважды, найдите эти два числа.
Идеи решения проблем
Два неравных элемента должны иметь битовое представление, там разные результаты всех элементов массива по исключающему ИЛИ, полученному путем повторения двух элементов исключающего ИЛИ, результата нет.
diff &= -diff, чтобы получить самый правый бит diff, который не равен 0, то есть самый правый бит, который отличается в представлении на уровне битов двух элементов, не имеющих дубликатов. Используя этот бит, два элемента могут быть преобразованным дифференцировать.
public void FindNumsAppearOnce(int[] nums, int num1[], int num2[]) {
int diff = 0;
for (int num : nums)
diff ^= num;
diff &= -diff;
for (int num : nums) {
if ((num & diff) == 0)
num1[0] ^= num;
else
num2[0] ^= num;
}
}
57.1 и два числа для S
Описание темы
Дан массив, отсортированный в порядке возрастания, и число S, найдите в массиве два числа, сумма которых равна ровно S. Если сумма нескольких пар чисел равна S, выведите наименьшее произведение двух чисел.
Идеи решения проблем
С двойными указателями один указатель указывает на значение с меньшим элементом, а другой указатель указывает на значение с большим элементом. Указатели на меньшие элементы проходятся от головы к хвосту, а указатели на более крупные элементы проходятся от хвоста к голове.
- Если сумма двух указателей на элементы sum == target, то будет получен требуемый результат;
- Если сумма > цель, переместите более крупные элементы, чтобы сумма стала меньше;
- Если сумма
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
int i = 0, j = array.length - 1;
while (i < j) {
int cur = array[i] + array[j];
if (cur == sum)
return new ArrayList<>(Arrays.asList(array[i], array[j]));
if (cur < sum)
i++;
else
j--;
}
return new ArrayList<>();
}
57.2 Последовательности последовательных положительных чисел, сумма которых равна S
Описание темы
Выведите все последовательности последовательных положительных чисел, сумма которых равна S.
Например, непрерывная последовательность, сумма которой равна 100:
[9, 10, 11, 12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]。
Идеи решения проблем
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
int start = 1, end = 2;
int curSum = 3;
while (end < sum) {
if (curSum > sum) {
curSum -= start;
start++;
} else if (curSum < sum) {
end++;
curSum += end;
} else {
ArrayList<Integer> list = new ArrayList<>();
for (int i = start; i <= end; i++)
list.add(i);
ret.add(list);
curSum -= start;
start++;
end++;
curSum += end;
}
}
return ret;
}
58.1 Перевернуть столбцы порядка слов
Описание темы
Input:
"I am a student."
Output:
"student. a am I"
Идеи решения проблем
В заголовке должно быть неявное условие, запрещающее использование лишнего пробела. Хотя входным параметром заголовка Java является тип String, вам необходимо сначала создать массив символов, чтобы сложность пространства была O (N), но правильный тип параметра должен быть таким же, как исходная книга, которая представляет собой массив символов, и можно использовать только пространство массива символов. Любое решение, использующее дополнительное пространство, будет сильно обесценено на собеседованиях, включая рекурсивные решения.
Правильное решение должно быть таким, как в книге, сначала повернуть каждое слово, а затем повернуть всю строку.
public String ReverseSentence(String str) {
int n = str.length();
char[] chars = str.toCharArray();
int i = 0, j = 0;
while (j <= n) {
if (j == n || chars[j] == ' ') {
reverse(chars, i, j - 1);
i = j + 1;
}
j++;
}
reverse(chars, 0, n - 1);
return new String(chars);
}
private void reverse(char[] c, int i, int j) {
while (i < j)
swap(c, i++, j--);
}
private void swap(char[] c, int i, int j) {
char t = c[i];
c[i] = c[j];
c[j] = t;
}
58.2 Вращение строки влево
Описание темы
Input:
S="abcXYZdef"
K=3
Output:
"XYZdefabc"
Идеи решения проблем
Переверните «abc» и «XYZdef» отдельно, чтобы получить «cbafedZYX», а затем переверните всю строку, чтобы получить «XYZdefabc».
public String LeftRotateString(String str, int n) {
if (n >= str.length())
return str;
char[] chars = str.toCharArray();
reverse(chars, 0, n - 1);
reverse(chars, n, chars.length - 1);
reverse(chars, 0, chars.length - 1);
return new String(chars);
}
private void reverse(char[] chars, int i, int j) {
while (i < j)
swap(chars, i++, j--);
}
private void swap(char[] chars, int i, int j) {
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}
59. Максимальное значение скользящего окна
Описание темы
Учитывая массив и размер скользящего окна, найдите максимальное значение всех значений в скользящем окне.
Например, если входной массив равен {2, 3, 4, 2, 6, 2, 5, 1}, а размер скользящего окна равен 3, то имеется 6 скользящих окон, и их максимальные значения равны { 4, 4, 6, 6, 6, 5}.
Идеи решения проблем
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ret = new ArrayList<>();
if (size > num.length || size < 1)
return ret;
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 大顶堆 */
for (int i = 0; i < size; i++)
heap.add(num[i]);
ret.add(heap.peek());
for (int i = 0, j = i + size; j < num.length; i++, j++) { /* 维护一个大小为 size 的大顶堆 */
heap.remove(num[i]);
heap.add(num[j]);
ret.add(heap.peek());
}
return ret;
}
60. Очки n игральных костей
Описание темы
Найдите вероятность того, что сумма очков, выпавших на n кубиках, будет равна s.
Идеи решения проблем
динамическое программирование
Используйте двумерный массив dp для хранения количества вхождений точки, где dp[i][j] представляет количество раз, когда первая игральная кость i произвела точку j.
Пространственная сложность: O(N2)
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int face = 6;
final int pointNum = face * n;
long[][] dp = new long[n + 1][pointNum + 1];
for (int i = 1; i <= face; i++)
dp[1][i] = 1;
for (int i = 2; i <= n; i++)
for (int j = i; j <= pointNum; j++) /* 使用 i 个骰子最小点数为 i */
for (int k = 1; k <= face && k <= j; k++)
dp[i][j] += dp[i - 1][j - k];
final double totalNum = Math.pow(6, n);
List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
for (int i = n; i <= pointNum; i++)
ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));
return ret;
}
Динамическое программирование + вращающиеся массивы
Пространственная сложность: O(N)
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int face = 6;
final int pointNum = face * n;
long[][] dp = new long[2][pointNum + 1];
for (int i = 1; i <= face; i++)
dp[0][i] = 1;
int flag = 1; /* 旋转标记 */
for (int i = 2; i <= n; i++, flag = 1 - flag) {
for (int j = 0; j <= pointNum; j++)
dp[flag][j] = 0; /* 旋转数组清零 */
for (int j = i; j <= pointNum; j++)
for (int k = 1; k <= face && k <= j; k++)
dp[flag][j] += dp[1 - flag][j - k];
}
final double totalNum = Math.pow(6, n);
List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
for (int i = n; i <= pointNum; i++)
ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));
return ret;
}
61. Покер Стрейт
Описание темы
Пять карт, из которых большой и маленький призраки — проказы, а лицевая сторона карты — 0. Определите, могут ли эти пять карт составить стрит.
Идеи решения проблем
public boolean isContinuous(int[] nums) {
if (nums.length < 5)
return false;
Arrays.sort(nums);
// 统计癞子数量
int cnt = 0;
for (int num : nums)
if (num == 0)
cnt++;
// 使用癞子去补全不连续的顺子
for (int i = cnt; i < nums.length - 1; i++) {
if (nums[i + 1] == nums[i])
return false;
cnt -= nums[i + 1] - nums[i] - 1;
}
return cnt >= 0;
}
62. Последнее число, оставшееся в круге
Описание темы
Пусть дети образуют большой круг. Затем случайным образом назначьте число m и позвольте ребенку с номером 0 начать считать. Каждый раз, когда ребенок, который кричит т-1, будет выходить петь песенку, а затем он может выбрать любой подарок из подарочной коробки, и не будет возвращаться в круг, начиная со следующего ребенка, и продолжать 0...т -1 счет.... и так далее.... пока не останется последний ребенок, выполнять не надо.
Идеи решения проблем
Джозефа, решение длины окружности n можно рассматривать как решение длины n-1 плюс длина m числа отчетов. Поскольку это круг, вам нужно взять остаток n в конце.
public int LastRemaining_Solution(int n, int m) {
if (n == 0) /* 特殊输入的处理 */
return -1;
if (n == 1) /* 递归返回条件 */
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
63. Максимальная прибыль по акциям
Описание темы
Может быть одна покупка и одна продажа, покупка должна быть первой. Стремитесь к максимальной прибыли.
Идеи решения проблем
Используя жадную стратегию, предполагая, что операция продажи выполняется в i-м раунде, цена операции покупки должна быть раньше i и цена должна быть самой низкой.
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int soFarMin = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
soFarMin = Math.min(soFarMin, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
}
return maxProfit;
}
64. Найдите 1+2+3+...+n
Описание темы
Требуется, чтобы такие ключевые слова, как умножение и деление, for, while, if, else, switch, case и условные операторы суждения A ? B : C не могли использоваться.
Идеи решения проблем
Самое важное в использовании рекурсивного решения — указать условие возврата, но в этом вопросе нельзя напрямую использовать оператор if для указания условия возврата.
Условные операторы и операторы && имеют принцип короткого замыкания, то есть второй условный оператор не будет выполнен, если первый условный оператор ложен. Используя эту функцию, рекурсивное условие возврата отрицается и затем используется как первый условный оператор &&, а тело рекурсии преобразуется во второй условный оператор, затем, когда условие рекурсивного возврата истинно, рекурсивный не будет выполняться. часть тела, рекурсивно возвращается.
Условие рекурсивного возврата этого вопроса: n 0 после отрицания; основная часть рекурсии — это sum += Sum_Solution(n - 1), которая преобразуется в условный оператор (sum += Sum_Solution( п - 1) ) > 0.
public int Sum_Solution(int n) {
int sum = n;
boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0);
return sum;
}
65. Складывать без добавления, вычитания, умножения и деления
Описание темы
Напишите функцию для нахождения суммы двух целых чисел, при этом не требуется использовать четыре арифметических символа +, -, *, /.
Идеи решения проблем
a ^ b означает сумму двух чисел без учета переноса, (a & b)
Причина, по которой рекурсия завершится, заключается в том, что (a & b)
public int Add(int a, int b) {
return b == 0 ? a : Add(a ^ b, (a & b) << 1);
}
66. Создайте ассортимент продуктов
Описание темы
Учитывая массив A[0, 1,..., n-1], создайте массив B[0, 1,..., n-1], где элемент B[i]=A[0]*A[1 ]*...*A[i-1]*A[i+1]*...*A[n-1]. Требует, чтобы деление не могло быть использовано.
Идеи решения проблем
public int[] multiply(int[] A) {
int n = A.length;
int[] B = new int[n];
for (int i = 0, product = 1; i < n; product *= A[i], i++) /* 从左往右累乘 */
B[i] = product;
for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--) /* 从右往左累乘 */
B[i] *= product;
return B;
}
67. Преобразование строки в целое число
Описание темы
Преобразует строку в целое число и возвращает 0, если строка не является допустимым числом, что требует библиотечных функций, которые не могут использовать строки для преобразования целых чисел.
Iuput:
+2147483647
1a33
Output:
2147483647
0
Идеи решения проблем
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (i == 0 && (c == '+' || c == '-')) /* 符号判定 */
continue;
if (c < '0' || c > '9') /* 非法输入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
68. Наименьший общий предок двух узлов в дереве.
Идеи решения проблем
бинарное дерево поиска
Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree
В двоичном дереве поиска общий корень-предок двух узлов p, q удовлетворяет условию root.val >= p.val && root.val
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}
обычное бинарное дерево
Leetcode : 236. Lowest Common Ancestor of a Binary Tree
Найдите, существует ли p или q в левом и правом поддеревьях.Если p и q находятся в двух поддеревьях соответственно, то корневой узел является младшим общим предком.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}