# solutions2

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list.
``````

In [ ]:

class Solution(object):
"""
:rtype: ListNode
"""
return None
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if slow == fast:
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None

``````

## Integer to Roman

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
``````

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

``````

## Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".
``````

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]

``````

## Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique.
``````

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

``````

## Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
``````

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

``````

## Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]
``````

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

``````

## Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X
``````

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]

``````
``````

a
ab

``````

## Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
``````

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

``````

## Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example: Input: "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
``````

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

``````

## Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Example: n = 15, Return: [ "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz" ]
``````

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

``````

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2. Note: The length of both num1 and num2 is < 5100. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly.
``````

In [ ]:

class Solution(object):
"""
: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]

``````

## Sum of Left Leaves

Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
``````

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

``````

## Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent. Example: Input: n = 1 Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"] Note: The order of output does not matter. The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00". The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".
``````

In [ ]:

class Solution(object):
"""
: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

``````

## Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231). Example 1: Input: 3 Output: 3 Example 2: Input: 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
``````

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])

``````

## Rotate Function

Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow: F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. Calculate the maximum value of F(0), F(1), ..., F(n-1). Note: n is guaranteed to be less than 105. Example: A = [4, 3, 2, 6] F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
``````

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

``````

## First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2.
``````

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

``````

## Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used. Note: All letters in hexadecimal (a-f) must be in lowercase. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character. The given number is guaranteed to fit within the range of a 32-bit signed integer. You must not use any method provided by the library which converts/formats the number to hex directly.
``````

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'

``````

## Find the Difference

Given two strings s and t which consist of only lowercase letters. String t is generated by random shuffling string s and then add one more letter at a random position. Find the letter that was added in t.
``````

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

``````

## Ransom Note

``````

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

``````

## Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I'll tell you whether the number is higher or lower. You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it!
``````

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

``````

## Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order.
``````

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

``````

## Intersection of Two Arrays

Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. Note: Each element in the result must be unique. The result can be in any order.
``````

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))

``````

## Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Given s = "hello", return "holle". Example 2: Given s = "leetcode", return "leotcede".
``````

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

``````

## Reverse String

Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh".
``````

In [ ]:

class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
return s[::-1]

``````

## Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Follow up: Could you solve it without loops/recursion?
``````

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

``````

## Power of Three

Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion?
``````

In [ ]:

class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
return n > 0 and 1162261467 % n == 0

``````

## Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap. For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
``````

In [ ]:

class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return n%4 != 0

``````

## Word Pattern

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str. Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false. Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
``````

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
return True

``````

## Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to sumRange function.
``````

In [ ]:

class NumArray(object):
def __init__(self, nums):
"""
: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]

``````

## Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number. For example: Secret number: "1807" Friend's guess: "7810" Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.) Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B". Please note that both secret number and friend's guess may contain duplicate digits, for example: Secret number: "1123" Friend's guess: "0111" In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
``````

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)

``````

## Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.
``````

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):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left < right:
mid = (left+right)/2
right = mid - 1
else:
left = mid + 1
return right
else:
return right+1

``````

## Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number.
``````

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

``````

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime?
``````

In [ ]:

class Solution(object):
"""
:type num: int
:rtype: int
"""
if num == 0:
return 0
return (num-1)%9+1

``````

## Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: ["1->2->5", "1->3"]
``````

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

``````

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time Each intermediate word must exist in the word list For example, Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
``````

In [ ]:

import string
import collections
class Solution(object):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
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

``````

## Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false. Note: You may assume the string contains only lowercase alphabets.
``````

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

``````

Given a singly linked list, determine if it is a palindrome.
``````

In [ ]:

class Solution(object):
"""
: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
tail = reverseNode(mid)
return False
tail = tail.next
return True

``````

## Implement Queue using Stacks

Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.
``````

In [ ]:

class Queue(object):
def __init__(self):
"""
"""
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 == []

``````

## Power of Two

Given an integer, write a function to determine if it is a power of two.
``````

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

``````

## Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
``````

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

``````

## Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1
``````

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 Stack using Queues

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):
"""
"""
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 == []

``````

## Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure. Rectangle Area Assume that the total area is never beyond the maximum possible value of int.
``````

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:
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]

``````

## Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
``````

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

``````

## Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” _______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5 For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
``````

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):
"""
:rtype: ListNode
"""
tail.next = None
temp.next = tail
tail = temp
return tail

``````

## Isomorphic Strings

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. For example, Given "egg", "add", return true. Given "foo", "bar", return false. Given "paper", "title", return true.
``````

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]

i += 1
j += 1
return True

``````

## Count Primes

Description: Count the number of prime numbers less than a non-negative number, n.
``````

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)

``````