In [ ]:
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if head is None:
return head
dummy = ListNode(0)
dummy.next = head
pos = dummy
while pos.next:
if pos.next.val == val:
pos.next = pos.next.next
else:
pos = pos.next
return dummy.next
In [ ]:
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
def split(N):
ans = []
while N > 0:
ans.append(N%10)
N /= 10
return ans
nums = {}
while True:
val = sum([x**2 for x in split(n)])
if val == 1:
return True
elif val in nums:
return False
else:
nums[val] = 1
n = val
In [ ]:
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
L = len(nums)
if L == 0:
return 0
elif L == 1:
return nums[0]
elif L == 2:
return max(nums[0], nums[1])
dp = [0] * L
dp[0] = nums[0]
if nums[1] > nums[0]:
dp[1] = nums[1]
else:
dp[1] = nums[0]
for n in xrange(2, L):
dp[n] = max(dp[n-1], nums[n]+dp[n-2])
return dp[-1]
In [ ]:
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
num = 0
for _ in xrange(32):
if n % 2 == 1:
num += 1
n = n >> 1
return num
In [ ]:
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
new = 0
for i in xrange(32):
new = (new << 1) | ((n >> i) % 2)
return new
In [ ]:
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
L = len(nums)
k = k%L
buff = nums[L-k:]
for i in xrange(L-k-1, -1, -1):
nums[i+k] = nums[i]
for i in xrange(k):
nums[i] = buff[i]
In [ ]:
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
ans, base = 0, 5
while base <= n:
ans += n/base
base *= 5
return ans
In [ ]:
class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
L = len(s)
num = 0
for pos in xrange(L):
num += (ord(s[L-pos-1]) - 64) * 26**pos
return num
In [ ]:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
lim = len(nums)/2
pre = {}
for n in nums:
if n in pre:
pre[n] += 1
if pre[n] > lim:
return n
else:
pre[n] = 1
return pre.keys()[-1]
In [ ]:
class Solution(object):
def convertToTitle(self, n):
"""
:type n: int
:rtype: str
"""
col = ''
while n > 26:
s = n % 26
if s == 0:
s = 26
n = (n-s) / 26
col = chr(s+64) + col
col = chr(n+64) + col
return col
In [ ]:
class Solution(object):
def compareVersion(self, version1, version2):
"""
:type version1: str
:type version2: str
:rtype: int
"""
v1 = map(int, version1.split('.'))
v2 = map(int, version2.split('.'))
i, j = 0, 0
L1, L2 = len(v1), len(v2)
while i < L1 and j < L2:
if v1[i] > v2[j]:
return 1
elif v1[i] < v2[j]:
return -1
else:
i += 1
j += 1
while i < L1:
if v1[i] > 0:
return 1
i += 1
while j < L2:
if v2[j] > 0:
return -1
j += 1
return 0
In [ ]:
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if headA == None or headB == None:
return None
La, tailA = 0, headA
while tailA.next:
La += 1
tailA = tailA.next
Lb, tailB = 0, headB
while tailB.next:
Lb += 1
tailB = tailB.next
if tailA != tailB:
return None
if La > Lb:
for _ in xrange(La-Lb):
headA = headA.next
else:
for _ in xrange(Lb-La):
headB = headB.next
while headA and headA != headB:
headA = headA.next
headB = headB.next
return headA
In [ ]:
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.minVals = []
self.vals = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.vals.append(x)
if len(self.minVals) == 0 or x <= self.minVals[-1]:
self.minVals.append(x)
def pop(self):
"""
:rtype: void
"""
if self.minVals[-1] == self.vals[-1]:
self.minVals.pop()
self.vals.pop()
def top(self):
"""
:rtype: int
"""
return self.vals[-1]
def getMin(self):
"""
:rtype: int
"""
return self.minVals[-1]
In [ ]:
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
dic = {}
for n in nums:
if n in dic:
return True
else:
dic[n] = 1
return False
In [ ]:
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
L = len(prices)
if L == 0:
return 0
profits = [0] * L
leftBuy, leftProfit = prices[0], 0
for i in xrange(1,L):
if prices[i] < leftBuy:
leftBuy = prices[i]
else:
leftProfit = max(leftProfit, prices[i] - leftBuy)
profits[i] = leftProfit
rightSell, rightProfit, ans = prices[-1], 0, profits[-1]
for j in xrange(L-2, -1, -1):
if prices[j] > rightSell:
rightSell = prices[j]
else:
rightProfit = max(rightProfit, rightSell - prices[j])
ans = max(ans, rightProfit+profits[j])
return ans
In [ ]:
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
profit = 0
for i in xrange(1, len(prices)):
if prices[i] > prices[i-1]:
profit += (prices[i]-prices[i-1])
return profit
In [ ]:
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None:
return False
fast, slow = head, head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
In [ ]:
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = re.sub('[^A-Za-z0-9]+', '', s)
if s == "":
return True
i, j = 0, len(s)-1
while i < j:
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
In [ ]:
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
buy, profit = prices[0], 0
for sell in prices[1:]:
if sell - buy > profit:
profit = sell - buy
elif sell < buy:
buy = sell
return profit
In [ ]:
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
rows = len(triangle)
if rows == 0:
return 0
nums = triangle[-1]
for row in xrange(rows-2, -1, -1):
for col in xrange(len(triangle[row])):
nums[col] = min(nums[col], nums[col+1]) + triangle[row][col]
return nums[0]
In [ ]:
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
nums = [0] * (rowIndex+2)
nums[1] = 1
for i in xrange(1, rowIndex+1):
for j in xrange(rowIndex+1, 0, -1):
nums[j] += nums[j-1]
return nums[1:]
In [ ]:
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows < 1:
return []
ans = [[1]]
while numRows > 1:
i, last = 0, ans[-1]
L, temp = len(last), []
while i+1 < L:
temp.append(last[i]+last[i+1])
i += 1
ans.append([1]+temp+[1])
numRows -= 1
return ans
In [ ]:
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
now = root
leftMost = None
while now and now.left:
if leftMost is None:
leftMost = now.left
now.left.next = now.right
if now.next:
now.right.next = now.next.left
now = now.next
else:
now = leftMost
leftMost = None
In [ ]:
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if root is None:
return None
def clean(node):
if node is None:
return None
if node.left is None and node.right is None:
return (node, node)
right = clean(node.right)
left = clean(node.left)
if left:
node.right = left[0]
node.left = None
if right:
left[1].right = right[0]
return (node, right[1])
else:
return (node, left[1])
else:
if right:
return (node, right[1])
clean(root)
In [ ]:
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
paths = []
def findPath(node, path, S):
if node is None:
return
if node.left is None and node.right is None:
if node.val == S:
paths.append(path+[node.val])
findPath(node.left, path+[node.val], S-node.val)
findPath(node.right, path+[node.val], S-node.val)
findPath(root, [], sum)
return paths
In [ ]:
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
def pathSum(node, S):
if node.left == None and node.right == None:
return S == node.val
elif node.left:
if node.right:
return pathSum(node.left, S-node.val) or pathSum(node.right, S-node.val)
else:
return pathSum(node.left, S-node.val)
elif node.right:
return pathSum(node.right, S-node.val)
else:
return False
if root is None:
return False
return pathSum(root, sum)
In [ ]:
class Solution(object):
def findDepth(self, root):
if root == None:
return 0
left = self.findDepth(root.left)
if left == -1:
return -1
right = self.findDepth(root.right)
if right == -1:
return -1
if abs(right-left) <= 1:
return max(right, left) + 1
else:
return -1
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.findDepth(root) != -1
In [ ]:
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
n, pos = 0, head
while pos:
n += 1
pos = pos.next
self.head = head
def buildTree(start, end):
if start > end:
return None
mid = (start+end)/2
left = buildTree(start, mid-1)
root = TreeNode(self.head.val)
root.left = left
self.head = self.head.next
root.right = buildTree(mid+1, end)
return root
return buildTree(0, n-1)
In [ ]:
class Solution(object):
def finder(self, nums, val):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)/2
if nums[mid] == val:
right = mid-1
else:
left = mid+1
return right+1
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
L = len(nums)
if L == 0:
return None
mid = L/2
val = nums[mid]
if val == nums[mid-1]:
mid = self.finder(nums[:mid], val)
root = TreeNode(val)
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
In [ ]:
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
ans = []
nodes = [root]
while len(nodes) > 0:
vals, temp = [], []
for node in nodes:
if node:
vals.append(node.val)
temp.append(node.left)
temp.append(node.right)
if vals:
ans = [vals] + ans
nodes = temp
return ans
In [ ]:
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
self.i = len(postorder)-1
def helper(Inorder):
if Inorder == []:
return None
root = TreeNode(postorder[self.i])
j = Inorder.index(postorder[self.i])
self.i -= 1
root.right = helper(Inorder[j+1:])
root.left = helper(Inorder[:j])
return root
return helper(inorder)
In [ ]:
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
self.i = 0
def helper(Inorder):
if Inorder == []:
return None
root = TreeNode(preorder[self.i])
j = Inorder.index(preorder[self.i])
self.i += 1
root.left = helper(Inorder[:j])
root.right = helper(Inorder[j+1:])
return root
return helper(inorder)
In [ ]:
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
In [ ]:
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
order = 1
ans = []
nodes = [root]
while len(nodes) > 0:
vals, temp = [], []
for node in nodes:
if node:
vals.append(node.val)
if order == 0:
temp = [node.left, node.right] + temp
else:
temp = [node.right, node.left] + temp
if vals != []:
ans.append(vals)
nodes = temp
order = (order+1)%2
return ans
In [ ]:
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
ans = []
nodes = [root]
while len(nodes) > 0:
vals, temp = [], []
for node in nodes:
if node:
vals.append(node.val)
temp.append(node.left)
temp.append(node.right)
if vals != []:
ans.append(vals)
nodes = temp
return ans
In [ ]:
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
def helper(left, right):
if left == None or right == None:
return left == None and right == None
if left.val != right.val:
return False
return helper(left.right, right.left) and helper(left.left, right.right)
return helper(root.left, root.right)
In [ ]:
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p == None:
return q == None
if q == None:
return p == None
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
In [ ]:
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.lim = None
def helper(node):
if node:
if helper(node.left):
if self.lim == None or self.lim < node.val:
self.lim = node.val
return helper(node.right)
else:
return False
else:
return False
else:
return True
return helper(root)
In [ ]:
class Solution(object):
def dfs(self, start, end):
if start > end:
return [None]
ans = []
for rootVal in xrange(start, end+1):
leftTrees = self.dfs(start, rootVal-1)
rightTrees = self.dfs(rootVal+1, end)
for left in leftTrees:
for right in rightTrees:
root = TreeNode(rootVal)
root.left = left
root.right = right
ans.append(root)
return ans
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n < 1:
return []
return self.dfs(1, n)
In [ ]:
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp, i = [1,1], 2
while i <= n:
count = 0
for left in xrange(i):
right = i-left-1
count += (dp[left]*dp[right])
dp.append(count)
i += 1
return dp[n]
In [ ]:
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
def helper(node):
if node.left:
helper(node.left)
ans.append(node.val)
if node.right:
helper(node.right)
if root:
helper(root)
return ans
In [ ]:
class Solution(object):
def isValid(self, num):
L = len(num)
if L == 0 or L > 3:
return False
if L > 1 and num[0] == '0':
return False
if L == 3 and int(num) > 255:
return False
return True
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ips = []
def helper(S, ip, level):
if level == 4:
if S == '':
ips.append('.'.join(ip))
else:
return
i = 0
while i < len(S) and i < 3:
if self.isValid(S[:i+1]):
helper(S[i+1:], ip+[S[:i+1]], level+1)
i += 1
helper(s, [], 0)
return ips
In [ ]:
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
def helper(m, n, buf):
if m == '0' and n == '0':
if buf == '1':
ans, buf = '1', '0'
else:
ans = '0'
elif m == '1' and n == '1':
if buf == '1':
ans = '1'
else:
ans = '0'
buf = '1'
else:
if buf == '1':
ans = '0'
else:
ans, buf = '1', '0'
return ans, buf
buf, ans = '0', ''
i, j = len(a)-1, len(b)-1
while i >= 0 and j >= 0:
temp, buf = helper(a[i], b[j], buf)
ans = temp + ans
i -= 1
j -= 1
while i >= 0:
temp, buf = helper(a[i], '0', buf)
ans = temp + ans
i -= 1
while j >= 0:
temp, buf = helper(b[j], '0', buf)
ans = temp + ans
j -= 1
if buf == '1':
ans = buf + ans
return ans
In [ ]:
class Solution(object):
def findNode(self, head, k):
while k > 0:
head = head.next
k -= 1
return head
def reverse(self, start, k):
last, now = start, start.next
while k > 0:
temp = now.next
now.next = last
last = now
now = temp
k -= 1
return last, now
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
pivot = self.findNode(dummy, m-1)
start = pivot.next
last, now = self.reverse(start, n-m)
start.next = now
pivot.next = last
return dummy.next
In [ ]:
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
i, j, k = m-1, n-1, m+n-1
while i >= 0 and j >= 0:
if nums1[i] >= nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
In [ ]:
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s == '' or s[0] == '0':
return 0
dp = [1,1]
L = len(s)
for i in xrange(1, L):
n = int(s[i-1:i+1])
count = 0
if 9 < n < 27:
count += dp[i-1]
if s[i] != '0':
count += dp[i]
if count == 0:
return 0
else:
dp.append(count)
return dp[L]
In [ ]:
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
pre = {}
ans = []
for n in nums:
if n in pre:
pre[n] += 1
else:
pre[n] = 1
def helper(Keys, parents):
if Keys == []:
ans.append(parents)
else:
i = 0
while i <= pre[Keys[0]]:
helper(Keys[1:], parents + [Keys[0]] * i)
i += 1
helper(pre.keys(), [])
return ans
In [ ]:
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
ans = [0]
add = 1
while n > 0:
for num in ans[::-1]:
ans.append(num+add)
n -= 1
add *= 2
return ans
In [ ]:
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head is None:
return head
ahead, bhead = ListNode(0), ListNode(0)
atail, btail = ahead, bhead
while head:
if head.val < x:
atail.next = head
atail = atail.next
else:
btail.next = head
btail = btail.next
head = head.next
btail.next = None
atail.next = bhead.next
return ahead.next
In [ ]:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
L = len(nums)
left, right = 0, L-1
while left <= right:
mid = (left+right)/2
if nums[mid] == target:
return True
elif nums[mid] > nums[left]:
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[left]:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
left += 1
return False
In [ ]:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)/2
if nums[mid] == target:
return mid
elif nums[mid] >= nums[left]:
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
In [ ]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
now = ListNode(0)
new = now
pos = head
while pos:
if pos.next and pos.val == pos.next.val:
while pos.next and pos.val == pos.next.val:
pos = pos.next
else:
print pos.val
now.next = pos
now = now.next
pos = pos.next
now.next = None
return new.next
In [ ]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
last = head.val
prev, pos = head, head.next
while pos:
if pos.val == last:
prev.next = pos.next
else:
last = pos.val
prev = pos
pos = pos.next
return head
In [ ]:
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
pre = {}
def helper(N):
if N == 0:
return 1
elif N < 0:
return 0
else:
if N not in pre:
a, b = helper(N-1), helper(N-2)
pre[N] = a+b
return pre[N]
return helper(n)
In [ ]:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
counts = {}
for n in nums:
if n in counts:
counts[n] += 1
else:
counts[n] = 1
L = 0
for n in sorted(counts.keys()):
end = L + min(2, counts[n])
while L < end:
nums[L] = n
L += 1
return L
In [ ]:
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
Ls, Lp = len(s), len(p)
dp = [[False for _ in xrange(Lp+1)] for _ in xrange(Ls+1)]
dp[0][0] = True
for i in xrange(1, Lp+1):
if p[i-1] == '*':
dp[0][i] = dp[0][i-2]
for j in xrange(1, Ls+1):
for i in xrange(1, Lp+1):
if p[i-1] == '*':
dp[j][i] = dp[j][i-2]
if not dp[j][i] and (p[i-2] == '.' or s[j-1] == p[i-2]):
dp[j][i] = dp[j-1][i]
elif p[i-1] == '.' or s[j-1] == p[i-1]:
dp[j][i] = dp[j-1][i-1]
return dp[-1][-1]
In [ ]:
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if word == '':
return True
m, n = len(board), len(board[0])
if m == 0 or n == 0:
return False
visited = [[False for _ in xrange(n)] for _ in xrange(m)]
def search(i, j, w):
if w == '':
return True
if i < 0 or i >= n or j < 0 or j >= m:
return False
elif w[0] != board[j][i] or visited[j][i]:
return False
else:
visited[j][i] = True
if search(i+1, j, w[1:]) or search(i-1, j, w[1:]) or search(i, j+1, w[1:]) or search(i, j-1, w[1:]):
return True
else:
visited[j][i] = False
return False
for j in xrange(m):
for i in xrange(n):
if search(i, j, word):
return True
return False
In [ ]:
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
def helper(rest, parents):
if rest == []:
ans.append(parents)
else:
helper(rest[1:], parents)
helper(rest[1:], parents+rest[:1])
helper(nums, [])
return ans
In [ ]:
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
colors = {0: 0, 1: 0, 2: 0}
for n in nums:
colors[n] += 1
i = 0
for c in xrange(3):
for _ in xrange(colors[c]):
nums[i] = c
i += 1
In [ ]:
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m, n = len(matrix), len(matrix[0])
if m == 0 or n == 0:
return False
def helper(nums, L):
left, right = 0, L-1
while right-left > 1 and nums[left] <= target and target <= nums[right]:
mid = (left+right)/2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid
else:
left = mid
if nums[left] <= target and target < nums[right]:
return left
else:
return right
rows = [r[0] for r in matrix]
row = helper(rows, m)
col = helper(matrix[row], n)
return matrix[row][col] == target
In [ ]:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
firstRow, firstCol = False, False
m, n = len(matrix), len(matrix[0])
for i in xrange(n):
if matrix[0][i] == 0:
firstRow = True
break
for j in xrange(m):
if matrix[j][0] == 0:
firstCol = True
break
for j in xrange(1, m):
for i in xrange(1, n):
if matrix[j][i] == 0:
matrix[j][0], matrix[0][i] = 0, 0
for i in xrange(1, n):
if matrix[0][i] == 0:
for j in xrange(1, m):
matrix[j][i] = 0
for j in xrange(1, m):
if matrix[j][0] == 0:
for i in xrange(1, n):
matrix[j][i] = 0
if firstRow:
for i in xrange(n):
matrix[0][i] = 0
if firstCol:
for j in xrange(m):
matrix[j][0] = 0
In [ ]:
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
P = ['/']
for f in path.split('/'):
if f == '' or f == '.':
continue
elif f == '..':
if P [-1] != '/':
P.pop()
else:
P.append('/'+f)
if len(P) == 1:
return '/'
else:
return ''.join(P[1:])
In [ ]:
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x <= 1:
return x
left = 1
right = x
mid = (left + right) / 2
while mid > left:
temp = mid * mid
if temp == x:
return mid
elif temp > x:
right = mid
else:
left = mid
mid = (left + right) / 2
return left
In [ ]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
def merge2Lists(L1, L2):
ans = ListNode(0)
pos = ans
while L1 and L2:
if L1.val > L2.val:
pos.next = L2
L2 = L2.next
pos = pos.next
else:
pos.next = L1
L1 = L1.next
pos = pos.next
if L1:
pos.next = L1
elif L2:
pos.next = L2
return ans.next
if lists == []:
return []
while len(lists) > 1:
L1, L2 = lists[:2]
lists = lists[2:]
lists.append(merge2Lists(L1,L2))
return lists[0]
In [ ]:
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
costs = grid
for i in xrange(len(grid)):
for j in xrange(len(grid[i])):
if i == 0 and j == 0:
continue
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i][j-1], grid[i-1][j])
return grid[-1][-1]
In [ ]:
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
counts = obstacleGrid
for i in xrange(len(obstacleGrid)):
for j in xrange(len(obstacleGrid[i])):
if obstacleGrid[i][j] == 1:
obstacleGrid[i][j] = 0
elif i == 0 and j == 0:
obstacleGrid[i][j] = 1
elif i == 0:
obstacleGrid[i][j] = obstacleGrid[i][j-1]
elif j == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j]
else:
obstacleGrid[i][j] = obstacleGrid[i][j-1] + obstacleGrid[i-1][j]
return obstacleGrid[-1][-1]
In [ ]:
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
carry = 1
i = len(digits) - 1
while i >= 0 and carry > 0:
carry += digits[i]
digits[i] = carry % 10
carry = carry / 10
i -= 1
if carry > 0:
return [carry] + digits
return digits
In [ ]:
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def findKth(k, A, m, B, n):
if m <= 0:
return B[k-1]
if n == 0:
return A[k-1]
if k == 1:
return min(A[0], B[0])
a, b = m/2, n/2
pivot = a + b + 1
if A[a] >= B[b]:
if pivot >= k:
return findKth(k, A[:a], a, B, n)
else:
return findKth(k-b-1, A, m, B[b+1:], n-b-1)
else:
if pivot >= k:
return findKth(k, A, m, B[:b], b)
else:
return findKth(k-a-1, A[a+1:], m-a-1, B, n)
m, n = len(nums1), len(nums2)
S = m+n
if S % 2 == 0:
return 0.5 * (findKth(S/2, nums1, m, nums2, n) + findKth(S/2+1, nums1, m, nums2, n))
else:
return findKth(S/2+1, nums1, m, nums2, n)
In [ ]:
class Solution(object):
def uniquePaths(self, M, N):
"""
:type m: int
:type n: int
:rtype: int
"""
pre = {}
def helper(m, n):
if m == 1 or n == 1:
return 1
a, b = (m, n) if m > n else (n, m)
if (a, b) in pre:
return pre[(a,b)]
else:
ans = helper(m-1, n) + helper(m, n-1)
pre[(a,b)] = ans
return ans
return helper(M, N)
In [ ]:
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head == None:
return head
path = {}
L = 0
while head:
path[L] = head
L += 1
head = head.next
k = k % L
if k == 0:
return path[0]
ans = path[L-k]
path[L-k-1].next = None
if k == 1:
ans.next = path[0]
else:
path[L-1].next = path[0]
return ans
In [ ]:
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
nums = range(1,n+1)
fac = [1]
for i in xrange(2, n):
fac.append(fac[-1]*i)
ans = []
for p in fac[::-1]:
remainder = k % p
carry = k / p
if remainder == 0:
carry -= 1
ans.append(nums[carry])
nums.remove(nums[carry])
k = remainder
ans += nums
return ''.join(map(str, ans))
In [ ]:
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
matrix = []
if n == 0:
return matrix
for _ in xrange(n):
matrix.append([0]*n)
left = 0
right = n-1
top = 0
bottom = n-1
pos = 1
while left < right and top < bottom:
for i in xrange(right-left+1):
matrix[top][left+i] = pos
pos += 1
top += 1
for j in xrange(bottom-top+1):
matrix[top+j][right] = pos
pos += 1
right -= 1
for i in xrange(right-left+1):
matrix[bottom][right-i] = pos
pos += 1
bottom -= 1
for j in xrange(bottom-top+1):
matrix[bottom-j][left] = pos
pos += 1
left += 1
if left == right and top == bottom:
matrix[top][left] = pos
return matrix
In [ ]:
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
pos = 0
ans = 0
for jump in nums[:-1]:
ans = max(ans, pos+jump)
if (ans <= pos):
return False
pos += 1
return True
In [ ]:
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
m = len(matrix)
if m == 0:
return matrix
n = len(matrix[0])
left = 0
right = n-1
top = 0
bottom = m-1
ans = []
while left < right and top < bottom:
for i in xrange(left, right+1):
ans.append(matrix[top][i])
top += 1
for j in xrange(top, bottom+1):
ans.append(matrix[j][right])
right -= 1
for i in xrange(right, left-1, -1):
ans.append(matrix[bottom][i])
bottom -= 1
for j in xrange(bottom, top-1, -1):
ans.append(matrix[j][left])
left += 1
if left <= right and top == bottom:
ans += matrix[top][left:right+1]
if top < bottom and left == right:
for j in xrange(top, bottom+1):
ans.append(matrix[j][right])
return ans
In [ ]:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
L = len(nums)
if L == 0:
return None
ans = nums[0]
S = 0
for i in xrange(L):
S += nums[i]
if S > ans:
ans = S
if S < 0:
S = 0
return ans
In [ ]:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1.0
elif n == 1:
return x
if n < 0:
x = 1.0 / x
n = -n
if n % 2 == 1:
return x * self.myPow(x, n-1)
else:
return self.myPow(x*x, n/2)
In [ ]:
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
pre = {}
for word in strs:
W = ''.join(sorted(word))
if W in pre:
pre[W].append(word)
else:
pre[W] = [word]
return pre.values()
In [ ]:
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
left = 0
right = n-1
top = 0
bottom = n-1
while left < right and top < bottom:
temp1 = matrix[top][left:right+1]
temp2 = temp1[:]
L = right-left+1
for j in xrange(L):
temp1[j] = matrix[top+j][right]
matrix[top+j][right] = temp2[j]
temp2 = temp1[:]
for i in xrange(1,L):
temp1[i] = matrix[bottom][right-i]
matrix[bottom][right-i] = temp2[i]
temp2 = temp1[:]
for j in xrange(1,L):
temp1[j] = matrix[bottom-j][left]
matrix[bottom-j][left] = temp2[j]
temp2 = temp1[:]
for i in xrange(1,L-1):
temp1[i] = matrix[top][left+i]
matrix[top][left+i] = temp2[i]
left += 1
right -= 1
top += 1
bottom -= 1
In [ ]:
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
nums.sort()
def helper(Nums, parents=[]):
L = len(Nums)
if L == 0:
ans.append(parents)
else:
for i in xrange(L):
if i == 0 or Nums[i] != Nums[i-1]:
helper(Nums[:i]+Nums[i+1:], parents+[Nums[i]])
helper(nums)
return ans
In [ ]:
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
def helper(Nums, parents=[]):
L = len(Nums)
if L == 0:
ans.append(parents)
else:
for i in xrange(L):
helper(Nums[:i]+Nums[i+1:], parents+[Nums[i]])
helper(nums)
return ans
In [ ]:
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = num1[::-1]
num2 = num2[::-1]
L1 = len(num1)
L2 = len(num2)
pre = {}
ans = ''
for i in xrange(L1):
for j in xrange(L2):
S = int(num1[i]) * int(num2[j])
if i+j in pre:
pre[i+j] += S
else:
pre[i+j] = S
carry = 0
for i in xrange(L1+L2-1):
digit = (carry+pre[i]) % 10
carry = (carry+pre[i]) / 10
ans = str(digit) + ans
if carry > 0:
ans = str(carry) + ans
else:
while ans[0] == '0' and len(ans) > 1:
ans = ans[1:]
return ans
In [ ]:
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
L = len(candidates)
ans = []
used = [0] * len(candidates)
def dfs(now, index, temp):
if now == target:
ans.append(temp[:])
return
else:
for i in xrange(index, L):
if candidates[i] + now <= target and (i == 0 or candidates[i] != candidates[i-1] or used[i-1] == 1):
temp.append(candidates[i])
used[i] = 1
dfs(now + candidates[i], i+1, temp)
used[i] = 0
temp.pop()
dfs(0, 0, [])
return ans
In [ ]:
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
def helper(nums, T):
L = len(nums)
ans = []
if L == 0 or T <= 0:
return ans
index = L-1
while index >= 0:
mul = 1
S = nums[index] * mul
while S < T:
combs = helper(nums[:index], T - S)
for comb in combs:
ans.append(comb + [nums[index]] * mul)
mul += 1
S = nums[index] * mul
if S == T:
ans.append([nums[index]] * mul)
index -= 1
return ans
return helper(candidates, target)
In [ ]:
class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
ans = '1'
while n > 1:
strs = ''
i = 0
while i < len(ans):
j = i + 1
temp = ans[i]
count = 1
while temp == ans[j:j+1]:
count += 1
j += 1
i = j
strs += '{}{}'.format(count,temp)
n -= 1
ans = strs
return ans
In [ ]:
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
L = len(nums)
start = 0
end = L
pivot = (start+end)/2
while start < end:
if nums[pivot] == target:
return pivot
elif nums[pivot] > target:
end = pivot
else:
start = pivot+1
pivot = (start + end)/2
return pivot
In [ ]:
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
def valid(nums):
pre = {}
for n in nums:
if n == ".":
continue
if n in pre:
return False
else:
pre[n] = 1
return True
def smallBoard(i, j):
grid = []
for y in xrange(j,j+3):
for x in xrange(i,i+3):
grid.append(board[y][x])
return grid
for row in board:
if not valid(row):
return False
for col in xrange(9):
nums = [board[row][col] for row in range(9)]
if not valid(nums):
return False
for j in xrange(0,8,3):
for i in xrange(0,8,3):
if not valid(smallBoard(i, j)):
return False
return True
In [ ]:
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
def helper(Nums):
L = len(Nums)
if L == 0:
return [-1,-1]
elif L == 1:
if Nums[0] == target:
return [0,0]
else:
return [-1,-1]
pivot = L/2
if Nums[pivot] == target:
ans = [pivot, pivot]
left = helper(Nums[:pivot])
if left[0] != -1:
ans[0] = left[0]
right = helper(Nums[pivot+1:])
if right[1] != -1:
ans[1] += (right[1]+1)
return ans
elif Nums[pivot] < target:
ans = helper(Nums[pivot+1:])
if ans != [-1,-1]:
return [x+pivot+1 for x in ans]
return ans
else:
return helper(Nums[:pivot])
return helper(nums)
In [ ]:
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
L_needle = len(needle)
L_haystack = len(haystack)
i = 0
while i+L_needle <= L_haystack:
if haystack[i:i+L_needle] == needle:
return i
i += 1
return -1
In [ ]:
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
L = len(nums)
i = L-2
while i >= 0:
if nums[i+1] > nums[i]:
break
i -= 1
if i < 0:
nums.sort()
return
pivot, j = i+1, i+2
while j < L:
if nums[j] > nums[i] and nums[j] < nums[pivot]:
pivot = j
j += 1
nums[i], nums[pivot] = nums[pivot], nums[i]
for end in xrange(L-1,i,-1):
for start in xrange(i+1, end):
if nums[start] > nums[start+1]:
nums[start], nums[start+1] = nums[start+1], nums[start]
In [ ]:
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if divisor == 0:
return -1
ans, shift = 0, 31
neg = (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0)
a, b = abs(dividend), abs(divisor)
while shift >= 0:
if a >= b << shift:
a -= b << shift
ans += 1 << shift
shift -= 1
if neg:
ans = -ans
if ans > 2147483647:
return 2147483647
elif ans < -2147483648:
return -2147483648
return ans
In [ ]:
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
for i in xrange(len(nums)-1, -1, -1):
if nums[i] == val:
del nums[i]
return len(nums)
In [ ]:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left = 0
L = len(nums)
while left < L:
right = left + 1
while right < L and nums[left] == nums[right]:
right += 1
del nums[left+1:right]
left += 1
L = len(nums)
return len(nums)
In [ ]:
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def helper(node):
if node and node.next:
temp = node.next
node.next = helper(node.next.next)
temp.next = node
return temp
else:
return node
return helper(head)
In [ ]:
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
def helper(l, r, item, res):
if r < l:
return
if r == 0 and l == 0:
res.append(item)
if l > 0:
helper(l-1, r, item+"(", res)
if r > 0:
helper(l, r-1, item+")", res)
res = []
helper(n,n,"", res)
return res
In [ ]:
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
letter = {"0": " ", "1": "*", "2": "abc",
"3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def helper(D):
ans = []
if D == "":
return ans
elif len(D) == 1:
return list(letter[D])
else:
combs = helper(D[1:])
for c in letter[D[0]]:
if combs == []:
ans.append(c)
else:
for comb in combs:
ans.append(c+comb)
return ans
return helper(digits)
In [ ]:
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
L = len(nums)
ans = 0
diff = None
if L < 3:
return ans
# Sorting the array
nums.sort()
last = None
for i in range(L-2):
# Ignore those duplicated computation
if last == nums[i]:
continue
new_target = target - nums[i]
left = i+1
right = L-1
while left < right:
S = nums[left] + nums[right]
if S == new_target:
return target
else:
# Update the difference
temp = abs(S - new_target)
if diff == None or temp < diff:
diff = temp
ans = S + nums[i]
if S < new_target:
left += 1
while left < right and nums[left] == nums[left-1]:
left += 1
else:
right -= 1
while left < right and nums[right] == nums[right+1]:
right -= 1
return ans
In [ ]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
ans = ListNode(0)
pointer = ans
while l1 and l2:
if l2.val > l1.val:
pointer.next = l1
l1 = l1.next
else:
pointer.next = l2
l2 = l2.next
pointer = pointer.next
while l1:
pointer.next = l1
l1 = l1.next
pointer = pointer.next
while l2:
pointer.next = l2
l2 = l2.next
pointer = pointer.next
return ans.next
In [ ]:
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
ans = ""
A = {"}": "{", ")": "(", "]": "["}
for c in s:
if c in "({[":
ans += c
else:
if len(ans) > 0 and ans[-1] == A[c]:
ans = ans[:-1]
else:
return False
return ans == ""
In [ ]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
paths = {}
index = 0
node = head
while node:
paths[index] = node
index += 1
node = node.next
if index - n == 0:
if 1 in paths:
return paths[1]
else:
return []
else:
node = paths[index-n-1]
if index-n+1 in paths:
node.next = paths[index-n+1]
else:
node.next = None
return head
In [ ]:
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = []
L = len(nums)
if L < 4:
return result
nums.sort()
last1 = None
for i in range(L-3):
if nums[i] == last1:
continue
last2 = None
for j in range(i+1, L-2):
if nums[j] == last2:
continue
new_target = target - nums[i] - nums[j]
left = j+1
right = L-1
while left < right:
if nums[left] + nums[right] == new_target:
result.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif nums[left] + nums[right] < new_target:
left += 1
else:
right -= 1
last2 = nums[j]
last1 = nums[i]
return result
In [ ]:
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
L = len(nums)
result = []
if L < 3:
return result
nums.sort()
last = None
for i in range(L-2):
if nums[i] == last:
continue
target = -1 * nums[i]
left = i + 1
right = L - 1
while left < right:
if nums[left] + nums[right] == target:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif nums[left] + nums[right] < target:
left += 1
else:
right -= 1
last = nums[i]
return result
In [ ]:
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) < 1:
return ''
def prefix(s1, s2):
L1 = len(s1)
L2 = len(s2)
if L1 > L2:
s1, s2 = s2, s1
L1, L2 = L2, L1
while s1 != s2[:L1]:
s1 = s1[:-1]
L1 -= 1
return s1
ans = strs[0]
for s in strs[1:]:
ans = prefix(ans, s)
return ans
In [ ]:
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
if s == '':
return 0
MAP = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
result = MAP[s[-1]]
last = s[-1]
for c in s[-2::-1]:
if MAP[c] >= MAP[last]:
result += MAP[c]
else:
result -= MAP[c]
last = c
return result
In [ ]:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l = 0
r = len(height) - 1
ans = 0
while(l < r):
if height[l] > height[r]:
temp = (r -l) * height[r]
r -= 1
else:
temp = (r - l) * height[l]
l += 1
if temp > ans:
ans = temp
return ans
In [ ]:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s == '':
return s
L = len(s)
def expand(c1, c2):
while(c1 >= 0 and c2 <= L-1 and s[c1] == s[c2]):
c1 -= 1
c2 += 1
return s[c1+1:c2]
maxL = 1
ans = s[0]
for i in range(L):
temp = expand(i, i)
if len(temp) > maxL:
maxL = len(temp)
ans = temp
temp = expand(i, i+1)
if len(temp) > maxL:
maxL = len(temp)
ans = temp
return ans
In [ ]:
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
div = 1
while(x/div >= 10):
div *= 10
while(x > 0):
l = x/div
r = x%10
if l != r:
return False
x = x%div/10
div /= 100
return True
In [ ]:
class Solution(object):
def myAtoi(self, s):
"""
:type str: s
:rtype: int
"""
def clean(s):
t = ''
if s:
s = s.strip()
if s[0] in '-+' or s[0].isdigit():
t += s[0]
for c in s[1:]:
if c.isdigit():
t += c
else:
return t
return t
result = 0
sign = 1
s = clean(s)
if s:
if s[0] == '-':
sign = -1
s = s[1:]
s = s[::-1]
for i in range(len(s)):
if s[i].isdigit():
result += int(s[i]) * (10**i)
else:
break
if result > 2147483647 and sign == 1:
result = 2147483647
elif result > 2147483648 and sign == -1:
result = 2147483648
return sign * result
In [ ]:
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if x >= 0:
sign = 1
else:
sign = -1
result = int(str(abs(x))[::-1])
if result > 2147483647:
return 0
else:
return sign * result
In [ ]:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans, start, end = 0, 0, 0
counts = {}
for c in s:
end += 1
counts[c] = counts.get(c, 0) + 1
while counts[c] > 1:
counts[s[start]] -= 1
start += 1
ans = max(ans, end - start)
return ans
In [ ]:
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows <= 1:
return s
n = len(s)
ans = ''
window = 2 * numRows - 2
for i in range(numRows):
flag = i > 0 and i < numRows-1
j = 0
index = i + window * j
while index < n:
ans += s[index]
if flag and index + window - 2*i<n:
ans += s[index + window - 2*i]
j += 1
index = i + window * j
return ans
In [ ]:
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 == None: return l2
if l2 == None: return l1
buffer = 0
ans = ListNode(0)
pos = ans
while l1 and l2:
n1 = l1.val
n2 = l2.val
val = buffer + n1 + n2
buffer = val / 10
val = val % 10
pos.next = ListNode(val)
pos = pos.next
l1 = l1.next
l2 = l2.next
l3 = None
if l1:
l3 = l1
elif l2:
l3 = l2
while l3:
n3 = l3.val
val = buffer + n3
buffer = val / 10
val = val % 10
pos.next = ListNode(val)
pos = pos.next
l3 = l3.next
if buffer > 0:
pos.next = ListNode(buffer)
return ans.next
In [ ]:
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
L = len(nums)
Nums = {}
for i in range(L):
n = target-nums[i]
if n in Nums:
return [Nums[n], i]
else:
Nums[nums[i]] = i
In [ ]:
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
In [ ]:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ones = 0
twos = 0
for n in nums:
twos |= ones&n
ones ^= n
threes = twos & ones
ones &= ~threes
twos &= ~threes
return ones
In [ ]:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for n in nums:
result ^= n
return result
In [ ]:
class Solution(object):
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
count = 0
for c in s.strip()[::-1]:
if c.isalpha():
count += 1
else:
break
return count
In [ ]:
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
result = []
def helper(start=1, end=n-k+1, parent=[], level=k):
last = (level == 1)
for i in range(start, end+1):
if last:
result.append(parent+[i])
else:
helper(i+1, end+1, parent+[i], level-1)
helper()
return result
In [ ]:
class Solution(object):
def findPaths(self, root):
paths = []
def helper(node, path=''):
if node:
path += str(node.val)
if node.left == None and node.right == None:
paths.append(path)
else:
if node.left:
helper(node.left, path)
if node.right:
helper(node.right, path)
helper(root)
return paths
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
result = 0
for path in self.findPaths(root):
result += int(path)
return result
In [ ]:
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
elif root.left:
if root.right:
return min(self.minDepth(root.left), self.minDepth(root.right))+1
else:
return self.minDepth(root.left)+1
elif root.right:
return self.minDepth(root.right)+1
else:
return 1