Google 2021实习OA

喜笑颜开进去，愁眉苦脸出来。遇到的其中一题是19年变体，另一题变得稍微有点大，看到有点面生...

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

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

有用的话求加大米，看面经急需。感恩！

第一题为毛不能直接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

我的想法差不多, dp在subarray end 在每一个index上的时候 使用掉k次替换后的最长的只有数字X的subarray

1. def longest_unique_subarray(arr, k):
   
2.     dp=[[1 for i in range(k+1)] for j in range(-10, 11)]
   
3.     for i in range(-10, 11):
   
4.         dp[i][0]=0
   
5.     dp[arr[0]][0]=1
   
6.     ret=1
   
7.     for i in range(1, len(arr)):
   
8.         for target in range(-10, 11):
   
9.             if target==arr[i]:
   
10.                 for replace in range(k+1):
    
11.                     dp[target][replace]+=1
    
12.                     ret=max(ret, dp[target][replace])
    
13.             else:
    
14.                 for replace in range(k-1, -1, -1):
    
15.                     dp[target][replace+1]=dp[target][replace]+1
    
16.                     ret=max(ret, dp[target][replace+1])
    
17.                 dp[target][0]=0
    
18.     return ret
    
19. arrs=[[9,-8],[1,2,10,3,10,10],[3,1,3,3,1,3,1,1]]
    
20. for arr in arrs:
    
21.     print(longest_unique_subarray(arr, 3))

复制代码

[/i][/i]

什么是最长的相等数列？和谁比呀？

第一题是换三次数为任意数，使得原数列的所有数字都相等的subarray长度最大，是这个意思吗？ subarray也要按原来的数列顺序， 只是可以更换element的值是嘛？

熊猫杀很大缺积分 发表于 2020-10-29 12:24:50
第一题是换三次数为任意数，使得原数列的所有数字都相等的subarray长度最大，是这个意思吗？ subarray也要按原来的数列顺序， 只是可以更换element的值是嘛？

是的。要按照原来的顺序，更换任意三个或以下element。

匿名者 发表于 2020-10-30 13:43
是的。要按照原来的顺序，更换任意三个或以下element。

感谢楼主 祝早日move forward

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

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

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

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

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

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