一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1013|回复: 10
收起左侧

求教一道狗家的变形题

[复制链接] |试试Instant~ |关注本帖
hidden_track 发表于 2016-5-27 02:36:46 | 显示全部楼层 |阅读模式

() @ - -  |

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
LC 340         Longest Substring with At Most K Distinct Characters  这题如果cannot fit into memory应该怎么处理呢?多谢!!
newbiee 发表于 2016-5-27 03:30:24 | 显示全部楼层
哈哈,我onsite就背面到了这题,我是这么做的: 用hashmap [char, int] 碰到已有的单词,更新新的位置,没有则往里面家,如果map size 超出 k, 删去所有map value中最小的那个key;
.1point3acres缃
补充内容 (2016-5-27 03:31):
输入时 infinite char stream
回复 支持 1 反对 0

使用道具 举报

hison7463 发表于 2016-5-27 02:55:50 | 显示全部楼层
你是说K number of Integer cannot fit into memory?还是说给的String cannot fit?
回复 支持 反对

使用道具 举报

 楼主| hidden_track 发表于 2016-5-27 02:59:44 | 显示全部楼层
hison7463 发表于 2016-5-27 02:55
你是说K number of Integer cannot fit into memory?还是说给的String cannot fit?

Given String cannot be fitted in the memory
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-5-27 03:22:43 | 显示全部楼层
hidden_track 发表于 2016-5-27 02:59
Given String cannot be fitted in the memory
.1point3acres缃
那应该还是双指针吧,一个left指针和一个i指针,每次把i指针里的元素填到hashmap里,如果发现hashmap的size大于k,从left开始一个个往左删,知道hashmap的size是k,然后比较一下长度
回复 支持 反对

使用道具 举报

 楼主| hidden_track 发表于 2016-5-27 03:35:46 | 显示全部楼层
newbiee 发表于 2016-5-27 03:30
哈哈,我onsite就背面到了这题,我是这么做的: 用hashmap [char, int] 碰到已有的单词,更新新的位置,没 ...

明白了,多谢!您方便私信下面筋吗?我下周二去MTV面。。求好运
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-27 03:46:39 | 显示全部楼层
// using a queue to push the characters.   
int longestSubstringWithKDistinct(string s, int k) {  
  if(s.size() <= k) return s.size();  .鏈枃鍘熷垱鑷1point3acres璁哄潧
  int i = 0;  
  int maxSize = 0;  .鏈枃鍘熷垱鑷1point3acres璁哄潧
  queue<char> chars;  
  unordered_map<char, int> hashMap;  . 鍥磋鎴戜滑@1point 3 acres
  while(i < s.size()) {  
    chars.push(s);  
    hashMap[s]++;  
    while(hashMap.size() > k) {  
      char ch = chars.front();   鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      chars.pop();  
      hashMap[ch]--;  
. from: 1point3acres.com/bbs       if(hashMap[ch] == 0) hashMap.erase(ch);  
    }  
    maxSize = max(maxSize, (int)chars.size());  
    i++;  
  }  
  return maxSize;  . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}  
  
// two pointers.  
int longestSubStringK(string s, int k) {  
  if(s.size() <= k) return s.size();  
  vector<int> hashMap(256, 0);  
  int maxSize = 0;  
  int count = 0;  
  int i = 0;  
  int j = 0;  
  while(i < s.size()) {  
    if(hashMap[s] == 0) {  .1point3acres缃
        hashMap[s]++;  
        count++;  
    } else {hashMap[s]++;}  . visit 1point3acres.com for more.
    if(count > k) {  
      maxSize = max(maxSize, i - j);  
      while(--hashMap[s[j++]] > 0) {  -google 1point3acres
      }  
      count--;  
    }  
    i++;  
  }  
  maxSize = max(maxSize, i - j);  
  return maxSize;  
}  
  
int main(void) {  
  cout << longestSubstringWithKDistinct("ecebaddde", 2) << endl;  
  cout << longestSubStringK("ecebaddde", 2) << endl;  
}  

补充内容 (2016-5-27 03:51):
不能fit memory的话,把第一个while 改成isstringstream 或者getchar,就可以了,感觉没什么区别。。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-27 03:47:41 | 显示全部楼层
newbiee 发表于 2016-5-27 03:30
哈哈,我onsite就背面到了这题,我是这么做的: 用hashmap [char, int] 碰到已有的单词,更新新的位置,没 ...

不能删除key最小的。因为要求substr
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-27 05:47:04 | 显示全部楼层
每次一个个字符读进来还是每次读内存大小的字串?如果每次读一个,移动指针的时候怎样更新hashmap呢?
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-27 06:37:33 | 显示全部楼层
jy_121 发表于 2016-5-27 05:47
每次一个个字符读进来还是每次读内存大小的字串?如果每次读一个,移动指针的时候怎样更新hashmap呢?

啥意思?没明白,第一个i是一直增加的,j 一直比i小,有啥问题么?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-27 07:32:43 | 显示全部楼层
blackrose 发表于 2016-5-27 06:37
啥意思?没明白,第一个i是一直增加的,j 一直比i小,有啥问题么?

就是想问下你这个two pointer解法的输入s是什么?是全部的字符串还是每次读一部分进来?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表