Описание испытания
Напишите функцию, которая переворачивает строку. Входная строка задается как массив символов s
.
Вы должны сделать это, изменив входной массив на месте с O(1)
дополнительной памятью.
Пример 1:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Пример 2:
Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Интуиция
Мы хотим перевернуть массив символов на месте, а это означает, что мы не можем использовать дополнительную память, например, для создания нового массива.
Для этого мы будем использовать подход с двумя указателями, где мы размещаем два указателя, i и j, на двух концах массива. Мы поменяем местами символы в этих указателях, чтобы перевернуть массив.
Подход
- Мы будем использовать два указателя, i и j, инициализированные соответственно началом и концом массива.
- Пока i меньше j, выполним следующие шаги:
- Поменяйте местами символы в позициях i и j.
- Переместите i на один шаг вперед (к середине), увеличив его.
- Переместите j на один шаг назад (к середине), уменьшив его.
- Мы продолжаем повторять вышеуказанные шаги, пока i не станет меньше или равно j. Когда я становится равным или большим, чем j, весь массив будет перевернут.
Сложность
- Временная сложность:
подход с двумя указателями работает за линейное время O(N), где N — длина массива символов. Это связано с тем, что каждый элемент заменяется не более одного раза. - Сложность пространства:
Сложность пространства постоянна O(1), потому что мы не используем никакой дополнительной памяти, которая растет с размером входных данных. Мы изменяем данный массив на месте.
function reverseString(s: string[]): void { // Iterate from the beginning (i) and end (j) of the array towards the middle. for (let i = 0, j = s.length - 1; i < s.length / 2; i++, j--) { // Use a temporary variable (temp) to store the character at index i. const temp = s[i]; // Replace the character at index i with the character at index j. s[i] = s[j]; // Replace the character at index j with the character in the temporary variable (temp). s[j] = temp; } // At this point, the string array 's' contains the reversed string. }