有閒來坐剪紙藝術公司 常考題
1. Two Sum
class Solution(object):
def twoSum(self, nums, target):
result, dic = [], {}
if not nums: return result
for i in range(len(nums)):
if (target - nums[i]) in dic:
result.append(dic[target - nums[i]])
result.append(i)
return result
else:
dic[nums[i]] = i
return result
7. Reverse Integer
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
large, small, s, nag = 2147483648, -2147483647, [], 0
for i in str(x): s.append(i)
if s[0] == '-':
nag = 1
s.append(s[0])
s.remove(s[0])
s = s[::-1]
ans = int("".join(s))
if ans > large or ans < small: return 0
else: return ans
21. Merge Two Sorted Lists
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 and not l2: return []
elif not l1: return l2
elif not l2: return l1
dummy = ListNode(0)
ptr = dummy
res = []
while l1 and l2:
if l1.val <= l2.val:
dummy.next = l1
l1 = l1.next
dummy = dummy.next
else:
dummy.next = l2
l2 = l2.next
dummy = dummy.next
if l1: dummy.next = l1
if l2: dummy.next = l2
return ptr.next
28. Implement strStr()
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
hl, nl = len(haystack), len(needle)
if nl == 0 : return 0
if hl == nl and needle in haystack: return 0
for i in range(hl-nl+1):
if needle in haystack[i:i+nl]: return i
return -1
70. Climbing Stairs
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
res = [1,1]
if n <= 1: return res[n]
for i in range(n+1):
if i > 1:
temp = res[0] + res[1]
res[0] = res[1]
res[1] = temp
return res[-1]
102. Binary Tree Level Order Traversal
# 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]]
"""
res, level, queue = [], [], []
if not root: return res
queue.append(root)
while queue:
it = range(len(queue))
for i in it:
pop = queue[0]
del queue[0]
level.append(pop.val)
if pop.left : queue.append(pop.left)
if pop.right: queue.append(pop.right)
res.append(level)
level = []
return res
Second solution:
from collections import deque
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res, q, level= [], deque([]), []
if not root: return res
q.append(root)
while q:
for i in range(len(q)):
temp = q.popleft()
level.append(temp.val)
if temp.left : q.append(temp.left)
if temp.right: q.append(temp.right)
res.append(level)
level = []
return res
104. Maximum Depth of Binary Tree
BFS:
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
level, queue = 1, []
if not root: return 0
queue.append(root)
while queue:
it = range(len(queue))
for i in it:
pop = queue[0]
del queue[0]
if pop.left : queue.append(pop.left)
if pop.right: queue.append(pop.right)
if queue: level += 1
return level
DFS - post order:
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
return max( self.maxDepth(root.left)+1, self.maxDepth(root.right)+1 )
DFS - second
class Solution(object):
def maxDepth(self, root):
global deep
deep = 0
if not root : return deep
def dfs(node, level):
global deep
if level > deep: deep = level
if node.left : dfs( node.left, level+1 )
if node.right : dfs( node.right, level+1 )
dfs(root, 1)
return deep
118. Pascal's Triangle
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
res, level = [], []
for i in range(numRows):
for j in range(i+1):
if j == 0 or j == i:
level.append(1)
else:
level.append(res[i-1][j]+ res[i-1][j-1])
res.append(level)
level = []
return res
Second solution:
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
res = []
if numRows <= 0: return res
for i in range(1, numRows+1):
if i < 3:
temp = [1] * i
else:
temp = []
for j in range(i):
if j == 0 or j == i-1:
temp.append(1)
else:
temp.append(res[i-2][j-1] + res[i-2][j])
res.append(temp)
return res
165. Compare Version Numbers
class Solution(object):
def compareVersion(self, version1, version2):
"""
:type version1: str
:type version2: str
:rtype: int
"""
v1, v2, s = [], [], 0
for i in range(len(version1)):
if version1[i] == '.':
v1.append("".join([version1[s:i]]))
s = i + 1
v1.append("".join([version1[s:]]))
s = 0
for j in range(len(version2)):
if version2[j] == '.':
v2.append("".join([version2[s:j]]))
s = j + 1
v2.append("".join([version2[s:]]))
for k in range(min(len(v1),len(v2))):
if int(v1[k]) > int(v2[k]): return 1
elif int(v1[k]) < int(v2[k]): return -1
if len(v1) > len(v2):
for i in range(len(v2), len(v1)):
if int(v1[i]) > 0:
return 1
elif len(v1) < len(v2):
for i in range(len(v1), len(v2)):
if int(v2[i]) > 0:
return -1
return 0
190. Reverse Bits
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res = []
while n:
temp = n%2
res.append(str(temp))
n /= 2
while len(res) < 32:
res.append(str(0))
ans, j = 0, 0
for i in range(len(res)-1, -1, -1):
ans += int(res[i]) * (2**j)
j += 1
return ans
191. Number of 1 Bits
class Solution(object):
def hammingWeight(self, n):
res = []
while n:
temp = n%2
res.append(str(temp))
n /= 2
while len(res) < 32:
res.append(str(0))
ans = 0
for i in range(len(res)):
if res[i] == '1':
ans += 1
return ans
206. Reverse Linked List
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return []
dummy = ListNode(0)
while head:
ne = head.next
head.next = dummy.next
dummy.next = head
head = ne
return dummy.next
237. Delete Node in a Linked List
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
257. Binary Tree Paths
# 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 binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res, path = [], []
if not root: return res
def dfs(node, path):
if not node: return
path.append(str(node.val))
dfs(node.left, path[:])
dfs(node.right, path[:])
if not node.left and not node.right:
res.append(path)
path = []
dfs(root, path)
for i in range(len(res)):
res[i] = "->".join(res[i])
return res
36. Valid Sudoku
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for i in xrange(9):
hs1,hs2,hs3=[0]*10, [0]*10, [0]*10
for j in xrange(9):
# check row
if board[i][j]!='.':
hs1[int(board[i][j])] += 1
if hs1[int(board[i][j])]>1: return False
# check column
if board[j][i] != '.':
hs2[int(board[j][i])] += 1
if hs2[int(board[j][i])]>1: return False
# check block
if board[(i/3)*3 + j/3][(i%3)*3 + j%3] != '.':
hs3[int(board[(i/3)*3 + j/3][(i%3)*3 + j%3])] += 1
if hs3[int(board[(i/3)*3 + j/3][(i%3)*3 + j%3])]>1: return False
return True
48. Rotate Image
總結: 先沿對角線對折, 接著沿最中間的列對折.
寫的時候先不要去想怎麼沿著斜線對折, 專心在如何print 出一個倒三角.
m = len(a)
n = len(a[0])
for i in range(m):
for j in range(n-i-1):
print [i][j]
-------------------
總結: 先沿對角線對折, 接著沿最中間的列對折.
寫的時候先不要去想怎麼沿著斜線對折, 專心在如何print 出一個倒三角.
m = len(a)
n = len(a[0])
for i in range(m):
for j in range(n-i-1):
print [i][j]
-------------------
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
def sw(a, b):
a, b = b, a
return a, b
le = len(matrix[0])
# fold slash
for i in range(le-1):
for j in range(le-i):
matrix[i][j], matrix[le-1-j][le-1-i] = sw( matrix[i][j], matrix[le-1-j][le-1-i] )
# fold middle in row
for i in range(le/2):
for j in range(le):
matrix[i][j], matrix[le-i-1][j] = sw(matrix[i][j], matrix[le-i-1][j])
69. Sqrt(x)
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
left, right = 0 , x/2 + 1
while left <= right:
mid = (left+right) / 2
sq = mid * mid
if sq == x: return mid
elif sq < x: left = mid + 1
else: right = mid - 1
return right
151. Reverse Words in a String
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
word = s.split()
word.reverse()
return " ".join(word)
215. Kth Largest Element in an Array
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums.sort()
return nums[-k]
236. Lowest Common Ancestor of a Binary Tree
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
238. Product of Array Except Self
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
size = len(nums)
output = [1] * size
left = 1
for x in range(size - 1):
left *= nums[x]
output[x + 1] *= left
right = 1
for x in range(size - 1, 0, -1):
right *= nums[x]
output[x - 1] *= right
return output
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix == [] or matrix[0] == []: return False
n = len(matrix[0])-1
m = 0
while m < len(matrix) and n >= 0:
if target == matrix[m][n]: return True
elif target > matrix[m][n]: m += 1
elif target < matrix[m][n]: n -= 1
return False
284. Peeking Iterator
class PeekingIterator(object):
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.ite = iterator
self.peekFlag = False
self.nextElement = None
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
if not self.peekFlag:
self.nextElement = self.ite.next()
self.peekFlag = True
return self.nextElement
def next(self):
"""
:rtype: int
"""
if not self.peekFlag:
return self.ite.next()
nextElement = self.nextElement
self.peekFlag = False
self.nextElement = None
return nextElement
def hasNext(self):
"""
:rtype: bool
"""
return self.peekFlag or self.ite.hasNext()
4. Median of Two Sorted Arrays
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
ln_1 = len(nums1)
ln_2 = len(nums2)
total_l = ln_1 + ln_2
cl_1, cl_2 = 0, 0
total = []
for i in range(total_l):
while cl_1 < ln_1 and cl_2 < ln_2:
if nums1[cl_1] <= nums2[cl_2]:
total.append(nums1[cl_1])
cl_1 += 1
else:
total.append(nums2[cl_2])
cl_2 += 1
if cl_1 < ln_1: total = total + nums1[cl_1:]
if cl_2 < ln_2: total = total + nums2[cl_2:]
return total[total_l/2] if total_l % 2 != 0 else (total[(total_l/2) - 1] + total[(total_l/2)]) / 2.0
221. Maximal Square
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix == [] or matrix[0] == []: return 0
m = len(matrix)
n = len(matrix[0])
dp = [[ 0 for i in range(n+1)] for j in range(m+1) ]
result = 0
for i in range(1,m+1):
for j in range(1,n+1):
if matrix[i-1][j-1] == "0":
dp[i][j] = 0
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
if dp[i][j] > result: result = dp[i][j]
#print dp
return result*result if result > 1 else result
42. Trapping Rain Water
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
left = [0 for i in range(len(height))]
right = [0 for i in range(len(height))]
ans = 0
for i in range( 1,len(height) ):
left[i] = max(left[i-1], height[i-1])
for j in range(len(height)-2, -1, -1):
right[j] = max(right[j+1], height[j+1])
for k in range(len(height)):
temp = min( left[k] , right[k] ) - height[k]
if temp > 0: ans += temp
return ans
留言
張貼留言