1.
Two sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {}
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return prevMap[diff], i
prevMap[n] = i
return
2. Best time to buy and sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1
maxp = 0
while r < len(prices):
if prices[l] < prices[r]:
profit = prices[r]-prices[l]
maxp = max(maxp,profit)
else:
l = r
r = r+1
return maxp
3. Squares of a Sorted Array
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res = []
l, r = 0, len(nums) - 1
while l<=r:
if nums[l] * nums[l] > nums[r] * nums[r]:
res.append(nums[l]* nums[l])
l = l+1
else:
res.append(nums[r] * nums[r])
r = r-1
return res[::-1]
4. Fibonacci Number
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return self.fib(n-1)+self.fib(n-2)
5. Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
s1 = ""
for c in s:
if self.AlphaNum(c) == True:
s1 += c.lower()
return s1 == s1[::-1]
def AlphaNum(self, c):
return (ord("A") <= ord(c) <= ord("Z") or ord("a") <= ord(c) <= ord("z") or ord("0")<=
ord(c) <= ord("9"))
6. Binary Search
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r = 0, len(nums) -1
while l<=r:
mid = l + ((r-l)//2)
if nums[mid]>target:
r = mid -1
elif nums[mid]<target:
l = mid + 1
else:
return mid
return -1
7. Exercise tracker
s = "Today I did 20 pushups,15 squats, and 30 jumping jacks"
st = ""
for c in s:
if(ord("0")<=ord(c)<=ord("9") or c == ","):
st += c
st1 = st.split(",")
total = 0
for i in st1:
if i:
total += int(i)
print(“%.2f” % total)
8. Find the Duplicate Number
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums) - 1):
if(nums[i]==nums[i+1]):
return nums[i]
9. Contains Duplicate
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
hashset = set()
for n in nums:
if n in hashset:
return True
hashset.add(n)
return False
10.Find Pivot Index
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = sum(nums)
leftSum = 0
for i in range(len(nums)):
rightSum = total - nums[i] - leftSum
if leftSum == rightSum:
return i
leftSum += nums[i]
return -1
11.Majority Elements
class Solution:
def majorityElement(self, nums: List[int]) -> int:
res, count = -1, 0
for i in nums:
if(count==0):
res = i
if(res == i):
count += 1
else:
count -=1
return res
12.Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
res, l = 0, 0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l+=1
charSet.add(s[r])
res = max(res,(r-l)+1)
return res
13.Lucky Number in a matrix
class Solution:
def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
ROWS, COLS = len(matrix), len(matrix[0])
res = []
row_min = set()
col_max = set()
for r in range(ROWS):
row_min.add(min(matrix[r]))
for c in range(COLS):
cur_max = matrix[0][c]
for r in range(ROWS):
cur_max = max(matrix[r][c],cur_max)
col_max.add(cur_max)
for n in row_min:
if n in col_max:
res.append(n)
return res
14.Decimal To Binary
n = 2013
s = ""
while n > 0:
r = n%2
s += str(r)
n = n//2
print(int(s[::-1]))
