https://leetcode.com/problems/valid-anagram/
return sorted(s) == sorted(t)
Run time is 96 ms.
Monday, August 31, 2015
Leetcode 241. Different Ways to Add Parentheses
https://leetcode.com/problems/different-ways-to-add-parentheses/
The main thought is to divide two parts when encountering a operator. And to avoid repeated calculation, we establish a lookup table to store calculated result.
Solution:
The main thought is to divide two parts when encountering a operator. And to avoid repeated calculation, we establish a lookup table to store calculated result.
Solution:
# T:O(n * Catalan numbers) S:O(n * Catalan numbers)
class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
lookup = [[None for _ in xrange(len(input) + 1)] for _ in xrange(len(input) + 1)]
ops = {'+': operator.add, '-': operator.sub, '*': operator.mul}
def diffWaysToComputeRecu(left, right):
if lookup[left][right]:
return lookup[left][right]
result = []
for i in xrange(left, right):
if input[i] in ops:
for x in diffWaysToComputeRecu(left, i):
for y in diffWaysToComputeRecu(i + 1, right):
result.append(ops[input[i]](x, y))
if not result:
result = [int(input[left:right])]
lookup[left][right] = result
return lookup[left][right]
return diffWaysToComputeRecu(0, len(input))
Run Time: 60 ms
Sunday, August 30, 2015
Leetcode 240. Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii/
Solution:
Solution:
# T:O(m+n) S:O(1)
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])
i, j = 0, n - 1
while i < m and j > -1:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else: i += 1
return False
Run Time: 128 ms
Leetcode 239. Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum/
The hard point is to achieve O(n) time. Actually we can smell a sense of queue here. Python has a quite powerful deque data structure, and we can use that. Still using max() is too slow, we should link the whole process.
Solution:
The hard point is to achieve O(n) time. Actually we can smell a sense of queue here. Python has a quite powerful deque data structure, and we can use that. Still using max() is too slow, we should link the whole process.
Solution:
# T:O(n) S:O(k)
from collections import deque
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer[]}
def maxSlidingWindow(self, nums, k):
q = deque()
max_numbers = []
for i in xrange(k):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
for i in xrange(k, len(nums)):
max_numbers.append(nums[q[0]])
while q and nums[i] >= nums[q[-1]]:
q.pop()
while q and q[0] <= i - k:
q.popleft()
q.append(i)
if q:
max_numbers.append(nums[q[0]])
return max_numbers
Run Time: 208 ms
Leetcode 238. Product of Array Except Self
https://leetcode.com/problems/product-of-array-except-self/
Because division is not allowed, so we should use multiplying only. The thought is to scan twice, first multiply left side, second multiply right.
Solution:
Because division is not allowed, so we should use multiplying only. The thought is to scan twice, first multiply left side, second multiply right.
Solution:
# T:O(n) S:O(1)
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums: return []
left_product = [1 for _ in xrange(len(nums))]
for i in xrange(1, len(nums)):
left_product[i] = left_product[i - 1] * nums[i - 1]
right_product = 1
for i in xrange(len(nums) - 2, -1, -1):
right_product *= nums[i + 1]
left_product[i] = left_product[i] * right_product
return left_product
Run Time: 180 ms
Leetcode 237. Delete Node in a Linked List
https://leetcode.com/problems/delete-node-in-a-linked-list/
Very basic operation.
node.val = node.next.val
node.next = node.next.next
Run time is 68 ms.
Very basic operation.
node.val = node.next.val
node.next = node.next.next
Run time is 68 ms.
Leetcode 236. Lowest Common Ancestor of a Binary Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
The elegant solution is using recursion. If p and q are in left and right, this is the node; or it will be in the subtree that has p and q.
Solution:
The elegant solution is using recursion. If p and q are in left and right, this is the node; or it will be in the subtree that has p and q.
Solution:
# T:O(h) S:O(h)
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root in (None, p, q):
return root
left, right = [self.lowestCommonAncestor(child, p, q) \
for child in (root.left, root.right)]
# 1. If the current subtree contains both p and q,
# return their LCA.
# 2. If only one of them is in that subtree,
# return that one of them.
# 3. If neither of them is in that subtree,
# return the node of that subtree.
return root if left and right else left or right
Run Time: 156 ms
Leetcode 235. Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Because BST is a knid of binary tree, so if we use the result of binary tree, it is also correct but not that fast.
If we use BST's feature, the thing is clear: when the three nodes are on the same tree, there should be
s <= root.val <= b. If not, the two nodes must be on left or right subtree, then use the value to decide go left or right.
Solution:
Because BST is a knid of binary tree, so if we use the result of binary tree, it is also correct but not that fast.
If we use BST's feature, the thing is clear: when the three nodes are on the same tree, there should be
s <= root.val <= b. If not, the two nodes must be on left or right subtree, then use the value to decide go left or right.
Solution:
# T:O(n) S:O(1)
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
s, b = sorted([p.val, q.val])
while not s <= root.val <= b:
# Keep searching since root is outside of [s, b].
root = root.left if s <= root.val else root.right
# s <= root.val <= b.
return root
Run Time: 132 ms
Leetcode 234. Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/
The task is easy, while O(1) space needs some thinking. We can get the length, then how to check? Because there is no way back in single linked list, we should reverse the first or last half and then do the check. Restoring the list is optional.
Solution:
The task is easy, while O(1) space needs some thinking. We can get the length, then how to check? Because there is no way back in single linked list, we should reverse the first or last half and then do the check. Restoring the list is optional.
Solution:
# T:O(n) S:O(1)
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
reverse, fast = None, head
while fast and fast.next:
fast = fast.next.next
head.next, reverse, head = reverse, head, head.next
# If the number of the nodes is odd,
# set the head of the tail list to the next of the median node.
tail = head.next if fast else head
# Compare the reversed first half list with the second half list.
# And restore the reversed first half list.
is_palindrome = True
while reverse:
is_palindrome = is_palindrome and reverse.val == tail.val
reverse.next, head, reverse = head, reverse, reverse.next
tail = tail.next
return is_palindrome
Run Time: 136 ms
Leetcode 233. Number of Digit One
https://leetcode.com/problems/number-of-digit-one/
The key point is to get the law.
Solution:
The key point is to get the law.
Solution:
# T:O(lgn) S:O(1)
class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
left = right = len = 1
if n <= 0: return 0
while n >= len:
left = n / len
right = n % len
if left % 10 >= 2:
res += (left / 10 + 1) * len
elif left % 10 == 1:
res += (left / 10) * len + (right + 1)
else: res += (left / 10) * len
len *= 10
return res
Run Time: 44 ms
Leetcode 232. Implement Queue using Stacks
https://leetcode.com/problems/implement-queue-using-stacks/
Solution:
Solution:
# T:O(1) S:O(n)
class Queue:
# initialize your data structure here.
def __init__(self):
self.A, self.B = [], []
# @param x, an integer
# @return nothing
def push(self, x):
self.A.append(x)
# @return nothing
def pop(self):
self.peek()
self.B.pop()
# @return an integer
def peek(self):
if not self.B:
while self.A:
self.B.append(self.A.pop())
return self.B[-1]
# @return an boolean
def empty(self):
return not self.A and not self.B
Run Time: 40 ms
Leetcode 231. Power of Two
https://leetcode.com/problems/power-of-two/
2 one line solutions.
Solution 1:
return bin(n)[2:].count('1') == 1 and n > 0
Run time 64 ms;
Solution 2:
return n > 0 and (n & (n - 1)) == 0
Run time: 60 ms.
2 one line solutions.
Solution 1:
return bin(n)[2:].count('1') == 1 and n > 0
Run time 64 ms;
Solution 2:
return n > 0 and (n & (n - 1)) == 0
Run time: 60 ms.
Leetcode 230. Kth Smallest Element in a BST
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
We know that for a BST, left < root < right. So if we go left to the end, this is the smallest node, its root is the 2nd, and its root's right is the 3rd. In this way, we can get the kth smallest node. In order to go back, we need a stack.
Solution:
We know that for a BST, left < root < right. So if we go left to the end, this is the smallest node, its root is the 2nd, and its root's right is the 3rd. In this way, we can get the kth smallest node. In order to go back, we need a stack.
Solution:
# T:O(max(h,k)) S:O(h)
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
s, cur, rank = [], root, 0
while s or cur:
if cur:
s.append(cur)
cur = cur.left
else:
cur = s.pop()
rank += 1
if rank == k:
return cur.val
cur = cur.right
return float("-inf")
Run Time: 80 ms
Leetcode 229. Majority Element II
https://leetcode.com/problems/majority-element-ii/
Remember Majority Element one? In that problem, only one number can occur over n/2 times, and we solve it by +1 when it occurs and -1 when others occur, when count value equals 0 we change to the next number and set count 1, so in the end the current number is what we want.
So can we use the same thought here? For n/3, there will be at most two such numbers. Hence we can play the exactly same trick again, while this time there are two numbers.
Solution:
Remember Majority Element one? In that problem, only one number can occur over n/2 times, and we solve it by +1 when it occurs and -1 when others occur, when count value equals 0 we change to the next number and set count 1, so in the end the current number is what we want.
So can we use the same thought here? For n/3, there will be at most two such numbers. Hence we can play the exactly same trick again, while this time there are two numbers.
Solution:
# T:O(n) S:O(1)
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n1 = n2 = None
c1 = c2 = 0
for num in nums:
if n1 == num:
c1 += 1
elif n2 == num:
c2 += 1
elif c1 == 0:
n1, c1 = num, 1
elif c2 == 0:
n2, c2 = num, 1
else:
c1, c2 = c1 - 1, c2 - 1
size = len(nums)
return [n for n in (n1, n2)
if n is not None and nums.count(n) > size / 3]
Run Time: 64 ms
Leetcode 228. Summary Ranges
https://leetcode.com/problems/summary-ranges/
Solution:
Solution:
# T:O(n) S:O(n)
class Solution(object):
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
if not nums: return []
i, ret = 0, []
while i < len(nums):
start = i
while i < len(nums) - 1 and nums[i] == nums[i+1] - 1:
i += 1
end = i
if start == end:
ret.append(str(nums[i]))
else:
ret.append(str(nums[start])+"->"+str(nums[end]))
i += 1
return ret
Run Time: 56 ms
Leetcode 227. Basic Calculator II
https://leetcode.com/problems/basic-calculator-ii/
When there are '*' and '/', priority should be concerned.
Solution:
When there are '*' and '/', priority should be concerned.
Solution:
# T:O(n) S:O(n)
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
operands, operators = [], []
operand = ""
for i in reversed(xrange(len(s))):
if s[i].isdigit():
operand += s[i]
if i == 0 or not s[i-1].isdigit():
operands.append(int(operand[::-1]))
operand = ""
elif s[i] == ')' or s[i] == '*' or s[i] == '/':
operators.append(s[i])
elif s[i] == '+' or s[i] == '-':
while operators and \
(operators[-1] == '*' or operators[-1] == '/'):
self.compute(operands, operators)
operators.append(s[i])
elif s[i] == '(':
while operators[-1] != ')':
self.compute(operands, operators)
operators.pop()
while operators:
self.compute(operands, operators)
return operands[-1]
def compute(self, operands, operators):
left, right = operands.pop(), operands.pop()
op = operators.pop()
if op == '+':
operands.append(left + right)
elif op == '-':
operands.append(left - right)
elif op == '*':
operands.append(left * right)
elif op == '/':
operands.append(left / right)
Run Time: 420 ms
Leetcode 226. Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree/
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Solution:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Solution:
# T:O(n) S:O(h)
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root: return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
Run Time: 40 ms
Saturday, August 29, 2015
Leetcode 225. Implement Stack using Queues
https://leetcode.com/problems/implement-stack-using-queues/
Solution:
Solution:
# T:push: O(n), pop: O(1), top: O(1) S:O(n)
class Queue:
def __init__(self):
self.data = collections.deque()
def push(self, x):
self.data.append(x)
def peek(self):
return self.data[0]
def pop(self):
return self.data.popleft()
def size(self):
return len(self.data)
def empty(self):
return len(self.data) == 0
class Stack:
# initialize your data structure here.
def __init__(self):
self.q_ = Queue()
# @param x, an integer
# @return nothing
def push(self, x):
self.q_.push(x)
for _ in xrange(self.q_.size() - 1):
self.q_.push(self.q_.pop())
# @return nothing
def pop(self):
self.q_.pop()
# @return an integer
def top(self):
return self.q_.peek()
# @return an boolean
def empty(self):
return self.q_.empty()
Run Time: 40 ms
Leetcode 224. Basic Calculator
https://leetcode.com/problems/basic-calculator/
For problems concerning sequence, stack is a good choice. Here we can build two stacks, one for operators, one for operands. Note the numbers might be greater than 9, so converting string to integer needs more attention.
Another problem is the process direction. For instance, 2-1+2=3, but if we use stack from left to right, N=[2,1,2], S=[-,+], we cannot use pop because in that way it would be 2-2+1=-1, so we have to reverse both N and S. Therefore we could reverse s and use pop operation.
Solution:
For problems concerning sequence, stack is a good choice. Here we can build two stacks, one for operators, one for operands. Note the numbers might be greater than 9, so converting string to integer needs more attention.
Another problem is the process direction. For instance, 2-1+2=3, but if we use stack from left to right, N=[2,1,2], S=[-,+], we cannot use pop because in that way it would be 2-2+1=-1, so we have to reverse both N and S. Therefore we could reverse s and use pop operation.
Solution:
# T:O(n) S:O(n)
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
operands, operators = [], []
operand = ""
for i in reversed(xrange(len(s))):
if s[i].isdigit():
operand += s[i]
if i == 0 or not s[i-1].isdigit():
operands.append(int(operand[::-1]))
operand = ""
elif s[i] == ')' or s[i] == '+' or s[i] == '-':
operators.append(s[i])
elif s[i] == '(':
while operators[-1] != ')':
self.compute(operands, operators)
operators.pop()
while operators:
self.compute(operands, operators)
return operands[-1]
def compute(self, operands, operators):
left, right = operands.pop(), operands.pop()
op = operators.pop()
if op == '+':
operands.append(left + right)
elif op == '-':
operands.append(left - right)
Run Time: 392 ms
Leetcode 223. Rectangle Area
https://leetcode.com/problems/rectangle-area/
The thought is simple: two areas of rectangles subtract overlapping area. The key is to get the overlapping area.
Solution:
The thought is simple: two areas of rectangles subtract overlapping area. The key is to get the overlapping area.
Solution:
# T:O(1) S:O(1)
class Solution(object):
def computeArea(self, A, B, C, D, E, F, G, H):
"""
:type A: int
:type B: int
:type C: int
:type D: int
:type E: int
:type F: int
:type G: int
:type H: int
:rtype: int
"""
return (D - B) * (C - A) + \
(G - E) * (H - F) - \
max(0, (min(C, G) - max(A, E))) * \
max(0, (min(D, H) - max(B, F)))
Run Time: 148 ms
Leetcode 222. Count Complete Tree Nodes
https://leetcode.com/problems/count-complete-tree-nodes/
If use recursion ignoring the feature of completed binary tree, the run time will get TLE.
First we should get the level of this tree. Because the left node will be there first, we can go along the left and gain the level. Then we must decide how many nodes are in this level. This is not very easy, and we can use binary search to find the most right node.
Solution:
If use recursion ignoring the feature of completed binary tree, the run time will get TLE.
First we should get the level of this tree. Because the left node will be there first, we can go along the left and gain the level. Then we must decide how many nodes are in this level. This is not very easy, and we can use binary search to find the most right node.
Solution:
# T:O((logn)^2) S:O(1)
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None: return 0
node, level = root, 0
while node.left is not None:
node = node.left
level += 1
# Binary search.
left, right = 2 ** level, 2 ** (level + 1)
while left < right:
mid = left + (right - left) / 2
if not self.exist(root, mid):
right = mid
else:
left = mid + 1
return left - 1
# Check if the nth node exist.
def exist(self, root, n):
k = 1
while k <= n:
k <<= 1
k >>= 2
node = root
while k > 0:
if (n & k) == 0:
node = node.left
else:
node = node.right
k >>= 1
return node is not None
Run Time: 188 ms
Leetcode 221. Maximal Square
https://leetcode.com/problems/maximal-square/
DP with sliding window.
Solution:
DP with sliding window.
Solution:
# T:O(n^2) S:O(n)
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
size = [[0 for j in xrange(n)] for i in xrange(2)]
max_size = 0
for j in xrange(n):
if matrix[0][j] == '1':
size[0][j] = 1
max_size = max(max_size, size[0][j])
for i in xrange(1, m):
if matrix[i][0] == '1':
size[i % 2][0] = 1
else:
size[i % 2][0] = 0
for j in xrange(1, n):
if matrix[i][j] == '1':
size[i % 2][j] = min(size[i % 2][j - 1], \
size[(i - 1) % 2][j], \
size[(i - 1) % 2][j - 1]) + 1
max_size = max(max_size, size[i % 2][j])
else:
size[i % 2][j] = 0
return max_size * max_size
Run Time: 136 ms
Leetcode 220. Contains Duplicate III
https://leetcode.com/problems/contains-duplicate-iii/
Window and bucket!
if： | nums[i] - nums[j] | <= t
namely： | nums[i] / t - nums[j] / t | <= 1
then： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1
therefore： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}
Solution:
Window and bucket!
if： | nums[i] - nums[j] | <= t
namely： | nums[i] / t - nums[j] / t | <= 1
then： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1
therefore： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}
Solution:
# T:O(n*t) S:O(max(k,t))
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @param {integer} t
# @return {boolean}
def containsNearbyAlmostDuplicate(self, nums, k, t):
if k < 0 or t < 0:
return False
window = collections.OrderedDict()
for n in nums:
# Make sure window size
if len(window) > k:
window.popitem(False)
bucket = n if not t else n // t
# At most 2t items.
for m in (window.get(bucket - 1), window.get(bucket), window.get(bucket + 1)):
if m is not None and abs(n - m) <= t:
return True
window[bucket] = n
return False
Run Time: 144 ms
Leetcode 219. Contains Duplicate II
https://leetcode.com/problems/contains-duplicate-ii/
Solution:
Solution:
# T:O(n) S:O(n)
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {boolean}
def containsNearbyDuplicate(self, nums, k):
if k >= len(nums) - 1:
return len(nums) > len(set(nums))
for i in xrange(k, len(nums)):
tmp = nums[i-k:i+1]
if len(tmp) > len(set(tmp)):
return True
else:
return False
Run Time: 60 ms
Leetcode 218. The Skyline Problem
https://leetcode.com/problems/the-skyline-problem/
This problem is indeed not very easy, while the key point is to keep efficient and care about many cases.
Solution:
This problem is indeed not very easy, while the key point is to keep efficient and care about many cases.
Solution:
# T:O(nlgn) S:O(n)
# Divide and conquer solution.
start, end, height = 0, 1, 2
class Solution:
# @param {integer[][]} buildings
# @return {integer[][]}
def getSkyline(self, buildings):
intervals = self.ComputeSkylineInInterval(buildings, 0, len(buildings))
res = []
last_end = -1
for interval in intervals:
if last_end != -1 and last_end < interval[start]:
res.append([last_end, 0])
res.append([interval[start], interval[height]])
last_end = interval[end]
if last_end != -1:
res.append([last_end, 0])
return res
# Divide and Conquer.
def ComputeSkylineInInterval(self, buildings, left_endpoint, right_endpoint):
if right_endpoint - left_endpoint <= 1:
return buildings[left_endpoint:right_endpoint]
mid = left_endpoint + ((right_endpoint - left_endpoint) / 2)
left_skyline = self.ComputeSkylineInInterval(buildings, left_endpoint, mid)
right_skyline = self.ComputeSkylineInInterval(buildings, mid, right_endpoint)
return self.MergeSkylines(left_skyline, right_skyline)
# Merge Sort.
def MergeSkylines(self, left_skyline, right_skyline):
i, j = 0, 0
merged = []
while i < len(left_skyline) and j < len(right_skyline):
if left_skyline[i][end] < right_skyline[j][start]:
merged.append(left_skyline[i])
i += 1
elif right_skyline[j][end] < left_skyline[i][start]:
merged.append(right_skyline[j])
j += 1
elif left_skyline[i][start] <= right_skyline[j][start]:
i, j = self.MergeIntersectSkylines(merged, left_skyline[i], i,\
right_skyline[j], j)
else: # left_skyline[i][start] > right_skyline[j][start].
j, i = self.MergeIntersectSkylines(merged, right_skyline[j], j, \
left_skyline[i], i)
# Insert the remaining skylines.
merged += left_skyline[i:]
merged += right_skyline[j:]
return merged
# a[start] <= b[start]
def MergeIntersectSkylines(self, merged, a, a_idx, b, b_idx):
if a[end] <= b[end]:
if a[height] > b[height]: # |aaa|
if b[end] != a[end]: # |abb|b
b[start] = a[end]
merged.append(a)
a_idx += 1
else: # aaa
b_idx += 1 # abb
elif a[height] == b[height]: # abb
b[start] = a[start] # abb
a_idx += 1
else: # a[height] < b[height].
if a[start] != b[start]: # bb
merged.append([a[start], b[start], a[height]]) # |a|bb
a_idx += 1
else: # a[end] > b[end].
if a[height] >= b[height]: # aaaa
b_idx += 1 # abba
else:
# |bb|
# |a||bb|a
if a[start] != b[start]:
merged.append([a[start], b[start], a[height]])
a[start] = b[end]
merged.append(b)
b_idx += 1
return a_idx, b_idx
Run Time: 148 ms
Leetcode 217. Contains Duplicate
https://leetcode.com/problems/contains-duplicate/
We can use set in Python, which has the feature of getting rid of duplicate automatically.
Solution:
We can use set in Python, which has the feature of getting rid of duplicate automatically.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param {integer[]} nums
# @return {boolean}
def containsDuplicate(self, nums):
return len(nums) > len(set(nums))
Run Time: 80 ms
Leetcode 216. Combination Sum III
https://leetcode.com/problems/combination-sum-iii/
Nothing but DFS.
Solution:
Nothing but DFS.
Solution:
# T:O(k*C(n,k)) S:O(k)
class Solution:
# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
result = []
self.combinationSumRecu(result, [], 1, k, n)
return result
def combinationSumRecu(self, result, intermediate, start, k, target):
if k == 0 and target == 0:
result.append(list(intermediate))
elif k < 0:
return
while start < 10 and start * k + k * (k - 1) / 2 <= target:
intermediate.append(start)
self.combinationSumRecu(result, intermediate, start + 1, k - 1, target - start)
intermediate.pop()
start += 1
Run Time: 44 ms
Thursday, August 27, 2015
Leetcode 215. Kth Largest Element in an Array
https://leetcode.com/problems/kth-largest-element-in-an-array/
The plain thought is to sort, and then give the kth element. Run time of this method is 48 ms. This way is simple and easy. Other ways can achieve better performance while much more complex.
Solution:
The plain thought is to sort, and then give the kth element. Run time of this method is 48 ms. This way is simple and easy. Other ways can achieve better performance while much more complex.
Solution:
# T:O(n) S:O(1)
from random import randint
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(self, nums, k):
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = randint(left, right)
new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums)
if new_pivot_idx == k - 1:
return nums[new_pivot_idx]
elif new_pivot_idx > k - 1:
right = new_pivot_idx - 1
else: # new_pivot_idx < k - 1.
left = new_pivot_idx + 1
def PartitionAroundPivot(self, left, right, pivot_idx, nums):
pivot_value = nums[pivot_idx]
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in xrange(left, right):
if nums[i] > pivot_value:
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1
nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx
Run Time: 64 ms
Leetcode 214. Shortest Palindrome
https://leetcode.com/problems/shortest-palindrome/
Using KMP algorithm.
Solution:
Using KMP algorithm.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param {string} s
# @return {string}
def shortestPalindrome(self, s):
if not s:
return s
A = s + s[::-1]
prefix = self.getPrefix(A)
i = prefix[-1]
while i >= len(s):
i = prefix[i]
return s[i+1:][::-1] + s
def getPrefix(self, pattern):
prefix = [-1] * len(pattern)
j = -1
for i in xrange(1, len(pattern)):
while j > -1 and pattern[j+1] != pattern[i]:
j = prefix[j]
if pattern[j+1] == pattern[i]:
j += 1
prefix[i] = j
return prefix
Run Time: 96 ms
Leetcode 213. House Robber II
https://leetcode.com/problems/house-robber-ii/
The majority part is still the same. Actually the difference is clear: if we rob first house, we cannot rob the last house.
Solution:
The majority part is still the same. Actually the difference is clear: if we rob first house, we cannot rob the last house.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param {integer[]} nums
# @return {integer}
def rob(self, nums):
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
return max(self.robRange(nums, 0, len(nums) - 1),\
self.robRange(nums, 1, len(nums)))
def robRange(self, nums, start, end):
num_i, num_i_1 = nums[start], 0
for i in xrange(start + 1, end):
num_i_1, num_i_2 = num_i, num_i_1
num_i = max(nums[i] + num_i_2, num_i_1);
return num_i
Run Time: 36 ms
Leetcode 212. Word Search II
https://leetcode.com/problems/word-search-ii/
We can use trie to make the problem simple.
Solution:
We can use trie to make the problem simple.
Solution:
# T:O(m*n) S:O(1)
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.is_string = False
self.leaves = {}
# Inserts a word into the trie.
def insert(self, word):
cur = self
for c in word:
if not c in cur.leaves:
cur.leaves[c] = TrieNode()
cur = cur.leaves[c]
cur.is_string = True
class Solution:
# @param {character[][]} board
# @param {string[]} words
# @return {string[]}
def findWords(self, board, words):
visited = [[False for j in xrange(len(board[0]))] for i in xrange(len(board))]
result = {}
trie = TrieNode()
for word in words:
trie.insert(word)
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if self.findWordsRecu(board, trie, 0, i, j, visited, [], result):
return True
return result.keys()
def findWordsRecu(self, board, trie, cur, i, j, visited, cur_word, result):
if not trie or i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:
return
if board[i][j] not in trie.leaves:
return
cur_word.append(board[i][j])
next_node = trie.leaves[board[i][j]]
if next_node.is_string:
result["".join(cur_word)] = True
visited[i][j] = True
self.findWordsRecu(board, next_node, cur + 1, i + 1, j, visited, cur_word, result)
self.findWordsRecu(board, next_node, cur + 1, i - 1, j, visited, cur_word, result)
self.findWordsRecu(board, next_node, cur + 1, i, j + 1, visited, cur_word, result)
self.findWordsRecu(board, next_node, cur + 1, i, j - 1, visited, cur_word, result)
visited[i][j] = False
cur_word.pop()
Run Time: 840 ms
Leetcode 211. Add and Search Word - Data structure design
https://leetcode.com/problems/add-and-search-word-data-structure-design/
Actually we can do it using the trie data structure that we designed before.
Solution:
Actually we can do it using the trie data structure that we designed before.
Solution:
# T:O(min(n, h)) S:O(min(n, h))
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.is_string = False
self.leaves = {}
class WordDictionary:
def __init__(self):
self.root = TrieNode()
# @param {string} word
# @return {void}
# Adds a word into the data structure.
def addWord(self, word):
curr = self.root
for c in word:
if not c in curr.leaves:
curr.leaves[c] = TrieNode()
curr = curr.leaves[c]
curr.is_string = True
# @param {string} word
# @return {boolean}
# Returns if the word is in the data structure. A word could
# contain the dot character '.' to represent any one letter.
def search(self, word):
return self.searchHelper(word, 0, self.root)
def searchHelper(self, word, start, curr):
if start == len(word):
return curr.is_string
if word[start] in curr.leaves:
return self.searchHelper(word, start+1, curr.leaves[word[start]])
elif word[start] == '.':
for c in curr.leaves:
if self.searchHelper(word, start+1, curr.leaves[c]):
return True
return False
Run Time: 568 ms
Leetcode 210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/
Very similar with problem 207.
Solution:
Very similar with problem 207.
Solution:
# T:O(|V|+|E|) S:O(|E|)
class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {integer[]}
def findOrder(self, numCourses, prerequisites):
res, zero_in_degree_queue, in_degree, out_degree =\
[], collections.deque(), {}, {}
for i, j in prerequisites:
if i not in in_degree:
in_degree[i] = sets.Set()
if j not in out_degree:
out_degree[j] = sets.Set()
in_degree[i].add(j)
out_degree[j].add(i)
for i in xrange(numCourses):
if i not in in_degree:
zero_in_degree_queue.append(i)
while zero_in_degree_queue:
prerequisite = zero_in_degree_queue.popleft()
res.append(prerequisite)
if prerequisite in out_degree:
for course in out_degree[prerequisite]:
in_degree[course].discard(prerequisite)
if not in_degree[course]:
zero_in_degree_queue.append(course)
del out_degree[prerequisite]
if out_degree:
return []
return res
Run Time: 112 ms
Leetcode 209. Minimum Size Subarray Sum
https://leetcode.com/problems/minimum-size-subarray-sum/
Rolling window method.
Solution:
Rolling window method.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param {integer} s
# @param {integer[]} nums
# @return {integer}
def minSubArrayLen(self, s, nums):
start, sum, mid_len = 0, 0, float("inf")
for i in xrange(len(nums)):
sum += nums[i]
while sum >= s:
min_len = min(min_len, i - start + 1)
sum -= nums[start]
start += 1
if min_len == float("inf"):
return 0
return min_len
Run Time: 88 ms
Leetcode 208. Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/
Solution:
Solution:
# T:O(n) S:O(1)
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.is_string = False
self.leaves = {}
class Trie:
def __init__(self):
self.root = TrieNode()
# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
cur = self.root
for c in word:
if not c in cur.leaves:
cur.leaves[c] = TrieNode()
cur = cur.leaves[c]
cur.is_string = True
# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
res, node = self.childSearch(word)
if res:
return node.is_string
return False
# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
return self.childSearch(prefix)[0]
def childSearch(self, word):
cur = self.root
for c in word:
if c in cur.leaves:
cur = cur.leaves[c]
else:
return False, None
return True, cur
Run Time: 348 ms
Tuesday, August 25, 2015
Leetcode 207. Course Schedule
https://leetcode.com/problems/course-schedule/
We can do it using graph.
Solution:
We can do it using graph.
Solution:
# T:O(|V|+|E|) S:O(|E|)
class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {boolean}
def canFinish(self, numCourses, prerequisites):
zero_in_degree_queue, in_degree, out_degree = collections.deque(), {}, {}
for i, j in prerequisites:
if i not in in_degree:
in_degree[i] = sets.Set()
if j not in out_degree:
out_degree[j] = sets.Set()
in_degree[i].add(j)
out_degree[j].add(i)
for i in xrange(numCourses):
if i not in in_degree:
zero_in_degree_queue.append(i)
while zero_in_degree_queue:
prerequisite = zero_in_degree_queue.popleft()
if prerequisite in out_degree:
for course in out_degree[prerequisite]:
in_degree[course].discard(prerequisite)
if not in_degree[course]:
zero_in_degree_queue.append(course)
del out_degree[prerequisite]
if out_degree:
return False
return True
Run Time: 108 ms
Leetcode 206. Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
Solution:
Solution:
# T:O(n) S:O(1)
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
dummy = ListNode(float("-inf"))
while head:
dummy.next, head.next, head = head, dummy.next, head.next
return dummy.next
Run Time: 60 ms
Leetcode 205. Isomorphic Strings
https://leetcode.com/problems/isomorphic-strings/
This is a thing of mapping. On each occurrence, record the mapping. If one char maps to two chars, False; or two chars map to the same char, False.
Solution:
This is a thing of mapping. On each occurrence, record the mapping. If one char maps to two chars, False; or two chars map to the same char, False.
Solution:
# T:O(n) S:O(1) At most 26 mappings
class Solution:
# @param {string} s
# @param {string} t
# @return {boolean}
def isIsomorphic(self, s, t):
length, dict = len(s), {}
for i in xrange(length):
if s[i] not in dict:
if t[i] in dict.values():
return False
dict[s[i]] = t[i]
else:
if dict[s[i]] != t[i]:
return False
return True
Run Time: 64 ms
Leetcode 204. Count Primes
https://leetcode.com/problems/count-primes/
Brute force is not acceptable. The solution is really smart, while there are still spaces to improve.
Solution:
Brute force is not acceptable. The solution is really smart, while there are still spaces to improve.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
if n <= 2:
return 0
is_prime = [True] * n
num = 0
for i in xrange(2, n):
if is_prime[i]:
num += 1
for j in xrange(i+i, n, i):
is_prime[j] = False
return num
Run Time: 804 ms
Leetcode 203. Remove Linked List Elements
https://leetcode.com/problems/remove-linked-list-elements/
Solution:
Solution:
# T:O(n) S:O(1)
class Solution:
# @param {ListNode} head
# @param {integer} val
# @return {ListNode}
def removeElements(self, head, val):
dummy = ListNode(float("-inf"))
dummy.next = head
prev, curr = dummy, dummy.next
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next
Run Time: 128 ms
Leetcode 202. Happy Number
https://leetcode.com/problems/happy-number/
Easy problem. Just use some recursion.
Solution:
Easy problem. Just use some recursion.
Solution:
# T:O(k) S:O(k)
class Solution:
# @param {integer} n
# @return {boolean}
def perform(self, n):
ret = 0
while n:
ret += (n%10)**2
n /= 10
return ret
def isHappy(self, n):
lst = []
while True:
if self.perform(n) == 1:
return True
if n not in lst:
lst.append(n)
n = self.perform(n)
if n in lst:
return False
Run Time: 48 ms
Leetcode 201. Bitwise AND of Numbers Range
https://leetcode.com/problems/bitwise-and-of-numbers-range/
Bit operation. The key is to find common part from left side.
Solution:
Bit operation. The key is to find common part from left side.
Solution:
# T:O(1) S:O(1)
class Solution:
# @param m, an integer
# @param n, an integer
# @return an integer
def rangeBitwiseAnd(self, m, n):
i, diff = 0, n-m
while diff:
diff >>= 1
i += 1
return n&m >> i << i
Run Time: 196 ms
Leetcode 200. Number of Islands
https://leetcode.com/problems/number-of-islands/
The thought is to search for four directions. Note not to search repeatedly.
Solution:
The thought is to search for four directions. Note not to search repeatedly.
Solution:
# T:O(m*n) S:O(m*n)
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def numIslands(self, grid):
if not grid:
return 0
row = len(grid)
col = len(grid[0])
used = [[False for j in xrange(col)] for i in xrange(row)]
count = 0
for i in xrange(row):
for j in xrange(col):
if grid[i][j] == '1' and not used[i][j]:
self.dfs(grid, used, row, col, i, j)
count += 1
return count
def dfs(self, grid, used, row, col, x, y):
if grid[x][y] == '0' or used[x][y]:
return
used[x][y] = True
if x != 0:
self.dfs(grid, used, row, col, x - 1, y)
if x != row - 1:
self.dfs(grid, used, row, col, x + 1, y)
if y != 0:
self.dfs(grid, used, row, col, x, y - 1)
if y != col - 1:
self.dfs(grid, used, row, col, x, y + 1)
Run Time: 136 ms
Leetcode 199. Binary Tree Right Side View
https://leetcode.com/problems/binary-tree-right-side-view/
The lazy way is to get level order and use the right most element, while it is wasteful. We can do better than that. The key is to put right nodes in if exist.
Solution:
The lazy way is to get level order and use the right most element, while it is wasteful. We can do better than that. The key is to put right nodes in if exist.
Solution:
# T:O(n) S:O(h)
class Solution:
# @param root, a tree node
# @return a list of integers
def rightSideView(self, root):
result = []
self.rightSideViewDFS(root, 1, result)
return result
def rightSideViewDFS(self, node, depth, result):
if not node:
return
if depth > len(result):
result.append(node.val)
self.rightSideViewDFS(node.right, depth+1, result)
self.rightSideViewDFS(node.left, depth+1, result)
Run Time: 60 ms
Leetcode 198. House Robber
https://leetcode.com/problems/house-robber/
Using DP. The key is to get the right formula.
Solution:
Using DP. The key is to get the right formula.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param num, a list of integer
# @return an integer
def rob(self, num):
if len(num) == 0:
return 0
if len(num) == 1:
return num[0]
num_i, num_i_1 = max(num[1], num[0]), num[0]
for i in xrange(2, len(num)):
num_i_1, num_i_2 = num_i, num_i_1
num_i = max(num[i] + num_i_2, num_i_1);
return num_i
Run Time: 36 ms
Leetcode 191. Number of 1 Bits
https://leetcode.com/problems/number-of-1-bits/
Two solutions.
Solution 1:
Solution 2:
Two solutions.
Solution 1:
# T:O(m) S:O(1)
class Solution:
# @param n, an integer
# @return an integer
def hammingWeight(self, n):
result = 0
while n:
n &= n - 1
result += 1
return result
Run Time: 56 msSolution 2:
# T:O(m) S:O(m)
class Solution:
# @param n, an integer
# @return an integer
def hammingWeight(self, n):
s = bin(n)[2:]
cnt = 0
for ch in s:
if ch == '1':
cnt += 1
return cnt
Run Time: 48 msLeetcode 190. Reverse Bits
https://leetcode.com/problems/reverse-bits/
Two solutions. String one and bit operation one.
Solution 1:
Solution 2:
Two solutions. String one and bit operation one.
Solution 1:
# T:O(n) S:O(1)
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
s = bin(n)
s = s[2:]
length = len(s)
zeros = 32 - len(s)
s = '0'*zeros + s
s = s[::-1]
return int(s,2)
Run Time: 56 msSolution 2:
# T:O(n) S:O(1)
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
result = 0
for i in xrange(32):
result <<= 1
result |= n & 1
n >>= 1
return result
Run Time: 60 ms
Leetcode 189. Rotate Array
https://leetcode.com/problems/rotate-array/
Many ways to solve it.
Solution:
Many ways to solve it.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
k %= len(nums)
self.reverse(nums, 0, len(nums))
self.reverse(nums, 0, k)
self.reverse(nums, k, len(nums))
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end-1] = nums[end-1], nums[start]
start += 1
end -= 1
Run Time: 88 ms
Leetcode 188. Best Time to Buy and Sell Stock IV
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
Here comes the boss. DP for sure. If k is large enough, the whole prices can be covered, which is similar with ii; otherwise the solution is the same principle with iii.
Solution:
Here comes the boss. DP for sure. If k is large enough, the whole prices can be covered, which is similar with ii; otherwise the solution is the same principle with iii.
Solution:
# T:O(k*n) S:O(k)
class Solution:
# @return an integer as the maximum profit
def maxProfit(self, k, prices):
if k >= len(prices) / 2:
return self.maxAtMostNPairsProfit(prices)
return self.maxAtMostKPairsProfit(prices, k)
def maxAtMostNPairsProfit(self, prices):
profit = 0
for i in xrange(len(prices) - 1):
profit += max(0, prices[i + 1] - prices[i])
return profit
def maxAtMostKPairsProfit(self, prices, k):
max_buy = [float("-inf") for _ in xrange(k + 1)]
max_sell = [0 for _ in xrange(k + 1)]
for i in xrange(len(prices)):
for j in xrange(1, min(k, i/2+1) + 1):
max_buy[j] = max(max_buy[j], max_sell[j-1] - prices[i])
max_sell[j] = max(max_sell[j], max_buy[j] + prices[i])
return max_sell[k]
Run Time: 128 ms
Leetcode 187. Repeated DNA Sequences
https://leetcode.com/problems/repeated-dna-sequences/
Hash table is a clear solution. We can use advanced rolling hash, or just the easiest one.
Solution:
Hash table is a clear solution. We can use advanced rolling hash, or just the easiest one.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param {string} s
# @return {string[]}
def findRepeatedDnaSequences(self, s):
length = len(s)
if length <= 10: return []
dict, ret = {}, []
for i in xrange(10, length+1):
if s[i-10 : i] in dict:
dict[s[i-10:i]] += 1
if s[i-10:i] not in ret:
ret.append(s[i-10:i])
else:
dict[s[i-10:i]] = 1
return ret
Run Time: 124 ms
Leetcode 186. Reverse Words in a String II
[locked]
# Time: O(n)
# Space:O(1)
#
# Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
#
# The input string does not contain leading or trailing spaces and the words are always separated by a single space.
#
# For example,
# Given s = "the sky is blue",
# return "blue is sky the".
#
# Could you do it in-place without allocating extra space?
#
class Solution:
# @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
# @return nothing
def reverseWords(self, s):
self.reverse(s, 0, len(s))
i = 0
for j in xrange(len(s) + 1):
if j == len(s) or s[j] == ' ':
self.reverse(s, i, j)
i = j + 1
def reverse(self, s, begin, end):
for i in xrange((end - begin) / 2):
s[begin + i], s[end - 1 - i] = s[end - 1 - i], s[begin + i]
Leetcode 179. Largest Number
https://leetcode.com/problems/largest-number/
Note: we now only care about algorithm problems. So some problems are ignored.
Using built-in function will make it simple.
Solution:
Note: we now only care about algorithm problems. So some problems are ignored.
Using built-in function will make it simple.
Solution:
# T:O(nlgn) S:O(1)
class Solution:
# @param num, a list of integers
# @return a string
def largestNumber(self, num):
num = [str(x) for x in num]
num.sort(cmp=lambda x, y: cmp(y + x, x + y))
largest = ''.join(num)
return largest.lstrip('0') or '0'
Run Time: 64 ms
Leetcode 174. Dungeon Game
https://leetcode.com/problems/dungeon-game/
Interesting problem with classic DP solution. The better thought is start from end, and count each grid the min hp the hero needs to get through. The solution is using rolling DP with very elegant coding. Very impressive.
Solution:
Interesting problem with classic DP solution. The better thought is start from end, and count each grid the min hp the hero needs to get through. The solution is using rolling DP with very elegant coding. Very impressive.
Solution:
# T:O(m*n) S:O(m+n)
class Solution:
# @param dungeon, a list of lists of integers
# @return a integer
def calculateMinimumHP(self, dungeon):
DP = [float("inf") for _ in dungeon[0]]
DP[-1] = 1
for i in reversed(xrange(len(dungeon))):
DP[-1] = max(DP[-1] - dungeon[i][-1], 1)
for j in reversed(xrange(len(dungeon[i]) - 1)):
min_HP_on_exit = min(DP[j], DP[j + 1])
DP[j] = max(min_HP_on_exit - dungeon[i][j], 1)
return DP[0]
Run Time: 52 ms
Leetcode 173. Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/
The iterator consists of a tree and a stack. For BST, the smallest number is the most left node.
Solution:
The iterator consists of a tree and a stack. For BST, the smallest number is the most left node.
Solution:
# T:O(1) S:O(h)
class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.stack = []
self.cur = root
# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.stack or self.cur
# @return an integer, the next smallest number
def next(self):
while self.cur:
self.stack.append(self.cur)
self.cur = self.cur.left
self.cur = self.stack.pop()
node = self.cur
self.cur = self.cur.right
return node.val
Run Time: 140 ms
Leetcode 172. Factorial Trailing Zeroes
https://leetcode.com/problems/factorial-trailing-zeroes/
We know that 2 x 5 =10 is the source of trailing zeroes. So do we need to count the numbers of 2 and 5 in the factorial? Actually no. Because when one 5 occurred, two 2 have occurred. Hence we only need to count the number of 5, for 2 must be more.
Solution:
We know that 2 x 5 =10 is the source of trailing zeroes. So do we need to count the numbers of 2 and 5 in the factorial? Actually no. Because when one 5 occurred, two 2 have occurred. Hence we only need to count the number of 5, for 2 must be more.
Solution:
# T:O(lgn) S:O(1)
class Solution:
# @return an integer
def trailingZeroes(self, n):
result = 0
while n > 0:
result += n / 5
n /= 5
return result
Run Time: 52 ms
Leetcode 171. Excel Sheet Column Number
https://leetcode.com/problems/excel-sheet-column-number/
This is the reverse operation of problem 168.
Solution:
This is the reverse operation of problem 168.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param s, a string
# @return an integer
def titleToNumber(self, s):
result = 0
for i in xrange(len(s)):
result *= 26
result += ord(s[i]) - ord('A') + 1
return result
Run Time: 60 ms
Monday, August 24, 2015
Leetcode 170. Two Sum III - Data structure design
[locked]
# Time: O(n)
# Space: O(n)
#
# Design and implement a TwoSum class. It should support the following operations: add and find.
#
# add - Add the number to an internal data structure.
# find - Find if there exists any pair of numbers which sum is equal to the value.
#
# For example,
# add(1); add(3); add(5);
# find(4) -> true
# find(7) -> false
#
class TwoSum:
# initialize your data structure here
def __init__(self):
self.lookup = {}
# @return nothing
def add(self, number):
if number in self.lookup:
self.lookup[number] += 1
else:
self.lookup[number] = 1
# @param value, an integer
# @return a Boolean
def find(self, value):
for key in self.lookup:
num = value - key
if num in self.lookup and (num != key or self.lookup[key] > 1):
return True
return False
Leetcode 169. Majority Element
https://leetcode.com/problems/majority-element/
The simple thought is using hash table to count. However, there is another tricky way. Because the number of majority is bigger than n/2, so if we add 1 when see it and subtract 1 when not see it, the final value should be larger than 0.
Solution:
The simple thought is using hash table to count. However, there is another tricky way. Because the number of majority is bigger than n/2, so if we add 1 when see it and subtract 1 when not see it, the final value should be larger than 0.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):
idx, cnt = 0, 1
for i in xrange(1, len(num)):
if num[idx] == num[i]:
cnt += 1
else:
cnt -= 1
if cnt == 0:
idx = i
cnt = 1
return num[idx]
Run Time: 72 ms
Leetcode 168. Excel Sheet Column Title
https://leetcode.com/problems/excel-sheet-column-title/
Solution:
Solution:
# T:O(lgn) S:O(1)
class Solution:
# @param {integer} n
# @return {string}
def convertToTitle(self, n):
result, dvd = "", n
while dvd:
result += chr((dvd - 1) % 26 + ord('A'))
dvd = (dvd - 1) / 26
return result[::-1]
Run Time: 36 ms
Leetcode 167. Two Sum II - Input array is sorted
[locked]
# Time: O(n)
# Space: O(1)
#
# Given an array of integers that is already sorted in ascending order,
# find two numbers such that they add up to a specific target number.
#
# The function twoSum should return indices of the two numbers such that
# they add up to the target, where index1 must be less than index2.
# Please note that your returned answers (both index1 and index2) are not zero-based.
#
# You may assume that each input would have exactly one solution.
#
# Input: numbers={2, 7, 11, 15}, target=9
# Output: index1=1, index2=2
#
class Solution:
def twoSum(self, nums, target):
start, end = 0, len(nums) - 1
while start != end:
sum = nums[start] + nums[end]
if sum > target:
end -= 1
elif sum < target:
start += 1
else:
return [start + 1, end + 1]
Leetcode 166. Fraction to Recurring Decimal
https://leetcode.com/problems/fraction-to-recurring-decimal/
The hard part is how to get repeated fraction number. The answer is that when the dividend appears twice, there will be such situation.
Solution:
The hard part is how to get repeated fraction number. The answer is that when the dividend appears twice, there will be such situation.
Solution:
# T:O(lgn) S:O(1)
class Solution:
# @param {integer} numerator
# @param {integer} denominator
# @return {string}
def fractionToDecimal(self, numerator, denominator):
dvd, dvs = abs(numerator), abs(denominator)
integer, decimal, dict = "", '', {}
if dvd > dvs:
integer = str(dvd / dvs)
dvd %= dvs
else:
integer = "0"
if dvd > 0:
integer += "."
idx = 0
while dvd:
if dvd in dict:
decimal = decimal[:dict[dvd]] + "(" + decimal[dict[dvd]:] + ")"
break
dict[dvd] = idx
idx += 1
dvd *= 10
decimal += str(dvd / dvs)
dvd %= dvs
if (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0):
return "-" + integer + decimal
else:
return integer + decimal
Run Time: 44 ms
Leetcode 165. Compare Version Numbers
https://leetcode.com/problems/compare-version-numbers/
The problem itself is not very hard, but how to deal with extra zeros? Of course we can add a sentence to judge if the remaining part is all zeros, while the better way is to fill zeros before hand to make the two strings have the same length.
Solution:
The problem itself is not very hard, but how to deal with extra zeros? Of course we can add a sentence to judge if the remaining part is all zeros, while the better way is to fill zeros before hand to make the two strings have the same length.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param a, a string
# @param b, a string
# @return a boolean
def compareVersion(self, version1, version2):
v1, v2 = version1.split("."), version2.split(".")
if len(v1) > len(v2):
v2 += ['0' for _ in xrange(len(v1) - len(v2))]
elif len(v1) < len(v2):
v1 += ['0' for _ in xrange(len(v2) - len(v1))]
i = 0
while i < len(v1):
if int(v1[i]) > int(v2[i]):
return 1
elif int(v1[i]) < int(v2[i]):
return -1
else:
i += 1
return 0
Run Time: 56 ms
Leetcode 164. Maximum Gap
https://leetcode.com/problems/maximum-gap/
Using bucket sorting.
Solution:
Using bucket sorting.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param numss: a list of integers
# @return: the maximum difference
def maximumGap(self, nums):
if len(nums) < 2:
return 0
# Init bucket.
max_val, min_val = max(nums), min(nums)
gap = max(1, (max_val - min_val) / (len(nums) - 1))
bucket_size = (max_val - min_val) / gap + 1
bucket = [{'min':float("inf"), 'max':float("-inf")} \
for _ in xrange(bucket_size)]
# Find the bucket where the n should be put.
for n in nums:
# min_val / max_val is in the first / last bucket.
if n in (max_val, min_val):
continue
i = (n - min_val) / gap
bucket[i]['min'] = min(bucket[i]['min'], n)
bucket[i]['max'] = max(bucket[i]['max'], n)
# Count each bucket gap between the first and the last bucket.
max_gap, pre_bucket_max = 0, min_val
for i in xrange(bucket_size):
# Skip the bucket it empty.
if bucket[i]['min'] == float("inf") and \
bucket[i]['max'] == float("-inf"):
continue
max_gap = max(max_gap, bucket[i]['min'] - pre_bucket_max)
pre_bucket_max = bucket[i]['max']
# Count the last bucket.
max_gap = max(max_gap, max_val - pre_bucket_max)
return max_gap
Run Time: 96 ms
Leetcode 163. Missing Ranges
[locked]
# Time: O(n)
# Space: O(1)
#
# Given a sorted integer array where the range of elements are [lower, upper] inclusive,
# return its missing ranges.
#
# For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99,
# return ["2", "4->49", "51->74", "76->99"].
#
class Solution:
# @param A, a list of integers
# @param lower, an integer
# @param upper, an integer
# @return a list of strings
def findMissingRanges(self, A, lower, upper):
ranges = []
pre = lower - 1
for i in xrange(len(A) + 1):
if i == len(A):
cur = upper + 1
else:
cur = A[i]
if cur - pre >= 2:
ranges.append(self.getRange(pre + 1, cur - 1))
pre = cur
return ranges
def getRange(self, lower, upper):
if lower == upper:
return "{}".format(lower)
else:
return "{}->{}".format(lower, upper)
Leetcode 162. Find Peak Element
https://leetcode.com/problems/find-peak-element/
The slick solution is to return the index of max number. The normal solution is to use binary search,
Solution:
The slick solution is to return the index of max number. The normal solution is to use binary search,
Solution:
# T:O(lgn) S:O(1)
class Solution:
# @param num, a list of integer
# @return an integer
def findPeakElement(self, num):
low, high = 0, len(num) - 1
while low < high:
mid = low + (high - low) / 2
if (mid == 0 or num[mid - 1] <= num[mid]) and \
(mid == len(num) - 1 or num[mid + 1] <= num[mid]):
return mid
elif mid > 0 and num[mid - 1] > num[mid]:
high = mid - 1
else:
low = mid + 1
return low
Run Time: 76 ms
Leetcode 161. One Edit Distance
[locked]
# Time: O(m + n)
# Space: O(1)
#
# Given two strings S and T, determine if they are both one edit distance apart.
#
class Solution:
# @param s, a string
# @param t, a string
# @return a boolean
def isOneEditDistance(self, s, t):
m, n = len(s), len(t)
if m > n:
return self.isOneEditDistance(t, s)
if n - m > 1:
return False
i, shift = 0, n - m
while i < m and s[i] == t[i]:
i += 1
if shift == 0:
i += 1
while i < m and s[i] == t[i + shift]:
i += 1
return i == m
Leetcode 160. Intersection of Two Linked Lists
https://leetcode.com/problems/intersection-of-two-linked-lists/
The simple thought is to get lengths of two lists, and make them start with the same distance from tails. This method will use 3 iterations.
There is an improved method. Even two lists' lengths differ, their sum is the same one. So if we make two pointers starting with heads, and switch to another head when finishing this lists, actually the effect is same with simple thought. While this method saves time.
Solution:
The simple thought is to get lengths of two lists, and make them start with the same distance from tails. This method will use 3 iterations.
There is an improved method. Even two lists' lengths differ, their sum is the same one. So if we make two pointers starting with heads, and switch to another head when finishing this lists, actually the effect is same with simple thought. While this method saves time.
Solution:
# T:O(m+n) S:O(1)
class Solution:
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
curA, curB = headA, headB
tailA, tailB = None, None
while curA and curB:
if curA == curB:
return curA
if curA.next:
curA = curA.next
elif tailA is None:
tailA = curA
curA = headB
else:
break
if curB.next:
curB = curB.next
elif tailB is None:
tailB = curB
curB = headA
else:
break
Run Time: 436 ms
Leetcode 159. Longest Substring with At Most Two Distinct Characters
[locked]
# Time: O(n^2)
# Space: O(1)
#
# Given a string, find the length of the longest substring T
# that contains at most 2 distinct characters.
#
# For example, Given s = "eceba",
#
# T is "ece" which its length is 3.
#
class Solution:
# @param s, a string
# @return an integer
def lengthOfLongestSubstringTwoDistinct(self, s):
longest, start, distinct_count, visited = 0, 0, 0, [0 for _ in xrange(256)]
for i, char in enumerate(s):
if visited[ord(char)] == 0:
distinct_count += 1
visited[ord(char)] += 1
while distinct_count > 2:
visited[ord(s[start])] -= 1
if visited[ord(s[start])] == 0:
distinct_count -= 1
start += 1
longest = max(longest, i - start + 1)
return longest
Leetcode 158. Read N Characters Given Read4 II - Call multiple times
[locked]
# Time: O(n)
# Space: O(1)
#
# The API: int read4(char *buf) reads 4 characters at a time from a file.
#
# The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
#
# By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
#
# Note:
# The read function may be called multiple times.
#
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
def read4(buf):
global file_content
i = 0
while i < len(file_content) and i < 4:
buf[i] = file_content[i]
i += 1
if len(file_content) > 4:
file_content = file_content[4:]
else:
file_content = ""
return i
class Solution:
def __init__(self):
self.buffer_size, self.offset = 0, 0
self.buffer = [None for _ in xrange(4)]
# @param buf, Destination buffer (a list of characters)
# @param n, Maximum number of characters to read (an integer)
# @return The number of characters read (an integer)
def read(self, buf, n):
read_bytes = 0
eof = False
while not eof and read_bytes < n:
if self.buffer_size == 0:
size = read4(self.buffer)
else:
size = self.buffer_size
if self.buffer_size == 0 and size < 4:
eof = True
bytes = min(n - read_bytes, size)
for i in xrange(bytes):
buf[read_bytes + i] = self.buffer[self.offset + i]
self.offset = (self.offset + bytes) % 4
self.buffer_size = size - bytes
read_bytes += bytes
return read_bytes
Leetcode 157. Read N Characters Given Read4
[locked]
Solution:
Solution:
# Time: O(n)
# Space: O(1)
#
# The API: int read4(char *buf) reads 4 characters at a time from a file.
#
# The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
#
# By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
#
# Note:
# The read function will only be called once for each test case.
#
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
def read4(buf):
global file_content
i = 0
while i < len(file_content) and i < 4:
buf[i] = file_content[i]
i += 1
if len(file_content) > 4:
file_content = file_content[4:]
else:
file_content = ""
return i
class Solution:
# @param buf, Destination buffer (a list of characters)
# @param n, Maximum number of characters to read (an integer)
# @return The number of characters read (an integer)
def read(self, buf, n):
read_bytes = 0
eof = False
buffer = ['' for _ in xrange(4)]
while not eof and read_bytes < n:
size = read4(buffer)
if size < 4:
eof = True
bytes = min(n - read_bytes, size)
for i in xrange(bytes):
buf[read_bytes + i] = buffer[i]
read_bytes += bytes
return read_bytes
Leetcode 156. Binary Tree Upside Down
Note: this problem is locked. If you want to look at it, please buy Leetcode's book. Such problems will be marked with 'locked' in later pages. The solution is referred from kamyu104's GitHub.
Solution:
Solution:
# Time: O(n)
# Space: O(1)
#
# Given a binary tree where all the right nodes are either leaf nodes with a sibling
# (a left node that shares the same parent node) or empty, flip it upside down and
# turn it into a tree where the original right nodes turned into left leaf nodes.
# Return the new root.
#
# For example:
# Given a binary tree {1,2,3,4,5},
#
# 1
# / \
# 2 3
# / \
# 4 5
#
# return the root of the binary tree [4,5,2,#,#,3,1].
#
# 4
# / \
# 5 2
# / \
# 3 1
#
# Definition for a binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# @param root, a tree node
# @return root of the upside down tree
def upsideDownBinaryTree(self, root):
p, parent, parent_right = root, None, None
while p:
left = p.left
p.left = parent_right
parent_right = p.right
p.right = parent
parent = p
p = left
return parent
# Time: O(n)
# Space: O(n)
class Solution2:
# @param root, a tree node
# @return root of the upside down tree
def upsideDownBinaryTree(self, root):
return self.upsideDownBinaryTreeRecu(root, None)
def upsideDownBinaryTreeRecu(self, p, parent):
if p is None:
return parent
root = self.upsideDownBinaryTreeRecu(p.left, p)
if parent:
p.left = parent.right
else:
p.left = None
p.right = parent
return root
Sunday, August 23, 2015
Leetcode 155. Min Stack
https://leetcode.com/problems/min-stack/
We can use another stack to store min value. Or not.
Solution 1:
Solution 2:
We can use another stack to store min value. Or not.
Solution 1:
# T:O(n) S:O(1)
class MinStack:
def __init__(self):
self.min = None
self.stack = []
# @param x, an integer
# @return an integer
def push(self, x):
if not self.stack:
self.stack.append(0)
self.min = x
else:
self.stack.append(x - self.min)
if x < self.min:
self.min = x
# @return nothing
def pop(self):
x = self.stack.pop()
if x < 0:
self.min = self.min - x
# @return an integer
def top(self):
x = self.stack[-1]
if x > 0:
return x + self.min
else:
return self.min
# @return an integer
def getMin(self):
return self.min
Run Time: 152 msSolution 2:
# T:O(n) S:O(n)
class MinStack:
def __init__(self):
self.stack, self.minStack = [], []
# @param x, an integer
# @return an integer
def push(self, x):
self.stack.append(x)
if len(self.minStack):
if x < self.minStack[-1][0]:
self.minStack.append([x, 1])
elif x == self.minStack[-1][0]:
self.minStack[-1][1] += 1
else:
self.minStack.append([x, 1])
# @return nothing
def pop(self):
x = self.stack.pop()
if x == self.minStack[-1][0]:
self.minStack[-1][1] -= 1
if self.minStack[-1][1] == 0:
self.minStack.pop()
# @return an integer
def top(self):
return self.stack[-1]
# @return an integer
def getMin(self):
return self.minStack[-1][0]
Run Time: 92 ms
Leetcode 154. Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Solution:
Solution:
# T:O(lgn)~O(n) S:O(1)
class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
low, high = 0, len(num)
while low < high - 1 and num[low] >= num[high - 1]:
mid = low + (high - low) / 2
if num[mid] > num[low]:
low = mid + 1
elif num[mid] < num[low]:
if mid == high - 1:
return num[mid]
else:
high = mid + 1
else:
low += 1
return num[low]
Run Time: 48 ms
Leetcode 153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
One line for Python: return min(nums). The normal way is binary search.
Solution:
One line for Python: return min(nums). The normal way is binary search.
Solution:
# T:O(lgn) S:O(1)
class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
low, high = 0, len(num)
while low < high - 1 and num[low] >= num[high - 1]:
mid = low + (high - low) / 2
if num[mid] > num[low]:
low = mid + 1
elif num[mid] < num[low]:
if mid == high - 1:
return num[mid]
else:
high = mid + 1
else:
return num[mid]
return num[low]
Run Time: 52 ms
Leetcode 152. Maximum Product Subarray
https://leetcode.com/problems/maximum-product-subarray/
Note that a very small negative number can be very large after timing a negative number, so the min value should also be recorded.
Solution:
Note that a very small negative number can be very large after timing a negative number, so the min value should also be recorded.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param A, a list of integers
# @return an integer
def maxProduct(self, A):
global_max, local_max, local_min = float("-inf"), 1, 1
for x in A:
local_max, local_min = max(x, local_max * x, local_min * x), min(x, local_max * x, local_min * x)
global_max = max(global_max, local_max)
return global_max
Run Time: 84 ms
Leetcode 151. Reverse Words in a String
https://leetcode.com/problems/reverse-words-in-a-string/
For Python, such string processing is quite easy.
Solution:
For Python, such string processing is quite easy.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param s, a string
# @return a string
def reverseWords(self, s):
return ' '.join(reversed(s.split()))
Run Time: 48 ms
Saturday, August 22, 2015
Leetcode 150. Evaluate Reverse Polish Notation
https://leetcode.com/problems/evaluate-reverse-polish-notation/
Apparently using stack is a good idea. If we switch the four cases, the branches are too many. So we can use the operator module to simplify the code.
Note the last 'int' is necessary because the result should be type of int.
Solution:
Apparently using stack is a good idea. If we switch the four cases, the branches are too many. So we can use the operator module to simplify the code.
Note the last 'int' is necessary because the result should be type of int.
Solution:
# T:O(n) S:O(n)
import operator
class Solution:
# @param tokens, a list of string
# @return an integer
def evalRPN(self, tokens):
numerals, operators = [], \
{"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div}
for token in tokens:
if token not in operators:
numerals.append(int(token))
else:
y, x = numerals.pop(), numerals.pop()
numerals.append(int(operators[token](x * 1.0, y)))
return numerals.pop()
Run Time: 80 ms
Leetcode 149. Max Points on a Line
https://leetcode.com/problems/max-points-on-a-line/
The basic thought is to count the points that have the same slope to every point. Also do not miss the vertical lines.
Solution:
The basic thought is to count the points that have the same slope to every point. Also do not miss the vertical lines.
Solution:
# T:O(n^2) S:O(n)
class Solution:
# @param points, a list of Points
# @return an integer
def maxPoints(self, points):
max_points = 0
for i, start in enumerate(points):
slope_count, same = {}, 1
for j in xrange(i + 1, len(points)):
end = points[j]
if start.x == end.x and start.y == end.y:
same += 1
else:
slope = float("inf")
if start.x - end.x != 0:
slope = (start.y - end.y) * 1.0 / (start.x - end.x)
if slope not in slope_count:
slope_count[slope] = 1
else:
slope_count[slope] += 1
current_max = same
for slope in slope_count:
current_max = max(current_max, slope_count[slope] + same)
max_points = max(max_points, current_max)
return max_points
Run Time: 80 ms
Leetcode 148. Sort List
https://leetcode.com/problems/sort-list/
For O(nlgn) time, the way is merge sort.
Solution:
For O(nlgn) time, the way is merge sort.
Solution:
# T:O(nlgn) S:O(lgn)
class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
if head == None or head.next == None:
return head
fast, slow, prev = head, head, None
while fast != None and fast.next != None:
prev, fast, slow = slow, fast.next.next, slow.next
prev.next = None
sorted_l1 = self.sortList(head)
sorted_l2 = self.sortList(slow)
return self.mergeTwoLists(sorted_l1, sorted_l2)
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 != None and l2 != None:
if l1.val <= l2.val:
cur.next, cur, l1 = l1, l1, l1.next
else:
cur.next, cur, l2 = l2, l2, l2.next
if l1 != None:
cur.next = l1
if l2 != None:
cur.next = l2
return dummy.next
Run Time: 412 ms
Leetcode 147. Insertion Sort List
https://leetcode.com/problems/insertion-sort-list/
It is a linked list version of insert sorting.
Solution:
It is a linked list version of insert sorting.
Solution:
# T:O(n^2) S:O(1)
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
if not head:
return head
dummy = ListNode(0)
dummy.next = head
curr = head
while curr.next:
if curr.next.val < curr.val:
pre = dummy
while pre.next.val < curr.next.val:
pre = pre.next
tmp = curr.next
curr.next = tmp.next
tmp.next = pre.next
pre.next = tmp
else:
curr = curr.next
return dummy.next
Run Time: 348 ms
Leetcdoe 146. LRU Cache
https://leetcode.com/problems/lru-cache/
This is quite comprehensive. We use double linked list.
Solution:
This is quite comprehensive. We use double linked list.
Solution:
# T:O(1) S:O(n)
class ListNode:
def __init__(self, key, val):
self.val = val
self.key = key
self.next = None
self.prev = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert(self, node):
if self.head is None:
self.head = node
else:
self.tail.next = node
node.prev = self.tail
self.tail = node
def delete(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
del node
class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
self.list = LinkedList()
self.dict = {}
self.capacity = capacity
def _insert(self, key, val):
node = ListNode(key, val)
self.list.insert(node)
self.dict[key] = node
# @return an integer
def get(self, key):
if key in self.dict:
val = self.dict[key].val
self.list.delete(self.dict[key])
self._insert(key, val)
return val
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, val):
if key in self.dict:
self.list.delete(self.dict[key])
elif len(self.dict) == self.capacity:
del self.dict[self.list.head.key]
self.list.delete(self.list.head)
self._insert(key, val)
import collections
class LRUCache2:
def __init__(self, capacity):
self.cache = collections.OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
val = self.cache[key]
del self.cache[key]
self.cache[key] = val
return val
def set(self, key, value):
if key in self.cache:
del self.cache[key]
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
Run Time: 436 ms
Leetcode 145. Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/
Solution:
Solution:
# T:O(n) S:O(n)
class Solution:
# @param root, a tree node
# @return a list of integers
def recursive_postorder(self, root, list):
if root:
self.postorder( root.left, list )
self.postorder( root.right, list )
list.append(root.val)
def iterative_postorder(self, root, list):
stack = []
pre = None
if root:
stack.append(root)
while stack:
curr = stack[len(stack) - 1]
if (curr.left == None and curr.right == None) or\
(pre and (pre == curr.left or pre == curr.right)):
list.append(curr.val)
stack.pop()
pre = curr
else:
if curr.right: stack.append(curr.right)
if curr.left: stack.append(curr.left)
return list
def postorderTraversal(self, root):
list = []
self.iterative_postorder(root,list)
return list
Run Time: 72 ms
Leetcode 144. Binary Tree Preorder Traversal
https://leetcode.com/problems/binary-tree-preorder-traversal/
Solution:
Solution:
# T:O(n) S:O(n)
class Solution:
# @param root, a tree node
# @return a list of integers
def iterative_preorder(self, root, list):
stack = []
while root or stack:
if root:
list.append(root.val)
stack.append(root)
root = root.left
else:
root = stack.pop()
root = root.right
return list
def recursive_preorder(self, root, list):
if root:
list.append(root.val)
self.preorder(root.left,list)
self.preorder(root.right,list)
def preorderTraversal(self,root):
list = []
self.iterative_preorder(root,list)
return list
Run Time: 48 ms
Leetcode 143. Reorder List
https://leetcode.com/problems/reorder-list/
Still simple. 3 steps to do the task: cut, reverse and merge. Concerning the cut process, we can use the slow and fast pointers-- they are really useful.
Solution:
Still simple. 3 steps to do the task: cut, reverse and merge. Concerning the cut process, we can use the slow and fast pointers-- they are really useful.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param head, a ListNode
# @return nothing
def reorderList(self, head):
if head == None or head.next == None:
return
fast, slow, prev = head, head, None
while fast != None and fast.next != None:
fast, slow, prev = fast.next.next, slow.next, slow
current, prev.next, prev = slow, None, None
while current != None:
current.next, prev, current = prev, current, current.next
l1, l2 = head, prev
dummy = ListNode(0)
current = dummy
while l1 != None and l2 != None:
current.next, current, l1 = l1, l1, l1.next
current.next, current, l2 = l2, l2, l2.next
return
Run Time: 168 ms
Leetcode 142. Linked List Cycle II
https://leetcode.com/problems/linked-list-cycle-ii/
This needs some math calculation, while the result turns out to be simple enough. Still slow and fast pointers.
Solution:
This needs some math calculation, while the result turns out to be simple enough. Still slow and fast pointers.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast is slow:
fast = head
while fast is not slow:
fast, slow = fast.next, slow.next
return fast
return None
Run Time: 80 ms
Leetcode 141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
For this problem, the best solution is to use two pointers: slow and fast. If they meet at somewhere, there is a cycle.
Solution:
For this problem, the best solution is to use two pointers: slow and fast. If they meet at somewhere, there is a cycle.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param head, a ListNode
# @return a boolean
def hasCycle(self, head):
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast is slow:
return True
return False
Run Time: 76 ms
Leetcode 140. Word Break II
https://leetcode.com/problems/word-break-ii/
A combination of DFS and DP. Use DFS to generate strings, and use DP to judge if it is valid.
Solution:
A combination of DFS and DP. Use DFS to generate strings, and use DP to judge if it is valid.
Solution:
# T:O(n^2) S:O(n)
class Solution:
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def check(self, s, dict):
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(1, len(s)+1):
for k in range(0, i):
if dp[k] and s[k:i] in dict:
dp[i] = True
return dp[len(s)]
def dfs(self, s, dict, stringlist):
if self.check(s, dict):
if len(s) == 0: Solution.res.append(stringlist[1:])
for i in range(1, len(s)+1):
if s[:i] in dict:
self.dfs(s[i:], dict, stringlist+' '+s[:i])
def wordBreak(self, s, dict):
Solution.res = []
self.dfs(s, dict, '')
return Solution.res
Run Time: 84 ms
Leetcode 139. Word Break
https://leetcode.com/problems/word-break/
Using DP.
Solution:
Using DP.
Solution:
# T:O(n^2) S:O(n)
class Solution:
# @param s, a string
# @param dict, a set of string
# @return a boolean
# @good coding!
def wordBreak(self, s, dict):
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(1, len(s)+1):
for k in range(i):
if dp[k] and s[k:i] in dict:
dp[i] = True
return dp[len(s)]
Run Time: 68 ms
Leetcode 138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/
There are mainly two solutions. Solution 1 is to generate a linked list in place and split it as the new list; solution 2 is to copy a new linked list. Solution 2 is easier, though it used an extra dictionary.
Solution 1:
Solution 2:
There are mainly two solutions. Solution 1 is to generate a linked list in place and split it as the new list; solution 2 is to copy a new linked list. Solution 2 is easier, though it used an extra dictionary.
Solution 1:
# T:O(n) S:O(n)
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
# copy and combine copied list with original list
current = head
while current:
copied = RandomListNode(current.label)
copied.next = current.next
current.next = copied
current = copied.next
# update random node in copied list
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# split copied list from combined one
dummy = RandomListNode(0)
copied_current, current = dummy, head
while current:
copied_current.next = current.next
current.next = current.next.next
copied_current, current = copied_current.next, current.next
return dummy.next
Run Time: 124 msSolution 2:
# T:O(n) S:O(n)
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
dummy = RandomListNode(0)
current, prev, copies = head, dummy, {}
while current:
copied = RandomListNode(current.label)
copies[current] = copied
prev.next = copied
prev, current = prev.next, current.next
current = head
while current:
if current.random:
copies[current].random = copies[current.random]
current = current.next
return dummy.next
Run Time: 152 ms
Leetcode 137. Single Number II
https://leetcode.com/problems/single-number-ii/
Now this is much more complex. No simple operation to solve.
The solution is actually using binary to simulate ternary.
Solution:
Now this is much more complex. No simple operation to solve.
The solution is actually using binary to simulate ternary.
Solution:
# T:O(n) S:O(1)
lass Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
one, two = 0, 0
for x in A:
one, two = (~x & one) | (x & ~one & ~two), (~x & two) | (x & one)
return one
Run Time: 64 ms
Leetcode 136. Single Number
https://leetcode.com/problems/single-number/
Linear time complexity means O(n) and hence no sorting. Of course we can use a hash table, while it will use O(n) space.
So what is the O(n) O(1) solution? Actually it is based on the two formulas: N XOR N = 0, N XOR 0 = N. Therefore we just XOR them all and the result is the wanted number.
Solution:
Linear time complexity means O(n) and hence no sorting. Of course we can use a hash table, while it will use O(n) space.
So what is the O(n) O(1) solution? Actually it is based on the two formulas: N XOR N = 0, N XOR 0 = N. Therefore we just XOR them all and the result is the wanted number.
Solution:
# T:O(n) S:O(1)
import operator
class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
return reduce(operator.xor, A)
Run Time: 60 ms
Leetcode 135. Candy
https://leetcode.com/problems/candy/
Actually this problem is not that hard if you grasp the point. Two scans will do the job.
Solution:
Actually this problem is not that hard if you grasp the point. Two scans will do the job.
Solution:
# T:O(n) S:O(n)
class Solution:
# @param ratings, a list of integer
# @return an integer
def candy(self, ratings):
candynum = [1 for i in range(len(ratings))]
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
candynum[i] = candynum[i-1] + 1
for i in range(len(ratings)-2, -1, -1):
if ratings[i+1] < ratings[i] and candynum[i+1] >= candynum[i]:
candynum[i] = candynum[i+1] + 1
return sum(candynum)
Run Time: 108 ms
Leetcode 134. Gas Station
https://leetcode.com/problems/gas-station/
The solution is first make sure the sum of gas is greater or equal than the cost; then try to start from every station and go around.
Solution:
The solution is first make sure the sum of gas is greater or equal than the cost; then try to start from every station and go around.
Solution:
# T:O(n) S:O(1)
class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
if sum(gas) < sum(cost): return -1
n, diff, stationIndex = len(gas), 0, 0
for i in range(n):
if gas[i]+diff < cost[i]:
stationIndex, diff = i+1, 0
else: diff += gas[i]-cost[i]
return stationIndex
Run Time: 48 ms
Leetcode 133. Clone Graph
https://leetcode.com/problems/clone-graph/
We can use both BFS and DFS.
Solution 1:
Solution 2:
We can use both BFS and DFS.
Solution 1:
# T:O(n) S:O(n)
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
# @DFS
def cloneGraph(self, node):
def dfs(input, map):
if input in map:
return map[input]
output = UndirectedGraphNode(input.label)
map[input] = output
for neighbor in input.neighbors:
output.neighbors.append(dfs(neighbor, map))
return output
if node == None: return None
return dfs(node, {})
Run Time: 192 msSolution 2:
# T:O(n) S:O(n)
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
# @BFS
def cloneGraph(self, node):
if node == None: return None
queue, map = [], {}
newhead = UndirectedGraphNode(node.label)
queue.append(node)
map[node] = newhead
while queue:
curr = queue.pop()
for neighbor in curr.neighbors:
if neighbor not in map:
copy = UndirectedGraphNode(neighbor.label)
map[curr].neighbors.append(copy)
map[neighbor] = copy
queue.append(neighbor)
else:
# turn directed graph to undirected graph
map[curr].neighbors.append(map[neighbor])
return newhead
Run Time: 84 ms
Leetcode 132. Palindrome Partitioning II
https://leetcode.com/problems/palindrome-partitioning-ii/
Last problem is using DFS because string list is required, while in this problem, only a number is wanted, hence we can use DP.
Below p[i][j] means whether string from i to j is a palindrome, and dp[i] means how many palindromes could have under min-cut from index i to end, namely the number of cut pluses 1.
Solution:
Last problem is using DFS because string list is required, while in this problem, only a number is wanted, hence we can use DP.
Below p[i][j] means whether string from i to j is a palindrome, and dp[i] means how many palindromes could have under min-cut from index i to end, namely the number of cut pluses 1.
Solution:
# T:O(n^2) S:O(n^2)
class Solution:
# @param s, a string
# @return an integer
# @dfs time out
# @dp is how many palindromes in the word
def minCut(self, s):
dp = [0 for i in range(len(s)+1)]
p = [[False for i in range(len(s))] for j in range(len(s))]
for i in range(len(s)+1):
dp[i] = len(s) - i
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j] and (((j - i) < 2) or p[i+1][j-1]):
p[i][j] = True
dp[i] = min(1+dp[j+1], dp[i])
return dp[0]-1
Run Time: 764 ms
Subscribe to:
Posts (Atom)