网易笔试0918

[TOC]

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys

d = dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', range(26)))
s = sys.stdin.readline()
# if ' ' not in s:
# s = "AB 1" # 输入有毛病哦
s, m = s.split()
m = int(m)
n = len(s)
costs = [0]*n
costs[0] = 1
for i in range(1, n):
costs[i] = 1 + min(abs(d[s[i]] - d[s[i-1]]), abs(26 + d[s[i]] - d[s[i-1]]), abs(26 + d[s[i-1]] - d[s[i]]))
_sum = sum(costs)
res = _sum
ss = 0
for i in range(1, m+1):
ss += costs[i]
res = min(res, _sum - ss + m*2)
if m+1<n:
for i in range(m+1, n):
ss += costs[i]-costs[i-m]
res = min(res, _sum - ss + m*2)
print(res)

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from itertools import groupby

n = int(input())

def bitcnt(n):
res = 0
for i, l in groupby(bin(n)[2:]):
if i=='1':
n = len(list(l))
res += n
return res
s = bin(n)[2:]
if n==0:
print(-1)
else:
print(min(bitcnt(n), 1+bitcnt(2**len(s)-n)))

4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n, a, b = map(int, input().split())
if n>500:
print(0)
else:
grid = [input() for _ in range(n)]
g = [[float('inf')]*n for _ in range(n)]
g[0][0] = 0
dirs = [[0,1], [0, -1], [1, 0], [-1, 0]]

def valid(i, j):
return 0<=i<n and 0<=j<n

l = [[0, 0]]

while l:
newl = set()
for i, j in l:
for di, dj in dirs:
ii, jj = i+di, j+dj
if not valid(ii, jj): continue
c = a if grid[ii][jj]=='#' else 0
if g[ii][jj] > g[i][j] + c:
g[ii][jj] = g[i][j] + c
newl.add((ii, jj))
l = list(newl)

print(g[-1][-1])

亚马逊面试

  1. 树中最长连续递增路径长度
  2. 合并多个排序过的数组
  3. 拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
     0
1 2
1 2 1 3


0 -> 1 -> 2 : 3

def helper(root):
if not root:
return 0
res = 1
if root.left and root.val+1==root.left.val:
res = 1 + helper(root.left)
if root.right and root.val+1==root.right.val:
res = max(res, 1 + helper(root.right))
return res

def solve(root):
if not root:
return 0
l = [root]
res = 0
while l:
node = l.pop()
res = max(res, helper(node))
if node.left:
l.append(node.left)
if node.right:
l.append(node.right)
return res


merge({{1, 4, 7},{2, 5, 8},{3, 6, 9, 10},...}) = {1, 2, 3, 4, 5, 6, 7, 8, 9}

public int[] merge(int[][] arrays) {
int n = arrays.length;
List<Integer> res = new ArrayList<>();
// i, j
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-> arrays[a[0]][a[1]]-arrays[b[0]][b[1]]);
for(int i=0; i<n; i++){
if(arrays[i].length>0){
pq.add(new int[]{i, 0});
}
}
while(!pq.isEmpty()){
int[] ij = pq.poll();
int i = ij[0], j = ij[1];
res.add(arrays[i][j]);
if(j!=arrays[i].length){
ij[1]++;
pq.offer(ij);
}
}
return res.toArray(new int[res.size()]);
}
//时间复杂度:O(N * log(arrays.length))


1. reverse(1->2->3) = 3->2->1

2.
0:
1: 0
2: 0
3: 1, 2
4: 3
output: 0, 1, 2, 3, 4

def solve(req):
# 入度为 0
# 更新受影响的节点的入度
n = len(req)
res = []
indegrees = [0]*n # 每个节点的入度
out = [[] for _ in range(n)] # 被当前节点依赖的节点
stack = [] # 入度为 0 的节点
for i in range(n):
indegrees[i] = len(req[i])
if indegrees[i]==0:
stack.append(i)
# j -> i
for j in req[i]:
out[j].append(i)
while stack:
node = stack.pop()
res.append(node)
# node -> j
for i in out[node]:
indegrees[i] -= 1
if indegrees[i]==0:
stack.append(i)
return res
# 推荐文章
  1.MYSQL45讲-笔记
  2.《Java业务开发常见错误100例》笔记
  3.django
  4.flutter
  5.elastic search

评论


:D 一言句子获取中...