LeetCode
My solutions to different problems and what not.
Usually I pay less attention to the time/space complexity part and focus more on just solving the problem.
Problems
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.
You can return the answer in any order.
Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, ival in enumerate(nums):
for j, jval in enumerate(nums):
if ival + jval == target and i != j:
return [i, j]9. Palindrome Number
Given an integer x, return true if x is a palindrome, and false otherwise.
Solution
class Solution:
def isPalindrome(self, x: int) -> bool:
counter = 0
xstr = str(x)
for idx, c in enumerate(xstr):
if c == xstr[len(xstr) - 1 - idx]:
counter = counter + 1
return counter == len(xstr)13. Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Solution
class Solution:
def romanToInt(self, s: str) -> int:
d = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
"IV": 4,
"IX": 9,
"XL": 40,
"XC": 90,
"CD": 400,
"CM": 900
}
result = 0
idx = 0
nxt = ""
while idx < len(s):
c = s[idx]
if idx < len(s) - 1:
nxt = s[idx + 1]
if c + nxt in d.keys():
result = result + d[c + nxt]
idx = idx + 1
else:
result = result + d[c]
idx = idx + 1
return result14. 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 "".
Solution
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
first = strs[0]
res = ""
for i, c in enumerate(first):
if all(i < len(s) and s[i] == c for s in strs[1:]):
res = res + c
else:
return res
return res20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Solution
class Solution:
from collections import deque
def isValid(self, s: str) -> bool:
stack = deque()
for c in s:
if len(stack) > 0 and stack[-1] == "(" and c == ")":
stack.pop()
elif len(stack) > 0 and stack[-1] == "[" and c == "]":
stack.pop()
elif len(stack) > 0 and stack[-1] == "{" and c == "}":
stack.pop()
else:
stack.append(c)
return len(stack) == 028. Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Solution
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)118. Pascal's Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Solution with the use of math.comb()
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for n in range(numRows):
row = []
for k in range(n + 1):
row.append(comb(n, k))
res.append(row)
return resSolution without the use of math.comb()
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
i = 0
while i < numRows:
l = []
if i == 0:
l = [1]
elif i == 1:
l = [1,1]
else:
row = res[i - 1]
l = []
for idx, v in enumerate(row):
if idx < len(row) - 1:
l.append(row[idx] + row[idx + 1])
l = [1] + l + [1]
res.append(l)
i = i + 1
return res119. Pascal's Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Solution
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
return [math.comb(rowIndex, k) for k in range(rowIndex + 1)]136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Solution
class Solution:
def singleNumber(self, nums: List[int]) -> int:
u = set()
for elem in nums:
if elem in u:
u.discard(elem)
else:
u.add(elem)
return u.pop()1046. Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
If
x == y, both stones are destroyed, andIf
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Solution
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
while len(stones) > 1:
largest = stones.pop(stones.index(max(stones)))
snd_largest = stones.pop(stones.index(max(stones)))
if largest != snd_largest:
stones.append(largest - snd_largest)
if stones == []:
return 0
return stones[0]Last updated