Algorithms Flashcards
Two Sum
# arrays # dicts
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
def twoSum(nums: List[int], target: int) -> List[int]:
nums_dict = {}
# создаем словарь значение:индекс
for i in range(len(nums)):
if nums[i] not in nums_dict:
nums_dict[nums[i]] = i
else:
if nums[i] * 2 == target:
return [nums_dict.get(nums[i]),i]
# проход по индексам списка
for i in range(len(nums)):
x = nums[i]
y = target - x
if x!=y and y in nums_dict:
return [i,nums_dict[y]]
Add Two Numbers # linked lists You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
# Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0 # остаток от суммы (если > 10)
res = None
r = None
while l1 or l2 or carry:
d1 = l1.val if l1 else 0
d2 = l2.val if l2 else 0
sum = d1 + d2 + carry
carry = sum // 10;
resNode = ListNode(sum % 10)
if res:
res.next = resNode
else:
r = resNode
res = resNode
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return r
Longest Substring Without Repeating Characters # strings Given a string, find the length of the longest substring without repeating characters.
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
def lengthOfLongestSubstring(self, s: str) -> int:
start = 0
sub_max = 0
# проходим по срезу строки, сдвигая границы: если символ имеет индекс -1 в текущей подстроке, длина текущей подстроки больше sub_max, увеличиваем sub_max. Иначе сдвигаем первую границу подстроки
for end in range(len(s)):
c = s[end]
c_index = s.find(c, start, end)
if c_index != -1:
start = c_index + 1
else:
if (end-start) + 1 > sub_max:
sub_max += 1
return sub_max
ZigZag Conversion
# strings
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this:
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
def convert(s: str, numRows: int) -> str:
if numRows == 1:
return s
res = “”
d = 0
k = 0
# пока результирующая строка не сравняется с исходной: прибавляем к ней по символу из двух индексов, прибавляем символ по третьему индексу, если второй не нулевой и меньше числа рядов на 1 и третий индекс меньше длины строки. Первый индекс увеличиваем на двойное число рядов минус 2.
while len(res) != len(s):
res += s[d + k]
if k != 0 and k != numRows - 1:
ind = d + 2 * numRows - 2 - k
if ind < len(s):
res += s[ind]
d += 2 * numRows - 2
# если сумма индексов больше длины строки, обнуляем первый индекс и увеличиваем второй
if d + k >= len(s):
d = 0
k += 1
return res
Reverse Integer # numbers # arithmetic Given a 32-bit signed integer, reverse digits of an integer.
Input: 123
Output: 321
def reverse(self, x: int) -> int:
r = 0
p = 1
// если число отрицательное, берем его модуль и умножаем на -1
if x < 0:
x = abs(x)
p = -1
// циклом делим число на 10, получаем последнюю цифру и прибавляем ее к результату, умноженному на 10
while x != 0:
t = x % 10
x = x // 10
r = r * 10 + t
r = r * p
#if r > 2**31 or r <= -2**31:
# return 0
return rPalindrome Number # numbers # arithmetic Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
def isPalindrome(self, x: int) -> bool:
if(x < 0 or (x % 10 == 0 and x != 0)):
return False
// сохраняем исходное число в отдельной переменной
r = 0
k = x
// циклом делим число на 10, пока перевертыш меньше. Прибавляем последнюю цифру числа к перевертышу, умноженному на 10. В конце проверяем равенство чисел или первой цифры перевертыша
while r < k:
r = r * 10 + k % 10
k = k // 10
return r == k or k == r // 10Integer to Roman # numbers # strings # dicts Convert integers to Roman numbers 3 -> III 9 -> IX
def intToRoman(self, num: int) -> str:
// заводим словарь соответствий арабских цифр римским
d = {
1000: ‘M’, 900: ‘CM’, 500: ‘D’, 400: ‘CD’, 100: ‘C’,
90: ‘XC’, 50: ‘L’, 40: ‘XL’, 10: ‘X’, 9: ‘IX’, 5: ‘V’, 4: ‘IV’,
1: ‘I’
}
res = ‘’
// проходимся циклом по словарю: к выходной строке прибавляем значение, умноженное на результат целого деления числа на ключ, берем остаток от деления числа на ключ
for i in d:
res += (num//i) * d[i]
num %= i
return res
Roman to Integer # numbers # strings # dicts Convert a Roman number into integer III -> 3 LVIII -> 58
def romanToInt(s: str) -> int:
res = 0
// заводим словарь соответствий римских цифр арабским
roman = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
prev = 0 // переменная для сохранения предыдущего значения
// проходимся циклом по перевернутой строке: если пред. значение больше текущего, вычитаем текущее из результата, иначе прибавляем его
for i in s[::-1]:
current = roman[i]
if prev > current:
res -= current
else:
res += current
prev = current
return resLongest Common Prefix # strings Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Input: ["flower","flow","flight"] Output: "fl"
def longestCommonPrefix(self, strs: List[str]) -> str:
if not len(strs) or not len(strs[0]):
return ""
// цикл по индексам первого слова массива
for i in range(len(strs[0])):
// цикл по словам массива после первого: если индекс больше длины текущего слова или буква с текущим индексом не соответствует букве первого слова с тем же индексом, вернуть срез первого слова до этого индекса
for s in strs[1::]:
if len(s) <= i or s[i] != strs[0][i]:
return strs[0][:i]
return strs[0]Letter Combinations of a Phone Number
# strings # dicts
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
def letterCombinations(self, digits: str) -> List[str]:
// составляем словарь соответствий цифр буквам
phone = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
if digits:
// составляем список с буквами по первой цифре номера
res = list(phone[digits[0]])
// цикл по цифрам номера после первой: копируем содержимое результирующего массива в другой массив, результирующий обнуляем
for d in digits[1:]:
temp = res
res = []
// цикл по буквам отдельных цифр
for letter in phone[d]:
// цикл по сочетаниям рабочего массива: прибавляем текущую букву к сочетанию, сохраняем в результирующий массив
for chars in temp:
chars+=letter
res.append(chars)
return res
else:
return []Merge Two Sorted Lists # linked lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
# Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = None
// сначала определяем корневую ноду итогового списка: сравниваем значения и переставляем указатель на следующую ноду
if not l1 and not l2:
return None
if l1 and (not l2 or l1.val < l2.val):
res = l1
l1 = l1.next
else:
res = l2
l2 = l2.next
head = res
// цикл по оставшимся нодам: сравниваем значения и переставляем указатели
while True:
if not l1:
res.next = l2
break
if not l2:
res.next = l1
break
if l1.val < l2.val:
res.next = l1
l1 = l1.next
else:
res.next = l2
l2 = l2.next
res = res.next
return head
Search in Rotated Sorted Array
# arrays # search
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
def search(self, nums: List[int], target: int) -> int:
def binarySearch(arr, x, left_bound, right_bound):
if right_bound == left_bound - 1:
return -1
// определяем серединный индекс
mid = (left_bound + right_bound+1) // 2
if arr[mid] == x:
return mid
// если значение левой границы меньше серединного значения, проверяем, входит ли искомое значение в этот промежуток, если да, то выполняем поиск в левой части от середины, иначе поиск в правой части
if arr[left_bound] < arr[mid]:
if arr[left_bound] <= x <= arr[mid]:
return binarySearch(arr, x, left_bound, mid - 1)
else:
return binarySearch(arr, x, mid + 1, right_bound)
// если искомое значение больше середины и меньше правой границы, выполняем поиск в правой части, если нет, то в левой части
else:
if arr[right_bound] >= x > arr[mid]:
return binarySearch(arr, x, mid + 1, right_bound)
else:
return binarySearch(arr, x, left_bound, mid - 1)
return binarySearch(nums,target,0,len(nums)-1)
Group Anagrams # strings # anagrams # dicts Given an array of strings, group anagrams together. Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
// составляем словарь, в котором ключи - кортеж букв, а значения - составленные из них слова, имеющиеся в массиве. Проходимся циклом по словам массива. Делаем ключ из кортежа букв слова, значением делаем массив с этим словом (проверяя, есть ли уже значение ключа. В конце возвращаем список значений словаря
for w in strs:
key = tuple(sorted(w))
d[key] = d.get(key, []) + [w]
return list(d.values())Maximum Subarray
# arrays
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
def maxSubArray(self, nums: List[int]) -> int:
// делаем массив из 0 длиной исходного массива, первые элементы одинаковы
dp = [0]*len(nums)
dp[0] = nums[0]
// проходимся по индексам первого массива: записываем во второй массив либо число из первого массива с этим индексом, либо сумму числа из первого массива с текущим индексом и числа из второго массива с предыдущим индексом (что больше). В конце возвращаем максимум второго массива
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i-1]+nums[i])
return max(dp)Minimum Path Sum # arrays # graphs # matrices Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
def minPathSum(self, grid: List[List[int]]) -> int:
// создаем нулевую матрицу той же размерности
m = len(grid)
n = len(grid[0])
matrix = [[0 for i in range(n)] for i in range(m)]
// заполняем первый столбец и первый ряд матрицы кумулятивными суммами из 1го столбца и 1го ряда исходного массива
sums = 0
for i in range(n):
sums += grid[0][i]
matrix[0][i] = sums
sums = 0
for j in range(m):
sums += grid[j][0]
matrix[j][0] = sums
// проходимся по матрице (индексы), заполняем элементы: минимальное значение из соседних элементов сверху и слева плюс значение из исходной матрицы на этом же месте. В конце возвращаем самый правый нижний элемент
for i in range(1,m):
for j in range(1,n):
matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1]) + grid[i][j]
return matrix[m-1][n-1]
Best Time to Buy and Sell Stock II
# arrays
Say you have an array prices for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
def maxProfit(self, prices: List[int]) -> int:
profit = 0
// проходимся циклом по индексам массива: если следующий элемент больше предыдущего, прибавляем их разность к профиту
for i in range(len(prices)-1):
if prices[i+1] - prices[i] > 0:
profit += (prices[i+1] - prices[i])
return profit
Single Number # arrays Given a non-empty array of integers, every element appears twice except for one. Find that single one. Input: [2,2,1] Output: 1
def singleNumber(self, nums: List[int]) -> int:
i = 0
// проходимся циклом по массиву: если количество вхождений числа равно 1, возвращаем это число, иначе сдвигаем индекс
while nums:
if nums.count(nums[i]) == 1:
return nums[i]
else:
i += 1
Min Stack # stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
E.g. MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
class MinStack:
// конструктор с массивом значений
def \_\_init\_\_(self):
self.stack = []
// при добавлении нового элемента в стек сравниваем его с текущим минимумом, потом добавляем в массив кортеж (значение, текущий минимум)
def push(self, x: int) -> None:
curMin = self.getMin()
if curMin is None or x < curMin:
curMin = x
self.stack.append((x, curMin))
def pop(self) -> None:
self.stack.pop()
// возвращаем нулевой элемент последнего кортежа
def top(self) -> int:
if len(self.stack) == 0:
return None
else:
return self.stack[-1][0]
// возвращаем первый элемент последнего кортежа
def getMin(self) -> int:
if len(self.stack) == 0:
return None
else:
return self.stack[-1][1]
Number of Islands # arrays # graphs Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Input: 11110 11010 11000 00000
Output: 1
def numIslands(self, grid: List[List[str]]) -> int:
islands = 0
// проходимся циклом по матрице: если элемент равен 1, увеличиваем счетчик островов и выполняем поиск в глубину соседних элементов, чтобы объединить их всех как один остров
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == ‘1’:
islands += 1
self.dfs(grid, i, j)
return islands
// функция для поиска в глубину
def dfs(self, grid, r, c):
grid[r][c] = ‘0’ // отмечаем посещенный элемент 0
// проходимся циклом по соседям данного элемента: если индексы не выходят на пределы матрицы и элемент равен 1, выполняем поиск с него
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr = dr + r
nc = dc + c
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == ‘1’:
self.dfs(grid, nr, nc)
LRU Cache
# linked lists # dicts
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a positive capacity.
LRUCache cache = new LRUCache(2);
cache. put(1, 1);
cache. put(2, 2);
cache. get(1); // returns 1
cache. put(3, 3); // evicts key 2
cache. get(2); // returns -1 (not found)
cache. put(4, 4); // evicts key 1
cache. get(1); // returns -1 (not found)
cache. get(3); // returns 3
cache. get(4); // returns 4
// используется класс ноды со своими ключом, значением, и указателями на след. и пред. ноды class ListNode(object):
def \_\_init\_\_(self, key: int, val: int):
self. key = key
self. val = val
self. prev = None
self. next = None
class LRUCache:
// в конструкторе заводятся головная нода, хвост, словарь с ключами и значениями нод, максимальный объем и текущий размер (0)
def \_\_init\_\_(self, capacity: int):
self.head = ListNode(-1, -1)
self.tail = self.head
self.key2node = {}
self.capacity = capacity
self.length = 0
// если ключа нет в словаре кеша, возвращаем -1
def get(self, key: int) -> int:
if key not in self.key2node:
return -1
node = self.key2node[key]
val = node.val
// если у найденной ноды есть след.указатель, то перемещаем след.указатель предыдущей ноды на следующую ноду, пред.указатель следующей ноды на предыдущую ноду, след.указатель хвоста на ноду, пред.указатель ноды на хвост, обнуляем след.указатель ноды, делаем ноду хвостом
if node.next:
node.prev.next = node.next
node.next.prev = node.prev
self.tail.next = node
node.prev = self.tail
node.next = None
self.tail = node
return val
def put(self, key: int, value: int) -> None:
// если ключ уже есть в словаре кеша, то заменяем его значение
if key in self.key2node:
node = self.key2node[key]
node.val = value
// если у ноды есть указатель на след. ноду, то перемещаем след.указатель предыдущей ноды на следующую, пред.указатель следующей ноды на предыдущую, след.указатель хвоста на ноду, пред.указатель ноды на хвост, обнуляем след.указатель ноды, и делаем ноду хвостом
if node.next:
node.prev.next = node.next
node.next.prev = node.prev
self.tail.next = node
node.prev = self.tail
node.next = None
self.tail = node
else:
// иначе заводим новую ноду с ключом и значением, пару ключ-значение добавляем в словарь кеша, ставим след. указатель от хвоста к ноде, пред.указатель от ноды к хвосту, делаем ноду хвостом, увеличиваем размер кеша
node = ListNode(key, value)
self.key2node[key] = node
self.tail.next = node
node.prev = self.tail
self.tail = node
self.length += 1
// если размер кеша превышает допустимый объем, то следующую ноду после головы отмечаем на удаление, перемещаем след. указатель от головы на ноду после удаляемой, перемещаем пред.указатель ноды после головы на голову, удаляем из словаря кеша ключ удаляемой ноды, уменьшаем размер кеша
if self.length > self.capacity:
remove = self.head.next
self.head.next = self.head.next.next
self.head.next.prev = self.head
del self.key2node[remove.key]
self.length -= 1
Bitwise AND of Numbers Range # bitwise Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Input: [5,7] Output: 4
def rangeBitwiseAnd(self, m: int, n: int) -> int:
i = 0
// пока границы диапазона не стали равны друг другу, выполняем побитовый сдвиг вправо (делим на 2^1) и увеличиваем счетчик. В конце выполняем побитовый сдвиг влево правой границы (умножаем на 2^i)
while m != n:
m >>= 1
n >>= 1
i += 1
return n << iHappy Number # numbers # arithmetic Write an algorithm to determine if a number n is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Return True if n is a happy number, and False if not. Input: 19 Output: true Explanation: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
def isHappy(self, n: int) -> bool:
// функция для вычисления суммы цифр
def getSum(n:int) -> int:
sums = 0
while n:
sums += (n%10) ** 2
n //= 10
return sums
// заводим множество для хранения уже встречавшихся значений
seen = set()
// циклом вычисляем сумму цифр, если результат вычисления уже есть во множестве встречавшихся, выходим из цикла и возвращаем ложь, иначе добавляем во множество
while n != 1:
n = getSum(n)
if n in seen:
return False
else:
seen.add(n)
else:
return TrueProduct of Array Except Self # arrays # arithmetic Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Input: [1,2,3,4] Output: [24,12,8,6]
def productExceptSelf(self, nums: List[int]) -> List[int]:
// заводим второй массив из единиц
arr = [1] * len(nums)
pi = pj = 1
// проходимся циклом по индексам массива, заводим второй индекс, идущий с конца. Элементы с этими индексами умножаем на указатели pi, pj, после указатели умножаем на числа тех же индексов из первого массива
for i in range(len(nums)):
j = -1-i
arr[i]*=pi
arr[j]*=pj
pi *= nums[i]
pj *= nums[j]
return arr
Move Zeroes # arrays Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Input: [0,1,0,3,12] Output: [1,3,12,0,0]
def moveZeroes(self, nums: List[int]) -> None:
// подсчитываем количество нулей в массиве
zeroes = nums.count(0)
// циклом удаляем нули из массива
while 0 in nums:
nums.remove(0)
// прибавляем к массиву новый массив из нулей
nums.extend([0]*zeroes)
Contiguous Array
# arrays
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
def findMaxLength(self, nums: List[int]) -> int:
// заводим переменную-счетчик, словарь для индексов и счетчика, максимальную длину подмассива
c,d,m = 0,{0:0},0
// проходимся циклом по списку кортежей (индекс, значение): прибавляем к счетчику 0 или 1 в зависимости от значения. Если значение счетчика уже есть в словаре, проверяем, что больше: максимальная длина или подстрока индекс+1 - значение из словаря по счетчику? Если нет в словаре, добавляем запись счетчик : индекс + 1
for i,v in enumerate(nums):
c += 2*v -1
if c in d:
m = max(m,i+1-d[c])
else:
d[c] = i+1
return m
Jump Game # arrays Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
def canJump(self, nums: List[int]) -> bool:
// переменная для самого дальнего индекса
j = 0
// для каждого индекса, длина прыжка которого равна значению, определяем максимальную длину прыжка (если индекс+значение больше текущего максимума, переопределяем максимум). Если максимум меньше текущего индекса, то него никак нельзя прыгнуть, поэтому сразу возвращаем false
for ind, val in enumerate(nums):
if j < ind:
return False
j = max(j, ind+val)
return TrueDiameter of Binary Tree # trees # graphs Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
# Definition for a binary tree node. # class TreeNode: # def \_\_init\_\_(self, x): # self.val = x # self.left = None # self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.res = 0
// функция для поиска в глубину
def dfs(node):
if node == None:
return 0
// выполняем поиск в глубину левого узла и правого узла, определяем максимум текущий результат vs левый узел + правый узел, возвращаем максимум из левого и правого узла + 1
l = dfs(node.left)
r = dfs(node.right)
self.res = max(self.res,l+r)
self.res = max(self.res,max(l,r))
return max(l,r) +1
dfs(root)
return self.res
Subarray Sum Equals K # arrays # dicts Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Input:nums = [1,1,1], k = 2
Output: 2
// если кумулятивная сумма элементов массива увеличилась на k, значит, это нужная подпоследовательность
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
sums = 0
d = {0:1}
// проходимся по индексам массива: прибавляем к сумме значение по индексу, к счетчику значение из словаря по ключу (сумма - к), или 0, если такого нет, в словарь добавляем новую запись сумма-ключ: значение по ключу сумма (либо 0) + 1
for i in range(len(nums)):
sums += nums[i]
count += d.get(sums-k, 0)
d[sums] = d.get(sums, 0) + 1
return countValid Parenthesis String
# strings
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
An empty string is also valid.
”()” - True
“()” -True
“())” - True
“)(“ - False
def checkValidString(self, s: str) -> bool:
\\ cmin - это минимальное количество открытых скобок (должно быть 0 в конце), cmax - это максимальное количество открытых скобок (не должно быть меньше 0)
cmin = cmax = 0
// цикл по строке: если скобка ), увеличиваем оба счетчика, если ( - уменьшаем максимум, меняем минимум либо на минимум-1, либо 0 (что больше). Если *, увеличиваем максимум и меняем минимум
for i in s:
if i == '(':
cmax += 1
cmin += 1
if i == ')':
cmax -= 1
cmin = max(cmin - 1, 0)
if i == '*':
cmax += 1
cmin = max(cmin - 1, 0)
if cmax < 0:
return False
return cmin == 0Backspace String Compare # strings Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character. Note that after backspacing an empty text, the text will continue empty.
Input: S = “ab#c”, T = “ad#c”
Output: true
Explanation: Both S and T become “ac”.
def backspaceCompare(self, S: str, T: str) -> bool:
// функция для очистки от решеток-“пробелов”: пока есть решетки в строке, заменяем срезы строк [индекс до решетки:индекс после решетки] на пустую строку, если решетка не в начале строки. Если она в начале, заменяем строку на срез с 1-го индекса
def cleanBackspaces(text: str):
if ‘#’ in text:
while ‘#’ in text:
if text.index(‘#’) != 0:
text = text.replace(text[(text.index(‘#’) - 1):text.index(‘#’) + 1], ‘’)
else:
text = text[1:]
return text
// выполняем очистку на обеих строках и сравниваем их
S = cleanBackspaces(S)
T = cleanBackspaces(T)
return S == T
Middle of the Linked List # linked lists Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.
Input: [1,2,3,4,5]
Output: Node 3 from this list
Input: [1,2,3,4,5,6]
Output: Node 4 from this list.Since the list has two middle nodes with values 3 and 4, we return the second one.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.next = None
// используем 2 указателя, на след. ноду и через одну ноду. Сдвигаем их циклом, пока возможно
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
tmp = head
while tmp and tmp.next:
head = head.next
tmp = tmp.next.next
return headLongest Common Subsequence # strings Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0.
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
// строим пустую матрицу размерности длина первой строки + 1 х длина второй строки + 1
matrix = [[None]*(n+1) for i in range(m+1)]
// проходимся по элементам матрицы: если один из индексов 0, записываем 0, если буквы строк по текущим индексам-1 совпадают, записываем значение соседа сверху слева + 1, иначе записываем бОльшее значение из соседей (слева или сверху). В конце возвращаем значение последнего элемента матрицы
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
matrix[i][j] = 0
elif text1[i-1] == text2[j-1]:
matrix[i][j] = matrix[i-1][j-1] + 1
else:
matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1])
return matrix[m][n]
Maximal Square # arrays # matrices Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
def maximalSquare(self, matrix: List[List[str]]) -> int:
m = len(matrix)
n = len(matrix[0]) if m else 0
maxn = 0
// строим нулевую матрицу размерности m+1 x n+1
f = [[0] * (n+1) for _ in range(m+1)]
// проходимся по элементам матрицы (начиная f[1][1]): если элемент из исходной матрицы с индексами -1 равен единице, то в матрицу записываем минимальное значение из соседей (сверху, слева, слева-сверху) + 1. В результат записываем бОльшее из значений: текущее или текущего элемента. Возвращаем квадрат результата
for i in range(1,m+1):
for j in range(1,n+1):
if matrix[i-1][j-1] == '1':
f[i][j] = 1 + min(f[i-1][j], f[i][j-1], f[i-1][j-1])
maxn = max(maxn, f[i][j])
return maxn**2Binary Tree Maximum Path Sum # trees # graphs Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Input: [1,2,3]
1 / \ 2 3
Output: 6
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
// исходное значение максимума ставим на -бесконечность
self.max = float('-inf')
// вспомогательная функция для нахождения суммы узлов: рекурсивно вызываем функцию для левой и правой веток корня, сравниваем полученные значения с 0 и сохраняем бОльшее, в максимум записываем либо текущее, либо значение левой ноды + значение правой ноды + значение корня. Возвращаем максимум из левой ноды/правой ноды/ 0 + значение корневой ноды. В конце передаем в функцию корневую ноду и возвращаем итоговый максимум
def get_sum(root):
if root is None:
return 0
else:
ls = max(get_sum(root.left), 0)
rs = max(get_sum(root.right), 0)
self.max = max(self.max, ls + rs + root.val)
return max(ls, rs, 0) + root.val
get_sum(root)
return self.max
Construct Binary Search Tree from Preorder Traversal # trees # graphs # arrays Return the root node of a binary search tree that matches the given preorder traversal. (Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.) It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
# Definition for a binary tree node. # class TreeNode: # def \_\_init\_\_(self, x): # self.val = x # self.left = None # self.right = None
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
// делаем корневую ноду из нулевого элемента массива
root = TreeNode(preorder[0])
// в стек добавляем корневую ноду
stack = [root]
i = 1
// циклом проходимся по оставшимся элементам массива
while i < len(preorder):
temp = None
// извлекаем из стека последний элемент, пока значение из массива больше топа стека
while len(stack) > 0 and preorder[i] > stack[-1].val:
temp = stack.pop()
// делаем это значение правой нодой и добавляем в стек
if temp:
temp.right = TreeNode(preorder[i])
stack.append(temp.right)
// если значение меньше, делаем его левой нодой и добавляем в стек
else:
temp = stack[-1]
temp.left = TreeNode(preorder[i])
stack.append(temp.left)
i += 1
return root
First Bad Version
# arrays # recursion
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true
Then 4 is the first bad version.
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
// определяем нижнюю и верхнюю границу прохода
lo = 1
hi = n
// цикл, пока нижняя граница не больше верхней: определяем середину, если это значение подходит, сдвигаем верхнюю границу (середина -1), иначе сдвигаем нижнюю границу (середина + 1). В конце возвращаем значение нижней границы
while lo <= hi:
mid = (lo + hi) // 2
if isBadVersion(mid):
hi = mid - 1
else:
lo = mid + 1
return lo
Last Stone Weight
# arrays
We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that’s the value of last stone.
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
// цикл, пока камней в массиве больше 1: сортируем камни по весу, прибавляем разницу последних двух камней. В конце возвращаем первый камень
while len(stones) > 1:
stones.sort()
stones.append(stones.pop() - stones.pop())
return stones[0]
Counting Elements
# arrays
Given an integer array arr, count element x such that x + 1 is also in arr. If there’re duplicates in arr, count them seperately.
Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.
class Solution:
def countElements(self, arr: List[int]) -> int:
out = 0
// циклом проходимся по массиву и увеличиваем счетчик
for i in arr:
if i + 1 in arr:
out += 1
return out
def countElements(self, arr: List[int]) -> int:
// делаем сет из массива, проходимся циклом по массиву и проверяем, есть ли бОльшее число в сете, и увеличиваем счетчик
numbers_present = set(arr)
count = 0
for num in arr:
if num+1 in numbers_present:
count += 1
return count
Perform String Shifts
# strings # arrays
You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:
direction can be 0 (for left shift) or 1 (for right shift).
amount is the amount by which string s is to be shifted.
A left shift by 1 means remove the first character of s and append it to the end.
Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.
Return the final string after all operations.
Input: s = “abc”, shift = [[0,1],[1,2]]
Output: “cab”
Explanation:
[0,1] means shift to left by 1. “abc” -> “bca”
[1,2] means shift to right by 2. “bca” -> “cab”
def stringShift(self, s: str, shift: List[List[int]]) -> str:
// сначала определяем итоговый поворот строки: если направление равно 1, прибавляем к повороту количество символов, иначе отнимаем от него это количество
rotate = 0
for direction, n in shift:
if direction == 1:
rotate += n
else:
rotate -= n
// если модуль поворота больше самой строки, берем за поворот остаток от деления на длину строки
if abs(rotate) > len(s):
rotate %= len(s)
// если поворот больше 0, меняем местами части строки: в начало идет кусок с индекса (длина строки - поворот), затем оставшаяся часть
if rotate > 0:
return s[len(s)-rotate:] + s[:len(s)-rotate]
// если меньше 0, в начало идет кусок строки начиная с индекса -поворот, затем оставшаяся часть
else:
return s[-rotate:] + s[:-rotate]
Leftmost Column with at Least a One
# arrays # matrices
A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1. You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface: BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
BinaryMatrix.dimensions() returns a list of 2 elements [rows, cols], which means the matrix is rows * cols.
Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.
# """ # This is BinaryMatrix's API interface. # You should not implement it, or speculate about its implementation # """ #class BinaryMatrix(object): # def get(self, x: int, y: int) -> int: # def dimensions(self) -> list[]:
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: ‘BinaryMatrix’) -> int:
// определяем количество строк и столбцов
rows, cols = binaryMatrix.dimensions()
// ставим указатель на -1
ptr = -1
i = 0
j = cols - 1
// проходимся циклом по матрице (пока i меньше строк, а j не меньше 0: если элемент матрицы на данных координатах равен 1, то приравниваем указатель индексу столбца (j), j сдвигаем на -1, иначе сдвигаем индекс строки на 1. В конце возвращаем указатель
while i < rows and j >= 0:
if binaryMatrix.get(i,j) == 1:
ptr = j
j -= 1
else:
i += 1
return ptr
First Unique Number # arrays You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the FirstUnique class: FirstUnique(int[] nums) Initializes the object with the numbers in the queue. int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer. void add(int value) insert value to the queue.
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1
// класс для ноды списка
class DoublyLinkedListNode:
def \_\_init\_\_(self, data):
self.data = data
self.prev = None
self.next = None
// класс двусвязного списка: в конструкторе корневая нода с пустым значением
class DoublyLinkedList:
def \_\_init\_\_(self):
self.dummy_head = DoublyLinkedListNode(None)
self.dummy_head.next = self.dummy_head
self.dummy_head.prev = self.dummy_head
// метод для проверки, пустой ли список (если корневая нода указывает на саму себя)
def is_empty(self):
return self.dummy_head.next == self.dummy_head
// метод для первой ноды (возвращает следующую ноду после корневой)
def first_node(self):
return self.dummy_head.next
// метод для удаления ноды: меняем след.указатель предыдущей ноды на след.ноду, пред. указатель след.ноды на предыдущую ноду, обнуляем след. и пред. указатели данной ноды и возвращаем ее
def pop(self, node):
node.prev.next = node.next
node.next.prev = node.prev
node.next = None
node.prev = None
return node
// добавление ноды: пред. указатель ноды ставим на пред.указатель корня, след. указатель ставим на корень, след. указатель ноды перед корнем ставим на ноду, пред. указатель корня ставим на ноду
def push_last(self, node):
node.prev = self.dummy_head.prev
node.next = self.dummy_head
self.dummy_head.prev.next = node
self.dummy_head.prev = node
class FirstUnique:
// в конструкторе заводим словарь, двусвязный список, добавляем с словарь значения из массива
def __init__(self, nums: List[int]):
self.num_to_node = dict()
self.unique_nodes = DoublyLinkedList()
for num in nums:
self.add(num)
// если список пустой, возвращаем -1, иначе значение первой ноды
def showFirstUnique(self) -> int:
if self.unique_nodes.is_empty():
return -1
return self.unique_nodes.first_node().data
// добавление в словарь: если значения нет в словаре, делаем ноду с этим значением, добавляем в словарь запись значение:нода, добавляем ноду в двусвязный список. Иначе сохраняем в переменную значение по ключу в словаре, если у ноды есть след.указатель, удаляем ее
def add(self, value: int) -> None:
if value not in self.num_to_node:
node = DoublyLinkedListNode(value)
self.num_to_node[value] = node
self.unique_nodes.push_last(node)
else:
node = self.num_to_node[value]
# if node is still in the list, pop the node
if node.next:
self.unique_nodes.pop(node)
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
# trees # graphs # arrays
Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation:
The path 0 -> 1 -> 0 -> 1 is a valid sequence
Other valid sequences are:
0 -> 1 -> 1 -> 0
0 -> 0 -> 0
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
// если дерево пустое, проверяем, пустой ли массив (если тоже пустой, то возвращаем истину)
if not root:
return len(arr) == 0
// вызываем вспомогательную функцию с аргументами корень дерева, массива, индекс 0
return self.isValid(root, arr, 0)
// вспомогательная функция с использованием индекса массива
def isValid(self, root: TreeNode, arr: List[int], index: int) -> bool:
// если значение корня не равно значению массива по данному индексу, возвращаем ложь
if root.val != arr[index]:
return False
// если индекс - последний в массиве, проверяем, нет ли у корня правой и левой ветвей
if index == len(arr) - 1:
return not root.left and not root.right
// выполняем проверку: есть ли левая ветвь и рекурсивно вызываем вспомогательную функцию на левой ветви (сдвигаем индекс на 1) или есть ли правая ветвь и рекурсивный вызов функции на правой ветви (сдвигаем индекс на 1)
return (root.left and self.isValid(root.left, arr, index + 1)) or (root.right and self.isValid(root.right, arr, index + 1))
Jewels and Stones # strings # dicts You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels. The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Input: J = “aA”, S = “aAAbbbb”
Output: 3
def numJewelsInStones(self, J: str, S: str) -> int:
stones_dict = {}
count = 0
// составляем словарь символ:количество в строке S
for s in S:
if s in stones_dict:
stones_dict[s] += 1
else:
stones_dict[s] = 1
// проходимся по строке J, если символ есть в словаре, добавляем по ключу его значение
for j in J:
if j in stones_dict:
count += stones_dict[j]
return count
Ransom Note # strings Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note.
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
// проходимся по сету символов в записке: если частотность символа в записке больше, чем частотность символа в журнале, сразу возвращаем ложь
for i in set(ransomNote):
if ransomNote.count(i) > magazine.count(i):
return False
return True
Number Complement # numbers # bitwise Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
def findComplement(self, num: int) -> int:
i = 1
// циклом побитово сдвигаем счетчик i (умножаем на степень двойки)
while i <= num:
i = i << 1
// в конце вычитаем единицу (чтобы выровнять количество битов) и выполняем исключающее или с числом
return (i - 1) ^ numFirst Unique Character in a String # strings # dicts Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = “leetcode”
return 0.
s = “loveleetcode”,
return 2.
def firstUniqChar(self, s: str) -> int:
// делаем словарь с частотностями букв
freq = {}
for letter in s:
if letter not in freq:
freq[letter] = 1
else:
freq[letter] += 1
// проходимся циклом по индексам строки
for i in range(len(s)):
if freq[s[i]] == 1:
return i
return -1Majority Element
# numbers
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.
Input: [3,2,3]
Output: 3
Input: [2,2,1,1,1,2,2]
Output: 2
// проходимся по сету чисел, сравниваем их частотность с major
def majorityElement(self, nums: List[int]) -> int:
major = len(nums) / 2
for n in set(nums):
if nums.count(n) > major:
return n
// проходимся циклом по массиву, манипулируем счетчиком: если он равен 0, текущее число - это кандидат, к счетчику прибавляем 1, если текущее число является кандидатом, если нет - отнимаем 1. В конце возвращаем число-кандидат
def majorityElement(self, nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
// делаем словарь частотности, определяем максимальное значение и возвращаем его ключ
def majorityElement(self, nums):
num_dict = {}
for n in nums:
if n not in num_dict:
num_dict[n] = 1
else:
num_dict[n] += 1
major = max(num_dict.values())
for k, v in num_dict.items():
if v == major:
return k
// сортируем массив и возвращаем элемент посередине
def majorityElement(self, nums):
nums.sort()
return nums[len(nums)//2]
Cousins in Binary Tree
# trees # graphs
In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
lookup = {}
// вспомогательная функция прохода по дереву: добавляем в словарь пары значение: (глубина, значение родителя), проходимся по левой и правой веткам дерева
def searchTree(root, depth=0, parentVal=None):
if root == None:
return
lookup[root.val] = (depth, parentVal)
searchTree(root.left, depth+1, root.val)
searchTree(root.right, depth+1, root.val)
searchTree(root)
// проверяем по словарю, что глубины нод совпадают, а значения родительских нод нет
return lookup[x][0] == lookup[y][0] and lookup[x][1] != lookup[y][1]
Check If It Is a Straight Line # arrays # numbers You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
// сохраняем координаты первых двух точек в отдельных переменных
(x0, y0), (x1, y1) = coordinates[: 2]
// проверяем, что отношение наклона у всех точек одинаковое
return all((x1 - x0) * (y - y1) == (x - x1) * (y1 - y0) for x, y in coordinates)Valid Perfect Square # numbers Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt.
Input: 16
Output: true
Example 2:
Input: 14
Output: false
// метод Ньютона
def isPerfectSquare(self, num: int) -> bool:
r = num
while r*r > num:
r = (r + num/r) // 2
return r*r == numFind the Town Judge
# numbers # arrays
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
Example 1:
Input: N = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: N = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Example 4:
Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
def findJudge(self, N: int, trust: List[List[int]]) -> int:
// составляем массив из нулей длиной N+1
trusted = [0] * (N+1)
// заполняем массив: для элемента с индексом первого числа отнимаем единицу, для элемента с индексом второго числа прибавляем единицу
for a, b in trust:
trusted[a] -= 1
trusted[b] += 1
// таким образом, у числа-"судьи" будет значение N-1: ищем это число циклом
for i in range(1, N+1):
if trusted[i] == N-1:
return i
return -1Flood Fill
# matrices # graphs # array
An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).
Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.
To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.
At the end, return the modified image.
Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
row= len(image)
col = len(image[0])
color = image[sr][sc]
if color == newColor: return image
// используем обход в глубину: если пиксель того же цвета, что стартовый пиксель, меняем цвет. Таким же образом проходимся по соседним пикселям (сверху, снизу, справа и слева)
def dfs(r, c):
if image[r][c] == color:
image[r][c] = newColor
if r >= 1: dfs(r-1, c)
if r+1 < row: dfs(r+1, c)
if c >= 1: dfs(r, c-1)
if c+1 < col: dfs(r, c+1)
dfs(sr, sc)
return image
Single Element in a Sorted Array # arrays You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
def singleNonDuplicate(self, nums: List[int]) -> int:
// заводим переменные для левой и правой границ массива
l, r = 0, len(nums)-1
// цикл пока левая граница меньше правой
while l < r:
// находим индекс середины
m = l + (r - l)//2
// если индекс четный
if m % 2 == 0:
// если число справа от середины такое же, то сдвигаем левую границу (середина + 2), иначе сдвигаем правую границу на середину
if nums[m] == nums[m+1]:
l = m + 2
else:
r = m
// если число слева от середины такое же, то сдвигаем левую границу (середина + 1), иначе сдвигаем правую границу (середина - 1)
else:
if nums[m] == nums[m-1]:
l = m + 1
else:
r = m - 1
// в конце возвращаем число с индексом левой границы
return nums[l]Remove K Digits # strings Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero.
Example 1:
Input: num = “1432219”, k = 3
Output: “1219”
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = “10200”, k = 1
Output: “200”
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = “10”, k = 2
Output: “0”
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
def removeKdigits(self, num: str, k: int) -> str:
stack = []
// заполняем стек, проходимся циклом по цифрам
for i in range(len(num)):
while True:
// если к нулевое или стек пустой, выходим
if k == 0 or not stack:
break
// если последний элемент стека больше текущей цифры, убавляем к и выкидываем последний элемент стека, иначе просто выходим
if stack[-1] > num[i]:
k -= 1
stack.pop()
else:
break
// добавляем в стек текущую цифру
stack.append(num[i])
// проходимся циклом по стеку, убираем последние значения, убавляя к (если в пред.цикле к не убавилось)
while k != 0:
stack.pop()
k -= 1
// проверка того, что в начале нет нулей, убираем нули в стеке
for i in range(len(stack)):
if stack[i] != "0":
break
stack = stack[i:]
// если стек пустой, возвращаем 0, иначе строку с цифрами
if not stack:
return "0"
return "".join(stack)
Implement Trie (Prefix Tree) # trees Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
class Trie:
// в конструкторе объявляем два сета для хранения слов и префиксов
def \_\_init\_\_(self):
self.words = set()
self.prefixes = set()
// добавляем слово в сет слов, проходимся циклом по слову, добавляем сочетания в сет префиксов
def insert(self, word: str) -> None:
self.words.add(word)
for i in range(len(word)):
self.prefixes.add(word[:i+1])
// проверяем, есть ли слово в сете слов
def search(self, word: str) -> bool:
return word in self.words
// проверяем, есть ли префикс в сете префиксов
def startsWith(self, prefix: str) -> bool:
return prefix in self.prefixes
Maximum Sum Circular Subarray # arrays # subarrays Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10
Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4
Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3
Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1
def maxSubarraySumCircular(self, A):
// заводим переменные для общего количества, максимальной-минимальной суммы, текущего максимума-минимума
total, maxSum, curMax, minSum, curMin = 0, -float('inf'), 0, float('inf'), 0
// проходимся циклом по массиву: в текущий максимум записываем бОльшее из текущий максимум + число/число, в максимальную сумму бОльшее из макс.сумма/текущий максимум, в текущий минимум меньшее из текущий мин.+число/число, в мин.сумму меньшее из мин.сумма/текущий мин., в общее число прибавляем текущее число
for a in A:
curMax = max(curMax + a, a)
maxSum = max(maxSum, curMax)
curMin = min(curMin + a, a)
minSum = min(minSum, curMin)
total += a
// в конце возвращаем бОльшее из макс.сумма/общее число-мин.сумма (если макс.сумма больше 0), либо макс.сумму
return max(maxSum, total - minSum) if maxSum > 0 else maxSumOdd Even Linked List # linked list Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head:
return head
// используем нечетный указатель на голову и четный указатель на ноду после головы, заводим начало списка четных нод
odd = head
even = head.next
eHead = even
// проходимся по списку, пока есть четная нода и след. после нее: меняем указатели четн. и нечет. нод на следующие, после этого меняем сами четные и нечетные ноды
while even and even.next:
odd.next = odd.next.next
even.next = even.next.next
odd = odd.next
even = even.next
// в конце ставим указатель последней нечетной ноды на начало писка с четными нодами, возвращаем голову
odd.next = eHead
return headFind All Anagrams in a String
# strings # anagrams
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.The order of output does not matter.
Example 1: Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
// метод скользящего окна
def findAnagrams(self, s: str, p: str) -> List[int]:
// словарь для частотности букв в анаграмме
chars = {}
for i in p:
if i in chars:
chars[i] += 1
else:
chars[i] = 1 // переменные для левой и правой границы, список итоговых индексов, счетчик для оставшихся букв в анаграмме
start = 0
end = 0
ans = []
counter = len(chars) // цикл, пока правый индекс меньше длины строки
while end < len(s): // если буква правого индекса есть в словаре, уменьшаем ее частотность, если частотность нулевая, уменьшаем счетчик
if s[end] in chars:
chars[s[end]] -= 1
if chars[s[end]] == 0:
counter -= 1 // сдвигаем правый индекс
end += 1 // пока счетчик равен нулю: если разность правого и левого индекса равна длине анаграммы, добавляем в ответ левый индекс
while counter == 0:
if end - start == len(p):
ans.append(start) // если буква левого индекса есть в словаре, увеличиваем ее частотность, если частотность больше 0, увеличиваем счетчик
if s[start] in chars:
chars[s[start]] += 1
if chars[s[start]] > 0:
counter += 1 // сдвигаем левый индекс
start += 1 // в конце возвращаем массив индексов
return ans
Permutation in String # strings # permutations Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
Input: s1 = “ab” s2 = “eidbaooo”
Output: True
Explanation: s2 contains one permutation of s1 (“ba”).
Input:s1= “ab” s2 = “eidboaoo”
Output: False
def checkInclusion(self, s1: str, s2: str) -> bool:
// заводим два массива для букв в строках (каждый индекс соответствует букве)
list1 = [0] * 26
list2 = [0] * 26
// заполняем первый массив для строки-анаграммы
for char in s1:
list1[ord(char)-ord(‘a’)] += 1
// проходимся по индексам второй строки: заполняем второй массив, если индекс больше длины анаграммы, то отнимаем единицу в букве по индексу (индекс - длина анаграммы)
for i in range(len(s2)):
list2[ord(s2[i]) - ord(‘a’)] += 1
if i >= len(s1):
list2[ord(s2[i-len(s1)]) - ord(‘a’)] -= 1
// в конце сравниваем два массива (если анаграмма есть в строке, то массивы одинаковые)
if list1 == list2:
return True
return False
Online Stock Span
# stock # stack # oop
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.
The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.
For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].
class StockSpanner:
// в конструкторе заводим стек
def \_\_init\_\_(self):
self.stack = []
def next(self, price):
count = 1 // цикл по стеку, пока он непустой и цена больше последней в стеке: к счетчику прибавляем второе значение из последней пары стека, при этом ее удаляя
while self.stack and price >= self.stack[-1][0]:
count += self.stack.pop()[1] // в стек заводим пару значений: цена и текущее значение счетчика, в конце возвращаем счетчик
self.stack.append((price, count))
return count
Kth Smallest Element in a BST
# graphs # trees # bst
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
// заводим стек
stack = []
// цикл, пока дерево не пройдено или стек не пустой
while root or stack:
// цикл, пока дерево не пройдено: добавляем в стек ноду, переходим на левую ветку
while root:
stack.append(root)
root = root.left
// берем последнюю ноду из стека, уменьшаем k, если оно равно 0, возвращаем значение ноды
root = stack.pop()
k -= 1
if k == 0:
return root.val
// переходим на правую ветку
root = root.rightCount Square Submatrices with All Ones # matrices # arrays # numbers Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.
def countSquares(self, matrix: List[List[int]]) -> int:
// проходимся циклом по матрице, начиная с элемента (1,1): каждую ячейку умножаем на минимум из соседних значений (сверху, слева, наискосок слева) +1
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
matrix[i][j] *= min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
// в конце возвращаем сумму всех элементов матрицы (функцией map считаем суммы строк, потом всю сумму)
return sum(map(sum, matrix))Sort Characters By Frequency # strings Given a string, sort it in decreasing order based on the frequency of characters.
Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
def frequencySort(self, s: str) -> str:
// составляем массив из пар буква-частотность, сортируем по частотности по убыванию, формируем строку
freq = []
for letter in set(s):
freq.append((letter, s.count(letter)))
freq.sort(key=lambda i: i[1], reverse=True)
res = “”
for pair in freq:
res += pair[0] * pair[1]
return res
Interval List Intersections
# arrays # numbers
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists.
(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
ans = []
// заводим два указателя
i = j = 0
// циклом проходимся по массивам, пока указатели меньше длин массивов
while i < len(A) and j < len(B):
// определяем левую и правую границу пересечения: левая - максимум из первых координат, правая - минимум из вторых координат, если левая граница не больше правой, записываем координаты пересечения
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
ans.append([lo, hi])
// если вторая координата в первом массиве меньше второй координаты во втором массиве, сдвигаем первый указатель, иначе второй
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
// в конце возвращаем массив с пересечениями
return ans
Uncrossed Lines
# arrays # numbers # dp
We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:
A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
// строим матрицу размерности (длина А + 1) * (длина В + 1)
dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
// циклом заполняем матрицу: для каждого элемента по диагонали снизу выбираем больший из соседей сверху и слева и по диагонали наверх с учетом равенства чисел из массивов по текущим индексам
for i in range(len(A)):
for j in range(len(B)):
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + (A[i] == B[j]))
// в конце возвращаем самый последний элемент матрицы
return dp[-1][-1]Possible Bipartition # arrays # graphs Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group. Return true if and only if it is possible to split everyone into two groups in this way.
Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]
Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
// нужно построить граф из отношений: если граф цикличный и количество вершин в нем нечетное, то разбить людей на группы нельзя, в остальных случаях можно
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
// делаем массив для пар отношений, массив с -1 для отметки посещенных вершин, переменную-счетчик
bag = [[] for i in range(N+1)]
visited = [-1] * (N+1)
count = 0
// заполняем bag: ставим второе число пары по индексу первого числа и наоборот
for dislike in dislikes:
bag[dislike[0]].append(dislike[1])
bag[dislike[1]].append(dislike[0])
// проходимся циклом от 1 до N+1: если элемент по текущему индексу в массиве посещенных вершин равен -1, а длина элемента по текущему индексу в массиве bag больше 0, и
for i in range(1, N+1):
if visited[i] == -1 and len(bag[i]) > 0:
if not self.visit(0, i, bag, visited):
return False
return True
// вспомогательная функция для отметки посещенных вершин (принимает параметры текущего уровня глубины графа, текущего индекса, массивы bag и visited): если элемент по текущему индексу в массиве посещенных неотрицательный, проверяем, четная ли разность глубины графа и текущего посещенного элемента
def visit(self, curLevel, i, bag, visited):
if visited[i] >= 0:
return (curLevel - visited[i]) % 2 == 0
// в текущий посещенный элемент записываем значение текущую глубину графа
visited[i] = curLevel
// циклом проходимся по числам в bag по текущему индексу: если не посещено по функции с параметрами глубина+1, число из bag и массивы, возвращаем false
for des in bag[i]:
if not self.visit(curLevel + 1, des, bag, visited):
return False
return True
Counting Bits # numbers # arrays # bits Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
def countBits(self, num: int) -> List[int]:
res = [0]
// заполняем результирующий массив циклом, пока длина массива не больше числа: к массиву прибавляем последовательность чисел на 1 больше из кусочка массива с начала до индекса (число + 1 - текущая длина массива)
while len(res) <= num:
res += [i + 1 for i in res[:num + 1 - len(res)]]
return res
Course Schedule
# arrays # graphs
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
// нужно проверить, является ли граф, построенный из пар курсов, цикличным
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
// создаем массивы для графа и списка посещенных вершин
graph = [[] for _ in range(numCourses)]
visited = [0 for _ in range(numCourses)]
# заполняем массив графа
for pair in prerequisites:
graph[pair[0]].append(pair[1])
# посещаем каждую вершину: проходимся циклом по индексам до числа курсов: если вершина по текущему индексу не посещена, возвращаем ложь
for i in range(numCourses):
if not self.dfs(graph, visited, i):
return False
return True
// вспомогательная функция для обхода графа
def dfs(self, graph, visited, i):
# если i-я вершина отмечена как текущая в посещении, значит, граф цикличный, возвращаем ложь
if visited[i] == -1:
return False
# если вершина уже посещена, больше ее не отмечаем
if visited[i] == 1:
return True
# отмечаем вершину как текущую
visited[i] = -1
# посещаем рекурсивно все соседние вершины
for j in graph[i]:
if not self.dfs(graph, visited, j):
return False
# когда все соседи посещены, отмечаем вершину как посещенную, в конце возвращаем истину
visited[i] = 1
return True
K Closest Points to Origin # arrays # numbers # coordinates We have a list of points on the plane. Find the K closest points to the origin (0, 0). (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
// сортируем координаты по сумме их квадратов, возвращаем срез массива до нужного числа
points.sort(key=lambda i: i[0]**2 + i[1]**2)
return points[:K]Edit Distance
# strings
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
// задача о расстоянии Левенштейна
def minDistance(self, word1: str, word2: str) -> int:
// сохраняем длины слов (если первое слово длиннее второго, меняем местами)
n, m = len(word1), len(word2)
if n > m:
word1, word2 = word2, word1
n, m = m, n
// устанавливаем текущий ряд - диапазон до длины первого слова + 2
current_row = range(n + 1)
// циклом проходимся от 1 до длины второго слова + 1: определяем предыдущий ряд и текущий ряд (т.е. работаем только с этими рядами, а не со всей матрицей): текущий меняем на предыдущий, а новый делаем из значения текущего индекса и нулей (длина первого слова)
for i in range(1, m + 1):
previous_row, current_row = current_row, [i] + [0] * n
// внутренний цикл от 1 до длины первого слова + 1: определяем стоимости операций с буквами: добавить - к значению по индексу j прибавляем 1, удалить - к значению по индексу j-1 прибавляем 1, заменить - значение по индексу i-1
for j in range(1, n + 1):
add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
// если буква первого слова по индексу j-1 не равна букве второго слова по индексу i-1, к операции замены прибавляем 1
if word1[j - 1] != word2[i - 1]:
change += 1
// в значение текущего ряда по индексу j записываем минимум из операций
current_row[j] = min(add, delete, change)
// возвращаем значение из текущего ряда по индексу длина первого слова (т.е. последнее)
return current_row[n]Invert Binary Tree
# trees # graphs
Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
// используем рекурсию: если дерево пустое (корень пустой), возвращаем None, для левой ветки дерева выполняем инверсию с правой веткой, а для правой ветки инверсию с левой. В конце возвращаем корень
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return rootDelete Node in a Linked List # linked lists Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
The linked list will have at least two elements.
All of the nodes’ values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.
# Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
// просто записываем в значение ноды значение следующей ноды, и передвигаем указатель через след.ноду
class Solution:
def deleteNode(self, node):
if node.next:
node.val, node.next = node.next.val, node.next.next
Two City Scheduling
# numbers # arrays
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
// сортируем массив по разнице стоимости поездки в города (тогда в левой части массива окажутся люди, кому дешевле ехать в А, а в правой - кому дешевле ехать в В)
costs.sort(key=lambda cost: cost[0] - cost[1])
// высчитываем суммарную стоимость поездок в город А (первое число из пары, первая половина списка)
costs_for_A = sum([cost[0] for cost in costs[:len(costs) // 2]])
// высчитываем суммарную стоимость поездок в город В (второе число из пары, вторая половина списка)
costs_for_B = sum([cost[1] for cost in costs[len(costs) // 2:]])
// в конце возвращаем полную сумму
return costs_for_A + costs_for_BReverse String # strings Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters.
Example 1:
Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
def reverseString(self, s: List[str]) -> None:
// используем два указателя, i = длина строки -1, j = 0
i=len(s)-1
j=0
// проходимся циклом, пока i не меньше j: меняем местами символы по индексам указателей, i уменьшаем на единицу, а j увеличиваем на единицу
while i>=j:
s[j],s[i]=s[i],s[j]
i=i-1
j=j+1Random Pick with Weight # arrays # numbers # random Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
class Solution:
// в конструкторе сохраняем массив с весами, сохраняем длину массива, проходимся циклом по индексам, к каждому весу прибавляем вес предыдущего, сохраняем отдельно последний вес массива
def \_\_init\_\_(self, w: List[int]):
self.w = w
self.n = len(w)
for i in range(1,self.n):
w[i] += w[i-1]
self.s = self.w[-1]
def pickIndex(self) -> int:
// выбираем случайное число от 1 до последнего веса, определяем левую и правую границу (0 и длина-1)
seed = random.randint(1,self.s)
l,r = 0, self.n-1
// используем алгоритм бинарного поиска: пока левая граница меньше правой, определяем середину, если случайное число не больше веса по индексу середины, правую границу переносим на середину, иначе левую границу переносим на середину + 1. В конце возвращаем левую границу
while l
Queue Reconstruction by Height # arrays # numbers Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
// сортируем массив по убыванию роста (первое число пары)
people = sorted(people, key = lambda x: (-x[0], x[1]))
res = []
// в итоговый массив вставляем пары, где индекс равен второму числу (кол-во высоких человек перед текущим)
for p in people:
res.insert(p[1], p)
return res
Coin Change 2 # arrays # numbers # dp # knapsack You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
def change(self, amount: int, coins: List[int]) -> int:
// делаем массив из нулей длиной количество + 1, первым элементом ставим единицу
dp = [0] * (amount + 1)
dp[0] = 1
// проходимся циклом по номиналам, внутренний цикл по индексам от 1 до количество + 1: если индекс больше-равно номинала, то к элементу массива по текущему индексу прибавляем элемент по индексу (индекс - номинал). В конце возвращаем последний элемент массива
for i in coins:
for j in range(1, amount + 1):
if j >= i:
dp[j] += dp[j - i]
return dp[amount]
Power of Two # numbers # math # binary Given an integer, write a function to determine if it is a power of two.
Example 1:
Input: 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: 218
Output: false
// у числа-степени двойки только первый бит равен единицы, у числа меньше на 1 все биты единицы, кроме первого. Сравниваем числа побитовым И
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & (n-1) == 0)Метод скользящего окна
Шаблон скользящего окна используется для выполнения операции с определённым размером окна данного массива или связанного списка, например для поиска самого длинного подмассива, содержащего все 1. Скользящие окна начинаются с 1-го элемента, продолжают смещаться вправо на один элемент и регулируют длину окна в соответствии с задачей, которую вы решаете. В некоторых случаях размер окна остаётся постоянным, а в других — увеличивается или уменьшается.
Как определить, когда использовать шаблон скользящего окна:
входные данные задачи — это линейная структура данных, например связанный список, массив или строка;
нужно найти самую длинную/короткую подстроку, подмассив или желаемое значение.
Задачи, для которых подойдёт шаблон скользящего окна:
максимальная сумма подмассива размера «K» (лёгкий);
самая длинная подстрока с различными «K» символами (средний);
анаграммы строки (сложный).
Метод с двумя указателями
Это шаблон, в котором два указателя перебирают структуру данных в тандеме, пока один или оба указателя не достигнут определённого условия. Два указателя часто полезны при поиске пар в отсортированном массиве или связанном списке. Например, когда нужно сравнить каждый элемент массива с другими его элементами.
С одним указателем пришлось бы постоянно возвращаться назад через массив, чтобы найти ответ. Так же, как и с одним итератором, это неэффективно для временной и пространственной сложности — концепции, называемой асимптотическим анализом. Хотя решение в лоб с одним указателем будет работать, его сложность — около O (n²). Во многих случаях два указателя помогут найти решение с лучшей временной и пространственной сложностью.
Как определить, что подойдёт шаблон двух указателей:
вы имеете дело с отсортированными массивами (или связанными списками), и вам необходимо найти набор элементов, которые удовлетворяют определённым ограничениям;
набор элементов в массиве представляет собой пару, триплет или даже подмассив.
Задачи, для которых подойдёт шаблон двух указателей:
возведение в квадрат отсортированного массива (лёгкий);
триплеты, суммирующие до нуля (средний);
сравнение строк, содержащих пробелы (средний).
Метод с быстрыми и медленными указателями
Подход быстрого и медленного указателя, также известный как алгоритм зайца и черепахи, использует два указателя, которые перемещаются по массиву (или последовательности / связному списку) с разными скоростями. Этот подход полезен при работе с циклически связанными списками или массивами.
Двигаясь с разными скоростями (скажем, в циклически связанном списке), алгоритм доказывает, что эти два указателя обязательно встретятся. Быстрый указатель должен перехватывать медленный, когда оба указателя находятся в цикле.
Как определить, когда использовать шаблон быстрого и медленного указателя:
задача касается цикла в связанном списке или массиве;
нужно узнать положение определённого элемента или общую длину связанного списка.
Когда использовать его вместо двух указателей?
В некоторых случаях не следует использовать шаблон Двух указателей, например в одном списке, где вы не можете двигаться в обратном направлении. Использовать этот шаблон нужно, когда вы пытаетесь определить, является ли связанный список палиндромом.
Задачи, для которых подойдёт шаблон быстрого и медленного указателей:
цикл связанного списка (лёгкий);
является ли связанный список палиндромом (средний);
цикл в круговом массиве (сложный).
Метод слияния интервалов
Эффективный метод работы с пересекающимися интервалами. В большинстве задач, связанных с интервалами, нужно либо найти пересекающиеся интервалы, либо совместить интервалы, если они пересекаются. возможные случаи: интервалы не пересекаются, полностью пересекаются, пересекаются на границах (порядок важен)
Как определить, что подойдёт шаблон слияния интервалов?
нужно составить список только с взаимоисключающими интервалами;
вы слышите термин «пересекающиеся интервалы».
Задачи, для которых подойдёт шаблон слияния интервалов:
пересечение интервалов (средний);
максимальная нагрузка на процессор (сложный).
Метод циклической сортировки
Интересный подход для решения задач, которые связаны с массивами, содержащими числа в заданном диапазоне. Шаблон циклической сортировки выполняет итерацию по массиву по одному числу за раз, и если текущее число, которое вы перебираете, не соответствует правильному индексу, вы меняете его местами с числом по правильному индексу. Можете попытаться поместить число, с которым мы поменяли текущее число, в правильный индекс, но это приведет к сложности O (n²), поэтому больше подойдёт метод циклической сортировки.
Как определить, когда использовать шаблон циклической сортировки:
в задачах с использованием отсортированного массива с числами в заданном диапазоне;
если нужно найти отсутствующее/дублированное/наименьшее число в отсортированном/повёрнутом массиве.
Задачи, для которых подойдёт шаблон циклической сортировки:
найти недостающий номер (лёгкий);
найти наименьшее недостающее положительное число (средний).
Метод разворота связанного списка
Вас могут попросить инвертировать связи между набором узлов связанного списка. Часто это нужно сделать на месте, то есть используя существующие объекты узла и не используя дополнительную память.
Шаблон меняет местами только один узел, начиная с одной переменной (current), указывающей на головной элемент связанного списка, а другая переменная (previous) будет указывать на предыдущий узел, который вы обработали. Шаг за шагом вы развернёте узел, наведя его на предыдущий, прежде чем перейти к следующему узлу. Кроме того, вы обновите переменную previous, чтобы всегда указывать на предыдущий узел, который вы обработали.
Как определить, когда использовать шаблон разворот связанного списка:
если вас попросили развернуть связанный список без использования дополнительной памяти.
Задачи, для которых подойдёт шаблон разворот связанного списка:
перевернуть подсписок (средний);
перевернуть каждый K-элемент подсписка (средний).
Метод дерева BFS
Этот шаблон основан на методе поиска в ширину (BFS) для обхода дерева и использует очередь для отслеживания всех узлов уровня перед переходом на следующий уровень. Любая задача, связанная с обходом дерева в поэтапном порядке, может быть эффективно решена с помощью этого подхода.
Дерево BFS работает, помещая корневой узел в очередь, а затем непрерывно повторяясь, пока очередь не станет пустой. Для каждой итерации мы удаляем узел в начале очереди и «посещаем» этот узел. После удаления каждого узла из очереди мы также вставляем все его дочерние элементы в очередь.
Как определить, когда использовать шаблон дерево BFS:
вас просят обойти дерево поэтапно (или поуровнево).
Задачи, для которых подойдёт шаблон дерево BFS:
поуровневый обход двоичного дерева (лёгкий);
зигзагообразный обход (средний).
Метод дерева DFS
Дерево DFS основано на методе поиска в глубину (DFS) для обхода дерева.
Можете использовать рекурсию (или стек для итеративного подхода), чтобы отслеживать все предыдущие (родительские) узлы при обходе.
Дерево DFS работает начиная с корня дерева. Если узел не является листом, нужно сделать две вещи:
Решить, обрабатывать ли текущий узел сейчас (прямой обход), между обработкой двух дочерних элементов (центрированный обход) или после обработки обоих дочерних элементов (обратный обход).
Сделать два рекурсивных вызова для обоих потомков текущего узла, чтобы обработать их.
Как определить, когда использовать шаблон дерево DFS:
вас просят совершить прямой, центрированный или обратный обход дерева;
требуется найти что-то, где узел ближе к листу.
Задачи, для которых подойдёт шаблон дерево BFS:
сумма номеров путей (средний);
все пути для суммы (средний).
Метод двух куч
Во многих задачах дан набор элементов, которые можно разделить на две части. Чтобы решить задачу, нужно знать наименьший элемент в одной части и наибольший в другой.
Этот шаблон использует две кучи: Min Heap, чтобы найти самый маленький элемент, и Max Heap, чтобы найти самый большой. Шаблон работает, сохраняя первую половину чисел в Max Heap, потому что вы ищите наибольшее число в первой половине. Затем вы сохраняете вторую половину чисел в Min Heap, так как хотите найти наименьшее число во второй половине. В любой момент медиана текущего списка чисел может быть вычислена из верхнего элемента двух куч.
Как определить, когда использовать шаблон две кучи:
приоритетные очереди, планирование;
нужно найти самые маленькие / самые большие / медианные элементы набора;
иногда полезен в задачах с бинарной структурой данных.
Задачи, для которых подойдёт шаблон две кучи:
найти медиану потока чисел (средний).
Метод подмножеств
Огромное количество задач на собеседовании связано с перестановками и комбинациями заданного набора элементов. Шаблон подмножества описывает эффективный метод поиска в ширину (BFS) для их решения.
Шаблон выглядит так:
Дан набор из [1, 5, 3].
Начните с пустого набора: [[]].
Добавьте первое число (1) ко всем существующим подмножествам, чтобы создать новые подмножества: [[], [1]].
Добавьте второе число (5) ко всем существующим подмножествам: [[], [1], [5], [1,5]].
Добавьте третье число (3) ко всем существующим подмножествам: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1, 5,3]].
Как определить, когда использовать шаблон подмножества:
нужно найти комбинации или перестановки заданного набора.
Задачи, для которых подойдёт шаблон подмножества:
подмножества с дубликатами (лёгкий);
перестановки строк при изменении регистра (средний).
Метод с модифицированным бинарным поиском
Когда вам дают отсортированный массив, связанный список или матрицу и просят найти определённый элемент, лучшим алгоритмом будет бинарный поиск. Этот шаблон описывает эффективный способ решения всех задач, связанных с бинарным поиском.
Для набора по возрастанию шаблоны выглядят так:
Сначала найдите середину начала и конца. Простой способ найти середину был бы: middle = (start + end) / 2. Но от этого может быть целочисленное переполнение, поэтому рекомендуется представлять середину как: middle = start + (end – start) / 2.
Если ключ равен числу в середине индекса, верните середину.
Если «ключ» не равен середине индекса:
Если ключ < arr [middle], уменьшите поиск до end = middle — 1.
Если ключ > arr [middle], уменьшите поиск до to end = middle + 1.
Задачи, для которых подойдёт шаблон модифицированный бинарный поиск:
Бинарный поиск, не зависящий от порядка (лёгкий);
Поиск в отсортированном бесконечном массиве (средний).
Метод Топ К-элементов
Любая задача, в которой требуется найти самые большие / самые маленькие / частые K-элементы среди данного набора, подпадает под этот шаблон.
Лучшая структура данных для отслеживания K-элементов — куча. Этот шаблон будет использовать кучу для решения задач, связанных с K-элементами одновременно из набора заданных элементов. Шаблон выглядит так:
Вставьте K-элементы в Min-heap или Max-heap в зависимости от задачи.
Выполните итерации по оставшимся числам и, если найдёте число, которое больше, чем у вас в куче, удалите это число и вставьте большее.
Нет необходимости в алгоритме сортировки, потому что куча будет отслеживать элементы для вас.
Как определить, когда использовать шаблон Топ К-элементов:
если нужно найти самые большие / самые маленькие / частые K-элементы в данном наборе;
если нужно отсортировать массив, чтобы найти верный элемент.
Задачи, для которых подойдёт шаблон Топ К-элементов:
топ K-номеров (лёгкий);
топ K-частых номеров (средний).
K-Way слияние
K-way слияние поможет решить задачи, связанные с набором отсортированных массивов.
Когда вам дают отсортированные K-массивы, вы можете использовать кучу для эффективного выполнения отсортированного обхода всех элементов всех массивов. Можете поместить наименьший элемент каждого массива в Min Heap, чтобы получить общий минимум. После этого поместите следующий элемент из того же массива в кучу. Затем повторите, чтобы сделать отсортированный обход всех элементов.
Шаблон выглядит так:
Вставьте первый элемент каждого массива в Min Heap.
Извлеките самый маленький (большой) элемент из кучи и добавьте в объединённый список.
После удаления наименьшего элемента из кучи вставьте следующий элемент из того же списка в кучу.
Повторите шаги 2 и 3, чтобы заполнить объединённый список в отсортированном порядке.
Как определить, когда использовать шаблон K-Way слияние:
задача состоит из отсортированных массивов, списков или матрицы;
требуется объединить отсортированные списки или найти самый маленький элемент в отсортированном списке.
Задачи, для которых подойдёт шаблон K-Way слияние:
слияние K-сортированных списков (средний);
K-пары с самыми большими суммами (сложный).
Топологическая сортировка
Топологическая сортировка используется для нахождения линейного порядка элементов, которые зависят друг от друга. Например, если событие «Б» зависит от события «A», то «A» предшествует «Б» в топологическом порядке.
Этот шаблон — простой способ понять методику выполнения топологической сортировки набора элементов.
Шаблон работает так:
Инициализация.
Храните график в списках смежности, используя HashMap.
Для нахождения всех источников используйте HashMap, чтобы сохранить количество степеней.
Постройте график и найдите степени всех вершин.
Постройте график из входных данных и заполните хэш-карту степенями.
Найдите все источники.
Все вершины с «0» степенями будут источниками и будут храниться в очереди.
Сортировка.
Для каждого источника сделайте следующее:
добавьте его в отсортированный список,
получите все дочерние элементы из графа,
уменьшите степень каждого дочернего элемента на 1,
если степень дочернего элемента становится «0», добавьте её в очередь источников.
Повторяйте, пока исходная очередь не станет пустой.
Как определить, когда следует использовать шаблон Топологической сортировки?
задача связана с графами, которые не имеют направленных циклов;
нужно обновить все объекты в отсортированном порядке;
есть класс объектов, которые следуют определённому порядку.
Задачи, для которых подойдёт шаблон Топологической сортировки:
планирование задач (средний);
минимальная высота дерева (сложный).
Is Subsequence
# strings
Given a string s and a string t, check if s is subsequence of t.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
def isSubsequence(self, s: str, t: str) -> bool:
// если первая строка (которая должна быть подпоследовательностью) пустая, сразу возвращаем истину
if len(s) == 0:
// если вторая строка пустая, возвращаем ложь
return True
if len(t) == 0:
return False
// заводим два указателя
i, j = 0, 0
// проходим циклом, пока указатели меньше длин строк
while i < len(s) and j < len(t):
// если символы строк по текущим индексам совпадают, сдвигаем первый указатель
if s[i] == t[j]:
i += 1
// все время сдвигаем второй указатель
j += 1
// в конце проверяем, равен ли первый указатель длине первой строке (все символы первой строки входят во вторую)
return i == len(s)Search Insert Position # arrays # numbers Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
// используем бинарный поиск
def searchInsert(self, nums: List[int], target: int) -> int:
// определяем левую и правую границы
l , r = 0, len(nums)-1
// циклом проходимся, пока левая граница не больше правой
while l <= r:
// определяем середину, если элемент по индексу середины равен искомому числу, возвращаем индекс (т.е. середину), если элемент по индексу середины меньше искомого числа, сдвигаем левую границу (середина + 1), иначе сдвигаем правую границу (середина - 1)
mid=(l+r)//2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid+1
else:
r = mid-1
// в конце возвращаем индекс левой границы
return lSort Colors
# arrays # numbers
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
// так называемая задача о голландском флаге
def sortColors(self, nums: List[int]) -> None:
// заводим три указателя по цветам, красный и белые нулевые, синий равен длине массива -1
red, white, blue = 0, 0, len(nums) - 1
// проходимся циклом, пока белый указатель не больше синего
while white <= blue:
// если число по индексу белого указателя равно 0, меняем местами числа по белому и красному указателям, увеличиваем красный и белый указатели на 1
if nums[white] == 0:
nums[red], nums[white] = nums[white], nums[red]
red += 1
white += 1
// если число по белому указателю равно 2, меняем местами числа по белому и синему указателям, синий указатель уменьшаем на 1
elif nums[white] == 2:
nums[white], nums[blue] = nums[blue], nums[white]
blue -= 1
// в противном случае увеличиваем белый указатель
else:
white += 1
Insert Delete GetRandom O(1) # numbers # structures # oop Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
class RandomizedSet(object):
// объявляем массив и словарь для хранения значений и их индексов
def \_\_init\_\_(self):
self.nums, self.pos = [], {}
// если значения нет в словаре, добавляем значение в массив, в словарь добавляем запись значение: длина массива -1
def insert(self, val):
if val not in self.pos:
self.nums.append(val)
self.pos[val] = len(self.nums) - 1
return True
return False
// если значение есть в словаре, заводим переменные для индекса (значение в словаре по ключу значения) и последнего элемента в массиве, потом меняем их, удаляем последний элемент массива, удаляем элемент по индексу значения
def remove(self, val):
if val in self.pos:
idx, last = self.pos[val], self.nums[-1]
self.nums[idx], self.pos[last] = last, idx
self.nums.pop(); self.pos.pop(val, 0)
return True
return False
// возвращаем элемент массива по случайному индексу от 0 до длины массива -1
def getRandom(self):
return self.nums[random.randint(0, len(self.nums) - 1)]
алгоритм Евклида (поиск НОД) # numbers #math
def gcd(a, b):
if a == 0:
return b
elif b == 0:
return a
elif a >= b:
return gcd(a%b, b)
else:
return gcd(a, b%a)Largest Divisible Subset #numbers #arrays #math Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine.
Example 1:
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if len(nums) == 0:
return []
// составляем дополнительный массив массивов из чисел
output_list = [[i] for i in nums]
// сортируем массив
nums.sort()
// проходимся по индексам до длины массива
for i in range(len(nums)):
// второй индекс от 0 до первого индекса + 1
for j in range(0,i+1):
// если число по первому индексу нацело делится на число по второму индексу и они не равны
if nums[i]%nums[j] == 0 and nums[i]!=nums[j]:
// длина списка доп.массива по второму индексу плюс число из массива по первому индексу не меньше длины списка по первому индексу
if len(output_list[j] + [nums[i]]) >= len(output_list[i]):
// в список по первому индексу добавляем список по второму индексу и число из массива по первому индексу
output_list[i] = output_list[j] + [nums[i]]
// сортируем дополнительный массив по убыванию
output_list.sort(key=lambda x: -len(x))
// в конце возвращаем первый список массива
return output_list[0]Cheapest Flights Within K Stops
# graphs
There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.
Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
Example 1: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
// составляем массив из бесконечно больших значений длиной количество городов
dist = [math.inf]*n
//делаем элемент массива с индексом отправного города 0
dist[src] = 0
//проходимся циклом до значения количества пересадок +1
for _ in range(K+1):
// делаем копию массива
olddist = dist[:]
// проходимся циклом в массиве перелетов
for f in flights:
//присваиваем элементу массива по индексу второго значения из тройки (отправление-назначение-цена) меньшее из элемента массива по индексу второго значения из тройки / элемента из копии массива по индексу (первое значение из тройки плюс третье значение из тройки)
dist[f[1]] = min(dist[f[1]], olddist[f[0]] + f[2])
// в конце возвращаем элемент по индексу города назначения, если он меньше бесконечности, иначе -1
return dist[dst] if dist[dst] < math.inf else -1Search in a Binary Search Tree # trees #graphs #search Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
// обычный рекурсивный поиск: если значение больше корня, выполняем поиск по правой ветке, если меньше, то поиск по левой, пока не найдем нужную ноду (или None, если такой ноды нет)
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return None
if root.val == val:
return root
elif val > root.val:
return self.searchBST(root.right, val)
else:
return self.searchBST(root.left, val)Validate IP Address
# strings
Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.
IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots (“.”), e.g.,172.16.254.1;
Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.
IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (“:”). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).
However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.
Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.
Note: You may assume there is no extra space or special characters in the input string.
Example 1:
Input: “172.16.254.1”
Output: “IPv4”
Explanation: This is a valid IPv4 address, return “IPv4”.
Example 2:
Input: “2001:0db8:85a3:0:0:8A2E:0370:7334”
Output: “IPv6”
Explanation: This is a valid IPv6 address, return “IPv6”.
Example 3:
Input: “256.256.256.256”
Output: “Neither”
Explanation: This is neither a IPv4 address nor a IPv6 address.
def validIPAddress(self, IP: str) -> str:
// если в строке есть точка, проверяем на соответствие IPv4: разделяем адрес по точке, должно быть 4 блока, не должно быть пустых блоков или начинающихся с 0, не должно быть букв или чисел больше 255
if "." in IP:
splitted = IP.split(".")
if len(splitted) != 4: return "Neither"
for part in splitted:
if len(part) == 0 or (len(part)>1 and part[0] == "0"): return "Neither"
if not part.isnumeric() or int(part) > 255: return "Neither"
return "IPv4"
// если в строке есть двоеточие, проверяем на соответствие IPv6: разделяем адрес по двоеточию, блоков должно быть 8, они не должны быть пустыми или быть длиннее 4, в блоках должны быть только цифры от 0 до 9 и буквы от a до f
elif ":" in IP:
symbols = "0123456789abcdefABCDEF"
splitted = IP.split(":")
if len(splitted) != 8: return "Neither"
for part in splitted:
if len(part) == 0 or len(part) > 4: return "Neither"
for elem in part:
if elem not in symbols: return "Neither"
return "IPv6"
// если ничего не подошло, возвращаем "Neither"
return "Neither"Принципы жадных алгоритмов
Надежный шаг - существует оптимальное решение, согласованное с локальным жадным шагом
Оптимальность подзадач - задача, остающаяся после жадного шага, имеет тот же тип
Покрыть отрезки точками
# greedy #numbers
По данным nn отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.
// сортируем массив отрезков по правой границе, делаем массив точек, в него добавляем первую правую точку. Циклом проходимся по отрезкам: если левая граница отрезка больше последней точки из массива, добавляем правую границу в массив точек
def minPoints(arr):
arr.sort(key=lambda x: x[1])
points = [arr[0][1]]
for i in arr:
if i[0] > points[-1]:
points.append(i[1])
return pointsНепрерывный рюкзак
# greedy #knapsack
Выведите максимальную стоимость частей предметов (от каждого предмета можно отделить любую часть, стоимость и объём при этом пропорционально уменьшатся), помещающихся в данный рюкзак
def list_continuous_knapsack(capacity, item_list):
// сортируем список предметов по стоимости за единицу веса по убыванию
item_list.sort(key=lambda x: x[0] / x[1], reverse=True)
full_cost = 0
// проходимся циклом по списку: если общий вес предмета легче вместимости рюкзака, к общей стоимости прибавляем общую стоимость предмета и убавляем вместимость, иначе к общей стоимости прибавляем отношение цены к весу умноженное на вместимость
for cost, weight in item_list:
if weight < capacity:
full_cost += cost
capacity -= weight
else:
full_cost += cost / weight * capacity
break
return float("{:.3f}".format(full_cost))
Различные слагаемые
# greedy #numbers
По данному числу n найдите максимальное число k, для которого nn можно представить как сумму k различных натуральных слагаемых
def different_addends_iterative(n):
k = 1
addends = []
// проходимся циклом, пока число не меньше 2k+1: добавляем k в массив, из n вычитаем k, k увеличиваем на 1
while n >= 2 * k + 1:
addends.append(k)
n -= k
k += 1
// в конце добавляем в массив n
addends.append(n)
return k, addendsSurrounded Regions
# matrices
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example: X X X X X O O X X X O X X O X X
After running your function, the board should be: X X X X X X X X X X X X X O X X
def solve(self, board: List[List[str]]) -> None:
if not board or not board[0]:
return
// заводим переменные для рядов и колонок
R, C = len(board), len(board[0])
if R <= 2 or C <= 2:
return
// обходим границы матрицы, заменяем все О на N
for r in range(R):
self.dfs(board, r, 0, R, C)
self.dfs(board, r, C-1, R, C)
for c in range(C):
self. dfs(board, 0, c, R, C)
self. dfs(board, R-1, c, R, C)
// обходим матрицу, заменяем O на X, N на O
for r in range(R):
for c in range(C):
if board[r][c] == "O":
board[r][c] = "X"
if board[r][c] == "N":
board[r][c] = "O"
// функция обхода в глубину
def dfs(self, board, r, c, R, C):
// если ряд большен-равен 0 и меньше числа рядов и колонка больше-равна 0 и меньше числа колонок и ячейка по данным индексам содержит О, заменяем на N и обходим соседей
if 0<=r
H-Index II # arrays # numbers Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
Example:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.
// используем обычный бинарный поиск
def hIndex(self, citations):
n = len(citations)
l, r = 0, n-1
// цикл, пока левая граница не больше правой: устанавливаем середину, если число по индексу середины больше-равно разности общего числа и середины, сдвигаем правую границу (середина -1), иначе сдвигаем левую (середина + 1)
while l <= r:
mid = (l+r)//2
if citations[mid] >= n-mid:
r = mid - 1
else:
l = mid + 1
// в конце возвращаем разность общего числа и левой границы
return n-lLongest Duplicate Substring
# strings
Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)
Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is “”.)
Example 1:
Input: “banana”
Output: “ana”
// используем функцию хеширования и бинарный поиск
def longestDupSubstring(self, S: str) -> str:
A = [ord(c) - ord('a') for c in S]
mod = 2**63 - 1
def test(L):
p = pow(26, L, mod)
cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
seen = {cur}
for i in range(L, len(S)):
cur = (cur * 26 + A[i] - A[i - L] * p) % mod
if cur in seen: return i - L + 1
seen.add(cur)
res, lo, hi = 0, 0, len(S)
while lo < hi:
mi = (lo + hi + 1) // 2
pos = test(mi)
if pos:
lo = mi
res = pos
else:
hi = mi - 1
return S[res:res + lo]
Кодирование Хаффмана
# greedy # strings
По данной непустой строке s длины не более 10^4, состоящей из строчных букв латинского
алфавита, постройте оптимальный беспрефиксный код. В первой строке выведите количество
различных букв k, встречающихся в строке, и размер получившейся закодированной строки.
Sample Input:
abacabad
Sample Output: 4 14 a: 0 b: 10 c: 110 d: 111 01001100100111
from collections import Counter
import heapq
def huffman_encoding_v1(s):
encoding_dict = {}
heap = [(freq, char) for char, freq in Counter(s).items()]
heapq.heapify(heap)
if len(heap) == 1: # если в строке только один символ
_freq, char = heapq.heappop(heap)
encoding_dict[char] = str(0) # the only type of characters is encoded by zero
while len(heap) >= 2: # если в строке как минимум два символа
min_freq, min_char = heapq.heappop(heap)
min2_freq, min2_char = heapq.heappop(heap)
heapq.heappush(heap, (min_freq + min2_freq, min_char + min2_char))
for i, char_string in enumerate([min_char, min2_char]): # 0 для min_char, 1 для min2_char
for char in char_string: # каждый последующий символ кодируется с 0/1
if char in encoding_dict:
encoding_dict[char] = str(i) + encoding_dict[char]
else:
encoding_dict[char] = str(i)
return encoding_dict
def main():
s = input()
encoding_dict = huffman_encoding_v1(s)
encoded_str = ''.join([encoding_dict[char] for char in s])
print(len(encoding_dict), len(encoded_str))
for key, value in sorted(encoding_dict.items()):
print('{}: {}'.format(key, value))
print(encoded_str)
if __name__ == ‘__main__’:
main()
декодирование Хаффмана
# greedy # strings
Восстановите строку по её коду и беспрефиксному коду символов.
В первой строке входного файла заданы два целых числа kk и ll через пробел — количество различных букв, встречающихся в строке, и размер получившейся закодированной строки, соответственно. В следующих kk строках записаны коды букв в формате “letter: code”. Ни один код не является префиксом другого. Буквы могут быть перечислены в любом порядке. В качестве букв могут встречаться лишь строчные буквы латинского алфавита; каждая из этих букв встречается в строке хотя бы один раз. Наконец, в последней строке записана закодированная строка. Исходная строка и коды всех букв непусты. Заданный код таков, что закодированная строка имеет минимальный возможный размер.
Sample Input : 4 14 a: 0 b: 10 c: 110 d: 111 01001100100111
Sample Output :
abacabad
def huffman_decoding(encoding_dict, encoded_str):
decoded_str = ''
encoding_dict = {value: key for key, value in encoding_dict.items()}
sequence = ''
for char in encoded_str:
sequence += char
if sequence in encoding_dict:
decoded_str += encoding_dict[sequence]
sequence = ''
return decoded_str
def main():
k, _l = (int(i) for i in input().split())
encoding_dict = {}
for _ in range(k):
key, value = (i.strip() for i in input().split(':'))
encoding_dict[key] = value
encoded_str = input()
print(huffman_decoding(encoding_dict, encoded_str))
if __name__ == ‘__main__’:
main()
