首页 > 9.1 拼多多 笔试 算法岗位 3.35/4
头像
Derec_
编辑于 2020-09-01 21:06
+ 关注

9.1 拼多多 笔试 算法岗位 3.35/4

总体是 1.0-0.75-0.6-1.0

1. 12345678找规律,不算难,根据矩阵中i,j的坐标判断matrix[i][j] 的值.  ac 1.0
n = int(input())
matrix = [[0]*n for i in range(n)]
if n%2 == 1:
    for i in range(n):
        for j in range(n):
            if i == n//2&nbs***bsp;j == n//2&nbs***bsp;i==j&nbs***bsp;i+j == n-1:
                continue
            if 0<=i<=n//2-1:
                if 0<=j<=i-1:
                    matrix[i][j] = 3
                elif i<=j<=n//2-1:
                    matrix[i][j] = 2
                elif n//2+1<=j<n-1-i:
                    matrix[i][j] = 1
                else:
                    matrix[i][j] = 8
            if n//2 <= i <= n-1:
                if 0<=j<=n-i-1:
                    matrix[i][j] = 4
                elif n-i-1<j<=n//2:
                    matrix[i][j] = 5
                elif n//2<=j<=i-1:
                    matrix[i][j] = 6
                else:
                    matrix[i][j] = 7

    for i in range(n):
        print(' '.join(list(map(str,matrix[i]))))

if n%2== 0:
    for i in range(n):
        for j in range(n):
            if i==j&nbs***bsp;i+j == n-1:
                continue
            if 0<=i<=n//2-1:
                if 0<=j<=i-1:
                    matrix[i][j] = 3
                elif i<=j<=n//2-1:
                    matrix[i][j] = 2
                elif n//2<=j<=n-1-i:
                    matrix[i][j] = 1
                else:
                    matrix[i][j] = 8
            if n//2 <= i <= n-1:
                if 0<=j<=n-i-1:
                    matrix[i][j] = 4
                elif n-i-1<j<n//2:
                    matrix[i][j] = 5
                elif n//2<=j<=i-1:
                    matrix[i][j] = 6
                else:
                    matrix[i][j] = 7
    for i in range(n):
        print(' '.join(list(map(str,matrix[i]))))
2. 先把1所在的每一块区域回溯计算得到面积,再判断每个0的4个方向1的面积,比对即可 ; 0.75
n,m = list(map(int, input().split()))
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split())))

res = []
all = sum([sum(x) for x in matrix])
def helper(i,j):
    if not (0<=i<=n-1 and 0<=j<=m-1):
        return
    if matrix[i][j] == 0:
        return
    if matrix[i][j] == 2:
        return
    res.append(1)
    matrix[i][j] = 2
    helper(i+1, j)
    helper(i-1, j)
    helper(i, j+1)
    helper(i, j-1)


def change(i,j,num,index):
    if not (0<=i<=n-1 and 0<=j<=m-1):
        return
    if matrix[i][j] == 0:
        return
    if type(matrix[i][j]) is not int:
        return

    matrix[i][j] = [num,index]
    change(i+1, j, num, index)
    change(i-1, j, num, index)
    change(i, j+1, num, index)
    change(i, j-1, num, index)

index = 1
for i in range(n):
    for j in range(m):
        res = []
        helper(i,j)
        num = sum(res)
        change(i,j,num,index)
        index += 1

def concat(i,j):
    tem = 0
    around = set()
    if 0<=i+1<=n-1:
        if matrix[i+1][j]!=0:
            if matrix[i+1][j][1] not in around:
                tem += matrix[i+1][j][0]
                around.add(matrix[i+1][j][1])
    if 0<=i-1<=n-1:
        if matrix[i-1][j]!=0:
            if matrix[i-1][j][1] not in around:
                tem += matrix[i-1][j][0]
                around.add(matrix[i-1][j][1])
    
    if 0<=j+1<=m-1:
        if matrix[i][j+1]!=0:
            if matrix[i][j+1][1] not in around:
                tem += matrix[i][j+1][0]
                around.add(matrix[i][j+1][1])
    
    if 0<=j-1<=m-1:
        if matrix[i][j-1]!=0:
            if matrix[i][j-1][1] not in around:
                tem += matrix[i][j-1][0]
                around.add(matrix[i][j-1][1])
    return tem
# for i in range(n):
#     print(matrix[i])
res = 0
around = set()

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 0:
            tem = concat(i,j)
            # print(tem)
            if tem<all:
                res = max(tem+1,res)
            else:
                res = max(tem,res)
print(res)
3. 带负数的上限背包,没考虑负数,只考虑正数; 0.6
n,m = list(map(int, input().split()))
C = []
V = []
tem = 0
for i in range(n):
    ci, vi = list(map(int, input().split()))
    if ci == 0:
        tem+=vi
        continue
    C.append(ci)
    V.append(vi)



dp = [[tem]+[0]*(m) for _ in range(len(C)+1)]
for i in range(1,len(C)+1):
    for j in range(1,m+1):
        dp[i][j] = dp[i-1][j]
        if C[i-1]<=j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-C[i-1]]+V[i-1])
print(dp[-1][-1])

4. 首先要除去m中的大公约数防止重复计算,然后回溯得到feature中所有的排列组合,再用n一个一个除即可,这里注意,如果是计数个组合,则相加,偶数个,则相减。 ac 1.0
n,m = list(map(int, input().split()))
feature = []
for i in range(m):
    feature.append(int(input()))
feature.sort()
i = 0
while i<=len(feature)-1:
    for j in range(i):
        if feature[i]%feature[j] == 0:
            feature.pop(i)
            i-=1
            break
    i+=1

res = 0
index = []
length = len(feature)
def get(start,tem):
    index.append(tem+[])
    for i in range(start,length):
        get(i+1,tem+[feature[i]])
get(0,[])
index.pop(0)
# print(index)
def product(nums):
    tem = 1
    for num in nums:
        tem*=num
    return tem

for ind in index:
    g = len(ind)
    tem = product(ind)
    k = n//tem
    print(ind,k)

    if g % 2 == 1:
        res+=k
    else:
        res-=k
print(res)

面试求捞。。。


全部评论

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

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐