Google 2021实习OA

第一题可以用sliding window来解

1. from collections import defaultdict
   
2. def longest_unique_subarray(arr, k):
   
3.     l, r = 0, 0
   
4.     memo = defaultdict(int)
   
5.     longest = 0
   
6.     ret = 0
   
7.    
   
8.     while r < len(arr):
   
9.         memo[arr[r]] += 1
   
10.         if memo[arr[r]] > longest:
    
11.             longest = memo[arr[r]]
    
12.         if r-l+1-longest <= k:
    
13.             ret = max(ret, r-l+1)
    
14.         else:
    
15.             memo[arr[l]] -= 1
    
16.             if arr[l] == arr[r]:
    
17.                 for val in memo.values():
    
18.                     longest = max(longest, val)
    
19.             l += 1
    
20.         r += 1
    
21.     return ret

复制代码

跑了几个case都没有问题 有没有大佬帮忙看看有没有什么edgecase没有考虑到

第一题为毛不能直接O(20 * 2 * n)
每个值扫一遍， 用two pointer
p1一直向前直到遇到第四个不一样的值
然后p2向前一直遇到一个不一样的值
随时更新maxlength就行，每个value最多被扫两遍所以是O(2n * 20)？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies