问一道题目

问一道题目
对于任何一个string,如 uuuwioo 如何输出结果u3w1i1o2, 用什么数据结构? hash 不行
多谢

argumentt 发表于 2019-1-8 08:55
这个不用数据结构，直接brute force从头扫到尾。如果当前字符和前一个字符一致，就counter+1然后直接看下一 ...

你的解法是对的。我当时也是这么想的。不过没写出来程序。最近状态不佳。不过面试官说有一种数据结构可以用，而且他说我一定知道，但是他没有告诉我。 我现在也不清楚是哪个数据结构。

hs9906 发表于 2019-1-8 09:07
抛砖引玉，假设只是小写的话，用26个字母的数组存出现次数。不知道你所谓的hash不行是指的不让用hash table ...

面试官说hash 用在这里是错的，我也觉得hash 用在这里是错的。他说有种数据结构可以用在这里，不过没有告诉我是哪个数据结构，他说我一定知道。

微信用户_0x045 发表于 2019-1-9 05:07
难道是链表？每个结点存字母和连续出现次数。每出一个和上个不同的字符就开一个新结点……

linked list? 可能吧。不过按照面试官的意思估计没这么高级。

这个不用数据结构，直接brute force从头扫到尾。如果当前字符和前一个字符一致，就counter+1然后直接看下一个；如果不一致就把前一段的结果记录到最终结果里，更新当前字符并且counter清零，接着读。

抛砖引玉，假设只是小写的话，用26个字母的数组存出现次数。不知道你所谓的hash不行是指的不让用hash table还是这个思路都不让。毕竟这个解法也是hash的思路，只不过是自己构建的。

虽然只是扫一遍就能做完的但是也有个专有名词叫游程编码...

需要in place么

这个程序不难，只是我最近状态不佳。

xiaoxiaoc 发表于 2019-1-8 11:07
面试官说hash 用在这里是错的，我也觉得hash 用在这里是错的。他说有种数据结构可以用在这里，不过没有告 ...

难道是。。。 map?

补充内容 (2019-1-8 11:37):
em...我说的map其实也是hash表。。 弱菜发出去才反应过来T_T

Hash是不行的，因为前后字符可能有重复，比如aabcccaa这种，没法知道一个重复是前后连续的字符重复还是不连续的字符串重复，最后还是要靠比较前后两个字符。如果是in place就比较复杂，比如像abcd这种情况需要插入