предисловие

Отзыв от прошлой статьи не плохой.Оказывается,после новогодних поздравлений группа людей действительно начала учиться,и весенние наборы 2021 начинаются один за другим.Чем я могу вам помочь, так это обновить алгоритм вводная колонка как можно больше в феврале.Все очень довольны 👍~

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

Я изначально планировал представить это через статью, порекомендовать свой путь и маршрут, чтобы расчесать вопросы, и получить отзывы от некоторых партнеров: лучше быть более подробным, ориентироваться на нулевой фундамент, Xiaobai и т. д.githubСо скоростью доступа тоже проблема, и картинки могут не грузиться.

Поэтому я планирую разделить статью на несколько модулей, чтобы вы могли понять только через статью, впервые опубликованную в НаггетсChocolateПодведение итогов студентов в целом. Скоро наступит китайский Новый год, и я надеюсь, что он поможет вам с весенним набором. Планируемый контент-план выглядит следующим образом:

• 🐮Написанное для вводного руководства по интерфейсному алгоритму с нулевым основанием, Акмер взял свою девушку, чтобы почистить 80+ [стеков, очередей и связанных списков] (Готово 🎉)
• 🐮Написанное для вводного руководства по интерфейсному алгоритму с нулевым основанием, Акмер взял свою девушку на чистку 80+ [рекурсия и возврат] (Готово 🎉)
• 🐮При написании вводного руководства по интерфейсному алгоритму, основанному на нуле, акмер взял свою девушку, чтобы почистить 80+【Двойные указатели и строки】(Этот выпуск завершен🎉)
• 🐮При написании вводного руководства по интерфейсному алгоритму, основанному на нуле, Акмер взял свою девушку, чтобы почистить 80+ [статьи о бинарном дереве]
• 🐮Написано для вводного руководства по интерфейсному алгоритму с нулевым основанием, Акмер взял свою девушку на чистку 80+ [Dynamic Programming DP]
• 🐮При написании вводного руководства по интерфейсному алгоритму с нулевым основанием Акмер взял свою девушку на чистку зубов 80+ [резюме]

Добро пожаловать в гостиРепозиторий GitHub, уже есть 552 больших заводских реальных вопроса, охватывающих все виды реальных вопросов, я желаю вам крепкой весны и осени ~

Как подготовить алгоритм

Прежде всего, позвольте мне кратко представиться, я играл в ACM в школе (если я не слышал об этом, я не говорил, потому что нет карт большой стоимости, железные карты, карты участия и сертификаты куча)

Если вы знаете acm и участвовали в нем, для внутренних фронтендов (обратите внимание, что это означает фронтенд) интервью не должно занять много времени, чтобы почистить вопросы.Если у вас есть идеи о моем опыте acm, я рассмотреть это продолжение вСтанция B выпускает видео.

Тогда для новичка с нулевой базой на подготовку алгоритма может уйти около 10-20 дней, а для непрофессиональных занятий этот срок может быть немного больше. Итак, теперь я собираюсь поделиться тем, как я взял свою девушку с нулевыми знаниями, чтобы почистить вопросы.

• Первый момент это то,что не сложно прояснить алгоритм.Если вы его понимаете,это будет иметь значение.Возможно вам понравится делать вопрос.Конечно,другое дело для вопроса, который задает начальник acm.Уровень интервью
• Второй момент заключается в том, что предварительная проверка алгоритма будет относительно простой.Все письменные тестовые вопросы, с которыми я столкнулся в процессе весеннего и осеннего набора, — это общие вопросы, такие как поиск, жадность, простое динамическое программирование, классические алгоритмы сортировки и т. д. все сleetcodeБольшинство из них простые и умеренно сложные, и эти алгоритмы следует изучать в школе по таким предметам, как анализ и разработка алгоритмов, структуры данных и алгоритмы.
• Третий момент, так как речь идет о чистке вопросов, как чистить, я сослался на нескольких больших парней в Наггетс (ссылка есть в конце статьи), все порекомендуют подтемы почистить, здесь, Я также настоятельно рекомендую здесь, я надеюсь, немного уменьшить количество вопросов об алгоритме чистки и помочь вам начать работу. ,вместо того чтобы быть очень пассивным.Очень удобно подводить итоги и подводить итоги~
• Для других, вы можете обратиться к статье большого парня, которая не будет повторяться здесь...

Интеллект-карта, облегчающая решение проблем

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

Чтобы получить PDF-файл в высоком разрешении, ответьте на [LeetCode] в общедоступной учетной записи WeChat [Little Lion Front-end], и вы можете добавить пингвинов в группу пингвинов [666151691] для просмотра вопросов или общения и совместного обучения.

Эта складская щетка ставит под сомнение ссылку на маршрутssh(Цените большого парня) Адрес склада:GitHub.com/forget 1673495/приходите…

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

Во-вторых, большинство кодов решения проблем на этом складе имеют собственный стиль кода, и количество вопросов также было расширено и будет продолжать обновляться.Почему бы не пометить и не собрать их?

Введение склада

Адрес склада:GitHub.com/chocolate19…

Язык, который будет использоваться в этом репозитории:JavaScript, — это чистый маршрут для чистки переднего конца, который является благом для друзей, у которых нет направления в чистке переднего конца. Код решения проблемы будет записан в этот репозиторий.Issues, согласно сlabel Сортировать. Например, если вы хотите просмотреть вопросы в категории «Рекурсия и поиск с возвратом», вы можете выбрать метку для фильтрации.

В то же время друзья могутIssuesОтправьте свой собственный код решения проблемы в 🤝 Добро пожаловатьContributing, можно пробить карточку и свайпать вопрос, а тот, кто упорствует, тот самый крутой! Поставьте ⭐️, если этот проект помог вам!

Вопросы кисти

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

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

двойной указатель

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

Оригинальное название портала суммы трех чисел

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

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

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

Пример:

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

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

Идеи решения проблем

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

Избегайте повторяющихся решений при перемещении двойного указателя

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

• В соответствии с предпосылкой слева
• Согласно предпосылке слева

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    let len = nums.length;
    if (len < 2) return [];
    let res = [];
    nums.sort((a, b) => a - b); // 从小到大进行排序
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 去掉重复项
        let L = i + 1;
        let R = len - 1;
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]; // 三数之和
            if (sum === 0) {
                res.push([nums[i], nums[L], nums[R]]);
                while (L < R && nums[L] == nums[L + 1]) L++; // 去重，直到指向不一样的数
                while (L < R && nums[R] == nums[R - 1]) R--;
                L++;
                R--;
            } else if (sum < 0) {
                L++; // 和小于0，就是左边值太小了，往右移
            } else if (sum > 0) {
                R--; // 和大于0，就是右边值太大了，往左移
            }
        }
    }
    return res;
};

16. Сумма ближайших трех чисел

16. Ближайшая сумма трех порталов

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

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

Пример:

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

намекать:

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

Идеи решения проблем

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

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
    let len = nums.length;
    nums.sort((a, b) => a - b); // 从小到大进行排序
    let res = nums[0] + nums[1] + nums[len - 1]; // 初始化随机一个res
    for (let i = 0; i < len - 2; i++) {
        let L = i + 1;
        let R = len - 1;
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]; // 三数之和
            sum > target ? R-- : L++; // 比目标值大，就往左内缩，小的话，就往右内缩
            if (Math.abs(sum - target) < Math.abs(res - target)) {
                res = sum; // 迭代更新res
            }
        }
    }
    return res;
};

75. Цветовая классификация

75. Цветовая классификация оригинального названия портала

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

Дан массив из n элементов красного, белого и синего цветов, отсортируйте их на месте так, чтобы элементы одного цвета были соседними в порядке красного, белого и синего.

В этой задаче мы используем целые числа 0, 1 и 2 для представления красного, белого и синего цветов соответственно.

Уведомление: Эта проблема не может быть решена с помощью функции сортировки в кодовой базе.

Пример:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

Передовой:

Интуитивным решением является использование двухпроходного алгоритма сортировки по количеству. Сначала итеративно вычислите количество элементов 0, 1 и 2, а затем перепишите текущий массив в порядке 0, 1 и 2. Можете ли вы придумать алгоритм однопроходного сканирования, использующий только постоянное пространство?

Идеи решения проблем

Двойной указатель, текущее значение равно 2, тогда оно будет заменено правым указателем, в противном случае текущее значение равно 0, затем оно будет заменено левым указателем, и он не будет двигаться, если он равен 1.

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    let len = nums.length;
    let L = 0;
    let R = len - 1;
    let i = 0;
    while (i <= R) {
        while (nums[i] == 2 && i < R) { // 当前值为2，那么就和右边指针进行交换
            [nums[i], nums[R]] = [nums[R], nums[i]];
            R--;
        }
        while (nums[i] == 0 && i > L) { // 当前值为0，那么就和左边指针进行交换
            [nums[i], nums[L]] = [nums[L], nums[i]];
            L++;
        }
        i++;
    }
    return nums;
};

Я думаю, что следующий код должен облегчить понимание:

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    let len = nums.length;
    let L = 0;
    let R = len - 1;
    let i = 0;
    while (i <= R) {
        if (nums[i] == 0) { // 当前值为0，那么就和左边指针进行交换
            [nums[i], nums[L]] = [nums[L], nums[i]];
            L++;
            i++;
        } else if (nums[i] == 2) { // 当前值为2，那么就和右边指针进行交换
            [nums[i], nums[R]] = [nums[R], nums[i]];
            R--;
        } else {
            i++;
        }
    }
    return nums;
};

344. Обратная строка

344. Портал оригинального названия обратной строки

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

Напишите функцию, которая переворачивает входную строку. входная строка как массив символовchar[]дается в виде.

Не выделяйте лишнее место для другого массива, вы должныИзмените входной массив на месте, используя дополнительное пространство O (1) для решения этой проблемы.

Вы можете предположить, что все символы в массивеASCIIпечатные символы в кодовой таблице.

Пример 1:

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

Пример 2:

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

Идеи решения проблем

Способ 1: использовать собственный API JS

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    return s.reverse();
};

Способ 2: двойной указатель, обмен головой и хвостом

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    let i = 0, j = s.length - 1;
    while (i < j) {
        [s[i], s[j]] = [s[j], s[i]]; // 双指针，交换
        i++ , j--;
    }
    return s;
};

11. Емкость, в которой больше всего воды

11. Оригинальное название портала контейнера, вмещающего больше всего воды

Описание темы Вам даны 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

Идеи решения проблем

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

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let len = height.length;
    let L = 0;
    let R = len - 1;
    let res = 0;
    while (L < R) {
        if (height[L] < height[R]) {  // 选择短板效应
            let ans = height[L] * (R - L);
            L++;
            res = Math.max(res, ans); // 求当前容纳最多的水
        } else {
            let ans = height[R] * (R - L);
            res = Math.max(res, ans);
            R--;
        }
    }
    return res;
};

42. Поймать дождь

42. Оригинальный тематический портал приема дождя

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

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

Вышеупомянутое состоит из массивов[0,1,0,2,1,0,1,3,2,1,2,1] Представляет карту высот, в данном случае может отображать 6 единиц дождя (синяя часть представляет дождь). Спасибо Маркосу за предоставление этого изображения.

Пример:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

Идеи решения проблем

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

Возьмем в качестве примера левый: текущий запас воды в столбце = последняя самая высокая высота столбца (см. только слева от текущего столбца) - текущая высота столбца

То же самое касается права.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let len = height.length;
    let L = 0, R = len - 1;
    let leftHeight = 0, rightHeight = 0;
    let res = 0;
    while (L < R) {
        if (height[L] < height[R]) { // 左边高度小，当然看左边
            leftHeight = Math.max(leftHeight, height[L]);
            res += leftHeight - height[L]; // 当前柱子能存放的水
            L++;
        } else { // 右边高度小，看右边
            rightHeight = Math.max(rightHeight, height[R]);
            res += rightHeight - height[R]; // 当前柱子能存放的水
            R--;
        }
    }
    return res;
};

209. Подмассив минимальной длины

209. Подмассив минимальной длины

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

Дан массив из n положительных целых чисел и положительное целое число s , найти наименьший непрерывный подмассив в массиве, сумма которого ≥ s , и вернуть его длину. Возвращает 0, если не существует подходящего подмассива.

Пример:

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

Передовой:

• Если вы уже сделали решение за время O(n), попробуйте решение за время O(n log n).

Идеи решения проблем

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

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (s, nums) {
    let len = nums.length;
    let L = 0, R = 0;
    let res = Infinity, sum = 0;
    while (R < len) {
        sum += nums[R];
        while (sum >= s) { // 滑动窗口
            res = Math.min(res, R - L + 1);
            sum -= nums[L];
            L++;
        }
        R++;
    }
    return res == Infinity ? 0 : res; // 判断合法性
};

925. Длительное нажатие ввода

925. Длительное нажатие ввода

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

Ваш друг набирает свое имя с клавиатурыname. Иногда при наборе символаc, клавиша может быть нажата и символ может быть введен 1 или более раз.

Вы проверите символы, введенные с клавиатурыtyped.如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True.

Пример 1:

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

Пример 2:

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

Пример 3:

输入：name = "leelee", typed = "lleeelee"
输出：true

Пример 4:

输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。

намекать:

• name.length <= 1000
• typed.length <= 1000
• nameа такжеtypedВсе символы представляют собой строчные буквы.

Идеи решения проблем

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

• еслиtypedа такжеnameЕсли предыдущая цифра текущего индекса не равна, то имена не соответствуют, и выскакивают напрямую Это небольшая оптимизация.
• когдаtypedВыпрыгнуть можно после прогулки, если этоi == nЕсли просто выскочить, то в этом случае: name: abc | typed: abcd рассудит об ошибке

/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function (name, typed) {
    let n = name.length; // 求出字符串长度
    let m = typed.length;
    let cnt = 0; // 统计匹配成功个数
    let i = 0, j = 0; // 双指针
    let flag = false; // 判断是否中途遇到不匹配阶段
    while (1) {
        if (name[i] == typed[j]) { // 匹配成功
            i++ , cnt++ , j++;
        } else {
            if (typed[j] == name[i - 1]) {
                j++;
            } else {
                // 如果 typed 和 name 当前索引前一位都不相等的话，那么名字就不对应，直接跳出去
                flag = true;
            }
        }
        if (flag) break;
        if (j == m) break; // 当 typed走完才能跳出去，如果是 i == n  就跳出去的话，这种情况：abc | abcd 就会判断出错
    }
    if (cnt === n && j === m) return true;
    else return false;
};

763. Разделите диапазон букв

763. Оригинальный заглавный портал, разделяющий буквенный интервал

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

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

Пример 1:

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

намекать:

• Sдлина в[1, 500]между.
• SСодержит только строчные буквы'a'прибыть'z'.

Идеи решения проблем

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

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

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

ЕстьmaxLen После этого мы также должны позволитьiуказатель, т.е.хвостовой указательПереход к этому месту - это сегмент, который мы можем сегментировать.

(Подумайте, если вы не пойдетеmaxLen Если , буквы в этом диапазоне могут иметь другие позиции, поэтому условие, что одна и та же буква появится только в одном из фрагментов, не может быть выполнено)

Ссылаться нагруппа тупых свинейИллюстрация большого парня.

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function (S) {
    let map = {}; // 用来统计当前字母最远位置
    for (let i = 0; i < S.length; i++) {
        map[S[i]] = i; // 存储当前字母当前位置
    }
    let start = 0; // 头指针
    let res = [];
    let maxLen = 0;
    for (let i = 0; i < S.length; i++) {
        let curMaxLen = map[S[i]];
        maxLen = Math.max(maxLen, curMaxLen); // 计算出当前区间范围是否还可以继续扩大区间
        if (i === maxLen) {
            let tmp = i - start + 1;
            start = i + 1;
            res.push(tmp);  // 划分片段
        }
    }
    return res;
};

нить

459. Повторяющиеся подстроки

459. Портал оригинального названия дубликата подстроки

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

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

Пример 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

Пример 2:

输入: "aba"

输出: False

Пример 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

Идеи решения проблем

Для примера строки, чтобы увидеть, повторяется ли она в одной из подстрок строки, мы можем один раз соединить исходную строку с самой собой, а затем найти первый бит (начиная с 0) исходной строки, чтобы увидеть, повторяется ли она. можно найти сплайсинг.После начала строки, т.е.s.length, то такой ситуации как повторная композиция нет, иначе есть возвратTrue.

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    return (s+s).indexOf(s,1) !== s.length
};

проиллюстрировать:

Я думаю, что некоторые друзья зададутся вопросом, а почему струнная часть только в этом вопросе?

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

• 22. Генерация кронштейна(откат)
• 20. Допустимые скобки(куча)
• 17. Буквенные комбинации телефонных номеров(возврат, поиск в глубину)

Кроме того, я хотел бы упомянуть вам, что областью действия строки является палиндром, и ряд связанных с ним задач, таких как: алгоритм конной повозки, задача о самой длинной подстроке палиндрома, как судить о палиндроме, самая длинная общая префикс и т. д., они находятся вleetcodeВсе вышеперечисленное является оригинальным, иMaraway.Я часто сталкиваюсь с алгоритмами в письменных тестах и ​​на собеседованиях, до сих пор помню, что столкнулся с ними в компании ByteDance в то время, сначала исследовал палиндром, а в итоге привлекManacherАлгоритм, если вы не слышали об этом алгоритме, это хорошо, по крайней мере, эта статья вам поможет, идите и изучите его~

Что касается вопроса про буквосочетание номера телефона, то я пропустил его в предыдущей статье.Это реальный вопрос для моего интервью с Tencent весной 2020. Я застрял с этим вопросом в то время.Я узнал позже, что это не очень сложно.один раз:

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

17. Монограмма номера телефона оригинальное название портала(возврат, поиск в глубину)

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

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

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

Пример:

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

проиллюстрировать:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

Идеи решения проблем

Используя возврат для текущей опции, мы можем повторить выбор, поэтомуforЗдесь цикл начинается с 0, для комбинации букв мы делаемmapПросто карта.

Ссылаться наxiao_ben_zhuИллюстрация большого парня

var letterCombinations = function (digits) {
  if(!digits.length) return [];
  // 直接映射
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let res = [];
  let dfs = (cur, start) => {
    if (start >= digits.length) {
      res.push(cur);
      return;
    }
    // 取当前可选的字母组合
    let str = map[digits[start]];
    for (let i = 0; i < str.length; i++) {
      dfs(cur + str[i], start + 1);
    }
  }
  dfs('', 0);
  return res;
};

Решение 2

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

var letterCombinations = function(digits) {
  if(!digits.length) return []
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let queue = []
  queue.push('')
  for(let i=0;i<digits.length;i++){
      let size = queue.length
      while(size--){
          let cur = queue.shift()
          let str = map[digits[i]]
          for(let j=0;j<str.length;j++){
              queue.push(cur+str[j])
          }
      }
  }
  return queue
};

Ссылка в этой статье

• Как внешний интерфейс подготавливает структуры данных и алгоритмы?
• Расширенное руководство по алгоритму, написанное во внешнем интерфейсе, как я решал 200 вопросов за два месяца с нулевой основой
• (1.8w слово) Двигаясь вперед с большой нагрузкой, как фронтенд-инженеры систематически практикуют структуры данных и алгоритмы? 【начальство】
• leetcode && leetcode, всем, кто решает проблемы, спасибо~

Эпилог

❤️Подписывайтесь + Нравится + Избранное + Комментарий + Пересылка ❤️, оригинальность не так проста, ваша поддержка будет моей самой большой мотивацией~

Посетите блог Чаои, друзьям удобно читать и играть~

Наконец, я желаю вам счастливого нового года, удачи в год быка, удачи ++, вы готовитесь к весеннему набору, вы можете закончить весенний набор раньше, предложение мягкое, я надеюсь, что моя статья поможет вам , скоро встретимся в следующем выпуске ~

Приходите и следуйте за мной, хотя изучение интерфейса «горько», но есть сотня статей о Шоколаде, которые будут более «сладкими» ~

【Автор: Сто шоколадок】Талант /user/298153…