前端刷题笔记3–11日

Part 1 算法题

1、小团一天最多可以烤n个蛋糕,每个蛋糕有一个正整数的重量。早上,糕点铺已经做好了m个蛋糕。现在,有一个顾客要来买两个蛋糕,他希望买这一天糕点铺烤好的最重的和最轻的蛋糕,并且希望这两个蛋糕的重量恰好为a和b。剩余的n-m个蛋糕可以现烤,请问小团能否满足他的要求?

PS:输入包含多数组数据,每组数据两行。每组数据第一行包含4个整数n,m,a,b, 用空格隔开。这里不保证a,b 的大小关系。 接下来一行m个数,代表烤好的蛋糕的重量。

思路:将烤好面包的重量放到一个数组之中,会有一下集中情况:

情况一:烤好面包中的最小重量min,或者最大重量max已经超出顾客所希望的a,b重量范围。输出‘NO’。

情况二:如果烤好的面包的重量都控制在a,b范围之中,这个时候n-m(剩余还可以烤的面包数量)==0,如果min!=a 或max!=b,输出‘NO’

情况三:若n-m==1,意味着还有一次额外烤的机会,如果min!=a且 max!=b,输出‘NO’

这里稍稍记录一下处理输入的方法:

python: nums = input()

Javascript: var nums = readline();

nums = input()
while(True):
n,m,a,b = map(int,nums.split()) //map会根据提供的函数对指定序列做映射。
dones = list(map(int,input().split()))//重新input()获取第二行数据
minmum = min(dones)
maxmum = max(dones)
if a>b:
a,b=b,a
result = 'YES'
if minmum<a:
result = 'NO'
else:
if maxmum>b:
result='NO'
else:
if n-m==1:
if minmum>a and maxmum<b:
result='NO'
elif n-m==0:
if minmum>a or maxmum<b:
result='NO'
print(result)
try:
nums=input()
except:
break //如果有try就先运行try 里面的代码,如果try 中的代码出现异常,运行except 里的代码

代码测试通过。

2、已知在这个游戏环节中每个人最后都会得到一个分数score_i,显而易见的是,游戏很有可能出现同分的情况,小团计划该环节晋级人数为x人,则将所有人的分数从高到低排序,所有分数大于等于第x个人的分数且得分不为0的人都可以晋级。请你求出本环节的实际晋级人数。显然这个数字可能是0,如果所有人的得分都是0,则没有人满足晋级条件。

PS: 输入第一行为n,x 代表参加比赛人数,以及指定的x. 第二行为n个参赛选手的成绩(排序不规则)

思路:我的第一个想法就是把第二行输入的成绩先按照从大到小的顺序排列出来,然后判断在第x个人的成绩,如果是0,就找它之前不是0 的成绩的人的位置,如果不是0,直接输出x 就可以。

nums = input()
while(True):
n,x = map(int,nums.split())
score = list(map(int,input().split()))
score.sort(reverse=True)//reverse默认是false
while score[x-1]==0 and x>=1:
x=x-1
print(x)

以上代码报错:nums = input()
EOFError: EOF when reading a line
这个是因为忘记给while加上结束标志了。由于题干说只输入两行数据,所以不需要用while也可以。
另外上面的代码还少考虑了一种情况,那就是假设如果第4名参赛者得分不是0,并且跟之后的4位参赛者有一样的成绩,那么输出的result也需要加上之后的4位参赛者。

nums = input()
n,x = map(int,nums.split())
score = list(map(int,input().split()))
score.sort(reverse=True)
if score[x-1]!=0 and score[x-1]==score[x]:
a=x
for i in range(a,n):
if score[a-1]==score[i]:
x=x+1
result = x
else:
while score[x-1]==0 and x>=1:
x=x-1
result = x
print(result)

代码测试通过。

3、转盘上有N盘寿司围成一圈,第1盘与第2盘相邻,第2盘与第3盘相邻,…,第N-1盘与第N盘相邻,第N盘与第1盘相邻。小团认为第i盘寿司的美味值为A[i](可能是负值,如果小团讨厌这盘寿司)。现在,小团要在转盘上选出连续的若干盘寿司,使得这些寿司的美味值之和最大(允许不选任何寿司,此时美味值总和为0)。

PS:按组输入,每组输入三行数据,第一行表示一共有几组,第二行表示N,第三行表示N个由空格隔开的整数,从A[1]~A[N].

思路:这是一道动态规划题目。正常题目应该是求子序列最大和,但是这个题目比较麻烦的就是序列的首尾相连了。
正常序列的最大子序列和‘m’我们可以求出来。首尾相连的时候的最大子序列和 n 其实是序列和减去最小的子序列。比较m 和n 的大小,取大的。

def commonarray(N,score):
dp = [None]*N
dp[0]=score[0]
for i in range(1,N):
dp[i]=max(dp[i-1]+score[i],score[i])
result=max(dp)
return result
def linkarray(N,score):
dp = [None]*N
dp[0]=score[0]
for i in range(1,N):
dp[i]=min(dp[i-1]+score[i],score[i])
result = sum(score)-min(dp)
return result
nums = input()
while(True):
a = int(nums.split()[0]) //nums.split()返回为字符串数组,不可以用int,所以需要取出数组中的那个数字
N = int(input().split()[0])
score = list(map(int,input().split()))
max_common = commonarray(N,score)
max_link = linkarray(N,score)
if max_common>max_link:
result=max_common
else:
result=max_link
print(result)
try:
nums = input()
except:
break

上面这段代码是有问题的,报错:array assignment out of index 什么什么的,错误原因也很蠢。因为我审题有误。变量a其实是代表一共有几组,之后每组只有两行。所以根本不需要把a=int(input().split()[0])放到while 里面。放在外面得到所有组的数量,然后for循环就可以。

把读取数据的部分修改一下:

nums = input()
a = int(nums.split()[0])
for i in range(n):
N = int(input().split()[0])
score = list(map(int,input().split()))
max_common = commonarray(N,score)
max_link = linkarray(N,score)
if max_common>max_link:
result=max_common
else:
result=max_link
print(result)

测试通过。