M******r
发帖数: 120 | 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] | d*********g
发帖数: 234 | | M******r
发帖数: 120 | 3 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
: Impossible
【在 d*********g 的大作中提到】
: Impossible
| d*********g
发帖数: 234 | 4 以我多年刷题经验，你走偏了。you are not on the right track
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
【在 M******r 的大作中提到】
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
:
: Impossible
:
| M******r
发帖数: 120 | 5 那这道题应该怎么做？出题人跟我说这道题能做到o(n)
: 以我多年刷题经验，你走偏了。you are not on the right track
【在 d*********g 的大作中提到】
: 以我多年刷题经验，你走偏了。you are not on the right track
:
:
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
| w*******o
发帖数: 113 | 6 我觉得可以这样。
把Keywords建踹树。
然后hashmap对keywords统计。
把hashmap里面每个当前的值删了。如果map为空，就记录左指针。
并且把左指针的的值放入map里。
这样就O(n * k)了 k为字符串平均长度。 | s*****y
发帖数: 253 | | c******w
发帖数: 1108 | 8 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
是O（1）所以overall只O（n） | z*******o
发帖数: 4773 | | M******r
发帖数: 120 | 10 赞。
check
【在 c******w 的大作中提到】
: 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
: ，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
: 是O（1）所以overall只O（n）
| | | h*****n
发帖数: 93 | 11 这不就是LeetCode #76 Minimum Window Substring的变形吗？只不过Keywords必须
相邻，也就是windows.size()等于keywords.size() | M******r
发帖数: 120 | 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] | d*********g
发帖数: 234 | | M******r
发帖数: 120 | 14 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
: Impossible
【在 d*********g 的大作中提到】
: Impossible
| d*********g
发帖数: 234 | 15 以我多年刷题经验，你走偏了。you are not on the right track
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
【在 M******r 的大作中提到】
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
:
: Impossible
:
| M******r
发帖数: 120 | 16 那这道题应该怎么做？出题人跟我说这道题能做到o(n)
: 以我多年刷题经验，你走偏了。you are not on the right track
【在 d*********g 的大作中提到】
: 以我多年刷题经验，你走偏了。you are not on the right track
:
:
: 我搞一个全局hash行不行，就是把map里面所有entry的hashcode加起来或者乘起来
:
| w*******o
发帖数: 113 | 17 我觉得可以这样。
把Keywords建踹树。
然后hashmap对keywords统计。
把hashmap里面每个当前的值删了。如果map为空，就记录左指针。
并且把左指针的的值放入map里。
这样就O(n * k)了 k为字符串平均长度。 | s*****y
发帖数: 253 | | c******w
发帖数: 1108 | 19 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
是O（1）所以overall只O（n） | z*******o
发帖数: 4773 | | | | M******r
发帖数: 120 | 21 赞。
check
【在 c******w 的大作中提到】
: 严重走偏了。指需要一个hashmap存keywords。search words从左往右一个一个扫过去
: ，check是否在keyword里。只需要记一下当前的continous run多长就够了。每次check
: 是O（1）所以overall只O（n）
| h*****n
发帖数: 93 | 22 这不就是LeetCode #76 Minimum Window Substring的变形吗？只不过Keywords必须
相邻，也就是windows.size()等于keywords.size() | l***e
发帖数: 108 | 23 ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
一模一样的 | H**********5
发帖数: 2012 | 24 second this
: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword
。做法
: 一模一样的
【在 l***e 的大作中提到】
: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
: 一模一样的
| z*********n
发帖数: 1451 | 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()
| z*********n
发帖数: 1451 | 26
不一样，题目有adjacent要求，LC76 BANC含ABC，但这题BANC就非法了。
【在 l***e 的大作中提到】
: ^对的。这题明显的leetcode 76变形，只是把character换成了string keyword。做法
: 一模一样的
| s******n
发帖数: 226 | 27 明白人
【在 s*****y 的大作中提到】
: sha256 两个文件
| z*********n
发帖数: 1451 | 28
明白个毛。。。。
你生成sha是不是得便利一遍文件？你有这功夫直接把俩文件一个一个字符比了就行了
。sha是这个场合用的么？
【在 s******n 的大作中提到】
: 明白人
|
|
