网易2019实习生招聘编程题集合¶
1 牛牛找工作¶
3¶
4¶
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。
输出描述:
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
输入例子1:
3 3
1 100
10 1000
1000000000 1001
9 10 1000000000
输出例子1:
100
1000
1001
自测 通过
# -*- coding: utf-8 -*-
while True:
try:
jobs = []
N, M = map(int, input().split())
for i in range(N):
hard, sal = map(int, input().split())
jobs.append((hard, sal))
sorted(jobs)
friends = list(map(int, input().split()))
for friend in friends:
sal = jobs[0][1]
for job in jobs:
if job[0] <= friend:
if job[1] >= sal:
sal = job[1]
else:
break
print(sal)
except:
break
2 被 3 整除¶
小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。并且小Q对于能否被3整除这个性质很感兴趣。小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。
输入例子1:
2 5
输出例子1:
3
例子说明1:
12, 123, 1234, 12345...
其中12, 123, 12345能被3整除。
解题思路
这题只能找规律了 能否被 3 整除符合 0 1 1 0 1 1 的规律
def func(n):
timer = n // 3
mod = n % 3
if mod == 0:
return 2 * timer
else:
return 2 * timer + (0 if mod == 1 else 1)
while True:
try:
l, r = map(int, input().split())
print(func(r) - func(l-1))
except:
break
牛客 AC
3 安置路灯¶
小Q正在给一条长度为n的道路设计路灯安置方案。为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入描述:
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。
输出描述:
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
输入例子1:
2
3
.X.
11
...XX....XX
输出例子1:
1
3
解题思路
利用栈，栈空则 X 不入栈。栈满三个就清空，路灯计数 +1
牛客 AC
N = int(input())
for i in range(N):
n = int(input())
road = input()
stack = []
sum = 0
for ch in road:
if not stack:
if ch == 'X':
continue
else:
stack.append(ch)
else:
stack.append(ch)
if len(stack) == 3:
sum += 1
stack = []
if len(stack):
sum += 1
print(sum)
4 迷路的牛牛¶
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出描述:
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
输入例子1:
3
LRR
输出例子1:
E
解题思路
构造一个环形 buff 区，利用余数实现。
牛客 AC
ls = ['N', 'E', 'S', 'W']
while True:
try:
n = int(input())
seq = input()
stat = 0
for ch in seq:
if ch == 'L':
stat = (stat-1) % 4
if ch == 'R':
stat = (stat+1) % 4
print(ls[stat])
except:
break
5 数对¶
链接：https://www.nowcoder.com/questionTerminal/bac5a2372e204b2ab04cc437db76dc4f
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。牛牛希望你能帮他计算一共有多少个可能的数对。
输入描述:
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述:
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入
5 2
输出
7
说明
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)
解题思路
对于每一个 y 考虑 x 从 0 到 n 的所有可能，可分为 余数 从 0 到 y-1 的很多组还有最后一组零头，另外如果 k=0 考虑去掉 x 为 0 的计数(虽说 x y 都为正整数，但考虑 0 是为了方便)
while True:
try:
n, k = map(int, input().split())
res = 0
for y in range(k+1, n+1):
a = (n+1)// y
b = (n+1)%y
res += a * (y-k) + ((b-k) if b >=k else 0)
if k == 0:
res -= n-k
print(res)
except:
break