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
