предисловие
Эта статья была включенаGitHub https://github.com/ponkans/F2E(Существует большое дерево знаний и навыков, организованное Weiwei), добро пожаловать, Звезда, продолжайте обновлять 💧
Честно говоря, когда я впервые писал алгоритм, я немного нервничал, ведь это был гарнир, который не мог пройти математику.
В конце первого года обучения, четвёртый снизу в классе, паф, отморозок реально забит~
Прежде чем писать, я думал о том, как бы написать алгоритмы поинтереснее, прямо как урок математики высокого уровня в университете.Честно говоря, то, о чем говорил преподаватель, было очень скучно. .
Если это не ограничено так называемыми академическими правилами, это действительно тяжело слушать.
Пусть M(x0,y0,z0) — известная точка на плоскости, n=(A,B,C) — вектор нормали, а M(x,y,z) — любая точка на плоскости, тогда точка формула самолета Уравнение хххх, и я заснул, слушая его. . . (Учитель, я больше не могу!!)
Поэтому Weiguai постарается написать его как можно интереснее, чтобы вы почти запомнили идею этого алгоритма после прочтения.
Сегодняшняя тема такая, по заданной строке найдите ту, которая не содержит повторяющихся символовсамая длинная подстрокадлина.
Кратко объяснить.
Например, учитывая строку "Связь водяного монстра CC"
Первый шаг — найти подстроку строки, не содержащую повторяющихся символов.
- С
- С-соединение
- С вода
- водяной монстр С
- водяной монстр
Второй шаг — вычислить длину каждой подстроки и взять максимальное значение.
- Максимальное значение здесь, очевидно, равно 4, поэтому ответ равен 4.
хорошо, после завершения примера на самом деле очень легко обнаружить, что ядро — это первый шаг, чтобы найти подстроку, которая не содержит повторяющихся символов.
Так как же мне его найти?Для того,чтобы было проще понять друзьям,которые впервые смотрят на этот алгоритм,я нарисовал несколько картинок.Если вы не поняли после прочтения,добавьте пожалуйста WeChat и ругайте меня.отморозокОтлично!
Найдите два пистолета, оба направлены на первого персонажа в начале.
Мы успешно нашли первую неповторяющуюся подстроку "C".
Затем оставьте красный пистолет неподвижным, а зеленый переместится на одну позицию назад.
В это время было обнаружено, что между двумя орудиями символы повторялись,Найдите позицию, которая повторяется с помощью зеленого пистолета, и переместите красный пистолет в следующую позицию повторяющейся позиции., то становится вот так.
Итак, мы обнаружили, что вторая неповторяющаяся подстрока, как и первая, тоже «C».
Не паникуй, переходим к зеленому пистолету.
Так как в процессе перемещения между красной и зеленой пушками не было повторения, мы нашли неповторяющиеся подстроки "С-подключен", "К-подключен к воде", "К-подключен к водному монстру"
Не торопитесь, не торопитесь, это еще не конец, тогда двигайте зеленую пушку (зеленая пушка достигла последней позиции, все кончено)
Можно обнаружить, что когда мы перемещаем зеленый пистолет в положение «подключиться», подстрока между красным и зеленым повторяет «подключение», поэтому мы по-прежнему следуем предыдущей повторяющейся идее:
- Найдите позицию, в которой повторяющийся символ «соединяется»
- Переместите красный пистолет в последнюю часть позиции, которая является «водой».
- Получите неповторяющуюся подстроку между красным и зеленым «соединением водяного монстра».
Отсюда видно, что когда нашиЗеленая пушка перемещается в последнюю позицию, наш поиск завершен, и мы нашли все неповторяющиеся подстроки.
На самом деле красные и зеленые пушки вверху, другими словами, это левый и правый указатели. Перемещение красных и зеленых пушек означает перемещение левого и правого указателей. Окно между двумя указателями и есть тот результат, который нам нужен.
Так же, как когда мы вырезали видео, мы перетаскивали материал, который фиксирует ход видео. .
Такую идею решения проблем часто называют скользящим окном.
После понимания идеи писать код на самом деле относительно просто.
Перейдите сразу к исходной теме и коду LeetCode, я написал в комментариях несколько крайних случаев (Внимательно смотрите комментарии, будут проблемы, если границы прописаны не правильноОй). Убрать комментарий про 10 строчек кода.Рекомендуется делать это в первый раз,можете написать.Поверьте,вы сможете это написать.
Может быть, вы начнете свое путешествие по алгоритму LeetCode💗~
резюме
Вопрос о скользящем окне на самом деле заключается в том, чтобы выяснить, какова граница скольжения влево и вправо [съесть дыню]. Например, когда левое окно в приведенном выше вопросе сжимается, это ключ.
Я открыл колонку серии алгоритмов, и в будущем я напишу некоторые темы, связанные с алгоритмами.В ближайшем будущем алгоритмы должны быть связаны со скользящим окном.
В последнем резюме Национального дня упоминались некоторые технологии, и есть большая вероятность, что статья будет опубликована в этом ритме в ближайшее время.
- Исходный код Redux, дизайнерские идеи
- Промис, генератор, асинхронный ожидание исходного кода (ведь он часто используется в работе, его нужно видеть)
- Анализ исходного кода общих хуков (новый стек технологий компании — React)
- алгоритм
Я водяной монстр, обычный программист. Спасибо за внимание и даже 3 💕😊
Свяжитесь со мной / публичный аккаунт
Поиск в WeChat【водяной монстр] Или отсканируйте QR-код ниже, чтобы ответить на «Добавить группу», я приглашу вас в группу технического обмена. Честно говоря, в этой группе, даже если вы не говорите, просто чтение записей чата — это своего рода рост. (Али технический эксперт, автор Ao Bing, Java3y, старший клиент Mogujie, эксперт по безопасности Ant Financial, там все большие коровы).
Водяной монстр также будет регулярно создавать оригиналы, регулярно обмениваться опытом с небольшими партнерами или помогать читать резюме. Будьте внимательнее, не теряйтесь, есть возможность побегать вместе 🏃↓↓↓