当前位置: 首页 > 面试经验 >

8.20 网易笔试 算法岗

优质
小牛编辑
101浏览
2023-03-28

8.20 网易笔试 算法岗

以为刷了1000题,秋招笔试应该AK很轻松了 结果今天考了两场都没A掉,上午卡python的. 太难了

Q1 100%

贪心从左到右转换,题目意思是相邻的数换位置。

n = int(input())
*nums, = map(int, input().split())

hm = dict()
for i in range(n):
hm[nums[i]] = i
res = []
acc = 0
for i in range(n):
while nums[i] != i + 1:
acc += 1
idx2 = hm[nums[i] - 1]
nums[i], nums[idx2] = nums[idx2], nums[i]
hm[nums[idx2]] = idx2
hm[nums[i]] = i
res.append([idx2, i])
print(acc)
for i in range(len(res)):
print(res[i][0], res[i][1])

Q2 100%

哈希加前缀和

s = input().strip()
from collections import defaultdict
hm = defaultdict(int)
hm['0,0,0'] = 1
r = e = d = 0
res = 0
for i in range(len(s)):
if s[i] == 'r':
r += 1
if s[i] == 'e':
e += 1
if s[i] == 'd':
d += 1
state = f'{0},{e-r},{d-r}'
res += hm[state]
hm[state] += 1
print(res)

Q3 100%

看到位运算,基本上都是把每一位拆开了看,横看成岭侧成峰

n, k = map(int, input().split())
*nums, = map(int, input().split())

cnt = [[0] * 30 for _ in range(n)]

for i in range(n):
tmp = nums[i]
idx = -1
while tmp:
if tmp & 1:
cnt[i][idx] += 1
tmp = tmp >> 1
idx -= 1
final = [0] * 30
exclude = set()
for i in range(30):
tmp = 0
s = set()
for j in range(n):
if j in exclude:
continue
if cnt[j][i] == 1:
tmp += 1
else:
s.add(j)
if tmp >= k:
final[i] = 1
exclude = exclude | s

print(int(''.join(map(str,final)), 2))

Q4 60%

参考斐波那契数列logn做法,但是我不知道怎么算 mod k,其中n应该是不能mod,不然会影响结果,有没有A了的大佬说说怎么做

mod = 10 ** 9 + 7
def matmul(A, B):
res = [[0] * 2 for _ in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
res[i][j] += A[i][k] * B[k][j]
res[i][j] %= mod
return res

def quickpowmat(A, n):
mul = [[1,0],[0,1]]
base = A
while n:
if n & 1:
mul = matmul(mul, base)
base = matmul(base, base)
n = n >> 1
return mul

def quickpow(a, n):
mul = 1
base = a
while n:
if n & 1:
mul *= base
mul %= mod
base = base * base
base %= mod
n = n >> 1
return mul

a, b, n = map(int, input().split())
def solve1(a,b,n):
if n == 1:
return a % mod
elif n == 2:
return b % mod
A = [[2,2],[1,0]]
init = [[0,1],[1,0]]
trans = quickpowmat(A, n - 2)
final = matmul(trans,init)
a0, b0 = final[0]
res = quickpow(a,a0) * quickpow(b,b0)
res %= mod
return res
print(solve1(a,b,n))
#网易笔试##秋招笔试#
 类似资料: