Leetcode(Python)
1. Two Sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
for i in range(len(nums)):
if target - nums[i] not in dict:
dict[nums[i]] = i
else:
return [dict[target-nums[i]], i]
2. Add Two Numbers
# 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
dummy = ListNode(0);
p = dummy
while l1 and l2:
p.next = ListNode((l1.val + l2.val + carry)% 10)
carry = (l1.val + l2.val + carry) // 10
l1 = l1.next
l2 = l2.next
p = p.next
if l2:
while l2:
p.next = ListNode((l2.val + carry) % 10)
carry = (l2.val + carry) // 10
l2 = l2.next
p = p.next
if l1:
while l1:
p.next = ListNode((l1.val + carry) % 10)
carry = (l1.val + carry) // 10
l1 = l1.next
p = p.next
if carry == 1:
p.next = ListNode(1)
return dummy.next
3. Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = -1
max = 0
d = {}
for i in range(len(s)):
if s[i] in d and d[s[i]] > start:
start = d[s[i]]
d[s[i]] = i
else:
d[s[i]] = i
if i - start > max:
max = i - start
return max
7. Reverse Integer
class Solution:
def reverse(self, x: int) -> int:
num = 0
a = abs(x)
while(a != 0):
temp = a % 10
num = num * 10 + temp
a = int(a/10)
if x > 0 and num < 2147483647:
return num
elif x < 0 and num <= 2147483647:
return -num
else:
return 0
8. String to Integer (atoi)
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
stripS = str.strip()
if stripS == "" or stripS == "-" or stripS == "+":
return 0
s1 = re.match('[^\d]+', (stripS.lstrip("-")).lstrip("+"))
if s1 != None:
return 0
else:
s1 = re.search('\-*\+*\d+', stripS).group()
if s1[0:2] == "--" or s1[0:2] == "-+" or s1[0:2] == "++":
return 0
result = int(s1)
if result > 0:
return 2147483647 if result > 2147483647 else result
else:
return -2147483648 if result < -2147483648 else result
9. Palindrome Number
class Solution:
def isPalindrome(self, x: int) -> bool:
num = 0
a = abs(x)
while(a != 0):
temp = a % 10
num = num * 10 + temp
a = int(a / 10)
## a = a // 10
if x >=0 and x == num:
return True
else:
return False
13. Roman to Integer
class Solution:
def romanToInt(self, s: str) -> int:
numeral_map = {'I': 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
result = 0
for i in range(len(s)):
if i > 0 and numeral_map[s[i]] > numeral_map[s[i-1]]:
result += numeral_map[s[i]] - 2 * numeral_map[s[i-1]]
else:
result += numeral_map[s[i]]
return result
14. Longest Common Prefix
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
for i in range(len(strs[0])):
for string in strs[1:]:
if i >= len(string) or string[i] != strs[0][i]:
return strs[0][:i]
return strs[0]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
result = ""
i = 0
while True:
try:
sets = set(string[i] for string in strs)
if len(sets) == 1:
result += sets.pop()
i += 1
else:
break
except Exception as e:
break
return result
16. 3Sum Closest
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums) == 3:
return sum(nums)
nums = sorted(nums)
if sum(nums[:3]) >= target:
return sum(nums[:3])
if sum(nums[-3:]) <= target:
return sum(nums[-3:])
c = nums[0] + nums[1] + nums[2]
for i in range(0, len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i+1
k = len(nums) - 1
while j<k:
res = nums[i] + nums[j] + nums[k]
if abs(res - target) < abs(c - target):
c = res
elif res == target:
return target
elif res < target:
j = j + 1
else:
k = k - 1
return c
17. Letter Combinations of a Phone Number
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
def backtrack (combination, next_digits):
if len(next_digits) == 0:
output.append(combination)
else:
for letter in phone[next_digits[0]]:
backtrack(combination + letter, next_digits[1:])
output = []
if digits:
backtrack("", digits)
return output
20. Valid Parenthese
class Solution:
def isValid(self, s: str) -> bool:
stack = []
lookup = {"(":")","{":"}","[":"]"}
for parenthese in s:
if parenthese in lookup:
stack.append(parenthese)
elif len(stack) == 0 or lookup[stack.pop()] != parenthese:
return False
return len(stack) == 0
21. Merge Two Sorted Lists
# 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:
curr = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
22. Generate Parentheses
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
result = []
self.helper(n, n, '', result)
return result
def helper(self, l, r, item, result):
if r < l:
return
if l == 0 and r == 0:
result.append(item)
if l > 0:
self.helper(l-1, r, item + '(', result)
if r > 0:
self.helper(l, r-1, item + ')', result)
23. Merge k Sorted Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def mergeTwoLists(l1, l2):
curr = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if len(lists) == 0:
return
head = lists[0]
for i in range(1, len(lists)):
head = mergeTwoLists(head, lists[i])
return head
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
arr = []
for linkedlist in lists:
while linkedlist:
arr.append(linkedlist.val)
linkedlist = linkedlist.next
arr.sort()
head = ret = ListNode()
for i in arr:
temp = ListNode(i)
head.next = temp
head = head.next
return ret.next
26. Remove Duplicates from Sorted Array
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
count = 0
for i in range(len(nums)):
if nums[count] != nums[i]:
count += 1
nums[count] = nums[i]
return count + 1
27. Remove Element
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
write = 0
for i in range(len(nums)):
if nums[i] != val:
nums[write] = nums[i]
write +=1
return write
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, last = 0, len(nums) - 1
while i <= last:
if nums[i] == val:
nums[i], nums[last] = nums[last], nums[i]
last -= 1
else:
i += 1
return last + 1
28. Implement strStr()
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
for i in range(len(haystack) - len(needle) + 1):
if haystack[i: i+len(needle)] == needle:
return i
return -1
35. Search Insert Position
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target > nums[len(nums) - 1]:
return len(nums)
for i in range(len(nums)):
if nums[i] >= target:
return i
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if target == nums[mid]:
return mid
elif target < nums[mid]:
right = mid
else:
left = mid + 1
return left
38. Count and Say
class Solution:
def countAndSay(self, n: int) -> str:
seq = "1"
for i in range(n-1):
seq = self.getNext(seq)
return seq
def getNext(self, seq):
i, next_seq = 0, ""
while i < len(seq):
count = 1
while i < len(seq) - 1 and seq[i] == seq[i+1]:
count += 1
i += 1
next_seq += str(count) + seq[i]
i += 1
return next_seq
46. Permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) <= 1:
return [nums]
answer = []
for i, num in enumerate(nums):
n = nums[:i] + nums[i+1:]
for y in self.permute(n):
answer.append([num] + y)
return answer
53. Maximum Subarray
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if max(nums) < 0:
return max(nums)
local_max, global_max = 0, 0
for num in nums:
local_max = max(0, local_max + num)
global_max = max(global_max, local_max)
return global_max
55. Jump Game
class Solution:
def canJump(self, nums: List[int]) -> bool:
far = 0
for i in range(len(nums)-1):
far = max(far, i+nums[i])
if far <= i:
return False
return far >= len(nums)-1
56. Merge Intervals
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x : x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
58. Length of Last Word
class Solution:
def lengthOfLastWord(self, s: str) -> int:
count = 0
local_count = 0
for i in range(len(s)):
if s[i] == ' ':
local_count = 0
else:
local_count += 1
count = local_count
return count
66. Plus One
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in reversed(range(len(digits))):
if digits[i] == 9:
digits[i] = 0
print(digits)
else:
digits[i] += 1
return digits
digits[0] = 1
digits.append(0)
return digits
67. Add Binary
class Solution:
def addBinary(self, a: str, b: str) -> str:
result, carry, val = "", 0, 0
for i in range(max(len(a), len(b))):
val = carry
if i < len(a):
val += int(a[-(i+1)])
if i < len(b):
val += int(b[-(i+1)])
carry, val = val // 2, val % 2
print(val)
result +=str(val)
if carry:
result += str(1)
return result[::-1]
69. Sqrt(x)
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
if mid > x / mid:
right = mid - 1
else:
left = mid + 1
return left -1
70. Climbing Stairs
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1 for i in range(n+1)]
for i in range(2, n+1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
83. Remove Duplicates from Sorted List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
current = head
while current:
runner = current.next
while runner and current.val == runner.val:
runner = runner.next
current.next = runner
current = runner
return head
88. Merge Sorted Array
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
while m > 0 and n > 0:
if nums1[m-1] < nums2[n-1]:
nums1[m-1+n] = nums2[n-1]
n = n - 1
else:
nums1[m-1+n], nums1[m-1] = nums1[m-1], nums1[m-1+n]
m = m - 1
if m == 0 and n > 0:
nums1[:n] = nums2[:n]
return nums1
89. Gray Code
class Solution:
def grayCode(self, n: int) -> List[int]:
def helper(n, result):
if (n == 0):
result.append(0)
return
helper(n-1, result)
k = 1 << (n - 1)
for i in range(len(result)-1, -1, -1):
result.append(result[i] + k)
result = []
helper(n, result)
return result
98. Validate Binary Search Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.valid(root, float('-inf'), float('inf'))
def valid (self,root, min, max):
if not root:
return True
if root.val >= max or root.val <= min:
return False
return self.valid(root.left, min, root.val) and self.valid(root.right, root.val, max)
100. Same Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
if p is not None and q is not None:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
101. Symmetric Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
return self.isSymmetricRecu(root.left, root.right)
def isSymmetricRecu(self, left, right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
return self.isSymmetricRecu(left.left, right.right) and self.isSymmetricRecu(left.right, right.left)
104. Maximum Depth of Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
else:
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
107. Binary Tree Level Order Traversal II
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
result, current = [], [root]
while current:
next_level, vals = [], []
for node in current:
vals.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
current = next_level
result.append(vals)
return result[::-1]
108. Convert Sorted Array to Binary Search Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def to_bst(nums, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(nums[mid])
node.left = to_bst(nums, start, mid-1)
node.right = to_bst(nums, mid+1, end)
return node
return to_bst(nums, 0, len(nums) - 1)
110. Balanced Binary Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def get_height(root):
if root is None:
return 0
left_height, right_height = get_height(root.left), get_height(root.right)
if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return(get_height(root) >= 0)
111. Minimum Depth of Binary Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left and root.right:
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
else:
return max(self.minDepth(root.left), self.minDepth(root.right)) + 1
112. Path Sum
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root is None:
return False
if root.left is None and root.right is None and root.val == sum:
return True
else:
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
114. Flatten Binary Tree to Linked List
# 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 flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
cur = root
while cur:
if cur.left:
pre = cur.left
while pre.right:
pre = pre.right
pre.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.right
return cur
118. Pascal's Triangle
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
result = []
for i in range(numRows):
result.append([])
for j in range(i+1):
if j in (0, i):
result[i].append(1)
else:
result[i].append(result[i-1][j-1] + result[i-1][j])
return result
119. Pascal's Triangle II
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
result = [1] + [0] * rowIndex
for i in range(rowIndex):
result[0] = 1
for j in range(i+1, 0, -1):
result[j] = result[j] + result[j-1]
return result
121. Best Time to Buy and Sell Stock
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit, min_price = 0, float("inf")
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
125. Valid Palindrome
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
i, j = 0, (len(s)-1)
while i<j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
136. Single Number
class Solution:
def singleNumber(self, nums: List[int]) -> int:
list = []
for i in nums:
if i in list:
list.remove(i)
else:
list.append(i)
return list.pop()
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result ^= num
return result
141. Linked List Cycle
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast == slow:
return True
return False
151. Reverse Words in a String
class Solution:
def reverseWords(self, s: str) -> str:
if s =="":
return s
ls = s.split()
if ls == []:
return ""
result = ""
for i in range(0, len(ls) - 1):
result += ls[len(ls)-1-i] + " "
result += ls[0]
return result
160. Intersection of Two Linked Lists
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p1 = headA
p2 = headB
while p1 != p2:
if not p1:
p1 = headB
else:
p1 = p1.next
if not p2:
p2 = headA
else:
p2 = p2.next
return p2
162. Find Peak Element
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
for x in range(1, size - 1 ):
if nums[x] > nums[x - 1] and nums[x] > nums[x + 1]:
return x
return [0,size - 1][nums[0] < nums[size - 1]]
##That last row is an obscure way of writing an if then else expression.
## [0, size-1] creates a list of two elements.
## nums[0] < nums[size-1] returns either True or False
left, right = 0, len(nums) - 1
while left < right:
mid = (right + left) // 2
if nums[mid] < nums[mid + 1]:
ledt = mid + 1
else:
right = mid
return left
165. Compare Version Numbers
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
version1 = version1.split('.')
version2 = version2.split('.')
v1 = 0
for i in range(len(version1)):
s = int(version1[i])
v1 += (s*10**-i)
v2 = 0
for i in range(len(version2)):
s = int(version2[i])
v2 += (s*10**-i)
if v1 < v2:
return -1
elif v1 > v2:
return 1
else:
return 0
166. Fraction to Recurring Decimal
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
negativeFlag = numerator * denominator < 0
numerator = abs(numerator)
denominator = abs(denominator)
numList = []
cnt = 0
loopDict = dict()
loopStr = None
while True:
numList.append(str(numerator // denominator))
cnt += 1
numerator = 10 * (numerator % denominator)
if numerator == 0:
break
loc = loopDict.get(numerator)
if loc:
loopStr = "".join(numList[loc:cnt])
break
loopDict[numerator] = cnt
ans = numList[0]
if len(numList) > 1:
ans += "."
if loopStr:
ans += "".join(numList[1: len(numList) - len(loopStr)]) + "(" + loopStr + ")"
else:
ans += "".join(numList[1:])
if negativeFlag:
ans = "-" + ans
return ans
167. Two Sum II - Input array is sorted
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
start = 0
end = len(numbers) - 1
sum = 0
while start != end:
sum = numbers[start] + numbers[end]
if sum > target:
end -= 1
elif sum < target:
start += 1
else:
return [start+1, end+1]
169. Majority Element
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
left = self.majorityElement(nums[:len(nums)//2])
right = self.majorityElement(nums[len(nums)//2:])
if left == right:
return left
if nums.count(left) > nums.count(right):
return left
else:
return right
172. Factorial Trailing Zeroes
class Solution:
def trailingZeroes(self, n: int) -> int:
x = 5
res = 0
while x <= n:
res += n//x
x *= 5
return res
179. Largest Number
class Solution:
def largestNumber(self, nums: List[int]) -> str:
n = len(nums)
for i in range(n):
for j in range(n-i-1):
temp_1 = str(nums[j])
temp_2 = str(nums[j+1])
if(int(temp_1+temp_2)<int(temp_2+temp_1)):
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
output = ''
for i in nums:
output = output + str(i)
return str(int(output))
198. House Robber
class Solution:
def rob(self, nums: List[int]) -> int:
now = last =0
for i in nums:
last, now = now, max(i+last, now)
return now
DP
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n ==1:
return nums[0]
dp = [nums[0]]*n
dp[1] = max(nums[1],nums[0])
if n==2:
return dp[1]
for i in range(2, n):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[n-1]
202. Happy Number
class Solution:
def isHappy(self, n: int) -> bool:
tank = set()
while True:
if n not in tank:
tank.add(n)
n = sum( [int(x)*int(x) for x in list(str(n))])
if n == 1:
return True
else:
return False
204. Count Primes
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
# Corner case handle
return 0
is_prime = [ True for _ in range(n) ]
# Base case initialization
is_prime[0] = False
is_prime[1] = False
upper_bound = int(n ** 0.5)
for i in range( 2, upper_bound+1 ):
if not is_prime[i]:
# only run on prime number
continue
for j in range( i*i, n, i):
# mark all multiples of i as "not prime"
is_prime[j] = False
return sum(is_prime)
205. Isomorphic Strings
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
if s == t:
return True
hashmap = {}
for chars, chart in zip(s,t):
if chars in hashmap.keys() and hashmap[chars] != chart:
return False
elif chart in hashmap.values() and hashmap.get(chars) != chart:
return False
else:
hashmap[chars] = chart
return True
242. Valid Anagram
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return sorted(s) == sorted(t)
322. Coin Change
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
memo = dict()
def dp(n):
if n in memo: return memo[n]
if n == 0: return 0
if n <0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1: continue
res = min(res, 1+subproblem)
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(amount)
342. Power of Four
class Solution:
def isPowerOfFour(self, num: int) -> bool:
if num < 1:
return False
x = log(num) / log(4)
return x == int(x)
387. First Unique Character in a String
class Solution:
def firstUniqChar(self, s: str) -> int:
count = Counter(s)
for idx, ch in enumerate(s):
if count[ch] == 1:
return idx
return -1
367. Valid Perfect Square
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left <= right:
mid = (left+right) // 2
if mid ** 2 == num:
return True
elif mid ** 2 < num:
left = mid + 1
else:
right = mid -1
return False
392. Is Subsequence
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
for x in s:
if x in t:
t = t[t.index(x) + 1:]
else:
return False
return True
441. Arranging Coins
class Solution:
def arrangeCoins(self, n: int) -> int:
left, right = 0, n
while left <= right:
k = (right + left) // 2
curr = k * (k + 1) // 2
if curr == n:
return k
if n < curr:
right = k - 1
else:
left = k + 1
return right
535. Encode and Decode TinyURL
import string
import random
import math
fully_tiny = {}
tiny_full = {}
letters = string.ascii_letters + string.digits
class Codec:
def encode(self, longUrl):
"""Encodes a URL to a shortened URL.
:type longUrl: str
:rtype: str
"""
def short_addr():
ans = ''
tmp = ''
for i in range(6):
tmp = letters[random.randint(0, 10000) % 62]
ans += tmp
return ans
if longUrl in fully_tiny:
return "http://tinyurl.com/" + fully_tiny[longUrl]
else:
suffix = short_addr()
fully_tiny[longUrl] = suffix
tiny_full[suffix] = longUrl
return "http://tinyurl.com/" + suffix
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL.
:type shortUrl: str
:rtype: str
"""
shortUrl = shortUrl.split('/')[-1]
if shortUrl in tiny_full:
return tiny_full[shortUrl]
else:
return None
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))
540. Single Element in a Sorted Array
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l<r:
mid = (l + r) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid+1]:
l = mid + 2
else:
r = mid
return nums[l]
704. Binary Search
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left<= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif target < nums[mid]:
right = mid - 1
elif target > nums[mid]:
left = mid + 1
return -1
724. Find Pivot Index
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
S = sum(nums)
leftsum = 0
for i, x in enumerate(nums):
if leftsum == (S - leftsum - x):
return i
leftsum += x
return -1
873. Length of Longest Fibonacci Subsequence
class Solution:
def lenLongestFibSubseq(self, A: List[int]) -> int:
s = set(A)
n = len(A)
result = 0
for i in range(n-1):
for j in range(i+1, n):
a, b = A[i], A[j]
count = 2
while a+b in s:
a, b = b, a+b
count += 1
result = max(result, count)
return result if result > 2 else 0
897. Increasing Order Search Tree
# 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 increasingBST(self, root: TreeNode) -> TreeNode:
def inorder(node):
if node:
inorder(node.left)
node.left = None
self.cur.right = node
self.cur = node
inorder(node.right)
ans = self.cur = TreeNode(None)
inorder(root)
return ans.right
938. Range Sum of BST
class Solution(object):
def rangeSumBST(self, root, L, R):
def dfs(node):
if node:
if L <= node.val <= R:
ans.append(node.val)
dfs(node.left)
dfs(node.right)
if node.val < L:
dfs(node.right)
if node.val > R:
dfs(node.left)
ans = []
dfs(root)
print(ans)
return sum(ans)
1002. Find Common Characters
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
dict = collections.Counter(A[0])
for i in range(1, len(A)):
del_keys = []
for k, v in dict.items():
if k in A[i]:
dict[k] = min(A[i].count(k), v)
else:
del_keys.append(k)
for key in del_keys:
del dict[key]
return list(dict.elements())
1137. N-th Tribonacci Number
class Solution:
def tribonacci(self, n: int) -> int:
dp = {}
dp[0] = 0
dp[1] = 1
dp[2] = 1
for i in range(3, n+1):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
return dp[n]
1338. Reduce Array Size to The Half
class Solution:
def minSetSize(self, arr: List[int]) -> int:
r = 0
s = 0
count = {}
for i in arr:
if i in count:
count[i] += 1
else:
count[i] = 1
cnt = sorted(count.items(), key=lambda x:x[1], reverse=True)
# cnt = reversed(sorted(count.values()))
for i in cnt:
r += 1
s += i[1]
if s >= (len(arr)//2):
return r
else:
return
1486. XOR Operation in an Array
class Solution:
def xorOperation(self, n: int, start: int) -> int:
res = 0;
arr = [start + 2 * i for i in range(n)]
for a in arr:
res ^= a
return res
1518. Water Bottles
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
return numBottles + (numBottles-1) // (numExchange-1)