#### 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i in xrange(len(nums)):
if nums[i] not in dic:
dic[target-nums[i]] = i
else:
return [dic[nums[i]], i]


You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
node = ListNode(None)
carry = 0
while l1 and l2:
s = l1.val + l2.val + carry
node.next = ListNode(s % 10)
carry = s /10
l1 = l1.next
l2 = l2.next
node = node.next

while l1:
s = l1.val + carry
node.next = ListNode(s % 10)
carry = s / 10
l1 = l1.next
node = node.next
while l2:
s = l2.val + carry
node.next = ListNode(s % 10)
carry = s / 10
l2 = l2.next
node = node.next
node.next = ListNode(carry) if carry else None


#### 7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
rev = 0
negative = False
if x < 0:
negative = True
x = -x
while x:
rev = rev * 10 + x % 10
x = x / 10
if rev > (2**31) - 1:
return 0
return -rev if negative else rev


#### 9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
s = str(x)
length = len(s)
for i in range(length / 2):
if s[i] != s[length - i -1]:
return False
return  True


#### 12. Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
table = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD' ),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]
result = ''
while len(table) > 0:
(val, roman) = table[0]
if num < val:
table.pop(0)
else:
num -= val
result += roman
return result


#### 13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

{'M':1000, 'CM':900, 'D':500, 'CD':400, 'C':100,'XC':90, 'L':50, 'XL':40, 'X':10, 'IX':9, 'V':5, 'IV':4, 'I':1} 先观察罗马数字的特点，双字符的罗马数字比如XL的值为L-X的值， LXL+X， 而且没有VX这种写法。所以我们可以通过反向循环来解决。

class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
table = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
res, p = 0, 'I'
for i in s[::-1]:
if table[i] < table[p]:
res = res - table[i]
else:
res = res + table[i]
p = i
return res


#### 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
res = ''
for s in zip(*strs):
if reduce(lambda x,y: y if x==y else False,s):
res += s[0]
else:
break
return res


#### 19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type n: int
:rtype: ListNode
"""
for _ in range(0, n):
ptr2 = ptr2.next
if ptr2 is None:
while ptr2.next is not None:
ptr1 = ptr1.next
ptr2 = ptr2.next
ptr1.next = ptr1.next.next


#### 20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
dic = {')':'(', ']':'[', '}':'{'}
for c in s:
if c in dic.keys():
if len(stack) <= 0 or dic[c] != stack.pop():
return False
elif c in dic.values():
stack.append(c)
return len(stack) == 0


#### 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
node = ListNode(None)
while l1 and l2:
if l1.val < l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
while l1:
node.next = l1
l1 = l1.next
node = node.next
while l2:
node.next = l2
l2 = l2.next
node = node.next


#### 24. Swap Nodes in Pairs

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
while node and node.next:
next = node.next.next
node.next.next = node
temp = next and next.next
node.next = next.next if temp else next
node = next


#### 26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums[:] = list(set(nums))
nums.sort()
return len(nums)


#### 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
for i in range(nums.count(val)):
nums.remove(val)
return len(nums)


#### 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""

# cheating solution
# return haystack.find(needle)

# normal solution
for i in range(len(haystack) - len(needle) + 1):
for j in range(i, len(needle) + i):
if haystack[j] == needle[j-i]:
continue
else:
break
else:
return i
return -1


#### 35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
low = 0
high = len(nums) - 1
while low < high:
mid = low + (high - low) / 2
if nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid - 1
else:
return mid
return low + 1 if nums[low] < target else low


#### 46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

# cheating
# return map(list, itertools.permutations(nums))

# recursive
return [[n] + p for i, n in enumerate(nums)
for p in self.permute(nums[:i] + nums[i+1:])] or [[]]


#### 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[ [1,1,2], [1,2,1], [2,1,1] ]

class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

# list is unhashable in python 2
# history = set()
history = []
res = []

for i, n in enumerate(nums):
if n not in history:
history.append(n)
res += [[n] + p for p in self.permuteUnique(nums[:i] + nums[i+1:]) or [[]]]
return res


#### 50. Pow(x, n)

Implement pow(x, n).

class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1.0

x = 1/x if n < 0 else x
n = abs(n)
m = 1

while n > 1:
if n % 2:
m *= x
x *= x
n /= 2
return m * x


#### 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tempSum = 0
maxSum = nums[0]
for num in nums:
tempSum += num
if tempSum > maxSum:
maxSum = tempSum
if tempSum < 0:
tempSum = 0
return maxSum


#### 58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

class Solution(object):
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
lastlen = 0
length = len(s)
for i in range(length-1, -1 ,-1):
if s[i] == ' ':
if lastlen == 0:
continue
break
else:
lastlen += 1
return lastlen


#### 66. Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
res = []
carry = 1
for i in reversed(digits):
temp = (i + carry) % 10
res.insert(0, temp)
if temp == 0 and carry == 1:
carry = 1
else:
carry = 0
if carry:
res.insert(0, carry)
return res


Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

class Solution(object):
"""
:type a: str
:type b: str
:rtype: str
"""
res = ['' for i in range(max(len(a), len(b))+1)]
carry = 0
a_len = len(a)
b_len = len(b)
for i in range(len(res)):
p1 = int(a[a_len-i-1]) if i<a_len else 0
p2 = int(b[b_len-i-1]) if i<b_len else 0
s = p1 + p2 + carry
res[len(res)-1-i] = str(s%2)
carry = s/2
if res[0] == '0':
return ''.join(res[1:])
else:
return ''.join(res)


#### 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return b


#### 80. Remove Duplicates from Sorted Array II

What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
flag = 0
length = len(nums)
i = 1
while i < length:
if nums[i] == nums[i - 1]:
flag += 1
if flag > 1:
del nums[i]
i -= 1
length -= 1
else:
flag = 0
i += 1
return length


#### 83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
preNode = node
while node.next is not None:
node = node.next
if node.val == preNode.val:
preNode.next = node.next
else:
preNode = preNode.next


#### 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
ptr1 = m - 1
ptr2 = n - 1
ptr = m + n - 1
while ptr1 >= 0 and ptr2 >= 0:
if nums1[ptr1] > nums2[ptr2]:
nums1[ptr] = nums1[ptr1]
ptr1 -= 1
else:
nums1[ptr]  = nums2[ptr2]
ptr2 -= 1
ptr -= 1
while ptr2 >= 0:
nums1[ptr] = nums2[ptr2]
ptr -= 1
ptr2 -= 1


#### 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
\
2
/
3


return [1,3,2].

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def traversal(root):
if root is None:
return
traversal(root.left)
res.append(root.val)
traversal(root.right)
traversal(root)
return res


#### 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
elif p is None or q is None:
return False

if p.val==q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False


#### 101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
/ \
2   2
/ \ / \
3  4 4  3


But the following [1,2,2,null,3,null,3] is not:

    1
/ \
2   2
\   \
3    3


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
elif p is None or q is None:
return False

if p.val==q.val:
return self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
else:
return False

def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
return self.isSameTree(root.left, root.right)


#### 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7


return its level order traversal as:

[ [3], [9,20], [15,7] ]

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
res = []
level = []
this_count = 1
next_count = 0
queue = [root]
while queue:
current = queue.pop(0)
level.append(current.val)
this_count -= 1
if current.left:
queue.append(current.left)
next_count += 1
if current.right:
queue.append(current.right)
next_count += 1
if this_count == 0:
res.append(level)
level = []
this_count = next_count
next_count = 0
return res


#### 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1


#### 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
n=len(nums)
if not nums:
return None
mid=n/2
root=TreeNode(nums[mid])
root.left=self.sortedArrayToBST(nums[:mid])
root.right=self.sortedArrayToBST(nums[mid+1:])
return root


#### 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
return abs(self.getHeight(root.left) - self.getHeight(root.right)) <= 1 and \
self.isBalanced(root.left) and self.isBalanced(root.right)

def getHeight(self, root):
if root is None:
return 0
return max(self.getHeight(root.left), self.getHeight(root.right)) + 1


#### 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

• 如果root为空，深度为0。
• 如果root不为空：

• 如果左右子树都不为空，最小深度就是 1 + min(minDepth(left), minDepth(right))
• 如果左子树为空，最小深度就是 1 + minDepth(right)
• 如果右子树为空，最小深度就是 1 + minDepth(left)

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
elif root.left is None:
return 1 + self.minDepth(root.right)
elif root.right is None:
return 1 + self.minDepth(root.left)
return 1+min(self.minDepth(root.left),self.minDepth(root.right))


#### 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

          5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1


return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
from __builtin__ import sum as _sum
if root is None:
return False
stack = [root]
path_stack = [(root.val,)]

while len(stack):
node = stack.pop()
path_sum = _sum(path_stack.pop())
if node.left is None and node.right is None and path_sum == sum:
return True
if node.left is not None:
stack.append(node.left)
path_stack.append((path_sum, node.left.val))
if node.right is not None:
stack.append(node.right)
path_stack.append((path_sum, node.right.val))
return False


#### 118. Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]


Solution

class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0:
return []
res = [[1],]
for i in range(numRows-1):
temp = [1]
temp.extend([sum(p) for p in zip(res[i],res[i][1:])])
temp.append(1)
res.append(temp)
return res


#### 119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
res = [1]
for i in range(rowIndex):
temp = [1]
temp.extend([sum(p) for p in zip(res,res[1:])])
temp.append(1)
res[:] = temp
return res


#### 121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
minp = prices[0] if prices else 0
maxp = 0
for price in prices:
if price < minp:
minp = price
if maxp < (price - minp):
maxp = price - minp
return maxp


#### 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = 0
for i in nums:
n ^= i
return n


Note: X^X = 0; 0^X = X

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: bool
"""
return False
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False


#### 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

1) 使用快慢指针我们可以得到交点F
2) 假设慢指针这时走了L1+L2+x*c， 快指针走了L1+L2+y*c，( c=L2+L3, x为慢指针在圆内行进圈数， y为快指针行进圈数)
3) 因为快指针行进路程为慢指针的两倍，所以有
2*(L1+L2+x*c) = L1+L2+y*c
L1=(y-2*x-1)c+c-L2 可知L1的长度为圆周倍数和L3(c-L2)的和,所有若此时将一个指针置于S处，另一个指针置于F，再次相交所需的路程即为L1

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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


#### 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
\
2
/
3


return [1,2,3].

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def traversal(root):
if root is None:
return
res.append(root.val)
traversal(root.left)
traversal(root.right)
traversal(root)
return res


#### 153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
start , end = 0, len(nums)-1
while start < end:
mid = start + (end - start) / 2
if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid
return nums[start]


#### 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.


Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

class MinStack(object):

def __init__(self):
"""
"""
self.stack = []
self.min = 0

def push(self, x):
"""
:type x: int
:rtype: void
"""
if len(self.stack) == 0:
self.min = x
self.stack.append(self.min)
elif x <= self.min:
self.stack.append(self.min)
self.min = x
self.stack.append(x)

def pop(self):
"""
:rtype: void
"""
if self.top() == self.min:
x = self.stack.pop()
self.min = self.stack.pop()
return x
else:
return self.stack.pop()

def top(self):
"""
:rtype: int
"""
return self.stack[-1]

def getMin(self):
"""
:rtype: int
"""
return self.min

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()


#### 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3


1) A B 长度相同，遍历即可
2) A B 长度不同。同时遍历，当短链表指针遍历完后，指向长链表头结点。这时长链表的指针还有 二者长度差 个结点才能遍历完长链表。继续同时遍历，当长链表指针遍历完后，指向短链表的头结点。这时，短链表指针在长链表上已经遍历完 长度差 个结点，也就是说现在两个链表剩余遍历的结点数目相同，演化为情况1。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
while p != q:
p = p.next if p else headB
q = q.next if q else headA
return p


#### 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
start , end = 0, len(nums)-1
while (start + 1) < end:
mid = start + (end - start) / 2
if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
return mid
if nums[mid] > nums[mid - 1]:
start = mid + 1
else:
end = mid
if nums[start] > nums[end]:
return start
else:
return end


#### 167. Two Sum II - Input array is sorted

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(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i in xrange(len(numbers)):
if numbers[i] not in dic:
dic[target-numbers[i]] = i
else:
return [dic[numbers[i]] + 1, i + 1]


#### 168. Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
... 26 -> Z
27 -> AA
28 -> AB

class Solution(object):
def convertToTitle(self, n):
"""
:type n: int
:rtype: str
"""
res = []
while n != 0:
res.insert(0, chr((n - 1) % 26 + 65))
n = (n - 1) / 26
return ''.join(res)


#### 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Note:投票算法

class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
num, count = None, 0
for i in nums:
if count == 0:
num, count = i, 1
elif i == num:
count += 1
else:
count -= 1
return num


#### 171. Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
for index, value in enumerate(s[::-1]):
res += (ord(value)-64) * 26**index
return res


#### 189. Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:k], nums[k:] = nums[len(nums)-k:], nums[:len(nums)-k]


#### 191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
return list(bin(n)).count('1')


#### 202. Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
visited = set()
while n!=1:
if n in visited:
return False
temp = 0
for i in str(n):
temp += int(i)**2
n = temp
return True


#### 203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type val: int
:rtype: ListNode
"""
break
while node is not None:
if node.val == val:
pre.next = node.next
else:
pre = node
node = node.next


#### 205. 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 "foo", "bar", return false.

Given "paper", "title", return true.

class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dic = {}
sarr = list(s)
tarr = list(t)
if len(sarr) != len(tarr):
return False
for i in range(len(sarr)):
if sarr[i] not in dic:
if tarr[i] in dic.values():
return False
dic[sarr[i]] = tarr[i]
elif dic[sarr[i]] != tarr[i]:
return False
return True


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
return


#### 217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
return len(nums) != len(set(nums))


#### 219. 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.

class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
dic = {}
for i in range(len(nums)):
if nums[i] in dic and i - dic[nums[i]] <= k:
return True
dic[nums[i]] = i
return False


#### 226. Invert Binary Tree

Invert a binary tree.

     4
/   \
2     7
/ \   / \
1   3 6   9


to

     4
/   \
7     2
/ \   / \
9   6 3   1


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is not None:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root


#### 231. Power of Two

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

class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
return n != 0 and not n&(n-1)


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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: bool
"""
return True
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
return False
return True

def reverseList(self, node):
next = None
while node is not None:
temp = node.next
node.next = next
next = node
node = temp
return next


#### 235. 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).”

        &#95;&#95;&#95;&#95;&#95;&#95;&#95;6&#95;&#95;&#95;&#95;&#95;&#95;
/              \
___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.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if p.val > q.val:
p, q = q, p
while not (p.val <= root.val and root.val <= q.val):
root = root.left if q.val < root.val else root.right
return root


#### 237. 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.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next


#### 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
p = 1
n = len(nums)
res = []
for i in range(len(nums)):
res.append(p)
p = p * nums[i]
p = 1
for i in range(n-1,-1,-1):
res[i] = res[i] * p
p = p * nums[i]
return res


#### 242. 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.

class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return sorted(s) == sorted(t)


Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

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


#### 260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
import collections
dic = collections.Counter(nums)
res = []
for key in dic:
if dic[key] == 1:
res.append(key)
return res


class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = reduce(operator.xor, nums)
ans = reduce(operator.xor, (x for x in nums if x & xor & -xor))
return [ans, ans ^ xor]


#### 263. 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.

class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 1:
return True
if num < 2:
return False
if num == 2 or num == 3 or num == 5:
return True
if num % 2 == 0:
return self.isUgly(num / 2)
if num % 3 == 0:
return self.isUgly(num / 3)
if num % 5 == 0:
return self.isUgly(num / 5)

return False


#### 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2

class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
for i in range(len(nums)):
if i != nums[i]:
return i
return i + 1


#### 283. Move Zeroes

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.

class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
count = nums.count(0)
for i in range(count):
nums.remove(0)
nums.append(0)


#### 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, O(1) extra space.
• Your runtime complexity should be less than O(n2).
• There is only one duplicate number in the array, but it could be repeated more than once.

index: 0 1 2 3 4 5

value: 2 5 1 1 4 3


index: 0 1 2 3 4 5

value: 1 4 0 0 3 2


class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums);
slow, fast = nums[n-1], nums[nums[n-1]-1]
while slow != fast:
slow = nums[slow-1]
fast = nums[nums[fast-1]-1]

slow = n;
while slow != fast:
slow = nums[slow-1];
fast = nums[fast-1];
return slow;


#### 290. 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.

class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
dic = {}
parr = list(pattern)
sarr = str.split()
if len(parr) != len(sarr):
return False
for i in range(len(parr)):
if parr[i] not in dic:
if sarr[i] in dic.values():
return False
dic[parr[i]] = sarr[i]
elif dic[parr[i]] != sarr[i]:
return False

return True


#### 292. 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.

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


#### 303. 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.


sumRange()方法会多次调用，所以在构造实例时多下功夫。

class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = list(nums)
for i in range(1,len(nums)):
nums[i] += nums[i-1]
self.numsSum = nums

def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
return self.numsSum[j]-self.numsSum[i]+self.nums[i]


#### 319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3.

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

class Solution(object):
def bulbSwitch(self, n):
"""
:type n: int
:rtype: int
"""
import math
return int(math.sqrt(n))


#### 326. Power of Three

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

class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
if n <= 0:
return False
return 3**round(math.log(n,3)) == n


#### 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

1(odd) 2(even) 3 4 5 NULL

temp = even.next even.next = even.next.next # 1(odd) 2(even) 4 5 NULL temp.next = odd.next # 3(temp) 2(even) odd.next = temp # 1(odd) 3(temp) 2(even) 4 5 NULL 移动odd even指针 odd = odd.next even = even.next

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
return None

while even and even.next:
temp = even.next
even.next = even.next.next
temp.next = odd.next
odd.next = temp

odd = odd.next
even = even.next



#### 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = [0]
for i in range(1,num+1):
if i&1 == 0:
result.append(result[i/2])
else:
result.append(result[i/2]+1)
return result


#### 342. 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?

$S_n=\sum_{n=1}^\infty4^{n-1}$ $4S_n-S_n=4^n-1$

class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
return num > 0 and (num & (num - 1)) == 0 and (num - 1) % 3 == 0


#### 344. Reverse String

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

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


#### 345. 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".

class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
vowel = ['a', 'e', 'i', 'o', 'u']
vowel.extend(''.join(vowel).upper())
ptr1 = 0
ptr2 = len(s) - 1
l = list(s)
while ptr1 < ptr2:
if l[ptr1] not in vowel:
ptr1  += 1
if l[ptr2] not in vowel:
ptr2 -= 1
if l[ptr1] in vowel and l[ptr2] in vowel:
l[ptr1], l[ptr2] = l[ptr2], l[ptr1]
ptr1 += 1
ptr2 -= 1
return ''.join(l)


#### 349. 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.

class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ return list(set(nums1).intersection(set(nums2)))

#### 350. 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].

class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
res = []
m, n = len(nums1), len(nums2)
i, j = 0, 0
while i < m and j < n:
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
res.append(nums1[i])
i += 1
j += 1
return res


#### 357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

class Solution(object):
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
if n==0:
return 1
res = 10
m = 9
for i in range(1, n):
m *= (10-i)
res += m
return res


#### 367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
for i in xrange(1, num+1):
temp = i**2
if temp>num:
break
if temp==num:
return True
return False


#### 371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
MAX_INT = 0x7FFFFFFF
MIN_INT = 0x80000000
while b:
carry = a & b
a = (a ^ b) % MASK
return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)


#### 374. 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!


Example:

n = 10, I pick 6.

Return 6.

# The guess API is already defined for you.
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
low = 1
high = n
while low <= high:
middle = low + (high - low) / 2
res = guess(middle)
if res > 0:
low = middle + 1
elif res < 0:
high = middle - 1
else:
return middle


#### 383. Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
return not (collections.Counter(ransomNote) - collections.Counter(magazine))


#### 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();


Solution

import random

class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type size: int
"""
self.nums = nums

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
nums = self.nums[:]
random.shuffle(nums)
return nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()


#### 387. 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.


Note: You may assume the string contain only lowercase letters.

class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
from collections import Counter
dic = Counter(s)
for i in range(len(s)):
if dic[s[i]] == 1:
return i
return -1


#### 389. 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.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

class Solution(object):
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
res = 0
for c in s+t:
res = res ^ ord(c)
return chr(res)


#### 392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
p1, p2= 0, 0
len1, len2 = len(s), len(t)
while p1 < len1 and p2 < len2:
if s[p1] == t[p2]:
p1 += 1
p2 +=1
return p1 == len1


#### 396. 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.

class Solution(object):
def maxRotateFunction(self, A):
"""
:type A: List[int]
:rtype: int
"""
res = 0
length = len(A)
array_sum = sum(A)
for i in range(length):
res += i*A[i]
maxres = res
for i in range(length):
res += array_sum - A[length-i-1] * length
if res > maxres:
maxres = res
return maxres


#### 400. 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.

Solution

class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
n -= 1
for digits in range(1, 11):
first = 10**(digits - 1)
if n < 9 * first * digits:
return int(str(first + n/digits)[n%digits])
n -= 9 * first * digits


#### 404. 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.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
total = 0
if root.left is not None and root.left.left is None and root.left.right is None:
total = total + root.left.val + self.sumOfLeftLeaves(root.right)
else:
total = total + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)


#### 405. 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.


Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"

class Solution(object):
def toHex(self, num):
"""
:type num: int
:rtype: str
"""
hex_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
res = []
for _ in range(8):
res.insert(0, hex_list[num & 0b1111])
num = num >> 4
return ''.join(res).lstrip('0') or '0'


#### 409. 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.

class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
from collections import Counter
dic = Counter(s)
count = sum(map(lambda v: v-1 if v % 2 else v, dic.values()))
if count < len(s):
count += 1
return count


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.

class Solution(object):
"""
:type num1: str
:type num2: str
:rtype: str
"""
i = 0
res = []
carry = 0
len1 = len(num1)
len2 = len(num2)
length = max(len1, len2)
while i < length:
val1 = num1[len1-i-1] if len1-i-1 >= 0 else '0'
val2 = num2[len2-i-1] if len2-i-1 >= 0 else '0'
val = ord(val1) + ord(val2) + carry - 96
if val > 9:
carry = val / 10
val = val % 10
else:
carry = 0
res.insert(0, chr(val+48))
i += 1
if carry != 0:
res.insert(0, chr(carry+48))
return ''.join(res)