Найти хорошую работу LeetcodeTop100(Easy) с помощью JavaScript

внешний интерфейс алгоритм JavaScript регулярное выражение

Запиши этоleetcode top100

В этой части записывается только легкая сложность, потому что это легкая сложность, поэтому в основном ставьте ответ прямо.

1. two sum

Сумма двух чисел — находит два числа в неупорядоченном массиве, которые в сумме дают постоянное значение, возвращает нижний индекс

Поскольку необходимо вернуть нижний индекс, метод (NlogN) сначала сортировки, а затем сканирования с двумя указателями (спереди->назад, сзади->спереди) не работает. Так что выбирайте похожиеhashраствор формы;keyявляется значением массива,valueиндекс

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = {};
    nums.forEach((num, index) => map[num] = index);
    const len = nums.length;
    for(let i = 0; i < len; i++) {
        const otherIndex = map[target - nums[i]];
        if(otherIndex && otherIndex != i) {
            return [Math.min(i, otherIndex), Math.max(i, otherIndex)]
        }
    }
};

20. Valid Parentheses

Определить, содержит ли входная строка только(, ), {, }, [ and ]

  • Открывающая скобка должна быть закрыта скобкой того же типа.
  • Открывающие скобки должны быть закрыты в правильном порядке.
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const helpMap = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    for(let i = 0; i < s.length; i++) {
        const char = s[i];
        if(char in helpMap) {
            stack.push(helpMap[char]);
        } else if(char !== stack.pop()){
            return false;
        }
    }
    return stack.length === 0;
};

21. Merge Two Sorted Lists

Объединяет два сортировках связанных списков и возвращает их как новый связанный список. Новый связанный список должен быть выполнен путем сращивания узлов предыдущих двух связанных списков.

  • Решение 1. Рекурсия
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
  • Решение 2. Цикл
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    const newList = new ListNode(null);
    let newPointer = newList;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            newPointer.next = l1;
            l1 = l1.next;
        } else {
            newPointer.next = l2;
            l2 = l2.next;
        }
        newPointer = newPointer.next;
    }
    if (l1) newPointer.next = l1;
    if (l2) newPointer.next = l2;
    return newList.next;
};

35. Search Insert Position

Учитывая отсортированный массив и целевое значение, вернуть индекс, если цель найдена. Если нет, верните индекс, в который индекс был вставлен по порядку.

Вариант бинарного поиска

Обычно о рекурсии бинарного поиска пишут слишком много, вот версия, которая не использует рекурсию

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let start = 0, end = nums.length - 1;
    let mid = Math.ceil((end + start) / 2);
    while(nums[mid] !== target) {
        if(end <= start) {
            // 如果没有找到要看看插哪里
            return nums[end] < target ? end + 1 : end;
        }
        if(nums[mid] > target) {
            // 保护一下不要变成负的
            end = Math.max(mid - 1, 0);
        } else {
            // 保护一下不要越界
            start = Math.min(mid + 1, nums.length - 1);
        }
        mid = Math.floor((end + start) / 2);
    }
    return mid;
};

52. Maximum Subarray

Классическая задача: найти наибольшую сумму подпоследовательности в массиве

Решение: пройти каждый элемент массива от начала до конца, если сумма предыдущего элемента положительна, добавить значение этого элемента, чтобы продолжить поиск, если сумма предыдущего элемента отрицательна, этот элемент начинает новую сумму считать. И весь процесс должен обращать внимание на максимальное значение суммы обновления.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let cache = 0;
    let max = -Infinity;
    nums.forEach(num => {
        cache += num;
        if(cache > max) max = cache;
        if(cache < 0) cache = 0;
    })
    return max;
};

70. Climbing Stairs

Шаговые прыжки, классическое двойное проникновение

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = [0, 1, 2];
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n]
};

100. Same Tree

Определить, идентичны ли два бинарных дерева Плохой способ написания: напишите код в одну строку, используя короткое замыкание и другие функции, и обратите внимание на защиту значений.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    return (p || q) ? (p || {}).val === (q || {}).val && isSameTree((p || {}).left, (q || {}).left) && isSameTree((p || {}).right, (q || {}).right) : true
};

101. Symmetric Tree

Определить, является ли бинарное дерево зеркальным отображением Решение 1. Продолжайте писать строку

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return childIsSymmetric((root || {}).left, (root || {}).right);
};

function childIsSymmetric (left, right) {
    return (left || right) ? (left || {}).val === (right || {}).val && childIsSymmetric((left || {}).left, (right || {}).right) && childIsSymmetric((left || {}).right, (right || {}).left) : true;
}

Решение второе:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true;
    function areMirror(left, right) {
        if(!left && !right) return true;
        if((left && !right) || (right && !left)) return false;
        if(left.val != right.val) return false;
        return areMirror(left.left, right.right) && areMirror(left.right, right.left);
    }
    return areMirror(root.left, root.right);
};

104. Maximum Depth of Binary Tree

найти глубину бинарного дерева

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root, deep = 0) {
    if(!root) return deep;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};

121. Best Time to Buy and Sell Stock

Дан массив, где i-й элемент — цена данной акции в i-й день. Только одна покупка и продажа могут быть сделаны, чтобы максимизировать прибыль

Сначала установите максимальную прибыль и минимальную цену:

  • Если цена акции текущего дня меньше самой низкой цены, установите самую низкую цену на цену акции дня.
  • Если максимальная прибыль меньше, чем цена дня минус минимальная цена, то устанавливаем максимальную прибыль равной цене дня минус минимальная цена.
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(!prices.length) return 0;
    let minPrice = Infinity, maxProfit = -Infinity;
    prices.forEach(price => {
        if(price < minPrice) {
            minPrice = price;
        }
        if(maxProfit < (price - minPrice)) {
            maxProfit = (price - minPrice);
        }
    });
    return maxProfit;
};

136. Single Number

Классическая проблема, строка кода XOR для решения

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums){
    return nums.reduce((a,b) => { return a ^ b})；
}

141. Linked List Cycle

Определить, есть ли в связанном списке цикл, нельзя использовать дополнительное пространство Решение: используйте два указателя, быстрый указатель выполняет два шага каждый раз, а медленный указатель — один шаг каждый раз. Таким образом, каждый раз, когда быстрый указатель перемещается на один шаг дальше, чем медленный указатель, если есть кольцо, оно в конечном итоге встретится.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    let slow = head;
    let fast = head;

    while (fast) {
        slow = slow.next;
        fast = fast.next && fast.next.next;
        if (slow === fast && fast !== null) {
            return true;
        }
    }

    return false;
};

155. Min Stack

спроектировать опоруpush,pop,topи извлечь стек с наименьшим элементом в постоянное время.

  • push(x) -- поместить элемент x в стек
  • pop() -- удаляет элемент с вершины стека
  • top() -- получить верхний элемент
  • getMin() -- получить наименьший элемент в стеке

Оптимальное решение - O(1):

Что требует этот вопрос, так это реализовать стек, а операция изменения элементов стека - это толькоpop()а такжеpush(x), так что мы можемpushПри сохранении функции, аналогичнойтайникДа, запишите стек того, какой самый маленький элемент в это времяminStack. каждый разpush, обновить наштайник, на этот раз нужно только сравнить текущий элемент стека иminStackверхний элемент стека, затем сделайте небольшой толчокminStackТо есть это означает, что минимальное значение в этот момент должно быть наименьшим элементом в предыдущем стеке и в новом.

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    const minStackTop = this.minStack[this.minStack.length - 1];
    this.minStack.push(Math.min(x, minStackTop === undefined ? Infinity : minStackTop));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

160. Intersection of Two Linked Lists

Найдите узел в общем начале двух односвязных списков.

  • Если два связанных списка вообще не пересекаются, вернутьnull.
  • После возврата функции связанный список должен сохранить свою первоначальную структуру.
  • Можно предположить, что во всей звеньевой структуре петель нет.
  • Код выполняется за время O(n) и использует только память O(1).

image.png | left | 488x165
Как видно из приведенного выше рисунка, если указатели, используемые для обхода, встречаются на входе общедоступного узла связанного списка, то есть узлы, по которым ходят два указателя, имеют одинаковую длину, необходимо только перейти к связанный список B после обхода связанного списка A (переход узлов a + c + b), а затем связанный список B завершается и изменяется на связанный список A (остаются узлы b + c + a).

В то же время нам также приходится иметь дело с ситуацией, когда два связанных списка не имеют общего узла:

image.png | left | 244x161

Как показано на рисунке выше, после того, как указатель, начинающийся с A, прошел узлы a + b, указатель, начинающийся с B, также прошел узлы b + a, поэтому они оба находятся после одного шага в это время.undefined, то есть, если два связанных списка не имеют общего узла, пока два указателя считаютсяundefinedПросто знаю.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let nodeA = headA, nodeB = headB;
    while(nodeA !== nodeB) {
        nodeA = nodeA ? nodeA.next : headB;
        nodeB = nodeB ? nodeB.next : headA;
    }
    return nodeA || null;
};

169. Majority Element

Найдите количество вхождений в массив больше, чем `⌊ n/2 ⌋ Этот вопрос немного интереснее, и даются следующие решения:

  • Поскольку это больше половины, вы можете напрямую отсортировать и увидеть число в средней позиции.
  • Алгоритм голосования Мура: «Каждый раз находить другую пару элементов и удалять их из массива до тех пор, пока массив не станет пустым или будет содержать только один элемент».
  • Boyer-Moore Algorithm(алгоритм голосования по большинству): записать текущую переменную большинстваAи его номерnumA, при обходе, если текущий элемент и элемент записиAравно, тоnumAПрибавьте 1, если не равно, тоnumAВычесть 1. еслиnumAноль, обновитьAи сброситьnumA. Суть такова: при обходе массива, еслиnumAОн равен 0, что указывает на то, что в настоящее время нет элементов-кандидатов, то есть более половины элементов не были найдены в предыдущем процессе обхода. Тогда, если больше половины элементовAсуществует, тоAВ оставшихся подлочках количество вхождений также должно превышать половину. Таким образом, мы можем преобразовать оригинальную проблему в его подблемы.Вот визуальный процесс 
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let result, count = 0
    nums.forEach(num => {
        if(result !== num) {
            if(count === 0) {
                count = 1;
                result = num;
            } else {
                count--;
            }
        } else {
            count++
        }
    });
    return result;
};

198. House Robber

Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме хранится определенная сумма денег, и единственное ограничение, которое мешает вам грабить, это: Поскольку дома соединены системой безопасности, если два соседних дома взломаны в одну и ту же ночь, они автоматически свяжутся с полицией. следовательно, не может грабить соседние дома. Имея список неотрицательных целых чисел, представляющих сумму денег на дом, вычислите максимальную сумму денег, которую можно ограбить следующей ночью, не поставив в известность полицию.

ДП: Для i-й комнаты наш выбор воровать или не воровать

  • Если принято решение украсть, то i-1-я комната не должна быть украдена, тогда этот шагdp[i] = nums[i-1] + dp[i -2], предполагатьdp[i]Указывает максимальную сумму денег, накопленную при ограблении i-го дома
  • Если вы не украли его, то не имеет значения, украли ли вы его уже на предыдущем шаге.dp[i] = dp[i -1]
  • следовательноdp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1] ) 
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(!nums.length) return 0;
    const dp = [nums[0]];
    for(let i = 1; i < nums.length; i++){
        dp[i] = Math.max(dp[i - 1], (dp[i - 2] || 0) + nums[i]);
    }
    return dp[nums.length - 1];
};

206. Reverse Linked List

обратно связанный список

Может честно зацикливаться/рекурсивно:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    if (!head) return head;
    let start = head;
    let end = head
    while (end.next) {
        const node = end.next;
        end.next = node.next;
        node.next = start;
        start = node;
    }
    return start;
}

Вы также можете поиграть с ним:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head, pre) {
    if(!head) return head
    const next = head.next;
    head.next = pre || null
    return next ? reverseList(next, head) : head;
};

226. Invert Binary Tree

Инвертировать бинарное дерево

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return [];
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root
};

234. Palindrome Linked List

Чтобы определить, является ли связанный список палиндромом, требуется O(n) времени и O(1) пространства.

Этот вопрос насильственное решение состоит в том, чтобы перевести список «Латтен», чтобы перейти к строке, затем см. Если оно верно, соответствует требованиям времени сложности, но не соответствует требованиям пространственной сложности.

Если требуется пространство O (1), это можно сделать только из самого связанного списка. Сначала оцените палиндром не более чем с двух сторон к середине или от середины к обеим сторонам. Поскольку мы можем сделать сам связанный список, подумайте о том, чтобы сделать связанный список доступным в обратном направлении (поскольку требуется пространство O (1), поэтому его нельзя напрямую преобразовать в двусвязный список). Поскольку мы можем заставить связанный список двигаться только в одном направлении, мы можем думать о выборе пути от середины к обеим сторонам, а левая сторона — вперед (pre), назад вправо (next).

Итак, как нам найти средний узел — средний узел — это половина связанного списка, тогда мы используем быстрый указатель, чтобы делать два шага за раз, и медленный указатель, чтобы делать один шаг за раз, затем, когда быстрый указатель достигает конца, медленный указатель должен перейти в середину связанного списка. При этом обратите внимание на то, чтобы различать, является ли длина связанного списка нечетной или четной: если она нечетная, узел в середине не нужно оценивать, а два узла до и после него следует использовать для начать сравнение.

Окончательный код выглядит следующим образом:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(!head) return true;
    if(!head.next) return true;
    let fast = head.next, slow = head;
    let pair = null;
    while(fast != null && fast.next != null) {
        slow.next.pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    if(!fast || fast.next) {
        // 奇数
        pair = slow.next;
        slow = slow.pre;
    } else {
        // 偶数
        pair = slow.next;
    }
    while(pair) {
        if(pair.val !== slow.val) return false;
        pair = pair.next;
        slow = slow.pre;
    }
    return true;
};

283. Move Zeroes

Имея массив nums, напишите функцию для перемещения всех нулей в его конец, сохраняя при этом относительный порядок ненулевых элементов. Дополнительные требования:

  • Вы должны, не делая копию массива подна местесделай это
  • Минимизируйте общее количество операций. Идеи:
  • Операция минимизации: операция завершается в процессе однократного перемещения, и дополнительная операция перемещения не требуется.
  • Обратите внимание на количество нулейzeroesNums, затем продвигайтесь вперед на каждое ненулевое числоzeroesNums, и, наконец, заполните нулем в конце массива
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let zeroesNums = 0;
    nums.forEach((num, index) => {
        if(num === 0) {
            zeroesNums++;
        } else {
            nums[index - zeroesNums] = num;
        }
    });
    for(let i = nums.length - 1; zeroesNums > 0; i--) {
        nums[i] = 0;
        zeroesNums--;
    }
};

437. Path Sum III

Учитывая бинарное дерево, в котором каждый узел является целым числом (может быть положительным или отрицательным), найдите, сколько путей в сумме дает заданное значение. Обратите внимание, что путь не обязательно должен начинаться или заканчиваться корнем или концом, а должен идти вниз (т. е. идти только от родителя к дочернему).

Решение первое: Решение методом грубой силы с использованием BFS и рекурсии для поиска подходящих путей. Следует отметить, что этот метод не использует кэш, то есть все узлы пути повторно проходятся при вычислении суммы каждого пути. Временная сложность O(n²)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) return 0;
    let result = 0;
    const queue = [root];
    while(stack.length) {
        const node = queue.shift();
        result += reslove(node, sum);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result
};

function reslove(root, sum) {
    if(!root) return 0;
    let result = 0;
    if(sum === root.val) result++;
    return result + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}

Решение второе: Если вы не хотите использоватьqueue, вы также можете использовать рекурсию для прямого поиска

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) return 0;
    return reslove(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
};

function reslove(root, sum) {
    if(!root) return 0;
    return ((sum === root.val) ? 1 : 0) + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}

Решение третье (O(n)): В первых двух решениях мы многократно обходим каждый уровень узлов сверху вниз (первый уровень проходится один раз, второй уровень проходится дважды, ...). В это время мы должны найти способ использовать кеш, чтобы уменьшить количество обходов.

Следовательно, есть решение со следующей сложностью O(n) (идея написана в комментариях)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    // 缓存
    const hashMap = {};
    let currentSum = 0;
    return pathSumRecursive(root, currentSum, hashMap, sum);
};

function pathSumRecursive(node, currentSum, hashMap, target) {
    if (!node) {
        return 0;
    }

    const newCurrentSum = currentSum + node.val;
    // 看一看能不能利用之前的缓存，巧妙的在一次遍历中算出了所有线段
    // 当前路径和 - 目标值 —— 本质是看 中间有没有一段路径和 等于 目标值
    // 比如 2 - 5 - 3 的路径， 目标为 8，那么在 3 这个节点时，路径和为 10 ， 减去目标值8 后为 2， 之前路径上有1条路线和为 2，因此中间有一段和为目标值 8
    let totalPaths = hashMap[newCurrentSum - target] || 0;
    
    if (newCurrentSum === target) {
        totalPaths++;
    }
    // 更新一下缓存
    if (hashMap[newCurrentSum]) {
        hashMap[newCurrentSum]++;
    } else {
        hashMap[newCurrentSum] = 1;
    }

    totalPaths += pathSumRecursive(node.left, newCurrentSum, hashMap, target);
    totalPaths += pathSumRecursive(node.right, newCurrentSum, hashMap, target);
    
    // 由于是共用一个缓存，因此遍历完后续节点后，要在退回上一层的时候把自身从缓存中删掉，来保证缓存数据的正确性（只应该有之前路径的）
    hashMap[newCurrentSum]--;
    return totalPaths;
}

438. Find All Anagrams in a String

Найти изоморфы в строках: Дана строка s и непустая строка p, найти все начальные индексы изоморфов p в s. Что такое изоморфизм: две строчные буквы одинаковы, порядок букв в строке может быть разным, например, ab и ba изоморфны

Решение первое:

Первое, что приходит в голову при этом, это использовать кеш для повышения эффективности Здесь мы сначала используем форму карты для отображения. Также используйте скользящее окно — два указателя (индекса) для указания на текущую подстроку. Затем просканируйте спереди назад, чтобы увидеть, есть ли совпадение через карту. если

  • Текущий символ находится в нашей карте, но он совпал, нам нужно сканировать указатель в начало назад, пока не встретится тот же символ.
  • Текущий символ вообще не существует в нашей карте, а это значит, что до этого символа не будет квалифицированной строки, поэтому нам нужно восстановить карту и начать со следующего символа текущего символа.
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const targetMap = {};
    // 构建map
    for(let char of p) {
        if(targetMap[char]) {
            targetMap[char]++;
        } else {
            targetMap[char] = 1;
        }
    }
    let start = 0;
    let cacheLen = p.length;
    const result = [];
    for(let i = 0; i < s.length; i++) {
        const char = s[i];
        // 如果 char 还有
        if(targetMap[char]) {
            targetMap[char]--;
            cacheLen--;
            // 如果都匹配上了
            if(cacheLen === 0) {
                result.push(start); // 推进去
                // 所有的向前移动一位
                targetMap[s[start]]++; 
                start++;
                cacheLen++;
            }
        } else if(targetMap[char] === 0) {
            // char 有，但是超过个数了，就要向前走把char去掉一个
            while(s[start] !== char) {
                targetMap[s[start]]++;
                start++;
                cacheLen++;
            }
            start++;
        } else {
            // char 根本没有，就跳过之前这段
            while(start < i) {
                targetMap[s[start]]++;
                start++;
            }
            start++;
            cacheLen = p.length;
        }
    }
    return result;
};

Решение второе: На приведенном выше рисунке Obj используется для сопоставления, и мы также можем использовать массивы в сочетании с символьными индексами для выполнения сопоставления.

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s2, s1) {
    const map = Array(128).fill(0);
    let start = 0,
        end = 0,
        counter = s1.length;
    const res = [];
    for (let i = 0; i < s1.length; ++i) {
        map[s1.charCodeAt(i)]++;
    }
    while (end < s2.length) {
        if (map[s2.charCodeAt(end)] > 0) {
            counter--;
        }
        map[s2.charCodeAt(end)]--;
        end++;
        while (counter == 0) {
            if (end - start == s1.length) {
                res.push(start);
            }
            if (map[s2.charCodeAt(start)] == 0) {
                counter++;
            }
            map[s2.charCodeAt(start)]++;
            start++;
        }
    }
    return res;
};

448. Find All Numbers Disappeared in an Array

Обычное решение: поскольку в заголовке указано условие, что все числа в массиве находятся в [1, n], а дополнительный пробел не требуется, можно подумать, что заголовок является рутинным вопросом: переместить/добавить /subtract/bits числа в исходной позиции Операция и другие решения. Для этого вопроса вы обычно можете выбрать метод обращения числа в соответствующей позиции: изменить число в соответствующей позиции числа, которое появляется, на отрицательное число, а затем пройти, чтобы найти эти положительные числа и нижний индекс +1 это число, которое не появлялось ранее.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    nums.forEach(num => {
        num = Math.abs(num);
        if(nums[num - 1] > 0) {
            nums[num - 1] = -nums[num - 1]
        }
    });
    const result = [];
    nums.forEach((num, index) => {
        if(num > 0) {
            result.push(index + 1);
        }
    });
    return result;
};

Побитовая версия операции: Прежде всего, вам нужно кратко понять, что делают несколько битовых операций:

  • Медианная операция JavaScript обрабатывает свои операнды как 32-битную последовательность битов, а самый левый бит числа со знаком равен 1.
  • 1
  • 1
  • с 1 |операция, она превратит число (независимо от положительного или отрицательного) в отрицательное число (изменяется только бит знака)
  • с 1 &операция, она превратит число (независимо от положительного или отрицательного) в положительное число (изменяется только бит знака) Решение позволяет избежать суждения о символе вышеописанным способом.
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    for (var i = 0; i < nums.length; i++) {
        nums[(nums[i] & ((1 << 31) - 1)) - 1] |= (1 << 31);
        //                 统一正负数运算            变成负数                               
    }
    
    ans = [];
    
    for (var i = 0; i < nums.length; i++) {
        // 如果不是负数，就推进去
        if ((nums[i] & (1 << 31)) != (1 << 31))
            ans.push(i+1);
    }
    
    return ans;
};

461. Hamming Distance

Hamming DistanceПредставляет количество различных символов в соответствующих позициях двух строк одинаковой длины, а также измеряет минимальное количество подстановок, необходимых для преобразования строки x в y путем замены символов.

1. Традиционное решение: после преобразования в двоичный формат пошаговый расчет требует ручного заполнения или ручной оценки.undefined

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
    let binaryX = x.toString(2);
    let binaryY = y.toString(2);
    const len = Math.max(binaryX.length, binaryY.length);
    if (binaryX.length < len) {
        binaryX = binaryX.padStart(len, '0')
    } else {
        binaryY = binaryY.padStart(len, '0')
    };
    let result = 0;
    for (let i = len - 1; i >= 0; i--) {
        if (binaryX[i] !== (binaryY[i])) {
            result++
        }
    }
    return result;
};

2. Битовая операция: побитовое XOR, нет необходимости учитывать длину дополнения, более кратко

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
    var res = x ^ y;
    var count = 0;
    while (res != 0) {
        if (res % 2 == 1) count++;
        res = Math.floor(res / 2); // res = res >> 1;
    }
    return count;
};

538. Convert BST to Greater Tree

К каждому узлу бинарного дерева поиска добавляется значение всех узлов, превышающее его: каждый ключ исходного BST заменяется на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST.

Решение первое:

  • Свойства BST следующие:
    • Если его левое поддерево не пусто, значение всех узлов в левом поддереве меньше значения его корневого узла;
    • Если его правое поддерево не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла;
    • Его левое и правое поддеревья также являются деревьями с бинарной сортировкой соответственно.
  • Используйте правый-> средний-> левый порядок для перехода от большого к меньшему и используйтеcacheValкэшировать значения больше текущего узла для достижения временной сложности O(n)
  • сделать это рекурсивноcacheValвместо сохранения значения во внешнем слое (немного более хлопотно, потому что нужно обработать крайний левый узел правого поддерева):строка кода 29)
  • Поскольку самый левый узел правого поддерева является наименьшим, за исключением текущего узла, значение самого левого узла правого поддерева является наибольшим (сумма всех узлов больше, чем текущий узел). Следовательно, текущему узлу нужно только добавить значение самого левого узла правого поддерева.
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    if(root) {
        converVal(root);
        return root;
    } else {
        return [];
    }
};

function converVal(root, cacheVal = 0) {
    if(root.right) {
        cacheVal = converVal(root.right, cacheVal);
    }
    root.val += cacheVal;
    cacheVal = root.val;
    if(root.left) {
        // 处理右子树最左节点，返回给上一层递归来使用（此时右子树最左节点为上一层节点需要加的值）
        return converVal(root.left, cacheVal);
    } 
    return root.val;
}

Решение 2: поместите раствор в раствор 1cacheValПредлагается ставить замыкание на периферию, и тогда не нужно каждый раз рекурсивно передавать его, а нужно только проходить от большого к малому, что просто и понятно.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let sum = 0;
    
    return function inner(root) {
        if (root == null) return null;
        inner(root.right);
        root.val += sum;
        sum = root.val;
        inner(root.left);
        return root;
    }(root);
};

543. Diameter of Binary Tree

Учитывая бинарное дерево, вычислите длину диаметра дерева - диаметр бинарного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корневой узел.

Рекурсия, поскольку она ищет самый длинный путь, делится на два случая для рассмотрения:

  • Найдите самый длинный путь на одной стороне левого поддерева и правого поддерева текущего поддерева и верните его на предыдущий уровень для использования.
  • Возвращает самый длинный путь текущего поддерева (самый длинный путь левого поддерева + текущий корневой узел (1) + самый длинный путь правого поддерева для использования предыдущим слоем

Наконец, найдите большее из двух

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    if(!root) return 0;
    // 返回一个最大的
    return Math.max(...diameterOfSubtree(root)) - 1;
};
function diameterOfSubtree(root) {
    if(!root.left && !root.right) return [1, 1];
    let left = 0, leftBig = 0, right = 0, rightBig = 0;
    if(root.left) [left, leftBig] = diameterOfSubtree(root.left);
    if(root.right) [right, rightBig] = diameterOfSubtree(root.right);
    // 当前子树最长路径
    const cacheBig = Math.max(leftBig, rightBig, left + right + 1);
    return [1 + Math.max(left, right), cacheBig];
}

572. Subtree of Another Tree

Определить, является ли дерево подструктурой другого дерева

Решение 1. Прямая рекурсия, чтобы увидеть, является ли это поддеревом, но это повторный обход

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function (s, t) {
    return !!(subtree(s, t) || 
            (s.left && isSubtree(s.left, t)) || 
            (s.right && isSubtree(s.right, t)));
};
function subtree(s, t) {
    if (!s && !t) return true;
    return ((s || {}).val === (t || {}).val) && 
            subtree(s.left, t.left) && 
            subtree(s.right, t.right);
}

Решение 2. Предварительно закажите обход дерева, сохраните его как строку, а затем посмотрите, содержит ли источник цель.

var isSubtree = function(s, t) {
  let string1 = {str: ""};
  let string2 = {str: ""};
  treeString(s, string1);
  treeString(t, string2);

  return string1.str.includes(string2.str);
}

function treeString(root, string) {
  if (!root) {
    string.str += "X";
    return;
  }
  string.str += `,${root.val},`
  treeString(root.left, string);
  treeString(root.right, string);
}

581. Shortest Unsorted Continuous Subarray

Кратчайший несортированный непрерывный подмассив: для целочисленного массива вам нужно найти кратчайший непрерывный подмассив, требование состоит в том, что если подмассив отсортирован в порядке возрастания, весь массив также будет отсортирован в порядке возрастания.

Первый простой метод - отсортировать массив, тогда количество исходного массива и нового массива не совпадает с лимитом, но сложность этого O(nlgn) (обход после сортировки)

Или мы можем использовать два указателя, один спереди назад и один сзади вперед.

  • Найдите последний индекс, который не является максимальным значением спереди назад
  • Найдите первый индекс, который не является минимальным значением сзади вперед

Затем вы можете выяснить, какой сегмент не отсортирован в порядке возрастания.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let last = 0, first = -1, max = -Infinity, min = Infinity;
    for(let i = 0, j = nums.length - 1; j >= 0; j--, i++){
        max = Math.max(max, nums[i]);
        if(nums[i] !== max) first = i;
        
        min = Math.min(min, nums[j]);
        if(nums[j] !== min) last = j;
    }
    return first - last + 1;
};

617. Merge Two Binary Trees

Предполагается, что в этом вопросе есть порочная ошибка - тестовый пример:

Input: [] []
Expected: []
Output: null

Рекурсивный:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
  if (!t1) {
    return t2;
  }
  if (!t2) {
    return t1;
  }
  t1.val += t2.val;
  t1.left = mergeTrees(t1.left, t2.left);
  t1.right = mergeTrees(t1.right, t2.right);
  return t1;
};

Нерекурсивный: используйте метод обхода уровня стека и дерева

var mergeTrees = function (t1, t2) {
    if (t1 === null) {
        return t2;
    }
    const stack = [];
    stack.push([t1, t2]);
    while (stack.length !== 0) {
        const t = stack.pop();
        if (t[0] === null || t[1] === null) {
            continue;
        }
        t[0].val += t[1].val;
        if (t[0].left === null) {
            t[0].left = t[1].left;
        } else {
            stack.push([t[0].left, t[1].left]);
        }
        if (t[0].right === null) {
            t[0].right = t[1].right;
        } else {
            stack.push([t[0].right, t[1].right]);
        }
    }
    return t1;
};
Категории