|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
10/17 904. 水果成篮
滑动窗口l,r 记录当前水果
如果超过两种则滑动l 减少至两种
def totalFruit(fruits):
"""
:type fruits: List[int]
:rtype: int
"""
m = {}
ans = 0
l = 0
for r,v in enumerate(fruits):
m[v] = m.get(v,0)+1
if len(m)>2:
m[fruits[l]]-=1
if m[fruits[l]] == 0:
m.pop(fruits[l])
l+=1
ans = max(ans,r-l+1)
return ans
10/18 902. 最大为 N 的数字组合
如果n是k位的正数 那么对于小于k位的所有数都是满足的
m=len(digits) m+m2+…+m(k-1)
只需要考虑k位有多少小于n的数
对于n[i] digits中需要满足小于n[i] 如果有x个 那么后续也是接什么都行x*m^(k-1-i)
如果有digit中的数等于n[i] 则继续考虑n[i+1]
注意 如果是最后一位且n[k-1]在digits中 需要额外+1
def atMostNGivenDigitSet(digits, n):
"""
:type digits: List[str]
:type n: int
:rtype: int
"""
nstr = str(n)
s = set(digits)
k = len(nstr)
m = len(digits)
ans = 0
base = 1
for i in range(k-1):
base *= m
ans +=base
for i in range(k):
c = nstr[i]
x = 0
for d in digits:
if d<c:
x+=1
else:
break
ans += x*pow(m,k-1-i)
if c not in s:
break
if i==k-1:
ans+=1
return ans
10/19 1700. 无法吃午餐的学生数量
统计两类学生数量
遍历三明治 减去喜欢这个三明治学生一名
直至没有学生或三明治
def countStudents(students, sandwiches):
"""
:type students: List[int]
:type sandwiches: List[int]
:rtype: int
"""
n = len(students)
x = sum(students)
y = n-x
for i,v in enumerate(sandwiches):
if v==1:
if x==0:
return n-1-i
x-=1
else:
if y==0:
return n-1-i
y-=1
return 0
10/20 779. 第K个语法符号
对于第i层的第k个数
到了第i+1层会变成第2k-1,2k个数 其中2k-1与上一层k相同 2k则不同
def kthGrammar(n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
ans = 0
while k>1:
if k%2==0:
ans ^=1
k/=2
return ans
10/21 901. 股票价格跨度
单调栈 从后往前查看价格 如果遇到了比自己大的价格则停止
所以只需要单调递减栈即可 之前小于自己的价格必定不会被后续小于自己的价格识别到
st单调栈存放地址及数值(idx,value)
当前价格price 小于price的value都可以出栈 结果为当前idx-最先遇到的value大于自己的idx
class StockSpanner(object):
def __init__(self):
self.st = [(-1,float("inf"))]
self.idx = -1
def next(self, price):
"""
:type price: int
:rtype: int
"""
self.idx+=1
while price >= self.st[-1][1]:
self.st.pop()
self.st.append((self.idx,price))
return self.idx-self.st[-2][0]
10/22 1235. 规划兼职工作
将工作按结束时间从小到大排列
dp[i]记录截止前i个工作能获得的最大收益
第i-1份工作可以选择做 或者 不做
选择做则需要找到结束时间小于等于开始时间的位置
def jobScheduling(startTime, endTime, profit):
"""
:type startTime: List[int]
:type endTime: List[int]
:type profit: List[int]
:rtype: int
"""
n = len(startTime)
job = sorted(zip(startTime,endTime,profit),key = lambda x:x[1])
dp = [0]*(n+1)
li = sorted(endTime)
def find(r,v):
l = 0
while l<=r:
mid = (l+r)>>1
if li[mid]> v:
r = mid-1
else:
l = mid+1
return l
for i in range(1,n+1):
k = find(i,job[i-1][0])
dp[i] = max(dp[i-1],dp[k]+job[i-1][2])
return dp[n]
10/23
|