1. Two Sum:
Дано: задан массив целых чисел nums и целое число target, верните индексы двух чисел массива nums сумма которых равна target.
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i
Предыдущая версия помогает легче понять текущее решение: записываем в хэш таблицу разность target и текущего элемента цикла, которое соответственно должно быть равно второму числу, которое будет искаться дальше в цикле, когда пара находится, выдаём ответ.
Временная сложность: цикла даёт сложность O(n)
Пространственная сложность: используем хэш-таблицу hashmap, которая может хранить до N элементов, то есть получаем O(n)
9. Palindrome Number:
Дано: задано целое число x, вернуть True, если x является палиндромом
и False в противном случае.
def isPalindrome(x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0):
return False
currentValue= x
newValue= 0
while x>0:
newValue= newValue* 10 + x%10
x = x//10
return newValue == currentValue
Для начала необходимо определить переменную newValue, в которой будет храниться перевернутое число. Затем используем алгоритм, придуманный для этого действа: пока исходное число не станет равным 0, будем извлекать последнюю цифру числа, то есть отсекать поразрядно значения, с помощью операции взятия остатка от деления на 10 (x % 10)и добавлять ее в конец результирующего числа, умножая его на 10. После каждой итерации исходное число currentValue целочисленно делится на 10 (x//10), чтобы отбросить уже обработанную последнюю цифру.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем две переменные O(1) + O(1) дополнительной памяти, поэтому O(1).
13. Roman to Integer
Дано: Преобразуйте римские цифры (s) в целое число.
def romanToInt(s: str) -> int:
roman_to_integer= {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
result= 0
for i in range(len(s)):
if i < len(s) - 1 and roman_to_integer[s[i]] < roman_to_integer[s[i + 1]]:
ans -= roman_to_integer[s[i]]
else:
result+= roman_to_integer[s[i]]
return result
Проходим цикл, если символ не последний в строке и следующий символ больше по таблице соответствия текущего вычитаем из переменной result
Временная сложность: цикла даёт сложность O(n)
Пространственная сложность: используем числовую переменную result, дающую O(1)
14. Longest Common Prefix
Дано: Напишите функцию для поиска самой длинной строки с общим префиксом среди массива строк. Если общего префикса нет, то возвращается пустая строка "".
def longestCommonPrefix(self, v: List[str]) -> str:
ans = ""
v = sorted(v)
first = v[0]
last = v[-1]
for i in range(min(len(first), len(last))):
if (first[i] != last[i]):
return ans
ans += first[i]
return ans
Создаём переменную для хранения подстроки одинаковых символов ans.
Сортируем наш массив, это нужно для того, чтобы первый элемент первой строки совпадал с первым элементом последней строки...иначе нету одинаковых элементов. Перебираем символы первой и последней строк в отсортированном списке по минимальным строкам в массиве. Если текущий символ первой строки не равен текущему символу последней строки, то возвращается найденный на данный момент общий префикс. Иначе текущий символ добавляется в строку ans.
Временная сложность: цикл даёт сложность O(n), , sorted() O(nlogn?), что даёт общую сложность O(nlogn).
Пространственная сложность: используем строку и 2 числовых переменных, что даёт O(1)
20. Valid Parentheses
Дано: Задана строка s, содержащая только символы '(', ')', '{', '}', '[' и ']'. Определите, является ли эта строка корректной.
def isValid(s: str) -> bool:
parenthesis= {'(': ')', '{': '}', '[': ']'}
stack = []
for i in s:
if i in parenthesis:
stack.append(i)
elif len(stack) == 0 or parenthesis[stack.pop()] != i:
return False
return stack== []
Создаём список для оперирования строкой leftSymbols. Пройдем по строке циклом слева направо., если правая скобка и стек пуст (значит, нет совпадающей левой скобки), или последняя левая скобка в списке не совпадает с текущим i, то есть правой скобкой, возвращаем False.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем список, дающий нам сложность O(n)
26. Remove Duplicates from Sorted Array
Дано: из целочисленного отсортированного массива nums, удалить дубликаты.
Изменить массив nums таким образом, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, так же как и размер nums. Вернуть k.
def removeDuplicates(nums: List[int]) -> int:
i = 1
while i < len(nums):
if nums[i] == nums[i - 1]:
nums.pop(i)
else:
i += 1
return len(nums)
Простой хороший вариант с использованием свойства pop(), удаление элемента по индексу. Проходим циклом, удаляем повторяющиеся элементы
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: O(1).
27. Remove Element
Дано: целочисленный массив nums и целое число val, требуется удалить все вхождения val в массив. Вернуть количество оставшихся элементов в nums. (Изменить нужно исходный массив, а не создавать новый).
def removeElement(nums: List[int], val: int) -> int:
index = 0
for i in range(len(nums)):
if nums[i] != val:
nums[index] = nums[i]
index += 1
return index
Создаём вспомогательную переменную и прибавляем к ней все элементы не равные заданному значению, параллельно переназначая индексы элементов.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: вспомогательная переменная даёт сложность O(1).
28. Find the Index of the First Occurrence in a String
Дано: две строки needle и haystack, вернуть индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.
def strStr(haystack: str, needle: str) -> int:
if needle == haystack:
return 0
i = 0
j = len(needle)
while j <= len(haystack):
currentNeedle = haystack[i:j]
if currentNeedle == needle:
return i
i += 1
j += 1
return -1
Если needle не равна haystack, то функция инициализирует две переменные: i - начальный индекс подстроки haystack и j - конечный индекс этой подстроки. Первоначально i устанавливается в 0, а j - в длину списка needle.
Затем используем цикл, который продолжается до тех пор, пока j не станет больше длины haystack. На каждой итерации цикла функция извлекает подстроку из haystack, которая начинается с индекса i и заканчивается индексом j - 1. Эта подстрока сохраняется в переменной currentNeedle. Затем функция сравнивает currentNeedle с needle. Если они равны, то это означает, что needle является подстрокой haystack, начинающейся с индекса i. Если currentNeedle не равен needle, то функция увеличивает i и j на 1 и продолжает следующую итерацию цикла.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем две переменные O(1) + O(1) дополнительной памяти, поэтому O(1).
35. Search Insert Position
Дано: отсортированный массив целых чисел и целочисленное значение target, верните индекс target. Если target нету в списке , верните индекс, в котором он находилась бы.
def searchInsert(nums: List[int], target: int) -> int:
min = 0
max = len(nums)
while min < max:
m = (min + max) // 2
if nums[m] == target:
return m
if nums[m] < target:
min = m + 1
else:
max = m
return min
Применяется обычный алгоритм бинарного(двоичного) поиска
Временная сложность: O(logN) (так как мы уменьшаем срез массива на 2 на каждой итерации и проверяем только 1 элемент),
Пространственная сложность: O(1).
58. Length of Last Word
Дано: задана строка s, состоящая из слов и пробелов, верните длину последнего слова в строке.
def lengthOfLastWord(s: str) -> int:
result = 0
for i in range(len(s) - 1, -1, -1):
if s[i] != " ":
result += 1
elif result:
return result
return result
Проходим строку из конца в начало, если элемент не пробел прибавляем единицу и целочисленной переменной result, когда находим пробел, возвращаем переменную result.
Временная сложность: Цикл даёт нам сложность O(n)
Пространственная сложность: хранение переменной даёт нам O(1)