2016.9.12周一（Q58）

• 字符串去掉頭尾空格

 string s="      That is a string       ";
 s.erase(0, s.find_first_not_of(" \t")); //去除開頭空格和制表符
 s.erase(s.find_last_not_of(" \t")+1); //去除結(jié)尾空格和制表符```

2016.9.13星期二（Q66）
* 對算法適用范圍的小思考：
     * 沒有算法是絕對正確的，只有在某些條件下該算法才能夠正確運行。
     * 某些條件：最簡單的例子，邊緣特性，在循環(huán)的block之邊緣，block里的代碼并不能正確運行或者說并不能產(chǎn)生最終正確結(jié)果。這時候需要把特殊的邊緣單獨拿出來處理，以獲得正確的最終結(jié)果。


2016.9.14星期三（Q67）
* Python：類型轉(zhuǎn)換超級方便，不需顧慮。 程序耗時 47ms。
* C++ ：類型轉(zhuǎn)換很麻煩，特別是int類型轉(zhuǎn)為string類型。 程序耗時 3ms。
* C++ 小技巧： string類型的構(gòu)造，當int為個位數(shù)時，可先int先直接轉(zhuǎn)為char,再構(gòu)建string。
* 或者自己寫一個轉(zhuǎn)換函數(shù)：

string getstring ( const int n )
{
std::stringstream newstr;
newstr<<n;
return newstr.str();
}```
注：需要引入頭文件<sstring>

2016.9.19星期一（Q70）

• 爬樓梯問題

  
  
  1
  
  

  美麗的斐波那契數(shù)列問題：
  (n)問題的解即為為(n-1)子問題和（n-2）子問題的解的和。（n>=3）

2016.11.13星期日（Q123）

• 買股票問題（最多買兩次）（很棒的一道題）（用到動態(tài)規(guī)劃與分而治之）
  源代碼如下

 int maxProfit(vector<int>& prices) {
        int size = (int)prices.size();
        if(size<2){
            return 0;
        }
        int temp = 0;
// 動態(tài)規(guī)劃：當納入第i個元素時，利潤的變化（基于i-1個元素結(jié)果上的變化）
        int* dpLeft = new int[size]; dpLeft[0] = 0;
        int* dpRight = new int[size]; dpRight[size-1] = 0;
        temp = prices[0];
        for(int i=1;i<size; ++i){
            temp = min(temp, prices[i]);
            dpLeft[i] = max(dpLeft[i-1], prices[i]-temp);
        }
        temp = prices[size-1];
        for(int i = size-2; i>=0; --i){
            temp = max(temp, prices[i]);
            dpRight[i] = max(dpRight[i+1], temp - prices[i]);
        }
//  要點：左一次右一次，左利潤在右利潤的左邊
// 最大利潤是兩次的結(jié)合或者一次最大值
        temp = 0;
        for(int i=1; i<size-1; ++i){
            temp = max(temp, dpLeft[i]+dpRight[i+1]);
        }
        temp = max(temp, dpLeft[size-1]);
        return temp;
    }

2016.12.25星期日

• 很簡單但很棒的一道題（追及相遇問題思想的應用）

141.png

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
       if(head==NULL)return false;
       ListNode* worker = head;
       ListNode* runner = head;
       while(runner->next!=NULL && runner->next->next!=NULL){
           worker=worker->next;
           runner = runner->next->next;
           if(worker==runner) return true;
       }
       return false;
    }
};

2016.1.12星期四

• 很好地利用n/2這個特性

169Q.png

169S.png