yp 1-10
1 139 word break
https://leetcode.com/problems/word-break/
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
dp = [False]*len(s)
for i in range(len(s)):
for j in range(i,len(s)):
if i==0 and s[i:j+1] in wordDict:
dp[j] = True
elif dp[i-1]==True and s[i:j+1] in wordDict:
dp[j] = True
return dp[-1]
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
dp = [False]*(len(s)+1)
dp[0]=True
for i in range(len(s)+1):
for w in wordDict:
l = len(w)
if l<=i and s[i-l:i]==w:
dp[i] = dp[i-l] or dp[i]
return dp[-1]
2 merge intervals 扫描线算法，没什么好说的。
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
times = []
for s,e in intervals:
times.append((s,0))
times.append((e,1))
times.sort()
s = []
res = []
for t in times:
if t[1]==0:
s.append(t)
else:
tmp = s.pop()
if not s:
res.append([tmp[0], t[0]])
return res
#[1,6],[8,10],[15,18]
intervals = [[1,3],[2,6],[8,10],[15,18]]
so = Solution()
a = so.merge(intervals)
print(a)
3 generate parenthesis
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.dfs(n, n, '', res)
return res
def dfs(self, l, r, cur, res):
if l<0 or r<0:
return
if l==0 and r==0:
res.append(cur)
self.dfs(l-1, r, cur+'(', res)
if r>l:
self.dfs(l, r-1, cur+')', res)
so = Solution()
ans = so.generateParenthesis(4)
print(ans)
4 ，输入一个string，全部都是小写，然后把其中的某些变成大写，输出all combinations。follow up是问有多少种可能，我答的是n的阶乘，现在一想发现是2的n次方
class Solution(object):
def shift(self, s):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.dfs(0, s, '', res)
return res
def dfs(self, i, s, cur, res):
if i==len(s):
res.append(cur)
return
self.dfs(i+1, s, cur+s[i].upper(), res)
self.dfs(i+1, s, cur+s[i], res)
s = 'abc'
so = Solution()
a = so.shift(s)
print(a)
5 224 basic calculator 每天写一遍basic calculator有益于身心健康。
class Solution(object):
def basicCaculator(self, s):
"""
:type n: int
:rtype: List[str]
"""
num, nums, ops = 0, [0], []
s = s + '#'
for i in range(len(s)):
if s[i] in '0123456789':
num += num*10 + int(s[i])
else:
if i>0 and s[i-1] not in '+-*/()':
nums.append(num)
num = 0
if s[i] in '+-*/':
if ops and ops[-1] in '*/':
y, x, op = nums.pop(), nums.pop(), ops.pop()
nums.append(self.applyOps(x, y, op))
ops.append(s[i])
elif s[i]=='(':
ops.append(s[i])
elif s[i]==')':
while ops[-1]!='(':
y, x, op = nums.pop(), nums.pop(), ops.pop()
nums.append(self.applyOps(x, y, op))
ops.pop()
while ops:
y, x, op = nums.pop(), nums.pop(), ops.pop()
nums.append(self.applyOps(x, y, op))
return nums[-1]
def applyOps(self, x, y, op):
if op=='+':
return x + y
elif op=='-':
return x - y
elif op=='*':
return x * y
else:
if x//y<0 and x%y:
return x//y+1
else:
return x//y
s = '1*(2-3)'
so = Solution()
a = so.basicCaculator(s)
print(a)
6 Integer to English Words 电面没做过的，应该现场来不及写完吧，讲道理是这样的。
class Solution(object):
def __init__(self):
self.less20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
self.tens = ["","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
self.thousands = ["","Thousand","Million","Billion"]
def numberToWords(self, num):
"""
:type num: int
:rtype: str
"""
res = ''
index = 0
while num:
res = self.helper(num%1000) + ' ' + self.thousands[index] + ' ' + res
index += 1
num = num//1000
return res
def helper(self, num):
res = ''
if num>=100:
res = self.less20[num//100] + ' ' + 'Hundred'
num = num%100
if num >=20:
res = res + (' ' if res else '') + self.tens[num//10] + (' ' if self.tens[num//10] else '') + self.less20[num%10]
else:
res = res + (' ' if res else '') + self.less20[num]
return res
num = 2111111121
so = Solution()
a = so.numberToWords(num)
print(a)
7 Write a function that takes two arguments, a list of words and an integer n, and returns the nth most common word in the list.
e.g. f(['cat', 'dog', 'cat'], 1) => 'cat' (the 1st most common word) f(['cat', 'dog', 'cat'], 2) => 'dog' (the 2nd most common word)
奉献给大家
import collections
class Solution(object):
def kthcommon(self, words, k):
"""
:type wrods: List[str]
:type k: int
:rtype: str
"""
return collections.Counter(words).most_common(k)[k-1][0]
words = ['cat', 'dog', 'cat']
so = Solution()
a = so.kthcommon(words, 2)
print(a)
8 longest-consecutive-sequence
import collections
class Solution(object):
def longest_consecutive_sequence(self, nums):
s = set(nums)
res = 0
for num in nums:
if (num-1) not in s:
tmp = 0
while num in s:
tmp += 1
num += 1
res = max(res, tmp)
return res
nums = [100, 4, 200, 1, 3, 2]
so = Solution()
a = so.longest_consecutive_sequence(nums)
print(a)
9 电面45分钟
Input 2D平面四个点 第一问判断是不是一个square
不一定要跟x轴 y轴平行 (Square 可以旋转)
代码大致上像是:
struct Point {
double x, y;
Point(double x_, double y_) : x(x_), y(y_) {}
};
bool isSquare(con****st vector<Point>& points) {
...
}
不会做！碰到我就跪地求饶好啦！
class Solution(object):
def ifSquare(self, points):
q = points.pop()
res = []
for p in points:
dist = (abs(p[0]-q[0])**2 + abs(p[1]-q[1])**2)**(0.5)
res.append((dist, p))
m = max(res)
res.remove(m)
x, y = res[0], res[1]
print(m, x, y, (x[0]**2 + y[0]**2)**(0.5))
if x[0]!=y[0] or m[0]!=(x[0]**2 + y[0]**2)**(0.5) or\
m[0]!=(abs(x[1][0]-y[1][0])**2 + abs(x[1][1]-y[1][1])**2)**(0.5):
return False
return True
第二问 是 return 四个点围成的形状: "rectangle", "square", "diamond", “parallelogram",. ...
10 最后来说coding题吧，就是一个dart game，然后有一群possible scores,然后给你一个candidate score，问这个candidate score是不是可能的得分。For example:possible scores: [3,5,3,3,5] (有duplicates，unsorted，可能有很多很多possible score，不一定只有3和5) candidate score: 6, yes candidate score: 11, yes candidate score: 7, no candidate score: 0, yes 我感觉这题有点像leetcode combination sum那题，但是那题是用回溯求出所有可能解，这题是判断是否可以，想写个recursion的方法，试了几次还是弄不好，求各位大神帮忙。
class Solution(object):
def dartGame(self, scores, target):
"""
:type scores: List[int]
:rtype: Bool
"""
scores.sort()
return self.dfs(scores, target)
def dfs(self, scores, target):
if target==0:
return True
if target<0 or not scores:
return False
for i in range(len(scores)):
if scores[i]<=target:
if self.dfs(scores[i+1:], target-scores[i]):
return True
return False
scores = [3,5,3,3,5]
target = 7
so = Solution()
a = so.dartGame(scores, target)
print a