Алгоритмы с нуля
Строки — это массивы
Ты знаешь массивы: ряд ящиков, пронумерованные, рядом. Строка — ряд символов. Алгоритмически это массив. Можешь прыгнуть на любой символ по индексу за O(1). Но строки отличаются в одном: они неизменяемы. Раз созданная, ты не можешь изменить один символ. Эта неизменяемость — скрытая ловушка: строить строку повторяющимся += в цикле тайно O(n²).
После этого урока ты сможешь видеть строку как массив символов, объяснить, почему строки неизменяемы, узнать ловушку O(n²) при конкатенации и как её исправить, применить приёмы Блока 02 (два указателя, скользящее окно) к строкам, разобраться в кодах символов и сравнении, решить классические задачи на строки.
Строка — последовательность символов, хранящихся подряд в памяти. В JavaScript (и многих других языках) строка доступна только для чтения — неизменяема. Раз создана, ты не можешь изменить один символ.
Почему видеть строку как массив?
Как массив, строка имеет:
- Индексирование с нуля:
s[0]первый символ,s[1]второй и т. д. - O(1) доступ к символу: Прыгни на любой индекс, прочти символ за константное время.
- Известная длина:
s.length— количество символов. - Обход: Цикл через
for (let i = 0; i < s.length; i++), как в массиве.
Поэтому каждый приём Блока 02 (два указателя, скользящее окно, обход) работает и на строках.
Ловушка неизменяемости: O(n²) конкатенация
Потому что строки неизменяемы, каждая операция += создаёт новую строку и копирует все символы старой в неё.
// ❌ Это O(n²)
let result = "";
for (let i = 0; i < 1000; i++) {
result += "x"; // Каждый += создаёт новую строку и копирует result в неё
}Почему O(n²)? Проследи:
- Итерация 1: скопируй 0 символов, напиши 1. Работа = 1.
- Итерация 2: скопируй 1 символ, напиши 1. Работа = 2.
- Итерация 3: скопируй 2 символа, напиши 1. Работа = 3.
- …
- Итерация n: скопируй (n-1) символов, напиши 1. Работа = n.
Итого работа = 1 + 2 + 3 + … + n = O(n²).
Для 1000 итераций ты делаешь ~500 000 копий символов. Для 10 000 итераций ~50 млн. Ловушка спрятана в невинном коде.
Исправка: собрать в массив, потом объединить
// ✅ Это O(n)
const result = [];
for (let i = 0; i < 1000; i++) {
result.push("x"); // Array push O(1) амортизировано
}
const str = result.join(""); // Одна join-операция O(n)Почему O(n)? Push — O(1) амортизировано (без копирования). Join проходит массив раз и строит финальную строку за один проход.
Символы и их коды
Каждый символ имеет числовой код. В JavaScript используй charCodeAt(i) для получения кода и String.fromCharCode(code) для создания символа из кода.
'a'.charCodeAt(0); // 97
'z'.charCodeAt(0); // 122
String.fromCharCode(97); // 'a'Коды символов упорядочены: 'a' = 97, 'b' = 98, …, 'z' = 122. Когда ты сравниваешь символы с < или >, ты сравниваешь их коды. Поэтому 'a' < 'b' истинно.
Приёмы Блока 02 на строках
Все техники, что ты выучил, работают на строках:
- Два указателя: Проверь, палиндром ли строка (сравни противоположные концы).
- Скользящее окно: Найди самую длинную подстроку с уникальными символами.
- Обход: Считай, сколько раз появляется каждый символ, ищи паттерн.
- Модификация на месте: Построй новую строку из конкретных символов.
Запрограммируем классические задачи на строки:
1. Проверка палиндрома двумя указателями (противоположные концы):
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false; // Несовпадение: не палиндром
}
left++;
right--;
}
return true; // Все пары совпали
}2. Подсчёт символов (обход + аккумулятор):
function charCount(s) {
const count = {};
for (let i = 0; i < s.length; i++) {
const char = s[i];
count[char] = (count[char] || 0) + 1;
}
return count;
}3. Построить строку эффективно (сбор в массив + join):
function repeatChar(ch, n) {
const chars = [];
for (let i = 0; i < n; i++) {
chars.push(ch);
}
return chars.join(""); // O(n) итого
}Попробуй запустить:
Проследи проверку палиндрома шаг за шагом на “racecar”:
1
function isPalindrome(s) {
2
let left = 0, right = s.length - 1;
3
while (left < right) {
4
if (s[left] !== s[right]) return false;
5
left++;
6
right--;
7
}
8
return true;
9
}
Теперь проследи ловушку конкатенации vs. эффективное исправление:
Для 5 итераций построить “xxxxx”, наивный способ +=:
- Итер 1: скопируй "", добавь “x” → “x” (работа = 1)
- Итер 2: скопируй “x”, добавь “x” → “xx” (работа = 2)
- Итер 3: скопируй “xx”, добавь “x” → “xxx” (работа = 3)
- Итер 4: скопируй “xxx”, добавь “x” → “xxxx” (работа = 4)
- Итер 5: скопируй “xxxx”, добавь “x” → “xxxxx” (работа = 5)
Итого: 1+2+3+4+5 = 15 копий символов.
Эффективный способ: push 5 раз (5 × O(1) = O(5)), потом join раз (O(5) построить строку). Итого: ~10 операций.
Операции со строками и их стоимость:
| Операция | Пример | Время |
|---|---|---|
| Доступ к символу по индексу | s[5] | O(1) |
| Получить длину | s.length | O(1) |
| Проверить палиндром (два указателя) | isPalindrome(s) | O(n) |
| Подсчитать символы (обход) | charCount(s) | O(n) |
| Построить += в цикле | result += s[i] повторяющийся | O(n²) ❌ |
| Построить массив + join | arr.push(); arr.join() | O(n) ✅ |
| Скользящее окно подстрока | longestUnique(s) | O(n) |
Ловушка конкатенации—почему это важно:
Для строки 1000 символов, построенной += в цикле, ты делаешь ~500 000 копий символов. Для 10 000 символов ~50 млн. Код выглядит простым, но скрытая стоимость квадратична.
Использование массива + join всегда лучше при построении строк из частей.
Почему индексирование строки (например, s[5]) O(1), если строки неизменяемы?
Какова сложность этого кода? let result = ''; for (let i = 0; i < 1000; i++) { result += 'x'; }
Как исправить ловушку O(n²) конкатенации?
Проверь, 'level' палиндром ли двумя указателями. Что вернёт isPalindrome('level')? (1 = правда, 0 = ложь)
Если считаешь символы в строке циклом (charCount), какова сложность?
Частая ошибка
Построить строку += в цикле. Ты пишешь let result = ""; for (let i = 0; i < n; i++) { result += someStr[i]; } и думаешь O(n). Но каждый += на самом деле создаёт новую строку и копирует старую в неё. Получаешь O(n²) работу — та же ловушка, что ловит людей, строящих списки во многих языках. Исправка: всегда используй массив и join.
Граничные случаи
Пустая и однозначная строки. Строка длины 0 ведёт себя как массив длины 0: индексирование за границей, циклы не бегут. Строка длины 1 имеет один символ на индексе 0; циклы двух указателей выходят сразу (left < right это 0 < 0 = ложь). Оба граничных случая правильно обработаны алгоритмами.
Строка неизменяема в JavaScript, поэтому ты не можешь изменить символ на месте. Как эта неизменяемость ведёт к ловушке O(n²) конкатенации?
Строка — это массив символов—она индексирована, подряжная, и доступ к любому символу за O(1).
Ключевые факты:
-
Строки неизменяемы: Раз созданы, ты не можешь изменить символ на месте. Каждое изменение создаёт новую строку.
-
Индексирование символа O(1): Как в массиве, прыгни на
s[i]прямо без сканирования. -
Ловушка конкатенации O(n²): Каждый += копирует всю строку до. Построить строку символ за символом O(n²) работы.
-
Исправка массив + join: Заталкивай символы в массив (O(1) амортизировано каждый), потом объедини раз (O(n)). Итого: O(n).
-
Приёмы Блока 02 работают на строках: Два указателя на палиндромы, скользящее окно на подстроки, обход на подсчёт символов.
-
Символы упорядочены по коду:
'a'<'b'< … <'z'. ИспользуйcharCodeAt(i)для числового кода.
Ты теперь имеешь весь инструментарий Блока 02: массивы, обход, два указателя, скользящее окно, префиксные суммы, модификация на месте, и строки как массивы. Дальше ты выучишь, как отсортировать данные и искать эффективно в отсортированных массивах.