2015-8-22 周六 晴
早晨五点起床，五点半出门，在路上喝了碗八宝粥算是早餐。手拎着背包，包里装了一瓶水，遮阳帽，钱包，手机。之所以手拎着背包，是因为这样能保证一只手臂能压得很低，在放松手臂的同时，也保证降低速度，不跑那么快。
六点开跑。起点在沙河，出发时拍了一张照片，太阳刚刚出来，气温还不太高，真是跑步的好天气。

跑步过程中，发现脚上穿的亚瑟士GT2000太紧了，这双鞋子，刚买回来的时候就有点紧，平时都是穿薄丝袜能勉强穿上，今日却穿的双运动袜子，鞋太紧，脚底板一直处于紧绷状态，得不到放松，脚腕也明显受其影响，放松不下来。这样持续了刚开始起步的五公里，由于担心左膝受伤，中途几次想放弃这次跑步计划。直至七公里的时候，身体慢慢适应了这种节奏，小腿和脚腕才慢慢有放松感。使用大腿带动小腿和脚腕跨步，小腿和脚腕完全放松，不用力，这种感觉很是舒服。甚至有种幻觉，跑步就是在放松。

路上的景色很美，特别是进入昌平城区之后的水库路上，树林成荫。

进入十三陵水库后，大约跑了有17公里左右。中间由于百度地图导航错误，多跑了两公里。

十三陵水库果然是跑步、骑行的好地方，路上一直有很多骑车的人，从身边经过。跑步的人也不少，在路上还遇到了一个跑步组织的休息饮水处。

跑步总结：
1、跑步总计22公里，2小时27分，配速6'38''。结束后佳明手表提示VO2 MAX 44，马拉松成绩预测为3:45。呵呵，现在心肺能力提高了，膝盖却成了瓶颈。
2、能保护膝盖的不是昂贵的鞋子，而是你放松的跑姿。
3、放松的跑姿：忘记你正在跑步这件事。完全的放松，放松的小腿，放松的脚腕，放松的脚底板和持续发力的大腿。
4、每周务必有一次 LSD 拉练，这样才能保证身体有充足的耐力。
5、跑步状态小结：

3公里：刚热身；
7公里：身体刚放松
15公里：身体状态最佳，再次调整跑姿，处于跑而不累的状态，跑就是放松。
20公里：气温升高，身体缺水，有点疲劳，跑姿明显变形，脚腕无法放松，大腿无力，步子拖拉。
6、平时仍然需要多做力量训练，力量是成绩和耐力的基础。

题目：
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_6

   /              \
___2__          ___8__

/ \ / \
0 _4 7 9

     /  \
     3   5 

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路：
二叉树两个节点的最近的父节点。二叉树遍历，从根节点遍历左节点和右节点，判断当前节点是否包含两个节点，如果是的话，马上停止遍历，第一次出现的2的时候，即为最近的父节点。如下图，如果目标是寻找3和5的LCA，首先进入6->2->4，那么在4节点先知道该节点包含2个节点，则停止遍历。算法复杂度：O（logN）

_6

   /              \
___2__          ___8__

/ \ / \
0 _4 7 9

     /  \
     3   5

代码：

/**

• Definition for a binary tree node.
• struct TreeNode {
• int val;
• TreeNode *left;
• TreeNode *right;
• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
• };
  */

class Solution
{
public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    m_pAncestor = NULL;

    HasNodeCount(root, p, q);

    return m_pAncestor;
}

//if it return 2, it's the common ancestor,-1 is find it
int HasNodeCount(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if (root == NULL)
    {
        return 0;
    }

    int node_count = 0;
    int left_count = 0;
    int right_count = 0;
    int cur_count = 0;

    if (root->left != NULL)
    {
        left_count = HasNodeCount(root->left, p, q);
    }
     
    if (root->right != NULL)
    {
        right_count = HasNodeCount(root->right, p, q);
    }

    if (p != NULL && root->val == p->val)
    {
        cur_count++;
    }

    if (q != NULL && root->val == q->val)
    {
        cur_count++;
    }

    if (left_count == -1 || right_count == -1)
    {
        return -1;
    }

    node_count = left_count + right_count + cur_count;
    if (node_count == 2)
    {
        m_pAncestor = root;
        return -1;
    }

    return node_count;
}

private:

TreeNode* m_pAncestor;

};

总结：
1、理解Lowest Common Ancestor of a Binary (LCA)，即最近父节点。
2、使用迭代的算法，一定要找到其终结点。比如该终结点是 return -1；和return 0;
3、代码比较紊乱，不想整理了，等下次刷题时再优化吧。

受到网络上一组父子每年一张的照片启发，决定给我们家米粒也来每年在同一个时间同一个地点拍摄一张照片，直至我们老去。也是件幸福之事。

时间：2015年~未来很久
地点：奥林匹克森林公园
人物：米粒的爸爸、妈妈和其他亲人（谁在北京就跟谁一起留影吧 O(∩_∩)O~）

第一年、2015年8月9日 晴 周日 奥林匹克森林公园

目的：
鞭策自己在养孩子的道路上，能够不随波的夸孩子聪明、夸孩子漂亮、夸孩子帅气，并能带动周围的人。每个孩子都是很聪明的，正是因为这样，更要去培养孩子的认知，不能让他因为别人口中的聪明、漂亮、帅气而成为一个肤浅的人。

文章内容：
刚买了薛涌的新书《天才是训练出来的》。从薛以前的文章看，感觉他是偏向天才天成派的，所以这次看到这个标题就很想知道，是什么让他的观点发生了如此大的转变。

书尚未读完，然而书中大量引用的实验和数据经常让人惊叹不已，不论是支持天成论的还是培养论的，感觉十分过瘾。也许过一阵子我会写一篇整体的读后感，现在先和大家分享一个实验吧。

20世纪90年代，还在哥伦比亚大学教书的Carol S. Dweck进行了一个著名的实验。她把400名七年级的孩子随机分为两组完成很容易的解谜游戏。事后对第一组的孩子不停地夸奖：“你真聪明！”对第二组孩子则称赞：“你一定是非常努力！”接下来，这两组孩子在如下两种解谜游戏中进行选择：一种是容易的游戏，一种则难得多，不过老师告诉他们这组难的游戏可以让他们学到更多的东西。结果，被夸奖聪明的那组孩子，有一半以上选择了容易的游戏；被称赞用功的孩子，则有90%选择了难的游戏。

Carol S Dweck和她的同事用同样的方法对纽约市12所学校100名五年级的学生进行了另一次研究。这些孩子同样被随机分为两组来做适龄的智商测试题。测试完之后，第一组得到的赞誉是“你真聪明！”第二组得到的是“你真努力！”接下来，这两组学生要对付难得多的智商测试，即八年级程度的测试题。结果，第一组孩子意志消沉，第二组孩子则竭尽全力。最后一轮测试，难度回到第一次测试的水平。第一组被夸奖“聪明”的孩子，成绩居然下降了将近20%；第二组被夸奖“努力”的孩子，成绩则提高了30%。

Carol 接下来的问题是：是什么使这些学生们选择了不同的目标、有了不同的工作态度？她的结论是：前一组学生希望“显示”自己的才能，后一组学生希望“发展”自己的才能。在这里，“才能”对两组学生意味着不同的东西。对于第一组学生来说，才能是先天的、固定的，他们愿意把这种才能一遍又一遍地展示。对于第二组学生来说，才能是一个过程，是在不停的发展之中。这种发展的引擎是自己的努力。所以，他们不愿意重复已经掌握的东西，而急不可待地要闯入新的领域。对这两组学生，失败的意义也不同。第一组学生遇到失败，本能的反应就是“天呀，我不行！”第二组学生遇到失败，则采取了面对现实的态度：“我这套做法看来不行，要换个方法试试。”

Carol S. Dweck甚至利用哥伦比亚大学的脑电图室，让具有这两种精神气质的人回答各种问题，然后给他们回馈，同时检测他们的脑电波活动情况。结果现实，“固态气质”的人特别关心自己所显示出来的能力是什么，特别注意自己的答案是否正确。当你提供一些能帮助他们学习的信息时，他们的脑电波中没有信号现实出任何兴趣。甚至当他们答错了问题时，他们也没有兴趣追究什么是正确答案。“进取气质“的人则对各种问题中所包含的能够增长他们知识的信息感兴趣，似乎并不在乎对这些问题的回答究竟把自己排到什么智力水平上。

这里的道理很简单：固态气质的人，心思全花在琢磨“自己是老几”的问题上，既然他们相信人的素质是固态的，自己究竟是老大还是老二、老三就变得至关重要。所以他们所做的一切就是证明自己，生怕自己不聪明，乃至于通过躲避挑战来躲避失败。进取气质的人则是个学习者，他们为了发现自己的问题，宁愿去尝试失败，因而总愿意迎接新的挑战。

——薛涌 《天才是训练出来的》P175-p177

题目：
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

思路-1：
32位数据，先计算出每位的值存储到一个数组里。然后循环这个数组，使用目标值去比较，若目标值小于当前位的值，继续循环；若当前目标值等于当前位值，计数并终止；若当前目标值大于当前位值，计数并重新计算当前目标值继续循环。算法复杂度：O(2 * 32)

代码-1：

class Solution {
public:

int hammingWeight(uint32_t n) {
    std::deque<uint32_t> nAllVaule;
    for (uint32_t i = 0; i <= 31; i++)
    {
        uint32_t cur_vaule = pow(2, i);
        nAllVaule.push_front(cur_vaule);
    }

    uint32_t letf_value = n;
    int count = 0;
    for (uint32_t i = 0; i < nAllVaule.size(); i++)
    {
        if (letf_value < nAllVaule[i])
        {
            continue;
        }

        if (letf_value == nAllVaule[i])
        {
            count++;
            break;
        }

        if (letf_value > nAllVaule[i])
        {
            count++;
            letf_value = letf_value - nAllVaule[i];
            continue;
        }
    }

    return count;
}

};
思路-2：
当前剩余值除2，若除不尽则计数，n取 n/2；若n为0，则终止。算法复杂度：O(16)
代码-2：

class Solution {
public:

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        if (n {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 2 == 1) {
            ++count;
        }
        n /= 2;
    }
    return count;
}

};
总结：
1、该算法较简单，但思路有很多种，比如爆破法（思路-1），即从最大位开始模糊匹配，较为复杂；还有一种就是取模法（思路-2）。
2、爆破法和取模法的算法复杂度相差还是很大的，官网上的显示是爆破法：15ms，取模法的时间是5ms；相差三倍
3、提交错误地方: typedef std::deque Deque; 这是一个类型的声明，而不是一个变量的声明，std::deque nQeque;这样才是一个变量。