LC
刷题顺序按照AC率由高到低，没错，我就是这么油！
import collections
class Solution(object):
def canPermutePalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
dic = collections.defaultdict(int)
for c in s:
dic[c] += 1
tmp = 0
for k in dic:
if dic[k]%2:
tmp += 1
return tmp == 1 or tmp == 0
args = ["code"]
s = Solution()
ans = s.canPermutePalindrome(*args)
print(ans)
Pokeman大神用counter教我做人。
import collections
class Solution(object):
def canPermutePalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
return sum(v % 2 for v in collections.Counter(s).values()) < 2
args = ["code"]
s = Solution()
ans = s.canPermutePalindrome(*args)
print(ans)
P2 . Maximum Depth of Binary Tree
# 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
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left, right) + 1
典型的dfs题目，visit每一个Node，然后把value加起来。区别在于需要先build一下map因为subordinates只包括id不包括object。
class Solution(object):
def getImportance(self, employees, id):
"""
:type employees: Employee
:type id: int
:rtype: int
"""
emap = {e.id: e for e in employees}
s, res = [emap[id]], 0
while s:
tmp = s.pop()
res += tmp.importance
for sub in tmp.subordinates:
s.append(emap[sub])
return res
P4. Flood Fill
一道2D matrix 的search 问题。我用了一个visit来存被渲染过的， 避免重复访问。
class Solution(object):
def floodFill(self, image, sr, sc, newColor):
"""
:type image: List[List[int]]
:type sr: int
:type sc: int
:type newColor: int
:rtype: List[List[int]]
"""
visited = set()
ogColor = image[sr][sc]
stack = [(sr, sc)]
while stack:
tmp = stack.pop()
visited.add(tmp)
r, c = tmp[0], tmp[1]
image[r][c] = newColor
for i, j in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
if 0 <= i < len(image) and 0 <= j < len(image[0]) \
and image[i][j] == ogColor and (i, j) not in visited:
stack.append((i, j))
return image
大神的recursively DFS 答案，很有意思
class Solution(object):
def floodFill(self, image, sr, sc, newColor):
rows, cols, orig_color = len(image), len(image[0]), image[sr][sc]
def traverse(row, col):
if (not (0 <= row < rows and 0 <= col < cols)) or image[row][col] != orig_color:
return
image[row][col] = newColor
[traverse(row + x, col + y) for (x, y) in ((0, 1), (1, 0), (0, -1), (-1, 0))]
if orig_color != newColor:
traverse(sr, sc)
return image
吴波会考这种题？！ 我不信。
class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
s = s[::-1]
return sum([ (ord(s[i]) - 64)*26**i for i in range(len(s))])
args = ['AB']
s = Solution()
ans = s.titleToNumber(*args)
print(ans)
P6. Valid Anagram
py黑魔法。
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return collections.Counter(s)==collections.Counter(t)
P7. Roman to Integer
这道题有点恶心，不想写，先抄个以前的答案放在介里！拿到面试了在写一遍哈！
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
table = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
r = 0
for i in range(len(s)-1):
val = table[s[i]]
if val >= table[s[i+1]]:
r += val
else:
r -= val
r += table[s[len(s)-1]]
return r
哎哟，太久没写。都快要忘咯！
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return None
tail = None
while head:
tmp = head.next
head.next = tail
tail = head
head = tmp
return tail
再写一个recursively的吧。
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return None
self.root = None
self.helper(head, head.next)
return self.root
def helper(self, pre, cur):
if not cur:
self.root = pre
return
next = cur.next
cur.next = pre
self.helper(cur, next)
P9. Best Time to Buy and Sell Stock
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
minVal = prices[0]
res = 0
for p in prices:
res = max(res, p - minVal)
minVal = min(p, minVal)
return res
P10. Happy Number
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
memo = set()
while n not in memo and n!=1:
memo.add(n)
n = sum(map(lambda x: x**2, map(int, list(str(n)))))
return n==1
P11. Two Sum
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i, num in enumerate(nums):
if target - num not in dic:
dic[num] = i
else:
return [dic[target - num], i]
P13. Word Pattern
主要是要记得建立双向hash map
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
p2w = {}
w2p = {}
words = str.split()
p = list(pattern)
if len(words) != len(p):
return False
pmap = zip(p, words)
for p, w in pmap:
if p in p2w and p2w[p] != w:
return False
if w in w2p and w2p[w] != p:
return False
p2w[p] = w
w2p[w] = p
return True
args = ['abba', "dog dog dog dog"]
s = Solution()
ans = s.wordPattern(*args)
print(ans)
P14. Min Stack
这道题主要是要注意各种corner case吧。
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.s = []
self.m = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.s.append(x)
if not self.m or x <= self.m[-1]:
self.m.append(x)
def pop(self):
"""
:rtype: void
"""
tmp = self.s.pop()
if self.m and tmp == self.m[-1]:
self.m.pop()
return tmp
def top(self):
"""
:rtype: int
"""
return self.s[-1] if self.s else None
def getMin(self):
"""
:rtype: int
"""
return self.m[-1] if self.m else None
P15. Valid Palindrome
'A'.isalnum() 用来判断是否是字母或者数字。
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
l, r = 0, len(s) - 1
while l<r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True