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]
2. Add Two Numbers
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):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
node = ListNode(None)
head = node
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
return head.next
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的值，
LX为L+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
我们使用两个指针第一个指针先走 n 步，然后两个指针一起循环。第一个指针到达链表的尾部时，第二个指针正处于链表的倒数第 n 个结点。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
ptr1 = head
ptr2 = head
for _ in range(0, n):
ptr2 = ptr2.next
# remove head node
if ptr2 is None:
return head.next
while ptr2.next is not None:
ptr1 = ptr1.next
ptr2 = ptr2.next
ptr1.next = ptr1.next.next
return head
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)
head = node
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
return head.next
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
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):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
node = head
if head is None or head.next is None:
return head
head = head.next
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
return head
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] ]
参考https://discuss.leetcode.com/topic/17277/one-liners-in-python
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
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
class Solution(object):
def addBinary(self, a, b):
"""
: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
Follow up for "Remove Duplicates":
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):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
node = head
preNode = node
while node.next is not None:
node = node.next
if node.val == preNode.val:
preNode.next = node.next
else:
preNode = preNode.next
return head
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
将101的解法稍微改了改
# 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
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
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):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None:
return False
slow = head
fast = head
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):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
slow = fast = head
hasCycle = False
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
hasCycle = True
slow = head
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):
"""
initialize your data structure here.
"""
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
利用双指针进行遍历，当都为None(同时遍历至链表终点)，或结点相同时停止。
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):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p, q = headA, headB;
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
visited.add(n)
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):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if head is None:
return head
while head.val == val:
pre = head
head = head.next
if head is None:
break
node = head
while node is not None:
if node.val == val:
pre.next = node.next
else:
pre = node
node = node.next
return head
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 "egg", "add", return true.
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
206. Reverse Linked List
Reverse a singly linked list.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return
link = head.next
head.next = None
while link:
temp = link.next
link.next = head
head = link
link = temp
return head
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)
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
我们使用双指针来寻找链表的中点，满指针每次前进 1 ，快指针每次前进 2。终止条件为快指针下一次指向 NULL
对于拥有奇数个元素的链表如
1->2->3->NUll 慢指针最终指向 2
对于拥有偶数个元素的链表ru
1->2->3->4->NULL 慢指针最终指向 2
下一步，我们将慢指针的下一个结点作为头结点的链表部分反转，之后逐个比较这两部分的元素。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return True
slow, fast = head, head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
rhead = self.reverseList(slow.next)
while rhead is not None:
if head.val != rhead.val:
return False
head = head.next
rhead = rhead.next
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).”
_______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.
# 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)
258. Add Digits
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):
def addDigits(self, num):
"""
: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
高端解法
首先我们对nums中的所有元素进行异或，题目已知这堆数字中只有两个数字仅出现一次，且这两个数字不同，其余数字均出现两次。所以我们相当于得到了这两个数字的异或结果xor。现在我们需要对这两个数字进行分离。xor & -xor可以得到xor从低位向高位，第一个非0位所对应的数字(xor = 10100, -xor=1100则xor & -xor = 100)。我们知道xor中为1的那一位是两个数字中不同的那一位(同0异1)。所以可以根据xor & -xor的结果来分离这两个数字了。当然其他的数字根据此条件也会分为两类，不过这并不影响，因为他们会出现两次。
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
首先我们对所有元素的值减1，然后将他们看做指针。
index: 0 1 2 3 4 5
value: 1 4 0 0 3 2
我们必须选择最后一个元素当做链表的起点，因为不会有任何的元素指向它。剩下要做的就是在这个链表中找到环的起点[LeetCode 142]。
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):
"""
initialize your data structure here.
: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.
对于第K盏灯，只有在遍历次数为K的约数时，才会改变状态。所以，K有偶数个约数时，最终状态为off;K有奇数个约数时，最终状态为on。约数成对出现，除非它有两个相同的约数(完全平方数)。总共有n盏灯，则一定有sqrt(n个数(向下取整)能够完全平方，即有 int(sqrt(n)) 盏灯为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 2 3 4 5 NULL
我们可以把1 2这部分看做已经排好的，使用两个指针分别排好部分的最后一个奇数，最后一个偶数。
1(odd) 2(even) 3 4 5 NULL
容易知道我们接下来交换结点，变成这个样子1 3(odd) 2 4(even) 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):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
odd = head
even = head.next
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
return head
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?
先推导一个公式
但是并不能只从这一条来判断，因为能整除3的还有7-1,10-1 ...
我们还需要加上一个条件num & (num-1)= 0，因为4^n一定是2^n
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])
排列组合问题：一个 n 位数，没有重复数字的概率为 9 * 9 * 8 ...
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
MASK = 0x100000000
while b:
carry = a & b
a = (a ^ b) % MASK
b = (carry<<1) % 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.
# @param num, your guess
# @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
首先2的31次方为 2147483648，我们可以分 10 个区间（0-9, 10-99,100-999...）。通过计算出每个区间有多少个数字，可以判断出 ｎ 落在哪个区间中。比如第四个区间，这是由４位数组成的区间，通过排列组合的知识可以得出这个区间一共有 9×10×3 个数字，有 9×10×3×4位数字。再去判断 n 具体在哪个数字内
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)
return total
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
415. Add Strings
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):
def addStrings(self, num1, num2):
"""
: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)