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 r
Palindrome 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 // 10
Integer 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 res
Longest 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 << i
Happy 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 True
Product 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)