首页 > 8.21 网易笔试结果统计+题目+解题思路+AK参考代码
头像
LifeAndDonuts
编辑于 2021-08-21 19:03
+ 关注

8.21 网易笔试结果统计+题目+解题思路+AK参考代码 投票

牛客的编辑器真是佛了

基本思路:
1. 排序+二分
2. 分治
3. 拓扑排序
4. 最短路

1. 数组中两个元素和小于等于M的组合数

题目描述

对于一个整型数组,里面任何2个元素相加,小于等于M的组合有多少种;
如果有符合的,输出组合对数;
没有,输出0;

参考代码

import sys
from bisect import bisect_right

readline = sys.stdin.readline

nums = list(map(int, readline().strip().split()))
M = int(readline().strip())

nums.sort()
ans = 0

for i, x in enumerate(nums):
    # ans += bisect_right(nums[:i], M - x) # 实际上 nums[:i] 的复杂度为 O(i),所以会导致整体的复杂度为 O(n^2),但是笔试时也过了,或者双指针可以达到 O(n)
    ans += bisect_right(nums, M - x, 0, i) # O(nlog(n))  

print(ans)

2. 计算K位

题目描述

给你两个正整数 n 和 k,其中 1 =< n <= 26,字符串 Sn 的形成规则如下:

Li表示26个字母a-z,依次是:
L1 = "a"
L2 = "b"
L3 = "c"
...
L26="z"

S1 = "a"
当 i > 1 时,Si = Si-1 +Li + reverse(invert(Si-1))
其中 + 表示字符串的连接操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(例如:'a' 翻转为'z','b' 翻转为'y', ... 而 'z' 翻转为 'a')。

例如,符合上述描述的序列的前 4 个字符串依次是:

S1="a"
S2="abz"
S3="abzcayz"
S4="abzcayzdabzxayz"

请你返回 Sn 的 第 k 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。
示例1输入输出示例仅供调试,后台判题数据一般不包含示例

参考代码

B = [0]
for i in range(1, 27):
    B.append(B[-1] * 2 + 1)


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        mid = (B[n] + 1) // 2
        if k == mid:
            return chr(n + ord("a") - 1)
        elif k < mid:
            return self.findKthBit(n - 1, k)
        return chr(
            ord("z")
            - ord(self.findKthBit(n - 1, B[n - 1] + 1 - (k - mid)))
            + ord("a")
        )

3. 纸张分配问题

题目描述

一群小朋友围成一圈准备开始画画,现在老师需要给这些孩子发纸张;
规则是如果一个小朋友的年龄比自己旁边的人大,那么这个小朋友就必须分到比身旁孩子更多的纸张;
所有孩子至少要有一个纸张,请帮助老师设计一个算法,算出最少需要多少张纸。
备注:
假设小朋友的总数量不会超过100个;
每个小朋友至少要求至少有一张纸;
当且仅当年龄大于相邻小朋友时,才会要求纸张数量更多(年龄相等的情况下,允许小于或者等于)。

参考代码

import sys
from collections import deque

readline = sys.stdin.readline

a = list(map(int, readline().strip().split()))
n = len(a)
adj = [[] for _ in range(n)]
indeg = [0] * n
for i in range(n):
    l = (i - 1 + n) % n
    r = (i + 1) % n
    if a[i] > a[l]:
        adj[l].append(i)
        indeg[i] += 1
    if a[i] > a[r]:
        adj[r].append(i)
        indeg[i] += 1
q = deque()
for i in range(n):
    if indeg[i] == 0:
        q.append(i)
b = [1] * n
while q:
    u = q.popleft()
    for v in adj[u]:
        b[v] = max(b[v], b[u] + 1)
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
print(sum(b))

4. 航海探险

题目描述

给你一个由 '0'(水)、'1'(陆地)和'2'(障碍物)组成的的二维网格,再给你一个两栖交通工具,走陆地费用为1,走水路费用为2,障碍物无法通行,请你计算从网格的起始位置行驶到最终位置的最小费用。
注意:仅可以水平方向 和 竖直方向行驶。如果无法到达目的地,则返回-1
另外,起始第1个位置不算,根据到达位置的属性来决定费用。
示例1输入输出示例仅供调试,后台判题数据一般不包含示例

参考代码

import heapq
from typing import List


class Solution:
    def minSailCost(self, g: List[List[int]]) -> int:
        n = len(g)
        m = len(g[0])
        dist = [[float("inf") for _ in range(m)] for _ in range(n)]
        dist[0][0] = 0
        q = []
        heapq.heappush(q, (0, 0))
        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]
        while q:
            d, u = heapq.heappop(q)
            i, j = divmod(u, m)
            for k in range(4):
                r, c = i + dx[k], j + dy[k]
                if 0 <= r < n and 0 <= c < m and g[r][c] != 2:
                    if d + 2 - g[r][c] < dist[r][c]:
                        dist[r][c] = d + 2 - g[r][c]
                        heapq.heappush(q, (dist[r][c], r * m + c))
        if dist[-1][-1] == float("inf"):
            return -1
        return dist[-1][-1]

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐