首页 > 京东笔试算法题
头像
机器也不想学习好吧
发布于 2021-08-21 20:54
+ 关注

京东笔试算法题

1.前缀切分后0与1比例相同
import sys

n = int(sys.stdin.readline())
s = [int(xfor x in list(sys.stdin.readline().strip())]

def solution(s):
    from collections import defaultdict
    dic = defaultdict(int)
    n = len(s)

    def gys(x1x2):
        if x1 == 0 and x2 > 0:
            return (0,1)
        elif x1 > 0 and x2 == 0:
            return (10)
        elif x1 ==0 and x2 == 0:
            return (0,0)
        
        ab = min(x1x2), max(x1,x2)
        while a > 0:
            tmp = b % a
            b = a
            a = tmp
        return (x1//bx2//b)
    
    rs = [1-x for x in s]

    cuSum1 = s[:1]
    for i in range(1,n):
        cuSum1.append(cuSum1[-1] + s[i])
    
    cuSum0 = rs[:1]
    for i in range(1,n):
        cuSum0.append(cuSum0[-1] + rs[i])
    
    ratio_list = [gys(x1,x2for x1,x2 in zip(cuSum0cuSum1)]

    res = []
    for ratio in ratio_list:
        dic[ratio] += 1
        res.append(str(dic[ratio]))
    
    return ' '.join(res)

print(solution(s))

2.n竹子,a,b,c段,最多几段
背包问题,注意下初始值
import sys

tmp = [int(xfor x in sys.stdin.readline().strip().split(' ')]
nabc = tmp

def solution(nabc):
    dp = [-float('inf')] * (n+1)
    dp[0] = 0
    for w in [a,b,c]:
        for i in range(wn+1):
            dp[i] = max(dp[i], dp[i-w]+1)
    
    return dp[-1]

print(solution(7,4,2,4))

全部评论

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

相关热帖

近期热帖

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

近期精华帖

热门推荐