предисловие
Во-первых, этоопросизпроблема алгоритма, темы в основном выбираются изleetcode
серединаhot 100 | 腾讯精选50题 | 精选Top面试题 | 剑指offer | 面试中遇到的一些算法题
,полный текст122Вопросы в основном охватывают классификацию алгоритмических вопросов в предварительных интервью. Из-за ограниченных способностей человека титул почтиeasy | mid
И провести несколько отличных проверок均在参考文献中
. если это поможет тебеНажмите 👍 и добавьте в избранное ❤️
содержание
- dp
- жадный
- две точки
- отступление
- Сортировать
- и проверить
- топологическая сортировка
- битовая операция
- двойной указатель
- матрица
- бинарное дерево
- хеш-таблица
- Стеки и очереди
- связанный список
- нить
dp
Мысль
Это очень похоже на идею школьной последовательности, дающей первый член, и рекурсивной формулы, позволяющей найти значение любого члена.
Шаги в основном таковы: найдите уравнение перехода состояния => создайте подходящую таблицу структуры данных => заполните таблицу
подниматься по лестнице
Предположим, вы поднимаетесь по лестнице. нужноnшаги, чтобы достичь вершины.
Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания?
dp[0] = 0 dp[1] = 1 dp[2] = 2
dp[n] = dp[n-1] + dp[n-2] // 到达第n阶楼梯有从n-1阶走一步和从第n-2阶走两步两种情况
var climbStairs = function(n) {
let dp = [];
dp[0] = 0,dp[1] = 1,dp[2] = 2;
for(let i = 3;i <= n;i++){
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n];
};
ограбление
Вы профессиональный вор, планирующий украсть дома вдоль улицы. В каждой комнате спрятана определенная сумма денег.Единственное ограничение, влияющее на вашу кражу, это то, что соседние дома оборудованы взаимосвязанными противоугонными системами.Если воры взломают два соседних дома в одну и ту же ночь, система сработает. автоматическая сигнализация.
Учитывая массив неотрицательных целых чисел, представляющих сумму, хранящуюся в каждом доме, вычислите максимальную сумму, которую вы можете украсть, не активировав тревогу.
// 动态规划方程:dp[n] = num + Max(dp[n-1])
// 由于不可以在相邻的房屋闯入,所以在当前位置 n 房屋可盗窃的最大值,要么就是 n-1 房屋可盗窃的最大值,要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值,二者之间取最大值
// 举例来说:1 号房间可盗窃最大值为 33 即为 dp[1]=3,2 号房间可盗窃最大值为 44 即为 dp[2]=4,3 号房间自身的值为 22 即为 num=2,那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5,3 号房间可盗窃最大值为 55
var rob = function(nums) {
if(nums.length === 0) return 0;
if(nums.length === 1) return nums[0];
if(nums.length === 2) return Math.max(nums[0],nums[1]);
let dp = [nums[0],Math.max(nums[0],nums[1])];
for(let i = 2;i < nums.length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return Math.max(dp[nums.length-1],dp[nums.length-2]);
};
самая большая площадь
В двумерной матрице, состоящей из 0 и 1, чтобы найти максимальный квадрат содержит только 1 и возвращает область
const maximalSquare = (matrix) => {
if (!matrix.length) return 0
let maxsqlen = 0
let rowLength = matrix.length, colLength = matrix[0].length
for (let row = 0; row < rowLength; row++) {
for (let col = 0; col < colLength; col++) {
if (matrix[row][col] === '1') {
matrix[row][col] = Number(matrix[row][col])
if (row != 0 && col != 0) {
matrix[row][col] = Math.min(matrix[row-1][col], matrix[row-1][col-1], matrix[row][col-1]) + 1
}
maxsqlen = Math.max(maxsqlen, matrix[row][col])
}
}
}
return maxsqlen**2
}
/** DP
* 题目要求最大正方形面积,面积 = 边长 * 边长,也就是求最大正方形的边长
* 所以也就变成了,在矩阵中找最大正方形,矩阵中只有0|1两种值,全部为1的才是正方形
* 如何知道矩阵中哪里是1,哪里是0,只能穷举,但要聪明的穷举,这不就是动态规划的本质嘛!
* 动态规划第一步,先假象我们创建了一个二维数组dp,用来存储「这个点为右下角的最大正方形的边长」
* 下面开始找 状态转换方程
* 思路:假设有如下矩阵
* 1 0 1 1 1
* 1 1 1 1 1
* 1 1 1 1 1
* 1 0 0 1 1
* 随便找一个点,直观地,我们先找最右下角的点,设该点的最大正方形边长为 dp[i][j], 我们用肉眼看一下,dp[i][j] 应该等于 2
* 为什么等于2,是因为我们看了 dp[i-1][j], dp[i-1][j-1], dp[i][j-1] 这三个点都为1,而又因为dp[i][j-2] 为0,所以
* 我们知道dp[i][j]最大就为2了。也就是我们不能只看dp[i][j]相邻的三个点,而应该看「这三个相邻点为正方形右下角」的边长情况,
* 取最小边长进行求解 dp[i][j] 的最大正方形边长。(看,我们找到了重叠子问题和最优子结构)
* 所以,状态转换方程为:dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
* 下一步,需要根据矩阵数据,进行选择和明确 base case 即可
*/
Изменить обмен
Даны монеты разного номинала и общая сумма. Напишите функцию для вычисления минимального количества монет, необходимого для получения общей суммы. Возвращает -1, если ни одна из комбинаций монет не составляет общую сумму.
// dp[0] = 0 金额为零时不需要硬币
// dp[n] = min(dp[n],dp[n-coin1] + 1,dp[n-coin2],...) 金额为n时,硬币数等于(n-coin)+1中所需硬币最少的组合
var coinChange = function(coins, amount) {
let dp = new Array( amount + 1 ).fill( Infinity );
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
разные пути
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
спросите, сколько всего существует различных путей
var uniquePaths = function(m, n) {
if(m === 1 && n === 1) return 1;
let data = [],rows = [0];
for(let i = 0;i < n-1;i++){
rows.push(1);
}
data.push(rows);
for(let i = 0;i < m-1;i++){
data.push([1]);
}
for(let i = 1;i < m;i++){
for(let j = 1;j < n;j++){
data[i][j] = data[i-1][j] + data[i][j-1];
}
}
return data[m-1][n-1];
};
Проблема со стандартным конечным автоматом
Эта статья расскажет вам об этой раме, а затем возьмет вас за шип.
Эти 6 задач торговли акциями имеют общие черты, и мы решаем их одну за другой посредством анализа четвертой задачи (ограничение максимального количества сделок до k). Поскольку четвертый вопрос является наиболее обобщенной формой, все остальные вопросы являются упрощениями этой формы.
Первый вопрос — только одна транзакция, что эквивалентно k = 1; второй вопрос — неограниченное количество транзакций, что эквивалентно k = +бесконечности (положительная бесконечность); третий вопрос — только 2 транзакции, что эквивалентно k = 2 ; Остальные два тоже неограниченное количество раз, но с дополнительными условиями «периода заморозки» и «платы за обработку» для транзакций, они фактически являются вариантами второго вопроса, и с ними легко справиться.
1. Исчерпывающая основа
Прежде всего, та же мысль: как исчерпывающе? Исчерпывающая идея здесь отличается от рекурсивной идеи в предыдущей статье.
Рекурсия на самом деле соответствует логике нашего мышления, продвигается пошагово, если не решается, отбрасывается в рекурсию, делается случайно, читабельность очень хорошая. Недостатком является то, что если что-то пойдет не так, найти причину ошибки будет непросто. Например, рекурсивное решение в предыдущей статье должно иметь вычислительную избыточность, но найти его действительно непросто.
Здесь нам не нужно рекордировать мышление, но использовать «государство» для выхлопа. Мы специально идем к каждому дню, посмотрите на все возможное «состояние», затем найдите «выбор», соответствующего каждому «государству». Мы должны исчерпать все «состояние», цель истощения состоит в том, чтобы обновить состояние в соответствии с соответствующим «выбором». Перечисленные Аннотация, просто помните «Государство» и «Выбор» два слова, это легко понять ниже.
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)
Например, эта проблема,Каждый день есть три «выбора»: покупка, продажа, без операции, мы используем покупку, продажу, отдых для представления этих трех вариантов. Но проблема в том, что не каждый день можно произвольно выбирать эти три варианта, потому что продавать нужно после покупки, а покупать после продажи. Тогда оставшаяся операция также должна быть разделена на два состояния, одно — это отдых после покупки (удержание акции), а другое — это отдых после продажи (акции не удерживаются). И не забывайте, у нас также есть ограничение на количество транзакций k, что означает, что ваша покупка может быть осуществлена только при условии, что k > 0.
Это очень сложно, не так ли? Не бойтесь. Наша цель сейчас - перечислить их все. Неважно, сколько у вас состояний, что должен сделать этот старик, так это перечислить их все.Есть три «состояния» этой проблемы, первое — количество дней, второе — максимально допустимое количество транзакций, а третье — текущее состояние удержания (т. держа). Затем мы можем использовать трехмерный массив для хранения всех комбинаций этих состояний:
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数,大 K 为最多交易数
此问题共 n × K × 2 种状态,全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
И мы можем описать значение каждого состояния на естественном языке, напримерdp[3][2][1]
Смысл такой: Сегодня третий день, я сейчас держу акции в руках, и пока совершил до 2-х сделок. Другой примерdp[2][3][0]
Значение: Сегодня второй день, в данный момент у меня нет акций, и я совершил до 3 сделок. Это легко понять, правда?
Окончательный ответ, который мы хотим найти, это dp[n - 1][K][0], что является максимальной прибылью, допустимой для K сделок в последний день. Читатель может спросить, почему не dp[n - 1][K][1]? Поскольку [1] означает, что акции все еще в наличии, а [0] означает, что акции в продаже проданы, очевидно, что прибыль последнего должна быть больше, чем прибыль первого.
Помните, как интерпретировать «состояние», когда вы чувствуете, что что-то трудно понять, это легко понять, переведя это на естественный язык.
Во-вторых, государственная трансфертная система
Теперь, когда мы завершили исчерпание «состояний», мы начинаем думать о том, какие «варианты» доступны для каждого «состояния» и как обновить «состояния». Просто взглянув на «состояние удержания», вы можете нарисовать диаграмму перехода состояний.
Из этой диаграммы ясно, как происходит переход из каждого состояния (0 и 1). По этой диаграмме запишем уравнение перехода состояний:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 选择 rest , 选择 sell )
解释:今天我没有持有股票,有两种可能:
要么是我昨天就没有持有,然后今天选择 rest,所以我今天还是没有持有;
要么是我昨天持有股票,但是今天我 sell 了,所以我今天没有持有股票了。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 选择 rest , 选择 buy )
解释:今天我持有着股票,有两种可能:
要么我昨天就持有着股票,然后今天选择 rest,所以我今天还持有着股票;
要么我昨天本没有持有,但今天我选择 buy,所以今天我就持有股票了。
Это объяснение должно быть очень ясным. Если вы покупаете, вы должны вычесть цену[i] из прибыли.Если вы продаете, вы должны добавить цену[i] к прибыли. Самая большая прибыль сегодня – это больший из двух возможных вариантов. И обратите внимание на ограничение к. Когда мы выбираем купить, мы уменьшаем к на 1, что легко понять.Конечно, вы можете уменьшить 1 и при продаже, то же самое.
Мы завершили самый сложный шаг в динамическом программировании: уравнение перехода состояния.Если вы можете понять предыдущий контент, то вы можете убить все проблемы за секунды, пока вы устанавливаете этот фреймворк.. Но есть еще один последний момент, который заключается в определении базового случая, который является самым простым случаем.
Если вам разрешено совершить не более одной сделки (т. е. купить и продать акции один раз), разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить.
var maxProfit = function(prices) {
let dp_i_0 = 0,dp_i_1 = -Infinity;
for(let i = 0;i < prices.length;i++){
dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1 = Math.max(dp_i_1,-prices[i]);
}
return dp_i_0;
};
Лучшее время для покупки и продажи акций II
1. 只要股票价格上涨,上涨的部分就是我的利润,可以理解为上涨期间第一天买入,然后一直持有到上涨最后一天即下跌前一天再卖出
2. 只要股票价格下跌,那我肯定在下跌前一天卖了,而且下跌期间永远不会买入
var maxProfit = function(prices) {
let profit = 0;
for (let i = 0; i < prices.length - 1; i++) {
if (prices[i + 1] > prices[i]) profit += prices[i + 1] - prices[i];
}
return profit;
};
жадный
Мысль
При решении проблемы всегда делайте то, что кажется лучшим выбором в данный момент. То есть вместо того, чтобы рассматривать общую оптимальность, он сделал локальное оптимальное решение в определенном смысле.
отрезать веревку
Дайте вам веревку длины n, разрежьте ее на m отрезков целочисленной длины (m, n — целые числа, n>1 и m>1), длина каждой веревки записывается как k[0],k[1 ]...к[м] . спроси у [0]k[1]Каково наибольшее возможное произведение ...*k[m]? Например, когда длина веревки равна 8, мы разрезаем ее на три отрезка длины 2, 3 и 3, и максимальное произведение, полученное в это время, равно 18.
var cuttingRope = function(number) {
if(number === 2 || number === 3) return number - 1;
let a = number % 3;
let b = parseInt(number / 3);
if(a === 0){
return 3 ** b;
}else if(a === 1){
return 2 * 2 * (3 ** (b - 1));
}else{
return 2 * (3 ** b);
}
};
игра в прыжки
Учитывая массив неотрицательных целых чисел, вы изначально находитесь в первой позиции массива.
Каждый элемент в массиве представляет максимальную длину, на которую вы можете прыгнуть в этой позиции.
Определите, сможете ли вы достичь последней позиции.
1. 使用一个变量保存当前可到达的最大位置
2. 时刻更新最大位置
3. 可达位置小于数组长度返回false,反之即反
var canJump = function(nums) {
let k = 0;
for(let i = 0;i < nums.length;i++){
if(i > k) return false;
k = Math.max(k,i + nums[i]);
}
return true;
};
Бензоколонка
На кольце есть N заправок, где на i-й заправке есть gas[i] литров бензина.
У вас есть машина с бесконечным топливным баком, и чтобы добраться от i-й заправки до i+1-й заправки, нужно затратить [i] литров бензина. Вы стартуете с одной из заправок и стартуете с пустым баком.
Возвращает номер заправки на момент выезда, если можно обойти цикл, -1 иначе
1. gas - cost >= 0才能绕场一周,以此思想判断能否行驶一周
2. 从正确初始位置开始,拥有的汽油总是比消耗的汽油多,以此思想寻找初始位置
var canCompleteCircuit = function(gas, cost) {
let cur = 0,total = 0,start = 0;
for(let i = 0;i < gas.length;i++){
total += gas[i] - cost[i];
if(cur < 0){
cur = gas[i] - cost[i];
start = i;
}else cur += gas[i] - cost[i];
}
return total >= 0 ? start : -1;
};
две точки
Мысль
При поиске упорядоченной последовательности предпочтение отдается дихотомическим
Введите поворот отсортированного по неубыванию массива, выведите наименьший элемент повернутого массива
// 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
// NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
//把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
//10111
1. 原数据为旋转数组,所以分界点前后都是有序的
2. 进行二分查找,注意因为找最小值,high赋值时应该从mid开始取,mid可能是最小值
function minNumberInRotateArray(rotateArray)
{
if(!rotateArray.length) return 0;
let left = 0,right = rotateArray.length-1;
while(left < right){
let mid = Math.floor((right+left) >> 1);
if(rotateArray[left] <= rotateArray[right]){
return rotateArray[left];
}
if(rotateArray[left] < rotateArray[mid]){
left = mid + 1;
}else if(rotateArray[right] > rotateArray[mid]){
right = mid;
}else{
left++;
}
}
}
Подсчитайте, сколько раз число появляется в отсортированном массиве
function GetNumberOfK(data, k)
{
let low = 0,high = data.length-1;
let pos,count = 0;
while(low < high){
let mid = Math.floor((low+high)>>1);
if(data[mid] === k){
pos = mid;
break;
}else if(data[mid] < k){
low = mid + 1;
}else{
high = mid-1;
}
}
if(pos !== undefined){
count++;
let left = pos,right = pos;
while(left--){
if(data[left] === k){
count++;
}else{
break;
}
}
while(right++){
if(data[right] === k){
count++;
}else{
break;
}
}
return count;
}else return 0;
}
Пропущенные числа от 0 до n-1
Все числа в возрастающем отсортированном массиве длины n-1 уникальны, и каждое число находится в диапазоне от 0 до n-1. Среди n чисел в диапазоне 0~n-1 есть только одно число, которого нет в массиве, найдите это число
var missingNumber = function(nums) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid === nums[mid]) {
left = mid + 1;
} else if (mid < nums[mid]) {
right = mid - 1;
}
}
return left;
};
самая длинная восходящая подпоследовательность
1. 维护一个子序列存放当前的上升序列
2. 将当前数与子序列最大值比较,如果比最大值大之间加入队尾,如果更新则找一个合适的位置替换当前位置的元素
var lengthOfLIS = function(nums) {
let n = nums.length;
if(n <= 1){
return n;
}
let tail = [nums[0]];
for(let i = 0;i < n;i++){
if(nums[i] > tail[tail.length-1]){
tail.push(nums[i]);
}else{
let left = 0;
let right = tail.length-1;
while(left < right){
let mid = (left + right) >> 1;
if(tail[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
tail[left] = nums[i];
}
}
return tail.length;
};
Поиск двумерной матрицы II
Напишите эффективный алгоритм для поиска в матричной матрице m x n целевого значения. Эта матрица обладает следующими свойствами:
Элементы каждой строки расположены в порядке возрастания слева направо. Элементы каждого столбца располагаются в порядке возрастания сверху вниз.
输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
1. 选取左下角的值作为初始值key
2. 如果目标值大于key,因为是最左边的值(最小),所以col++
3. 如果目标值小于,那么更小的值只可能是上一行,所以row--
function Find(target,array){
let rows = array.length;
if(rows <= 0) return false;
let cols = array[0].length;
if(cols <= 0) return false;
let row = rows - 1;
let col = 0;
while(row >= 0 && col < cols){
if(array[row][col] > target){
row--;
}else if(array[row][col] < target){
col++;
}else{
return true;
}
}
return false;
}
Pow(x, n)
выполнитьpow(x, n), т. е. вычислить n-ю степенную функцию x
//快速幂算法
var myPow = function(x, n) {
if (!x) return 0;
if (x === 1) return 1;
if (x === -1) return (n & 1) ? -1 : 1;
if (n == 2147483647) return 0;
if (n == -2147483648) return x === 2 ? 0 : 1;
if (n < 0) {
x = 1 / x;
n = -n;
}
let res = 1;
while(n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
искать пересечение
function intersection(...args){
if(!args.length) return [];
let res = [],left = args[0][0],right = args[0][1];
for(let i = 1;i < args.length;i++){
if(right >= args[i][0] || left <= args[i][1]){
left = Math.max(left,args[i][0]);
right = Math.min(right,args[i][1]);
res = [left,right];
}else{
return [];
}
}
return res;
}
Обратно
Идеи решения проблем
-
Глобальная переменная: сохранить результат
-
Параметры: выбор параметров для рекурсивной функции, обычно два типа параметров.
- Переменная состояния: значение, которое результат должен сохранить
- Переменная условия: определяет, завершен ли поиск и является ли поиск законным.
-
Условия завершения: условия завершения определены при определении переменных состояния и переменные состояния для определения конца процесса поиска. В целом процесс поиска есть два значения: поиск успеха и сохранения результатов не удалось и вернулись в предыдущее состояние.
-
Рекуррентный процесс: передать текущее состояние для поиска следующего рекурсивного.
шаблон
let res = []; //存储结果
function backtrack(path,condition,...){
if(judge(condition)){ //满足条件
res.push(path);
return;
}
for(let select of selectList){
if(剪枝条件) break;
path.push(select); // 走某条路
backtrack(path,newSelectList);
path.pop(); //返回上一个十字路口
}
}
Применимая сцена
- Перестановки
- массив, строка, задано определенное правило, попробуйте найти решение
- Поиск DFS в 2D-массиве
Как применить шаблон
я отфильтровалleetCode
серединаhot
И вопросы о возврате в банке вопросов интервью, вопросы от простых до сложных, охватывающие все сценарии использования.
Подмножество
данный наборНет повторяющихся элементовмассив целых чиселnums, который возвращает все возможные подмножества (множества мощности) этого массива.
- Определите массив res для хранения результата
- Каждое подмножество является переменной состояния, а количество элементов в наборе является переменной условия.
- Количество элементов подмножества меньше или равно количеству элементов множества является ограничивающим условием, при выполнении условия оно будет добавлено в результирующий массив, в противном случае произойдет возврат к предыдущему шагу
- Коллекция поиска следующего уровня должна удалить элементы, которые были добавлены в переменную состояния.
var subsets = function(nums) {
let res = [];
let n = nums.length;
function back(path,i){
if(i <= n){
res.push(path);
}
for(let j = i;j < n;j++){
path.push(nums[j]);
back(path.slice(0),j+1);
path.pop();
}
}
back([],0);
return res;
};
Также есть классное решение этой проблемы с использованием бинарного
-
правые 2^n подмножества набора
-
Используя двоичное моделирование, каждый бит берется или нет
-
Например: [1,2,3] => бит знака: 001 010 100 => 0-7 с &
=> [] [001] [010] [001 010] [100] [001 100] [010 100] [001 010 100] Существует ровно восемь типов, соответствующих индексам массива.
var subsets = function(nums) {
let n = 1 << nums.length;
let res = [];
for(let i = 0;i < n;i++){
let temp = [];
for(let j = 0;j < nums.length;j++){
if(i & (1 << j)){
temp.push(nums[j]);
}
}
res.push(temp);
}
return res;
};
полный массив
учитываянет повторенияПоследовательность чисел, возвращающая все возможные полные перестановки.
- определить разрешение
- Каждая последовательность перестановок является переменной состояния, а количество наборов в последовательности перестановок является условной переменной.
- Условие выполняется, когда количество элементов последовательности перестановок равно заданной последовательности
- Следующий уровень рекурсии зависит от пути, пройденного предыдущим уровнем рекурсии.
var permute = function(nums) {
let len = nums.length;
let res = [];
function back(path){
if(path.length === len){
res.push(path);
return;
}
for(let i = 0;i < len;i++){
if(path.indexOf(nums[i]) === -1){ //这里的判断很精髓
path.push(nums[i]);
back(path.slice());
path.pop();
}
}
}
back([]);
return res;
};
объединенная сумма
Учитывая массив кандидатов без повторяющихся элементов и целевое число target , найдите все комбинации в кандидатах, которые могут составить сумму целевых чисел. Числа в кандидатах могут быть выбраны повторно без ограничений.
- определить разрешение
- Каждый суб-массив является переменной состояния, целевое значение является переменной условия
- Добавление значений в подмассивы равняется целевому значению для удовлетворения требования
- Тар следующего уровня рекурсии (количество отличий от целевого значения) зависит от выбора предыдущего уровня рекурсии
var combinationSum = function(candidates, target) {
let res = [];
let len = candidates.length;
//这里排序是为了防止在for循环if判断时直接跳出了,比如这样的样例[8,7,4,3],11
candidates.sort((x,y) => x-y);
function back(path,i,tar){
if(tar === 0){
res.push(path);
return;
}
for(let j = i;j < len;j++){
//判断是否当前的路口都是通向死路
if(tar < candidates[j]) break;
path.push(candidates[j]);
back(path.slice(),j,tar-candidates[j]);
path.pop();
}
}
back([],0,target);
return res;
};
разделенный палиндром
задана строкаs,БудуsРазделить на подстроки так, чтобы каждая подстрока была палиндромом.
вернутьsВсе возможные схемы сегментации.
- определить разрешение
- Переменная состояния — это набор подстрок палиндрома, а переменная условия — это количество строк в наборе подстрок.
- Когда количество строк в наборе подстрок совпадает с длиной целевой строки, требование выполняется.
- Начальная позиция нижней рекурсии определяется верхней рекурсией
var partition = function(str){
let res = [];
function isPalindrome(s){
let head = 0;
let tail = s.length-1;
while(head <= tail){
if(s[head] !== s[tail]) return false;
head++;
tail--;
}
return true;
}
function backtrack(path,start){
if(start === str.length) res.push(path);
for(let i = start;i < str.length;i++){
if(!isPalindrome(str.slice(start,i+1))) continue;
path.push(str.slice(start,i+1));
backtrack(path.slice(),i+1);
path.pop();
}
}
backtrack([],0);
return res;
}
Поиск слова
Учитывая двумерную сетку и слово, чтобы узнать, существует ли слово в сетке.
Слова должны быть образованы буквами в соседних ячейках в алфавитном порядке, где «соседними» ячейками являются те, которые расположены либо по горизонтали, либо по вертикали. Буквы в одной и той же ячейке не могут использоваться повторно.
- Переменная состояния — это путь, а переменная условия — длина пути.
- Когда длина пути совпадает с длиной целевого словаря, условие выполняется
- Начальные координаты и длина пути следующей рекурсии определяются верхней рекурсией
var exist = function (board, word) {
//越界处理
board[-1] = []
board.push([])
//寻找首个字母
for (let y = 0; y < board.length; y++) {
for (let x = 0; x < board.length; x++) {
if (word[0] === board[y][x] && backtrack(y, x, 0)) return true
}
}
//回溯
function backtrack(y, x, i) {
//回溯终止
if (i + 1 === word.length) return true
//保存字母
var tmp = board[y][x]
board[y][x] = false
if (board[y][x + 1] === word[i + 1] && backtrack(y, x + 1, i + 1)) return true
if (board[y][x - 1] === word[i + 1] && backtrack(y, x - 1, i + 1)) return true
if (board[y + 1][x] === word[i + 1] && backtrack(y + 1, x, i + 1)) return true
if (board[y - 1][x] === word[i + 1] && backtrack(y - 1, x, i + 1)) return true
//复原字母
board[y][x] = tmp
}
return false
};
Восстановление IP-адреса
Получив строку, содержащую только числа, восстановите ее и верните все возможные форматы IP-адресов.
Действительный IP-адрес состоит ровно из четырех целых чисел (каждое от 0 до 255), разделенных знаком «.».
var restoreIpAddresses = function(s) {
let res = [];
if(s.length < 4 || s.length > 12) return res;
function dfs(s, sub, index) {
if(s.length === 0 && index === 4) res.push(sub.slice(1)); // 去掉开头的.
if(s.length === 0 || index === 4) return;
// 一个数
dfs(s.slice(1), `${sub}.${s.slice(0,1)}`, index + 1);
if(s[0] !== '0' && s.length > 1) {
dfs(s.slice(2), `${sub}.${s.slice(0,2)}`, index + 1); // 两个数
if(s.length > 2 && parseInt(s.slice(0,3)) <= 255) {
dfs(s.slice(3), `${sub}.${s.slice(0,3)}`, index + 1); //三个数
}
}
}
dfs(s, '', 0);
return res;
};
Алгоритм сортировки
Пузырьковая сортировка
Сравните размер значения ключа двух записей, если размер значения ключа двух записей поменяется местами, затем поменяйте местами две записи.
function bubbleSort(arr){
for(let i = 1;i < arr.length;i++){
for(let j = i;j > 0;j--){
if(arr[j] < arr[j-1]){
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
}
}
}
return arr;
}
Быстрый ряд
За эталон принимается значение ключа некоторой записи среди n записей, обычно за эталон берется значение ключа первой записи, а отсортированные записи делятся на две независимые части, меньшие или равные этому значению ключа на единицу. сортировка заключается в том, что значение ключа некоторых записей меньше, чем значение ключа другой части записи, а затем две части записей продолжают быстро сортироваться для достижения порядка всей последовательности
function quickSort(arr){
if(arr.length <= 1) return arr;
let right = [],left = [],keys = arr.shift();
for(let value of arr){
if(value > keys){
right.push(value)
}else{
left.push(value);
}
}
return quickSort(left).concat(keys,quickSort(right));
}
Сортировка вставками
Когда i-я (i больше или равна 1) запись вставлена, R1, R2, ... сортируются последовательности, вынимают i-й элемент, находят подходящую позицию в последовательности и вставляют ее в эту место нахождения.
function insertSort(arr){
for(let i = 1;i < arr.length;i++){
let j = i-1;
if(arr[i]<arr[j]){
let temp = arr[i];
while(j >= 0 && temp < arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
return arr;
}
Сортировка холмов
Алгоритм сначала делит группу сортируемых чисел на несколько групп с некоторым приращением d (n/2, n — количество сортируемых чисел), причем индексы, записанные в каждой группе, отличаются на d.Все элементы в каждой group напрямую сортируются вставками, затем группируются с меньшим приращением (d/2) и встроенной сортировкой вставками внутри каждой группы. Когда приращение уменьшается до 1, сортировка завершается после выполнения сортировки прямой вставкой.
function hillSort(arr){
let len = arr.length;
for(let gap = parseInt(len >> 1);gap >= 1;gap = parseInt(gap >> 1)){
for(let i = gap;i < len;i++){
if(arr[i] < arr[i-gap]){
let temp = arr[i];
let j = i - gap;
while(j >= 0 && arr[j] > temp){
arr[j+gap] = arr[j];
j -= gap;
}
arr[j+gap] = temp;
}
}
}
return arr;
}
сортировка выбором
В i-й операции выбора запись с наименьшим значением ключа выбирается из n-i+1 записей посредством ni-кратных сравнений ключ-значение, а запись с i-м (1 меньше или равна 1 меньше или равно n-1) обмен записями
function selectSort(arr){
for(let i = 0;i < arr.length;i++){
let min = Math.min(...arr.slice(i));
let index = arr.indexOf(min);
[arr[i],arr[index]] = [arr[index],arr[i]];
}
return arr;
}
сортировка кучей
function adjustMaxHeap(heap,head,heapSize){
let temp = heap[head];
let child = head * 2 + 1;
while(child < heapSize){
if(child+1 < heapSize && heap[child] < heap[child+1]) child++;
if(heap[head] < heap[child]){
heap[head] = heap[child];
head = child;
child = head * 2 + 1;
}else break;
heap[head] = temp;
}
}
function buildHeap(heap){
for(let i = (heap.length-1) >> 1;i >= 0;i--){
adjustMaxHeap(heap,i,heap.length);
}
}
function heapSort(arr){
buildHeap(arr);
for(let i = arr.length-1;i > 0;i--){
[arr[i],arr[0]] = [arr[0],arr[i]];
adjustMaxHeap(arr,0,i);
}
return arr;
}
Сортировка слиянием
Рассмотрим неупорядоченный файл с n записями как файл, состоящий из n упорядоченных подфайлов длины 1, а затем объедините их попарно.
function MergeSort(arr,left,right){
if(left >= right) return;
let mid = Math.floor((right - left) >> 1) + left;
MergeSort(arr,left,mid);
MergeSort(arr,mid+1,right);
Merge(arr,left,mid,right);
return arr;
}
function Merge(arr,left,mid,right){
let temp = [],i = 0;
let p1 = left,p2 = mid + 1;
while(p1 <= mid && p2 <= right){
arr[p1] <= arr[p2] ? temp[i++] = arr[p1++] : temp[i++] = arr[p2++];
}
while(p1 <= mid){
temp[i++] = arr[p1++];
}
while(p2 <= right){
temp[i++] = arr[p2++];
}
for(let i = 0;i < temp.length;i++){
arr[i+left] = temp[i];
}
}
сортировка ведра
Сгруппируйте данные в корзины одну за другой, а затем отсортируйте данные в каждой корзине.
function radixSort(arr,arrDomain,gropSize){
let data = [];
for(let i = 0;i < arr.length;i++) data.push([]);
console.log(data)
for(let i = 0;i < arr.length;i++){
data[Math.floor(parseInt(arr[i] / gropSize)) + 1].push(arr[i]);
}
for(let i = 0;i < data.length;i++){
quickSort(data[i]);
}
return data.flat(Infinity);
}
Стабильность, временная сложность и пространственная сложность каждого алгоритма сортировки
Система поставляется с реализацией сортировки
Внутренняя реализация сортировки отличается для каждого языка.
Для JS, если длина массива больше 10, используется QuickSort, в противном случае используется вставной сорт. Сортировка вставки выбрана, поскольку, хотя временная сложность очень плохая, она почти такой же, как O (n * logn), когда объем данных невелики. Однако постоянное время, необходимое для сортировки введения, очень мало, так что это быстрее чем другой сортировку.,
стабильность
Стабильность означает, что относительный порядок не может быть изменен для одного и того же значения. Вообще говоря, есть два одинаковых числа A и B. До сортировки A находится перед B, а после сортировки B бежит впереди A. В этой ситуации мы называем это нестабильностью сортировки.
Что означает стабильность? Личное понимание Для внешнего интерфейса, например, мы знакомы со сравнением виртуального DOM во фреймворке, мы рендерим ``список, когда данные нужно сравнивать и изменять после изменения данных, нестабильная сортировка или операции будут делать вещи, которые не нужно менять сами Изменения, приводящие к повторному рендерингу и потере производительности.
Сортировать вопросы интервью
- Быстрая сортировка лучше всего работает в полностью неупорядоченном случае с временной сложностью O(nlogn) и хуже всего в упорядоченном случае с временной сложностью O(n^2).
- Распространенным алгоритмом внешней сортировки является сортировка слиянием.
- Когда элементы массива в основном упорядочены, сортировка вставками работает лучше всего, потому что нужно сравнивать только размер, а временная сложность близка к O(n).
- Если только часть последовательности, полученная ранее упорядоченная последовательность, состоящая из 1000 элементов наименьшего элемента 5, с помощью самого быстрого метода кучной сортировки.
- Быстрая сортировка линейной таблицы длины n с n(n-1)/2 сравнениями в худшем случае.
практические вопросы
отсортированный связанный список
существуетO(n log n) временная сложность и постоянная пространственная сложность, сортировка связанного списка.
var sortList = function(head) {
let mergeList = (left,right) => {
let res = new ListNode(0);
let pre = res;
while(left && right){
if(left.val <= right.val){
pre.next = left;
left = left.next;
}else{
pre.next = right;
right = right.next;
}
pre = pre.next;
}
pre.next = left ? left : right;
return res.next;
}
let mergeSort = (node) => {
if(!node || !node.next) return node;
let mid = node;
let fast = node.next;
while(fast && fast.next){
mid = mid.next;
fast = fast.next.next;
}
let rightList = mid.next;
mid.next = null;
let left = node;
let right = rightList;
return mergeList(mergeSort(left),mergeSort(right));
}
return mergeSort(head);
};
обратная пара
Два числа в массиве, если первое число больше второго, два числа образуют обратную пару. Введите массив, найдите общее количество P обратных пар в этом массиве. И выведите результат P по модулю 1000000007. То есть выведите P%1000000007
let count = 0;
function InversePairs(data)
{
if (data == null || data.length == 0) {
return 0;
}
MergeSort(data,0,data.length-1);
return count % 1000000007;
}
function MergeSort(arr,left,right){
if(left >= right) return;
let mid = Math.floor((right - left)>>1) + left;
MergeSort(arr,left,mid);
MergeSort(arr,mid+1,right);
Merge(arr,left,mid,right);
}
function Merge(arr,left,mid,right) {
let temp = [],i = 0;
let p1 = left,p2 = mid + 1;
while(p1 <= mid && p2 <= right){
if(arr[p1] <= arr[p2]){
temp[i++] = arr[p1++];
}else{
count += mid - p1 + 1;
temp[i++] = arr[p2++];
}
}
while(p1 <= mid){
temp[i++] = arr[p1++];
}
while(p2 <= right){
temp[i++] = arr[p2++];
}
for(let i = 0;i < temp.length;i++){
arr[i+left] = temp[i];
}
}
и проверить
Он принадлежит к специальной структуре данных и обладает хорошей производительностью при решении задач связанной предметной области.
три компонента
-
поддерживать массив
let parents = []
, в котором хранится родительский узел текущего узла, а родительским узлом корневого узла является он сам. -
Запросите, какой узел является корневым узлом узла.
function find(root){ let temp,son = root; while(root !== parents[root]){ root = parents[root]; } while(son !== root){ //路径压缩,其实就是个扁平化处理的过程 temp = parents[son]; parents[son] = root; son = temp; } return root; } //递归版 function find(root){ if(root !== parents[root]) parents[root] = find(parents[root]); return parents[root]; }
-
Объединить два связанных домена
function join(x,y){ x = find(x); y = find(y); if(x !== y){ parents[x] = y; } }
практические вопросы
количество островов
- Напишите три основных компонента и сопоставьте их ключи и значения с исходным родителем.
- Определить, есть ли земля вокруг текущего узла, если есть, соединить их, если нет, инвертировать родительский узел текущего узла
- Найдите количество ключей и значений в массиве parents, которые все еще равны (то есть количество подключенных доменов)
var numIslands = function(grid) {
let row = grid.length;
if(row === 0) return 0;
let col = grid[0].length;
let parents = [];
for(let i = 0;i < row;i++){
for(let j = 0;j < col;j++){
parents[i*col+j] = i * col + j;
}
}
function find(root){
if(root !== parents[root]) parents[root] = find(parents[root]);
return parents[root];
}
function union(x,y){
x = find(x);
y = find(y);
if(x !== y){
parents[x] = y;
}
}
for(let i = 0;i < row;i++){
for(let j = 0;j < col;j++){
if(grid[i][j] === '1'){
i < row-1 && grid[i+1][j] === '1' && union((i+1)*col+j,i*col+j);
j < col-1 && grid[i][j+1] === '1' && union(i*col+j+1,i*col+j);
}else{
parents[i*col+j] = -parents[i*col+j];
}
}
}
return parents.filter((value,key) => (key === value && Object.is(key,value))).length;
};
Решение DFS
var numIslands = function(grid) {
const row = grid.length;
if(!row) return 0;
const col = grid[0].length;
let res = 0;
for(let i = 0; i < row; i++) {
for(let j = 0; j < col; j++) {
if(grid[i][j] === '1') {
res++;
dfs(grid, i, j);
}
}
}
function dfs(grid, i, j) {
if(i < 0 || i >= row || j < 0 || j >= col) return;
if(grid[i][j] === '1') {
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
return res;
};
окруженная территория
- Напишите три компонента
- Буду
O
Узлы разделены на внутренние узлы и граничные узлы, и введен виртуальный граничный корневой узел. - решимость
O
Является ли узел внутренним узлом, если да, замените наX
var solve = function(board) {
let row = board.length;
if(row === 0) return board;
let col = board[0].length;
let parents = [];
for(let i = 0;i < row;i++){
for(let j = 0;j < col;j++){
parents[i*col+j] = i * col + j;
}
}
function find(root){
if(root !== parents[root]) parents[root] = find(parents[root]);
return parents[root];
}
function union(x,y){
x = find(x);
y = find(y);
if(x !== y){
parents[x] = y;
}
}
function isConnected(x,y){
return find(x) === find(y);
}
let virtualArea = row * col + 1;
for(let i = 0;i < row;i++){
for(let j = 0;j < col;j++){
if(board[i][j] === 'O'){
if(i === 0 || i === row-1 || j === 0 || j === col-1){
union(i*col+j,virtualArea);
}else{
i > 0 && board[i-1][j] === 'O' && union(i*col+j,(i-1)*col+j);
i < row-1 && board[i+1][j] === 'O' && union(i*col+j,(i+1)*col+j);
j > 0 && board[i][j-1] === 'O' && union(i*col+j,i*col+j-1);
j < col-1 && board[i][j+1] === 'O' && union(i*col+j,i*col+j+1);
}
}
}
}
for(let i = 0;i < row;i++){
for(let j = 0;j < col;j++){
if(board[i][j] === 'O' && !isConnected(i*col+j,virtualArea)){
board[i][j] = 'X';
}
}
}
return board;
};
топологическая сортировка
к одномуНаправленный ациклический граф(Направленный ациклический граф, называемый DAG) Топологическая сортировка G состоит в том, чтобы упорядочить все вершины в G в линейную последовательность, так что любая пара вершин u и v в графе, если ребро ∈E(G ), то u появляется перед v в линейной последовательности. Обычно такую линейную последовательность называют последовательностью, удовлетворяющей топологическому порядку, или сокращенно топологической последовательностью. Проще говоря, наборчастичный заказполучить один из набораобщий заказ, эта операция называется топологической сортировкой. Я должен сказать, что объяснение энциклопедии очень профессионально, но я просто не знаю, о чем она говорит (wtcl).
Например
- Для ориентированного ациклического графа мы сначала находим узел с нулевой степенью вхождения (просто найдите один)
- Удалите узел и сохраните значение узла в массиве результатов, затем уменьшите степень вхождения всех соседних узлов узла на 1.
- Повторно найдите узел со степенью входа 0 и повторите операцию 2.
- Сохраните значения всех оставшихся узлов со степенью входа 0 в массив результатов.
как построить карту
Топологическая сортировка включает удаление узлов, поэтому для представления графа рекомендуется использовать структуру данных списка смежности.
список смежности
//这里是一个简单的邻接表(面向试题编程),该结构在练习题部分有
class Node{
constructor(value){
this.value = value;
this.next = null;
this.in = 0; //记录入度
}
}
class Graph{
constructor(nodeNum,edges){
this.list = new Array(nodeNum);
for(let i = 0;i < this.list.length;i++){ //初始化邻接表
this.list[i] = new Node(i);
}
let v1,v2,newNode = null;
for(let edge of edges){ //构建邻接表以及每个节点的入度数
[v2,v1] = edge;
newNode = new Node(v2);
newNode.next = this.list[v1].next;
this.list[v1].next = newNode;
this.list[v2].in++;
}
}
}
Любимые практические вопросы
Расписание занятий II
Теперь вам нужно пройти n курсов, обозначенных от 0 до n-1.
Некоторые предварительные курсы необходимы перед прохождением определенных курсов. Например, чтобы изучить курс 0, вам нужно сначала пройти курс 1, мы представляем их соответствием: [0,1]
Учитывая общее количество курсов и их предварительные условия, возвращает порядок обучения, который вы разместили, чтобы пройти все курсы.
Может быть более одного правильного заказа, вам просто нужно вернуть один. Возвращает пустой массив, если невозможно пройти все курсы.
- построить список смежности
- Создайте вспомогательный стек для хранения узлов с нулевой степенью вхождения, результирующий массив res для хранения результатов и счетчик счетчика для записи количества удаленных узлов.
- Каждый раз, когда берется узел во вспомогательном стеке, степень вхождения всех его смежных узлов вычитается на единицу, и степень вхождения определяется как равная нулю (таким образом, добавляется во вспомогательный стек), а значение узла равно положить в res, count++
- Определите, совпадает ли счетчик с количеством узлов в графе, и разница доказывает, что есть петля, просто верните значение, как того требует заголовок
class Node{
constructor(value){
this.value = value;
this.next = null;
this.in = 0;
}
}
class Graph{
constructor(nodeNum,edges){
this.list = new Array(nodeNum);
for(let i = 0;i < this.list.length;i++){
this.list[i] = new Node(i);
}
let v1,v2,newNode = null;
for(let edge of edges){
[v2,v1] = edge;
newNode = new Node(v2);
newNode.next = this.list[v1].next;
this.list[v1].next = newNode;
this.list[v2].in++;
}
}
}
var findOrder = function(numCourses, prerequisites) {
let list = new Graph(numCourses,prerequisites).list;
let stack = [],res = [];
for(let node of list){
node.in === 0 && stack.push(node);
}
let count = 0;
while(stack.length){
let node = stack.pop();
count++;
res.push(node.value);
while(node.next){
(--list[node.next.value].in) === 0 && stack.push(list[node.next.value]);
node = node.next;
}
}
if(count !== list.length) return [];
else return res;
};
Расписание занятий
В этом семестре вы должны пройти курсы numCourse, пронумерованные от 0 до numCourse-1.
Некоторые предварительные курсы необходимы перед прохождением определенных курсов. Например, чтобы изучить курс 0, вам нужно сначала пройти курс 1, мы представляем их соответствием: [0,1]
Учитывая общее количество курсов и их обязательные условия, не могли бы вы решить, возможно ли пройти все курсы?
//上题的简化版,直接看代码吧
class Node{
constructor(value){
this.value = value;
this.next = null;
this.in = 0;
}
}
class Graph{
constructor(nodeNum,edges){
this.list = new Array(nodeNum);
for(let i = 0;i < this.list.length;i++){
this.list[i] = new Node(i);
}
let v1,v2,newNode = null;
for(let edge of edges){
[v2,v1] = edge;
newNode = new Node(v2);
newNode.next = this.list[v1].next;
this.list[v1].next = newNode;
this.list[v2].in++;
}
}
}
var canFinish = function(numCourses, prerequisites) {
let list = new Graph(numCourses,prerequisites).list;
let stack = [];
for(let node of list){
node.in === 0 && stack.push(node);
}
let count = 0;
while(stack.length){
let node = stack.pop();
count++;
while(node.next){
(--list[node.next.value].in) === 0 && stack.push(list[node.next.value]);
node = node.next;
}
}
return count === list.length
};
битовая операция
количество единиц в двоичном формате
Пожалуйста, реализуйте функцию, которая принимает целое число в качестве входных данных и выводит количество единиц в двоичном представлении числа. Например, 9 в двоичном формате — это 1001, а 2 бита — это 1. Итак, если вы введете 9, функция выведет 2
//n & (n-1)每次1的数量--
var hammingWeight = function(n) {
let count = 0;
while(n){
count++;
n = n & (n-1);
}
return count;
};
В массиве есть число, которое превышает половину длины массива, найдите это число
// 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
1. count初始化为0,count === 0时,res = 当前数,count++
2. 当前数与res相同count++,否则count--
3. 以上两步能够选出出现次数最多的数,接下来判断它是否超过一半即可
function MoreThanHalfNum_Solution(numbers)
{
let result,count=0;
for(let i = 0;i < numbers.length;i++){
if(count === 0){
result = numbers[i];
count++;
}else{
if(result === numbers[i]){
count++;
}else{
count--;
}
}
}
let times = numbers.filter(x => x === result).length;
return times > Math.floor(numbers.length >> 1) ? result : 0;
}
Числа, которые появляются только один раз
учитываяне пустойМассив целых чисел, в котором каждый элемент встречается дважды, кроме одного, который встречается только один раз. Найдите элемент, который появляется только один раз
var singleNumber = function(nums) {
let num = nums[0];
for(let i = 1;i < nums.length;i++){
num ^= nums[i];
}
return num;
};
количество бит
задано неотрицательное целое числоnum. для0 ≤ я ≤ числокаждое число в диапазонеi, Число, которое является двоичным числом 1, вычисляется и возвращается в виде его массива
1. 奇数1的个数等于前一个偶数+1
2. 偶数1的个数等于当前偶数 >> 1 的值
var countBits = function(num) {
let res = [0];
for(let i = 1;i <= num;i++){
if(i & 1){
res[i] = res[i-1] + 1;
}else{
res[i] = res[i >> 1];
}
}
return res;
};
Расстояние Хэмминга
между двумя целыми числамиРасстояние ХэммингаОтносится к количеству различных позиций, в которых два числа соответствуют двоичным цифрам.
дать два целых числаx
а такжеy
Рассчитайте расстояние между ними
1. 亦或求出不同部分
2. 统计
var hammingDistance = function(x, y) {
let ans = x ^ y,count = 0;
while(ans){
if(ans & 1) count++;
ans = ans >> 1;
}
return count;
};
Функция записи и сумма двух целых чисел, функция не может использоваться in vivo требует +, -, *, / четыре символа операции
1. ^ 不进位的加法
2. & 判断进位点
3. << 1 进位
function Add(num1, num2)
{
return num2 ? Add(num1 ^ num2,(num1 & num2) << 1) : num1;
}
двойной указатель
Как следует из названия, используйте два указателя для поиска, чтобы повысить эффективность поиска.
сумма n чисел
сумма двух чисел
var twoSum = function(nums, target) {
if(!nums.length) return [];
let num = nums.slice(0);
nums.sort((x,y) => x-y);
let l = 0,r = nums.length-1;
while(l < r){
if(nums[l] + nums[r] === target) break;
else if(nums[l] + nums[r] < target){
l++;
}else{
r--;
}
}
l = num.indexOf(nums[l]);
r = num.indexOf(nums[r]) === l ? num.indexOf(nums[r],l+1) : num.indexOf(nums[r])
return [l,r];
};
сумма трех
var threeSum = function(nums) {
if(nums.length < 3) return [];
nums.sort((x,y) => x-y);
let res = [];
for(let i = 0;i < nums.length;i++){
//如果第一个数大于1就没必要排了
if(nums[i] > 0) return res;
//去重
if(i && nums[i] === nums[i-1]) continue;
let left = i+1,right = nums.length-1;
while(left < right){
if(nums[left] + nums[right] + nums[i] === 0){
res.push([nums[i],nums[left],nums[right]]);
//去重
while(left < right && nums[left] === nums[left+1]){
left++;
}
while(left < right && nums[right] === nums[right-1]){
right--;
}
left++;
right--;
}else if(nums[left] + nums[right] + nums[i] > 0){
right--;
}else{
left++;
}
}
}
return res;
};
Сумма ближайших трех чисел
//思路与前面基本一致,但需要两个变量,一个更新答案,一个更新最小差值
var threeSumClosest = function(nums, target) {
if(!nums.length) return 0;
let res = Infinity,mins = Infinity;
nums.sort((x,y) => x-y);
for(let i = 0;i < nums.length;i++){
let left = i + 1,right = nums.length-1;
while(left < right){
mins = Math.min(Math.abs(nums[i]+nums[left]+nums[right]-target),mins);
mins === Math.abs(nums[i]+nums[left]+nums[right]-target)
&& (res = nums[i]+nums[left]+nums[right]);
if(nums[i]+nums[left]+nums[right] < target){
left++;
}else if(nums[i]+nums[left]+nums[right] > target){
right--;
}else{
break;
}
}
}
return res;
};
Дождевая вода, проблемы с контейнерами
емкость с наибольшим количеством воды
//双指针时刻更新最大值即可,实质上还是枚举
var maxArea = function(height) {
if(!height.length) return 0;
let left = 0,right = height.length-1,res = 0;
while(left < right){
if(height[left] <= height[right]){
let cur = height[left] * (right - left);
res = Math.max(res,cur);
left++;
}else{
let cur = height[right] * (right - left);
res = Math.max(res,cur);
right--;
}
}
return res;
};
поймать дождь
// 比较巧妙的是如何获取每个单元格所能存放的雨水,可以有以下式子简单表示
// 以左边为例:当前柱子存水量 = 最近最高柱子高度(只看左边到当前柱子) - 当前柱子高度
// 右边同理
function trap(arr){
if(!arr.length) return 0;
let left = 0,right = arr.length-1,leftHeight = 0,rightHeight = 0,res = 0;
while(left < right){
if(arr[left] < arr[right]){
leftHeight = Math.max(arr[left],leftHeight);
res += leftHeight - arr[left];
left++;
}else{
rightHeight = Math.max(arr[right],rightHeight);
res += rightHeight - arr[right];
right--;
}
}
return res;
}
подмассив с наименьшей длиной
Учитывая массив из n положительных целых чисел и положительное целое число s, найдите непрерывный подмассив с наименьшей длиной в массиве, который удовлетворяет его сумме ≥ s, и верните его длину. Возвращает 0, если нет соответствующих смежных подмассивов.
// 滑动窗口的解法
// 每次将右指针对应的数添加到临时num中
// 查看是否满足题意,满足则作为一个可行解与len作比较,同时移动左指针
// 移动右指针到下一个位置
var minSubArrayLen = function(s, nums) {
let left = 0, right = 0, len = Infinity, num = 0;
while(right < nums.length) {
num += nums[right];
while(num >= s) {
len = Math.min(len, right - left + 1);
num -= nums[left];
left++;
}
right++;
}
return len === Infinity ? 0 : len;
};
класс связанного списка
Удалить n-й узел снизу связанного списка
var removeNthFromEnd = function(head, n) {
if(!head) return null;
let fast = head,slow = head,pre = head,p1 = head,len = 0;
while(p1){
len++;
p1 = p1.next;
}
//注意头节点删除的情况
if(len === n) return head.next;
while(n--){
fast = fast.next;
}
while(fast){
fast = fast.next;
pre = slow;
slow = slow.next;
}
pre.next = slow.next;
return head;
};
Пожалуйста, определите, является ли связанный список палиндромным связанным списком
1. 将前半部分链表反转
2. 判断前后两部分链表是否相等
var isPalindrome = function(head) {
if(!head) return true;
let pre = null,temp,fast = head,slow = head;
while(fast && fast.next){
fast = fast.next.next;
// 反转链表
temp = slow;
slow = slow.next;
temp.next = pre;
pre = temp;
}
if(fast) slow = slow.next;
while(pre && slow){
if(pre.val !== slow.val) return false;
pre = pre.next;
slow = slow.next;
}
return true;
};
Учитывая связанный список, определите, есть ли цикл в связанном списке
var hasCycle = function(head) {
if(!head || !head.next || !head.next.next) return false;
let fast = head.next.next,slow = head.next;
while(fast !== slow){
if(fast === null || fast.next === null) return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
};
Введите связанный список и выведите k-й узел снизу связанного списка.
function FindKthToTail(head, k)
{
// write code here
if(head === null || k === 0) return null;
let fast = head,slow = head;
while(k--){
if(fast === null) return null;
fast = fast.next;
}
while(fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
Введите два монотонно возрастающих связанных списка и выведите связанный список после объединения двух связанных списков.Конечно, нам нужно, чтобы объединенный связанный список удовлетворял правилу монотонно неубывающего.
//注意与拷贝链表区分
function Merge(pHead1, pHead2)
{
if(pHead1 === null){
return pHead2;
}else if(pHead2 === null){
return pHead1;
}
if(pHead1.val < pHead2.val){
pHead1.next = Merge(pHead1.next,pHead2);
return pHead1;
}else{
pHead2.next = Merge(pHead2.next,pHead1);
return pHead2;
}
}
Введите два связанных списка и найдите их первый общий узел
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
let p1 = pHead1,p2 = pHead2;
while (p1 !== p2){
p1 = p1 === null ? pHead2 : p1.next;
p2 = p2 === null ? pHead1 : p2.next;
}
return p1;
}
Найти позицию кольцевой записи кругового связанного списка
var detectCycle = function(head) {
if(!head || !head.next) return null;
let fast = head.next.next,slow = head.next,p1 = head;
while(fast !== null && fast !== slow){
if(fast.next) fast = fast.next.next;
else fast = null;
slow = slow.next;
}
if(fast === null) return null;
else{
while(p1 !== slow){
p1 = p1.next;
slow = slow.next;
}
return slow;
}
};
Строковый класс
палиндром проверки
var isPalindrome = function(s) {
let reg = /[a-z]|[0-9]/;
s = s.split('').map(x => x.toLowerCase()).filter((x) => reg.test(x)).join('');
let head = 0;
let tail = s.length-1;
while(head <= tail){
if(s[head] !== s[tail]) return false;
head++;
tail--;
}
return true;
};
матрица
печатать матрицу по часовой стрелке
Введите матрицу и распечатайте каждое число по часовой стрелке снаружи внутрь
// 例如,如果输入如下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.
旋转魔方法,每次打印第一列,然后将矩阵逆时针旋转
function rotate(arr){
if(!arr.length) return [];
let newArr = [];
for(let i = 0;i < arr[0].length;i++){
let temp = [];
for(let j = 0;j < arr.length;j++){
temp.push(arr[j][arr[0].length-1-i]);
}
newArr.push(temp);
}
return newArr;
}
function printMatrix(matrix)
{
if(!matrix.length) return [];
let ans = [];
while(matrix.length){
for(let i = 0;i < matrix[0].length;i++){
ans.push(matrix[0][i])
}
matrix.splice(0,1);
matrix = rotate(matrix);
}
return ans;
}
Повернуть изображение
учитываяn × nДвумерная матрица, представляющая изображение.
Поверните изображение по часовой стрелке на 90 градусов
var rotate = function(matrix) {
if(!matrix.length) return [];
let left = 0,right = matrix.length-1;
while(right-left > 0){
[matrix[left],matrix[right]] = [matrix[right],matrix[left]];
left++;
right--;
}
for(let i = 0;i < matrix.length;i++){
for(let j = i+1;j < matrix[i].length;j++){
[matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]];
}
}
return matrix;
};
Спиральная матрица II
задано положительное целое числоn, который создает массив, содержащий от 1 доn2 Квадратная матрица со всеми элементами спирали, расположенными по часовой стрелке.
//基本就是模拟这个过程,要注意转弯的边界条件
var generateMatrix = function(n) {
let rows = n-1,cols = n-1,col = 0,row = 0,iter = 1,x_dire = 1,y_dire = 1,cur_dire = 1,res = [];
for(let i = 0;i < n;i++) res.push([]);
while(iter <= n ** 2) {
if (cur_dire === 1 && res[row][col] === undefined) {
res[row][col] = iter;
iter++;
if (x_dire === 1) {
if (col < cols) {
col++;
} else {
cur_dire = -1;
x_dire = -x_dire;
if (y_dire === 1) row++;
else row--;
}
} else {
if (col > 0) {
col--;
} else {
cur_dire = -1;
x_dire = -x_dire;
if (y_dire === 1) row++;
else row--;
}
}
}else if (cur_dire === 1 && res[row][col]) {
if (y_dire === 1) row++;
else row--;
x_dire = -x_dire;
cur_dire = -1;
if (x_dire === 1) col++;
else col--;
}else if (cur_dire === -1 && res[row][col] === undefined) {
res[row][col] = iter;
iter++;
if (y_dire === 1) {
if (row < rows) {
row++;
} else {
cur_dire = 1;
y_dire = -y_dire;
if (x_dire === 1) col++;
else col--;
}
} else {
if (row >= 0) {
row--;
} else {
cur_dire = 1;
y_dire = -y_dire;
if (x_dire === 1) col++;
else col--;
}
}
} else if(cur_dire === -1 && res[row][col]) {
if (x_dire === 1) col++;
else col--;
y_dire = -y_dire;
cur_dire = 1;
if (y_dire === 1) row++;
else row--;
}
}
return res;
};
обнуление матрицы
учитываяm x nЕсли элемент равен 0, установите все элементы в его строке и столбце равными 0. пожалуйста, используйте**на месте**алгоритм
//利用了js的特性,-0和0的不相等
//将0所在行列中非0元素置为-0
var setZeroes = function(matrix) {
for(let i = 0;i < matrix.length;i++){
for(let j = 0;j < matrix[i].length;j++){
if(Object.is(matrix[i][j],0)){
for(let k = 0;k < matrix.length;k++){
if(k !== i && Object.is(matrix[k][j],0)) continue;
else matrix[k][j] = -0
}
for(let k = 0;k < matrix[i].length;k++){
if(k !== j && Object.is(matrix[i][k],0)) continue;
else matrix[i][k] = -0
}
}
}
}
return matrix;
};
Треугольник Ян Хуэй
//入坑题
function print(n) {
let arr = [],n1 = n;
while(n1--){
arr.push([]);
}
for(let i = 0;i < n;i++){
for(let j = 0;j <= i;j++){
if(j === 0 || j === i) arr[i][j] = 1;
else{
arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
}
}
}
arr.forEach(x => console.log(x.toString().replace(/,/g,' ')));
}
бинарное дерево
перебрать серию
Обход двоичного дерева до и после заказа (рекурсивный и нерекурсивный)
//递归
function pre(root){
if(!root) return root;
console.log(root.val);
pre(root.left);
pre(root.right);
}
function mid(root){
if(!root) return root;
mid(root.left);
console.log(root.val);
mid(root.right);
}
function next(root){
if(!root) return root;
next(root.right);
next(root.left);
console.log(root.val);
}
//非递归
//前序
//用栈进行模拟
//每次将栈顶元素添加到结果中,然后将栈顶元素的左右非空子树入栈(注意右子树先入栈,后弹出)
//直到栈为空跳出循环
function pre(root){
if(root === null) return root;
let res = [],stack = [];
stack.push(root);
while (stack.length){
let node = stack.pop();
res.push(node.val);
node.right && stack.push(node.right);
node.left && stack.push(node.left);
}
return res;
}
//中序
//对栈顶元素深度遍历左子树入栈,然后将栈顶添加到结果中,然后访问当前子节点的右子树,依次循环
function mid(root){
if(root === null) return root;
let res = [],stack = [];
stack.push(root);
while (stack.length){
while(root !== null){
stack.push(root);
root = root.left;
}
let node = stack.pop()
res.push(node.val);
root = node.right;
}
//根节点添加了两次
return res.slice(0,res.length-1);
}
//后序
//与前序相似,但生成顺序为根右左,最后将res反序
function next(root){
if(root === null) return root;
let res = [],stack = [];
stack.push(root);
while (stack.length){
let node = stack.pop();
res.push(node.val);
node.left && stack.push(node.left);
node.right && stack.push(node.right);
}
return res.reverse();
}
Иерархический обход
var levelOrder = function(root) {
if(!root) return [];
let nodes = [],queue = [root],path=[];
let cur = 1,next = 0;
while(queue.length){
let node = queue.shift();
path.push(node.val);
node.left && queue.push(node.left) && next++;
node.right && queue.push(node.right) && next++;
cur--;
if(!cur){
nodes.push(path);
path = [];
cur = next;
next = 0;
}
}
return nodes;
};
обходной вариант
Зигзагообразный иерархический обход бинарного дерева
Учитывая бинарное дерево, верните зигзагообразный иерархический обход его значений узла. (То есть следующий слой обходят слева направо, затем справа налево и так далее, чередуя слои).
var zigzagLevelOrder = function(pRoot) {
if(!pRoot) {
return []
}
var queue = [], res = [], temp = [],
node, level = 0, toBePrinted = 1, isEven = true;
queue.push(pRoot);
while(queue.length) {
node = queue.shift();
// 判断当前行为奇数行还是偶数行
if(isEven) {
temp.push(node.val);
} else {
temp.unshift(node.val);
}
// 计算每一行的元素个数
if(node.left) {
queue.push(node.left);
level++;
}
if(node.right) {
queue.push(node.right);
level++;
}
toBePrinted--;
// 判断当前行是否全部输出完毕
if(toBePrinted === 0) {
res.push(temp);
temp = [];
toBePrinted = level;
level = 0;
isEven = !isEven;
}
}
return res;
};
Печатайте бинарное дерево слой за слоем сверху вниз, а узлы в одном слое выводятся слева направо. Каждый слой выводит одну строку.
//相比bfs,需要增加两个变量,一个存当前层次的还有多少节点需要打印,一个存储下一层次有多少个节点(每次队列push时进行++)
function Print(pRoot) {
let nodes = [],queue = [pRoot],path=[];
let cur = 1,next = 0;
while(queue.length){
let node = queue.shift();
path.push(node.val);
node.left && queue.push(node.left) && next++;
node.right && queue.push(node.right) && next++;
cur--;
if(!cur){
nodes.push(path);
path = [];
cur = next;
next = 0;
}
}
return nodes;
}
Найдите значение на основе известного бинарного дерева
Найдите глубину бинарного дерева
function TreeDepth(pRoot)
{
if(pRoot === null) return 0;
let left = TreeDepth(pRoot.left);
let right = TreeDepth(pRoot.right);
return Math.max(left,right) + 1;
}
K-й наименьший элемент в бинарном дереве поиска
var kthSmallest = function(root, k) {
let res;
function midOrder(root){
if(!root) return root;
midOrder(root.left);
if(k === 0) return res;
else{
res = root.val;
k--;
}
midOrder(root.right);
}
midOrder(root);
return res;
};
последний общий предок бинарного дерева
(1)深度优先查找,查到两节点任意一个返回
(2)当两个节点都找到时返回root,否则返回null
var lowestCommonAncestor = function(root, p, q) {
if(!root) return null;
if(root === p || root === q) return root;
let left = lowestCommonAncestor(root.left,p,q);
let right = lowestCommonAncestor(root.right,p,q);
if(!left) return right;
if(!right) return left;
if(left && right) return root;
return null;
};
Учитывая бинарное дерево, вам нужно вычислить длину его диаметра.
Диаметр бинарного дерева — это максимальная длина пути любых двух узлов. Этот путь может проходить или не проходить через корневой узел.
易错点是直径可能不经过根节点
用max保存最大值,
当每个节点作为根节点时,与max比较进行更新
var diameterOfBinaryTree = function(root) {
let max = 0;
function dfs(root){
if(!root) return 0;
let l = dfs(root.left);
let r = dfs(root.right);
max = Math.max(max,l+r);
return Math.max(l,r)+1;
}
dfs(root);
return max;
};
Найдите сумму чисел от корня до конечных узлов
В бинарном дереве каждый его узел хранит число от 0 до 9, а каждый путь от корня до конечного узла представляет собой число.
Например, путь от корня к конечному узлу 1->2->3 представляет собой число 123.
Вычислите сумму всех чисел, сгенерированных от корневых до конечных узлов.
Объяснение: Листовой узел — это узел, у которого нет дочерних узлов.
// 简单的dfs
var sumNumbers = function(root) {
let res = 0;
function dfs(root,temp) {
if(!root) return;
temp += root.val;
if((!root.left) && (!root.right)) res += Number(temp);
dfs(root.left,temp);
dfs(root.right,temp);
}
dfs(root,'');
return res;
};
Некоторые специальные бинарные деревья (суждение и построение)
Проверить, является ли бинарное дерево симметричным бинарным деревом
function mirrors(root)
{
if(root === null) return root;
[root.left,root.right] = [root.right,root.left];
mirrors(root.left);
mirrors(root.right);
}
var isSymmetric = function(root) {
let mirror = JSON.parse(JSON.stringify(root));
mirrors(mirror);
if(JSON.stringify(mirror) === JSON.stringify(root)){
return true;
}else{
return false;
}
};
Проверка двоичного дерева поиска
Учитывая бинарное дерево, определите, является ли оно допустимым бинарным деревом поиска.
let pre = -Infinity;
var isValidBST = function(root) {
if(!root) return true;
let left = isValidBST(root.left);
if(root.val <= pre || !left) return false;
pre = root.val;
return isValidBST(root.right);
};
Построить бинарное дерево из последовательности обхода в прямом и обратном порядке
var buildTree = function(preorder, inorder) {
if(!preorder.length || !inorder.length) return null;
let root = new TreeNode(preorder[0]);
let key = 0;
for(let i = 0;i < inorder.length;i++){
if(inorder[i] === preorder[0]){
key = i;
break;
}
}
root.left = buildTree(preorder.slice(1,key+1),inorder.slice(0,key));
root.right = buildTree(preorder.slice(key+1),inorder.slice(key+1));
return root;
};
перевернуть бинарное дерево
var invertTree = function(root) {
if(root === null) return root;
[root.left,root.right] = [root.right,root.left];
invertTree(root.left);
invertTree(root.right);
return root;
};
Преобразование бинарного дерева поиска в дерево накопления
var convertBST = function(root) {
let cur = 0;
re = function(root){
if(!root) return root;
re(root.right);
root.val += cur;
cur = root.val;
re(root.left);
return root;
}
return re(root);
};
объединить бинарное дерево
var mergeTrees = function(t1, t2) {
if(t1 && t2){
t1.val += t2.val;
t1.left = mergeTrees(t1.left,t2.left);
t1.right = mergeTrees(t1.right,t2.right);
}
return t1 || t2;
};
Введите два бинарных дерева A, B, определите, является ли B подструктурой A
(ps: мы согласны с тем, что пустое дерево не является подструктурой любого дерева)
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
//判断是否为子结构跟先序遍历类似
function isSubtree(root1,root2) {
if(!root2) return true;
if(!root1) return false;
if(root1.val !== root2.val) return false;
return isSubtree(root1.left,root2.left) && isSubtree(root1.right,root2.right);
}
//从根节点开始递归判断是否含有子结构
function HasSubtree(pRoot1, pRoot2)
{
if(!pRoot1 || !pRoot2) return false;
return (
isSubtree(pRoot1,pRoot2)
|| HasSubtree(pRoot1.left,pRoot2)
|| HasSubtree(pRoot1.right,pRoot2)
)
}
Управляет заданным бинарным деревом, преобразовывая его в зеркальное отображение исходного бинарного дерева.
function Mirror(root)
{
if(root === null) return root;
[root.left,root.right] = [root.right,root.left];
Mirror(root.left);
Mirror(root.right);
return root;
}
Введите двоичное дерево, чтобы определить, является ли двоичное дерево сбалансированным двоичным деревом.
1. 比较两颗子树的高度,两边都取最大深度
2. 查看两颗子树高度差是否相差为1
3. 如果大于1,那么将其标记为-1(表示不是AVL树),然后每次递归时先判断该节点的子树是否时AVL树
function IsBalanced_Solution(pRoot)
{
return orderTree(pRoot) !== -1;
}
function orderTree(root) {
if(!root) return 0;
let left = orderTree(root.left);
let right = orderTree(root.right);
if(left === -1 || right === -1 || Math.abs(left-right) > 1) return -1;
return Math.max(left,right)+1;
}
Найдите несколько путей в бинарном дереве
Сумма Пути III
Для данного бинарного дерева каждый его узел содержит целочисленное значение.
Найдите пути и общее количество путей, равное заданному числу.
Путь не обязательно должен начинаться в корневом узле и заканчиваться конечным узлом, но направление пути должно быть нисходящим (только от родителя к дочернему).
Двоичное дерево не превышает 1000 узлов, а диапазон значений узлов представляет собой целое число [-1000000, 1000000].
function dfs(cur,sum,root,path,res){
cur += root.val;
path.push(root.val);
if(cur === sum && !root.left && !root.right){
res.push(path.slice(0));
}
root.left && dfs(cur,sum,root.left,path,res);
root.right && dfs(cur,sum,root.right,path,res);
path.pop();
}
var pathSum = function(root, sum) {
if(!root) return [];
let res = [],path = [],cur = 0;
dfs(cur,sum,root,path,res);
return res;
};
Путь в бинарном дереве, который суммируется со значением
Введите бинарное дерево и целое число, выведите все пути в бинарном дереве, где сумма значений узлов является входным целым числом. От корневого узла дерева вниз к узлам, пройденным листовыми узлами, формируется путь.
// 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)
1. dfs + 回溯
2. 深度搜索路径,将路径中的每个节点值相加,路径存入缓存,直到遍历到最深处
3. 比较当前值是否为目标值,如果是将缓存的路径加入结果数组,如果不是则回退到上一个节点
function dfs(root,expectNumber,cur,path,result) {
cur += root.val;
path.push(root);
if(cur === expectNumber && root.left === null && root.right === null){
result.push(path.slice(0));
}
root.left && dfs(root.left,expectNumber,cur,path,result);
root.right && dfs(root.right,expectNumber,cur,path,result);
//重要
path.pop();
}
function FindPath(root, expectNumber)
{
let result = [],path = [],cur = 0;
if(!root) return result;
dfs(root,expectNumber,cur,path,result);
return result;
}
Максимальная сумма путей в двоичном дереве
учитываяне пустойДвоичное дерево, возвращающее максимальную сумму путей.
В этой задаче путь определяется как последовательность от любого узла дерева к любому узлу. тропинкасодержит по крайней мере одинузел, и не обязательно через корневой узел.
var maxPathSum = function(root) {
let max = -Infinity;
function dfs(root){
if(!root) return 0;
let l = Math.max(dfs(root.left),0);
let r = Math.max(dfs(root.right),0);
max = Math.max(max,l + r + root.val);
return Math.max(l,r)+root.val;
}
dfs(root);
return max;
};
разное
Количество различных деревьев бинарных индексов
卡塔兰数
dp[0] = 1
dp[i] = dp[i-1] * (4 * i + 2) / (i + 2);
var numTrees = function(n) {
if(!n) return 0;
let dp = [1];
for(let i = 1;i < n;i++){
dp[i] = dp[i-1] * (4 * i + 2) /(i + 2);
}
return dp[n-1];
};
В соответствии с деревом зависимостей js выведите массив разумного порядка упаковки (вопросы интервью с Али)
function resolve(tree){
let len = tree.require.length,queue = [];
for(let i = 0;i < len;i++){
queue.push([]);
}
tree = flatten(tree);
let head = tree.name;
for(let key in tree){
let k = Number(key.slice(8,9));
Object.keys(tree[key]).length && queue[k].push(tree[key])
}
let res = [];
for(let i = queue.length-1;i >= 0;i--){
for(let j = queue[i].length-1;j >= 0;j--){
res.indexOf(queue[i][j]) === -1 && res.push(queue[i][j]);
}
}
return res;
}
function flatten(input) {
let res = {};
let re = function(obj,key){
if(obj instanceof Object && !(obj instanceof Array)){
let empty = true;
for(let i in obj){
re(obj[i],key ? `${key}.${i}` : i)
}
if(empty && key){
res[key] = {};
}
}else if(obj instanceof Array){
if(obj.length){
for(let i = 0;i < obj.length;i++){
re(obj[i],key ? `${key}[${i}]` : i)
}
}else{
res[key] = [];
}
}else{
if(obj !== undefined && obj !== null){
res[key] = obj;
}
}
};
re(input,'');
return res;
}
var tree1 = {
name: 'main.js',
require: [{
name: 'A.js'
}, {
name: 'B.js'
}] }
var tree2 = {
name: 'page.js',
require: [{
name: 'A.js',
require: [{
name: 'B.js',
require: [{
name: 'C.js'
}]
}]},
{
name: 'D.js',
require: [{
name: 'C.js'
}, {
name: 'E.js'
}]
}] }
resolve(tree1) // ['A.js', 'B.js', 'main.js']
resolve(tree2) // ['C.js', 'E.js', 'D.js', 'B.js', 'A.js', 'page.js']
Введите целочисленный массив, чтобы определить, является ли массив результатом обхода двоичного дерева поиска в обратном порядке. Если да, выведите Yes, иначе выведите No. Предположим, что любые два числа входного массива отличны друг от друга.
1. 后序遍历的最后一个节点为根节点
2. 二叉索引树右子树大于根节点,左子树小于根节点,所以可以用根节点将树分为两颗子树
3. 二叉索引树的子树也是二叉索引树,所以分别对子树进行判断,直到遍历到最后一个节点
var verifyPostorder = function(postorder) {
if(!postorder.length) return true;
let tail = postorder.pop();
let key = postorder.length;
for(let i = 0;i < postorder.length;i++){
if(postorder[i] > tail){
key = i;
break;
}
}
for(let i = key+1;i < postorder.length;i++){
if(postorder[i] < tail){
return false;
}
}
return verifyPostorder(postorder.slice(0));
};
Введите двоичное дерево поиска, преобразуйте двоичное дерево поиска в отсортированный двусвязный список
var treeToDoublyList = function(root) {
if(!root) return null;
let head = null,tail = null,pre = null;
function dfs(root){
if(!root) return null;
dfs(root.left);
//第一个节点作为头节点
if(!pre) head = root;
//将上一个节点的后继指针指向当前节点
else pre.right = root;
//将当前指针的前驱指针指向上一个节点
root.left = pre;
//更新上一个节点
pre = root;
//更新尾部节点
tail = root;
dfs(root.right);
}
dfs(root);
//首尾连接
head.left = tail;
tail.right = head;
return head;
};
Развернуть бинарное дерево в связанный список
前序遍历,将右子树放到左子树最右叶子节点的后面,将左子树放到右子树上,左子树置空
var flatten = function(root) {
function dfs(root){
if(!root) return;
dfs(root.left);
dfs(root.right);
let pre = root.left;
if(pre){
//获取左子树最右叶子节点
while(pre.right){
pre = pre.right;
}
//将右子树放在左子树最右右子节点后面
pre.right = root.right;
//将新构建的左子树放在右子树上
root.right = root.left;
//左子树置空
root.left = null;
}
}
dfs(root);
return root;
};
хеш-таблица
Можно использовать в интервьюhashmap
Часто есть лучшие решения для решения проблем, ноhashmap
Это одно из самых простых решений, чтобы думать и писать
дневная температура
На основе списка дневной температуры, пожалуйста, создайте список заново, и вывод для соответствующего местоположения будет заключаться в том, как долго ждать, пока температура не превысит количество дней для этого дня. Если после этого он не поднимется, используйте 0 вместо этого в этой позиции.
Например, учитывая список температур = [73, 74, 75, 71, 69, 72, 76, 73], ваш вывод должен быть [1, 1, 4, 2, 1, 1, 0, 0].
Совет: Длина списка температур находится в диапазоне [1, 30000]. Каждое значение температуры воздуха указано в градусах Фаренгейта и является целым числом в диапазоне [30, 100].
var dailyTemperatures = function(T) {
let res = [],len = T.length;
while(len--){
res.push(0);
}
for(let i = 0;i < T.length;i++){
for(let j = i+1;j < T.length;j++){
if(T[j] <= T[i]){
res[i]++;
if(j === T.length-1) res[i] = 0;
}else{
res[i]++;
break;
}
}
}
return res;
};
группировка анаграмм
Учитывая массив строк, сгруппируйте анаграммы вместе. Алфавитные анаграммы — это цепочки из одних и тех же букв, но в разном расположении.
var groupAnagrams = function(strs) {
if(!strs.length) return [];
let str = strs.slice(0),res = [];
strs = strs.map(x => x.split('').sort().join(''));
let map = new Map();
for(let i = 0;i < strs.length;i++){
map.hasOwnProperty(strs[i]) ? map[strs[i]].push(str[i]) : (map[strs[i]] = [str[i]]);
}
for(let key in map){
res.push(map[key]);
}
return res;
};
и является подмассивом K
Учитывая массив целых чисел и целое число **k, вам нужно найти сумму в этом массиве какkколичество последовательных подмассивов
var subarraySum = function(nums, k) {
if(!nums.length) return 0;
let res = 0;
for(let i = 0;i < nums.length;i++){
let cur = 0;
for(let j = i;j < nums.length;j++){
cur += nums[j];
if(cur === k) res++;
}
}
return res;
};
Топ K высокочастотных элементов
Учитывая непустой массив целых чисел, вернуть частоту до возникновенияkвысокий элемент
var topKFrequent = function(nums, k) {
if(!nums.length) return [];
let map = new Map();
for(let i = 0;i < nums.length;i++){
map.has(nums[i]) ? map.set(nums[i],map.get(nums[i])+1) : map.set(nums[i],1);
}
let values = [],res = [];
for(let [k,i] of map){
values.push(i);
}
values.sort((x,y) => y-x);
values = values.slice(0,k);
for(let [k,i] of map){
if(values.indexOf(i) !== -1){
res.push(k);
}
}
return res;
};
Все числа в массиве длины n находятся в диапазоне от 0 до n-1. Некоторые числа в массиве повторяются, но я не знаю, сколько чисел повторяется. Также не знаю, сколько раз повторяется каждое число.
// 请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
function duplicate(numbers, duplication)
{
let map = new Map();
for(let i = 0;i < numbers.length;i++){
map.has(numbers[i]) ? map.set(numbers[i],map.get(numbers[i]) + 1) : map.set(numbers[i],1);
if(map.get(numbers[i]) > 1){
duplication[0] = numbers[i];
return true;
}
}
return false;
}
Найдите первый символ, который встречается в строке только один раз (0
// 如果没有则返回 -1(需要区分大小写).
function FirstNotRepeatingChar(str)
{
let map = new Map();
for(let key of str){
map.has(key) ? map.set(key,map.get(key)+1) : map.set(key,1);
}
for(let [key,value] of map){
if(value === 1) return str.indexOf(key);
}
return -1;
}
Подсчет простых чисел
// 如果没有则返回 -1(需要区分大小写).
function FirstNotRepeatingChar(str)
{
let map = new Map();
for(let key of str){
map.has(key) ? map.set(key,map.get(key)+1) : map.set(key,1);
}
for(let [key,value] of map){
if(value === 1) return str.indexOf(key);
}
return -1;
}
Подсчитать все меньшие, чем неотрицательные целые числаnКоличество простых чисел
Учитывая диапазон значений для просеивания n, найдите простые числа в пределах sqrt (n), сначала просейте с 2, то есть оставьте 2 и удалите кратные 2; затем используйте следующее простое число, которое равно 3, просейте , до 3, и числа, кратные 3, удаляются; затем следующее простое число 5 используется для просеивания, остается 5, и числа, кратные 5, удаляются; повторяем
var countPrimes = function(n) {
let count = 0;
let signs = new Uint8Array(n);
for (let i = 2; i < n; i++) {
// 如果是素数
if (!signs[i - 1]) {
count++;
// 去除当前素数的n次项
for (let j = i * i; j <= n; j += i) {
signs[j - 1] = true;
}
}
}
return count;
};
Звоните на номера, содержащие только простые множители 2, 3 и 5, некрасивые номера
Возвращает k-е уродливое число
//例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
1. 0-6都是丑数,返回其值即可
2. 使用t1-t3表示2,3,5公因子的个数,每次取最小的公因子值,初值为1
function GetUglyNumber_Solution(index)
{
if(index < 7) return index;
let res = [1];
let t2 = 0,t3 = 0,t5 = 0;
for(let i = 1;i < index;i++){
res[i] = Math.min(res[t2]*2,res[t3]*3,res[t5]*5);
res[i] === res[t2]*2 && t2++;
res[i] === res[t3]*3 && t3++;
res[i] === res[t5]*5 && t5++;
}
return res[index-1]
}
самая длинная подстрока без повторяющихся символов
Дана строка, пожалуйста, найдите ту, которая не содержит повторяющихся символовсамая длинная подстрокадлина.
var lengthOfLongestSubstring = function(s) {
if(!s.length) return '';
let sub = '',res = '';
for(let i = 0;i < s.length;i++){
if(sub === ''){
sub += s[i];
if(i === s.length-1 && res.length < sub.length) res = sub;
}else{
if(sub.indexOf(s[i]) === -1){
sub += s[i];
if(i === s.length-1 && res.length < sub.length) res = sub;
}else{
if(sub.length > res.length) res = sub;
sub = sub.substr(sub.indexOf(s[i])+1) + s[i];
}
}
}
return res.length;
};
стеки и очереди
Стек удовлетворяет принципу «первый вошел, последний вышел», а очередь удовлетворяет принципу «первый пришел — первый вышел».
Используйте два стека для реализации очереди для выполнения операций Push и Pop в очереди. Элементы в очереди имеют тип int
1. 用出入栈进行模拟
2. 进队列全部添加到入栈中
3. 出队列检查出栈是否为空,不为空则将栈顶元素出栈;为空则先将入栈中的所有元素压入出栈
let in_stack = [],out_stack = [];
function push(value) {
in_stack.push(value);
}
function pop() {
if(!out_stack.length){
while(in_stack.length > 0){
out_stack.push(in_stack.pop())
}
}else{
return out_stack.pop();
}
}
Определите структуру данных стека, пожалуйста, реализуйте функцию min в этом типе, которая может получить наименьший элемент, содержащийся в стеке (временная сложность должна быть O (1)
1. 使用辅助栈存最小值
2. 入栈时检查元素是否为最小值,若是则压入主栈和辅助栈
3. 出栈时检查主栈栈顶元素是否与辅助栈一致,若是则一起弹出
// 注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。
let stack1 = [],stack2 = [];
function push(value) {
if(value <= Math.min(...stack1) || stack1.length === 0){
stack1.unshift(value);
stack2.unshift(value);
}else{
stack1.unshift(value)
}
}
function pop() {
if(stack1.length > 0) {
if (stack1[0] === stack2[0]) {
stack1.shift();
stack2.shift();
} else {
stack1.shift();
}
}
}
function top() {
if(stack1.length > 0) {
return stack1[0];
}
}
function min() {
if(stack2.length > 0) {
return stack2[0];
}
}
Максимальное значение скользящего окна
задан массивnums
и размер скользящего окнаk
, найти максимальное значение во всех скользящих окнах.
1. 维护一个单调的双向队列
2. 新增元素与队尾元素比较,比队尾小直接添加,比队尾大,弹出队尾,直到找到该元素合适的位置
3. 每次将双向队列中队首元素添加到结果中
var maxSlidingWindow = function(nums, k) {
if (k === 0) return [];
const length = nums.length;
if (length === 0) return [];
const deque = [];
for (let i = 0; i < k; ++i) {
cleanDeque(deque, nums, i, k);
deque.push(i);
}
const res = [];
res.push(nums[deque[0]]);
for (let i = k; i < length; ++i) {
cleanDeque(deque, nums, i, k);
deque.push(i);
res.push(nums[deque[0]]);
}
return res;
};
function cleanDeque(queue, arr, cur, k) {
// 如果双向队列中,包含不是滑动窗口内的数,直接出队
if (queue.length && cur >= k + queue[0]) {
queue.shift();
}
while (queue.length && arr[idx] > nums[queue[queue.length - 1]]) {
queue.pop();
}
}
допустимые скобки
Учитывая строку, содержащую только '(', ')', '{', '}', '[', ']', проверьте, является ли строка допустимой.
Действительная строка должна удовлетворять:
Открывающие скобки должны быть закрыты закрывающими скобками того же типа. Левые скобки должны быть закрыты в правильном порядке.
左括号入栈,右括号与栈顶比较是否匹配,匹配弹出栈顶,不匹配return false
查看栈是否为空
var isValid = function(s) {
if(!s.length) return true;
let stack = [];
for(let i = 0;i < s.length;i++){
if(s[i] === '(' || s[i] === '{' || s[i] === '['){
stack.unshift(s[i]);
}else{
if(s[i] === ')'){
if(stack[0] === '(') stack.shift();
else{
return false;
}
}else if(s[i] === ']'){
if(stack[0] === '[') stack.shift();
else{
return false;
}
}else if(s[i] === '}'){
if(stack[0] === '{') stack.shift();
else{
return false;
}
}
}
}
return stack.length === 0;
};
Декодирование строк
Дана строка, которая проходит через закодированную строку.
Правило кодирования: k[encoded_string], что означает, что encoded_string внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно будет положительным целым числом.
Можно предположить, что входная строка всегда действительна, во входной строке нет лишних пробелов, а входные квадратные скобки всегда правильно сформированы.
Кроме того, вы можете подумать, что исходные данные не содержат чисел, все числа просто представляют количество повторений k , например, не появится ввод, такой как 3a или 2[4].
var decodeString = function(s) {
// 用两个栈来存放当前状态,前者是重复次数,后者是累积字符串
let repetStack=[],resStack=[];
//拼接字符串
let resStr = "";
//表示重复次数
let repet = 0;
// 遍历s
for(let i=0;i<s.length;i++){
let cur = s.charAt(i);
if(cur == '['){
//双双压入栈中,保存当前状态
repetStack.push(repet);
resStack.push(resStr);
//置空,准备下面的累积
repet = 0;
resStr = "";
}else if(cur == ']'){
// 取出当前重复次数栈中的值,也就是当前字符串的重复次数
let count = repetStack.pop();
// 根据重复次数生成重复字符串,赋值给temp,和resStr拼接
let temp = "";
for(let i = 0;i<count;i++){
temp += resStr;
}
// 和前面已经求得的字符串进行拼接
resStr = resStack.pop() + temp;
}else if(cur>='0' && cur<='9'){
// repet累积
repet = repet*10 + (cur-'0');
}else{
//字符累积
resStr += cur;
}
}
return resStr;
};
Реконструкция когорт по росту
Предположим, что в очереди стоит неупорядоченная группа людей. Каждый человек представлен парой целых чисел (h, k), где h — рост человека, а k — количество людей, опережающих этого человека и чей рост больше или равен h. Напишите алгоритм для восстановления этой очереди.
1. 按升高降序,身高相同的按人数升序排列
2. 将队列的每个元素按序插入到索引位置
var reconstructQueue = function(people) {
if(!people) return [];
people.sort((x,y)=>{
return x[0] === y[0] ? x[1]-y[1] : y[0] - x[0];
});
let res = [];
for(let i = 0;i < people.length;i++){
res.splice(people[i][1],0,people[i]);
}
return res;
};
SPIX Expression Transfic
//数字直接添加到result
//栈空,运算符直接入栈
//遇到左括号直接入栈,遇到右括号栈顶元素添加到result中然后弹栈,依次循环直到遇到左括号,然后将左括号弹栈
//遇到运算符,判断运算符与栈顶元素的优先级,将所有优先级大于等于该运算符的栈顶弹栈,然后入栈该运算符
//将栈中剩余的字符添加到result中
function toPoland(str){
let stack = [],result = '';
for(let i = 0;i < str.length;i++){
if(!Object.is(Number(str[i]),NaN)){
result += str[i];
}else if(stack.length === 0 && Object.is(Number(str[i]),NaN)){
result += ' ';
stack.push(str[i]);
}else if(str[i] === '('){
stack.push(str[i])
}else if(str[i] === ')'){
result += ' ';
while(stack[stack.length-1] !== '('){
result += stack.pop();
}
stack.pop();
}else if(str[i] === '*' || str[i] === '/'){
while(stack[stack.length-1] === '*' || stack[stack.length-1] === '/'){
result += ' ' + stack.pop();
}
result += ' ';
stack.push(str[i]);
}else if(str[i] === '+' || str[i] === '-'){
while(stack[stack.length-1] === '*' || stack[stack.length-1] === '/' || stack[stack.length-1] === '+' || stack[stack.length-1] === '-'){
result += ' ' + stack.pop();
}
result += ' ';
stack.push(str[i]);
}
}
while(stack.length){
result += ' ' + stack.pop();
}
return result;
}
Вычислить постфиксные выражения
1. 数字入栈
2. 运算符,栈顶作为右操作数,次栈顶作为左操作数
3. 将运算结果入栈
4. 栈最后一个值即为结果
function CalcRPN(str) {
let stack = [];
let num = '';
for(let i = 0;i < str.length;i++){
if(str[i] === ' '){
if(num !== '') stack.push(Number(num));
num = '';
}else if(!Object.is(Number(str[i]),NaN)){
num += str[i];
}else if(str[i] === '+'){
let right = stack.pop();
let left = stack.pop();
stack.push(left + right);
}else if(str[i] === '-'){
let right = stack.pop();
let left = stack.pop();
stack.push(left - right);
}else if(str[i] === '*'){
let right = stack.pop();
let left = stack.pop();
stack.push(left * right);
}else if(str[i] === '/'){
let right = stack.pop();
let left = stack.pop();
stack.push(left / right);
}
}
return stack.pop();
}
Введите две целочисленные последовательности, первая последовательность представляет собой последовательность выталкивания стека, оцените, может ли вторая последовательность быть последовательностью всплывающих окон стека. Предположим, что все числа, помещенные в стек, не равны.
1. 模拟出栈的过程
2. 变量push栈,每次将一个元素压入辅助栈
3. 判断辅助栈是否为空的同时,pop栈的栈顶是否与辅助栈栈顶元素相同,如果都满足则两者出栈
4. 最后判断辅助栈是否为空
// 例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
// (注意:这两个序列的长度是相等的)
function IsPopOrder(pushV, popV) {
let stack = [],k = 0;
for(let i = 0;i < pushV.length;i++){
stack.unshift(pushV[i]);
while(stack[0] && popV[k] && stack[0] === popV[k]){
stack.shift();
k++;
}
}
return stack.length === 0;
}
K-й по величине элемент в массиве
// 优先队列。。写的有点蛋疼
var findKthLargest = function(nums, k) {
let queue = [];
for(let i = 0;i < nums.length;i++){
if(queue.length < k) {
let pos = 0;
while(pos < k) {
if(queue[pos] === undefined) {
queue[pos] = nums[i];
break;
} else {
if(nums[i] > queue[pos]) {
queue.splice(pos,0,nums[i]);
break;
}
}
pos++;
}
} else {
if(nums[i] > queue[k-1]) {
let pos = 0;
while(pos < k) {
if(nums[i] > queue[pos]) {
queue.splice(pos,0,nums[i]);
queue.pop();
break;
}
pos++;
}
}
}
}
return queue[k-1];
};
связанный список
обратно связанный список
function ReverseList(pHead)
{
// write code here
if(pHead === null || pHead.next === null) return pHead;
let pre = null,nex = null;
while(pHead !== null){
nex = pHead.next;
pHead.next = pre;
pre = pHead;
pHead = nex;
}
return pre;
}
Репликация сложных связанных списков
Пожалуйста, реализуйте функцию, которая копирует сложный связанный список. В сложном связанном списке в дополнение к следующему указателю, указывающему на следующий узел, каждый узел также имеет случайный указатель, указывающий на любой узел в связанном списке или нуль.
function Clone(pHead)
{
// write code here
if(pHead === null) return pHead;
let p1 = pHead;
while(p1 !== null){
let node = new RandomListNode(p1.label);
node.next = p1.next;
p1.next = node;
p1 = node.next;
}
p1 = pHead;
while(p1 !== null){
let node = p1.next;
if(p1.random) node.random = p1.random.next;
p1 = node.next;
}
p1 = pHead;
let p2 = pHead.next;
while(p1.next !== null){
let node = p1.next;
p1.next = node.next;
p1 = node;
}
return p2;
}
Объединить два отсортированных связанных списка
Объединить два восходящих связанных списка в новый восходящий связанный список и вернуться. Новый связанный список формируется путем объединения всех узлов данных двух связанных списков.
var mergeTwoLists = function(l1, l2) {
if(!l1) return l2;
if(!l2) return l1;
if(!l1 && !l2) return null;
if(l1.val <= l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
};
круговой связанный список
Учитывая связанный список, определите, есть ли цикл в связанном списке
var hasCycle = function(head) {
if(!head || !head.next || !head.next.next) return false;
let fast = head.next.next,slow = head.next;
while(fast !== slow){
if(fast === null || fast.next === null) return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
};
Круговой связанный список II
Учитывая связанный список, вернуть первый узел, где связанный список начинает входить в кольцо. Если связанный список не имеет цикла, вернутьnull
var detectCycle = function(head) {
if(!head || !head.next) return null;
let fast = head.next.next,slow = head.next,p1 = head;
while(fast !== null && fast !== slow){
if(fast.next) fast = fast.next.next;
else fast = null;
slow = slow.next;
}
if(fast === null) return null;
else{
while(p1 !== slow){
p1 = p1.next;
slow = slow.next;
}
return slow;
}
};
Пересекающийся связанный список
Напишите программу, которая находит начальный узел в месте пересечения двух односвязных списков.
var getIntersectionNode = function(headA, headB) {
var pA = headA;
var pB = headB;
while(pA !== pB){
pB = pB? pB.next: headA;
pA = pA? pA.next: headB;
}
return pA;
};
Скопировать связанный список со случайным указателем
В связном списке каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в связанном списке или на пустой узел.
var copyRandomList = function(pHead) {
if(pHead === null) return pHead;
let p1 = pHead;
while(p1 !== null){
let node = new Node(p1.val);
node.next = p1.next;
p1.next = node;
p1 = node.next;
}
p1 = pHead;
while(p1 !== null){
let node = p1.next;
if(p1.random) node.random = p1.random.next;
p1 = node.next;
}
p1 = pHead;
let p2 = pHead.next;
while(p1.next !== null){
let node = p1.next;
p1.next = node.next;
p1 = node;
}
return p2;
};
нить
сочетание букв номера телефона
задано число, содержащее только числа2-9
, возвращает все возможные комбинации букв, которые он может представлять.
Отображение цифр в буквы дается следующим образом (так же, как клавиши телефона). Обратите внимание, что 1 не соответствует ни одной букве.
// 这个回溯可以说很巧妙了,lc上有详解
var letterCombinations = function(digits) {
if(!digits) return [];
let map = {
'2': 'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'
};
let res = [];
function dfs(index,path) {
if(index === digits.length) {
res.push(path);
return;
}
for (let i = 0;i < map[digits[index]].length;i++) {
path += map[digits[index]][i];
dfs(index+1,path.slice());
path = path.slice(0, path.length-1);
}
}
dfs(0,'');
return res;
};
Палиндромная подстрока
Учитывая строку, ваша задача состоит в том, чтобы подсчитать, сколько палиндромных подстрок содержится в этой строке.
Подстроки с разными начальными или конечными позициями, даже если они состоят из одних и тех же символов, считаются отдельными подстроками.
var countSubstrings = function(s) {
let s2 = s.split('').reverse().join('');
let sum = 0;
const len = s.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j <= len; j++) {
if (s.substr(i, j - i) === s2.substr(len - j, j - i)) {
sum += 1
}
}
}
return sum;
};
Генерация кронштейна
количествоnПредставляет логарифм, порождающий круглые скобки. Пожалуйста, разработайте функцию, которая может генерировать все возможные иЭффективныйкомбинация скобок
var generateParenthesis = function(n) {
if(!n) return [];
let res = [];
function dfs(subs,left,right,n){
if(left === n && right === n){
res.push(subs);
return;
}
if(left < right){
return;
}
left < n && dfs(subs+'(',left+1,right,n);
right < n && dfs(subs+')',left,right+1,n);
}
dfs('',0,0,n);
return res;
};
самый длинный общий префикс
Напишите функцию для поиска самого длинного общего префикса в массиве строк.
Возвращает пустую строку, если не существует общего префикса""
var longestCommonPrefix = function(strs) {
if(!strs.length) return '';
strs.sort();
let a = strs[0],b = strs[strs.length-1],res = '';
for(let i = 0;i < a.length;i++){
if(i < b.length && a[i] === b[i]){
res += a[i];
}else break;
}
return res;
};
расшифровка пароля
Сяо Мин получил от босса таблицу паролей, в которой говорилось, что если он откроет секрет в таблице паролей, то сможет получить повышение по службе и повысить свою зарплату, выиграть Бай Фумэй и достичь вершины своей жизни. Эта таблица паролей представляет собой CSV-файл, а данные в ней состоят из цифр (без десятичной точки) и букв. Сяо Мину необходимо извлечь числа из каждых данных (например,1a2b3c
полученный после экстракции123
, извлеченное число рассматривается как десятичное число в целом), а элементы с нечетными значениями добавляются для разгадки секрета. Пожалуйста, реализуйте функцию sum, чтобы помочь Xiaomi завершить эту работу.
function sum(input: string) {
return input.split(/[,\n]/)
.map(item => Number(item.replace(/[a-z]/ig, "")))
.filter(num => num % 2 === 1)
.reduce((a, b) => a + b)
}
Разобрать параметр URL как объект
function parseUrl(url){
url = decodeURIComponent(url);
let strs = url.slice(url.indexOf('?')+1).split('&');
return strs.reduce((x,y)=>{
let key = y.split('=')[0];
let value = Object.is(Number(y.split('=')[1]),NaN) ? y.split('=')[1] : Number(y.split('=')[1]);
x[key] = value;
return x;
},{});
}
Реализовать шаблонизатор
const template = 'there are ${count} ${name} on the ${place}.';
function parse(template,obj){
let reg = /\$\{((\w|_|\$)*)\}/g;
let keys = template.match(reg).map(x => x.slice(2,x.length-1));
let value = keys.map(i => obj[i] === undefined ? '' : String(obj[i]));
return template.replace(reg,()=> value.shift());
}
console.log(parse(template, {count: 2, name: 'apples', place: 'table'}, create));
//there are 2 apples on the table.
Строка произвольного тега HTML в файл json
Предыдущий код ошибки был изменен, и общая идея выглядит следующим образом:
- Удалите строку HTML в и обработайте ее как массив
- Извлечь древовидную структуру
- Преобразование древовидной структуры в JSON
const str1 = '<div>1<span>2<a>3</a>4</span>5<span>6<a>7</a>8<a>9</a>10</span>11</div>';
function Dom2JSON(str) {
str = str.split('<').map(x => x.split('>'));
let res = [],stack = [],temp = {},cur = {},key = 0;
// 获取树形结构
for(let i = 1;i < str.length; i++) {
if (str[i][0].indexOf('/') === -1) {
temp = {};
temp['key'] = key++;
temp['tag'] = str[i][0];
temp['value'] = str[i][1];
temp['children'] = [];
temp['parent'] = stack.length === 0 ? 0 : stack[0]['key'];
stack.unshift(temp);
} else {
cur = stack.shift();
// 当前元素为根元素时栈为空
stack.length !== 0 && (stack[0]['value'] = stack[0]['value'] + cur['value'] + str[i][1]);
res.unshift(cur);
}
}
// 使得遍历时索引与key值匹配
res = res.sort((x, y) => x['key'] - y['key']);
for (let i = res.length - 1;i > 0;i--) {
temp = {};
temp['tag'] = res[i]['tag'];
temp['value'] = res[i]['value'];
temp['children'] = res[i]['children'];
res[res[i]['parent']]['children'].unshift(temp);
}
res = res[0];
delete res['parent'];
delete res['key'];
return JSON.parse(JSON.stringify(res));
}
console.log(Dom2JSON(str1));
}
// 转换结果如下
// let res ={
// tag: "div",
// value: "1234567891011",
// children: [
// {
// tag: "span",
// value: "234",
// children: [
// {
// tag: "a",
// value: "3",
// children: [],
// }
// ],
// },
// {
// tag: "span",
// value: "678910",
// children: [
// {
// tag: "a",
// value: "7",
// children: [],
// },
// {
// tag: "a",
// value: "9",
// children: [],
// }
// ]
// }
// ]}
использованная литература
Откат рутинной шаблонной кисти leetcode
Восемь классических алгоритмов сортировки (иллюстрация + справочный исходный код)
Супер люблю и проверяю коллекцию~
Начало работы с топологической сортировкой (очень просто)