亚麻intern oa1中一题：

题目很难呐，说好的都是easy和medi

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

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

了oa2，但怀疑是越来越卷了。

1. def rollinghash(nums, k):
   
2.     mod = 2 ** 64 - 1
   
3.     seen = set()
   
4.     for i in range(len(nums)):
   
5.         hash = 0
   
6.         count = 0
   
7.         for j in range(i, len(nums)):
   
8.             if nums[j] % 2 == 1:
   
9.                 count += 1
   
10.             if count > k:
    
11.                 break
    
12.             hash *= 1000
    
13.             hash += nums[j]
    
14.             hash %= mod
    
15.             seen.add(hash)
    
16.     return len(seen)
    
17. print(rollinghash([1,2,3,4], 1))
    
18. print(rollinghash([i for i in range(1, 1001)], 1000))

复制代码

这道题可以用rolling hash，就是rabin karp字符串匹配的思想，可以参考https://medium.com/algorithm-solving/rolling-hash-ecd7c08358ab

我也遇到了这题 真的挺难的 主要是去重不好做
一开始用c++ 我是把array转成string 这样只能过8/12
这题用c++感觉没法做 可以用Python来hash tuple

求问楼主是几号提交的申请呀？内推了没有消息ww

我感觉这题挺难的。
提供一个比较简单的思路
前缀和统计一个子数组的奇数

枚举所有的子数组，得到符合要求k的子数组

在上面这个过程，得进行array的哈希，我比较奇怪用的是golang刷题，我不知道别的语言能不能这样写。

大概就是 map[[]int]bool

这样也许能非常勉强地卡过。 说实话不太明白该怎么去重比较好，可能根据长度来？ 比如为n的必须是唯一的。

希望听听大佬的解释。

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

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

KerriganVAPG 发表于 2021-10-20 12:13:43
我感觉这题挺难的。
提供一个比较简单的思路
前缀和统计一个子数组的奇数

https://leetcode.com/discuss/int...odd-elements/265140
可以参考这个 我最后用Python全过了 不过现在还没消息

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

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

明天打算做一下亚麻的哦欸，希望不要遇到这道题

感谢zszszs