美团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 有兴趣可以看看
#面试复盘##春招##实习##笔试题目#