4.9 美团笔试py3 ac前4题思路和代码

代码不是很好看。前4题都ac了，最后一题9%，求大佬思路

第一题：

给定一个时间，包括星期、时、分，然后再给一个分钟数n，输出给定时间往前n分钟的星期、时、分，时分都是2位，不足首位补0。
思路：先把往前推的天数对10080取余，也就是一周的分钟数，然后对week，h，m的修改分别求出来，通过一个标志位判断是否借位：

pre = pre % 10080
week_ = pre // 1440
h_ = (pre % 1440) // 60
m_ = pre % 60
if m < m_:
    carry = 1
    m += 60 - m_
else:
    carry = 0
    m -= m_
if h < h_ + carry:
    h = h + 24 - h_ - carry
    carry_w = 1
else:
    h = h - h_ - carry
    carry_w = 0
week_ += carry_w
if week <= week_:
    week = week + 7 - week_
else:
    week = week - week_
h, m = str(h), str(m)
if len(h) == 1:
    h = '0' + h
if len(m) == 1:
    m = '0' + m
print(str(week))
print(h + ':' + m)

第二题：

有n个运动员，给2个长为n的数组，分别为出发时各个位置上运动员的编号和到达时运动员的编号，那么问到达时超过了别人的运动员有几个。
例子：
5
[5, 3, 1, 4, 2]
[2, 4, 5, 1, 3]
答案：
3
第一行为出发时的编号，第二行为到达时的编号，上例中只有3和5没有超过别人。
额。。双指针，具体看代码

n = 5
start = [5, 3, 1, 4, 2]
end = [2, 4, 5, 1, 3]

res = 0
idx1, idx2 = 0, 0
s = set()
while idx1 < n:
    if start[idx1] in s:
        idx1 += 1
        continue
    while end[idx2] != start[idx1]:
        res += 1
        s.add(end[idx2])
        idx2 += 1
    idx1 += 1
    idx2 += 1
print(res)

第三题

场景就不说了
给n和k，输出最小的x使得
[x] + [x/k] + [x/k^2] + ...
[x]为向下取整，总有一个时刻[x/k^m]==0，因此求使得前面m项和大于n的最小x。
思路：x从1开始会超时，我的解法比较暴力，只是在x的开始位置求了一下，从[n/k]*(k-1)开始，直到n,然后就AC了。。

n, k = 10, 3
ans = -1
for i in range(n // k * (k - 1), n + 1):
    total = 0
    ii = i
    while ii:
        total += ii
        if total >= n:
            ans = i
            break
        ii //= k
    if ans != -1:
        break
print(ans)

第四题

场景是正方形SABC，正方形各个点都是联通的，从S开始，经过n步之后回到S的不同路径。
思路：dp不行，会超时，找规律
n　　S　　A　　B　　C
0　　1　　0　　0　　0
1　　0　　1　　1　　1
2　　3　　2　　2　　2
3　　6　　7　　7　　7
每一轮迭代之后大概就是这样的，规律显而易见了。。
例子：
n = 3
答案：
6
解释：
S->A->B->S
S->A->C->S
S->B->A->S
S->B->C->S
S->C->A->S
S->C->B->S

n = 3
a, b = 1, 0
for i in range(1, n + 1):
    if i % 2 == 1:
        a = (3 * b) % 1000000007
        b = a + 1
    else:
        a = (3 * b) % 1000000007
        b = a - 1
print(a)

看到有人觉得第四题规律不知道怎么找的，我想了下，是可以推出来的

dp的思想，S是从ABC过来的，ABC其实是一样的，同等地位的，所以dp[n][S] = 3 * dp[n-1][A]，然后就是ABC的规律了。A是从SBC过来的，因此dp[n][ABC] = dp[n-1][S] + 2 * dp[n-1][BC]，所以结果就是
S, A = 3 * A, S + 2 * A
代码如下：

n = 3
a, b = 1, 0
for i in range(n):
    a, b = (3 * b) % 1000000007, (a + 2 * b) % 1000000007
print(a)

第五题

没思路，求大佬告知