一亩三分地论坛

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

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

[算法题] 求大神指点 input 是 stream 的题 应该怎么答?

[复制链接] |试试Instant~ |关注本帖
queeniejing 发表于 2015-11-24 04:17:09 | 显示全部楼层 |阅读模式

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

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

x
看到很多面经都有关于 input 是 stream 的题: 比如下面这个 longest substring with no more than N distinct characters; the input is a stream and 内存 is limited.    这种stream 的题 考点是什么? 应该怎么回答呢? LZ只是知道 stream 的话 要一个一个读。  求大神指点啊!!
stellari 发表于 2015-11-28 23:40:38 | 显示全部楼层
考点是:

1. “内存有限”==“不能保存stream所有的输入”,也就是说,当“取得元素i以后,你将只能保存元素 0, 1... i-1中的一部分,而不可能全部保存”;

2. “输入是stream”==“不能回顾”,也就是说,当“一旦取得元素i后未保存,那么将无法再获得元素i”

因此对这类问题,就不能使用需要“逆向扫描”,“二次扫描”之类的算法,也不能使用O(length of stream)级别的内存。

具体到这道题,如果不加内存限制的话,我可能会写出如下代码(注:longest substring with N distinct characters以下缩写为LSND):
  1. int getLSND(string s, int n) {
  2.     unordered_map<char, int> hist;  // 不变量是hist.size()==n
  3.     int i = 0;
  4.     int maxLen = 0;
  5.     for(int j = 0; j < s.size(); ++j) {
  6.         hist[s[j]]++;      
  7.         while (hist.size() > n) { // 若不变量被破坏,则重新恢复之
  8.             hist[s[i]]--;
  9.             if (hist[s[i]] == 0) hist.erase(s[i]);
  10.             i++;
  11.         }
  12.         maxLen = max(maxLen, j-i+1); // 在满足不变量的情况下求当前最大值
  13.     }
  14.     return maxLen;
  15. }
复制代码
原理是保存一个最大长度为n的map,其中保存的是"s[i..j]这个子串中的各字符的出现次数"。每将j前进1,就检查s[i..j]是否依然满足条件。如不满足,则 i++直至满足。然后看此时的s[i..j]的长度是否为当前最大。

但是上面的方法需要知道s[i..j]这个子串的全部内容,所以如果内存有限,这个方法就不行了,因为i和j之间的距离可能会相当大。保存这个子串所需的内存是O(s.size())级别的。

至于如何避免这个问题,我只能想到一个使用LRU队列的算法。大致意思是:

1. 维护一个最大长为N的队列q,其中每一个元素代表一种字母在“目前的LSND中最后一次出现的位置”。比如输入序列是
"aaabbccabbda...",N = 3. 那么当我们即将前进到倒数第二个元素d时,此时的LSND是"aaabbccabb",里面有3个不同字母:a、b、c。
它们最后一次出现的位置分别是:7,9, 6。所以q中的内容就是:[{6, 'c'}, {7, 'a'}, {9, 'b'}]

2. 维护一个map,使得可以从a, b, c等字符快速找到其在q中的位置。

3. 维护双指针i和j,分别表示“以当前字符结尾的LSND的开始位置”和“当前字符的位置”、

4. 每次从stream中读取一个字符ch。如果ch已经在q里面,那么就将其移到q队尾,并且改写它的出现位置;如果ch不在q里面,(如果此时q已经有N个元素,那么就先删掉q中最前面的那个元素),将其加入q队尾。

5. 完成4以后,如果发现q最前面的元素被删了,那么同时需要更新i。然后看此时j-i+1的值是否为目前最大。

还是举上面的例子:比如现在已经读到了'd'。(此前的LSND是aaabbccabb。i = 0,j = 9). 这时我们发现'd'不在q中,而q已满。为了达到“加入'd'以后q仍然还是一个SND"这一条件,我们必须删除掉开头许多字符,使得“恰好一种字母完全从q中消失”。显然,最先消失的应是目前位于q开头的'c',所以我们直接删除掉q的头元素'c',然后将i的位置至于“最后一个c位置+1”=6+1=7 处。此时的LSND是“abbd”,长度是 j - i + 1 = 10 - 7 + 1 = 4。

啰嗦了这么一堆,其实代码也不算难。也许有更简单的方法,但是我的思路只能到这个水平了:

  1.     int getLSND(stringstream& iss, int n) {
  2.         list<pair<int, char> > q;      // 当前有效序列
  3.         unordered_map<char, list<pair<int, char>>::iterator> last_c_pos;  // “每种字母”在“当前有效序列”中的位置
  4.         int i = 0, j = 0;
  5.         int maxLen = 0;
  6.         char ch = '\0';
  7.         for (; iss >> ch; ++j) {
  8.             if (last_c_pos.count(ch)) {   // 如果这个字母在当前有效序列中已存在
  9.                 auto iter = last_c_pos[ch];
  10.                 (*iter) = {j, ch};  // 更新队列中这个字母最后一次出现的位置
  11.                 q.splice(q.end(), q, iter);    // 将其移到队尾
  12.             }
  13.             else {  //如果这个字母并不存在
  14.                 if (q.size() == n) {  // 但是之前的有效序列已经满了
  15.                     pair<int, char> c= *q.begin(); // 获取最先结束的字母
  16.                     i = c.first+1;
  17.                     last_c_pos.erase(c.second);
  18.                     q.pop_front();
  19.                 }
  20.                 q.push_back({j, ch});
  21.                 last_c_pos[ch] = std::prev(q.end());
  22.             }
  23.             maxLen = max(maxLen, j-i+1);
  24.         }
  25.         return maxLen;
  26.     }
复制代码

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| queeniejing 发表于 2015-11-29 13:22:44 | 显示全部楼层
大神 你好棒 解释得好清楚  赞赞赞
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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