首页 > 9.1拼多多笔试部分代码
头像
Fzldq
编辑于 2020-09-02 15:53
+ 关注

9.1拼多多笔试部分代码

第一题
n = int(input())
dp = [[0] * n for _ in range(n)]
half = n // 2


def func(i, j):
    if i + 1 > half:
        if j + 1> half:
            if i > j:
                return 6
            else:
                return 7
        else:
            if i + j + 1 > n:
                return 5
            else:
                return 4
    else:
        if j + 1 > half:
            if i + j + 1 > n:
                return 8
            else:
                return 1
        else:
            if i > j:
                return 3
            else:
                return 2


for i in range(n):
    for j in range(n):
        if i == j&nbs***bsp;i + j + 1 == n:
            continue
        if n & 1:
            if i == half&nbs***bsp;bsp;j == half:
                continue
        dp[i][j] = func(i, j)

for i in dp:
    print(*i, sep=' ')

第二题并查集穷举超时,25%,求大佬代码😂
刚发现考试时的代码细节上有问题(太难受了),修改之后大概能再多点分了,不过根据leetcode的经验,python写并查集效率挺低的,大概达不到70%
我习惯m是行n是列
m, n = map(int, input().split())
grid = []
for _ in range(m):
    grid += [list(map(int, input().split()))]


class Solution:
    def UF(self, grid, m, n):
        self.count = 0
        self.parent = [-1] * (m * n)
        self.size = [0] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    self.parent[i * n + j] = i * n + j
                    self.size[i * n + j] = 1
                    self.count += 1
        self.cnt = self.count

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP == rootQ:
            return
        if self.size[rootP] > self.size[rootQ]:
            self.parent[rootQ] = rootP
            self.size[rootP] += self.size[rootQ]
        else:
            self.parent[rootP] = rootQ
            self.size[rootQ] += self.size[rootP]
        self.count -= 1

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def numIslands(self, grid):
        if len(grid) == 0&nbs***bsp;len(grid[0]) == 0:
            return 0
        m, n = len(grid), len(grid[0])
        self.UF(grid, m, n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                            self.union(i * n + j, x * n + y)


s = Solution()
s.numIslands(grid)
res = max(s.size)
for i in range(m):
    for j in range(n):
        if grid[i][j] == 0:
            tmp_set = set()
            for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                    tmp_set.add(s.find(x * n + y))
            if len(tmp_set) == 0:
                continue
            tmp = sum(s.size[root] for root in tmp_set) + 1
            if tmp > s.cnt:
                print(s.cnt)
                quit()
            res = max(res, tmp)

print(res)

第三题只拿了60%就不用说了。。普通背包骗个分
第四题集合思想+最小公倍数,数学题
from itertools import combinations as comb
from functools import reduce

n, m = map(int, input().split())
primes = []
for _ in range(m):
    primes += [int(input())]


def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)


def lcm(x, y):
    return x * y // gcd(x, y)


res = 0
plus = 1

for i in range(1, m + 1):
    for j in comb(primes, i):
        tmp = reduce(lcm, j)
        res += plus * (n // tmp)
    plus = - plus
print(res)


全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐