刷题感想（一）

在刷 TWO SUM 的题目的时候，首先用最笨的方法做了一遍。然后就想有没有更快的方法。直觉是应该有的。但是想了半天没想起来。汗。关键问题就是知道了一个数之后，怎么找到另外一个数在数组中的位置。其中想到了排序。但是排序也没有快多少，而且位置也会乱掉。然后就想不出来了。其实忘记了关键问题不是排序，而是查找。排序最快好像也就是O(N)LOG(N)。 但是查找最快可以是 O(1)。 再想一下的话，应该就会想到HASH TABLE。典型的用空间换时间。 以后还是要再多想想。

 

后来又刷了一道STRING的题目。N年不用C++了，发现STRING 居然不会用了。想把STRING的每个位置赋值的时候，我直接写的下面几行

 

string str1;

for (int i=0; i< 3; i++)

   str1[i]= 'a';

 

结果跑起来怎么也不对。后来想是不是没有用NUL字符结尾。发现也不行。最后认真从头看了一下STRING的介绍。发现一个误区是STRING的内存管理。STRING 的BUFFER 也是动态分配的。但是在用 OPERATOR [ ] 的时候，只是访问已经分配好的内存，而不会分配新的内存。 在上面程序中，如果把第一行改成  

    string str1="xxxxxx".

那么就可以输出一些字符了。最后发现正确的写法是只要把上面程序的第三行改成下面就行：

   str1.push_back( 'a' );

 

push_back() 是会自动分配空间的。