4.1 携程算法笔试
两道编程题：
1.找出数组中连续子数组的和等于n的字数组的数量
直接用滑动窗口，但是只A了80%，不知道是怎么回事
arr=[int(x) for x in input().split(',')]
n=int(input())
left=0
right=0
h=arr[left]
res=0
l=len(arr)-1
while right<l:
while right<l and h<n:
right+=1
h += arr[right]
if h==n:
res+=1
h -= arr[left]
left += 1
while left<=right and h>n:
h-=arr[left]
left+=1
if h==n:
res+=1
if right + 1<l:
right += 1
h += arr[right]
print(res) 第2题，有n个果盘，每个果盘里有0个和多个苹果和梨，先要求尽可能多的选择果盘，使得苹果数和梨的数量不多于m和n个
输入：
# a,ppap,ap,aaappa,p 2 3 其中a代表苹果，p代表梨，果盘用逗号隔开，最后是m和n 思路是动态规划，如果第i个果盘放入不会超出限制，则dp[i]=dp[i-1]+1,dp[i]表示在0-i个果盘中，最大的组合数 用三个数组来动态保存组合数，苹果数，梨数，也是只得了83%，有大佬可以看看问题在哪儿
s=input().split()
arr=s[0].split(',')
arr_t=[]
for i in range(len(arr)):
tem=arr[i]
a=0
p=0
for j in range(len(tem)):
if tem[j]=='a':
a+=1
else:
p+=1
arr_t.append([a,p])
arr=arr_t
m=int(s[1])
n=int(s[2])
l=len(arr)+1
dpa=[0]*l
dpp=[0]*l
dp=[0]*l
res=0
for i in range(len(arr)):
if arr[i][0]<=m and arr[i][1]<=n:
dp[i+1]=1
for i in range(1,l):
if dp[i]==0:
# 果盘不能放入
dp[i] = dp[i - 1]
dpa[i] = dpa[i - 1]
dpp[i] = dpp[i - 1]
else:
# 果盘能放入，遍历之前的结果，找到最大的组合
max_t=dp[i]
for j in range(i):
if dpa[j] + arr[i-1][0] <= m and dpp[j] + arr[i-1][1] <= n:
if dp[j] + 1>max_t:
dp[i] = dp[j] + 1
dpa[i] = dpa[j] + arr[i-1][0]
dpp[i] = dpp[j] + arr[i-1][1]
max_t=dp[j] + 1
dp[i]=max_t
res=max(res,dp[i])
print(res)
# a,ppap,ap,aaappa,p 2 3
