Skip to content

Latest commit

 

History

History
 
 

037. Count and Say

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题也没有着重考察什么知识点,顶多是考察字符串处理的经验。

我非常喜欢 C 语言,工作三年,有那么两年都是用纯 C 来做项目的,但为何后来投靠了 C++ 呢?因为 C 语言最大的弱项在于字符串处理。你说自己封装一个 string,没问题,并不难。 但这纯属重复造轮子,且不论你造的好与不好,在工作中用自己造的轮子,压力有多大,谁试试谁知道。

而 STL 里的 string,虽然也有一些问题,也没那么好用,但毕竟是规范,毕竟具备通用性。

这道题我先开始拿到非常费解,不知道如何下手,于是手动列出一个表:

n ret
1 1
2 11
3 21
4 1211
5 111221
6 312211
7 13112221
8 1113213211

列出了这个表,规律十分明显:

  • 我们起码要循环 n 次,才可以从 n==1 的时候演变而来。
  • 每一次演变,我们需要迭代上一次的字符串,然后遇到重复项,要归纳总结。
str.replace(b, e, std::to_string(e-b) + *b);

这个 replace 基本展现了我对于演变的理解,这不过这个步骤需要反复迭代。而 replace 却会破坏 iterator,不得已我重新弄了个 string,来避免 iterator 的破坏。

但仍然是把握上述两个规律。

看了这道题的讨论,几乎都是在说题意不清晰,但几乎没有特别好的解法。我的解法非常直接简单,效率图上,却显然不是最优的,如果有人知道简洁且效率最优的解法,一定要告诉我,给我当头来一棒!