Problems Flashcards
problems.leetcode_20_Valid Parentheses — Given a string s containing just the characters
‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
🎯 assert Solution().isValid(s=”()”) == True
🎯 assert Solution().isValid(s=”()[]{}”) == True
🎯 assert Solution().isValid(s=”(]”) == False
🎯 assert Solution().isValid(s=”([)]”) == False
🎯 assert Solution().isValid(s=”{[]}”) == True
🎯 assert Solution().isValid(s=”({{{{}}}))”) == False
🎯 assert Solution().isValid(s=”((“) == False
🎯 assert Solution().isValid(s=”){“) == False
🎯 assert Solution().isValid(s=”(}{)”) == False
🎯 assert Solution().isValid(s=”([}}])”) == False
🎯 assert Solution().isValid(s=”(([]){})”) == True
class Solution:
def isValid(self, s: str) -> bool:
answers = []
for i in s:
if i == '(' or i == '[' or i == '{':
answers.append(i)
elif len(answers):
pop_item = answers.pop()
if (pop_item == '(' and i != ')') or (pop_item == '[' and i != ']') or (pop_item == '{' and i != '}'):
return False
else:
return False
if len(answers):
return False
else:
return True
problems.leetcode_14_Longest Common Prefix — 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. “”
class Solution:
def longestCommonPrefix(self, strs) -> str:
commonPrefix = ''
for chars in zip(*strs):
print(chars)
# Если есть повторяющиеся, то-есть длина больше 1, тогда неправильно и включается елс
if len(set(chars)) == 1:
commonPrefix += chars[0]
else:
break
return commonPrefix
class Solution:
def longestCommonPrefix(self, strs) -> str:
if not isinstance(strs[0], str):
return ""
if len(strs) == 0:
return ""
if len(strs) == 1 or not strs[0].isalpha():
return strs[0]
biggest = max([len(i) for i in strs])
test = biggest
ind = -1
prefix = ""
while biggest > 0:
ind = ind + 1
biggest -= 1
leters = [i[ind] for i in strs if ind < len(i)]
if leters.count(leters[0]) == len(strs):
prefix += leters[0]
if len(prefix) == test:
return prefix
else:
if len(prefix) < 1:
return ""
return prefix
if \_\_name\_\_ == '\_\_main\_\_':
assert Solution().longestCommonPrefix(strs=["flower","flow","flight"]) == "fl"
assert Solution().longestCommonPrefix(strs=["dog","racecar","car"]) == ""
assert Solution().longestCommonPrefix(strs=[""]) == ""
assert Solution().longestCommonPrefix(strs=["a"]) == "a"
assert Solution().longestCommonPrefix(strs=[["",""]]) == ""
assert Solution().longestCommonPrefix(strs=["flower","flower","flower","flower"]) == "flower"
assert Solution().longestCommonPrefix(strs=["c","c"]) == "c"
problems.leetcode_141_Linked List Cycle — Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
🎯 Input: head = [3,2,0,-4], pos = 1 | Output: true
🎯 Input: head = [1,2], pos = 0 | Output: true
🎯 Input: head = [1], pos = -1 | Output: false
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
problems.leetcode_1_Two Sum — Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
class Solution:
def twoSum(self, nums, target: int):
values = {}
for idx, value in enumerate(nums):
if target - value in values:
return [values[target - value], idx]
else:
values[value] = idx
if \_\_name\_\_ == '\_\_main\_\_':
assert Solution().twoSum(nums=[2, 7, 11, 15], target=9) == [0, 1]
assert Solution().twoSum(nums=[3, 2, 4], target=6) == [1, 2]
assert Solution().twoSum(nums=[3, 3], target=6) == [0, 1]
problems.leetcode_234_Palindrome Linked List — Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
🎯 Input: head = [1,2,2,1] 👉 Output: true
🎯 Input: head = [1,2] 👉 Output: false
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
count = []
while head:
count.append(head.val)
head=head.next
return True if count == count[::-1] else False
problems.leetcode_70_Climbing Stairs — You are climbing a staircase. It takes n steps to
reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you
climb to the top?
🎯 Input: n = 2 👉 Output: 2 (1. 1 step + 1 | step 2. 2 steps)
🎯 Input: n = 2 👉 Output: 2 (1. 1 step + 1 step | 2. 2 steps)
from functools import lru_cache
class Solution:
def climbStairs(self, n: int) -> int:
@lru_cache(maxsize=32)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
return fib(n+1)
problems.leetcode_102_Binary Tree Level Order Traversal — Given the root of a binary tree,
check whether it is a mirror of itself (i.e., symmetric around its center).
🎯 Input: root = [1,2,2,3,4,4,3] 👉 Output: true
🎯 Input: root = [1,2,2,null,3,null,3] 👉 Output: false
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root == None:
return True
else:
return self.sym(root, root)
def sym(self, left, right):
if left is None and right is None:
return True
elif left is None or right == None:
return False
else:
return left.val == right.val and self.sym(left.left, right.right) and self.sym(left.right, right.left)
problems.leetcode_161_One Edit Distance — Given the heads of two singly linked-lists headA
and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
🎯 Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
🎯 Output: Intersected at ‘8’
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
A, B = headA, headB
visit = set()
while A:
visit.add(A)
A = A.next
while B:
if B in visit:
return B
B = B.next
return None
problems.leetcode_121_Best Time to Buy and Sell Stock — You are given an array prices where
prices[i] is the price of a given stock on the ith day. You want to maximize your profit by
choosing a single day to buy one stock and choosing a different day in the future to sell that
stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve
any profit, return 0.
🎯 Input: prices = [7,1,5,3,6,4] 👉 Output: 5
🎯 Input: prices = [7,6,4,3,1] 👉 Output: 0
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
min_p = float("inf")
for i in prices:
min_p = min(min_p, i)
profit = max(profit, i - min_p)
return profit
problems.leetcode_543_Diameter of Binary Tree — Given the root of a binary tree, return the length of the diameter of the tree. The length of a path between two nodes is represented by the number of edges between them.
🎯 Input: root = [1,2,3,4,5] 👉 Output: 3 👉 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
🎯 Input: root = [1,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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
answer = [0]
def l_r_root(root):
if not root:
return - 1
left = l_r_root(root.left)
right = l_r_root(root.right)
answer[0] = max(answer[0], 2 + left + right)
return 1 + max(left, right)
l_r_root(root)
return answer[0]
problems.leetcode_21_Merge Two Sorted Lists — You are given the heads of two sorted linked
lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
🎯Input: list1 = [1,2,4], list2 = [1,3,4] 👉 Output: [1,1,2,3,4,4]
🎯Input: list1 = [], list2 = [] 👉 Output: []
🎯Input: list1 = [], list2 = [0] 👉 Output: [0]
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
new = dummy
while list1 and list2:
if list1.val < list2.val:
new.next = list1
list1 = list1.next
else:
new.next = list2
list2 = list2.next
new = new.next
if list1:
new.next = list1
elif list2:
new.next = list2
return dummy.next
Фабричный метод
Любой метод который создает обьект.
from enum import Enum
from math import *
class CoordinateSystem(Enum):
CARTESIAN = 1
POLAR = 2
class Point:
def \_\_init\_\_(self, x, y):
self.x = x
self.y = y
def \_\_str\_\_(self):
return f"{self.x}, {self.y}"
@staticmethod
def new_cartesian(x, y):
return Point(x, y)
@staticmethod
def new_polar_point(rho, theta):
return Point(rho * cos(theta), rho * sin(theta))
if \_\_name\_\_ == '\_\_main\_\_':
p = Point.new_polar_point(1, 2)
print(p)
👉 -0.4161468365471424, 0.9092974268256817
Строитель
это порождающий паттерн проектирования, который позволяет создавать сложные объекты пошагово. Строитель даёт возможность использовать один и тот же код строительства для получения разных представлений объектов.
Прототип
это порождающий паттерн проектирования, который позволяет копировать объекты, не вдаваясь в подробности их реализации. (можно использовать deepcopy)
Итератор
это поведенческий паттерн проектирования, который даёт возможность последовательно обходить элементы составных объектов, не раскрывая их внутреннего представления.
