f*******7 发帖数: 943 | 1 感觉被三哥日了,以后用同样的题伺候三哥
回家发现是这题的变形
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-
characters/
Given a string, find the longest substring T that contains m distinct
characters.
"abcddedd", 3 return cddedd
"ababcccaccbcdef", 4 return ababcccaccbcd
要求O(N)写出来
请问,怎么高效记录distinct char的个数?如果是原题的话,仅仅用s[k] != s[j]比
较就可以,但是m > 2 就得考虑怎么样计数了。。。 |
l********6 发帖数: 129 | |
b**********5 发帖数: 7881 | 3 这是leetcode 原题吧。。。遇到这种题, 还说被黑。。。
推销个我自己的blog, matuanstepmom.blogspot.com,, Lee t code的Java答案和一
些面试题, 然后我工作时, 用到的一些东西
【在 f*******7 的大作中提到】 : 感觉被三哥日了,以后用同样的题伺候三哥 : 回家发现是这题的变形 : https://leetcode.com/problems/longest-substring-with-at-most-two-distinct- : characters/ : Given a string, find the longest substring T that contains m distinct : characters. : "abcddedd", 3 return cddedd : "ababcccaccbcdef", 4 return ababcccaccbcd : 要求O(N)写出来 : 请问,怎么高效记录distinct char的个数?如果是原题的话,仅仅用s[k] != s[j]比
|
a***u 发帖数: 383 | 4 小印是让返回string还是返回长度?返回string的话可以用leetcode的双指针方法。
google面过我一样的题,问的是返回longest string的长度。如果是返回长度。方法是
hashmap,key是char,value是该字符最后一次出现的位置。hashmap存m个distinct
char,如果m+1个distinct char出现了,就把hashmap里面value最小的那个key去掉,
把新的key value加进去。更新一下长度 = 新char的位置-被去掉的key的value
O(n)的难点是怎么从hashmap里面O(1)时间找到最小的value。我当时想的方法是
LRU,hashmap里的value连成一个linkedlist。least use的node就是该去掉的那个 |
j**********3 发帖数: 3211 | |
l********6 发帖数: 129 | 6 ms吧应该是 话说这题现在是要花钱才能做的 我说怎么没有印象~~
[在 jobhunter123 (jobhunting) 的大作中提到:]
:这是哪家? |
f*******7 发帖数: 943 | 7 leetcode那个m = 2的特殊情况吧,今天这个要的是m
【在 b**********5 的大作中提到】 : 这是leetcode 原题吧。。。遇到这种题, 还说被黑。。。 : 推销个我自己的blog, matuanstepmom.blogspot.com,, Lee t code的Java答案和一 : 些面试题, 然后我工作时, 用到的一些东西
|
f*******7 发帖数: 943 | 8 返回string,返回string的话不需要hashmap或set计数吗?
【在 a***u 的大作中提到】 : 小印是让返回string还是返回长度?返回string的话可以用leetcode的双指针方法。 : google面过我一样的题,问的是返回longest string的长度。如果是返回长度。方法是 : hashmap,key是char,value是该字符最后一次出现的位置。hashmap存m个distinct : char,如果m+1个distinct char出现了,就把hashmap里面value最小的那个key去掉, : 把新的key value加进去。更新一下长度 = 新char的位置-被去掉的key的value : O(n)的难点是怎么从hashmap里面O(1)时间找到最小的value。我当时想的方法是 : LRU,hashmap里的value连成一个linkedlist。least use的node就是该去掉的那个
|
b**********5 发帖数: 7881 | 9 你去我blog里查查, 或者随便Google一下,就出来答案了
length和sustring是一样的。知道length, 要start and。end。 和susstring没区别
【在 f*******7 的大作中提到】 : 返回string,返回string的话不需要hashmap或set计数吗?
|
j*****8 发帖数: 3635 | 10 返回string的话,用两个int记start和end就行
边扫边更新
【在 f*******7 的大作中提到】 : 返回string,返回string的话不需要hashmap或set计数吗?
|
|
|
f*******7 发帖数: 943 | 11 我的意思是如何计distinct这个个数啊
比如这个case
abcabcd 3 返回abcabc, 当startIndex = 0时,endIndex = 3时nums[3] = a, 此时
distinctCount = 3, 当endIndex = 4时,distinctCount依然是3,如何update这个
distinctCount啊
【在 b**********5 的大作中提到】 : 你去我blog里查查, 或者随便Google一下,就出来答案了 : length和sustring是一样的。知道length, 要start and。end。 和susstring没区别
|
j*****8 发帖数: 3635 | 12 当新char不在map的keySet里,且 keySet的size == 3
【在 f*******7 的大作中提到】 : 我的意思是如何计distinct这个个数啊 : 比如这个case : abcabcd 3 返回abcabc, 当startIndex = 0时,endIndex = 3时nums[3] = a, 此时 : distinctCount = 3, 当endIndex = 4时,distinctCount依然是3,如何update这个 : distinctCount啊
|
e***i 发帖数: 231 | 13 崇拜
Orz
牛肉姐还在努力进推特么?
【在 b**********5 的大作中提到】 : 你去我blog里查查, 或者随便Google一下,就出来答案了 : length和sustring是一样的。知道length, 要start and。end。 和susstring没区别
|
b**********5 发帖数: 7881 | 14 哎, twitter现在不是需要engineer, 是他妈的需要product visionary和CEO。。。
Jack dorsey两个公司。。。 我看还不如让我当CEO。。。 好好一个twitter, 竟然去
花时间搞moments。。 这是谁的他妈的idea??! 他妈的, curated news, 像
facebook, flipboard都有, 谁他妈的去看curated news??!! 那些想出来
moments的, 都他妈的需要fire掉!
我觉得increase word limits是好事, 这个要尽快执行
还有, twitter的ads, 需要提高质量。 twitter上面的ads, 我一个都没click过。
。。和我都没关系。。。
现在你看tv新闻,一有什么breaking, 你看espn quote 谁谁谁, 都是从twitter上
quote来的。 twitter可以explore一下, charge这些news outlet, 引用费, 然后
可以和user share 这个profit
twitter还需要的就是speech to text。。。我现在看periscope video, comment时,
打字太慢了。
twitter的future, 不能只靠现在这些word tweets。 需要靠periscope, Virtue
reality。 可以把google glass这种东西, 发展起来。 要有一个glass, 通过这个
glass, 就能把你看到的东西, realtime broadcast到periscope上。
【在 e***i 的大作中提到】 : 崇拜 : Orz : 牛肉姐还在努力进推特么?
|
k**l 发帖数: 2966 | 15 找一个大家喜欢的创新点难啊
说实话我挺喜欢facebook的广告,不太多,而且确实是我感兴趣的,不像chrome按关键
字找些不伦不类的东西来给我看
【在 b**********5 的大作中提到】 : 哎, twitter现在不是需要engineer, 是他妈的需要product visionary和CEO。。。 : Jack dorsey两个公司。。。 我看还不如让我当CEO。。。 好好一个twitter, 竟然去 : 花时间搞moments。。 这是谁的他妈的idea??! 他妈的, curated news, 像 : facebook, flipboard都有, 谁他妈的去看curated news??!! 那些想出来 : moments的, 都他妈的需要fire掉! : 我觉得increase word limits是好事, 这个要尽快执行 : 还有, twitter的ads, 需要提高质量。 twitter上面的ads, 我一个都没click过。 : 。。和我都没关系。。。 : 现在你看tv新闻,一有什么breaking, 你看espn quote 谁谁谁, 都是从twitter上 : quote来的。 twitter可以explore一下, charge这些news outlet, 引用费, 然后
|
a***u 发帖数: 383 | 16 需要啊,双指针,用hashmap记录 start和end之间每个char的次数,如果map size超过
m,start就往前走,直到map size=m位置。最后每个char visit2次 O(2n)=O(n)
【在 f*******7 的大作中提到】 : 返回string,返回string的话不需要hashmap或set计数吗?
|
m****u 发帖数: 3915 | 17 charge news source这个idea就是杀机取卵啊
那么多新闻网站quote你twitter的内容你应该高兴都来不及才对,还敢收费?收费了人
家就去quote instagram上的内容了,小札做梦都笑醒了
【在 b**********5 的大作中提到】 : 哎, twitter现在不是需要engineer, 是他妈的需要product visionary和CEO。。。 : Jack dorsey两个公司。。。 我看还不如让我当CEO。。。 好好一个twitter, 竟然去 : 花时间搞moments。。 这是谁的他妈的idea??! 他妈的, curated news, 像 : facebook, flipboard都有, 谁他妈的去看curated news??!! 那些想出来 : moments的, 都他妈的需要fire掉! : 我觉得increase word limits是好事, 这个要尽快执行 : 还有, twitter的ads, 需要提高质量。 twitter上面的ads, 我一个都没click过。 : 。。和我都没关系。。。 : 现在你看tv新闻,一有什么breaking, 你看espn quote 谁谁谁, 都是从twitter上 : quote来的。 twitter可以explore一下, charge这些news outlet, 引用费, 然后
|