LinkedIn题
150. Evaluate Reverse Polish Notation
Difficulty: Medium
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", ""] -> ((2 + 1) 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Hide Company Tags LinkedIn
思路：很简单，用stack存数字，遇到符号就弹出两个计算，然后把结果放回去。注意：python中5/-11 = -1， -121/6=-21.注意这个细节
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
for i in tokens:
if i not in ['+','-','*','/']:
stack.append(int(i))
else:
n1, n2 = stack.pop(), stack.pop()
if i == '/':
if n2* n1 < 0 and n2 % n1 != 0:
stack.append(n2 / n1 + 1)
else:
stack.append(n2 /n1)
elif i == '*':
stack.append(n2 * n1)
elif i == '+':
stack.append(n2 + n1)
else:
stack.append(n2 - n1)
return stack[0]
65. Valid Number
- Difficulty: Hard
Validate if a given string is numeric.
Some examples:"0"=>true" 0.1 "=>true"abc"=>false"1 a"=>false"2e10"=>true
Note:It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
Update (2015-02-10):
The signature of theC++function had been updated. If you still see your function signature accepts aconst char *argument, please click the reload buttonto reset your code definition.
思路：每一个字母只可能是符号，数字，点，e这几种情况，所以只需要用flag判断清楚每种情况的限制就好，但是有很多Corner case，所以需要和面试官问清楚。
1，符号：可能在首位，也可能在e后面，其他位置都不对。不能在最后一位！符号可以是+或-
2，点：不能在e后面，如果在最后一位前面必须是数字，不能有两个点
3，数字：可以允许连续n个零在一开始
4，e：不能是最后一个，不能有两个，前面必须有数字
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
hasDigit, hasE, hasDot, hasSign = False, False, False, False
s = s.strip()
i = 0
while i < len(s):
if s[i] in ['-', '+']:
if (i > 0 and s[i-1] != 'e') or i == len(s) - 1:
return False
hasSign = True
i += 1
elif s[i] == '.':
if (i == len(s) - 1 and not hasDigit) or hasDot or hasE:
return False
hasDot = True
i += 1
elif s[i] == 'e':
if hasE or not hasDigit or i == len(s) -1:
return False
hasE = True
i+= 1
elif s[i].isnumeric():
hasDigit = True
i+=1
else:
return False
return hasDigit
311. Sparse Matrix Multiplication
- Difficulty: Medium
Given twosparse matricesAandB, return the result ofAB.
You may assume thatA's column number is equal toB's row number.
Example:
A = [
[ 1, 0, 0],
[-1, 0, 3]
]
B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]
| 1 0 0 | | 7 0 0 | | 7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |
Hide Company Tags
思路：其实就是慢慢理清楚矩阵相乘是怎么回事就可以了。如果矩阵2*3与3*3 相乘，那么得到的结果就是2*3矩阵。首先构造一个2*3矩阵，然后替换里面的数字就可以了。我们只关心1，0可以不用管。如果A中的col有1，那么这个1必须和B中的对应row中所有1相乘，加起来是所得的res[i][k]
class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if not A or not B:
return []
res = [[0 for _ in range(len(B[0]))] for _ in range(len(A))]
for i in range(len(A)):
for j, eA in enumerate(A[i]):
if eA:
for k, eB in enumerate(B[j]):
if eB:
res[i][k] += eA * eB
return res
简介写法：
class Solution(object):
def compress(self, matrix):
return [
[i, j, num]
for i, row in enumerate(matrix)
for j, num in enumerate(row) if num
]
def multiply(self, A, B):
(cpA, cpB), r = map(self.compress, (A, B)), [
[0] * len(B[0]) for i in xrange(len(A))]
[r[rowA].__setitem__(columnB, r[rowA][columnB] + numA * numB)
for rowA, columnA, numA in cpA
for rowB, columnB, numB in cpB if columnA == rowB]
return r
366. Find Leaves of Binary Tree
- Difficulty: Medium
Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
Example:
Given binary tree
1
/ \
2 3
/ \
4 5
Returns[4, 5, 3], [2], [1].
Explanation:
- Removing the leaves
[4, 5, 3]would result in this tree:
1
/
2
- Now removing the leaf
[2]would result in this tree:
1
- Now removing the leaf
[1]would result in the empty tree:
[]
Returns[4, 5, 3], [2], [1].
Hide Company Tags
# 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 findLeaves(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# def dfs(root, level):
# leave = True
# if root.left and root.left.val != '#':
# leave = False
# dfs(root.left, level)
# if root.right and root.right.val != '#':
# leave = False
# dfs(root.right, level)
# if leave:
# level.append(root.val)
# root.val = '#'
# res = []
# p = root
# while p and p.val != '#':
# l = []
# dfs(p, l)
# res.append(l)
# p = root
# return res
def helper(root, res):
if not root:
return -1
left = helper(root.left, res)
right = helper(root.right, res)
level = max(left, right) + 1
if len(res) == level:
res.append([])
res[level].append(root.val)
root.left = root.right = None
return level
res = []
helper(root, res)
return res
156. Binary Tree Upside Down
Add to List
Question
Editorial Solution
My Submissions
- Total Accepted: 19718
- Total Submissions:
- Difficulty: Medium
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree
{1,2,3,4,5},
1
/ \
2 3
/ \
4 5
return the root of the binary tree[4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1
confused what"{1,#,2,3}"means?> read more on how binary tree is serialized on OJ.
Hide Company Tags
思路：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return root of the upside down tree
def upsideDownBinaryTree(self, root):
# take care of the empty case
# if not root:
# return root
# # take care of the root
# l = root.left
# r = root.right
# root.left = None
# root.right = None
# # update the left and the right children, form the new tree, update root
# while l:
# newL = l.left
# newR = l.right
# l.left = r
# l.right = root
# root = l
# l = newL
# r = newR
# return root
# p = []
# while root:
# p.append(root)
# root = root.left
# if not p:
# return None
# new_r = p.pop()
# move = new_r
# while p:
# node = p.pop()
# r = node.right
# move.left = r
# node.left = None
# node.right = None
# move.right = node
# move = move.right
# return new_r
if not root or not root.left:
return root
def updown(root):
if not root or not root.left:
return root,root
lRoot,rMost = updown(root.left)
rMost.left = root.right
root.left=None
root.right=None
rMost.right = root
return lRoot,rMost.right
result,rMost=updown(root)
return result