In [ ]:
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return None
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
In [ ]:
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
C = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
V = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
ans = ""
for v, c in zip(V, C):
if num >= v:
counts = num / v
num = num % v
ans += c*counts
return ans
In [21]:
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
dp = [True]
L = len(s)
for i in xrange(L):
dp.append(False)
for j in xrange(i, -1, -1):
if dp[j] and s[j:i+1] in wordDict:
dp[-1] = True
break
return dp[L]
In [ ]:
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
total, left, start = 0, 0, 0
for i in xrange(len(gas)):
diff = gas[i] - cost[i]
total += diff
left += diff
if left < 0:
left = 0
start = i+1
if total < 0:
return -1
else:
return start
In [ ]:
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def __init__(self):
self.dic = {}
def cloneGraph(self, node):
if node is None:
return None
if node.label in self.dic:
return self.dic[node.label]
root = UndirectedGraphNode(node.label)
self.dic[node.label] = root
for node in node.neighbors:
root.neighbors.append(self.cloneGraph(node))
return root
In [ ]:
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
def isPalindrome(s):
L = len(s)
mid = L/2
if L % 2 == 0:
return s[:mid] == s[:mid-1:-1]
else:
return s[:mid] == s[:mid:-1]
ans = []
def search(s, parent):
if s == "":
ans.append(parent)
else:
for i in xrange(1, len(s)+1):
c = s[:i]
if isPalindrome(c):
search(s[i:], parent+[c])
search(s, [])
return ans
In [ ]:
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
rows = len(board)
if rows == 0:
return
cols, queue = len(board[0]), []
def fill(row, col):
if row >=0 and row < rows and col >= 0 and col < cols and board[row][col] == 'O':
board[row][col] = 'D'
queue.append((row+1,col))
queue.append((row-1,col))
queue.append((row,col+1))
queue.append((row,col-1))
def bfs(row, col):
queue.append((row, col))
while queue:
pos = queue.pop()
fill(pos[0], pos[1])
for col in xrange(cols):
bfs(0, col)
bfs(rows-1, col)
for row in xrange(1, rows-1):
bfs(row, 0)
bfs(row, cols-1)
for row in xrange(rows):
for col in xrange(cols):
if board[row][col] == 'D':
board[row][col] = 'O'
elif board[row][col] == 'O':
board[row][col] = 'X'
In [18]:
s = 'aba'
for i in xrange(len(s)):
print s[:idd]
In [ ]:
class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max1, max2, max3 = [None]*3
L = len(nums)
while L > 0:
L -= 1
v = nums[L]
if max1 is None:
max1 = v
elif v > max1:
max1, max2, max3 = v, max1, max2
elif v == max1:
continue
else:
if max2 is None:
max2 = v
elif v > max2:
max2, max3 = v, max2
elif v == max2:
continue
else:
if max3 is None or v > max3:
max3 = v
return max1 if max3 is None else max3
In [ ]:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
counts = {}
ans, carry = 0, 0
for c in s:
if c in counts:
counts[c] += 1
else:
counts[c] = 1
for _, v in counts.items():
if v > 1:
if v % 2 == 0:
ans += v
else:
ans += (v-1)
carry = 1
else:
carry = 1
return ans+carry
In [ ]:
class Solution(object):
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
ans = []
for v in xrange(1, n+1):
if v % 3 == 0 and v % 5 == 0:
ans.append("FizzBuzz")
elif v % 3 == 0:
ans.append("Fizz")
elif v % 5 == 0:
ans.append("Buzz")
else:
ans.append(str(v))
return ans
In [ ]:
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
i, j, carry = len(num1), len(num2), 0
ans = ''
while i or j or carry:
digit = carry
if i:
i -= 1
digit += int(num1[i])
if j:
j -= 1
digit += int(num2[j])
ans += str(digit%10)
carry = digit/10
return ans[::-1]
In [ ]:
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def isLeave(node):
return node.left is None and node.right is None
def leftLeave(node):
if node:
if node.left and isLeave(node.left):
self.ans += node.left.val
leftLeave(node.left)
leftLeave(node.right)
leftLeave(root)
return self.ans
In [ ]:
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
def convert(n, nums):
L = len(nums)
if n > L:
return []
if n == 0:
return [0]
if n == 1:
return nums
else:
ans = []
for i in xrange(len(nums)):
for v in convert(n-1, nums[i+1:]):
ans.append(nums[i]+v)
return ans
times = []
for h in xrange(num+1):
m = num - h
minutes = convert(m, [1,2,4,8,16,32])
for hour in convert(h, [1,2,4,8]):
if hour < 12:
for minute in minutes:
if minute < 60:
if minute > 9:
times.append("{}:{}".format(hour, minute))
else:
times.append("{}:0{}".format(hour, minute))
return times
In [ ]:
class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
L, cnt, start = 1, 9, 1
while n > L * cnt:
n -= L * cnt
L += 1
cnt *= 10
start *= 10
start += (n-1) / L
return int(str(start)[(n-1)%L])
In [ ]:
class Solution(object):
def maxRotateFunction(self, A):
"""
:type A: List[int]
:rtype: int
"""
def F(nums):
S = 0
for i in xrange(len(nums)):
S += i * nums[i]
return S
S, L = sum(A), len(A)
ans = F(A)
last = ans
for n in A[::-1]:
now = last + S - L*n
if now > ans:
ans = now
last = now
return ans
In [ ]:
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
counts = {}
for c in s:
if c in counts:
counts[c] += 1
else:
counts[c] = 1
for i in xrange(len(s)):
if counts[s[i]] == 1:
return i
return -1
In [ ]:
class Solution(object):
def toHex(self, num):
"""
:type num: int
:rtype: str
"""
hexs = '0123456789abcdef'
if num < 0:
num += 0x100000000
ans = []
while num > 0:
ans.append(hexs[num%16])
num /= 16
return ''.join(ans[::-1]) if ans else '0'
In [ ]:
import collections
class Solution(object):
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
counts = collections.Counter(s)
for c in t:
if c in counts and counts[c] > 0:
counts[c] -= 1
else:
return c
In [ ]:
import collections
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
counts = collections.Counter(magazine)
for c in ransomNote:
if c in counts and counts[c] > 0:
counts[c] -= 1
else:
return False
return True
In [ ]:
class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left <= right:
mid = (left+right)/2
val = guess(mid)
if val is 0:
return mid
elif val is 1:
left = mid+1
else:
right = mid-1
In [ ]:
import collections
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
count = collections.Counter(nums1)
join = []
for n in nums2:
if n in count and count[n] > 0:
join.append(n)
count[n] -= 1
return join
In [ ]:
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1)&set(nums2))
In [ ]:
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
s = [c for c in s]
vowels = 'aeiouAEIOU'
left, right = 0, len(s)-1
while True:
while left < right and s[left] not in vowels:
left += 1
while left < right and s[right] not in vowels:
right -= 1
if left >= right:
return ''.join(s)
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
In [ ]:
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
return s[::-1]
In [ ]:
class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
cur = 0
while num > 3:
cur += num&3
num = num >> 2
return num == 1 and cur == 0
In [ ]:
class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
return n > 0 and 1162261467 % n == 0
In [ ]:
class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return n%4 != 0
In [ ]:
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
S = str.split()
pre, vals = {}, set()
if len(S) != len(pattern):
return False
for p, s in zip(pattern, S):
if p in pre:
if pre[p] != s:
return False
else:
if s in vals:
return False
else:
pre[p] = s
vals.add(s)
return True
In [ ]:
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.pre = []
S = 0
for n in nums:
S += n
self.pre.append(S)
def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
if i == 0:
return self.pre[j]
else:
return self.pre[j] - self.pre[i-1]
In [ ]:
class Solution(object):
def getHint(self, secret, guess):
"""
:type secret: str
:type guess: str
:rtype: str
"""
pre = {}
for n in guess:
if n in pre:
pre[n] += 1
else:
pre[n] = 1
A, B = 0, 0
for n1, n2 in zip(secret, guess):
if n1 == n2:
A += 1
if pre[n1] > 0:
pre[n1] -= 1
else:
B -= 1
elif n1 in pre and pre[n1] > 0:
B += 1
pre[n1] -= 1
return "{}A{}B".format(A, B)
In [ ]:
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
count, pos = 0, 0
for n in nums:
if n == 0:
count += 1
else:
nums[pos] = n
pos += 1
while count > 0:
nums[pos] = 0
pos += 1
count -= 1
In [ ]:
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left < right:
mid = (left+right)/2
if isBadVersion(mid):
right = mid - 1
else:
left = mid + 1
if isBadVersion(right):
return right
else:
return right+1
In [ ]:
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
while num > 1:
if num % 2 == 0:
num /= 2
elif num % 3 == 0:
num /= 3
elif num % 5 == 0:
num /= 5
else:
return False
return num == 1
In [ ]:
class Solution(object):
def addDigits(self, num):
"""
:type num: int
:rtype: int
"""
if num == 0:
return 0
return (num-1)%9+1
In [ ]:
class Solution:
# @param {TreeNode} root
# @return {string[]}
def binaryTreePaths(self, root):
paths = []
def helper(node, path):
if node:
val = str(node.val)
if node.left is None and node.right is None:
paths.append("->".join(path+[val]))
else:
helper(node.left, path+[val])
helper(node.right, path+[val])
helper(root, [])
return paths
In [ ]:
import string
import collections
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
wordList.add(endWord)
queue = collections.deque([(beginWord, 1)])
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in xrange(len(word)):
left, right = word[:i], word[i+1:]
for c in string.lowercase:
if c is not word[i]:
newWord = left+c+right
if newWord in wordList:
queue.append((newWord, steps+1))
wordList.remove(newWord)
return 0
In [ ]:
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
pre = {}
for c in s:
if c in pre:
pre[c] += 1
else:
pre[c] = 1
for c in t:
if c in pre:
if pre[c] > 0:
pre[c] -= 1
else:
return False
else:
return False
return sum(pre.values()) == 0
In [ ]:
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
def findMiddle(node):
fast, slow = node, node
while fast and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseNode(node):
if node is None or node.next is None: return node
node = node.next
prev = None
cur = node
while cur:
temp = cur
cur = cur.next
temp.next = prev
prev = temp
return prev
mid = findMiddle(head)
tail = reverseNode(mid)
while head and tail:
if head.val != tail.val:
return False
head = head.next
tail = tail.next
return True
In [ ]:
class Queue(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.stack.append(x)
def pop(self):
"""
:rtype: nothing
"""
self.stack = self.stack[1:]
def peek(self):
"""
:rtype: int
"""
return self.stack[0]
def empty(self):
"""
:rtype: bool
"""
return self.stack == []
In [ ]:
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
while n > 1:
if n % 2 == 1:
return False
n /= 2
return n == 1
In [ ]:
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
while node.next.next:
node.val = node.next.val
node = node.next
node.val = node.next.val
node.next = None
In [ ]:
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is None:
return root
temp = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(temp)
return root
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.
In [ ]:
class Stack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.Q = []
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.Q = [x] + self.Q
def pop(self):
"""
:rtype: nothing
"""
self.Q = self.Q[1:]
def top(self):
"""
:rtype: int
"""
return self.Q[0]
def empty(self):
"""
:rtype: bool
"""
return self.Q == []
In [ ]:
class Solution(object):
def computeArea(self, A, B, C, D, E, F, G, H):
width = [A, E, C, G]
height = [B, D, F, H]
width.sort()
height.sort()
total = (C-A)*(D-B) + (G-E)*(H-F)
if E > C or A > G or B > H or F > D:
return total
else:
if (A == width[1] and C == width[2]) and (B == height[1] and D == height[2]):
return (G-E)*(H-F)
if (E == width[1] and G == width[2]) and (F == height[1] and H == height[2]):
return (C-A)*(D-B)
w = width[1] - width[2]
h = height[1] - height[2]
return total - w * h
In [ ]:
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
L = len(nums)
index = {}
for i in xrange(L):
if nums[i] in index:
for j in index[nums[i]]:
if i - j <= k:
return True
index[nums[i]].append(i)
else:
index[nums[i]] = [i]
return False
In [ ]:
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(node, p, q) for node in (root.left, root.right))
if left and right:
return root
elif left:
return left
else:
return right
In [ ]:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
tail = head
head = head.next
tail.next = None
while head:
temp = head
head = head.next
temp.next = tail
tail = temp
return tail
In [ ]:
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
Ls, Lt = len(s), len(t)
if Ls != Lt:
return False
i, j = 0, 0
code = {}
vals = set()
while i < Ls and j < Lt:
if s[i] in code:
if code[s[i]] != t[j]:
return False
else:
if t[j] in vals:
return False
else:
code[s[i]] = t[j]
vals.add(t[j])
i += 1
j += 1
return True
In [ ]:
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
isPrime = [True] * max(n, 2)
isPrime[0], isPrime[1] = False, False
x = 2
while x * x < n:
if isPrime[x]:
p = x * 2
while p < n:
isPrime[p] = False
p += x
x += 1
return sum(isPrime)