logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
如何O(1)复杂度比较两个Hashmap相等
avatar
如何O(1)复杂度比较两个Hashmap相等# JobHunting - 待字闺中
M*r
1 楼
有一道题，要maintain一个sliding window，这个window用Hashmap来实现，
但是java里面hashmap.equals复杂度是O（n)
原题
Given a list of keywords and a list of search words, return a list of
indices that indicate the beginning of sequences of adjacent keywords.
Examples:
Search list: ['hello', 'hi', 'welcome', 'greetings', 'hi', 'greetings', 'hey
', 'hello']
Keywords: ['hi', 'hey', 'greetings']. from: 1point3acres.com/bbs
Output: [4]
Search list: ['i', 'saw', 'susie', 'sitting', 'in', 'a', 'shoe', 'shine', '
shop', 'where', 'she', 'sits', 'she', 'shines', 'and', 'where', 'she', '
shines', 'she', 'sits']
Keywords: ['she', 'sits', 'shines']
Output: [11, 17]
Search list: ['peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', '
peppers', 'a', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper',’ '
picked', 'if', 'peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', '
peppers', 'wheres', 'the', 'peck', 'of', 'pickled', 'peppers', 'peter', '
piper', 'picked']
Keywords: ['peter', 'picked', 'piper']
Output: [0, 13, 17, 31]
avatar
d*g
2 楼
Impossible
avatar
M*r
3 楼
我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来


: Impossible



【在 d*********g 的大作中提到】
: Impossible
avatar
d*g
4 楼
以我多年刷题经验，你走偏了。you are not on the right track


: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来



【在 M******r 的大作中提到】
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
:
: Impossible
:

avatar
M*r
5 楼
那这道题应该怎么做？出题人跟我说这道题能做到o(n)


: 以我多年刷题经验，你走偏了。you are not on the right track



【在 d*********g 的大作中提到】
: 以我多年刷题经验，你走偏了。you are not on the right track
:
:
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:

avatar
w*o
6 楼
我觉得可以这样。
把Keywords建踹树。
然后hashmap对keywords统计。
把hashmap里面每个当前的值删了。如果map为空，就记录左指针。
并且把左指针的的值放入map里。
这样就O(n * k)了 k为字符串平均长度。
avatar
s*y
7 楼
sha256 两个文件
avatar
c*w
8 楼
严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
是O（1）所以overall只O（n）
avatar
z*o
9 楼
two pointers 可解
avatar
M*r
10 楼
赞。

check

【在 c******w 的大作中提到】
: 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
: ，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
: 是O（1）所以overall只O（n）
avatar
h*n
11 楼
这不就是LeetCode #76 Minimum Window Substring的变形吗？只不过Keywords必须
相邻，也就是windows.size()等于keywords.size()
avatar
M*r
12 楼
有一道题，要maintain一个sliding window，这个window用Hashmap来实现，
但是java里面hashmap.equals复杂度是O（n)
原题
Given a list of keywords and a list of search words, return a list of
indices that indicate the beginning of sequences of adjacent keywords.
Examples:
Search list: ['hello', 'hi', 'welcome', 'greetings', 'hi', 'greetings', 'hey
', 'hello']
Keywords: ['hi', 'hey', 'greetings']. from: 1point3acres.com/bbs
Output: [4]
Search list: ['i', 'saw', 'susie', 'sitting', 'in', 'a', 'shoe', 'shine', '
shop', 'where', 'she', 'sits', 'she', 'shines', 'and', 'where', 'she', '
shines', 'she', 'sits']
Keywords: ['she', 'sits', 'shines']
Output: [11, 17]
Search list: ['peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', '
peppers', 'a', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper',’ '
picked', 'if', 'peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', '
peppers', 'wheres', 'the', 'peck', 'of', 'pickled', 'peppers', 'peter', '
piper', 'picked']
Keywords: ['peter', 'picked', 'piper']
Output: [0, 13, 17, 31]
avatar
d*g
13 楼
Impossible
avatar
M*r
14 楼
我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来


: Impossible



【在 d*********g 的大作中提到】
: Impossible
avatar
d*g
15 楼
以我多年刷题经验，你走偏了。you are not on the right track


: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来



【在 M******r 的大作中提到】
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
:
: Impossible
:

avatar
M*r
16 楼
那这道题应该怎么做？出题人跟我说这道题能做到o(n)


: 以我多年刷题经验，你走偏了。you are not on the right track



【在 d*********g 的大作中提到】
: 以我多年刷题经验，你走偏了。you are not on the right track
:
:
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:

avatar
w*o
17 楼
我觉得可以这样。
把Keywords建踹树。
然后hashmap对keywords统计。
把hashmap里面每个当前的值删了。如果map为空，就记录左指针。
并且把左指针的的值放入map里。
这样就O(n * k)了 k为字符串平均长度。
avatar
s*y
18 楼
sha256 两个文件
avatar
c*w
19 楼
严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
是O（1）所以overall只O（n）
avatar
z*o
20 楼
two pointers 可解
avatar
M*r
21 楼
赞。

check

【在 c******w 的大作中提到】
: 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
: ，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
: 是O（1）所以overall只O（n）
avatar
h*n
22 楼
这不就是LeetCode #76 Minimum Window Substring的变形吗？只不过Keywords必须
相邻，也就是windows.size()等于keywords.size()
avatar
l*e
23 楼
^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
一模一样的
avatar
H*5
24 楼
second this


: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword
。做法

: 一模一样的



【在 l***e 的大作中提到】
: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
: 一模一样的
avatar
z*n
25 楼

adjacent不意味着windows.size()等于keywords.size()， key word a,b,c
合法区间:a,a,a,a,b,b,b,a,a,a,a,b,b,b,c,c,c

【在 h*****n 的大作中提到】
: 这不就是LeetCode #76 Minimum Window Substring的变形吗？只不过Keywords必须
: 相邻，也就是windows.size()等于keywords.size()
avatar
z*n
26 楼

不一样，题目有adjacent要求，LC76 BANC含ABC，但这题BANC就非法了。

【在 l***e 的大作中提到】
: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
: 一模一样的
avatar
s*n
27 楼
明白人

【在 s*****y 的大作中提到】
: sha256 两个文件
avatar
z*n
28 楼

明白个毛。。。。
你生成sha是不是得便利一遍文件？你有这功夫直接把俩文件一个一个字符比了就行了
。sha是这个场合用的么？

【在 s******n 的大作中提到】
: 明白人
相关阅读
sr. engineer在面试一个sr.engineering manager的职位Re: 碰到两个都是FB 傻逼老中面试官 (转载)求推荐一本数据结构你认为最经典的书。请教一个offer也问职业选择Software Tester 在找工作，please refer me --- Northern Californiaapple onsite后都是默拒的么小弟offer真心求比较，Bloomberg, ServiceNow, Okta, EpicRumor: 果果要造车了问个投amazon的简历问题湾区女生这么开放啊 (转载)Google的Youtube组怎么样？请问有没有人找过中介挂靠cpt想问问， 我刷leetcode时， 做不出时最近找工作的一点经验内推一个职位注重analytics，in DC【视角】老板是个无能SB？Job opportunity in Alibaba Bay Area15年初毕业的master， 找大公司cs full time是不是已经晚了Experienced hardware engineer position
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。