«Интервью ДОЛЖЕН ЗАПРОСИТЬ» Выбор высокочастотных вопросов LeetCode

алгоритм
«Интервью ДОЛЖЕН ЗАПРОСИТЬ» Выбор высокочастотных вопросов LeetCode

Введение (преимущества в конце статьи) 🏂

Алгоритмы всегда были частым вопросом на фронтенд-интервью на крупных фабриках, и все часто готовятся к собеседованиям в этой области, проходя их.leetcodeВопросы по кисти.

я собрал несколькоleetcodeсередина"很有意思И очень "高频"Тема алгоритма, дан анализ идей (с графикой) и код.

Внимательно прочитав эту статью, я уверен, что она обязательно поможет вам на собеседовании по алгоритму! 🤠

Сумма двух чисел 🦊

❝

Сложность вопросаeasy, задействованные знания алгоритмов включают массивы, хеш-таблицы

❞

Название Описание

задан массив целых чиселnumsи целевое значениеtarget, пожалуйста, найдите тот, чья сумма является целевым значением в массиве两个целые числа и возвращают их индексы массива.

Можно предположить, что для каждого входа будет только один ответ. Однако один и тот же элемент массива нельзя использовать дважды.

Пример:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Анализ мыслей

Когда большинство учащихся увидят эту задачу, они обязательно подумают в глубине души: эта задача слишком проста, почему бы просто не пройти один и тот же массив в двух слоях: два слоя циклов для обхода одного и того же массива; значение первого слоя цикла прохождение записывается какa, значение, пройденное во время цикла второго слоя, записывается какb;подобноa+b = 目标值,Такaа такжеbСоответствующий индекс массива является ответом, который нам нужен.

В этом решении нет ничего плохого, но есть ли оптимизированное решение? 🤔

Имейте в виду, что двухуровневые циклы во многих случаях означаютO(n^2)сложность, которая может легко привести к тайм-ауту вашего алгоритма. Даже если нет тайм-аута, если вы напишите два уровня обхода, когда очевидно, что есть одноуровневое решение обхода, интервьюер значительно снизит вашу оценку впечатления. 🤒

На самом деле, в процессе обхода массива мы можем добавитьMapСтруктура для хранения пройденных чисел и соответствующих им значений индексов. Затем каждый раз, когда проходится новое число, он возвращается кMapчтобы узнатьtargetNumПоявилось ли отличие от этого номера уже в предыдущем номере. Если да, то ответ уже появился, и нам не нужно идти дальше.

Давайте используем пример в этом вопросе и картинку, чтобы проиллюстрировать идею, упомянутую выше:

  • объект здесьdiffsимитироватьmapструктура:Сначала пройдите по первому элементу массива, затемkey2,valueИндексировать 0
  • Внизу обход, я встретил 7:рассчитатьtargetNumРазница между 7 и 7 равна 2, перейдите кdiffsПолучил 2 из этогоkey, оказалось значением, которое появилось ранее. Тогда ответ на этот вопрос отсутствует!

Код 

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {
  const diffs = {};
  // 缓存数组长度
  const len = nums.length;
  // 遍历数组
  for (let i = 0; i < len; i++) {
    // 判断当前值对应的 target 差值是否存在
    if (diffs[target - nums[i]] !== undefined) {
      // 若有对应差值，那么得到答案
      return [diffs[target - nums[i]], i];
    }
    // 若没有对应差值，则记录当前值
    diffs[nums[i]] = i;
  }
};

Сумма трех чисел 🦁

❝

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

❞

Описание темы

дает вам содержаниеnмассив целых чиселnums,судитьnumsЕсть ли три элемента вa,b,c, так чтоa + b + c = 0. Найдите все тройки, удовлетворяющие условию и не повторяющиеся.

Примечание. Ответы не могут содержать повторяющиеся тройки.

Пример:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Анализ мыслей

и выше两数之和Точно так же, если вы не подумаете тщательно, самым быстрым способом может быть обход нескольких слоев. Но с извлеченными уроками мы также можем превратить задачу суммирования в задачу разности: зафиксировать одно из чисел и выяснить, есть ли в оставшихся числах два числа, которые в сумме дают это фиксированное число, равное 0.

Здесь мы используем双指针法Чтобы решить эту проблему, по сравнению с трехслойным циклом эффективность будет значительно повышена.

❝

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

❞

Итак, наш первый шаг — сначала отсортировать массив:

// 给 nums 排序
nums = nums.sort((a,b)=>{
    return a-b
})

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

  • Сумма больше 0, что указывает на то, что число справа слишком велико, и правый указатель перемещается влево.
  • Сумма сложения меньше 0, что указывает на то, что число слева слишком мало, а левый указатель перемещается вправо

Код 

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function(nums) {
    // 用于存放结果数组
    let res = []
    // 目标值为0
    let sum = 0
    // 给 nums 排序
    nums = nums.sort((a,b)=>{
        return a-b
    })
    // 缓存数组长度
    const len = nums.length
    for(let i=0;i<len-2;i++) {
        // 左指针 j
        let j=i+1
        // 右指针k
        let k=len-1
        // 如果遇到重复的数字，则跳过
        if(i>0&&nums[i]===nums[i-1]) {
            continue
        }
        while(j<k) {
            // 三数之和小于0，左指针前进
            if(nums[i]+nums[j]+nums[k]<0){
                j++
               // 处理左指针元素重复的情况
               while(j<k&&nums[j]===nums[j-1]) {
                    j++
                }
            } else if(nums[i]+nums[j]+nums[k]>0){
                // 三数之和大于0，右指针后退
                k--

               // 处理右指针元素重复的情况
               while(j<k&&nums[k]===nums[k+1]) {
                    k--
                }
            } else {
                // 得到目标数字组合，推入结果数组
                res.push([nums[i],nums[j],nums[k]])

                // 左右指针一起前进
                j++
                k--

                // 若左指针元素重复，跳过
                while(j<k&&nums[j]===nums[j-1]) {
                    j++
                }

               // 若右指针元素重复，跳过
               while(j<k&&nums[k]===nums[k+1]) {
                    k--
                }
            }
        }
    }

    // 返回结果数组
    return res
};

Контейнер, который удерживает наибольшую воду 🥃

❝

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

❞

Описание темы

Вам даны n целых неотрицательных чисел a1, a2, ..., an, каждое из которых представляет точку с координатами (i, ai). Нарисуйте n вертикальных линий в координатах, двумя конечными точками вертикальной линии i являются (i, ai) и (i, 0). Найдите две из этих линий, которые вместе с осью абсцисс образуют емкость с наибольшим количеством воды.

Объяснение: Вы не можете наклонить контейнер, а значение n не меньше 2.Вертикальная линия на рисунке представляет входной массив [1,8,6,2,5,4,8,3,7]. В этом случае максимальное количество воды, которое может вместить контейнер (показано синим цветом), равно 49.

Пример:

输入：[1,8,6,2,5,4,8,3,7]
输出：49

Анализ мыслей

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

Это решение требует двух слоев циклов, а временная сложностьO(n^2). Это относительно жестоко, и соответствующее暴力法.

закон о насилии 

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    for(let i = 0; i< height.length-1; i++) {
        for(let j = i + 1; j < height.length;j++) {
            let area = (j - i) * Math.min(height[i], height[j]);
            max = Math.max(max, area)
        }
    }

    return max;
}

Так есть ли лучший способ? Ответ положительный.

На самом деле немного похоже双指针Концепция , левый указатель указывает на нижний индекс 0, правый указатель указывает наlength-1. Затем двигайтесь от левой и правой сторон к середине, каждый раз принимая меньшее значение (потому что высота воды должна основываться на меньшем).

Если левая сторона меньше правой, тоi++,иначеj--(Этот шаг на самом деле состоит в том, чтобы взять большую из всех высот, мы знаем, что площадь равна长*宽). соответствует双指针 动态滑窗

Двойной указатель Динамическое скользящее окно 

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    let i = 0;
    let j = height.length - 1;
    while(i < j) {
        let minHeight = Math.min(height[i], height[j])
        let area = (j - i)*minHeight;
        max = Math.max(max, area)
        if(height[i] < height[j]) {
            i++
        } else {
            j--
        }
    }
    return max
};

подъем по лестнице 🎢

❝

Сложность вопросаeasy, задействованные знания алгоритмов включают последовательность Фибоначчи и динамическое программирование.

❞

Описание темы

Предположим, вы поднимаетесь по лестнице. Вам нужно n шагов, чтобы добраться до крыши.

Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания?

Примечание. Данное n является положительным целым числом.

Пример 1:

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

Пример 2:

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Анализ мыслей

Этот вопрос очень часто встречается на собеседованиях, а также является очень классическим.斐波那契数列тип темы.

Для решения этой задачи воспользуемся алгоритмической идеей динамического программирования — ее можно разделить на несколько подзадач, а количество способов подняться по n-й лестнице равно сумме 2-х частей:

  • взбиратьсяn−1Количество способов подняться по лестнице. Потому что еще один шаг приведет вас к энному шагу
  • взбиратьсяn−2Количество способов подняться по лестнице, так как еще 2 ступени приведут вас к n-й ступени

Формулу можно получить:

climbs[n] = climbs[n-1] + climbs[n-2]

При этом нужно сделать следующую инициализацию:

climbs[0] = 1;
climbs[1] = 1

Код 

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

};

Круговой связанный список 🍩

❝

Сложность вопросаeasy, задействованные знания алгоритма включают связанные списки и быстрые и медленные указатели.

❞

Описание темы

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

Чтобы представить кольцо в данном связанном списке, мы используем целое число pos для обозначения позиции в связанном списке, где соединяется конец связанного списка (индексы начинаются с 0). Если pos равно -1, в списке нет циклов.

Пример 1:

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

Пример 2:

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

Пример 3:

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

Анализ мыслей

链表成环Проблема также очень классические алгоритмические проблемы, часто встречающиеся в интервью.

Обычно существует два распространенных способа решения этой проблемы:标志法а также快慢指针法.

подписать закон

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

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true;
        head = head.next;
    }
    return false
};

Быстрый и медленный указатель (метод двойного указателя)

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

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if(!head || !head.next) {
        return false
    }
    let slow = head, fast = head.next;
    while(slow !== fast) {
        if(!fast || !fast.next) return false
        fast = fast.next.next;
        slow = slow.next
    }
    return true;
};

Допустимые скобки 🍉

❝

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

❞

Описание темы

Учитывая только включить'(',')','{','}','[',']'Строка , чтобы определить, является ли строка допустимой.

Действительная строка должна удовлетворять:

1. Открывающая скобка должна быть закрыта закрывающей скобкой того же типа. 2. Левые скобки должны быть закрыты в правильном порядке.

Обратите внимание, что пустые строки считаются допустимыми строками.

Пример 1:

输入: "()"
输出: true

Пример 2:

输入: "()[]{}"
输出: true

Пример 3:

输入: "(]"
输出: false

Пример 4:

输入: "([)]"
输出: false

Пример 5:

输入: "{[]}"
输出: true

Анализ мыслей

Этот вопрос можно использовать栈структура.

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

switch case 

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let arr = [];
    let len = s.length;
    if(len%2 !== 0) return false
    for(let i = 0; i<len;i++) {
        let letter = s[i];
        switch(letter) {
            case '(': {
                arr.push(letter);
                break;
            }
            case '{': {
                arr.push(letter);
                break;
            }
            case '[': {
                arr.push(letter);
                break;
            }
            case ')': {
                if(arr.pop() !== '(') return false
                break;
            }
            case '}': {
                if(arr.pop() !== '{') return false
                break;
            }
            case ']': {
                if(arr.pop() !== '[') return false
                break;
            }
        }
    }
    return !arr.length
};

Во-вторых, поддерживатьmapОбъект:

хеш-таблицаmap 

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    let stack = [];
    let len = s.length;
    if(len%2 !== 0) return false
    for(let i of s) {
        if(i in map) {
            stack.push(i)
        }  else {
            if(i !== map[stack.pop()]) return false
        }
    }
    return !stack.length
};

Раздвижное окно макс. ⛵

❝

Сложность вопросаhard, задействованные знания алгоритма имеют двусторонние очереди.

❞

Описание темы

Учитывая массив nums, существует скользящее окно размера k, перемещающееся из крайнего левого края массива в крайнее правое. Вы можете видеть только k чисел в скользящем окне. Скользящее окно перемещается вправо только на одну позицию за раз.

Возвращает максимальное значение в скользящем окне.

Для продвинутых: Можете ли вы решить эту задачу за линейное время?

Пример:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

намекать:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

Анализ мыслей

решение грубой силы

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

  • перебирать массив
  • Пройдите максимальное значение в каждом интервале по очереди и поместите его в массив
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let len = nums.length;
    if(len === 0) return []
    if(k === 1) return nums
    let resArr = []
    for(let i = 0; i <= len - k;i++) {
        let max = Number.MIN_SAFE_INTEGER;
        for(let j = i; j < i + k; j++) {
            max = Math.max(max, nums[j])
        }
        resArr.push(max)
    }
    return resArr;
};

дека

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

В сочетании с приведенной выше анимацией (Источник изображения) Разбираем следующие идеи:

  • Проверьте элементы в конце очереди, чтобы убедиться, что все они удовлетворяют условию быть больше или равны текущему элементу. Если это так, поставьте в очередь текущий элемент напрямую. В противном случае удаляйте элементы в конце очереди один за другим, пока элемент в конце очереди не станет больше или равен текущему элементу. (Этот шаг предназначен для поддержания уменьшения очереди: убедитесь, что головной элемент очереди является максимальным значением текущего скользящего окна. Таким образом, каждый раз, когда мы берем максимальное значение, мы можем напрямую взять головной элемент очереди. очередь.)
  • поставить в очередь текущий элемент
  • Проверьте элемент head, чтобы убедиться, что элемент head был исключен из скользящего окна. Если это так, удалите головной элемент из очереди. (Этот шаг предназначен для обеспечения достоверности очереди: убедиться, что все элементы в очереди находятся в пределах скользящего окна.)
  • Исключите частный случай, когда скользящее окно не было инициализировано и первое максимальное значение еще не появилось.
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    // 缓存数组的长度
    const len = nums.length;
    const res = [];
    const deque = [];
    for (let i = 0; i < len; i++) {
        // 队尾元素小于当前元素
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop()
        }
        deque.push(i)

        // 当队头元素的索引已经被排除在滑动窗口之外时
        while (deque.length && deque[0] <= i - k) {
            // 队头元素出对
            deque.shift()
        }
        if (i >= k - 1) {
            res.push(nums[deque[0]])
        }
    }
    return res
};

Дневная температура 🌡

❝

Сложность вопросаmedium, задействованное знание алгоритма имеет стек.

❞

Описание темы

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

Например, учитывая список температур = [73, 74, 75, 71, 69, 72, 76, 73], ваш вывод должен быть [1, 1, 4, 2, 1, 1, 0, 0].

Подсказка: длина списка температур находится в диапазоне [1, 30000]. Каждое значение температуры указано в градусах по Фаренгейту и является целым числом в диапазоне [30, 100].

Анализ мыслей

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

Однако это решение требует двух уровней обхода, а временная сложностьO(n^2), что явно не является оптимальным решением.

Этот раздел может использовать стек для оптимизации.

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

Код 

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    const len = T.length;
    const stack = [];
    const res = (new Array(len)).fill(0);
    for (let i=0; i < len;i++) {
        while(stack.length && T[i] > T[stack[stack.length - 1]]) {
            const top = stack.pop();
            res[top] = i - top;
        }
        stack.push(i)
    }
    return res
};

Генерация кронштейна 🎯

❝

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

❞

Описание темы

Число n представляет собой логарифм создания скобок. Пожалуйста, создайте функцию, которая может генерировать все возможные и допустимые комбинации скобок.

Пример:

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

Анализ мыслей

Эта проблема решается рекурсией.

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

Здесь есть потенциальное ограничение:有效的Комбинация кронштейнов. Соответствующая логика заключается в том, чтобы поставить "(" или ")" в каждой позиции перед:

  • Нужно определить, меньше ли число "(" n
  • Число ")" меньше, чем "("

Код 

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res = []
    const generate = (cur, left, right) => {
        if (left ===n && right === n) {
            res.push(cur)
            return
        }
        if (left < n) {
            generate(cur + '(', left + 1, right)
        }
        if (right < left) {
            generate(cur + ')', left, right + 1)
        }
    }
    generate('', 0, 0)
    return res
};

Буквенные комбинации телефонных номеров 🎨

❝

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

❞

Описание темы

Учитывая строку, содержащую только числа 2-9, вернуть все комбинации букв, которые она может представлять.

Отображение цифр в буквы дается следующим образом (так же, как клавиши телефона). Обратите внимание, что 1 не соответствует ни одной букве.Пример:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Анализ мыслей

Сначала используйте объектmapСохраните отношение сопоставления между числами и буквами, затем пройдите соответствующую строку и сохраните строку в массиве результатов в первый раз.resultВо втором и последующих обходах новый массив строк генерируется путем двухслойного обхода.

Код

Послойный обход хеш-карты 

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let res = [];
    if (digits.length === 0) return []
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    for (let num of digits) {
        let chars = map[num]
        if (res.length > 0) {
            let temp = []
            for (let char of chars) {
                for (let oldStr of res) {
                    temp.push(oldStr + char)
                }
            }
            res = temp
        } else {
            res.push(...chars)
        }

    }
    return res
};

рекурсия 

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let res = [];
    if (!digits) return []
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    function generate(i, str) {
        let len = digits.length;
        if (i === len) {
            res.push(str)
            return
        }
        let chars = map[digits[i]]
        for (let j = 0; j < chars.length; j++) {
            generate(i+1, str + chars[j])
        }
    }
    generate(0, '')
    return res
};

Количество островов 🏝

❝

Сложность вопросаmedium, используемое знание алгоритма — это DFS (поиск в глубину).

❞

Описание темы

Учитывая двухмерную сетку «1» (суша) и «0» (вода), подсчитайте количество островов в сетке.

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

Также можно предположить, что меш окружен водой со всех четырех сторон.

Пример 1:

输入:
11110
11010
11000
00000
输出: 1

Пример 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

Анализ мыслей

Как показано выше, все, что нам нужно рассчитать, это количество зеленых островов, которые связаны (только горизонтально и / или вертикально) на графике.

Классический подход к этой проблеме沉岛, общая идея такова: используйтеDFS(поиск в глубину), если встречается 1, текущая 1 будет изменена на 0, и поиск в глубину будет выполняться на верхней, нижней, левой и правой сторонах текущей координаты и подсчитываться.

Условие завершения: за границей двумерного массива или встретить 0 , вернуться напрямую.

Код 

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const rows = grid.length;
    if (rows === 0) return 0
    const cols = grid[0].length;
    let res = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                helper(grid, i, j, rows, cols)
                res++
            }
        }
    }
    return res
}
 function helper(grid, i, j, rows, cols) {
    if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
        return;

    grid[i][j] = "0"

    helper(grid, i + 1, j, rows, cols);
    helper(grid, i, j + 1, rows, cols);
    helper(grid, i - 1, j, rows, cols);
    helper(grid, i, j - 1, rows, cols);

}

Раздайте печенье 🍪

❝

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

❞

Описание темы

Допустим, вы замечательный родитель и хотите угостить своих детей маленьким печеньем. Однако каждому ребенку можно дать не более одного файла cookie. Для каждого ребенка i существует значение аппетита gi, которое является наименьшим размером файла cookie, который удовлетворит аппетит ребенка, а для каждого файла cookie j существует размер sj. Если sj >= gi , мы можем назначить этот файл cookie j дочернему элементу i, и этот дочерний элемент будет удовлетворен. Ваша цель — удовлетворить как можно больше детей и вывести это максимальное значение.

Уведомление:

Вы можете предположить, что значение аппетита положительное. Ребенок может иметь не более одного файла cookie.

Пример 1:

输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

Пример 2:

输入: [1,2], [1,2,3]

输出: 2

解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

Анализ мыслей

Эта тема является типичной贪心算法Добрый. Решение проблемы примерно такое:

  • Приоритет удовлетворения потребностей детей с низким аппетитом
  • Пусть максимальное количество детей, которое может быть удовлетворено, равноmaxNum = 0
  • Маленькие аппетиты требуют маленьких, большие аппетиты требуют больших
  • Решите с обеих сторон, затем по одной
    • когда饼干j >= 胃口iчас,i++,j++,maxNum++
    • когда饼干j < 胃口iКогда бисквитов недостаточно, замените их на более крупные.j++
  • После границы остановиться

Код 

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g = g.sort((a, b) => a - b)
    s = s.sort((a, b) => a - b)
    let gLen = g.length,
        sLen = s.length,
        i = 0,
        j = 0,
        maxNum = 0;
    while (i < gLen && j < sLen) {
        if (s[j] >= g[i]) {
            i++;
            maxNum++
        }
        j++
    }
    return maxNum
};

Лучшее время для покупки и продажи акций II 🚁

❝

Сложность вопросаeasyИспользуемые знания алгоритмов включают динамическое программирование и жадные алгоритмы.

❞

Описание темы

Дан массив, i-й элемент которого — цена данной акции в i-й день.

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

Уведомление:Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущую акцию, прежде чем покупать ее снова).

Пример 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

Пример 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

Пример 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

намекать:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

Анализ мыслей

На самом деле идея этого вопроса относительно проста:

  • поддерживать переменнуюprofitхранить прибыль
  • Поскольку вы можете покупать и продавать несколько раз, цена на задней должна быть больше, чем цена на передней, тогда вы можете покупать и продавать.
  • Следовательно, покаprices[i+1] > prices[i], затем наложитьprofit
  • обход завершенprofitмаксимальная прибыль

Код 

/**
 * @param {number[]} prices
 * @return {number}
 */
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
};

Разные пути 🛣

❝

Сложность вопросаmedium, знание алгоритма, связанное с динамическим программированием.

❞

Описание темы

Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).

Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).

В. Сколько всего существует различных путей?Например, изображение выше представляет собой сетку 7 x 3. Сколько существует возможных путей?

Пример 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

Пример 2:

输入: m = 7, n = 3
输出: 28

Анализ мыслей

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

Таким образом, динамическое уравнение может быть получено как:dp[i][j] = dp[i-1][j]+dp[i][j-1].

Код

❝

используется здесьArray(m).fill(Array(n).fill(1))Инициализируется, потому что у каждого квадрата есть хотя бы один ход.

❞ 
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = Array(m).fill(Array(n).fill(1))
    for (let i = 1; i < m;i++) {
        for (let j = 1; j< n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]

};

Изменить 💰

❝

Сложность вопросаmedium, знание алгоритма, связанное с динамическим программированием.

❞

Описание темы

Даны монеты разного номинала и общая сумма. Напишите функцию для вычисления минимального количества монет, необходимого для получения общей суммы. Возвращает -1, если ни одна из комбинаций монет не составляет общую сумму.

Пример 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

Пример 2:

输入: coins = [2], amount = 3
输出: -1

проиллюстрировать:Вы можете придумать бесконечное количество монет каждого типа.

Анализ мыслей

Мы также используем эту тему动态规划решать.

Предполагая, что даны монеты разного номинала [1, 2, 5] и цель равна 60, какое минимальное количество монет требуется?

Сначала нам нужно разложить подзадачи и найти оптимальную подструктуру иерархически.

❝

dp[i]: Указывает, что общая суммаiКоличество монет для оптимального решения при

❞

Давайте подумаем: сколько существует способов найти общую сумму 60? Есть 3 способа, потому что у нас есть 3 монеты разного номинала.

  • Возьмите монету достоинством 1 + общее количество монет для оптимального решения 59. То есть: дп[59] + 1
  • Берем монету номиналом 2 + количество монет для оптимального решения всего 58. То есть: дп[58] + 1
  • Возьмите монету номиналом 5 + общее количество монет для оптимального решения 55. То есть: дп[55] + 1

Следовательно, оптимальное решение с общей суммой 60 является оптимальным решением среди трех вышеупомянутых решений, то есть с наименьшим количеством монет.Давайте используем код, чтобы выразить это ниже:

dp[60] = Math.min(dp[59] + 1, dp[58] + 1, dp[55] + 1);

выведен状态转移方程:

dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)
❝

вcoinСколько возможностей, нам нужно сравнить, сколько раз пройденоcoinsМассивы, вы можете сравнить их по отдельности

❞

Код 

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(Infinity)
    dp[0] = 0;
    for (let i=0;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]
};

Благосостояние

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

Я также поддерживаюgithubсклад:https://github.com/Jack-cool/js_algorithm, который содержит большое количествоleetcodeПроблема решена, и она все еще обновляется.starкакие! 🤗

В этой статье используетсяmdniceнабор текста

Категории