LeetCode练习心得&&C++编程小技巧（常更）

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); //去除结尾空格和制表符```

2016.9.13星期二（Q66）
* 对算法适用范围的小思考：
     * 没有算法是绝对正确的，只有在某些条件下该算法才能够正确运行。
     * 某些条件：最简单的例子，边缘特性，在循环的block之边缘，block里的代码并不能正确运行或者说并不能产生最终正确结果。这时候需要把特殊的边缘单独拿出来处理，以获得正确的最终结果。


2016.9.14星期三（Q67）
* Python：类型转换超级方便，不需顾虑。 程序耗时 47ms。
* C++ ：类型转换很麻烦，特别是int类型转为string类型。 程序耗时 3ms。
* C++ 小技巧： string类型的构造，当int为个位数时，可先int先直接转为char,再构建string。
* 或者自己写一个转换函数：

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

2016.9.19星期一（Q70）

• 爬楼梯问题

  
  1
  

  美丽的斐波那契数列问题：
  (n)问题的解即为为(n-1)子问题和（n-2）子问题的解的和。（n>=3）

2016.11.13星期日（Q123）

• 买股票问题（最多买两次）（很棒的一道题）（用到动态规划与分而治之）
  源代码如下

 int maxProfit(vector<int>& prices) {
        int size = (int)prices.size();
        if(size<2){
            return 0;
        }
        int temp = 0;
// 动态规划：当纳入第i个元素时，利润的变化（基于i-1个元素结果上的变化）
        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]);
        }
//  要点：左一次右一次，左利润在右利润的左边
// 最大利润是两次的结合或者一次最大值
        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