import random
import numpy as npLeet Code (Easy)
This is just some examples from Leet Code problems (easy). In addition to the solution for each problem, I will write a test. And in addition to the time complexity, we will try to measure it. We also work on ways to optimize the code further if possible.
Two Sum
Link: https://leetcode.com/problems/two-sum/
Summary of Problem Description: Given a list of numbers, and a target value, return the indices that their sum is the target.
def func_v1(nums, target):
"""
For a given list of intergers, nums, find the two indices whose
values are added up to `target`.
Parameters
----------
nums: list
A list of integer numbers
target : int
An integer that is treated as the target value
Returns
-------
out : list
A list of length two that contains the indices whose sum
is equal to `target`
"""
n = len(nums)
for i in range(n - 1):
for j in range(n):
if nums[i] + nums[j] == target:
return [i, j]func_v1([0, 1, 2, 3], 4)[1, 3]Exercise: * What is the time complexity? * Can we make it faster? Say \(\mathcal{O}(NlogN)\)? How about \(\mathcal{O}{(N)}\)? What is space complexity in each case? * Can you write a test for it?
Palindrom
link: https://leetcode.com/problems/palindrome-number/description/
def is_palindrom(x):
"""
Parameters
----------
x : int
An integer number
Returns
-------
out : bool
True if x is palindrom, meaning its digits can be read the same
from left to right, and right to left.
"""
x_str = str(x)
return x_str == x_str[::-1] assert is_palindrom(121) == True
assert is_palindrom(123) == FalseRoman to Integer
link: https://leetcode.com/problems/roman-to-integer/description/
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
Note: * oman numerals are USUALLY written largest to smallest from left to right. * Example: VI is V + I, which is equivalent to 5 + 1 = 6 * However, IV is V - I since I (smaller number) comes before V (larger number).
def convert_roman_to_int(s):
"""
Parameters
----------
s : str
A string value representing a value in Roman format
Returns
-------
out : int
The integer value that is equivalent to the roman number `s`
"""
roman_values = {
'I' : 1,
'V' : 5,
'X' : 10,
'L' : 50,
'C' : 100,
'D' : 500,
'M' : 1000,
}
out = 0
i = 0
while i < len(s):
if i + 1 < len(s) and roman_values[s[i]] < roman_values[s[i + 1]]:
v = roman_values[s[i + 1]] - roman_values[s[i]]
i += 2
else:
v = roman_values[s[i]]
i += 1
out += v
return outs = 'I'
assert convert_roman_to_int(s) == 1
s = 'II'
assert convert_roman_to_int(s) == 2
s = 'IV'
assert convert_roman_to_int(s) == 4
s = 'VI'
assert convert_roman_to_int(s) == 6Longest Common Prefix
link: https://leetcode.com/problems/longest-common-prefix/description/
def find_longest_common_prefix(strs_lst):
"""
For a given list of strings, returns the longest common prefix.
Parameters
----------
strs_lst : list
A list of string values
Returns
-------
out : str
The longest common prefix of the strings provided in `strs_lst`
"""
out = strs_lst[0]
for i in range(1, len(strs_lst)):
item = strs_lst[i]
n = min(len(out), len(item))
if n == 0:
out = ""
break
for j in range(min(len(out), n)):
if out[j] == item[j]:
stop = j + 1
continue
stop = j
break
out = out[:stop]
return outstrs = ["flower","flow","flight"]
assert find_longest_common_prefix(strs) == 'fl'
assert find_longest_common_prefix(["ab", "a"]) == "a"
assert find_longest_common_prefix(["", ""]) == ""Valid Paranthesis
link: https://leetcode.com/problems/valid-parentheses/description/
def is_paranthesis_valid(s):
"""
For a given string `s` consisting of paranthesis characters, i.e.
`(`, `)`, `[`, `]`, `{`, and `}`, returns `True` if valid.
Parameters
----------
s : string
A string that consists of paranthesis
Returns
-------
out : bool
True if the string `s` represents a valid paranthesis.
"""
tracker = []
paranthesis_pairs = {
')': '(',
']': '[',
'}': '{',
}
flag = True
for c in s:
c_pair = paranthesis_pairs.get(c, None)
if c_pair is None:
tracker.append(c)
elif len(tracker) > 0 and tracker.pop() == c_pair:
continue
else:
flag = False
break
if flag == False or len(tracker) != 0:
out = False
else:
out = True
return outs = '{()}'
assert is_paranthesis_valid(s) == True
s = ''
assert is_paranthesis_valid(s) == True
s = '{}()'
assert is_paranthesis_valid(s) == True
s = '{()}[]'
assert is_paranthesis_valid(s) == True
s = ']'
assert is_paranthesis_valid(s) == False
s = '{'
assert is_paranthesis_valid(s) == False
s = '{]'
assert is_paranthesis_valid(s) == False
s = '[]('
assert is_paranthesis_valid(s) == FalseMerge two sorted list
class Node:
def __init__(self, v):
self.value = v
self.next = None
class LinkedList:
def __init__(self):
self.root = None
def append(self, v):
if self.root is None:
self.root = Node(v)
else:
new_node = Node(v)
new_node.next = self.root
self.root = new_nodeobj = LinkedList()
for i in range(1, 5):
obj.append(i)
# print LinkedList values
current_node = obj.root
while current_node is not None:
print(current_node.value)
current_node = current_node.next4
3
2
1