刷題感想（一）

在刷 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() 是會自動分配空間的。