美团4.2 第三第四题

第二题

# n = int(input())
# nums = list(map(int, input().split()))
n = 5
nums = [1,2,1,2,1]
left = [0] * n 
right = [0] * n 
# 从前往后遍历 left数组 left[i]表示想要开始到i位是单增 需要加多少个数
cur = nums[0]
for i in range(1,len(nums)):
    if nums[i] <= cur:
        left[i] = cur + 1 - nums[i]
        cur += 1
    else:
        cur = nums[i]
# 从后往前遍历 right数组 right[i]表示想要i位到最后是单减 需要加多少个数
cur = nums[-1]
for i in range(len(nums) - 2, -1, -1):
    if nums[i] <= cur:
        right[i] = cur + 1 - nums[i]
        cur +=1 
    else:
        cur = nums[i]
# 计算前缀和和后缀和 省事 直接用了left和right数组
for i in range(1,n):
    left[i] += left[i - 1]
for i in range(n - 2, -1,-1):
    right[i] += right[i + 1]
# 遍历切分点 切分点为i从0到长度-1 切分点代表开始到i严格单增 i+1到最后严格单减,这里不需要研究nums[i]和nums[i +1]的大小关系 因为不管什么样都满足条件
# 一直单增一直单减一定比这个答案大 所以不考虑了 因为left 和right的第一个元素都是0 严谨可以再循环外加上
res = float('inf')
for i in range(n - 1):
    res = min(res, left[i] + right[i + 1])

print(res)

第三题

考试时候总感觉子序列问题滑窗做不了忘记了 用的dp做超时了 现在补一个滑窗的做法 不知道对不对 大佬们看看, 复杂度应该是

from collections import defaultdict
s = 'aacac'
p = 'ac'
l = 0
r = 0
res = []
point = 0
###记录p第一个字母相同的个数
###如果p是'aac'那么相同的就是2 
###这么做是为了 当出现s是'abac'的时候返回的是[2,3]而不是[0,3]
p1 = 1
while p1 < len(p) and p[p1 - 1] == p[p1]:
    p1 += 1
###滑窗 
###找到最小满足子串的位置
###比如aacac应该返回[1,2]和[3,4]
###这些区间必然不可能重叠
hr = defaultdict(int)
while r < len(s):
    if s[l] != p[0]:
        l += 1
        r = l
        hr = defaultdict(int)
        continue
    if point <= p1:
        hr[s[r]] += 1
    if s[r] == p[point]:
        point += 1
    if point == len(p):
        while hr[p[0]] > p1:
            l += 1
            hr[s[l]] -= 1
        res.append([l,r])
        l = r + 1
        r = l 
        point = 0
        hr = defaultdict(int)
        continue
    r += 1
###计算总共有多少个
###计数本质是左右指针不同,只需要管左指针即可,右指针取的范围在r的后面都可以
###[1,2]前面两个 后面3个乘法法则 就是6个
###[3,4]前面最多到前一个l的下一位就是index为2 就可以保证不重复计算 后面只有1个 乘法法则就是2个
###最终就是8个
l = 0 
ans = 0
for i in range(len(res)):
    pre = res[i][0] - l + 1
    back = len(s) - res[i][1]
    ans += pre * back
    l = res[i][0] + 1
print(ans)

第四题

想当然用dp做了 结果a了就没管 后来发现做错了 貌似在某code上有类似的题 1723 有兴趣可以看看

#面试复盘##春招##实习##笔试题目#
全部评论
你好,小白一枚。我想请教一下,第五题编写测试用例怎么评分,难道一定要找到代码的bug吗?那它就给了java代码,我也不会啊。  另外我想问一下第二题的思路,如何理解从中切开,我认为可以让数组不是对半分,但是这样子我就不知道思路了。
点赞 回复
分享
发布于 2022-04-02 16:52
不一样leetcode上那个数据量小可以直接状压dp
点赞 回复
分享
发布于 2022-04-03 09:49
英特尔
校招火热招聘中
官网直投

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务