首页 > 4.1 携程算法笔试
头像
不喜欢刷题的小y
编辑于 2021-04-20 20:27
+ 关注

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



全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐