Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

chore - move python solutions from root to /python#425

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
mitchellirvin merged 4 commits intomainfrommirvin/move-python-sols-to-dir
Jul 9, 2022
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
9 changes: 9 additions & 0 deletionspython/1-Two-Sum.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {} # val -> index

for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
45 changes: 45 additions & 0 deletionspython/10-Regular-Expression-Matching.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
# BOTTOM-UP Dynamic Programming
class Solution:
def isMatch(self, s: str, p: str) -> bool:
cache = [[False] * (len(p) + 1) for i in range(len(s) + 1)]
cache[len(s)][len(p)] = True

for i in range(len(s), -1, -1):
for j in range(len(p) - 1, -1 ,-1):
match = i < len(s) and (s[i] == p[j] or p[j] == ".")

if (j + 1) < len(p) and p[j + 1] == "*":
cache[i][j] = cache[i][j + 2]
if match:
cache[i][j] = cache[i + 1][j] or cache[i][j]
elif match:
cache[i][j] = cache[i+1][j+1]

return cache[0][0]


# TOP DOWN MEMOIZATION
class Solution:
def isMatch(self, s: str, p: str) -> bool:
cache = {}

def dfs(i, j):
if (i, j) in cache:
return cache[(i, j)]
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False

match = i < len(s) and (s[i] == p[j] or p[j] == ".")
if (j + 1) < len(p) and p[j + 1] == "*":
cache[(i, j)] = (dfs(i, j + 2) or # dont use *
(match and dfs(i + 1, j))) # use *
return cache[(i, j)]
if match:
cache[(i,j)] = dfs(i + 1, j + 1)
return cache[(i,j)]
cache[(i,j)] = False
return False

return dfs(0, 0)
13 changes: 13 additions & 0 deletionspython/100-Same-Tree.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
# 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 not p and not q: return True
if p and q and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else: return False
23 changes: 23 additions & 0 deletionspython/102-Binary-Tree-Level-Order-Traversal.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
q = collections.deque()
if root: q.append(root)

while q:
val = []

for i in range(len(q)):
node = q.popleft()
val.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(val)
return res
41 changes: 41 additions & 0 deletionspython/104-Maximum-Depth-of-Binary-Tree.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
# RECURSIVE DFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0

return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

# ITERATIVE DFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
stack = [[root, 1]]
res = 0

while stack:
node, depth = stack.pop()

if node:
res = max(res, depth)
stack.append([node.left, depth + 1])
stack.append([node.right, depth + 1])
return res

# BFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0

level = 0
q = deque([root])
while q:

for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
13 changes: 13 additions & 0 deletionspython/1046-Last-Stone-Weight.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)

while len(stones) > 1:
first = heapq.heappop(stones)
second = heapq.heappop(stones)
if second > first:
heapq.heappush(stones, first - second)

stones.append(0)
return abs(stones[0])
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None

root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
return root
12 changes: 12 additions & 0 deletionspython/11-Container-With-Most-Water.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
res = 0

while l < r:
res = max(res, min(height[l], height[r]) * (r - l))
if height[l] < height[r]:
l += 1
elif height[r] <= height[l]:
r -= 1
return res
17 changes: 17 additions & 0 deletionspython/110-Balanced-Binary-Tree.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:

def dfs(root):
if not root: return [True, 0]

left, right = dfs(root.left), dfs(root.right)
balanced = (left[0] and right[0] and
abs(left[1] - right[1]) <= 1)
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
12 changes: 12 additions & 0 deletionspython/1143-Longest-Common-Subsequence.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]

for i in range(len(text1) - 1, -1, -1):
for j in range(len(text2) - 1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i][j + 1], dp[i + 1][j])

return dp[0][0]
16 changes: 16 additions & 0 deletionspython/115-Distinct-Subsequences.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
class Solution:
def numDistinct(self, s: str, t: str) -> int:
cache = {}

for i in range(len(s) + 1):
cache[(i, len(t))] = 1
for j in range(len(t)):
cache[(len(s), j)] = 0

for i in range(len(s) - 1, -1, -1):
for j in range(len(t) - 1, -1, -1):
if s[i] == t[j]:
cache[(i, j)] = cache[(i+1,j+1)] + cache[(i+1,j)]
else:
cache[(i,j)] = cache[(i+1,j)]
return cache[(0,0)]
13 changes: 13 additions & 0 deletionspython/12-Integer-To-Roman.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
class Solution:
def intToRoman(self, num: int) -> str:
symList = [["I", 1], ["IV" , 4], ["V" , 5], ["IX" , 9],
["X" , 10], ["XL" , 40], ["L" , 50], ["XC" , 90],
["C" , 100], ["CD", 400], ["D", 500], ["CM", 900],
["M" , 1000]]
res = ""
for sym, val in reversed(symList):
if num // val:
count = num // val
res += (sym * count)
num = num % val
return res
10 changes: 10 additions & 0 deletionspython/121-Best-Time-To-Buy-and-Sell-Stock.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0

l = 0
for r in range(1, len(prices)):
if prices[r] < prices[l]:
l = r
res = max(res, prices[r] - prices[l])
return res
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
class Solution:
def maxLength(self, arr: List[str]) -> int:
charSet = set()

def overlap(charSet, s):
c = Counter(charSet) + Counter(s)
return max(c.values()) > 1
# prev = set()
# for c in s:
# if c in charSet or c in prev:
# return True
# prev.add(c)
# return False

def backtrack(i):
if i == len(arr):
return len(charSet)
res = 0
if not overlap(charSet, arr[i]):
for c in arr[i]:
charSet.add(c)
res = backtrack(i + 1)
for c in arr[i]:
charSet.remove(c)
return max(res, backtrack(i + 1)) # dont concatenate arr[i]

return backtrack(0)
26 changes: 26 additions & 0 deletionspython/124-Binary-Tree-Maximum-Path-Sum.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
# 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 maxPathSum(self, root: TreeNode) -> int:
res = [root.val]

# return max path sum without split
def dfs(root):
if not root:
return 0

leftMax = dfs(root.left)
rightMax = dfs(root.right)
leftMax = max(leftMax, 0)
rightMax = max(rightMax, 0)

# compute max path sum WITH split
res[0] = max(res[0], root.val + leftMax + rightMax)
return root.val + max(leftMax, rightMax)

dfs(root)
return res[0]
19 changes: 19 additions & 0 deletionspython/125-Valid-Palindrome.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.alphanum(s[l]):
l += 1
while l < r and not self.alphanum(s[r]):
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True

# Could write own alpha-numeric function
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'))
28 changes: 28 additions & 0 deletionspython/127-Word-Ladder.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0

nei = collections.defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
nei[pattern].append(word)

visit = set([beginWord])
q = deque([beginWord])
res = 1
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
for neiWord in nei[pattern]:
if neiWord not in visit:
visit.add(neiWord)
q.append(neiWord)
res += 1
return 0
14 changes: 14 additions & 0 deletionspython/128-Longest-consecutive-sequence.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
classSolution:
deflongestConsecutive(self,nums:List[int])->int:
numSet=set(nums)
longest=0

forninnums:
# check if its the start of a sequence
if (n-1)notinnumSet:
length=1
while (n+length)innumSet:
length+=1
longest=max(length,longest)
returnlongest

11 changes: 11 additions & 0 deletionspython/13-Roman-To-Integer.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
class Solution:
def romanToInt(self, s: str) -> int:
roman = { "I" : 1, "V" : 5, "X" : 10,
"L" : 50, "C" : 100, "D" : 500, "M" : 1000 }
res = 0
for i in range(len(s)):
if i + 1 < len(s) and roman[s[i]] < roman[s[i + 1]]:
res -= roman[s[i]]
else:
res += roman[s[i]]
return res
Loading
[8]ページ先頭
©2009-2025 Movatter.jp