首页 > 美团算法综合8.15:1,0.5,1,0.18
头像
陆诚
编辑于 2020-08-21 18:25
+ 关注

美团算法综合8.15:1,0.5,1,0.18

四道题目分别是1,0.5,1,0.18,求解2,4解顺便贴出自己的代码。
1,四倍回文,如果一个数字的四倍和自己的回文相同那就是我们要找的回文,求1~n范围有多少这样的回文,数据是10^7除4之后是10^6,直接暴力。
def f1(n):
    r = []
    c = n // 4
    for i in range(1, c + 1):
        if str(4*i) == str(i)[::-1]:
            r.append(i)
    return r

while True:
    try:
        n = int(input())
        r = f(n)
        print(len(r))
        for i in r:
            print(str(i), ' ', str(i)[::-1])
    except:
        break

2,给一个车票记录的列表,列表的每个元素是做过的一趟车的起点和终点,如果一次出行完整的从车票起点走到了终点那就算做一次旅行,求总共有多少次旅行,0.55渣渣求解答0.55的渣渣明白了,如果一趟旅行的起点和终点是一样的那也算一次旅行,就是坐车从北京到北京也算,原地TP。。。
def f2(ts):
    if len(ts) == 1:
        u, v = ts[0][0], ts[0][1]
        if u == v:
            return 1
        elif u != v:
            return 0
    res = 0
    curr, last = '', ''
    for t in ts:
        u, v = t
        if curr == '' and last == '':
            curr, last = u, v
        elif curr == v and last == u:
            res += 1
            curr, last = '', ''
        elif last == u and curr != v:
            last = v
    return res

while True:
    try:
        n = int(input())
        ts = []
        for _ in range(n):
            temp = input().split()
            ts.append(temp)
        print(f(ts))
    except:
        break

3,并查集解决,模板直接套,具体题目的描述记不清了,反正只要熟练掌握并查集就可以做。
import collections

def f3(hs, n):
    roots = {}
    res = collections.defaultdict(set)
    def findroot(node):
        nonlocal roots
        if node not in roots:
            roots[node] = node
        elif roots[roots[node]] != roots[node]:
            roots[node] = findroot(roots[node])
        return roots[node]
    
    for h in hs:
        u, v = h
        
        if u not in roots:
            roots[u] = findroot(v)
        elif v not in roots:
            roots[v] = findroot(u)
        else:
            roots[findroot(u)] = findroot(v)
    
    for i in range(1, n + 1):
        curr = findroot(i)
        res[curr].add(i)
    ks = []
    
    for k in res:
        ks.append(sorted(res[k]))
    ks.sort(key = lambda k: k[0])
    return ks

while True:
    try:
        n, m = list(map(int, input().split()))
        hs = []
        for _ in range(m):
            temp = list(map(int, input().split()))
            hs.append(temp)
        ks = f(hs, n)
        print(len(ks))
        for k in ks:
            print(' '.join(map(str, k)))
    except:
        break

4,最后一道也是最难的一题,有n辆车和ab两个城市,a、b两个城市分别需要a、b辆车(a + b < n),然后给出n辆车每辆去往a城市或者b城市的收益,求合满足ab城市调度需求下能得到的最大收益,想的是通过dp(i,j,k)代表k辆车已经使用同时ab两地分别已经有i、j辆车的情况下得到的最大收益,但是三维动态规划没法得到解,求指点:
def f4(ps, a, b, n):
    dp = [[[0] * (n + 1) for _ in range(b + 1)] for _ in range(a + 1)]
    for i in range(a):
        for j in range(b):
            for k in range(n):
                if i == a:
                    dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j][k] + ps[k][1], dp[i][j][k])
                if j == b:
                    dp[i + 1][j + 1][k + 1] = max(dp[i][j + 1][k] + ps[k][0], dp[i][j][k])
                else:
                    dp[i + 1][j + 1][k + 1] = max(dp[i][j][k],dp[i][j + 1][k] + ps[k][0], dp[i + 1][j][k] + ps[k][1])
    print(dp)
    return dp[-1][-1][-1]
情急之下直接深搜一波,加上lru缓存过了0.18,估计是11个测试用例的2个吧
import functools

def f(ps, a, b, n):
    res = 0 
        @functools.lru_cache def dfs(i, j, tmp, cur):
        nonlocal res, ps
        if i == 0 and j == 0:
            res = max(res, tmp)
            return
        if cur == len(ps):
            return
        if i == 0:
            dfs(i, j - 1, tmp + ps[cur][1], cur + 1)
            dfs(i, j, tmp, cur + 1)
        if j == 0:
            dfs(i - 1, j, tmp + ps[cur][0], cur + 1)
            dfs(i, j, tmp, cur + 1)
        else:
            dfs(i - 1, j, tmp + ps[cur][0], cur + 1)
            dfs(i, j - 1, tmp + ps[cur][1], cur + 1)
            dfs(i, j, tmp, cur + 1)
        
    dfs(a, b, 0, 0)
    return res

2,4求解答!!!

全部评论

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

相关热帖

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

近期精华帖

热门推荐