京东笔试算法题
1.前缀切分后0与1比例相同
import sys
n = int(sys.stdin.readline())
s = [int(x) for x in list(sys.stdin.readline().strip())]
def solution(s):
from collections import defaultdict
dic = defaultdict(int)
n = len(s)
def gys(x1, x2):
if x1 == 0 and x2 > 0:
return (0,1)
elif x1 > 0 and x2 == 0:
return (1, 0)
elif x1 ==0 and x2 == 0:
return (0,0)
a, b = min(x1, x2), max(x1,x2)
while a > 0:
tmp = b % a
b = a
a = tmp
return (x1//b, x2//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,x2) for x1,x2 in zip(cuSum0, cuSum1)]
res = []
for ratio in ratio_list:
dic[ratio] += 1
res.append(str(dic[ratio]))
return ' '.join(res)
print(solution(s))
背包问题，注意下初始值
import sys
tmp = [int(x) for x in sys.stdin.readline().strip().split(' ')]
n, a, b, c = tmp
def solution(n, a, b, c):
dp = [-float('inf')] * (n+1)
dp[0] = 0
for w in [a,b,c]:
for i in range(w, n+1):
dp[i] = max(dp[i], dp[i-w]+1)
return dp[-1]
print(solution(7,4,2,4))
查看9道真题和解析
