2020年校招笔试真题详解

拼多多

第一题严格升序

输入：两行数字，第一行数字是数组A，第二行数字是数组B，数组A几乎升序（只需要替换数组中的一个元素就可以转换为严格升序（严格升序不能有邻近的元素相等））

要求：从B中选择一个元素与A中元素交换，该元素必须是可以使A升序的值最大的元素。

输出：字符串，严格排序后数组A各元素以空格间隔（如果失败返回NO）

if __name__ == "__main__":
    a = [int(x) for x in input().strip().split(' ')]
    b = [int(x) for x in input().strip().split(' ')]
    b.sort(reverse=True)
    for i in range(1, len(a)):
        if a[i] > a[i-1]: continue
        else: break
    if i == 1:
        if a[0] >= a[2]:
            for j in range(len(b)):
                if b[j] < a[1]:
                    a[0] = b[j]
                    break
            if a[0] < a[i]:
                print(' '.join(map(str, a)))
            else: print('NO')
        else:
            for j in range(len(b)):
                if a[0] < b[j] < a[2]:
                    a[1] = b[j]
                    break
                if b[j] < a[1]:
                    a[0] = b[j]
                    break
            if a[0] < a[1]:
                print(' '.join(map(str, a)))
            else: print('NO')
    elif i == len(a)-1:
        if b[0] > a[i-1]:
            a[i] = b[0]
            print(' '.join(map(str, a)))
        else: print('NO')
    else:
        for j in range(len(b)):
            if a[i-1] < b[j] < a[i+1]:
                a[i] = b[j]
                break
        if a[i-1] < a[i] < a[i+1]:
            print(' '.join(map(str,a)))
        else:
            print('NO')

考试的时候AC 87%，找出了问题，改了下代码，也不知能不能100%通过

第二题判断是否收尾相接形成圆环

输入：一组字符串，每个字符串的所有字符全部大写
要求：经过有限次字符串顺序交换是否能够收尾相接形成圆环，如：ABD、DCE、EGDA
输出：true或false

def dfs(s, vis, begin, end):
    if min(vis) == 1 and begin == end:
        return True
    find = [index for index, v in enumerate(vis) if v==0]
    for i in find:
        if s[i][0] == end:
            vis[i] = 1
            if dfs(s, vis, begin, s[i][-1]):
                return True
            vis[i] = 0
        else: continue
    return False
 
if __name__ == "__main__":
    s = [x for x in input().split()]
    visited = [0]*len(s)
    begin = '#'
    flag = False
    for i in range(len(s)):
        begin = s[i][0]
        end = s[i][-1]
        visited[i] = 1
        if dfs(s, visited, begin, end):
            flag = True
            break
        visited[i] = 0
        begin = '#'
 
    if flag: print('true')
    else:print('false')

第三题最短平均等待时间

输入：先输入N、M，分别代表程序个数（N）和依赖个数（M）；再输入N个数字，代表每个程序的执行时间；再输入M组数，分别代表M个依赖关系，每组数据的第二个数字代表的进程依赖第一个数字代表的进程

要求：求出符合依赖规则（被依赖的先执行），并且程序平均等待时间最短的程序执行序列

输出：程序执行顺序

第四题搭积木

输入：首先输入N，代表总共有N个积木；再输入N个数字，分别代表N个积木的长宽；再输入N个数字，分别代表N个积木的重量

要求：每个积木高1米；把积木搭起来，下面的积木一定要比上面积木的长宽大；下面的积木的承重最大是自己重量的7倍；求积木的最大高度

输出：积木高度

网易云音乐

第一题

有一天，小易把 1 到 n 的所有排列按字典序排成一排，小易从中选出了一个排列，假设它是正数第 Q 个排列，小易希望你能回答他倒数第 Q 个排列是什么。

例如 1 到 3 的所有排列是：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

若小易选出的排列是 1 2 3，则 Q = 1，而你应该输出排列 3 2 1。

输入描述：

第一行数字 n，表示排列长度
接下来一行 n 个数字，表示选出的排列
1 <= n <= 300000

输出描述：

一行n个数字，表示所求的排列。

示例1：

3
1 2 3

输出：

3 2 1

示例2：
输入：

5
3 1 5 2 4

输出：

3 5 1 4 2

n = int(input())
data = list(map(int, input().split()))
for i in data:
    print(n + 1 - i, end=" ")

第二题

小易有一个长度为 $n$ 的数字数组 $a_1,a_2,…a_n$
问你是否能用这 $n$ 个数字构成一个环（首尾相连），使得环中的每一个数字都小于它相邻的两个数字的和（每个数字都必须使用并且只能使用一次）。

输入描述：

第一行包含一个整数 t (1 <= t <= 10)，表示测试用例的组数。
每个测试用例输入如下：
第一行一个整数 n，表示数字的个数；
第二行 n 个整数 a1, a2,…, an，每两个整数之间用一个空格分隔。
输入数据保证
3 <= n <= 10^5
1 <= ai <= 10^9

示例1：

1
5
17 6 17 11 17

输出：

YES

示例2：

1
3
1 2 4

输出：

NO

t = int(input())
while t:
    n = int(input())
    data = list(map(int, input().split()))
    data.sort()
    data[-1], data[-2] = data[-2], data[-1]
    for i in range(n):
        pre, pos = (i - 1 + n) % n, (i + 1) % n
        if data[i] >= data[pre] + data[pos]:
            print("NO")
            break
    else:
        print("YES")
    t -= 1

第三题

小易给你一个包含n个数的数组 $a_1,a_2,…,a_n$。你可以对这个数组执行任意次以下交换操作：对数组中的两个下表 $i,j(1≤i,j≤n) i,j(1\leq i,j\leq n)i,j(1≤i,j≤n)$，如果 $a_i+a_j$ 为奇数，就可以交换 $a_i$ 和 $a_i$。

现在允许你使用操作次数不限，小易希望你能求出在所有能通过若干次操作可以得到的数组中字典序最小的一个是什么。

输入描述：

第一行一个整数 n；
第二行 n 个整数 $a_1,a_2,…,a_n$，表示数组，每两个数之间用空格分开
输入保证 $1<=n<=10^5;1<=a_i<=10^9$

输出描述：

n个整数，每两个整数之间用一个空格分开，表示得到的字典序最小的数组。

示例1：

4
7 3 5 1

输出：

7 3 5 1

示例2：

10
53941 38641 31525 75864 29026 12199 83522 58200 64784 80987

输出：

12199 29026 31525 38641 53941 58200 64784 75864 80987 83522

n = int(input())
data = list(map(int, input().split()))
odd, even = False, False
for i in data:
    if i & 1:
        odd = True
    else:
        even = True
if not odd or not even:
    print(data)
else:
    data.sort()
    for item in data:
        print(item, end=' ')

第四题

给定 01 序列 S，序列 S 是优秀的 01 序列，优秀的 01 序列定义如下：

如果序列 S、T 是优秀的，则序列 S+T 也是有序的，+ 被定义为按顺序链接两个序列。例如，“010”+“110”=“010110”。
如果序列 S 是优秀的，则序列 rev(S) 也是优秀的。rev(S) 被定义为按位反转（0变1，1变0）序列S，并删除前面的0。例如，rev(“1100101”)=“11010”。

现在请你判断序列 T 是不是优秀的

输入描述：

第一行一个整数T，表示输入T组数据。
每组数组的第一行是一个01序列，表示序列S。第二行是另一个01序列，表示序列T。
1<=|S|,|T|<=1000，S,T不含前导零

输出描述：

对于每组数据，一行输出”YES”或者”NO”,表示序列T是不是优秀的。

示例1：

1
1100
110011

输出：

YES

示例2：

1
1000
100001111

输出：

NO

贝壳

第一题

第二题消失的卡片

题目描述
桌面上本来摆着 n 张卡片，编号分别为 1 到 n ，结果一阵风吹来不小心吹掉了一张卡片 x ，因为剩下的卡片也被吹到了一起，所以你只能知道剩下的卡片编号中 0 到 9 各个数字的出现次数，你能求出 n 和 x 吗?

输入：

一行10个数字，以空格隔开，分别表示 0 到 9 的出现次数（每个不超过300）

输出：

一行一个解 n 和 x，如有多个解先按 n 从小到大，再按 x 从小到大，如果无解输出 “NO ANSWER”

样例输入：

0110111111

样例输出：

9 3

from itertools import permutations
if __name__ == "__main__":
    num = [int(x) for x in input().strip().split(' ')]
    n = 1
    flag = True
    while True:
        i = n
        while i > 0:
            yu = i % 10
            num[yu] -= 1
            i //= 10
        if max(num) == 0:
            break
        elif max(num) < 0:
            flag = False
            break
        else:
            n += 1
            continue
    if flag == False:
        print('NO ANSWER')
    else:
        res = []
        for i in range(10):
            if num[i] < 0:
                res += [str(i)]*abs(num[i])
        if res == []: print(n+1, n+1)
        else:
            ans = []
            for item in permutations(res):
                ans.append(''.join(item))
            ans = set(ans)
            ans = list(ans)
            ans.sort()
            for item in ans:
                if int(item) <= n
                print(n, int(item))

答案待验证

第三题

网易互娱

第一题

def func(x):
    cnt = 0
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return cnt
 
if __name__ == "__main__":
    m = int(input())
    for k in range(m):
        n = int(input())
        num = [int(x) for x in input().strip().split(' ')]
        res = []
        for i in range(n):
            c = func(num[i])
            res.append(c)
        ans = set(res)
        print(len(ans))

AC 100%

第二题

if __name__ == "__main__":
    T = int(input())
    for k in range(T):
        m, t, m1, t1, m2, t2 = [int(x) for x in input().strip().split(' ')]
        dp1 = [0]*(t+1)
        dp2 = [0]*(t+1)
        tem1, tem2 = 1, 1
        for i in range(t+1):
            if i%t1 == 0:
                if tem1 == 1:
                    tem1 =0
                else: tem1 = 1
            dp1[i] = tem1
        for i in range(t+1):
            if i%t2 == 0:
                if tem2 == 1:
                    tem2 =0
                else: tem2 = 1
            dp2[i] = tem2
        res = 0
        for i in range(1, t+1):
            dif = (1-dp1[i-1])*m1 - (1-dp2[i-1])*m2
            res += dif
            if res < 0:
                res = 0
            if res > m:
                res = m
        print(res)

AC 100%

第三题

import sys
def deal(s, k, s1, s2):
    L = 0
    R = 0
    change = 0
    ans = 1
    for i in range(len(s)):
        if s[i] in s1:
            if change < k:
                change += 1
                R += 1
            else:
                while L <= R and s[L] not in s1:
                    L += 1
                L += 1
                R += 1
        else:
            R += 1
        ans = max(ans, R - L)
    return ans

if __name__ == "__main__":
    # 读取第一行的n
    n = int(sys.stdin.readline().strip())
    res1 = []
    for i in range(n):
        s = sys.stdin.readline().strip()
        ss = [j for j in list(set(s)) if j != 'N']
        res = []
        res.append(deal(s, 2, ss, 'N'))
        res1.append(max(res))
    for i in res1:
        print(i)

AC 100%

字节跳动

第一题上学闹钟

题目描述：小明定了 n 个闹钟，他只能在闹钟响起时出发去学校，每个闹钟时间分别为 hi 点 mi 分，小明家到学校要 X 分钟，学校上课时间 A 点 B 分（0<=A<24小时，0<=B<60分钟），求他最晚几点起

输入：

3 //定了几个闹钟
5 0 //第1个闹钟的小时数和分钟数
6 0 //第2个闹钟的小时数和分钟数
7 0 //第3个闹钟的小时数和分钟数
59 //到学校要多少分钟
6 59 //上课的小时数和分钟数

输出：

6 0 //最晚的起床时间

if __name__ == "__main__":
    n = int(input())
    clock = []
    for i in range(n):
        hi, mi = [int(x) for x in input().strip().split(' ')]
        clock.append((hi, mi))
    X = int(input())
    A, B = [int(x) for x in input().strip().split(' ')]
    clock.sort(reverse=True)
    for h, m in clock:
        if (h, m) > (A, B):
            continue
        h1 = h + (m + X) // 60
        m1 = (m + X) % 60
        if h1 >= 24:
            h1 -= 24
        if (h1, m1) <= (A, B):
            print(h, m)
            break

AC 80%

第二题加密通信

小明和小红采用密码加密通信，每次通信有固定的明文长度 n 和加密次数 k 。
比如：密码二进制明文是 1001010 ，加密次数是 4 ，则每次将密文右移 1 位与明文做异或操作，总共位移 3 次（k=4, 所以k - 1 = 3）

输入：

7 4 // n k
1110100110 //密文

输出：

1001010 //明文

解释：

1001010—
-1001010–
–1001010-
—1001010
加密次数为4，故对于明文右移 4-1=3 轮，每轮与当前密文进行一次异或，故1001010对应密文为1110100110

if __name__ == "__main__":
    n, k = [int(x) for x in input().strip().split(' ')]
    s = input()
    q = [0]*(k-1) + [int(s[0])]
    res = '' + s[0]
    for i in range(1, n):
        q.pop(0)
        if sum(q)%2 == int(s[i]):
            res += '0'
            q.append(0)
        else:
            res += '1'
            q.append(1)
        # q.append(int(s[i]))
        # if sum(q) % 2 == 0:
        #     res += '0'
        #     q.pop(-1)
        #     q.append(0)
        # else:
        #     res += '1'
        #     q.pop(-1)
        #     q.append(1)

    print(res)

AC 66.7%，提示算法复杂度过大

第三题发工资

王大锤要给员工发工资，员工从左到右坐成一排，每个员工知道彼此的资历，每个员工只知道自己左右员工的工资，如果某员工比左边或右边的人资历老，那他一定比这个人工资高100元，每个人最低工资100元，求王大锤最低给多少工资

if __name__ == "__main__":
    n = int(input())
    work = [int(x) for x in input().strip().split(' ')]
    res = [100]*n
    for i in range(1, n):
        if work[i] > work[i-1]:
            res[i] = res[i-1] + 100
    for i in range(n-2, -1, -1):
        if work[i] > work[i+1]:
            res[i] = max(res[i], res[i+1] + 100)
    print(sum(res))

ac 100%

第四题

题目描述

小明练习跑步，他家附近的街道是棵树，这棵树上的点按 1 到 n 标号，任意两点间互相可达，并且有且仅有一条路，每条路的距离都是 1，需要在树上找条路来跑，小明对 3 很感兴趣，所以他想知道所有跑道距离和 % 3 = 0, 1，2 的道路总长度一共各有多长。即树上任意两点问距离 % 3 = k 的距离和。

输入描述：

第一行一个 n，点数 n< = 1e5
接下来 n-1 行每行 u, v 一条无向边

输出描述：

一行 3 个整数，分别代表 % 3 = 0，1, 2的两点距离的距离和
结果取模 1e9+7

输入：

3
1 2
2 3

输出：

0 2 2

说明：

长度 % 3=0的距离不存在，=1的有两条1-2，2-3总长度是2，=2的有1条，1-3，总长度是2

作业帮（8.14）

第一题

题目描述：
对于给定的 x,n ，求 $ x^1 + x^2 + \cdots + x^n $ 的结果，为避免结果过大，请将结果 % 998244353 后输出

输入描述：

输入共一行，分别表示 x, n

输出描述：

输出共一行，为题干要求的计算结果

if __name__ == "__main__":
    x, n = [int(x) for x in input().strip().split(' ')]
    if x == 1:
        print(n % 998244353)
    else:
        res = (pow(x, n+1) - x)//(x-1)
        print(res % 998244353)

AC 30%, 算法复杂度过大

第二题

题目描述：
给定两个单词 s1 和 52，计算出将 S1 转换成 s2 所使用的最少操作数。
你可以对一个单词进行如下三种操作:

插入一个字符
删除个字符
替换一个字符

输入描述:

每一行有两个字符串，用空格隔开

输出描述:

每一行输出这两个字行用的最小操作数

def minDistance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

    return dp[m][n]

if __name__ == "__main__":
    str1, str2 = [x for x in input().strip().split(' ')]
    res = minDistance(str1, str2)
    print(res)

第三题

题目描述
众所周知，大栗是一只非常爱学习的能猫。最近大栗迷上了学英语，为了锻炼自己对英文字母的敏锐感，完美主义的大栗设计了一个严苛的训练项目:从一串长度为N且仅包含大小写字母a-z A-Z)的字符串S中选出一个最优的子序列T，满足字符串中出现的所有字母都出现在子序利中，且子序列的字典序最小，（使用ascii编码来确定大小写字母间的字典序）
例如，对于S串”ccbdabbddcc”，最优的 T 串为”abdc”

输入描述：

输入只包含一行，为S串

输出描述：

输出只包含一行，为最优的子序列 T

腾讯

第一题

题意大致是，一个数组表示栅栏的高度，小明要拆除连续的 k 个栅栏，并且保证栅栏高度总和最小

if __name__ == "__main__":
    n, k = [int(x) for x in input().strip().split(' ')]
    h = [int(x) for x in input().strip().split(' ')]
    res = 0
    for i in range(k):
        res += h[i]
    ans = res
    index = 0
    for i in range(k, n):
        res -= h[i-k]
        res += h[i]
        if res < ans:
            ans = res
            index = i-k+2
    print(index)

第二题

题目描述：
给你一个 n * m 的二维矩阵，每个格子有且仅有 . 和 x 两种状态。. 的格子没破损，但走一次之后会变成 x 状态。’x’ 走 1 次会掉下去；x的格子已破损，再走会掉下去；让你判断能不能从起点(start_x, start_y)走到(end_x, end_y)，并且走到(end_x,end_y)刚好能掉下去。

测试样例

2
4 6
X…XX
…XX.
.X..X.
……
1 6
2 2
9 47
….X.X.X.X…X..X…..X..X..X..X….X.X…X..X
XX..X…X………X…X…X..X.XX……X…X…
..XX…X…….X…..X…..X.XX..X…..X..XX…
.X…XX….X…X…….X.X…X……X.X.X……
X……X..X.XXX….X…X.X.XX..X…….X….X.X
….XX.X…X.XXX.X..XX.XXX…XXX..XX.X.X.XX..XX
………X…X.XXXX…XX.XX….XX..X…X….X..
………….X….XXXX….X.X…XX.XX.X.X..X…
.X……X…..X……X……X.X.X..X…….XXX.
2 34
7 30

if __name__ == "__main__":
    t = int(input())
    while t > 0:
        n, m = [int(x) for x in input().strip().split(' ')]
        net = []
        for i in range(n):
            tem = list(input())
            net.append(tem)
        x0, y0 = [int(x) for x in input().strip().split(' ')]
        x1, y1 = [int(x) for x in input().strip().split(' ')]
        x_tar, y_tar = x1-1, y1-1
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        stack = []
        stack.append((x0-1, y0-1))
        while stack != []:
            x, y = stack[-1]
            if x == x_tar and y == y_tar:
                if net[x][y] == 'X':
                    print('YES')
                else:
                    cnt = 0
                    if 0 <= x-1 < n and 0 <= y < m and net[x-1][y]=='.': cnt += 1
                    if 0 <= x < n and 0 <= y+1 < m and net[x][y+1]=='.': cnt += 1
                    if 0 <= x+1 < n and 0 <= y < m and net[x+1][y]=='.': cnt += 1
                    if 0 <= x < n and 0 <= y-1 < m and net[x][y-1]=='.': cnt += 1
                    if cnt < 2: print('NO')
                    else: print('YES')
                break
            flag = False
            for i in range(4):
                x_ = x + dx[i]
                y_ = y + dy[i]
                if 0 <= x_ < n and 0 <= y_ < m and net[x_][y_] == '.' and (x_, y_) not in stack:
                    stack.append((x_, y_))
                    flag = True
                    break
            if flag == False:
                stack.pop(-1)
                net[x][y] = 'X'

        if stack == []:
            print('NO')

        t -= 1

能够通过两个测试样例

第三题

小明开了个店，冰淇淋有 n 个配料，店里每个配料的原材料数量为 wi ，每个原材料在商店的价格为 vi, 小明有 m 元钱，问可以最多做多少冰淇淋？

def cost(num, w, v):
    price = 0
    for i in range(n):
        if w[i] > num:
            continue
        price += v[i]*(num-w[i])
    return price

if __name__ == "__main__":
    n, m = [int(x) for x in input().strip().split(' ')]
    w = [int(x) for x in input().strip().split(' ')]
    v = [int(x) for x in input().strip().split(' ')]
    l = min(w)
    r = 1 + m//sum(v) + max(w)
    while l < r:
        mid = (l + r + 1) >> 1
        if cost(mid, w, v) < m:
            l = mid
        else:
            r = mid-1
    print(l)

第四题

题目描述
幅员辽阔的企鹅王国，共有 N 个大城市，标号从 1 到 N。每个城市都有且仅有一个机场。机场间设有 M 条常用单向直飞的航线。对于第 i(1≤i≤M) 条航线，从 Ui 号城市的机场起飞，抵达 vi 号城市，机票价格为 Wi。

由于某些特殊原因，航空公司临时决定，在接下来的Q天内，每天除了原有的 M 条常用航线外，新增一条特殊航线。对于第 i(1≤i≤Q)天，特殊航线从 si 号城市的机场，途经编号在 [li,ri) 区间内的所有城市，最终抵达 ri 号城市，机票价格为 pi。但是这种特殊航线只能在 si 号城市上飞机，[li, ri] 这段区间内的城市下飞机，不可中途登机。且该天的航线不会延续到第二天。

小Q是该航空公司的一名员工。他的家住在1号城市，而公司在N号城市。他希望知道，对于接下来的Q天，他从家乘飞机到公司，至少需要花费多少钱买机票？

1
2

第五题

题目描述

小Q在假期的时候去一个密室探险,这个密室可以看成? : 个 n * 3 的格子，小Q最开始可以选择第一行的任意一个格子进入 ,此后的每一步，他可以选择下一行的当前位置或左侧一格或右侧一格，简单的说，假设小Q当前坐标为(x,y) ,哪么他下一步可以前进至(x+1,y-1)或(x+1,y)或(x+1,y+1)，但他不能走出格子。每个格子都有一个数字，代表走到该格子可以得到的分数，但密室中有一些魔法格子，他们的数字为 0，当小Q经过魔法格子后，他在之后得到的分数都会取相反数，分数可多次反转，请问小Q在探险至密室的最后一行后，最多能得到多少分呢?

输入描述:

输入第一行将包含一个数字，你，代表密室的行数。之后的 n 行每行将包含 3 个数字w，代表密室每一行的三个数字。1 <= n <= 100000;
-100000 <= w <= 100000;

输出描述:

输出一个数字，代表小Q可以获得的最高分数。

输入

6
1 2 3
8 9 10
5 0 5
-9 -8 -10
0 1 2
5 4 6

输出

27

1
2

字节跳动第二次

第一题豆油瓶

题目描述：
抖音上每天都有几亿用户，如果用户 A 和 B 互动不少于 3 次，我们就认为 A 和 B 属于“豆油”，如果 A 和 B 是“豆油”，B 和 C 也是“豆油”，那么 A 和 C 也互为“豆油”，我们定义“豆油瓶”就是由直系和间接朋友所组成的群体。

给定个 N×N 的矩阵 M，代表抖音上所有用户的互动次数，如果M[i][j]= 5，那么第i个和第j个用户就互动过5次，为 0 的话代表没有互动，对于i = j，即同个用户，互动次数我们计为0。请你计算并输出发现的抖音上所有“豆油瓶”的个数。

输入描述:
输入第1行：二维数组的行数(列数一样)N
接下来的N行每行N个数字，空格分割

输出描述:
输出发现的“豆油瓶”数量 k

示例1:
输入

3
0 4 0
4 0 0
0 0 0

输出

2

解释：第1个和第2个用户互动超过3次，互为豆油第3个学生和其他人没有互动，自成个豆油瓶，所以结果为2

示例2:
输入

3
0 4 0
4 0 6
0 6 0

输出

1

解释：第1个和第2个用户互动超过3次，互为豆油，第2个和第3个用户也互为豆油，所以1和3互为间接豆油，三个用户都在同一个豆油瓶里，返回1

N的范围为[1,200]
所有学生自己对自己都是1，即M[i][i]=1
如果M[i][j]=1，那么M[j][i]=1

if __name__ == "__main__":
    n = int(input())
    net = []
    for i in range(n):
        node = [int(x) for x in input().strip().split(' ')]
        net.append(node)
    vis = [0]*n
    res = 0
    while min(vis) == 0:
        t = [i for i in range(n) if vis[i] == 0]
        vis[t[0]] = 1
        q = []
        q.append(t[0])
        while q:
            h = q.pop(0)
            for j in range(n):
                if net[h][j] >=3 and vis[j] == 0:
                    q.append(j)
                    vis[j] = 1
        res += 1
    print(res)

没测试不知道能不能 AC

第二题

题目描述
现有一个圆形花园共有 n 个入口，现在要修些路，穿过这些花园。要求每个入口只能有一条路，所有的路均不会相交，求所有可行的方法总数。
若圆形花园中有四个入口，答案2
若圆形花园中有六个入口，答案4

输入描述
整数n，代表有n个花园入口，n为2的倍数，n在2到1000的整数区间范围内

输出描述
输出整数 m mod 1000000007，采用 mod 1000000007 降低数字量级。

if __name__ == "__main__":
    n = int(input())
    res = [0]*(n+1)
    res[0] = 1
    for i in range(2, n+1, 2):
        for j in range(0, (i-2)+1, 2):
            res[i] += (res[j]*res[i-2-j])
        res[i] = res[i] % 1000000007
    print(res[n])

卡特兰数，leetcode 96题目，AC 100%

第三题 2048游戏

题目描述
2048游戏是一个 4×4 的矩阵，用户可以按上下左右4个方向键让所有的方块向同个方向运动，两个相同数字方块撞一起之后合并成为他们的和。每次操作之后随机生成个2或者4
合并规则：相邻会碰撞的两个数字合并且一个位置只会触发一次合并，且优先合并移动方向顶部的位罟
比如 [2 2 2 2] 行向右合井后为 [0 0 4 4] [0 2 2 2] 行向右合并后为 [0 0 2 4]

输入描述：

输入第一行是用户按下的方向键，1代表上，2代表下，3代表左，4代表右，接下来是一个 4×4 的矩阵，空格分割，0 代表该位置没有数字。

输出描述：

输出用户按下该方向键后的矩阵数值，忽略随机产生数字

输入

1
0 0 0 2
0 0 0 2
0 0 4 8
0 0 4 8

输出

0 0 8 4
0 0 0 16
0 0 0 0
0 0 0 0

输入

2
0 0 0 0
0 0 2 2
0 2 8 8
2 4 2 16

输出

0 0 0 0
0 0 2 2
0 2 8 8
2 4 2 16

1
2

第四题

题目描述
在漫天的星空里散落着一些糖果，他们各有各的甜度，有一些糖果之间会按照一定的规则有桥梁连接，好让你获得了这个糖果之后，可以去获得和该糖果相连的其他糖果，现在你要选择一个糖果开始，去尽可能得到更多的糖果。
我们将让过编号——1,2,…,n，每一个糖果的甜度记为 a[i]，若糖果 i 和糖果 j 甜度的最大公约数 > 1，则糖果 i 和糖果 j 之间会有桥梁连接。

输入描述:
首先输入一个数字n，表示天上有n个糖果
接下来一行有n个数字，表示各个糖果的甜度

输出描述
输出一个数，表示最多能获得多少个糖果

示例1
输入：

6
20 50 22 74 9 63

输出：

4

说明
各个糖所构造出的图如下
因为20 50 22 74两两之间至少有公约数2 所以两两之间有边。9和63的最大公约是9。9和63有边，其他公约数为1，所以没有边。

def GCD(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return b


if __name__ == "__main__":
    n = int(input())
    suger = [int(x) for x in input().strip().split(' ')]
    net = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if GCD(suger[i], suger[j]) > 1:
                net[i][j] = 1
                net[j][i] = 1
    vis = [0] * n
    ans = 0
    while min(vis) == 0:
        t = [i for i in range(n) if vis[i] == 0]
        vis[t[0]] = 1
        q = []
        q.append(t[0])
        res = 0
        while q:
            h = q.pop(0)
            res += 1
            for j in range(n):
                if net[h][j] == 1 and vis[j] == 0:
                    q.append(j)
                    vis[j] = 1
        ans = max(ans, res)
    print(ans)

第一次写该答案 AC 70%，提示内存使用过大

def GCD(a,b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return b

if __name__ == "__main__":
    n = int(input())
    suger = [int(x) for x in input().strip().split(' ')]
    net = []
    for i in range(n):
        node = []
        for j in range(n):
            if i != j and GCD(suger[i], suger[j]) > 1:
                node.append(j)
        net.append(node)
    print(net)
    vis = [0]*n
    ans = 0
    while min(vis) == 0:
        t = [i for i in range(n) if vis[i] == 0]
        vis[t[0]] = 1
        q = []
        q.append(t[0])
        res = 0
        while q:
            h = q.pop(0)
            res += 1
            for j in net[h]:
                if vis[j] == 0:
                    q.append(j)
                    vis[j] = 1
        ans = max(ans, res)
    print(ans)

优化了 net 数组内存，待测试

拼多多

第一题 严格升序

第二题 判断是否收尾相接形成圆环

第三题 最短平均等待时间

第四题 搭积木

网易云音乐

第一题

第二题

第三题

第四题

贝壳

第一题

第二题 消失的卡片

第三题

网易互娱

第一题

第二题

第三题

字节跳动

第一题 上学闹钟

第二题 加密通信

第三题 发工资

第四题

作业帮（8.14）

第一题

第二题

第三题

腾讯

第一题

第二题

第三题

第四题

第五题

字节跳动 第二次

第一题 豆油瓶

第二题

第三题 2048游戏

第四题

第一题严格升序

第二题判断是否收尾相接形成圆环

第三题最短平均等待时间

第四题搭积木

第二题消失的卡片

第一题上学闹钟

第二题加密通信

第三题发工资

字节跳动第二次

第一题豆油瓶